When does Quora approve the requested space

Master thesis. Coherent web caching of database objects in cloud computing


1 University of Hamburg Faculty of Mathematics, Computer Science and Natural Sciences Master's thesis Coherent web caching of database objects in Cloud Computing Felix Gessert Study course Computer Science (MSc) Mat. No. Subject semester 4 Florian Bückler's study course Computer Science (MSc) Mat. No. Subject semester 4 First reviewer: Second reviewer: Professor N. Ritter Professor W. Lamersdorf


3 Felix Gessert, Florian Bücklers I Coherent Web Caching of Database Objects in Cloud Computing Felix Gessert, Florian Bücklers Abstract. The science and practice of database systems is currently in one of the most radical upheavals in its history. Three paradigm shifts can be clearly identified: the change from the dominant relational data model to domain-specific, requirement-dependent data models and databases (NoSQL, Polyglot Persistence), the alignment of many databases to technologies of the web and its dimensions (horizontal scalability, big data) and the increasing shift in Data processing and storage on cloud computing platforms. In order to meet this paradigm shift in a technically appropriate manner, many innovations are necessary. In this thesis we describe how horizontal scalability and low network latencies can be achieved through web caching for databases based on web technologies, cloud computing and established algorithms. The challenge and originality of our approach lies in the requirement not to restrict the consistency and transactionality of database access. The practical and empirically evaluable implementation takes place in the ORESTES system (Objects RESTfully Encapsulated in Standard Formats). Specifically, we show how bloom filters (a probabilistic data structure for quantities) can be used to ensure that clients always read the latest data from web caches. We statistically prove the higher performance of our Bloomfilter implementation in several variants compared to existing implementations. In addition, we investigate and implement the use of content delivery networks and reverse proxy caches as a caching layer for database objects. The combination of ORESTES with the new techniques of cache coherence results, as we will show, in a database access protocol that is able to use the scaling mechanisms of the web (such as load balancing and web caching) in accordance with the requirements of modern database systems.

4 II Coherent web caching of database objects in cloud computing Contents 1 Introduction ORESTES motivation for a cloud-compatible persistence protocol concept The ORESTES REST / HTTP protocol Scaling model Implementation of cloud computing database-as-a-service Analysis of the DBaaS ecosystem Benchmark results for ORESTES in a cloud scenario Problem The Cache Coherence Related Work Coherent Web Caching ACID Transactions Without Cache Coherence Serialization Graph Testing (SGT) Timestamp Ordering FOCC and BOCC BOCC + and Optimistic Locking Summary Basic Concept Sorted Lists Balanced Search Trees Hash Tables Bloom Filters and Their Mathematical Properties Applications Summary Cache BigTable Variants Counting Bloom Filter Materialized Counting Bloomfilter ... 81

5 Felix Gessert, Florian Bücklers III Bitwise Bloomfilter Spectral Bloomfilter Bloomier Filter Stable Bloomfiler A 2 Bloomfilter Existing implementations Bloomfilter by Magnus Skjegstad Bloomfilter by Ilya Grigorik Implementation The Redis Bloomfilter Simple Redis Bloomfilter Redis Bloomfilter with Bit-Array Countern Redis Bloomfilter Comparison with explicit cryptographic counsel Hash functions Non-cryptographic hash functions Random generators Universal hash functions Checksums Hash quality Performance aspects Bloom filter as a compressed write log Window Evaluation Summary Cache Invalidations Reverse proxy cache: Varnish content delivery networks CDN structure Server structure Interaction protocols

6 IV Coherent web caching of database objects in cloud computing Content distribution Selection of content Update strategy Network latency of various CDNs Amazon CloudFront infrastructure Supported content types Cache behavior and update Invalidation API Evaluation The Orestes Invalidation Service Web caching and CDNs Evaluation Outlook Polyglot Persistence Implementation of Polyglot Persistence: Redis Implementation of new persistence APIs: JSPA Java Persistence API (JPA) Introduction to JSPA architecture Synchronization of operations via the queue Future Work Conclusion A List of figures B Sources and references C Division of work D Explanation

7 Felix Gessert, Florian Bücklers 1 1 Introduction Several upheavals are currently taking place in database systems and in the entire science and practice that deals with them. For about three decades, relational databases dominated the market almost without restriction [1]. But with the equally dominant position of the web and the exponentially growing amounts of data (cf. [2]), the requirements shifted increasingly. In our opinion, the range of partly conflicting requirements for a modern database system is fed by four categories: NoSQL [3], Big Data [4], Cloud Computing [2] and classic database theory [5]. In this work we want to show that an arc can be drawn between them and that the necessary technical prerequisites can be created. In order to make this ambitious goal feasible, it is absolutely necessary to fall back on numerous existing and established implementations and research results. In this thesis we are building on a system that we presented for the first time in our bachelor thesis [6]: ORESTES (Objects RESTfully Encapsulated in Standard Formats) [7]. It is a REST / HTTP protocol and framework for transactional, object-oriented access to databases. A crucial capability of the protocol is the use of web infrastructure, i.e. web caches and load balancers, as a scaling mechanism for the database system. This is made possible by the mechanism of the so-called optimistic concurrency control [8]: at the time of a transaction commit, it is validated that the client has not read any obsolete object copies from web caches. Despite the performance advantages through the use of web caches, there are two disadvantages that are to be solved in this thesis. On the one hand, these are transaction aborts as a result of outdated read results from web caches and, on the other hand, the lack of usability of server-side controllable cache networks (CDNs and reverse proxy caches). In addition, it should be shown that the developed techniques are not limited to the object-oriented data model and corresponding databases, but can be transferred to other data models and database systems. By synthesizing ORESTES with the new techniques for cache coherence, we want to meet the changed requirements for modern database systems, which we will now explain. In retrospect, the NoSQL movement has two primary motivations [3], [9], [10]: The realization that easily usable data models and interfaces can significantly improve the productivity of application development. The need to run databases on clusters in order to keep the load and data volume horizontal scale From the success of the NoSQL movement, we therefore derive two necessary requirements: enabling horizontal scalability (I) and transparent and intuitive data November

8 2 Coherent web caching of database objects in cloud computing bank interface (II). All representatives from the broad spectrum of NoSQL solutions have in common that they do not claim sole representation as a generally applicable data solution. Rather, they refer to a paradigm shift towards polyglot persistence [9], i.e. the coexistence of database systems in which each system takes on a specialized task. This results in the requirement that a modern database system should accept and support the paradigm of polyglot persistence (III). Another common attribute of NoSQL solutions is their web orientation [11]. This manifests itself on the one hand in the widespread use of JSON (JavaScript Object Notation) [12] as a schema-less display format and on the other hand in the implementation of database interfaces as REST API [3], [13]. Both of these allow the database system to be used smoothly in web contexts. A third requirement is therefore: Use of web standards (IV). Web standards offer another advantageous application for databases: web-based administration. No application platform reaches as many users as the stack of HTML5, CSS and JavaScript. A database system should use this platform to enable administration, monitoring and deployment (V). On the one hand, this has the advantage that no proprietary management software has to be installed and configured and, on the other hand, it enables easy-to-learn operation with many degrees of freedom in design. Furthermore, this supports the increasing spread of smart clients and single page apps, which can now use persistence as a service without the need for an application server. In addition, the web became an example of the problem of exponentially growing databases and high parallelism. The big data movement arose from the desire to analyze and integrate the huge amount of user- and machine-generated information for analytical purposes [4]. On the one hand, it made it necessary to use new, cluster-compatible data processing models such as MapReduce [14], Dryad [15], Impala [16], Spanner [17], Pregel [18] and Dremel [19] and, on the other hand, database systems with the ability to scale horizontally to be designed for large loads and data volumes [10]. From this we again conclude that a database system for web contexts must have the ability to scale horizontally for both analytical and operational workloads (I). Another engine for new requirements is cloud computing. It opened up a previously unseen usage scenario for databases: the use of a database system as a service (Database-as-a-Service, DBaaS). Instead of setting up and configuring the database system like the application, cloud computing allows a pay-as-you-go business model and largely dispensing with classic database administration. In our opinion, however, the database-as-a-service problem has not yet been resolved. If a client accesses a database deployed as a service in the cloud via a WAN, the network latency is inevitably so high that this leads to a severe performance limitation. However, low latency is critical for high throughput and efficiency of database queries. We therefore demand that a database system must provide a solution for the latency problem in the cloud (VI). Countless additional requirements can be derived from the unparalleled success story of classic database systems.

9 Felix Gessert, Florian Bücklers 3 However, one thing seems to us to be of particularly far-reaching importance: transactions [20]. Transactions are the most successful process to date that is able to make the complexity of concurrent processes controllable through a simple concept without severely restricting concurrent processes. The complexity of the concurrency control is shifted from the application to the database system. Modern NoSQL databases primarily do without transactions in favor of scalability and simplified implementation. However, we believe that a database system should offer transactions as an optional concept (VII). If not, this allows better scalability and otherwise higher productivity and reduced susceptibility to errors in application development. This assessment is shared by the so-called NewSQL movement [21] and the software industry, as the following often quoted statement shows: We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions (from Google Spanner, 2012 [17]). (I) Horizontal scalability (II) Transparent and intuitive database interface (III) Support of Polyglot Persistence (IV) Use of web standards (V) Web-based monitoring, deployment and administration (VI) Access with low network latency (VII) Transactions and strong consistency as Option Figure 1 Requirements. The results of this work are intended to meet these seven requirements for a modern database system. The seven requirements identified are summarized in Figure 1. The previous development of ORESTES has already been based on them. With this work, the requirements of the new mechanisms for cache coherence are to be further implemented. Ensuring cache coherence is divided into two new mechanisms: Prevention of obsolete read results from caches and proactive invalidation of server-controlled caching networks. We will now briefly introduce both of them and explain their implications for the requirements identified. N o v e m b e r

10 4 Coherent web caching of database objects in cloud computing Obsolete cache contents can always be read if a write operation was previously forwarded through other caches. Since the lifespan of the cached objects is characterized by a statically specified period of time, these ad-hoc changes inevitably lead to invalid cache entries. In this thesis, however, we develop a mechanism that we call bloomfilter-based cache coherence. In doing so, the client assumes responsibility for requesting outdated cache content with a revalidation request, so that the affected caches obtain the latest object version from the database. In order to determine which requests must be provided with a revalidation request, the client needs a representation of all changed objects within the time window that corresponds to the caching duration of the objects. The optimal data structure for storing these changes is a bloom filter for a number of reasons. It allows you to check in O (1) whether an object has been changed. In addition, its size is so small that it can be transmitted without any significant overhead at the start of a transaction or on request. The server records every changing operation in the bloom filter and clients query this bloom filter to prevent stale reads. The bloom filter-based cache coherence allows you to create a consistent system from uncontrolled caches that work according to the principle of eventual consistency. Other client CHANGE 2 CHECK BLOOMFILTER 3 1 OBJECT 4 REVALIDATION REQUEST Server Web cache client Figure 2 Bloom filter-based cache coherence. The functioning of the bloomfilter-based cache coherence is shown in Figure 2: 1. If an object is requested via a web cache, the server replies with the requested object, which the web cache stores from now on. 2. If the server receives a change in the delivered object, it also transfers the changes to the Bloom filter. At this point, the copy of the object held in the web cache is stale. 3. Before a client asks for an object, it checks the bloom filter, e.g. is withdrawn at the start of each transaction. 4. Since the change was noted by the server in the bloom filter, the client determines that a revalidation request must be attached to the object request.

11 Felix Gessert, Florian Bücklers 5 The bloom filter-based cache coherence affects almost all points in the catalog of requirements. The horizontal scalability is made possible by the unrestricted usability of web caches even with the boundary condition of strong consistency (I). The transparent database interface is maintained in that the bloom filter can be queried with a simple REST API call (II). The web standards are of course adhered to and the bloom filter is transmitted as JSON objects that can be processed independently of the language (III). Access with low network latency is also influenced. A higher network latency arises with bloom filter-based cache coherence during revalidation. At first glance this may seem like a disadvantage, but in reality it is a remarkable advantage: the significantly higher costs of an otherwise necessary transaction termination are prevented by the one-time acceptance of higher network latency (V). The result is strong consistency for transactions and non-transactional clients alike, who can request updated Bloom filters at random intervals (VI). The second pillar of the desired cache coherence is the combination of server-controlled caches. They include content delivery networks (CDNs) [22] and reverse proxy caches [23]. CDNs are the established infrastructure with which very large websites achieve scalability. CDNs (e.g. Akamai, LimeLight, Cloudfront) maintain worldwide networks of caching servers at positions that are close to potential clients. This means that cached content can be delivered with low latency regardless of the geographic position of the client. Reverse proxy caches are web caches that are set up in the same network as the server and, as its representative, answer HTTP requests and cache objects in the process. The thing that sets reverse proxy caches and CDNs apart from all other web caches is their ability to receive invalidations for cached objects [24].When objects are changed, the server is able to instruct the CDN and the reverse proxy caches to release their saved copy and instead request a new one if necessary. This offers the enormous advantage that with a server that detects changes and propagates corresponding invalidations, the time window of potentially outdated reads for these caches almost disappears. This approach has advantages even in conjunction with bloom filters. For example, Reverse proxy caches can be configured to ignore revalidations and instead deliver cached objects. This protects the server from the potential load that it experiences as soon as an object is always revalidated directly by the server for a period of time by being included in the Bloom filter. The consistency is not reduced because the reverse proxy caches are informed immediately about invalidations. The process of an inquiry in connection with invalidations is shown in Figure 3: N o v e m b e r

12 6 Coherent web caching of database objects in cloud computing 1. If an object is requested via a reverse proxy cache or the CDN, the object is then cached there. 2. If the server receives a change from a client, this change is usually carried out. also pass a cache from the CDN and a reverse proxy cache. These caches can now invalidate their entry. The caches not passed, however, keep the stale entry. 3. Since the server knows of the change, the invalidation subsystem informs all registered reverse proxy caches and the CDN with an invalidation. 4. A client that now requests an object receives the latest version of the object. CHANGE 2 Other client server 1 OBJECT CDN 4 OBJECT Client INVALIDATE 3 Invalidation subsystem reverse proxy cache Figure 3 Use of server-controlled cache networks. The instantaneous invalidation of server-controlled cache networks also has an impact on the requirements. The horizontal scalability is increased by the fact that CDNs and reverse proxy caches can work without restrictions as a scalable caching layer of the server (I). The invalidations also have a special effect on the network latency. Objects that have just been changed are still served from caches. With a global CDN, for example, this means that the latency to the client always remains very low (V). The consistency of CDNs and reverse proxy caches is thereby maintained automatically and without the help of the client (VI).

13 Felix Gessert, Florian Bücklers 7 One limitation of the previous approach by ORESTES is the commitment to the object-oriented model. However, the techniques for scaling through web caches and load balancing as well as the new mechanisms of cache coherence are not limited to this model. We are therefore expanding ORESTES to include the necessary aspects to support Polyglot Persistence (III). We demonstrate this using an example of an implementation to connect a key value store. The ORESTES REST / HTTP interface receives the new abstractions for operations of a key-value store. In addition, we show the advantages of the loose coupling of persistence API and database through the ORESTES protocol: the key-value store can also take over the interface of object-oriented persistence - using existing client APIs. The result is the possibility of high-performance storage of objects at the expense of queries. Since navigating (queryless) access is one of the most common scenarios with object-oriented persistence, object persistence through a key-value store is an interesting option for many use cases. Orestes Server Client Object Database Transactions Key-Value Store Others (e.g. Document Database) 2 4 Queries Object Persistence Schemas Key-Value Persistence Others 1 OBJECT 3 KEY-VALUE PAIR Object Persistence API (e.g. JDO) Key-Value API (e.g. JCache) Others Orestes REST / HTTP interface Client API Figure 4 Polyglot Persistence. The ORESTES protocol receives a new abstraction for storing key-value pairs. The implementation is linked to a key-value store, which can take on object persistence (without queries) on the one hand and key-value operations on the other. The new features of Polyglot Persistence are shown in Figure 4. The capabilities of the ORESTES REST / HTTP interface are also divided into different categories that can be implemented for different database systems as required. The connection of the key-value store can e.g. Go beyond pure key-value persistence and also offer object-oriented persistence and schema management (dashed line). A client has several options: N o v e m b e r

14 8 Coherent web caching of database objects in cloud computing 1. With the help of an object-oriented persistence API, which is based on the ORESTES protocol, the client can save, load, delete objects, etc. 2. Several database systems can offer the functionality on the server side , e.g. an object database (high queries, indexing, etc.) or a key value store (fast in-memory access, high availability, etc.). Due to the decoupling of client and server using the ORESTES protocol, the persistence API on the client side is agnostic to the underlying database system and does not require any new implementation. 3. The client can also use the native key-value interface, which is also offered via the ORESTES protocol. The same techniques for transaction management, web caching, etc. are used that have already been researched and implemented. 4. The call is passed on to the Key-Value Store via a server-side connection. This connection decides which functionalities are to be provided, e.g. whether transactions are supported. We see Polyglot Persistence as an important development. In this thesis we therefore show that the mechanisms of ORESTES are suitable for polyglot persistence and that different databases can benefit equally from the methods for cache coherence investigated in this master’s thesis. This master's thesis thus makes five contributions: We show how database-as-a-service models can be used in practice by solving the latency problem. The concept of the bloom filter-based cache coherence provides a generic principle with which non-invalidatable caches can be operated without loss of coherence. We prove that server-controlled cache combinations of reverse proxy caches and CDNs represent an already existing infrastructure that can be used to scale database systems. We are releasing a Bloomfilter implementation that is superior to other implementations because it offers both distribution and particularly extensive selection options for hash functions. We show that Polyglot Persistence is possible on the basis of a generic protocol (ORES- TES) and that considerable synergies are created, e.g. common web caching techniques. The rest of this work is structured as follows: the remaining parts of the introduction describe ORESTES, the context for the development of the new cache coherence mechanisms. Chapter 2 provides an overview of related research. Chapter 3 discusses the mechanism of bloom filter-based cache coherence, as well as the concepts and techniques for realizing a distributed, high-performance bloom filter with high statistical quality. Capital

15 Felix Gessert, Florian Bückler's 9th tel 4 discusses the connection of server-controlled cache connections and the effects on scalability. Chapter 5 shows the implementation of ORESTES as a Polyglot Persistence Protocol and the usability from JavaScript. Chapter 6 sets out the open questions and potential research directions. Chapter 7 summarizes the results of this work. 1.1 ORESTES Since numerous aspects of ORESTES have already been discussed in our bachelor thesis [6] and an explanatory poster [25] and a website are available, we limit ourselves in this introduction to the essential aspects of motivation, which are decisive for understanding this master thesis for a cloud-compatible persistence protocol The triumphant advance of cloud computing and NoSQL shows the clear need for scalable database systems with cloud-compatible, web-based interfaces [1]. In order to meet the requirements listed in the introduction, the properties of horizontal scalability of read requests, low latency, HTTP based access with standard protocols and the independence of client APIs and databases from a persistence protocol are fulfilled. These properties allow new database and application architectures. Databases that are offered as a service require the ability to scale read requests and to enable the potential distribution of database and application through low-latency access [26]. Low latency is essential to achieve high throughput and the reactivity of a local database deployment. Hiding the inevitable latency of cloud services is therefore an eminently important aspect of a persistence protocol. In order to use the elasticity and on-demand resources of cloud environments, the protocol must also offer a mechanism for horizontal scalability. This allows the database system to handle read-intensive workloads without loss of performance. As a result, a large number of clients can use the database efficiently and in parallel and benefit from the flexibility of cloud computing. Many applications in cloud environments have to interact with their services (which include persistence) through stateless HTTP [2]. HTTP allows the database to be managed, monitored and made available directly via a web browser. This makes HTTP an obvious choice for a persistence protocol. Due to the increasing heterogeneity of existing database solutions, the likelihood and expandability of data models, queries, transactions and consistency strategies is essential for a persistence protocol. The introduction of a loose coupling between persistence API and database on the protocol level is a basic requirement in order to promote the free combinability and coexistence of different database types (polyglot persistence [1]). The idea for implementing these requirements is shown in Table 1. N o v e m b e r

16 10 Coherent web caching of database objects in cloud computing Property Elastic read scalability Low latency Loose coupling between persistence API and database Web standards mechanism Web caching of database objects, workload-dependent starting of new web caches Caches with geographical proximity to the client, i.e. CDNs and Forward proxy caches Universal HTTP protocol with expandable resource structure for transactions, objects, schema management and queries Expandable HTTP content negotiation and predefined JSON formats Table 1 Requirements for a persistence protocol and implementation in ORESTES. The requirements are visualized in Figure 5: The communication between the application and the database must take place using a protocol that has a mechanism to enable horizontal read scalability and low latency. In addition, it must be extensible so that new persistence APIs and databases can easily make use of the protocol. Client Application Server Database Persistence API Scalability & low latency mechanism Database Interface Protocol Protocol Figure 5 The requirements for a persistence protocol. Our solution (ORESTES) is designed to meet the above properties. In its current implementation, ORESTES already fully supports object-oriented persistence. It can therefore be used through persistence APIs such as JDO (Java Data Objects) [27] or JPA (Java Persistence API) [28] on the client side and object-oriented databases [29] or relational databases with object-relational mapping on the server side. The ORESTES protocol, however, is so generic that other database systems such as key-value stores, document databases, wide-column stores, graph databases and even relational databases can be supported with the same principles and the same implementation (cf. [30]). . The central problem that ORESTES has solved for the first time is the apparent incompatibility of the HTTP caching model and dynamic database objects. In HTTP, the caching lifetime of objects is a static parameter, ad-hoc invalidations are not required for all caches that are not directly subordinate to the server (reverse proxies and CDNs).

17 Felix Gessert, Florian Bücklers 11 possible (cf. [31]). ORESTES shows that strong consistency and ACID transactions are still compatible with the HTTP caching model. This happens without the new mechanisms of this master's thesis but with the risk of transaction aborts: 1. When a client loads an object, an HTTP request is sent. 2. The object can be delivered from a web cache. The object met data contain a version number. 3. When the client commits the current transaction, it transfers the version numbers of all read objects (the so-called read set) to the server. On the basis of an optimistic concurrency control, the server decides whether stale reads or conflicts of concurrent transactions have occurred and rolls the transaction back if necessary. This is the weak point of the previous approach of every stale read, which leads to a transaction being aborted. The bloom filter based cache coherency can prevent this. Application on mobile device / private cloud / public cloud / on-premise or browser Orestes Internet load balancer Cache Cache Cache Cache DB with Orestes interface Writes, queries, schema Orestes Requests Scale-out No reads Figure 6 The ORESTES scaling model. The scale-out is based on the fan-out of HTTP requests by load balancers and the interception of read requests by web caches. The ORESTES scaling model is summarized in Figure 6. We will describe the scaling aspect in more detail below, as it is the cornerstone of ORESTES and is what makes the whole approach original. It is also the primary motivation for the cache coherence mechanisms of this master's thesis. Our implementation of ORESTES currently supports two persistence APIs (Java / JDO and JavaScript / JPA) and two database systems (Versant Object Database and db4o [32], [33]). In detailed benchmarks, which we only briefly address in this thesis, we were able to prove that with ORESTES a speedup of% for massively parallel, read-intensive workloads compared to the native binary protocols can be achieved. Concept The ORESTES REST / HTTP protocol REST (Representative State Transfer ) is an architectural style that gives an a-posteriori explanation for the success of the web [34]. REST is a collection of constraints that lead to desirable system properties such as scalability and simplicity when set to N o v e m b e r

18 12 Coherent web caching of database objects in cloud computing the design of a protocol can be applied [35]. Many services in cloud computing are technically offered as REST / HTTP services because they are easy to understand and can be used in any programming language [36]. HTTP is an application protocol based on the Transmission Control Protocol (TCP) and forms the basis of the web [35]. Most platform-as-a-service providers allow applications to use HTTP communication, whereas native TCP connections are prevented [2]. Since almost all network nodes - such as firewalls and proxies - allow and support HTTP, HTTP is an ideal protocol for a high degree of interoperability and accessibility. Since a REST API allows use from any modern programming language, many NoSQL databases offer REST interfaces. With ORESTES we show, however, that a suitable HTTP database interface offers considerably stronger reasons for using HTTP and REST than interoperability and ease of use. Resource structure data / db Orestes server database object in JSON format transactions / transaction namespace /simulation.classes class / Person references references {} "_objectinfo": {"class": "/db/sim.classes/person", "oid ":" /db/sim.classes/person/ "," version ":" 2 "}," /db/sim.classes/site ": {" owner ":" /db/sim.classes/person/ " , "posts": [], // ...}, "/db/sim.classes/person": {"status": "Reading ...", // ...} Database Object running TA / 8 changes / changeset changed matched query HTTP Interface GET PUT POST DELETE Hypermedia Figure 7 The REST / HTTP interface of ORESTES. The figure shows a section of the resource structure root> db> namespace> class> object. The dependencies of resources (hypermedia) are marked in red. In the ORESTES REST protocol, the key abstractions are mapped using resources such as schema, transaction, query, etc. These resources are uniquely identified by URLs. Through the Uniform Interface of HTTP with its methods GET, PUT, POST and DELETE, operations can be carried out on these resources, e.g. creating a new object. Representations (e.g. objects) can be of any media type

19 Felix Gessert, Florian Bücklers 13 accept. We define default formats in JSON (JavaScript Object Notation) [12], but allow any other media types (e.g. XML) that can be dynamically negotiated via HTTP content negotiation. Due to the expandability, the database contents can potentially always be represented in a way that is appropriate for the respective use case. The resource structure is also freely expandable. To e.g. To support the creation of map-reduce views, the definition of a new resource mr_view and an associated media type on the protocol level would suffice to expand the protocol. HTTP scaling model allows resources to be marked as cacheable.In this case, they are considered fresh for a static period of time specified per object and then discarded. A client requesting an object can always get this object from a web cache if it has saved the corresponding object and it is still considered fresh. Using a version number (ETag) or a change date, clients can revalidate an object on the Origin server, i.e. inquire about potential changes. This eliminates the effort of transferring and recalculating the representation if an object has not changed. In ORESTES, all objects are delivered with a configurable cache lifetime (e.g. 1 hour). Such an object can then be transferred directly from the cache to the client without creating a load on the server. At the same time, the network latency decreases, since on the one hand web caches are specialized in the fast delivery of objects and on the other hand are positioned closer to clients than the database server. Based on their position, we differentiate between five types of web caches (see Figure 8) [31], [35], [37]. 2 Forward Proxy Cache Web Proxy Cache Reverse Proxy Cache ISP Peering ISP 1 Client Cache Server Cache 5 (e.g. Browser) 3 4 Clients Orestes database Figure 8 The five different types of web caches. A distinction can be made between embedded (1, 5) and server-based (2,3,4) web caches. Web caches can be embedded directly in the client (client cache). The most popular example of such a cache is the browser cache. Since client caches are managed directly by the client, on the one hand they can deliver objects with a particularly low latency, but they do not contain the objects used by several clients and are usually small. Similarly, a cache can be embedded directly in the server (e.g. the page buffer of a DBMS). Almost all database systems operate this type of caching in order to particularly N o v e m b e r

20 14 Coherent web caching of database objects in cloud computing to cushion expensive operations, e.g. hard disk access [38]. The most powerful types of web caches are stand-alone servers. They are either configured explicitly in the client, automatically retrieved via configuration protocols, or as interception proxies transparently take over the connection between client and server. Forward proxy caches (e.g. Squid or Microsoft TMG [39], [40]) can be deployed as outgoing servers in the clients' network. Due to their geographical proximity to the client, the network latency can be kept very low, typically in the range of or less. Many Internet Service Providers (ISPs) use web proxy caches (often hardware appliances, e.g. Bluecoat Cacheflow) to save traffic and thus transit fees or to increase the quality of service for customers. The type of web cache used by many websites is the so-called reverse proxy cache (e.g. Varnish or Apache Traffic Server [23]). It acts as a representative of the server for incoming requests and accepts requests instead of it. Reverse proxy caches differ from the other web cache types mainly in that they can receive invalidations from the origin server. The caches used in CDNs are conceptually almost identical to reverse proxy caches. While web caching uses the fact that objects are read more often than written, web load balancing uses the inherent request parallelism of the HTTP protocol. Like web caching, load balancing can be implemented in both hardware and software. The statelessness of the HTTP protocol is a prerequisite for load balancing. Incoming requests can be distributed to any reverse proxy caches or servers without having to maintain a client-specific status in the load balancer or server. Load balancing can be implemented on different network levels. Very common is e.g. Layer-2 forwarding (direct routing), in which the load balancer and all origin servers share one (virtual) IP address. The load balancer forwards incoming layer-2 frames to the origin server according to a specified policy (e.g. round robin) and a TCP SYN packet, replacing the destination MAC address of the incoming frame with that of the selected server [41]. In this way, an end-to-end TCP connection is established completely transparently, while all TCP connections are evenly distributed to all servers (Layer-4 server load balancing). Another very simple implementation of load balancing is DNS round robin. There are several resource records for a domain name (e.g. ORESTES.info). The domain name is then resolved by different clients into different IP addresses that correspond to the individual backend servers. Since the network level of Web Load Balancing is completely transparent for client and server, only Gilly et al. [41] referenced. In order to use load balancing for ORESTES, e.g. Amazon's Elastic Load Balancing Service can be used [42]. Setting up your own load balancer is also easily possible with open source solutions such as HAProxy or Nginx [23].

21 Felix Gessert, Florian Bücklers 15 Policy-based Load- Balancer Caching Proxy Hash-based Cache Cache Cache Cache Cache Cache Cache Cache Cache Load-Balancing Cache Array Routing Protocol Query to Parent / Neighbor in Hierarchy Cache Cache Cache Cache Cache Cache Cache Cache Inter-Cluster Caching Cache Query-based Hierarchies Global Content Distribution Figure 9 Scaling mechanisms of web caches. An interesting and so far little noticed property of web caching is that web caches scale in the same way as database systems through sharding and replication. Therefore, the obvious approach is to use web caches for scaling database systems. Four general scaling mechanisms can be distinguished for web caches (see Figure 9). In the case of load balancing across multiple web caches, replication takes place implicitly. With every GET request via a web cache, the corresponding object is saved as a replica in the respective web cache. With cache clustering, e.g. is implemented in the Cache Array Routing Protocol (CARP) [43], the set of all URLs is disjunctly distributed to a set of web caches by a simple hash partitioning (like). Each web cache therefore holds a partition (shard) of the entire amount of data. A hybrid form of replication and sharding is implemented in query-based inter-cache protocols such as ICP, cache digests and HTCP [44] [46]. There, web caches have the option of querying neighboring web caches about the requested object in the event of a cache miss. This creates hierarchically structured, cooperative web cache clusters in which caches can reload objects from neighbors if necessary. Content delivery networks mostly also use combinations of sharding and partitioning. In addition to the standardized inter-cache protocols, proprietary special protocols are often used there. If, for example, a request arrives in a cache cluster of the CDN through the CDN's request routing mechanism, neighboring servers in the same cluster are queried first in the event of a cache miss. At N o v e m b e r

22 16 Coherent web caching of database objects in cloud computing and a cache miss in the cluster, clusters that are geographically further away are surveyed. The Origin server is only questioned if there is also a cache miss there. Key-Value Stores Document Databases Wide Column Stores Relational Databases Database System Replication Sharding Redis asynchronous Hash-based (Client) Riak asynchronous Consistent Hashing Voldemort asynchronous Consistent Hashing Couchbase asynchronous Hash-based Dynamo asynchronous Consistent Hashing CouchDB asynchronous Consistent Hashing MongoDB synchronous / asynchronous Range-based (Autosharding) BigTable asynchronous Range-based MegaStore synchronous Explicit parent-child table grouping (Entity Group) HBase asynchronous Range-based Hypertable synchronous Range-based Cassandra asynchronous Consistent Hashing SimpleDB asynchronous Shard per table / domain Azure Tables asynchronous Explicit partition key MySQL Cluster synchronous Hash-based VoltDB / H-Store synchronous Hash-based Oracle RAC synchronous - (Shared Disk) IBM PureScale synchronous - (Shared Disk) Table 2 Replication and sharding in horizontally scalable database systems (cf. [1], [3], [4 ], [11], [21], [47] [54]) As a consequence, this Be Therefore, web caches implement the scaling mechanisms of sharding and replication, which many database systems are newly implementing. Table 2 shows a relevant selection of horizontally scalable database systems and their use of replication and sharding. Replication can be broken down into two different approaches: synchronous and asynchronous replication. Both variants are implemented depending on the availability and consistency guarantees of the system. In newer NoSQL systems, asynchronous replication often predominates, as it allows low latencies by dispensing with immediate consistency. Sharding (also called partitioning) is mostly based on dividing the key space into contiguous areas (range parititioning) or a deterministic node allocation through a hash value of the keys (hash partitioning) [55]. If the read access always takes place as point access via the key, a hash-based approach is advantageous because it achieves the most even distribution of the data across nodes. Web cache clusters (e.g. based on CARP) can only work hash-based, as they have no knowledge of the internal structure of the key and therefore have to access URLs and metadata (e.g. ETags). Range-based partitioning would not bring any further advantages for ORESTES, since the replicas (web caches) do not support any transactions or query processing. In ORESTES, query results are therefore saved as a URL list from

23 Felix Gessert, Florian Bücklers 17 selected objects, which are then loaded via direct key access. Overall, implementation errors are repeated in the various implementations of sharding and replication, which can only be found and corrected through years of practical use. We therefore advocate the thesis that it is advantageous to use the solid and well-researched web caches as a scaling mechanism and to counter the disadvantages of their simplistic model at the protocol level. Web caches (clusters) differ from system-specific replication and sharding techniques [31]: 1. Web caches do not guarantee cache coherence for ad-hoc changes (asynchronous replication / eventual consistency). 2. Web caches cannot implement any database-specific logic (e.g. synchronization, locking, logging, etc.). So in order to make web caches usable for database systems, we solve both problems. We achieve cache coherence through the bloom filter-based cache coherence approach developed in this thesis. Furthermore, the concurrency check in ORESTES does not require strict cache coherence, since optimistic procedures are used. These are able to recognize the reading of outdated cache entries and the associated potential violation of serializability. The lack of database-specific logic is not a disadvantage on closer inspection. The fact that web caches are specialized in the very fast delivery of cached objects and do not have to carry out any operational overhead such as synchronization results in maximum throughput. The downside for ORESTES is that clients themselves are responsible for aggregating version numbers of read objects in a read set and transferring them to the server when a transaction is committed. Web caches only support write-through semantics for write operations, i.e. each write operation always reaches the ORESTES server (s). Since the ORESTES server only acts as a wrapper for the underlying database system, the responsibility for write scalability lies with this database system. In return, the entire load of navigating read access, i.e. all inquiries based on a primary key or a unique object ID, can be answered by web caches. How a web cache works when answering an object access is shown in Figure 10. The client makes its request for an object as an HTTP GET request to a URL that identifies the object. If the web cache does not yet have the requested object, it forwards the request to the database. However, if it detects a cache hit, it checks the cached object copy using the caching metadata (max-age = x) for validity. If the object has expired, it revalidates the database. For this purpose, a conditional delivery is required with an If-None-Match header, which only takes place if the object has actually changed. On the one hand, this saves the server n o v e m b e r

24 18 Coherent web caching of database objects in cloud computing, on the one hand the reconstruction of the object representation and, on the other hand, the transfer of the object itself. However, if the object copy is fresh (the expected standard case for objects in the working set), the web cache delivers the cached object directly to the client. Orestes read request GET / db / ns / 42 Object, TTL = x no cache hit? yes GET / db / ns / 42 Object fresh? yes no revalidate Orestes Application Web Caching System Database Figure 10 How a web cache works. We demonstrate how the cache works with a very simple example. To do this, we use the web interface that ORESTES provides for the database (Figure 12). Via the web interface, programmatic communication with the database can be made from the browser via an interactive JavaScript console, among other things. The persistence API is the JavaScript Persistence API (JSPA), a port of the Java Persistene API (JPA) developed in the course of this work. JSPA is described in more detail in Chapter 5. An example script (Figure 11) should query the extension of the Coffee class and output the name attribute. The query takes place via a query with an empty predicate. Since the API works asynchronously and event-based, the query result is output in a callback. var Coffee = Object.inherit ({initialize: function (name, countrycode, caffeine, parent) {this.name = name; this.countrycode = countrycode; this.caffeine = caffeine; this.parent = parent;}}); var factory = new jspa.entitymanagerfactory (); var pu = factory.persistenceunitutil; var em = factory.createentitymanager (); var query = em.createquery (null, Coffee); query.getresultlist (function (e, result) {result.foreach (function (c) {out.print ("name of the coffee:" + c.name);});}); Figure 11 A simple example that uses JSPA to load all objects of a class.

25 Felix Gessert, Florian Bücklers 19 Figure 12 Execution of a simple query via the ORESTES web interface. The result of the query are several requests at the REST / HTTP level. In the first step, the extension of the Coffee class is called up as a list of URLs (Figure 13). In the second step, all objects contained in the list are retrieved in parallel, all of which are answered from the browser cache (Figure 14). There are two reasons for the two-stage query: 1. Query results are dynamic and can therefore only be answered meaningfully by the database system. Previous approaches to cache query results in a dedicated manner are based on complete database systems in the vicinity of the clients and have not been very successful (DBProxy [56], DBCache [57]). 2. In order for objects to get into the web caches as quickly as possible, it is necessary to query them individually and thus make them separately cacheable. N o v e m b e r

26 20 Coherent web caching of database objects in cloud computing GET /db/test.persistent/coffee/all_objects HTTP / 1.1 Accept: application / json Accept-Charset: ISO, utf-8; q = 0.7, *; q = 0.3 Accept -Encoding: gzip, deflate, sdch Accept-Language: de-DE, de; q = 0.8, en-US; q = 0.6, en; q = 0.4 Connection: keep-alive User-Agent: Mozilla / 5.0 (Windows NT 6.2; WOW64) AppleWebKit / (KHTML, like Gecko) Chrome / Safari / Host: try.ORESTES.info Referer: HTTP / OK Cache-Control: no-cache, no-store, max-age = 0 Date: Tue, 13 Nov: 47: 47 GMT Server: Restlet-Framework / 2.1snapshot Vary: Accept Content-Length: 1500 Content-Type: application / json; charset = utf-8 ["/db/test.persistent/coffee/", "/db/test.persistent/coffee/", "/db/test.persistent/coffee/", "/db/test.persistent/ coffee / "," /db/test.persistent/coffee/ "," /db/test.persistent/coffee/ "," /db/test.persistent/coffee/ "," /db/test.persistent/coffee/ "," /db/test.persistent/coffee/ "," /db/test.persistent/coffee/ "] Figure 13 Query for the extension of the Coffee class. Despite the fact that objects are delivered from web caches for a statically defined period of time, the transactional guarantees must be met. If the underlying database system provides ACID transactions, these are also provided at the level of the ORESTES protocol. Without bloomfilter-based cache coherence, ACID guarantees are created with an increased risk of transaction abortions. When validating the read and write sets of the client, the server determines during the transaction commit whether the client has previously read obsolete objects. Objects are obsolete if the version number of an object in the (consistent) database, which increases monotonically during writing, is greater than the corresponding version number of the read set. The details of transaction management in ORESTES are presented in Chapter 3. With the techniques that were developed in this work, four consistency modes can be selected in ORESTES (the designations are based on Ramakrishnan [58]):

27 Felix Gessert, Florian Bückler's Read-Any: Such a request can be answered with objects from web caches. There is no guarantee that the object is up-to-date. 2.Read-Up-To-Date: A non-transactional, consistent request is answered by the database and therefore guarantees the most up-to-date consistent view. 3. Classic Transaction: In a conventional transaction, all objects can potentially be loaded from web caches. Stale reads are recognized at commit time. 4. Coherent Transaction: In this bloom filter-supported transaction, the client loads a bloom filter at the beginning of the transaction. This represents changes in the last caching period. The client always requests the changed objects contained in the bloom filter directly from the server and thus avoids stale reads. GET /db/test.persistent/coffee/ HTTP / 1.1 Host: try.orestes.info Connection: keep-alive User-Agent: Mozilla / 5.0 (Windows NT 6.2; WOW64) AppleWebKit / (KHTML, like Gecko) Chrome / Safari / Content-Type: application / json accept: application / json Referer: Accept-Encoding: gzip, deflate, sdch Accept-Language: de-de, de; q = 0.8, en-us; q = 0.6, en; q = 0.4 Accept-Charset: ISO, utf-8; q = 0.7, *; q = 0.3 HTTP / OK Cache-Control: max-age = 604800, public, stale-if-error = 3600, stalewhile-revalidate = 30 Date: Tue, Nov 13: 11:35 am GMT Server: Restlet-Framework / 2.1snapshot Vary: Accept Content-Length: 1500 Content-Type: application / json; charset = utf-8 ETag: "3" {"_objectinfo": {"oid": "/db/test.persistent/coffee/", "class": "/db/test.persistent/coffee", "version" : "3"}, "/db/test.persistent/coffee": {"caffeine": false, "name": "Arabica Ethiopian Late Vintage", "countrycode": 175, "parent": "/ db / test .persistent / coffee / "}} Figure 14 Querying an instance of the Coffee class. N o v e m b e r

28 22 Coherent web caching of database objects in cloud computing Implementation The systems that are involved in a request via ORESTES will now be considered using an example (Figure 15). A request should revalidate the already existing copy of an object. This is necessary, for example, if objects remain stored locally after the end of a transaction and are to be used in a later transaction at a later point in time. In this case, the client's persistence API will perform a revalidation in order to transfer the objects from their potentially inconsistent state (detached) to a consistent state (persistent clean). Client Persistence API 1 REST / HTTP Protocol 2 pm.getobjectbyid (id) pm.makepersistent (obj) pm.newquery (qry) em.persist (obj) em.find (cls, id) em.createquery (qry, cls) Java Data Objects 3 8 Java HTTP Layer Java Persistence API Port Forward Proxy Cache GET /db/sim.classes/person/2258 If-None-Match: "2" Cache-Control: max-age = 0 Accept: application / json Request JavaScript Internet & Web Infrastructure Content Delivery Networks (CDNs) Versant Object Database 4 Web Cache Web Cache Cluster Reverse Proxy Cache Wrapper 5 HTTP Layer 7 Response 200 OK 6 Cache-Control: public, max-age = Content-Type: application / json ETag: "3" Wrapper db4o JSON Object REST / HTTP Protocol Database Server Figure 15 Overview of systems involved in a conditional read request for an object.

29 Felix Gessert, Florian Bücklers 23 The revalidation request is carried out as follows: 1. The application calls an operation on the persistence API that requires a revalidation of an existing object (e.g. getobjectbyid (id)). 2. The persistence API forwards this call to the ORESTES framework. The ORESTES framework is an implementation of the ORESTES REST / HTTP protocol in Java. 3. The ORESTES framework sends a conditional HTTP GET request to revalidate the transferred object. 4. Forward proxy caches in the client's network forward these requests unchanged. CDNs and web proxy caches in networks of ISPs and reverse proxy caches in the server network proceed in the same way. The call thus reaches the HTTP layer of the database, i.e. the ORESTES framework. 5. The ORESTES framework forwards the revalidation to the database-specific wrapper. This checks whether the object is still valid and returns the result to the ORESTES framework. 6. Depending on the revalidation result, the ORESTES framework transmits a 304 Not Modified to the client or a 200 OK with the current object in JSON format. 7. Each caching system that forwards the response updates its saved copy and the caching metadata (i.e. version number and caching duration) if necessary. 8. The call reaches the client, where the ORESTES framework returns the revalidation result to the persistence API. As Figure 15 shows, the implementation of ORESTES currently supports two persistence APIs. Persistence APIs map calls to the database system on the ORESTES REST / HTTP protocol: Java Data Objects (JDO): For many years, JDO was the dominant standardized API for persistently storing objects in Java [27]. It was often used in combination with an object-relational mapper such as Hibernate, EclipseLink, DataNucleus, etc. With the Java Persistence API (JPA), which is very similar to JDO in almost all respects, another standardized persistence API for Java has existed for several years. The ORESTES JDO implementation is based on the Versant Inc. code base and maps all operations to the generic ORESTES framework. The ORESTES framework converts these calls into the REST / HTTP network communication of the ORESTES protocol. JavaScript Persistence API (JSPA): Since JavaScript is enjoying rapidly increasing popularity in the field of web apps, mobile apps, NoSQL and server-side web development, we have designed an object-oriented persistence API for JavaScript [59]. It corresponds in all points that allow it to the specification of the Java Persistence API [28]. JSPA can be executed in all common browsers as well as in the event-based web server Node.JS [60]. N o v e m b e r

30 24 Coherent web caching of database objects in cloud computing On the server side, ORESTES acts as a wrapper for the database and maps the REST / HTTP protocol to the native database interface. There are currently three connections, all of which have been further or newly developed in the course of this master's thesis. The Redis implementation was explicitly implemented to demonstrate the transferability of the results of this work to other data models and database systems: Versant Object Database (VOD): VOD is the market leader among object-oriented databases [32]. The connection to VOD was created in the course of a project cooperation. Db4o: Db4o is an object-oriented open source database system [33]. It does not perform as well as VOD, but it is portable and can also be embedded directly into applications. Redis: Redis is a newer open source NoSQL database in the Key-Value Store category. Since Redis performs operations in-memory, it is high-performance. The details of the ORESTES implementation are discussed in Chapter 5. 1.2 Cloud Computing As already shown in the catalog of requirements, a database system must meet several properties so that it can be used profitably in cloud environments. Classic database systems (e.g. DB2, Oracle, MSSQL, PostgreSQL, Sybase, Teradata, etc.) can also be used in cloud environments. However, since they were not developed explicitly for such use, they have many disadvantages and limitations there. Newer database systems, which are mostly called NoSQL, pick up on the development of cloud computing and actively support it. The most important point in which this manifests itself is the access log. REST APIs have established themselves for cross-language interoperability and loosely coupled service-oriented architectures. This is a huge advantage over traditional protocols that only implement proprietary binary interfaces. The difference between the two approaches is shown in Figure 16. A Java application that communicates with a relational database system requires a driver from the respective manufacturer. This driver typically maps methods of the Java Database Connectivity API (JDBC) to calls to a manufacturer-specific library installed on the client (so-called type 2 driver). This transfers the calls to the binary log of the database system. The binary protocols have been expanded over the years and are all tailored to the implementation of the database system and are therefore very closely linked to the manufacturer and the database system. Modern NoSQL databases that offer REST APIs differ fundamentally from this approach. There you can communicate directly with the database from any programming language. This is made possible by a native REST API of the databases, which is very easy for clients to consume.

31 Felix Gessert, Florian Bücklers 25 Classic DB communication Modern DB communication Java application Application (any language) JDBC API Persistence API Driver Manager Client Type-2 JDBC driver (manufacturer-specific) DB Library (manufacturer-specific) Binary protocol, e.g. TDS (Microsoft) MySQL Protocol Oracle Net PostgreSQL Protocol Client REST / HTTP, e.g. CouchDB Amazon SimpleDB Azure Tables OrientDB Neo4J DB DB Figure 16 Classic and modern database communication In terms of cloud computing, REST interfaces have overwhelming advantages over binary, proprietary TCP protocols: Use of the database from Platform-as-a-Service (PaaS) clouds, the mostly binary TCP connections forbid but allow HTTP communication (eg Google App Engine [2]). Use of the database from every common programming language, since HTTP is part of every standard library and the variety of programming languages ​​is increasing [61]. Use of existing, open standards (e.g. JSON and XML) with the associated tools, frameworks and monitoring tools (e.g. Pingdom [2]). Use of the database from mobile devices (HTML5 and native apps) and web browsers (JavaScript / Ajax), as JavaScript supports HTTP communication. Easy deployment, monitoring, etc. possible via the existing HTTP interface of the database and web browser. Use of the web infrastructure: load balancers and web caches. Further development of the interface during operation through new resources and expanded media types. Simple versioning of the interface using fault-tolerant media types. Loose coupling between database and client API, which allows extensive implementation freedom. Easier debugging because communication is human-readable. Easy development of administration tools. N o v e m b e r

32 26 Coherent web caching of database objects in cloud computing So far, only a few of the listed advantages of REST APIs have been used in NoSQL databases. With ORESTES we want to show that this is possible. In May 2012, ProgrammableWeb, the largest directory of web services, published an article on listed service interfaces for databases entitled 123 Database APIs [62]. As Figure 17 shows, 61% of these APIs are implemented as REST APIs. While not all of these interfaces are pure database interfaces (e.g. Freebase as a semantic dictionary), most of them are database-as-a-service interfaces for NoSQL databases. This shows a major disadvantage of the REST APIs of different databases - they lack universality. Since REST as an architectural style has expandability and modularization as a core concept, we want to equip the ORESTES REST protocol with the necessary universality. For example, the same resources and formats can be used for transactions, regardless of whether an object-oriented or key-value data model is used. Chapter 5 describes the implementation of this universal interface. 5% 2% 1% 2% 2% REST SOAP JavaScript 27% Others 61% GET POST XML-RPC Figure 17 Protocols from 123 database APIs (from [62]). Table 3 shows an examination of REST APIs of the database systems previously tested for sharding and replication, expanded to include those NoSQL databases that offer a REST interface. The investigation shows that almost all newer NoSQL databases already offer REST interfaces. For everyone else, there are usually plans to offer a REST API in the future, or the community has already developed experimental REST interfaces. The focus of many NoSQL systems on low latencies and high throughput also dispels the prejudice that REST interfaces are not suitable for performance-critical applications. The REST APIs examined vary greatly in the quality of their implementation. The more mature implementations also have some restrictions that we want to avoid with the ORESTES REST protocol. The following are some of the limitations you may encounter: Lack of support for web caching. This applies to each of the examined REST interfaces. Violation of statelessness that would allow load balancing of HTTP requests. Lack of expandability to new data and consistency models.

33 Felix Gessert, Florian Bücklers 27 Inadequate implementation of the REST constraints, e.g. Hypermedia. This leads, among other things, to incompatible API changes and poor resilience of the clients. Database system Redis Riak Voldemort Key-Value Stores Couchbase Dynamo Simple Storage Service Azure Blobs CouchDB Document Databases MongoDB ArangoDB RavenDB BigTable MegaStore HBase Hypertable Wide Column Stores Cassandra Graphen Databases Relational Databases SimpleDB Azure Tables OrientDB Neo4j InfoGrid AllegroGraph MySQL Cluster VoltDB / H-Store Oracle RAC IBM PureScale REST interface no yes no no (only for administration) yes (Amazon DynamoDB) yes yes yes only a few read operations, full REST APIs (prototypes) external yes yes no (Google internal) no (Google internal) yes (external StarGate project) no no (some prototypes; DBaaS with REST API: Cassandra.io) yes yes yes yes yes yes no no (only for administration) no no Table 3 Database systems and REST / HTTP interfaces, as of November 2012 (cf. [3], [ 11], [30], [42], [51], [63] [65]). An important goal of this work is to clear the ORESTES protocol of the deficiencies of the investigated REST interfaces and thus to make it suitable for use in cloud computing environments. The special focus is on the unique selling point of dealing with web caching and load balancing database-as-a-service.When using database systems in cloud computing (cloud data management), we distinguish between two degrees of freedom: the location of the application and the deployment of the Database system. An application can either run in the same cloud as the database system or outside the cloud. The database itself can be accessed via N o v e m b e r

34 28 Coherent web caching of database objects in cloud computing, a database-as-a-service model can be provided or set up, administered and maintained by the client himself. Cloud Application Browser Browser App App Mobile Mobile App App Browser Browser App App Mobile Mobile App App Application Application DB Virtual Machine IaaS Cloud DBaaS IaaS / PaaS Cloud Classic DBMS DBaaS Applications, Apps Applications, Apps Client Client DB Virtual Machine IaaS Cloud DBaaS Cloud Classic Application Figure 18 The four scenarios for the relationship between application and database. Figure 18 illustrates the four possible combinations. Each of the combinations is already being used in practice [2]. The figure also shows the relationships that are potentially at risk from high network latency. In order to still make the corresponding scenarios usable, the latency problem has to be solved. By deploying the application in geographical proximity to the database system, the latency problem can usually be solved for classic applications. For databases in cloud environments, the situation is different, however, not every application can be executed in the cloud. There are applications that build on existing infrastructure or use data that cannot be moved to the cloud for legal reasons or due to governance regulations. Such applications are inevitably exposed to higher latency as soon as they work with a cloud database. The same applies to browser applications and mobile apps that communicate directly with the database. This application architecture, which manages without an application server to encapsulate the database, is becoming increasingly popular [13]. This is expressed on the one hand in DBaaS offers that rely on interfaces for mobile and browser applications (e.g. MongoLab

35 Felix Gessert, Florian Bücklers 29 and Cassandra.io) and on the other hand through NoSQL database systems that incorporate the concept of client-side persistence directly into the design of the database (e.g. CouchDB). As a consequence, this means that despite the unsolved latency problem, new application architectures based on cloud databases are already establishing themselves. These architectures would benefit immensely from a solution to the latency problem. Numerous commercial DBaaS offers have emerged in the last two years. The DBaaS providers mostly specialize in a database system. They offer automated deployment for the database system in a selectable cloud or region of a cloud provider. The customer receives a service endpoint (i.e. in almost all cases the URL of a REST API) and can connect directly to the database from the persistence API of his application. All DBaaS providers also offer a browser console in which the individual databases can be administered. Some also offer additional functions, such as creating new replicas and shards, automatic archiving and disaster recovery through failover copies of the database. The typical process for using a DBaaS offer is shown in Figure 19 using the example of MongoHQ, a DBaaS provider for the MongoDB document database: 1. Most DBaaS providers work according to the freemium model, ie they offer basic services free of charge and all additional services in return a monthly fee (pay-as-you-go).Registration is usually required. 2. After logging in, a database instance can be created via a web console. 3. The URL of the database instance can be used from the application to establish a connection with the DBaaS Figure 19 Typical steps for using a DBaaS offer using the example of MongoHQ [66]. N o v e m b e r

36 30 Coherent web caching of database objects in cloud computing The application shown in Figure 19 loads a document from the database and measures the latency in the process. The result is approx. As a comparison value for the latency of a web cache of a CDN, Google with its global cache CDN is used. The network latency (measured in Hamburg) is there. The latency to a typical DBaaS differs from that of a CDN web cache by an order of magnitude. Table 4 shows measured network latencies for various cloud storage providers. These were determined using a JavaScript Test Suite from Cloudharmony.com, which determines the latency directly from the browser via the REST API of the respective provider (in this case from Hamburg). Cloud storage (e.g. Amazon Simple Storage Service or Azure Storage) is a special case of the DBaaS category, in which the DBaaS only allows the storage of blobs (binary large objects) under a key (URL). The terms storage-as-a-service and data-as-a-service are also common. However, the latency measurements are representative of other DBaaS offers, as these are served from the same data centers of the cloud providers (mostly Amazon Web Services and Windows Azure) and therefore have very similar latencies. The results from Amazon S3 and Azure Storage are the best, as these have data centers in Ireland and are therefore geographically very close to the measurement location Hamburg. In addition, both providers allow static caching of the files stored in their respective CDNs (Amazon Cloudfront, Azure CDN) [67], [68]. Service Location #Samples Min Max Std Median Avg (ms) (ms) Dev (ms) (ms) Simple Storage Service (S3) CA,% US Internap Cloud Storage HP Cloud Object Storage AZ, US%% Zetta Enterprise Cloud Storage Google Storage for Developers Windows Azure Storage IL, US%%% Windows Azure Storage TX, US% Simple Storage Service (S3) VA, US% Simple Storage Service (S3) IE% 65 66