Cloud Data Management: A Short Overview and Comparison of Current Approaches Siba Mohammad Sebastian Breß Eike Schallehn Otto-von-Guericke University Otto-von-Guericke University Otto-von-Guericke University Magdeburg Magdeburg Magdeburg siba.mohammad@iti.uni- sebastian.bress@st.ovgu.de eike@iti.cs.uni-magdeburg.de magdeburg.de ABSTRACT Users / Applications Users / Applications To meet the storage needs of current cloud applications, new data management systems were developed. Design de- cisions were made by analyzing the applications workloads Query Language Relational Cloud Storage Service and technical environment. It was realized that traditional Relational Database Management Systems (RDBMSs) with their centralized architecture, strong consistency, and rela- tional model do not fit the elasticity and scalability require- Relational DBMS ments of the Distributed Processing cloud. Different System with a variety architectures of data partitioning schemes and replica placement strate- gies were developed. As for the data model, the key-value pairs with its variations were adopted for cloud storage. The Figure 1: RDBMS as a service Structured Data System contribution of this paper is to provide a comprehensible overview of key-characteristics of current solutions and out- line the problems they do and do not address. This paper across heterogeneous hardware and software platforms. It should serve as an Storage entry point for orientation of future re- will store tera bytes of data, thus parameters of I/O opera- Distributed System search regarding new applications in cloud computing and tions and block sizes must be adapted to large sizes. Based advanced requirements for data management. on these assumptions the requirements for a cloud DBMS are: elasticity, scalability, fault tolerance and self manage- ability [11]. The rest of the paper is organized as follows. 1. INTRODUCTION First, we provide an overview of the architecture and the Data management used within the cloud or offered as a family tree of the cloud storage systems. Then, we discuss service from the cloud is an important current research field. how different systems deal with the trade-off in the Con- However, there are only few publications that provide a sur- sistency, Availability, Partition tolerance (CAP) theorem. vey and compare the different approaches. The contribution After that, we discuss different schemes used for data parti- of this paper is to provide a starting point for researchers and tioning and replication. Then, we provide a list of the cloud developers who want to work on cloud data management. data models. Cloud computing is a new technology that provides resources as an elastic pool of services in a pay-as-you-go model [5]. Whether it is storage space, computational power, or soft- 2. ARCHITECTURE OVERVIEW ware, customers can get it over the internet from one of the There are two main approaches to provide data manage- cloud service providers. Big players in the market, such as ment systems for the cloud. In the first approach, each Google [8], Amazon [13], Yahoo! [9], and Hadoop [7], defined customer gets an own instance of a Database Management the assumptions for cloud storage systems based on analyz- System (DBMS), which runs on virtual machines of the ser- ing the technical environment and applications workload. vice provider [10] as illustrated in Figure 1. The DBMS First, a data management system will work on a cluster of supports full ACID requirements with the disadvantage of storage nodes where components failure is the normal situ- loosing scalability. If an application requires more comput- ation rather than the exception. Thus, fault tolerance and ing or storage resources than the maximum allocated for an recovery must be built in. The system must be portable instance, the customer must implement partitioning on the application level using a different database instance for each partition [1]. Another solution is on demand assignment of resources to instances. Amazon RDS is an example of rela- tional database services, that supports MySQL, Oracle, and SQL Server. In the second approach, data management is not provided as a conventional DBMS on a virtualized platform, but as a combination of interconnected systems and services that 24th GI-Workshop on Foundations of Databases (Grundlagen von Daten- banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. can be combined according to application needs. Figure 2 Copyright is held by the author/owner(s). illustrates this architecture. The essential part is the dis- Users / Applications 2010 Users / Applications RDS HadoopDB Hive Query Language Relational Cloud Storage Service 2009 Cassandra Relational DBMS Distributed Processing System 2008 Hadoop MR HBase HDFS Dynamo SimpleDB Structured Data System 2007 S3 2006 Distributed Storage System 2005 Google MR Figure 2: Cloud data management architecture Bigtable 2004 tributed storage system. It is usually internally used by the cloud services provider and not provided as a public service. GFS use the system It is responsible for providing availability, scalability, fault 2003 use concepts tolerance, and performance for data access. Systems in this layer are divided in three categories: File system DBMS • Distributed File Systems (DFS), such as Google’s File System (GFS). Figure 3: Family tree of cloud data management • Cloud based file services, such as Amazon’s Simple systems Storage Service (S3). • Peer to peer file systems, such as Amazon’s Dynamo. tree of cloud storage systems as illustrated in Figure 3. We use a solid arrow to illustrate that a system uses another one The second layer consists of structured data systems and such as Hive using HDFS. We use a dotted arrow to illus- provides simple data models such as key-value pairs, which trate that a system uses some aspects of another system like we discuss in Section 6. These systems support various APIs the data model or the processing paradigm. An example of for data access, such as SOAP and HTTP. Examples of sys- this is Cassandra using the data model of Bigtable. In this tems in this layer are Google’s Bigtable, Cassandra, and family tree, we cover a range of commercial systems, open SimpleDB. The third layer includes distributed processing source projects, and academic research as well. We start systems, which are responsible for more complex data pro- on the left side with distributed storage systems GFS and cessing, e.g, analytical processing, mass data transforma- HDFS. Then, we have the structured storage systems with tion, or DBMS-style operations like joins and aggregations. API support such as Bigtable. Furthermore, there are sys- MapReduce [12] is the main processing paradigm used in tems that support a simple QL such as SimpleDB. Next, we this layer. have structured storage systems with support of MapReduce The final layer includes query languages. SQL is not sup- and simple QL such as Cassandra and HBase. Finally, we ported. However, developers try to mimic SQL syntax for have systems with sophisticated QL and MapReduce sup- simplicity. Most query languages of cloud data management port such as Hive and HadoopDB. We compare and classify systems support access to one domain, key space, or table, these systems based on other criteria in the coming sections. i.e., do not support joins [4, 2]. Other functionalities, such An overview is presented in Figure 4. as controlling privileges and user groups, schema creation, and meta data access are supported. Examples of query languages for cloud data are HiveQL, JAQL, and CQL. The 3. CONSISTENCY, AVAILABILITY, PARTI- previous components complement each other and work to- TION TOLERANCE (CAP) THEOREM gether to provide different sets of functionalities. One im- Tightly related to key features of cloud data management portant design decision that was made for most cloud data systems are discussions on the CAP theorem [14]. It states query languages is not supporting joins or aggregations. In- that consistency, availability, and partition tolerance are sys- stead, the MapReduce framework is used to perform these tematic requirements for designing and deploying applica- operations to take advantage of parallel processing on differ- tions for distributed environments. In the cloud data man- ent nodes within a cluster. Google pioneered this by provid- agement context these requirements are: ing a MapReduce framework that inspired other systems. For more insight into connections and dependencies be- • Consistency: includes all modifications on data that tween these systems and components, we provide a family must be visible to all clients once they are committed. System Analytical RDBMS Distributed Storage/File System Structured Data Systems Processing as Systems service Amazon S3 HadoopDB Cassandra SimpleDB CouchDB Dynamo Bigtable PNUTS HBase HDFS Hive RDS Property GFS Consistency Model ACID X X BASE X X X X SCLA X X X Tunable X X Consistency Partitioning Scheme Hash X X Range X X X List X X Composite X X Partition Key file file table table table table table Level space set of set of Partition chunk chunk tablet region tablet bucket chunk items items Data Models Key Value X X X X X X X X Row X Oriented Wide X X X X Column Document X Oriented Relational X X X Replication Rack aware X X X X X X Rack X X X unaware Datacenter X X X X aware Replication DB DB DB item chunk block item domain tablet record DB chunk DB Level file file file Map/Reduce Internally X X Input for X X X X X X X X Interface Query Lang X X X X X X API X X X X X X X X X X X Figure 4: Overview and classification of cloud data management systems(Gray field begins a new category of properties. Dark gray field means that the property is not applicable on a system) At any given point in time, all clients can read the C same data. • Availability: means that all operations on data, whether read or write, must end with a response within a spec- ified time. • Partition tolerance: means that even in the case of HBase HadoopDB components’ failures, operations on the database must Hive RDS continue. Bigtable The CAP theorem also states that developers must make trade-off decisions between the three conflicting requirements to achieve high scalability. For example, if we want a data storage system that is both strongly consistent and partition tolerant, the system has to make sure that write operations Tunable return a success message only if data has been committed BASE to all nodes, which is not always possible because of net- A Consistency P work or node failures. This means that its availability will CouchDB Cassandra be sacrificed. SimpleDB PNUTS In the cloud, there are basically four approaches for DBMSs Dynamo in dealing with CAP: S3 Atomicity, Consistency, Isolation, Durability (ACID): With ACID, users have the same consistent view of Figure 5: Classification of cloud data management data before and after transactions. A transaction is systems based on CAP atomic, i.e., when one part fails, the whole transaction fails and the state of data is left unchanged. Once a transaction is committed, it is protected against crashes high consistency or high availability and other degrees and errors. Data is locked while being modified by in between. An example of a system supporting tun- a transaction. When another transaction tries to ac- able consistency is Cassandra [15] where the user de- cess locked data, it has to wait until data is unlocked. termines the number of replicas that the system should Systems that support ACID are used by applications update/read. Another example is PNUTS [9], which that require strong consistency and can tolerate its af- provides per record time-line consistency. The user de- fects on the scalability of the application as already termines the version number to query at several points discussed in Section 2. in the consistency time-line. In Figure 5, we classify different cloud data management systems based on the Basically Available, Soft-state, Eventual consistency consistency model they provide. (BASE): The system does not guarantee that all users see the same version of a data item, but guarantees that all 4. PARTITIONING TECHNIQUES of them get a response from the systems even if it Partitioning, also known as sharding, is used by cloud means getting a stale version. Soft-state refers refers data management systems to achieve scalability. There is a to the fact, that the current status of a managed ob- variety of partitioning schemes used by different systems on ject can be ambiguous, e.g. because there are several different levels. Some systems partition data on the file level temporarily inconsistent replicas of it stored. Even- while others horizontally partition the key space or table. tually consistent means that updates will propagate Examples of systems partitioning data on the file level are through all replicas of a data item in a distributed the DFSs such as GFS and HDFS which partition each file system, but this takes time. Eventually, all replicas into fixed sized chunks of data. The second class of systems are updated. BASE is used by applications that can which partition tables or key space uses one of the following tolerate weaker consistency to have higher availability. partitioning schemes [18, 6] : Examples of systems supporting BASE are SimpleDB and CouchDB. List Partitioning A partition is assigned a list of discrete values. If the key of the inserted tuple has one of these Strongly Consistent, Loosely Available (SCLA): This values, the specified partition is selected . An example approach provides stronger consistency than BASE. of a system using list as the partitioning scheme is The scalability of systems supporting SCLA in the Hive [20]. cloud is higher compared to those supporting ACID. It is used by systems that choose higher consistency Range Partitioning The range of values belonging to one and sacrifice availability to a small extent. Examples key is divided into intervals. Each partition is assigned of systems supporting SCLA are HBase and Bigtable. one interval. A partition is selected if the key value of the inserted tuple is inside a certain range. An example Tunable consistency: In this approach, consistency is con- of a system using range partitioning is HBase. figurable. For each read and write request, the user de- cides the level of consistency in balance with the level Hash Partitioning The output of a hash function is as- of availability. This means that the system can work in signed to different partitions. The hash function is applied on key values to determine the partition. This not reach all replicas or a specified number of them within scheme is used when data does not lend itself to list a specific time. Example of that is the WRITE ALL opera- and range partitioning. An example of a system using tion in Cassandra, where the write fails if the system could hash as the partitioning scheme is PNUTS. not reach all replicas of data. However, some systems in the cloud choose to be always writeable and push conflict res- There are some systems that use a composite partitioning olution to read operations. An example of that is Dynamo scheme. An example is Dynamo, which uses a composite of which is used by many Amazon services like the shopping hash and list schemes (consistent hashing). Some systems cart service where customer updates should not be rejected. allow partitioning data several times using different parti- tioning schemes each time. An example is Hive, where each table is partitioned based on column values. Then, each par- 6. DATA MODEL tition can be hash partitioned into buckets, which are stored Just as different requirements compared to conventional in HDFS. DBMS-based applications led to the previously described One important design consideration to make is whether different architectures and implementation details, they also to choose an order-preserving partitioning technique or not. led to different data models typically being used in cloud Order preserving partitioning has an advantage of better data management. The main data models used by cloud performance when it comes to range queries. Examples of systems are: systems using order preserving partitioning techniques are Bigtable and Cassandra. Since most partitioning methods Key-value pairs It is the most common data model for depend on random position assignment of storage nodes, cloud storage. It has three subcategories: the need for load balancing to avoid non uniform distribu- tion of data and workloads is raised. Dynamo [13] focuses on • Row oriented: Data is organized as containers achieving a uniform distribution of keys among nodes assum- of rows that represent objects with different at- ing that the distribution of data access is not very skewed, tributes. Access control lists are applied on the whereas Cassandra [17] provides a load balancer that an- object (row) or container (set of rows) level [19]. alyzes load information to lighten the burden on heavily An example is SimpleDB. loaded nodes. • Document Oriented: Data is organized as a col- lection of self described JSON documents. Docu- 5. REPLICATION TECHNIQUES ment is the primarily unit of data which is iden- tified by a unique ID. Documents are the unit Replication is used by data management systems in the for access control [16]. Example of a cloud data cloud to achieve high availability. Replication means storing management system with document oriented data replicas of data on more than one storage node and probably model is CouchDB. more than one data center. The replica placement strategy affects the efficiency of the system [15]. In the following we • Wide column: In this model, attributes are grouped describe the replication strategies used by cloud systems: together to form a column family. Column family information can be used for query optimization. Rack Aware Strategy: Also known as the Old Network Some systems perform access control and both Topology Strategy. It places replicas in more than one disk and memory accounting at the column fam- data center on different racks within each data center. ily level [8, 17, 3]. An example of that is Bigtable. Data Center Aware Strategy: Also known as the New Systems of wide column data model should not be Network Topology Strategy. In this strategy, clients mistaken with column oriented DB systems. The specify in their applications how replicas are placed former deals with data as column families on the across different data centers. conceptual level only. The latter is more on the physical level and stores data by column rather Rack Unaware Strategy: Also known as the Simple Strat- than by row. egy. It places replicas within one data center using a method that does not configure replica placement on Relational Model (RM) The most common data model certain racks. for traditional DBMS is less often used in the cloud. Nevertheless, Amazon’s RDS supports this data model Replication improves system robustness against node fail- and PNUTS a simplified version of it. ures. When a node fails, the system can transparently read data from other replicas. Another gain of replication is in- creasing read performance using a load balancer that directs 7. SUMMARY AND CONCLUSION requests to a data center close to the user. Replication has a The cloud with its elasticity and pay-as-you-go model is disadvantage when it comes to updating data. The system an attractive choice for outsourcing data management ap- has to update all replicas. This leads to very important de- plications. Cloud service providers, such as Amazon and sign considerations that impact availability and consistency Microsoft, provide relational DBMSs instances on virtual of data. The first one is to decide whether to make repli- machines. However, the cloud technical environment, work- cas available during updates or wait until data is consistent loads, and elasticity requirements lead to the development across all of them. Most systems in the cloud choose avail- of new breed of storage systems. These systems range from ability over consistency. The second design consideration is highly scalable and available distributed storage systems to decide when to perform replica conflicts resolution, i.e., with simple interfaces for data access to fully equipped DBMSs during writes or reads. If conflict resolution is done during that support sophisticated interfaces, data models, and query write operations, writes could be rejected if the system can languages. Cloud data management systems faced with the CAP the- [5] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. H. orem trade-off provide different levels of consistency ranging Katz, A. Konwinski, G. Lee, D. A. Patterson, from eventual consistency to strict consistency. Some sys- A. Rabkin, I. Stoica, and M. Zaharia. Above the tems allow users to determine the level of consistency for clouds: A berkeley view of cloud computing. Technical each data input/output request by determining the number report, EECS Department, University of California, of replicas to work with or the version number of the data Berkeley, 2009. item. List, range, hash, and composite partitioning schemes [6] S. S. Avi Silberschatz, Henry F. Korth. Database are used to partition data to achieve scalability. With par- System Concepts Fifth Edition. McGraw-Hill, 2010. titioning comes the need for load balancing with two ba- [7] D. Borthakur. The Hadoop Distributed File System: sic methods: uniform distribution of data and workloads, Architecture and Design. The Apache Software and analyzing load information. With data partitioned and Foundation, 2007. distributed over many nodes, taking into consideration the [8] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. possibility of node and network failures, comes the need for Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. replication to achieve availability. Replication is done on Gruber. Bigtable: A distributed storage system for the partition level using rack aware, data center aware, and structured data. In In Proceedingss of the 7th rack unaware placement strategies. Cloud data management Conference on Usenix Symposium on Operating systems support relational data model, and key-value pairs Systems Design and Implementation - Volume 7, data model. The key-value pairs is widely used with differ- pages 205–218, 2006. ent variations: document oriented, wide column, and row [9] B. F. Cooper, R. Ramakrishnan, U. Srivastava, oriented. A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, As outlined throughout this paper, several typical proper- D. Weaver, and R. Yerneni. Pnuts: Yahoo!’s hosted ties of traditional DBMS, such as advanced query languages, data serving platform. Proc VLDB Endow., 2008. transaction processing, and complex data models, are mostly [10] C. Curino, E. Jones, R. A. Popa, N. Malviya, E. Wu, not supported by cloud data management systems. Some S. Madden, H. Balakrishnan, and N. Zeldovich. of them, because they are simply not required for current Relational Cloud: A Database Service for the Cloud. cloud applications. Others, because their implementation In 5th Biennial Conference on Innovative Data would lead to losing some of the important advantages, e.g., Systems Research, 2011. scalability and availability, of current cloud data manage- ment approaches. On the one hand, providing features of [11] S. Das, S. Agarwal, D. Agrawal, and A. E. Abbadi. conventional DBMS appears to lead toward worthwhile re- ElasTraS: An Elastic, Scalable, and Self Managing search directions and is currently addressed in ongoing re- Transactional Database for the Cloud. Technical search. On the other hand, advanced requirements, which report, 2010. are completely different may arise from future cloud appli- [12] J. Dean and S. Ghemawat. Mapreduce: simplified data cations, e.g., interactive entertainment, on-line role playing processing on large clusters. Commun. ACM, 2008. games, and virtual realities, have interesting characteristics [13] G. DeCandia, D. Hastorun, M. Jampani, of continuous, collaborative, and interactive access patterns, G. Kakulapati, A. Lakshman, A. Pilchin, sometimes under real-time constraints. In a similar way, S. Sivasubramanian, P. Vosshall, and W. Vogels. new ways of human-computer interaction in real-world en- Dynamo: Amazon’s highly available key-value store. vironments addressed, for instance, in ubiquitous comput- SIGOPS Oper. Syst. Rev., 2007. ing and augmented reality are often very data-intensive and [14] A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, sometimes require expensive processing, which could be sup- and P. Gauthier. Cluster-based scalable network ported by cloud paradigms. Nevertheless, neither traditional services. SIGOPS Oper. Syst. Rev., 1997. DBMS nor cloud data management can currently sufficiently [15] E. Hewitt. Cassandra The Definitive Guide. O Reilly support those applications. Media, Inc, 2010. [16] J. L. J. Chris Anderson and N. Slater. CouchDB The 8. ACKNOWLEDGMENTS Definitive Guide. OReilly Media, Inc, 2010. We would like to thank the Syrian ministry of higher ed- [17] A. Lakshman and P. Malik. Cassandra: a ucation for partially funding this research. decentralized structured storage system. SIGOPS Oper. Syst. Rev., 2010. [18] S. B. e. a. Lance Ashdown, Cathy Baird. Oracle9i 9. REFERENCES Database Concepts. Oracle Corporation., 2002. [1] Amazon RDS FAQ. [19] R. H. Prabhakar Chaganti. Amazon SimpleDB http://aws.amazon.com/rds/faqs/. [online; accessed Developer Guide Scale your application’s database on 10-March-2012]. the cloud using Amazon SimpleDB. Packt Publishing [2] Cassandra Query Language Documentation. Ltd, 2010. http://caqel.deadcafe.org/cql-doc. [online; accessed [20] A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, 25-July-2011]. S. Anthony, H. Liu, P. Wyckoff, and R. Murthy. Hive: [3] HBase: Bigtable-like structured storage for Hadoop a warehousing solution over a map-reduce framework. HDFS. http://wiki.apache.org/hadoop/hbase. [online; Proc. VLDB Endow., 2009. accessed 01-March-2012]. [4] Jaql Overview. http://www.almaden.ibm.com/cs/projects/jaql/. [online; accessed 31-August-2011].