Users / Applications To meet the storage needs of current cloud applications, new data management systems were developed. Design decisions were made by analyzing the applications workloads and technical enviQrounemrye Lnatn.gIutawgeas realized that traditional Relational Database Management Systems (RDBMSs) with their centralized architecture, strong consistency, and relational model do not t the elasticity and scalability requirements of theDcilsoturidb.uted Processing System Di erent architectures with a variety of data partitioning schemes and replica placement strategies were developed. As for the data model, the key-value pairs wiSthtruitcstuvarerida tDiaotnas System were adopted for cloud storage. The contribution of this paper is to provide a comprehensible overview of key-characteristics of current solutions and outline the problems they do and do not address. This paper should sDeirsvtreibausteadn Setnotrraygep Soyinsttefmor orientation of future research regarding new applications in cloud computing and advanced requirements for data management.
Data management used within the cloud or o ered as a
service from the cloud is an important current research eld.
However, there are only few publications that provide a
survey and compare the di erent approaches. The contribution
of this paper is to provide a starting point for researchers and
developers who want to work on cloud data management.
Cloud computing is a new technology that provides resources
as an elastic pool of services in a pay-as-you-go model [
Users / Applications
across heterogeneous hardware and software platforms. It
will store tera bytes of data, thus parameters of I/O
operations and block sizes must be adapted to large sizes. Based
on these assumptions the requirements for a cloud DBMS
are: elasticity, scalability, fault tolerance and self
manageability [
ARCHITECTURE OVERVIEW
There are two main approaches to provide data
management systems for the cloud. In the rst approach, each
customer gets an own instance of a Database Management
System (DBMS), which runs on virtual machines of the
service provider [
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 can be combined according to application needs. Figure 2 illustrates this architecture. The essential part is the dis
tributed storage system. It is usually internally used by the cloud services provider and not provided as a public service. It is responsible for providing availability, scalability, fault tolerance, and performance for data access. Systems in this layer are divided in three categories:
Distributed File Systems (DFS), such as Google's File System (GFS).
Cloud based le services, such as Amazon's Simple Storage Service (S3).
Peer to peer le systems, such as Amazon's Dynamo.
The second layer consists of structured data systems and
provides simple data models such as key-value pairs, which
we discuss in Section 6. These systems support various APIs
for data access, such as SOAP and HTTP. Examples of
systems in this layer are Google's Bigtable, Cassandra, and
SimpleDB. The third layer includes distributed processing
systems, which are responsible for more complex data
processing, e.g, analytical processing, mass data
transformation, or DBMS-style operations like joins and aggregations.
MapReduce [
The nal layer includes query languages. SQL is not
supported. However, developers try to mimic SQL syntax for
simplicity. Most query languages of cloud data management
systems support access to one domain, key space, or table,
i.e., do not support joins [
For more insight into connections and dependencies between these systems and components, we provide a family
RDS
Relational Cloud StoragHei vSeervice
HDFS Dynamo S3
use the system use concepts
tree of cloud storage systems as illustrated in Figure 3. We use a solid arrow to illustrate that a system uses another one such as Hive using HDFS. We use a dotted arrow to illustrate that a system uses some aspects of another system like the data model or the processing paradigm. An example of this is Cassandra using the data model of Bigtable. In this family tree, we cover a range of commercial systems, open source projects, and academic research as well. We start on the left side with distributed storage systems GFS and HDFS. Then, we have the structured storage systems with API support such as Bigtable. Furthermore, there are systems that support a simple QL such as SimpleDB. Next, we have structured storage systems with support of MapReduce and simple QL such as Cassandra and HBase. Finally, we have systems with sophisticated QL and MapReduce support such as Hive and HadoopDB. We compare and classify these systems based on other criteria in the coming sections. An overview is presented in Figure 4. 3.
CONSISTENCY, AVAILABILITY,
PARTITION TOLERANCE (CAP) THEOREM
Tightly related to key features of cloud data management
systems are discussions on the CAP theorem [
Consistency: includes all modi cations on data that must be visible to all clients once they are committed. G F S
H D F
S file
file chunk
chunk X X
X X
D y n a m o X X Key space set of items
X X
S i m p l e D B X X X X X
Property ACID BASE SCLA Tunable Consistency Hash Range List Composite H i v e
R D S X
X item
X domain item chunk block
Availability: means that all operations on data, whether read or write, must end with a response within a speci ed time.
Partition tolerance: means that even in the case of components' failures, operations on the database must continue.
The CAP theorem also states that developers must make trade-o decisions between the three con icting 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 return a success message only if data has been committed to all nodes, which is not always possible because of network or node failures. This means that its availability will be sacri ced.
In the cloud, there are basically four approaches for DBMSs in dealing with CAP: Atomicity, Consistency, Isolation, Durability (ACID): With ACID, users have the same consistent view of data before and after transactions. A transaction is 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 and errors. Data is locked while being modi ed by a transaction. When another transaction tries to access locked data, it has to wait until data is unlocked. Systems that support ACID are used by applications that require strong consistency and can tolerate its affects on the scalability of the application as already discussed in Section 2.
Basically Available, Soft-state, Eventual consistency (BASE):
The system does not guarantee that all users see the same version of a data item, but guarantees that all of them get a response from the systems even if it means getting a stale version. Soft-state refers refers to the fact, that the current status of a managed object can be ambiguous, e.g. because there are several temporarily inconsistent replicas of it stored. Eventually consistent means that updates will propagate through all replicas of a data item in a distributed system, but this takes time. Eventually, all replicas are updated. BASE is used by applications that can tolerate weaker consistency to have higher availability. Examples of systems supporting BASE are SimpleDB and CouchDB.
Strongly Consistent, Loosely Available (SCLA): This approach provides stronger consistency than BASE. The scalability of systems supporting SCLA in the cloud is higher compared to those supporting ACID. It is used by systems that choose higher consistency and sacri ce availability to a small extent. Examples of systems supporting SCLA are HBase and Bigtable. Tunable consistency: In this approach, consistency is congurable. For each read and write request, the user decides the level of consistency in balance with the level of availability. This means that the system can work in HadoopDB
RDS A BASE CouchDB SimpleDB Dynamo S3
HBase
Hive
Bigtable
Tunable Consistency P
Cassandra
PNUTS
high consistency or high availability and other degrees
in between. An example of a system supporting
tunable consistency is Cassandra [
PARTITIONING TECHNIQUES
Partitioning, also known as sharding, is used by cloud
data management systems to achieve scalability. There is a
variety of partitioning schemes used by di erent systems on
di erent levels. Some systems partition data on the le level
while others horizontally partition the key space or table.
Examples of systems partitioning data on the le level are
the DFSs such as GFS and HDFS which partition each le
into xed sized chunks of data. The second class of systems
which partition tables or key space uses one of the following
partitioning schemes [
Range Partitioning The range of values belonging to one key is divided into intervals. Each partition is assigned one interval. A partition is selected if the key value of the inserted tuple is inside a certain range. An example of a system using range partitioning is HBase.
Hash Partitioning The output of a hash function is assigned to di erent partitions. The hash function is applied on key values to determine the partition. This scheme is used when data does not lend itself to list and range partitioning. An example of a system using hash as the partitioning scheme is PNUTS.
There are some systems that use a composite partitioning scheme. An example is Dynamo, which uses a composite of hash and list schemes (consistent hashing). Some systems allow partitioning data several times using di erent partitioning schemes each time. An example is Hive, where each table is partitioned based on column values. Then, each partition can be hash partitioned into buckets, which are stored in HDFS.
One important design consideration to make is whether
to choose an order-preserving partitioning technique or not.
Order preserving partitioning has an advantage of better
performance when it comes to range queries. Examples of
systems using order preserving partitioning techniques are
Bigtable and Cassandra. Since most partitioning methods
depend on random position assignment of storage nodes,
the need for load balancing to avoid non uniform
distribution of data and workloads is raised. Dynamo [
REPLICATION TECHNIQUES
Replication is used by data management systems in the
cloud to achieve high availability. Replication means storing
replicas of data on more than one storage node and probably
more than one data center. The replica placement strategy
a ects the e ciency of the system [
Rack Unaware Strategy: Also known as the Simple Strategy. It places replicas within one data center using a method that does not con gure replica placement on certain racks.
Replication improves system robustness against node failures. When a node fails, the system can transparently read data from other replicas. Another gain of replication is increasing read performance using a load balancer that directs requests to a data center close to the user. Replication has a disadvantage when it comes to updating data. The system has to update all replicas. This leads to very important design considerations that impact availability and consistency of data. The rst one is to decide whether to make replicas available during updates or wait until data is consistent across all of them. Most systems in the cloud choose availability over consistency. The second design consideration is to decide when to perform replica con icts resolution, i.e., during writes or reads. If con ict resolution is done during write operations, writes could be rejected if the system can not reach all replicas or a speci ed number of them within a speci c time. Example of that is the WRITE ALL operation in Cassandra, where the write fails if the system could not reach all replicas of data. However, some systems in the cloud choose to be always writeable and push con ict resolution to read operations. An example of that is Dynamo which is used by many Amazon services like the shopping cart service where customer updates should not be rejected. 6.
Just as di erent requirements compared to conventional DBMS-based applications led to the previously described di erent architectures and implementation details, they also led to di erent data models typically being used in cloud data management. The main data models used by cloud systems are: Key-value pairs It is the most common data model for cloud storage. It has three subcategories:
Row oriented: Data is organized as containers
of rows that represent objects with di erent
attributes. Access control lists are applied on the
object (row) or container (set of rows) level [
Document Oriented: Data is organized as a
collection of self described JSON documents.
Document is the primarily unit of data which is
identi ed by a unique ID. Documents are the unit
for access control [
Wide column: In this model, attributes are grouped
together to form a column family. Column family
information can be used for query optimization.
Some systems perform access control and both
disk and memory accounting at the column
family level [
Relational Model (RM) The most common data model for traditional DBMS is less often used in the cloud. Nevertheless, Amazon's RDS supports this data model and PNUTS a simpli ed version of it. 7. SUMMARY AND CONCLUSION
The cloud with its elasticity and pay-as-you-go model is an attractive choice for outsourcing data management applications. Cloud service providers, such as Amazon and Microsoft, provide relational DBMSs instances on virtual machines. However, the cloud technical environment, workloads, and elasticity requirements lead to the development of new breed of storage systems. These systems range from highly scalable and available distributed storage systems with simple interfaces for data access to fully equipped DBMSs that support sophisticated interfaces, data models, and query languages.
Cloud data management systems faced with the CAP theorem trade-o provide di erent levels of consistency ranging from eventual consistency to strict consistency. Some systems allow users to determine the level of consistency for each data input/output request by determining the number of replicas to work with or the version number of the data item. List, range, hash, and composite partitioning schemes are used to partition data to achieve scalability. With partitioning comes the need for load balancing with two basic methods: uniform distribution of data and workloads, and analyzing load information. With data partitioned and distributed over many nodes, taking into consideration the possibility of node and network failures, comes the need for replication to achieve availability. Replication is done on the partition level using rack aware, data center aware, and rack unaware placement strategies. Cloud data management systems support relational data model, and key-value pairs data model. The key-value pairs is widely used with di erent variations: document oriented, wide column, and row oriented.
As outlined throughout this paper, several typical properties of traditional DBMS, such as advanced query languages, transaction processing, and complex data models, are mostly not supported by cloud data management systems. Some of them, because they are simply not required for current cloud applications. Others, because their implementation would lead to losing some of the important advantages, e.g., scalability and availability, of current cloud data management approaches. On the one hand, providing features of conventional DBMS appears to lead toward worthwhile research directions and is currently addressed in ongoing research. On the other hand, advanced requirements, which are completely di erent may arise from future cloud applications, e.g., interactive entertainment, on-line role playing games, and virtual realities, have interesting characteristics of continuous, collaborative, and interactive access patterns, sometimes under real-time constraints. In a similar way, new ways of human-computer interaction in real-world environments addressed, for instance, in ubiquitous computing and augmented reality are often very data-intensive and sometimes require expensive processing, which could be supported by cloud paradigms. Nevertheless, neither traditional DBMS nor cloud data management can currently su ciently support those applications.
We would like to thank the Syrian ministry of higher education for partially funding this research.