NoSQLDatabases - christof-strauch.de

1 nosql DatabasesChristof Topics on Software-TechnologyUltra-Large Scale SitesLecturerProf. Walter KrihaCourse of StudiesComputer Science and Media (CSM)UniversityHochschule der Medien, Stuttgart(Stuttgart Media University)Contents | iContents1 Introduction and Overview .. Uncovered Topics .. 12 The Motives and Main Drivers .. Criticism .. Classifications and Comparisons of nosql Databases .. 233 Basic Concepts, Techniques and Consistency .. Partitioning .. Storage Layout .. Query Models .. Distributed Data Processing via MapReduce .. 504 Key- Amazon s Dynamo.

2 Project Voldemort .. Other Key-/Value-Stores .. 675 Document Apache CouchDB .. MongoDB .. 766 Column-Oriented Google s Bigtable .. Bigtable Derivatives .. Cassandra .. 1147 Conclusion121A Further Reading, Listening and WatchingivB List of abbreviationsixC BibliographyxiiList of Figures | iiList of Vector Clocks .. Vector Clocks Exchange via Gossip in State Transfer Mode .. Vector Clocks Exchange via Gossip in Operation Transfer Mode .. Consistent Hashing Initial Situation .. Consistent Hashing Situation after Node Joining and Departure.

3 Consistent Hashing Virtual Nodes Example .. Consistent Hashing Example with Virtual Nodes and Replicated Data .. Membership Changes Node X joins the System .. Membership Changes Node B leaves the System .. Storage Layout Row-based, Columnar with/out Locality Groups .. Storage Layout Log Structured Merge Trees .. Storage Layout MemTables and SSTables in Bigtable .. Storage Layout Copy-on-modfify in CouchDB .. Query Models Companion SQL-Database .. Query Models Scatter/Gather Local Search .. Query Models Distributed B+Tree .. Query Models Prefix Hash Table / Distributed Trie.

4 MapReduce Execution Overview .. MapReduce Execution on Distributed Storage Nodes .. Amazon s Dynamo Consistent Hashing with Replication .. Amazon s Dynamo Concurrent Updates on a Data Item .. Project Voldemort Logical Architecture .. Project Voldemort Physical Architecture Options .. MongoDB Replication Approaches .. MongoDB Sharding Components .. MongoDB Sharding Metadata Example .. Google s Bigtable Example of Web Crawler Results .. Google s Bigtable Tablet Location Hierarchy .. Google s Bigtable Tablet Representation at Runtime.

5 110 List of Tables | iiiList of Classifications nosql Taxonomy by Stephen Yen .. Classifications Categorization by Ken North .. Classifications Categorization by Rick Cattell .. Classifications Categorization and Comparison by Scofield and Popescu .. Classifications Comparison of Scalability Features .. Classifications Comparison of Data Model and Query API .. Classifications Comparison of Persistence Design .. CAP-Theorem Alternatives, Traits, Examples .. ACID vs. BASE .. Amazon s Dynamo Summary of Techniques .. Amazon s Dynamo Evaluation by Ippolito.

6 Project Voldemort JSON Serialization Format Data Types .. MongoDB Referencing vs. Embedding Objects .. MongoDB - Parameters of thegroupoperation .. 891. Introduction and OverviewRelational database management systems (RDMBSs) today are the predominant technology for storingstructured data in web and business applications. Since Codds paper A relational model of data for largeshared data banks [Cod70] from 1970 these datastores relying on the relational calculus and providingcomprehensive ad hoc querying facilities by SQL (cf. [CB74]) have been widely adopted and are oftenthought of as the only alternative for data storage accessible by multiple clients in a consistent there have been different approaches over the years such as object databases or XML storesthese technologies have never gained the same adoption and market share as RDBMSs.

7 Rather, thesealternatives have either been absorbed by relational database management systems that allow to storeXML and use it for purposes like text indexing or they have become niche products for OLAP or the past few years, the one size fits all -thinking concerning datastores has been questioned by both,science and web affine companies, which has lead to the emergence of a great variety of alternativedatabases. The movement as well as the new datastores are commonly subsumed under the termNoSQL, used to describe the increasing usage of non-relational databases among Web developers (cf. [Oba09a]).

8 This paper s aims at giving a systematic overview of the motives and rationales directing this movement(chapter 2), common concepts, techniques and patterns (chapter 3) as well as several classes of NoSQLDatabases (key-/value-stores, document databases, column-oriented databases) and individual products(chapters 4 6). Uncovered TopicsThis paper excludes the discussion of datastores existing before and are not referred to as part of theNoSQL movement, such as object-databases, pure XML databases and DBMSs for special purposes (suchas analytics or stream processing). The class of graph databases is also left out of this paper but someresources are provided in the appendix A.

9 It is out of the scope of this paper to suggest individual NoSQLdatastores in general as this would be a total misunderstanding of both, the movement and the approach ofthe nosql datastores, as not being one size fits all -solutions. In-depth comparisons between all availableNoSQL databases would also exceed the scope of this The nosql -MovementIn this chapter, motives and main drivers of the nosql movement will be discussed along with remarkspassed by critics and reactions from nosql advocates. The chapter will conclude by different attempts toclassify and characterize nosql databases. One of them will be treated in the subsequent Motives and Main DriversThe term nosql was first used in 1998 for a relational database that omitted the use of SQL (see [Str10]).

10 The term was picked up again in 2009 and used for conferences of advocates of non-relational databasessuch as developer Jon Oskarsson, who organized the nosql meetup in San Francisco (cf. [Eva09a]).A blogger, often referred to as having made the term popular is Rackspace employee Eric Evans who laterdescribed the ambition of the nosql movement as the whole point of seeking alternatives is that youneed to solve a problem that relational databases are a bad fit for (cf. [Eva09b]).This section will discuss rationales of practitioners for developing and using nonrelational databases anddisplay theoretical work in this field.