Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> We describe our experiences with the Chubby lock service, which is intended to provide coarse-grained locking as well as reliable (though low-volume) storage for a loosely-coupled distributed system. Chubby provides an interface much like a distributed file system with advisory locks, but the design emphasis is on availability and reliability, as opposed to high performance. Many instances of the service have been used for over a year, with several of them each handling a few tens of thousands of clients concurrently. The paper describes the initial design and expected use, compares it with actual use, and explains how the design had to be modified to accommodate the differences. <s> BIB001 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> We describe our experience in building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected algorithmic and engineering problems encountered, and the solutions we found for them. Our measurements indicate that we have built a competitive system. <s> BIB002 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> We present Scalaris, an Erlang implementation of a distributed key/value store. It uses, on top of a structured overlay network, replication for data availability and majority based distributed transactions for data consistency. In combination, this implements the ACID properties on a scalable structured overlay. By directly mapping the keys to the overlay without hashing, arbitrary key-ranges can be assigned to nodes, thereby allowing a better load-balancing than would be possible with traditional DHTs. Consequently, Scalaris can be tuned for fast data access by taking, e.g. the nodes' geographic location or the regional popularity of certain keys into account. This improves Scalaris' lookup speed in datacenter or cloud computing environments. Scalaris is implemented in Erlang. We describe the Erlang software architecture, including the transactional Java interface to access Scalaris. Additionally, we present a generic design pattern to implement a responsive server in Erlang that serializes update operations on a common state, while concurrently performing fast asynchronous read requests on the same state. As a proof-of-concept we implemented a simplified Wikipedia frontend and attached it to the Scalaris data store backend. Wikipedia is a challenging application. It requires - besides thousands of concurrent read requests per seconds - serialized, consistent write operations. For Wikipedia's category and backlink pages, keys must be consistently changed within transactions. We discuss how these features are implemented in Scalaris and show its performance. <s> BIB003 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Data clustering has been received considerable attention in many applications, such as data mining, document retrieval, image segmentation and pattern classification. The enlarging volumes of information emerging by the progress of technology, makes clustering of very large scale of data a challenging task. In order to deal with the problem, many researchers try to design efficient parallel clustering algorithms. In this paper, we propose a parallel k -means clustering algorithm based on MapReduce, which is a simple yet powerful parallel programming technique. The experimental results demonstrate that the proposed algorithm can scale well and efficiently process large datasets on commodity hardware. <s> BIB004 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> S4 is a general-purpose, distributed, scalable, partially fault-tolerant, pluggable platform that allows programmers to easily develop applications for processing continuous unbounded streams of data. Keyed data events are routed with affinity to Processing Elements (PEs), which consume the events and do one or both of the following: (1) emit one or more events which may be consumed by other PEs, (2) publish results. The architecture resembles the Actors model, providing semantics of encapsulation and location transparency, thus allowing applications to be massively concurrent while exposing a simple programming interface to application developers. In this paper, we outline the S4 architecture in detail, describe various applications, including real-life deployments. Our design is primarily driven by large scale applications for data mining and machine learning in a production environment. We show that the S4 design is surprisingly flexible and lends itself to run in large clusters built with commodity hardware. <s> BIB005 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Artificial Bee Colony (ABC) algorithm which is one of the most recently introduced optimization algorithms, simulates the intelligent foraging behavior of a honey bee swarm. Clustering analysis, used in many disciplines and applications, is an important tool and a descriptive task seeking to identify homogeneous groups of objects based on the values of their attributes. In this work, ABC is used for data clustering on benchmark problems and the performance of ABC algorithm is compared with Particle Swarm Optimization (PSO) algorithm and other nine classification techniques from the literature. Thirteen of typical test data sets from the UCI Machine Learning Repository are used to demonstrate the results of the techniques. The simulation results indicate that ABC algorithm can efficiently be used for multivariate data clustering. <s> BIB006 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> The CAP theorem asserts that any networked shared-data system can have only two of three desirable properties. However, by explicitly handling partitions, designers can optimize consistency and availability, thereby achieving some trade-off of all three. The featured Web extra is a podcast from Software Engineering Radio, in which the host interviews Dwight Merriman about the emerging NoSQL movement, the three types of nonrelational data stores, Brewer's CAP theorem, and much more. <s> BIB007 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Novel systems that scale out on demand, relying on replicated data and massively distributed architectures with clusters of thousands of machines, particularly those designed for real-time data serving and update workloads, amply illustrate the realities of the CAP theorem. The featured Web extra is a video interview with Yahoo's Raghu Ramakrishnan about CAP and the cloud. <s> BIB008 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Failures are normal rather than exceptional in the cloud computing environments. To improve system availability, replicating the popular data to multiple suitable locations is an advisable choice, as users can access the data from a nearby site. This is, however, not the case for replicas which must have a fixed number of copies on several locations. How to decide a reasonable number and right locations for replicas has become a challenge in the cloud computing. In this paper, a dynamic data replication strategy is put forward with a brief survey of replication strategy suitable for distributed computing environments. It includes: 1) analyzing and modeling the relationship between system availability and the number of replicas; 2) evaluating and identifying the popular data and triggering a replication operation when the popularity data passes a dynamic threshold; 3) calculating a suitable number of copies to meet a reasonable system byte effective rate requirement and placing replicas among data nodes in a balanced way; 4) designing the dynamic data replication algorithm in a cloud. Experimental results demonstrate the efficiency and effectiveness of the improved system brought by the proposed strategy in a cloud. <s> BIB009 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Yellow elephants are slow. A major reason is that they consume their inputs entirely before responding to an elephant rider's orders. Some clever riders have trained their yellow elephants to only consume parts of the inputs before responding. However, the teaching time to make an elephant do that is high. So high that the teaching lessons often do not pay off. We take a different approach. We make elephants aggressive; only this will make them very fast. ::: ::: We propose HAIL (Hadoop Aggressive Indexing Library), an enhancement of HDFS and Hadoop MapReduce that dramatically improves runtimes of several classes of MapReduce jobs. HAIL changes the upload pipeline of HDFS in order to create different clustered indexes on each data block replica. An interesting feature of HAIL is that we typically create a win-win situation: we improve both data upload to HDFS and the runtime of the actual Hadoop MapReduce job. In terms of data upload, HAIL improves over HDFS by up to 60% with the default replication factor of three. In terms of query execution, we demonstrate that HAIL runs up to 68x faster than Hadoop. In our experiments, we use six clusters including physical and EC2 clusters of up to 100 nodes. A series of scalability experiments also demonstrates the superiority of HAIL. <s> BIB010 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> This paper presents a novel Bee Colony based optimization algorithm, named Job Data Scheduling using Bee Colony (JDS-BC). JDS-BC consists of two collaborating mechanisms to efficiently schedule jobs onto computational nodes and replicate datafiles on storage nodes in a system so that the two independent, and in many cases conflicting, objectives (i.e., makespan and total datafile transfer time) of such heterogeneous systems are concurrently minimized. Three benchmarks - varying from small- to large-sized instances - are used to test the performance of JDS-BC. Results are compared against other algorithms to show JDS-BC's superiority under different operating scenarios. These results also provide invaluable insights into data-centric job scheduling for grid environments. <s> BIB011 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> P2P systems are very important for future distributed systems and applications. In such systems, the computational burden of the system can be distributed to peer nodes of the system. Therefore, in decentralized systems users become themselves actors by sharing, contributing and controlling the resources of the system. This characteristic makes P2P systems very interesting for the development of decentralized applications. Data replication techniques are commonplace in P2P systems. Data replication means storing copies of the same data at multiple peers thus improving availability and scalability. The trustworthiness of peers also is very important for safe communication in P2P system. The trustworthiness of a peer can be evaluated based on the reputation and actual behaviour of peers to provide services to other peers. In this paper, we propose two fuzzy-based systems for data replication and peer trustworthiness for JXTA-Overlay P2P platform. The simulation results have shown that in the first system, replication factor increases proportionally with increase of number of documents per peer, replication percentage and scale of replication per peer parameters and the second system can be used successfully to select the most reliable peer candidate to execute the tasks. <s> BIB012 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Databases serving OLTP operations generated by cloud applications have been widely researched and deployed nowadays. Such cloud serving databases like BigTable, HBase, Cassandra, Azure and many others are designed to handle a large number of concurrent requests performed on the cloud end. Such systems can elastically scale out to thousands of commodity hardware by using a shared nothing distributed architecture. This implies a strong need of data replication to guarantee service availability and data access performance. Data replication can improve system availability by redirecting operations against failed data blocks to their replicas and improve performance by rebalancing load across multiple replicas. However, according to the PACELC model, as soon as a distributed database replicates data, another tradeoff between consistency and latency arises. This tradeoff motivates us to figure out how the latency changes when we adjust the replication factor and the consistency level. The replication factor determines how many replicas a data block should maintain, and the consistency level specifies how to deal with read and write requests performed on replicas. We use YCSB to conduct several benchmarking efforts to do this job. We report benchmark results for two widely used systems: HBase and Cassandra. <s> BIB013 </s> Big data storage technologies: a survey <s> Analysis of big data storage technologies based on Brewer's CAP theorem <s> Tick data are used in several applications that need to keep track of values changing over time, like prices on the stock market or meteorological measurements. Due to the possibly very frequent changes, the size of tick data tends to increase rapidly. Therefore, it becomes of paramount importance to reduce the storage space of tick data while, at the same time, allowing queries to be executed efficiently. In this paper, we propose an approach to decompose the original tick data matrix by clustering their attributes using a new clustering algorithm called Storage-Optimizing Hierarchical Agglomerative Clustering (SOHAC). We additionally propose a method for speeding up SOHAC based on a new lower bounding technique that allows SOHAC to be applied to high-dimensional tick data. Our experimental evaluation shows that the proposed approach compares favorably to several baselines in terms of compression. Additionally, it can lead to significant speedup in terms of running time. <s> BIB014
We have provided a brief illustration of Brewer's CAP theorem in Section 4.1. According to the new explanation BIB007 , it is clear that a storage system will be of either CP type or AP type. Here we present a systematic explanation of each storage system available for big data and categorize the system into CP and AP types since it is declared in the CAP theorem that it is impossible for a database to have both ACID consistency and data availability. Consequently, we focus on two pair of combinations from this theorem, which are consistency-partition resilience and availability-partition resilience, in our discussion. Table 5 elaborates the features of big data storage technologies. These features are further considered in analyzing and categorizing these storage systems according to Brewer's theorem. Table 5 also describes the methods for implementing consistency, replication, data partitioning, and indexing for these technologies. Furthermore, Brewer's category is suggested in Table 5 for each storage system. Based on the investigation of contemporary big data storage technologies presented in Table 5 , we suggest the type for each technology as depicted by Brewer. We identify and prove that each technology falls into either the CP or AP category. In Fig. 8 we present the categorization based on the two pairs given by Brewer for modern distributed systems, to show their success and capability towards Brewer's theorem. Intersection of two features presents the criteria, e.g., consistency-partition resilience (CP) and availability-partition resilience (AP). As Fig. 8 describes, recent distributed systems for storing big data satisfy either pair. Consistency and partition resilience are presented in Fig. 8 as CP, and the intersection shows the list of technologies that possess these two features from each data model. The pair availability-partition resilience is also shown in Fig. 8 , and at the intersection lie Cassandra, Voldemort, and DynamoDB. We previously explained that, according to Brewer, it is not possible for a system to fully support consistency and availability at the same time. Therefore, for a distributed system it is important to satisfy either choice, but partition resilience is mandatory. The trivial case for the systems having CP is that these systems become unresponsive to requests until the system recovers from partitioning and data on all sites are up to date. This phenomenon results in a locking state for the system, and the system may become unavailable for this time span. CP-type systems aim to ensure strong consistency regardless of the data access performance, and usually they believe in performing synchronous write operations. Scalaris, Redis, MemcacheDB, and Berkeley DB are CP-type key-value databases. Scalaris BIB003 implements a non-blocking Paxos commit protocol to ensure strong consistency. While the master-slave approach of MemcacheDB supports implementation of consistency and clients can access any replica on slaves for read operations, write operations are performed only at the master node. From the list of column-oriented databases, HBase, Hypertable, and BigTable are of CP type. For up-to-date and consistent data provisioning on all replicas, HBase allows synchronous writes to all replicas, which may increase latency or unavailability, but these are not the design goals for HBase BIB013 . HBase is designed to provide read/write consistency and holds clients' requests until the updating operation is complete. There is a write-aheadlog (WAL) in hard drive where write operations are updated first. Later, in-memory data are updated across all replicating nodes so that improved write throughput can be achieved. Similarly, BigTable implements transactional consistency on rows using Chubby service BIB001 and the Paxos algorithm BIB002 for persistent replicas and consistency lock management. Client acquires the lock and maintains the session during which it performs atomic reads and writes. Document databases such as MongoDB, Terrastore, and RethinkDB are CP-type databases. These databases prefer consistency over availability. MongoDB and RethinkDB are authoritative systems from the design perspective. Authoritative systems do not face the data inconsistency problem, which makes MongoDB and RethinkDB simple to build applications on top of them, whereas unavailability occurs very often for them  . Terrastore ensures that each single document is consistent and up to date. Because Terrastore does not allow interdocument transactions or multiple simultaneous operations on the same document, Terrastore becomes more scalable with simpler consistency. Tolerance to node failure is provided by Terrastore to the extent that at least one server node is working and the server node must have connection to the master node. Otherwise, Terrastore will not ensure partition resilience. All the graph databases discussed in this paper are of CP type. None of them is more inclined to support availability than consistency. AllegroGraph is the only graph database that implements transactional consistency; the rest of the graph databases aim to provide eventual consistency. HyperGraphDB implements Berkeley DB and offers non-blocking concurrency for transactions. Furthermore, HyperGraphDB has flexible schema, and updates are eventually consistent. Similarly, Neo4j supports nonblocking concurrency and eventual consistency. Even write-intensive transactions are efficiently accomplished by Neo4j. InfiniteGraph also supports eventual consistency for write operations. High availability to its extent can be achieved only when each request has received a response and the system does not ever face a complete locking state. However, it will not guarantee consistent results of requests. Key-value databases such as Aerospike, Voldemort, KAI, Riak, and DynamoDB are AP-type databases. Voldemort is designed as a highly available database where eventual consistency ensures almost up-to-date replicas. DynamoDB, when receiving a data update request, does not propagate it to all replicas for the reason of not locking them from availability to read requests. DynamoDB performs updating on a quorum of servers, while other servers respond to clients' requests in order to provide them access to consistent data at that time BIB008 . The quorum of servers needs to ensure successful write update before any request is entertained BIB013 . Riak has complex conflict resolution strategies, and implementation of quorum also results in latency problems. However, Riak is strongly available and is a partition-resilient key-value system. Cassandra is the only column-oriented AP-type database. Cassandra adopts the same mechanism to ensure availability and propagate consistency as DynamoDB does. Like Riak, Cassandra also has complex procedures for conflict resolution and quorum implementation. SimpleDB, CouchDB, OrientDB, Rocket U2, and Qizx are AP-type document databases. OrientDB offers versioning to implement the effect of write operations. In this way, effect of change in data can be viewed in different versions. As far as graph databases discussed in this paper are concerned, none of them is of AP type. In the next section we will summarize the discussion and identify future research challenges. This paper has presented the evolution and taxonomy of big data storage technologies. Technologies are commonly designed to provide a storage solution along with high scalability to growing data volumes with heterogeneous data structures. These databases are deployed over distributed systems to achieve high availability, improved data access, performance, and fault tolerance. However, the extent of provisioning these services is different for each database, which makes these databases distinguishable from each other. This extent helps identify these databases as of CP or AP type. In Table 5 , contemporary key-value, column-oriented, document-oriented, and graph databases are presented and analyzed on the basis of their adopted procedures for consistency, data partitioning, replication, and indexing. Moreover, their correlation with Brewer's CAP categorization is kept in the analysis to suggest their type. Key-value databases apply data partitioning on separate records regardless of each having the same attributes. A unique key is assigned to each record, and the value contains data of a record. Although they are mostly suitable for unstructured data, structured data can be presented with these databases if recordbased data retrieval and analysis needs to be performed on it. As far as licensing is concerned, most of the column-oriented and key-value databases are open source. BigTable is the only column-oriented database that has proprietary license. Likewise, DynamoDB is the only key-value database that is available commercially. Column-oriented databases such as HBase, Hypertable, Cassandra, and BigTable are mostly suitable for structured data with enough support to unstructured data. These databases apply vertical partitioning on the data and store each column as a separate chunk of data, and performing queries on attributes as well as attribute-based analysis of data is easier with this data model. As far as document-oriented databases are concerned, these databases also have the key-value data structure. However, the value identifies a document instead of a record. Documents are usually XML files with some schema. Compared to the key-value data model, document databases have less support to scalability and unstructured data. Furthermore, databases having document structure are, on average, prone to availability and consistency. For instance, MongoDB, Terrastore, and RethinkDB are consistent databases, whereas SimpleDB, CouchDB, OrientDB, Rocket U2, and Qizx are highly available. Graph databases are well-structured databases, where analyzing data as well as their relationships is significant. Although graph databases do not have good support to scalability and clustering, these databases offer complex data structures. According to our analysis, all graph databases in this survey are CP-type systems. With the proliferation of big data, industry and academia are more interested in data management than computational management. The technology has much evolved in provisioning vast storage and processing resources. However, in big data management, efficient techniques for data acquisition, preprocessing, processing, and storage are desirable. The ongoing development is focusing on bringing efficient solutions that support big data management. The Hadoop framework  has become the de facto standard for big data processing with the MapReduce programming model, which offers batch processing of extensive volume of files residing over commodity hardware, whereas for real-time big data processing, the simple, scalable streaming system (S4) BIB005 ) is a widely adopted tool. The Apache Software Foundation has a list of contributions to big data solutions such as Mahout, Lucene, Hive, Pig, and Spark. Besides processing, storage optimization is also important. Methods for data clustering, replication, and indexing for efficient storage utilization and data retrieval are of main concern. Storage-optimizing hierarchical agglomerative clustering BIB014 , the K-means algorithm BIB004 , and the artificial bee colony (ABC) algorithm BIB006 are the clustering approaches used in recent research. The storage technologies presented in this paper have built-in support to replication, which in turn ensures data availability, fault tolerance, and less data accessing delay. For efficient replication, the ABC algorithm BIB011 , D2RS BIB009 , and JXTA-overlay P2P platform BIB012 are the famous techniques used. HAIL BIB010 provides an indexing solution for Hadoop, which improves the data search and retrieval process. While summarizing the storage technologies presented in this paper, it can be stated that all the storage structures are partition-resilient, meaning that network partitioning and disconnections in distributed systems is rare and there are many options to handle and recover from a partitioning situation. Thus, the choice is only between consistency and availability. As illustrated in Section 4, the support to both of them is beyond the possibility of a distributed system. Thus, the discussed distributed storage systems are placed in either category. Storage systems that provide more support to consistency are CP-type systems. Apart from the efficiency of available big data storage technologies, the challenges of storing future big data still need to be addressed and considered. Finding and adopting the tradeoff between consistency and availability so that more throughput gains can be achieved from distributed storage systems leads to a number of challenges in this research. The following are some of these challenges: 1. Frequent data update and schema change: The update rate is mostly very high and the volume of data is growing very rapidly. In case of unstructured data, change in schema is also very common. However, available storage technologies are scalable, but the need to be efficient in data updates and schema is still under consideration. Some technologies like HDFS do not offer data update but append operation in only support. 2. Partitioning method: Data models suggest two methods of big data partitioning to make it contained on distributed storage nodes accordingly. Horizontal or vertical partitioning is applied on data based on access patterns. Data may be required to be analyzed by the features or records. Thus, the choice of column-oriented or key-value NoSQL databases is available. However, the prediction of access pattern might be wrong or change during execution. This poses a critical research challenge on existing data models specified for big data storage solutions. 3. Replication factor: Data are replicated over multiple sites to achieve fault tolerance and high availability to its users. Although this concept makes the storage very efficient to improve access performance, it compromises data consistency and does not suit in frequent data changing and up-to-date access requirement conditions. This leads to poorer access performance if frequent consistency locks are experienced. Furthermore, the number of replicas for data is a multiple of storage space consumption. Sometimes it looks wise to access data from a remote site rather to use local storage space. Therefore, preconfigured or customized replication by applications or users is a challenge. 4. User expertise: Data are becoming more complex nowadays. At the same time, the user space is broadened by enterprises, so that users from different domains can execute queries on data according to their problems. It reveals the requirement of simple-to-deploy and easy-to-use storage but with higher performance than the relational database solution. To achieve improved performance, sometimes these databases integrate DBMS platforms, which undoubtedly meets the expectations, but the implementation and configuration process becomes complex for non-expert users.