NoSQL Databases
Christof Strauch
([email protected]rt.de)
Lecture
Selected Topics on Software-Technology
Ultra-Large Scale Sites
Lecturer
Prof. Walter Kriha
Course of Studies
Computer Science and Media (CSM)
University
Hochschule der Medien, Stuttgart
(Stuttgart Media University)
Contents | i
Contents
1 Introduction 1
1.1 Introduction and Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Uncovered Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 The NoSQL-Movement 2
2.1 Motives and Main Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Criticism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Classifications and Comparisons of NoSQL Databases . . . . . . . . . . . . . . . . . . . . 23
3 Basic Concepts, Techniques and Patterns 30
3.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Storage Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Query Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5 Distributed Data Processing via MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Key-/Value-Stores 52
4.1 Amazon’s Dynamo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Project Voldemort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Other Key-/Value-Stores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5 Document Databases 69
5.1 Apache CouchDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 MongoDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6 Column-Oriented Databases 104
6.1 Google’s Bigtable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2 Bigtable Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 Cassandra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7 Conclusion 121
A Further Reading, Listening and Watching iv
B List of abbreviations ix
C Bibliography xii
List of Figures | ii
List of Figures
3.1 Vector Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Vector Clocks – Exchange via Gossip in State Transfer Mode . . . . . . . . . . . . . . . . . . 36
3.3 Vector Clocks – Exchange via Gossip in Operation Transfer Mode . . . . . . . . . . . . . . . 37
3.4 Consistent Hashing – Initial Situation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Consistent Hashing – Situation after Node Joining and Departure . . . . . . . . . . . . . . . 40
3.6 Consistent Hashing – Virtual Nodes Example . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.7 Consistent Hashing – Example with Virtual Nodes and Replicated Data . . . . . . . . . . . . 41
3.8 Membership Changes – Node X joins the System . . . . . . . . . . . . . . . . . . . . . . . . 43
3.9 Membership Changes – Node B leaves the System . . . . . . . . . . . . . . . . . . . . . . . 43
3.10 Storage Layout – Row-based, Columnar with/out Locality Groups . . . . . . . . . . . . . . . 45
3.11 Storage Layout – Log Structured Merge Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.12 Storage Layout – MemTables and SSTables in Bigtable . . . . . . . . . . . . . . . . . . . . . 46
3.13 Storage Layout – Copy-on-modfify in CouchDB . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.14 Query Models – Companion SQL-Database . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.15 Query Models – Scatter/Gather Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.16 Query Models – Distributed B+Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.17 Query Models – Prefix Hash Table / Distributed Trie . . . . . . . . . . . . . . . . . . . . . . 49
3.18 MapReduce – Execution Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.19 MapReduce – Execution on Distributed Storage Nodes . . . . . . . . . . . . . . . . . . . . . 51
4.1 Amazon’s Dynamo – Consistent Hashing with Replication . . . . . . . . . . . . . . . . . . . . 55
4.2 Amazon’s Dynamo – Concurrent Updates on a Data Item . . . . . . . . . . . . . . . . . . . . 57
4.3 Project Voldemort – Logical Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Project Voldemort – Physical Architecture Options . . . . . . . . . . . . . . . . . . . . . . . 64
5.1 MongoDB – Replication Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2 MongoDB – Sharding Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3 MongoDB – Sharding Metadata Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1 Google’s Bigtable – Example of Web Crawler Results . . . . . . . . . . . . . . . . . . . . . . 105
6.2 Google’s Bigtable – Tablet Location Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Google’s Bigtable – Tablet Representation at Runtime . . . . . . . . . . . . . . . . . . . . . 110
List of Tables | iii
List of Tables
2.1 Classifications – NoSQL Taxonomy by Stephen Yen . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Classifications – Categorization by Ken North . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Classifications – Categorization by Rick Cattell . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Classifications – Categorization and Comparison by Scofield and Popescu . . . . . . . . . . . 26
2.5 Classifications – Comparison of Scalability Features . . . . . . . . . . . . . . . . . . . . . . . 26
2.6 Classifications – Comparison of Data Model and Query API . . . . . . . . . . . . . . . . . . . 27
2.7 Classifications – Comparison of Persistence Design . . . . . . . . . . . . . . . . . . . . . . . 28
3.1 CAP-Theorem – Alternatives, Traits, Examples . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 ACID vs. BASE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1 Amazon’s Dynamo – Summary of Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 Amazon’s Dynamo – Evaluation by Ippolito . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3 Project Voldemort – JSON Serialization Format Data Types . . . . . . . . . . . . . . . . . . 66
5.1 MongoDB – Referencing vs. Embedding Objects . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 MongoDB - Parameters of the group operation . . . . . . . . . . . . . . . . . . . . . . . . . 89
1. Introduction
1.1. Introduction and Overview
Relational database management systems (RDMBSs) today are the predominant technology for storing
structured data in web and business applications. Since Codds paper “A relational model of data for large
shared data banks“ [Cod70] from 1970 these datastores relying on the relational calculus and providing
comprehensive ad hoc querying facilities by SQL (cf. [CB74]) have been widely adopted and are often
thought of as the only alternative for data storage accessible by multiple clients in a consistent way.
Although there have been different approaches over the years such as object databases or XML stores
these technologies have never gained the same adoption and market share as RDBMSs. Rather, these
alternatives have either been absorbed by relational database management systems that e. g. allow to store
XML and use it for purposes like text indexing or they have become niche products for e.g. OLAP or stream
processing.
In 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 alternative
databases. The movement as well as the new datastores are commonly subsumed under the term NoSQL,
“used to describe the increasing usage of non-relational databases among Web developers” (cf. [Oba09a]).
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 NoSQL
databases (key-/value-stores, document databases, column-oriented databases) and individual products
(chapters 4–6).
1.2. Uncovered Topics
This paper excludes the discussion of datastores existing before and are not referred to as part of the
NoSQL movement, such as object-databases, pure XML databases and DBMSs for special purposes (such
as analytics or stream processing). The class of graph databases is also left out of this paper but some
resources are provided in the appendix A. It is out of the scope of this paper to suggest individual NoSQL
datastores in general as this would be a total misunderstanding of both, the movement and the approach of
the NoSQL datastores, as not being “one size fits all”-solutions. In-depth comparisons between all available
NoSQL databases would also exceed the scope of this paper.
2. The NoSQL-Movement
In this chapter, motives and main drivers of the NoSQL movement will be discussed along with remarks
passed by critics and reactions from NoSQL advocates. The chapter will conclude by different attempts to
classify and characterize NoSQL databases. One of them will be treated in the subsequent chapters.
2.1. Motives and Main Drivers
The term NoSQL was first used in 1998 for a relational database that omitted the use of SQL (see [Str10]).
The term was picked up again in 2009 and used for conferences of advocates of non-relational databases
such as Last.fm 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 later
described the ambition of the NoSQL movement as “the whole point of seeking alternatives is that you
need 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 and
display theoretical work in this field. Furthermore, it will treat the origins and main drivers of the NoSQL
movement.
2.1.1. Motives of NoSQL practioners
The Computerworld magazine reports in an article about the NoSQL meet-up in San Francisco that
“NoSQLers came to share how they had overthrown the tyranny of slow, expensive relational databases in
favor of more efficient and cheaper ways of managing data.” (cf. [Com09a]). It states that especially Web
2.0 startups have begun their business without Oracle and even without MySQL which formerly was popular
among startups. Instead, they built their own datastores influenced by Amazon’s Dynamo ([DHJ
+
07]) and
Google’s Bigtable ([CDG
+
06]) in order to store and process huge amounts of data like they appear e. g.
in social community or cloud computing applications; meanwhile, most of these datastores became open
source software. For example, Cassandra originally developed for a new search feature by Facebook is now
part of the Apache Software Project. According to engineer Avinash Lakshman, it is able to write 2500
times faster into a 50 gigabytes large database than MySQL (cf. [LM09]).
The Computerworld article summarizes reasons commonly given to develop and use NoSQL datastores:
Avoidance of Unneeded Complexity Relational databases provide a variety of features and strict data
consistency. But this rich feature set and the ACID properties implemented by RDBMSs might be more
than necessary for particular applications and use cases.
As an example, Adobe’s ConnectNow holds three copies of user session data; these replicas do not neither
have to undergo all consistency checks of a relational database management systems nor do they have to
be persisted. Hence, it is fully sufficient to hold them in memory (cf. [Com09b]).
2. The NoSQL-Movement | 3
High Throughput Some NoSQL databases provide a significantly higher data throughput than traditional
RDBMSs. For instance, the column-store Hypertable which pursues Google’s Bigtable approach allows the
local search engine Zvent to store one billion data cells per day [Jud09]. To give another example, Google
is able to process 20 petabyte a day stored in Bigtable via it’s MapReduce approach [Com09b].
Horizontal Scalability and Running on Commodity Hardware “Definitely, the volume of data is
getting so huge that people are looking at other technologies”, says Jon Travis, an engineer at SpringSource
(cited in [Com09a]). Blogger Jonathan Ellis agrees with this notion by mentioning three problem areas of
current relational databases that NoSQL databases are trying to address (cf. [Ell09a]):
1. Scale out data (e. g. 3 TB for the green badges feature at Digg, 50 GB for the inbox search at
Facebook or 2 PB in total at eBay)
2. Performance of single servers
3. Rigid schema design
In contrast to relational database management systems most NoSQL databases are designed to scale well in
the horizontal direction and not rely on highly available hardware. Machines can be added and removed (or
crash) without causing the same operational efforts to perform sharding in RDBMS cluster-solutions; some
NoSQL datastores even provide automatic sharding (such as MongoDB as of March 2010, cf. [Mer10g]).
Javier Soltero, CTO of SpringSource puts it this way: “Oracle would tell you that with the right degree
of hardware and the right configuration of Oracle RAC (Real Application Clusters) and other associated
magic software, you can achieve the same scalability. But at what cost?” (cited in [Com09a]). Especially
for Web 2.0 companies the scalability aspect is considered crucial for their business, as Johan Oskarsson of
Last.fm states: “Web 2.0 companies can take chances and they need scalability. When you have these two
things in combination, it makes [NoSQL] very compelling.” (Johan Oskarsson, Organizer of the meet-up
and web developer at Last.fm, cf. [Com09a]). Blogger Nati Shalom agrees with that: “cost pressure also
forced many organizations to look at more cost-effective alternatives, and with that came research that
showed that distributed storage based on commodity hardware can be even more reliable then[sic!] many
of the existing high end databases” (cf. [Sha09a] and for further reading [Sha09c]). He concludes: “All of
this led to a demand for a cost effective “scale-first database””.
Avoidance of Expensive Object-Relational Mapping Most of the NoSQL databases are designed
to store data structures that are either simple or more similar to the ones of object-oriented program-
ming languages compared to relational data structures. They do not make expensive object-relational
mapping necessary (such as Key/Value-Stores or Document-Stores). This is particularly important for
applications with data structures of low complexity that can hardly benefit from the features of a re-
lational database. Dare Obasanjo claims a little provokingly that “all you really need [as a web de-
veloper] is a key<->value or tuple store that supports some level of query functionality and has de-
cent persistence semantics.” (cf. [Oba09a]). The blogger and database-analyst Curt Monash iterates
on this aspect: ”SQL is an awkward fit for procedural code, and almost all code is procedural. [For
data upon which users expect to do heavy, repeated manipulations, the cost of mapping data into
SQL is] well worth paying [. . . ] But when your database structure is very, very simple, SQL may not
seem that beneficial.“ Jon Travis, an engineer at SpringSource agrees with that: “Relational databases
give you too much. They force you to twist your object data to fit a RDBMS.” (cited in [Com09a]).
In a blog post on the Computerworld article Nati Shalom, CTO and founder of GigaSpaces, identifies
the following further drivers of the NoSQL movement (cf. [Sha09b]):
2. The NoSQL-Movement | 4
Complexity and Cost of Setting up Database Clusters He states that NoSQL databases are designed
in a way that “PC clusters can be easily and cheaply expanded without the complexity and cost of ’sharding,’
which involves cutting up databases into multiple tables to run on large clusters or grids”.
Compromising Reliability for Better Performance Shalom argues that there are “different scenarios
where applications would be willing to compromise reliability for better performance.” As an example of
such a scenario favoring performance over reliability, he mentions HTTP session data which “needs to be
shared between various web servers but since the data is transient in nature (it goes away when the user
logs off) there is no need to store it in persistent storage.”
The Current “One size fit’s it all” Databases Thinking Was and Is Wrong Shalom states that “a
growing number of application scenarios cannot be addressed with a traditional database approach”. He
argues that “this realization is actually not that new” as the studies of Michael Stonebraker (see below)
have been around for years but the old ’news’ has spread to a larger community in the last years. Shalom
thinks that this realization and the search for alternatives towards traditional RDBMSs can be explained
by two major trends:
1. The continuous growth of data volumes (to be stored)
2. The growing need to process larger amounts of data in shorter time
Some companies, especially web-affine ones have already adopted NoSQL databases and Shalom expects
that they will find their way into mainstream development as these datastores mature. Blogger Dennis
Forbes agrees with this issue by underlining that the requirements of a bank are not universal and especially
social media sites have different characteristics: “unrelated islands of data”, a “very low [. . . ] user/transac-
tion value” and no strong need for data integrity. Considering these characteristics he states the following
with regard to social media sites and big web applications:
“The truth is that you don’t need ACID for Facebook status updates or tweets or Slashdots
comments. So long as your business and presentation layers can robustly deal with inconsistent
data, it doesn’t really matter. It isn’t ideal, obviously, and preferrably [sic!] you see zero data
loss, inconsistency, or service interruption, however accepting data loss or inconsistency (even
just temporary) as a possibility, breaking free of by far the biggest scaling “hindrance” of the
RDBMS world, can yield dramatic flexibility. [. . . ]
This is the case for many social media sites: data integrity is largely optional, and the expense
to guarantee it is an unnecessary expenditure. When you yield pennies for ad clicks after
thousands of users and hundreds of thousands of transactions, you start to look to optimize.”
(cf. [For10])
Shalom suggests caution when moving towards NoSQL solutions and to get familiar with their specific
strengths and weaknesses (e.g. the ability of the business logic to deal with inconsistency). Others,
like David Merriman of 10gen (the company behind MongoDB) also stress that there is no single tool
or technology for the purpose of data storage but that there is a segmentation currently underway in the
database field bringing forth new and different data stores for e.g. business intelligence vs. online transaction
processing vs. persisting large amounts of binary data (cf. [Tec09]).
2. The NoSQL-Movement | 5
The Myth of Effortless Distribution and Partitioning of Centralized Data Models Shalom further
addresses the myth surrounding the perception that data models originally designed with a single database
in mind (centralized datamodels, as he puts it) often cannot easily be partitioned and distributed among
database servers. This signifies that without further effort, the application will neither necessarily scale
and nor work correct any longer. The professionals of Ajatus agree with this in a blog post stating that
if a database grows, at first, replication is configured. In addition, as the amount of data grows further,
the database is sharded by expensive system admins requiring large financial sums or a fortune worth of
money for commercial DBMS-vendors are needed to operate the sharded database (cf. [Aja09]). Shalom
reports from an architecture summit at eBay in the summer of 2009. Participants agreed on the fact
that although typically, abstractions involved trying to hide distribution and partitioning issues away from
applications (e. g. by proxy layers routing requests to certain servers) “this abstraction cannot insulate the
application from the reality that [. . . ] partitioning and distribution is involved. The spectrum of failures
within a network is entirely different from failures within a single machine. The application needs to be
made aware of latency, distributed failures, etc., so that it has enough information to make the correct
context-specific decision about what to do. The fact that the system is distributed leaks through the
abstraction.” ([Sha09b]). Therefore he suggests designing datamodels to fit into a partioned environment
even if there will be only one centralized database server initially. This approach offers the advantage to
avoid exceedingly late and expensive changes of application code.
Shalom concludes that in his opinion relational database management systems will not disappear soon.
However, there is definitely a place for more specialized solutions as a ”one size fits all“ thinking was and
is wrong with regards to databases.
Movements in Programming Languages and Development Frameworks The blogger David Inter-
simone additionally observes movements in programming languages and development frameworks that
provide abstractions for database access trying to hide the use of SQL (cf. []) and relational databases
([Int10]). Examples for this trend in the last couple of years include:
• Object-relational mappers in the Java and .NET world like the Java Persistence API (JPA, part of the
EJB 3 specification, cf. [DKE06], [BO06],), implemented by e.g. Hibernate ([JBo10a], or the LINQ-
Framework (cf. [BH05]) with its code generator SQLMetal and the ADO.NET Entity Framework (cf.
[Mic10]) since .NET version 4.
• Likewise, the popular Ruby on Rails (RoR, [HR10]) framework and others try to hide away the usage
of a relational database (e. g. by implementing the active record pattern as of RoR).
• NoSQL datastores as well as some databases offered by cloud computing providers completely omit
a relational database. One example of such a cloud datastore is Amazon’s SimpleDB, a schema-
free, Erlang-based eventually consistent datastore which is characterized as an Entity-Attribute-Value
(EAV). It can store large collections of items which themselves are hashtables containing attributes
that consist of key-value-pairs (cf. [Nor09]).
The NoSQL databases react on this trend and try to provide data structures in their APIs that are closer
to the ones of programming languages (e. g. key/value-structures, documents, graphs).
Requirements of Cloud Computing In an interview Dwight Merriman of 10gen (the company behind
MongoDB) mentions two major requirements of datastores in cloud computing environments ([Tec09]):
1. High until almost ultimate scalability—especially in the horizontal direction
2. Low administration overhead
In his view, the following classes of databases work well in the cloud:
2. The NoSQL-Movement | 6
• Data warehousing specific databases for batch data processing and map/reduce operations.
• Simple, scalable and fast key/value-stores.
• Databases containing a richer feature set than key/value-stores fitting the gap with traditional
RDBMSs while offering good performance and scalability properties (such as document databases).
Blogger Nati Shalom agrees with Merriman in the fact that application areas like cloud-computing boosted
NoSQL databases: “what used to be a niche problem that only a few fairly high-end organizations
faced, became much more common with the introduction of social networking and cloud computing”
(cf. [Sha09a]).
The RDBMS plus Caching-Layer Pattern/Workaround vs. Systems Built from Scratch with Scal-
ability in Mind In his article “MySQL and memcached: End of an era?” Todd Hoff states that in
a “pre-cloud, relational database dominated world” scalability was an issue of “leveraging MySQL and
memcached”:
“Shard MySQL to handle high write loads, cache objects in memcached to handle high read
loads, and then write a lot of glue code to make it all work together. That was state of the art,
that was how it was done. The architecture of many major sites still follow[sic!] this pattern
today, largely because with enough elbow grease, it works.” (cf. [Hof10c])
But as scalability requirements grow and these technologies are less and less capable to suit with them. In
addition, as NoSQL datastores are arising Hoff comes to the conclusion that “[with] a little perspective,
it’s clear the MySQL + memcached era is passing. It will stick around for a while. Old technologies
seldom fade away completely.” (cf. [Hof10c]). As examples, he cites big websites and players that have
moved towards non-relational datastores including LinkedIn, Amazon, Digg and Twitter. Hoff mentions
the following reasons for using NoSQL solutions which have been explained earlier in this paper:
• Relational databases place computation on reads, which is considered wrong for large-scale web
applications such as Digg. NoSQL databases therefore do not offer or avoid complex read operations.
• The serial nature of applications
1
often waiting for I/O from the data store which does no good to
scalability and low response times.
• Huge amounts of data and a high growth factor lead Twitter towards facilitating Cassandra, which
is designed to operate with large scale data.
• Furthermore, operational costs of running and maintaining systems like Twitter escalate. Web ap-
plications of this size therefore “need a system that can grow in a more automated fashion and be
highly available.” (cited in [Hof10c]).
For these reasons and the “clunkiness” of the MySQL and memcached era (as Hoff calls it) large scale (web)
applications nowadays can utilize systems built from scratch with scalability, non-blocking and asynchronous
database I/O, handling of huge amounts of data and automation of maintainance and operational tasks
in mind. He regards these systems to be far better alternatives compared to relational DBMSs with
additional object-caching. Amazon’s James Hamilton agrees with this by stating that for many large-scale
web sites scalability from scratch is crucial and even outweighs the lack of features compared to traditional
RDBMSs:
1
Hoff does not give more detail on the types of applications meant here, but—in the authors opinion—a synchronous mindset
and implementation of database I/O can be seen in database connectivity APIs (such as ODBC or JDBC) as well as in
object-relational mappers and it spreads into many applications from these base technologies.
2. The NoSQL-Movement | 7
“Scale-first applications are those that absolutely must scale without bound and being able to
do this without restriction is much more important than more features. These applications
are exemplified by very high scale web sites such as Facebook, MySpace, Gmail, Yahoo, and
Amazon.com. Some of these sites actually do make use of relational databases but many do
not. The common theme across all of these services is that scale is more important than
features and none of them could possibly run on a single RDBMS.” (cf. [Ham09] cited in
[Sha09a])
Yesterday’s vs. Today’s Needs In a discussion on CouchDB Lehnardt and Lang point out that needs
regarding data storage have considerably changed over time (cf. [PLL09]; this argument is iterated further
by Stonebraker, see below). In the 1960s and 1970s databases have been designed for single, large high-
end machines. In contrast to this, today, many large (web) companies use commodity hardware which will
predictably fail. Applications are consequently designed to handle such failures which are considered the
“standard mode of operation”, as Amazon refers to it (cf. [DHJ
+
07, p. 205]). Furthermore, relational
databases fit well for data that is rigidly structured with relations and allows for dynamic queries expressed
in a sophisticated language. Lehnhardt and Lang point out that today, particularly in the web sector, data
is neither rigidly structured nor are dynamic quieries needed as most applications already use prepared
statements or stored procedures. Therefore, it is sufficient to predefine queries within the database and
assign values to their variables dynamically (cf. [PLL09]).
Furthermore, relational databases were initially designed for centralized deployments and not for distribu-
tion. Although enhancements for clustering have been added on top of them it still leaks through that
traditional were not designed having distribution concepts in mind at the beginning (like the issues adverted
by the “fallaclies of network computing” quoted below). As an example, synchronization is often not im-
plemented efficiently but requires expensive protocols like two or three phase commit. Another difficulty
Lehnhardt and Lang see is that clusters of relational databases try to be “transparent” towards applications.
This means that the application should not contain any notion if talking to a singly machine or a cluster
since all distribution aspects are tried to be hidden from the application. They question this approach to
keep the application unaware of all consequences of distribution that are e. g. stated in the famous eight
fallacies of distributed computing (cf. [Gos07]
2
:
“Essentially everyone, when they first build a distributed application, makes the following eight
assumptions. All prove to be false in the long run and all cause big trouble and painful learning
experiences.
1. The network is reliable
2. Latency is zero
3. Bandwidth is infinite
4. The network is secure
5. Topology doesn’t change
6. There is one administrator
7. Transport cost is zero
2
The fallacies are cited according to James Gosling’s here. There is some discussion about who came up with the list: the
first seven fallacies are commonly credited to Peter Deutsch, a Sun Fellow, having published them in 1994. Fallacy number
eight was added by James Gosling around 1997. Though—according to the English Wikipedia—“Bill Joy and Tom Lyon
had already identified the first four as "The Fallacies of Networked Computing"” (cf. [Wik10]). More details on the eight
fallacies can be found in an article of Rotem-Gal-Oz (cf. [RGO06])
2. The NoSQL-Movement | 8
8. The network is homogeneous”
While typical business application using relational database management systems try, in most cases, to
hide distribution aspects from the application (e. g. by clusters, persistence layers doing object-relational
mapping) many large web companies as well as most of the NoSQL databases do not pursue this approach.
Instead, they let the application know and leverage them. This is considered a paradigm shift in the eyes
of Lehnardt and Lang (cf. [PLL09]).
Further Motives In addition to the aspects mentioned above David Intersimone sees the following three
goals of the NoSQL movement (cf. [Int10]):
• Reach less overhead and memory-footprint of relational databases
• Usage of Web technologies and RPC calls for access
• Optional forms of data query
2.1.2. Theoretical work
In their widely adopted paper “The End of an Architectural Era” (cf. [SMA
+
07]) Michael Stonebraker
3
et al. come to the conclusion “that the current RDBMS code lines, while attempting to be a “one size fits
all” solution, in fact, excel at nothing”. Nothing in this context means that they can neither compete with
“specialized engines in the data warehouse, stream processing, text, and scientific database markets” which
outperform them “by 1–2 orders of magnitude” (as shown in previous papers, cf. [Sc05], [SBc
+
07]) nor do
they perform well in their their home market of business data processing / online transaction processing
(OLTP), where a prototype named H-Store developed at the M.I.T. beats up RDBMSs by nearly two
orders of magnitude in the TPC-C benchmark. Because of these results they conclude that RDBMSs“ are
25 year old legacy code lines that should be retired in favor of a collection of “from scratch” specialized
engines. The DBMS vendors (and the research community) should start with a clean sheet of paper and
design systems for tomorrow’s requirements, not continue to push code lines and architectures designed for
yesterday’s needs”. But how do Stonebraker et al. come to this conclusion? Which inherent flaws do they
find in relational database management systems and which suggestions do they provide for the “complete
rewrite” they are requiring?
At first, Stonebraker et al. argue that RDBMSs have been architected more than 25 years ago when the
hardware characteristics, user requirements and database markets where different from those today. They
point out that “popular relational DBMSs all trace their roots to System R from the 1970s”: IBM’s DB2
is a direct descendant of System R, Microsoft’s SQL Server has evolved from Sybase System 5 (another
direct System R descendant) and Oracle implemented System R’s user interface in its first release. Now,
the architechture of System R has been influenced by the hardware characteristics of the 1970s. Since
then, processor speed, memory and disk sizes have increased enormously and today do not limit programs
in the way they did formerly. However, the bandwidth between hard disks and memory has not increased
as fast as the CPU speed, memory and disk size. Stonebraker et al. criticize that this development in the
field of hardware has not impacted the architecture of relational DBMSs. They especially see the following
architectural characteristics of System R shine through in today’s RDBMSs:
• “Disk oriented storage and indexing structures”
• “Multithreading to hide latency”
3
When reading and evaluating Stonebraker’s writings it has to be in mind that he is commercially involved into multiple
DBMS products such Vertica, a column-store providing data warehousing and business analytics.
2. The NoSQL-Movement | 9
• “Locking-based concurrency control mechanisms”
• “Log-based recovery”
In this regard, they underline that although “there have been some extensions over the years, including
support for compression, shared-disk architectures, bitmap indexes, support for user-defined data types and
operators [. . . ] no system has had a complete redesign since its inception”.
Secondly, Stonebraker et al. point out that new markets and use cases have evolved since the 1970s
when there was only business data processing. Examples of these new markets include “data warehouses,
text management, and stream processing” which “have very different requirements than business data
processing”. In a previous paper (cf. [Sc05]) they have shown that RDBMSs “could be beaten by specialized
architectures by an order of magnitude or more in several application areas, including:
• Text (specialized engines from Google, Yahoo, etc.)
• Data Warehouses (column stores such as Vertica, Monet, etc.)
• Stream Processing (stream processing engines such as StreamBase and Coral8)
• Scientific and intelligence databases (array storage engines such as MATLAB and ASAP)”
They go on noticing that user interfaces and usage model also changed over the past decades from terminals
where “operators [were] inputting queries” to rich client and web applications today where interactive
transactions and direct SQL interfaces are rare.
Stonebraker et al. now present “evidence that the current architecture of RDBMSs is not even appropriate
for business data processing”. They have designed a DBMS engine for OLTP called H-Store that is
functionally equipped to run the TPC-C benchmark and does so 82 times faster than a popular commercial
DBMS. Based on this evidence, they conclude that “there is no market where they are competitive. As
such, they should be considered as legacy technology more than a quarter of a century in age, for which a
complete redesign and re-architecting is the appropriate next step”.
Design Considerations
In a section about design considerations Stonebraker et al. explain why relational DBMSs can be out-
performed even in their home market of business data processing and how their own DMBS prototype
H-Store can “achieve dramatically better performance than current RDBMSs”. Their considerations espe-
cially reflect the hardware development over the past decades and how it could or should have changed the
architecture of RDBMSs in order to gain benefit from faster and bigger hardware, which also gives hints
for “the complete rewrite” they insist on.
Stonebraker et al. see five particularly significant areas in database design:
Main Memory As—compared to the 1970s—enormous amounts of main memory have become cheap
and available and as “The overwhelming majority of OLTP databases are less than 1 Tbyte in size and
growing [. . . ] quite slowly” they conclude that such databases are “capable of main memory deployment
now or in near future”. Stonebraker et al. therefore consider the OLTP market a main memory market
even today or in near future. They criticize therefore that “the current RDBMS vendors have disk-oriented
solutions for a main memory problem. In summary, 30 years of Moore’s law has antiquated the disk-oriented
relational architecture for OLTP applications”. Although there are relational databases operating in memory
(e. g. TimesTen, SolidDB) these systems also inherit “baggage”—as Stonebraker et al. call it—from System
R, e.g. disk-based recovery logs or dynamic locking, which have a negative impact on the performance of
these systems.
2. The NoSQL-Movement | 10
Multi-Threading and Resource Control As discussed before, Stonebraker et al. consider databases a
main-memory market. They now argue that transactions typically affect only a few data sets that have to
be read and/or written (at most 200 read in the TPC-C benchmark for example) which is very cheap if all
of this data is kept in memory and no disk I/O or user stalls are present. As a consequence, the do not see
any need for multithreaded execution models in such main-memory databases which makes a considerable
amount of “elaborate code” of conventional relational databases irrelevant, namely multi-threading systems
to maximize CPU- and disk-usage, resource governors limiting load to avoid resource exhausting and multi-
threaded datastructures like concurrent B-trees. “This results in a more reliable system, and one with
higher performance”, they argue. To avoid long running transactions in such a single-threaded system they
require either the application to break up such transactions into smaller ones or—in the case of analytical
purposes—to run these transactions in data warehouses optimized for this job.
Grid Computing and Fork-Lift Upgrades Stonebraker et al. furthermore outline the development from
shared-memory architectures of the 1970s over shared-disk architectures of the 1980s towards shared-
nothing approaches of today and the near future, which are “often called grid computing or blade com-
puting”. As a consequence, Stonebraker et al. insist that databases have to reflect this development, for
example (and most obviously) by horizontal partitioning of data over several nodes of a DBMS grid. Fur-
thermore, they advocate for incremental horizontal expansion of such grids without the need to reload any
or all data by an administrator and also without downtimes. They point out that these requirements have
significant impact on the architecture of DBMSs—e. g. the ability to transfer parts of the data between
nodes without impacting running transactions—which probably cannot be easily added to existing RDBMSs
but can be considered in the design of new systems (as younger databases like Vertica show).
High Availability The next topics Stonebraker et al. address are high availability and failover. Again,
they outline the historical development of these issues from log-tapes that have been sent off site by
organizations and were run on newly delivered hardware in the case of disaster over disaster recovery
services installing log-tapes on remote hardware towards hot standby or multiple-site solutions that are
common today. Stonebraker et al. regard high availability and built-in disaster recovery as a crucial feature
for DBMSs which—like the other design issues they mention—has to be considered in the architecture and
design of these systems. They particularly require DBMSs in the OLTP field to
1. “keep multiple replicas consistent, requiring the ability to run seamlessly on a grid of geographically
dispersed systems”
2. “start with shared-nothing support at the bottom of the system” instead of gluing “multi-machine
support onto [. . . ] SMP architectures.”
3. support a shared-nothing architecture in the best way by using “multiple machines in a peer-to-peer
configuration” so that “load can be dispersed across multiple machines, and inter-machine replication
can be utilized for fault tolerance”. In such a configuration all machine resources can be utilized during
normal operation and failures only cause a degraded operation as fewer resources are available. In
contrast, todays HA solutions having a hot standby only utilize part of the hardware resources in
normal operation as standby machines only wait for the live machines to go down. The conclude that
“[these] points argue for a complete redesign of RDBMS engines so they can implement peer-to-peer
HA in the guts of a new architecture” they conclude this aspect.
In such a highly available system that Stonebraker et al. require they do not see any need for a redo log
as in the case of failure a dead site resuming activity “can be refreshed from the data on an operational
site”. Thus, there is only a need for an undo log allowing to rollback transactions. Such an undo log does
not have to be persisted beyond a transaction and therefore “can be a main memory data structure that
2. The NoSQL-Movement | 11
is discarded on transaction commit”. As “In an HA world, one is led to having no persistent redo log, just
a transient undo one” Stonebraker et al. see another potential to remove complex code that is needed for
recovery from a redo log; but they also admit that the recovery logic only changes “to new functionality
to bring failed sites up to date from operational sites when they resume operation”.
No Knobs Finally, Stonebraker et al. point out that current RDBMSs were designed in an “era, [when]
computers were expensive and people were cheap. Today we have the reverse. Personnel costs are the
dominant expense in an IT shop”. They especially criticize that “RDMBSs have a vast array of complex
tuning knobs, which are legacy features from a bygone era” but still used as automatic tuning aids of
RDBMSs “do not produce systems with anywhere near the performance that a skilled DBA can produce”.
Instead of providing such features that only try to figure out a better configuration for a number of knobs
Stonebraker et al. require a database to have no such knobs at all but to be ““self-everything” (self-healing,
self-maintaining, self- tuning, etc.)”.
Considerations Concerning Transactions, Processing and Environment
Having discussed the historical development of the IT business since the 1970s when RDBMSs were designed
and the consequences this development should have had on their architecture Stonebraker et al. now turn
towards other issues that impact the performance of these systems negatively:
• Persistent redo-logs have to be avoided since they are “almost guaranteed to be a significant perfor-
mance bottleneck”. In the HA/failover system discussed above they can be omitted totally.
• Communication between client and DBMS-server via JDBC/ODBC-like interfaces is the next performance-
degrading issue they address. Instead of such an interface they “advocate running application logic –
in the form of stored procedures – “in process” inside the database system” to avoid “the inter-process
overheads implied by the traditional database client / server model.”
• They suggest furthermore to eliminate an undo-log “wherever practical, since it will also be a signif-
icant bottleneck”.
• The next performance bottleneck addressed is dynamic locking to allow concurrent access. The cost
of dynamic locking should also be reduced or eliminated.
• Multi-threaded datastructures lead to latching of transactions. If transaction runtimes are short, a
single-threaded execution model can eliminate this latching and the overhead associated with multi-
threaded data structures “at little loss in performance”.
• Finally, two-phase-commit (2PC) transactions should be avoided whenever possible as the network
round trips caused by this protocol degrade performance since they “often take the order of millisec-
onds”.
If these suggestions can be pursued depends on characteristics of OLTP transactions and schemes as
Stonbraker et al. point out subsequently.
Transaction and Schema Characteristics
In addition to hardware characteristics, threading model, distribution or availability requirements discussed
above, Stonebraker et al. also point out that the characteristics of database schemes as well as transac-
tion properties also significantly influence the performance of a DBMS. Regarding database schemes and
transactions they state that the following characteristics should be exploited by a DBMS:
2. The NoSQL-Movement | 12
Tree Schemes are database schemes in which “every table except a single one called root, has exactly
one join term which is a 1-n relationship with its ancestor. Hence, the schema is a tree of 1-n
relationships”. Schemes with this property are especially easy to distribute among nodes of a grid
“such that all equi-joins in the tree span only a single site”. The root table of such a schema may be
typically partitioned by it’s primary key and moved to the nodes of a grid, so that on each node has
the partition of the root table together with the data of all other tables referencing the primary keys
in that root table partition.
Constrained Tree Application (CTA) in the notion of Stonebraker et al. is an applications that has a
tree schema and only runs transactions with the following characteristics:
1. “every command in every transaction class has equality predicates on the primary key(s) of the
root node”
2. “every SQL command in every transaction class is local to one site”
Transaction classes are collections of “the same SQL statements and program logic, differing in the
run-time constants used by individual transactions” which Stonebraker et al. require to be defined in
advance in their prototype H-Store. They furthermore argue that current OLTP applications are often
designed to be CTAs or that it is at least possible to decompose them in that way and suggest schema
transformations to be applied systematically in order to make an application CTA (cf. [SMA
+
07, page
1153]. The profit of these efforts is that “CTAs [. . . ] can be executed very efficiently”.
Single-Sited Transactions can be executed to completion on only one node without having to commu-
nicate with other sites of a DBMS grid. Constrained tree application e.g. have that property.
One-Shot Applications entirely consist of “transactions that can be executed in parallel without requiring
intermediate results to be communicated among sites”. In addition, queries in one-shot applications
never use results of earlier queries. These properties allow the DBMS to decompose transactions
“into a collection of single-site plans which can be dispatched to the appropriate sites for execution”.
A common technique to make applications one-shot is to partition tables vertically among sites.
Two-Phase Transactions are transactions that contain a first phase of read operations, which can—
depending on its results—lead to an abortion of the transaction, and a second phase of write oper-
ations which are guaranteed to cause no integrity violations. Stonebraker et al. argue that a lot of
OLTP transactions have that property and therefore exploit it in their H-Store prototype to get rid
of the undo-log.
Strongly Two-Phase Transactions in addition to two-phase transactions have the property that in the
second phase all sites either rollback or complete the transaction.
Transaction Commutativity is defined by Stonebraker et al. as follows: “Two concurrent transactions
from the same or different classes commute when any interleaving of their single-site sub-plans pro-
duces the same final database state as any other interleaving (assuming both transactions commit)”.
Sterile Transactions Classes are those that commute “with all transaction classes (including itself)”.
H-Store Overview
Having discussed the parameters that should be considered when designing a database management system
today, Stonebraker et al. sketch their protoype H-Store that performs significantly better than a commercial
DBMS in the TPC-C benchmark. Their system sketch shall not need to be repeated in this paper (details
can be found in [SMA
+
07, p. 154ff], but a few properties shall be mentioned:
• H-Store runs on a grid
2. The NoSQL-Movement | 13
• On each rows of tables are placed contiguously in main memory
• B-tree indexing is used
• Sites are partitioned into logical sites which are dedicated to one CPU core
• Logical sites are completely independent having their own indexes, tuple storage and partition of
main memory of the machine they run on
• H-Store works single-threaded and runs transactions uninterrupted
• H-Store allows to run only predefined transactions implemented as stored procedures
• H-Store omits the redo-log and tries to avoid writing an undo-log whenever possible; if an undo-log
cannot be avoided it is discarded on transaction commit
• If possible, query execution plans exploit the single-sited and one-shot properties discussed above
• H-Store tries to achieve the no-knobs and high availability requirements as well as transformation
of transactions to be single-sited by “an automatical physical database designer which will specify
horizontal partitioning, replication locations, indexed fields”
• Since H-Store keeps replicas of each table these have to be updated transactionally. Read commands
can go to any copy of a table while updates are directed to all replicas.
• H-Store leverages the above mentioned schema and transaction characteristics for optimizations, e.g.
omitting the undo-log in two-phase transactions.
TPC-C Benchmark
When comparing their H-Store prototype with a commercial relational DBMS Stonebraker et al. apply
some important tricks to the benchmarks implementation. First, they partition the database scheme and
replicate parts of it in such a way that “the schema is decomposed such that each site has a subset of the
records rooted at a distinct partition of the warehouses”. Secondly, they discuss how to profit of transaction
characteristics discussed above. If the benchmark would run “on a single core, single CPU machine” then
“every transaction class would be single-sited, and each transaction can be run to completion in a single-
threaded environment”. In a ”paired-HA site [. . . ]all transaction classes can be made strongly two-phase,
meaning that all transactions will either succeed or abort at both sites. Hence, on a single site with a
paired HA site, ACID properties are achieved with no overhead whatsoever.“ By applying some further
tricks, they achieve that ”with the basic strategy [of schema partitioning and replication (the author of this
paper)] augmented with the tricks described above, all transaction classes become one-shot and strongly
two-phase. As long as we add a short delay [. . . ], ACID properties are achieved with no concurrency control
overhead whatsoever.”
Based on this setting, they achieved a 82 times better performance compared to a commercial DBMS.
They also analyzed the overhead of performance in the commercial DBMS and examined that it was mainly
caused by logging and concurrency control.
It has to be said that Stonebraker et al. implemented only part of the TPC-C benchmark and do not seem
to have adapted the TPC-C benchmark to perfectly fit with the commercial DBMS as they did for their own
H-Store prototype although they hired a professional DBA to tune the DBMS they compared to H-Store
and also tried to optimize the logging of this system to allow it to perform better.
2. The NoSQL-Movement | 14
Consequences
As a result of their analysis Stonebraker et al. conclude that “we are heading toward a world with at least
5 (and probably more) specialized engines and the death of the “one size fits all” legacy systems”. This
applies to the relational model as well as its query language SQL.
Stonebraker et al. state that in contrast to the 1970s when “the DBMS world contained only business
data processing applications” nowadays there are at least the following markets which need specialized
DBMSs
4
:
1. Data warehouses which typically have star or snowflake schemes, i. e. “a central fact table with
1-n joins to surrounding dimension tables, which may in turn participate in further 1-n joins to
second level dimension tables, and so forth”. These datastructures could be easily modeled using the
relational model but Stonebraker et al. suggest an entity-relationship model in this case which would
be simpler and more natural to model and to query.
2. The stream processing market has different requirements, namely to “Process streams of messages
at high speed [and to] Correlate such streams with stored data”. An SQL generalization called
StreamSQL which allows to mix streams and relational data in SQL FROM-clauses has caused some
enthusiasm and been suggested for standardization in this field. Stonebraker et al. also mention a
problem in stream processing often requiring stream data to be flat (as some news agencies deliver
it) but there is also a need for hierarchically structured data. Therefore, they “expect the stream
processing vendors to move aggressively to hierarchical data models” and that “they will assuredly
deviate from Ted Codd’s principles”.
3. Text processing is a field where relational databases have never been used.
4. Scientific-oriented databases will likely supply arrays rather than tables as their basic data structure.
5. Semi-structured data is a field where useful data models are still being discussed. Suggestions
include e.g. XML schema (fiercely debated because of its complexity) and RDF.
While “the relational model was developed for a “one size fits all” world, the various specialized systems
which we envision can each rethink what data model would work best for their particular needs“ Stonebraker
et al. conclude.
Regarding query languages for DBMSs they argue against a “one size fits all language” like SQL as, in
their opinion, it has no use case at all: in the OLTP market ad-hoc queries are seldom or not needed,
applications query in a prepared statement fashion or the query logic is deployed into the DBMS as stored
procedures. In opposition to this, other DBMS markets like data warehouses need abilities for complex
ad-hoc queries which are not fulfilled by SQL. For this reason, Stonebraker et al. do not see a need for this
language any more.
For specialized DBMSs in the above mentioned markets they furthermore discuss how these languages
should integrate with programming languages and argue against data sublanguages “interfaced to any
programming language” as it is done in JDBC and ODBC. “[this] has led to high overhead interfaces”.
Stonebraker et al. therefore suggest an “embedding of database capabilities in programming languages”.
Examples of such language embeddings include Pascal R and Rigel in the 1970s or Microsoft’s LINQ-
approach in the .NET platform nowadays. Regarding the languages to integrate such capabilities they are
in favor of what they call “little languages” like Python, Perl, Ruby and PHP which are “open source, and
can be altered by the community” and are additionally “less daunting to modify than the current general
4
Further details on these DBMS markets can be found in the earlier released paper “One Size Fits All”: An Idea Whose Time
Has Come and Gone (cf. [Sc05])
2. The NoSQL-Movement | 15
purpose languages” (that appear to them as a “one size fits all approach in the programming languages
world”). For their H-Store prototype they plan to move from C++ to Ruby for stored procedures.
2.1.3. Main Drivers
The NoSQL movement has attracted a great number of companies and projects over the last couple of years.
Especially big web companies or businesses running large and highly-frequented web sites have switched
from relational databases (often with a caching layer typically realized with memcached
5
, cf. [Hof10c],
[Hof10b]) towards non-relational datastores. Examples include Cassandra ([Apa10d]) originally developed
at Facebook and also used by Twitter and Digg today (cf. [Pop10a], [Eur09]), Project Voldemort developed
and used at LinkedIn, cloud services like the NoSQL store Amazon SimpleDB (cf. [Ama10b]) as well as
Ubuntu One, a cloud storage and synchronization service based on CouchDB (cf. [Can10c], [Hof10c]).
These users of NoSQL datastores are naturally highly interested in the further development of the non-
relational solutions they use. However, most of the popular NoSQL datastores have adopted ideas of either
Google’s Bigtable (cf. [CDG
+
06]) or Amazon’s Dynamo (cf. [DHJ
+
07]); Bigtable-inspired NoSQL stores are
commonly referred to as column-stores (e.g. HyperTable, HBase) whereas the Dynamo influenced most of
the key-/values-stores (e.g. Cassandra [Apa10d], Redis [S
+
10], Project Voldemort [K
+
10a]). Other projects
pursue different attempts like graph-databases that form an own class of data stores and document-stores
which can be seen as key/value-stores with additional features (at least allowing different, often hierarchical
namespaces for key/value-pairs which provides the abstraction of ”documents“); at least one of the latter
(CouchDB) is a reimplementation of existing document stores such as Lotus Notes, which has been around
since the 1990s and is consequently not designed with the awareness of current web technologies (which
is criticized by CouchDB-developers who consequently implemented their document-store from scratch,
cf. [Apa10c], [PLL09]). In summary, it can be concluded that the pioneers of the NoSQL movement are
mainly big web companies or companies running large-scale web sites like Facebook, Google and Amazon
(cf. [Oba09a]) and others in this field have adopted their ideas and modified them to meet their own
requirements and needs.
2.2. Criticism
2.2.1. Scepticism on the Business Side
In an article about the NoSQL meet-up in San Francisco Computerworld mentions some business related
issues concerning NoSQL databases. As most of them are open-source software they are well appreciated
by developers who do not have to care about licensing and commercial support issues. However, this can
scare business people in particular in the case of failures with nobody to blame for. Even at Adobe the
developers of ConnectNow which uses a Terracotta cluster instead of a relational database were only able
to convince their managers when they saw the system up and running (cf. [Com09a]).
2.2.2. NoSQL as a Hype
Some businesses appear to be cautious towards NoSQL as the movement seems like a hype potentially
lacking the fulfillment of its promises. This is a general skepticism towards new technologies provoking
considerable enthusiasm and has been expressed e. g. by James Bezdek in an IEEE editorial as follows:
5
Examples include Friendfeed, Wikipedia, XING, StudiVz/SchülerVz/MeinVz
2. The NoSQL-Movement | 16
“Every new technology begins with naïve euphoria – its inventor(s) are usually submersed in the
ideas themselves; it is their immediate colleagues that experience most of the wild enthusiasm.
Most technologies are overpromised, more often than not simply to generate funds to continue
the work, for funding is an integral part of scientific development; without it, only the most
imaginative and revolutionary ideas make it beyond the embryonic stage. Hype is a natural
handmaiden to overpromise, and most technologies build rapidly to a peak of hype. Following
this, there is almost always an overreaction to ideas that are not fully developed, and this
inevitably leads to a crash of sorts, followed by a period of wallowing in the depths of cynicism.
Many new technologies evolve to this point, and then fade away. The ones that survive do so
because someone finds a good use (= true user benefit) for the basic ideas.” (cf. [Bez93] cited
in [For10])
The participants of the NoSQL meet-up in San Francisco gave pragmatic advice for such remarks: com-
panies do not miss anything if they do not switch to NoSQL databases and if a relational DBMS does
its job, there is no reason to replace it. Even the organizer of the meet-up, Johan Oskarsson of Last.fm,
admitted that Last.fm did not yet use a NoSQL database in production as of June 2009. He furthermore
states that NoSQL databases “aren’t relevant right now to mainstream enterprises, but that might change
one to two years down the line” (Johan Oskarsson, Last.fm, cf. [Com09a]). Nonetheless, the participants
of the NoSQL meet-up suggest to take a look at NoSQL alternatives if it is possible and it makes sense
(e. g. in the development of new software) (cf. [Com09a]). Blogger Dennis Forbes does not see any ov-
erenthusiasm among the inventors and developers of non-relational datastores (“most of them are quite
brilliant, pragmatic devs”) but rather among developers using these technologies and hoping that “this
movement invalidates their weaknesses”. He—coming from traditional relational database development
for the financial, insurance, telecommunication and power generation industry—however states that “there
is indisputably a lot of fantastic work happening among the NoSQL camp, with a very strong focus on
scalability”. On the other hand, he criticizes in a postnote to his blog post that “the discussion is, by nature
of the venue, hijacked by people building or hoping to build very large scale web properties (all hoping to be
the next Facebook), and the values and judgments of that arena are then cast across the entire database
industry—which comprises a set of solutions that absolutely dwarf the edge cases of social media—which
is really...extraordinary” (cf. [For10]).
2.2.3. NoSQL as Being Nothing New
Similar to the hype argument are common remarks by NoSQL critics that NoSQL databases are nothing
new since other attempts like object databases have been around for decades. As an example for this
argument blogger David Intersimone mentions Lotus Notes which can be subsumed as an early document
store supporting distribution and replication while favoring performance over concurrency control (unless
otherwise indicated, [Int10]). This example is especially interesting as the main developer of CouchDB,
Damien Katz, worked for Lotus Notes for several years. NoSQL advocates comment that CouchDB is ’Notes
done right’ as Notes’ distribution features were not aware of current web technologies and the software
also got bloated with business relevant features instead of beeing just a slim datastore ([PLL09]).
Examples like Lotus Notes, business analytic or stream processing oriented datastores show that these
alternatives to relational databases have existed for a long time and blogger Dennis Forbes criticizes therefore
that the “one size fitting it all” argument is nothing more but a strawman since few people ever held “Rdbms’
as the only tool for all of your structured and unstructured data storage needs” (cf. [For10]).
2. The NoSQL-Movement | 17
2.2.4. NoSQL Meant as a Total “No to SQL”
At first, many NoSQL advocates especially in the blogosphere understood the term and the movement
as a total denial of RDBMSs and proclaimed the death of these systems. Eric Evans to whom the term
“NoSQL” is often credited though he was not the first who used it (see section 2.1 and e. g. [Ell09a])
suggested in a blog post of 2009 that the term now should mean “Not only SQL” instead of “No to SQL”
(cf. [Eva09b]). This term has been adopted by many bloggers as it stresses that persistence in databases
does not automatically mean to use a relational DBMS but that alternatives exist. Blogger Nati shalom
comments this shift in the following way: “I think that what we are seeing is more of a realization that
existing SQL database alternatives are probably not going away any time soon, but at the same time they
can’t solve all the problems of the world. Interestingly enough the term NOSQL has now been changed
to Not Only SQL, to represent that line of thought” (cf. [Sha09a]). Some bloggers stress that the term is
imprecise such as Dare Obasanjo saying that “there is a[sic!] yet to be a solid technical definition of what
it means for a product to be a "NoSQL" database aside from the fact that it isn’t a relational database”
(cf. [Oba09a]). Others, such as Michael Stonebraker claim that it has nothing to do with SQL at all
6
and should be named something like “NoACID“ as suggested by Dennis Forbes, who refers to Stonebraker
in his suggestion ([For10]). Still others such as Adam Keys criticize the term “NoSQL” as defining the
movement by what it does not stand for ([Key09]): “The problem with that name is that it only defines
what it is not. That makes it confrontational and not amazingly particular to what it includes or excludes.
[. . . ] What we’re seeing its [sic!] the end of the assumption that valuable data should go in some kind
of relational database. The end of the assumption that SQL and ACID are the only tools for solving
our problems. The end of the viability of master/slave scaling. The end of weaving the relational model
through our application code”. He suggests to subsume the movement and the datastores under the term
“post-relational” instead of “NoSQL”: “We’re seeing an explosion in the ideas about how one should store
important data. We’re looking at data to see if it’s even worth persisting. We’re experimenting with new
semantics around structure, consistency and concurrency. [. . . ] In the same way that post-modernism is
about reconsidering the ways of the past in art and architecture, post-relational is a chance for software
developers to reconsider our own ways. Just as post-modernism didn’t invalidate the entire history of art,
post-relational won’t invalidate the usefulness of relational databases.” (cf. [Key09]). However, as the
readers of his blog post comment this term is not that much better than “NoSQL” as it still defines the
movement and the databases by what they do not reflect (or better: by what they have omitted) instead
of what they stand for.
The irritation about the term and its first notion as a total neglect of relational databases has lead to
many provoking statements by NoSQL advocates
7
and caused a number of unfruitful discussions and some
flamewars (see e. g. [Dzi10] and as a response to it [Sch10]).
2.2.5. Stonebraker’s Critical Reception of NoSQL Databases
In his blog post “The “NoSQL” Discussion has Nothing to Do With SQL” ([Sto09]) Michael Stonebraker
states that there has been a lot of buzz around NoSQL databases lately. In his reception the main drivers
behind NoSQL conferences in the US are advocates of document stores and key/values-stores which provide
a “a low-level record-at-a-time DBMS interface, instead of SQL” in his sight. Stonebraker sees two reasons
for moving towards non-relational datastores—flexibility and performance.
6
See the next section on Stonebraker’s reception of the NoSQL-movement which goes far beyond criticizing only the term
“NoSQL“.
7
E. g. “The ACIDy, Transactional, RDBMS doesn’t scale, and it needs to be relegated to the proper dustbin before it does
any more damage to engineers trying to write scalable software”. The opinion expressed here has been softened by the
author in a postnote to his blog post: “This isn’t about a complete death of the RDBMS. Just the death of the idea that
it’s a tool meant for all your structured data storage needs.” (cf. [Ste09] cited in [For10])
2. The NoSQL-Movement | 18
The Flexibility Argument is not further examined by Stonebraker but it contains the following view:
there might be data that does not fit into a rigid relational model and which is bound too much by
the structure of a RDBMS. For this kind of data something more flexible is needed.
The Performance Argument is described as follows Stonebraker: one starts with MySQL to store data
and performance drops over the time. This leads to the following options: either to shard/partition
data among several sites causing “a serious headache managing distributed data” in the application;
or to move from MySQL towards a commercial RDMBS which can provoke large licensing fees; or
to even totally abandon a relational DBMS.
Stonebraker subsequently examines the latter argument in his blog post. He focuses on “workloads for
which NoSQL databases are most often considered: update- and lookup-intensive OLTP workloads, not
query-intensive data warehousing workloads” or specialized workflows like document-repositories.
Stonebraker sees two options to improve the performance of OLTP transactions:
1. Horizontal scaling achieved by automatic sharding “over a shared-nothing processing environment“.
In this scenario performance gets improved by adding new nodes. In his point of view, RDMBSs
written in the last ten years provide such a “shared nothing architecture” and “nobody should ever
run a DBMS that does not provide” this.
2. Improvement of the OLTP performance of a single node.
Stonebraker focuses on the second option and analyzes the sources of overhead which decrease performance
of OLTP transactions on a single node; as indicated by the title of his blog post, these have no relation
to the the query language (SQL). He states only a small percentage of total transaction cost is incurred
by useful work and sees five sources of performance overhead that have to be addressed when single node
performance should be optimized:
Communication between the application and the DBMS via ODBC or JDBC. This is considered the main
source of overhead in OLTP transactions which is typically addressed as follows: “Essentially all
applications that are performance sensitive use a stored-procedure interface to run application logic
inside the DBMS and avoid the crippling overhead of back-and-forth communication between the
application and the DBMS”. The other option to reduce communication overhead is using an embed-
dable DBMS which means that the application and the DBMS run in the same address space; because
of strong coupling, security and access control issues this is no viable alternative “for mainstream
OLTP, where security is a big deal” in Stonebrakers sight.
Logging is done by traditional DBMSs in addition to modifications of relational data on each transaction.
As log files are persisted to disk to ensure durability logging is expensive and decreases transaction
performance.
Locking of datasets to be manipulated causes overhead as write operations in the lock-table have to occur
before and after the modifications of the transaction.
Latching because of shared data structures (e.g. B-trees, the lock-table, resource-tables) inside an RDBMS
incurs further transaction costs. As these datastructures have to be accessed by multiple threads
short-term locks (aka latches) are often used to provide parallel but careful access to them.
Buffer Management finally also plays its part when it comes to transaction overhead. As data in tradi-
tional RDBMSs is organized in fixed pages work has to be done to manage the disk-pages cached in
memory (done by the buffer-pool) and also to resolve database entries to disk pages (and back) and
identify field boundaries.
2. The NoSQL-Movement | 19
As stated before, communication is considered the main source of overhead according to Stonebraker and
by far outweighs the other ones (take from this survey: [HAMS08]) which almost equally increase total
transaction costs. Besides avoiding communication between the application and the database all four
other sources of performance overhead have to be eliminated in order to considerably improve single node
performance.
Now, datastores whether relational or not have specific themes in common and NoSQL databases also have
to address the components of performance overhead mentioned above. In this context, Stonebraker raises
the following examples:
• Distribution of data among multiple sites and a shared-nothing approach is provided by relational as
well as non-relational datastores. “Obviously, a well-designed multi-site system, whether based on
SQL or something else, is way more scalable than a single-site system” according to Stonebraker.
• Many NoSQL databases are disk-based, implement a buffer pool and are multi-threaded. When
providing these features and properties, two of the four sources of performance overhead still remain
(Locking, Buffer management) and cannot be eliminated.
• Transaction-wise many NoSQL datastores provide only single-record transactions with BASE proper-
ties (see chapter 3 on that). In contrast to relational DBMSs ACID properties are sacrificed in favor
of performance.
Stonebraker consequently summarizes his considerations as follows: “However, the net-net is that the
single-node performance of a NoSQL, disk-based, non-ACID, multithreaded system is limited to be a modest
factor faster than a well-designed stored-procedure SQL OLTP engine. In essence, ACID transactions are
jettisoned for a modest performance boost, and this performance boost has nothing to do with SQL”. In
his point of view, the real tasks to speed up a DBMS focus on the elimination of locking, latching, logging
and buffer management as well as support for stored procedures which compile a high level language (such
as SQL) into low level code. How such a system can look like is described in the paper “The end of an
architectural era: (it’s time for a complete rewrite)” ([SMA
+
07]) that has already been discussed above.
Stonebraker also does not expect SQL datastores to die but rather states: “I fully expect very high speed,
open-source SQL engines in the near future that provide automatic sharding. [. . . ] Moreover, they will con-
tinue to provide ACID transactions along with the increased programmer productivity, lower maintenance,
and better data independence afforded by SQL.” Hence “high performance does not require jettisoning
either SQL or ACID transactions”. It rather “depends on removing overhead” caused by traditional imple-
mentations of ACID transactions, multi-threading and disk management. The removal of these sources of
overhead “is possible in either a SQL context or some other context”, Stonebraker concludes.
2.2.6. Requirements of Administrators and Operators
In his blog post “The dark side of NoSQL” (cf. [Sch09]) Stephan Schmidt argues that the NoSQL debate is
dominated by a developer’s view on the topic which usually iterates on properties and capabilities developers
like (e.g. performance, ease of use, schemalessness, nice APIs) whereas the needs of operations people and
system administrators are often forgotten in his sight. He reports that companies
8
encounter difficulties
especially in the following fields:
Ad Hoc Data Fixing To allow for ad hoc data fixing there first has to be some kind of query and ma-
nipulation language. Secondly, it is more difficult to fix data in distributed databases (like Project
Voldemort or Cassandra) compared to datastores that run on a single node or have dedicated shards.
8
He cites an Infinispan director and the vice president of engineering at a company called Loop.
2. The NoSQL-Movement | 20
Ad Hoc Data Querying Similarly to data fixing a query and manipulation for the particular datastore
is required when it comes to ad hoc queries and querying distributed datastores is harder than
querying centralized ones. Schmidt states that for some reporting tasks the MapReduce approach
(cf. [DG04]) is the right one, but not for every ad hoc query. Furthermore, he sees the rather cultural
than technical problem that customers have become trained and “addicted” to ad hoc reporting and
therefore dislike the absence of these means. For exhaustive reporting requirements Schmidt suggests
to use a relational database that mirrors the data of live databases for which a NoSQL store might
be used due to performance and scalability requirements.
Data Export Schmidt states that there are huge differences among the NoSQL databases regarding this
aspect. Some provide a useful API to access all data and in some it is absent. He also points out
that it is more easy to export data from non-distributed NoSQL stores like CouchDB, MongoDB or
Tokyo Tyrant as from distributed ones like Projekt Voldemort or Cassandra.
Schmidt’s points are humorously and extensively iterated in the talk “Your Guide to NoSQL” (cf. [Ake09])
which especially parodies the NoSQL advocates’ argument of treating every querying need in a MapReduce
fashion.
2.2.7. Performance vs. Scalability
BJ Clark presents an examination of various NoSQL databases and MySQL regarding performance and
scalability in his blog post “NoSQL: If only it was that easy”. At first, he defines scalability as “to change
the size while maintaining proportions and in CS this usually means to increase throughput.” Blogger
Dennis Forbes agrees with this notion of scalabilty as “pragmatically the measure of a solution’s ability to
grow to the highest realistic level of usage in an achievable fashion, while maintaining acceptable service
levels” (cf. [For10]). BJ Clark continues: “What scaling isn’t: performance. [. . . ] In reality, scaling doesn’t
have anything to do with being fast. It has only to do with size. [. . . ] Now, scaling and performance do
relate in that typically, if something is performant, it may not actually need to scale.” (cf. [Cla09]).
Regarding relational databases Clark states that “The problem with RDBMS isn’t that they don’t scale,
it’s that they are incredibly hard to scale. Ssharding[sic!] is the most obvious way to scale things, and
sharding multiple tables which can be accessed by any column pretty quickly gets insane.” Blogger Dennis
Forbes agrees with him that “There are some real scalability concerns with old school relational database
systems” (cf. [For10]) but that it is still possible to make them scale using e. g. the techniques described
by Adam Wiggins (cf. [Wig09]).
Besides sharding of relational databases and the avoidance of typical mistakes (as expensive joins caused
by rigid normalization or poor indexing) Forbes sees vertical scaling as still an option that can be easy,
computationally effective and which can lead far with “armies of powerful cores, hundreds of GBs of
memory, operating against SAN arrays with ranks and ranks of SSDs”. On the downside, vertical scaling
can relatively costly as Forbes also admits. But Forbes also argues for horizontal scaling of relational
databases by partitioning data and adding each machine to a failover cluster in order to achieve redundancy
and availability. Having deployments in large companies in mind where constraints are few and money is
often not that critical he states from his own experience
9
that “This sort of scaling that is at the heart
of virtually every bank, trading system, energy platform, retailing system, and so on. [. . . ] To claim that
SQL systems don’t scale, in defiance of such obvious and overwhelming evidence, defies all reason” (cf.
[For10]). Forbes argues for the use of own servers as he sees some artificial limits in cloud computing
environments such as limitations of IO and relatively high expenditures for single instances in Amazon’s
EC2; he states that “These financial and artificial limits explain the strong interest in technologies that
allows you to spin up and cycle down as needed” (cf. [For10]).
9
Forbes has worked in the financial, assurance, telecommunication and power supply industry.
2. The NoSQL-Movement | 21
BJ Clark continues his blog post by an evaluation of some NoSQL datastores with a focus on automatic
scalability (such as via auto-sharding) as he updates millions of objects (primary objects as he calls them)
on which other objects depend in 1:1 and 1:n relationships (he calls them secondary objects); secondary
objects are mostly inserted at the end of tables.
His evaluation can be summarized in the following way:
• The key/value-stores Tokyo Tyrant/Cabinet and Redis do not provide means for automatic, hor-
izontal scalability. If a machine is added—similar to memcached—it has to be made known to
the application which then (re-)hashes the identifiers of database entries against the collection of
database servers to benefit from the additional ressources. On the other hand he states that Tokyo
Tyrant/Cabinet and Redis perform extremely well so that the need for scaling horizontally will not
appear very early.
• The distributed key/value-store Project Voldemort utilizes additional servers added to a cluster
automatically and also provides for fault tolerance
10
. As it concentrates on sharding and fault-
tolerance and has a pluggable storage architecture, Tokyo Tyrant/Cabinet or Redis can be used as a
storage backend for Voldemort. This might also be a migration path from these systems if they need
to be scaled.
• The document-database MongoDB showed good performance characteristics but did not scale au-
tomatically at the time of the evaluation as it did not provide automatic sharding (which has changed
in version 1.6 released in August 2010 cf. [Mon10] and [MHC
+
10b]).
• Regarding the column-database Cassandra Clark thinks that it is “definitely supposed to scale, and
probably does at Facebook, by simply adding another machine (they will hook up with each other
using a gossip protocol), but the OSS version doesn’t seem to support some key things, like loosing
a machine all together”. This conclusion reflects the development state of Cassandra at the time of
the evaluation.
• The key/value store S3 of Amazon scaled very well, although, due to Clark, it is not as performant
as other candidates.
• MySQL, in comparison, does not provide automatic horizontal scalability by e. g. automatic sharding,
but Clark states that for most applications (and even web applications like Friendfeed, cf. [Tay09])
MySQL is fast enough and—in addition—is “familiar and ubiquitous”. In comparison to Tokyo
Tyrant/Cabinet and Redis Clark concludes that “It can do everything that Tokyo and Redis can do,
and it really isn’t that much slower. In fact, for some data sets, I’ve seen MySQL perform ALOT[sic!]
faster than Tokyo Tyrant” and “it’s just as easy or easier to shard MySQL as it is Tokyo or Redis,
and it’s hard to argue that they can win on many other points.”
The systems mentioned in the above evaluation will discussed in more detail later on in this paper. Besides,
it has to be mentioned that the evaluation took place in summer of 2009 (the blog post is of August),
therefore results reflect the development state of the evaluated systems at that time.
Clark summarizes his results by indicating that RDBMSs are not harder to scale than “lots of other things”
in his perspective, and that only a couple of NoSQL databases provide means for automatic, horizontal
scalability allowing to add machines while not requiring operators to interact. Therefore, it could be even
argued that “it’s just as easy to scale mysql (with sharding via mysql proxy) as it is to shard some of these
NoSQL dbs.” Therefore he does not proclaim an early death of RDBMSs and reminds that MySQL is still
in use at big web sites like Facebook, Wikipedia and Friendfeed. For new applications he suggests to use
the tool fitting the job best, reflecting that non-relational databases—just like relational ones—are no “one
size fits all” solutions either:
10
Redis in particular does not offer fault-tolerance and as data is held in memory it will be lost if a server crashes.
2. The NoSQL-Movement | 22
“If I need reporting, I won’t be using any NoSQL. If I need caching, I’ll probably use Tokyo
Tyrant. If I need ACIDity, I won’t use NoSQL. If I need a ton of counters, I’ll use Redis. If I
need transactions, I’ll use Postgres. If I have a ton of a single type of documents, I’ll probably
use Mongo. If I need to write 1 billion objects a day, I’d probably use Voldemort. If I need full
text search, I’d probably use Solr. If I need full text search of volatile data, I’d probably use
Sphinx.”
2.2.8. Not All RDBMSs Behave like MySQL
An argument often found in the NoSQL debate is that RDBMSs do not scale very well and are difficult to
shard. This is often pointed out by the example of MySQL. Furthermore, NoSQL databases are sometimes
seen as the successor of a MySQL plus memcached solution (cf. e.g. [Hof10c]) where the latter is taking
load away from the database to decrease and defer the need to distribute it. Concerning these typical
arguments blogger Dennis Forbes reminds that RDBMSs in general cannot be easily identified with MySQL
but others may be easier or better scalable: “MySQL isn’t the vanguard of the RDBMS world. Issues
and concerns with it on high load sites have remarkably little relevance to other database systems” (cf.
[For10]).
2.2.9. Misconceptions of Critics
NoSQL advocate Ben Scofield responds to some of the criticism mentioned above which he perceives to
be misconceived. He does so by expressing incisive arguments from the NoSQL debate responding to them
(cf. [Sco09]):
“NoSQL is just about scalability and/or performance.” Scofield argues that this could be an attrac-
tive claim for those “traditionalists” (as he calls them) who think that NoSQL data stores can be
made obsolete by making RDBMSs faster and more scalable. He claims that “there’s a lot more to
NoSQL than just performance and scaling” and that for example “NoSQL DBs often provide better
substrates for modeling business domains”.
“NoSQL is just document databases, or key-value stores, or . . . ” Scofield notes that many NoSQL-
articles address only document-oriented databases ore key-value stores, sometimes column-stores. He
states that “Good arguments can be made against each of those solutions for specific circumstances,
but those are arguments against a specific type of storage engine.” Scofield therefore criticizes that
narrowing the discussion to only one sort of NoSQL databases allows traditionalists to argue easily
against the whole movement or whole set of different NoSQL approaches.
“I can do NoSQL just as well in a relational database.” With the frequent argument of Friendfeed’s
usage of MySQL (cf. [Tay09]) in mind, Scofield notes that although it is possible to tweak and tune
a relational database this does not make sense for all types of data. “Different applications are good
for different things; relational databases are great for relational data, but why would you want to use
them for non-relational data?” he asks.
“NoSQL is a wholesale rejection of relational databases.” Some time ago this claim was often heard
in the NoSQL community but it became less common which Scofield appreciates that: “It seems
that we’re moving towards a pluralistic approach to storing our data, and that’s a good thing. I’ve
suggested ’polyglot persistence’ for this approach (though I didn’t coin the term), but I also like Ezra
Zygmuntowicz’s ’LessSQL’ as a label, too.”
2. The NoSQL-Movement | 23
2.3. Classifications and Comparisons of NoSQL Databases
In the last years a variety of NoSQL databases has been developed mainly by practitioners and web com-
panies to fit their specific requirements regarding scalability performance, maintainance and feature-set.
As it has been revealed some of these databases have taken up ideas from either Amazon’s Dynamo (cf.
[DHJ
+
07]) or Google’s Bigtable (cf. [CDG
+
06]) or a combination of both. Others have ported ideas in
existing databases towards modern web technologies such as CouchDB. Still others have pursued totally
different approaches like Neo4j or HypergraphDB.
Because of the variety of these approaches and overlappings regarding the nonfunctional requirements and
the feature-set it could be difficult to get and maintain an overview of the nonrelational database scene.
So there have been various approaches to classify and subsume NoSQL databases, each with different
categories and subcategories. Some classification approaches shall be presented here out of which one
possibility to classify NoSQL datastores will be pursued in the subsequent chapters.
2.3.1. Taxonomies by Data Model
Concerning the classification of NoSQL stores Highscalability author Todd Hoff cites a presentation by
Stephen Yen in his blog post “A yes for a NoSQL taxonomy” (cf. [Hof09c]). In the presentation “NoSQL
is a Horseless Carriage” (cf. [Yen09]) Yen suggests a taxononmy that can be found in table 2.1.
Term Matching Databases
Key-Value-Cache Memcached
Repcached
Coherence
Infinispan
EXtreme Scale
Jboss Cache
Velocity
Terracoqa
Key-Value-Store keyspace
Flare
Schema Free
RAMCloud
Eventually-Consistent Key-Value-
Store
Dynamo
Voldemort
Dynomite
SubRecord
Mo8onDb
Dovetaildb
Ordered-Key-Value-Store Tokyo Tyrant
Lightcloud
NMDB
Luxio
MemcacheDB
Actord
2. The NoSQL-Movement | 24
Term Matching Databases
Data-Structures Server Redis
Tuple Store Gigaspaces
Coord
Apache River
Object Database ZopeDB
DB4O
Shoal
Document Store CouchDB
Mongo
Jackrabbit
XML Databases
ThruDB
CloudKit
Perservere
Riak Basho
Scalaris
Wide Columnar Store Bigtable
Hbase
Cassandra
Hypertable
KAI
OpenNeptune
Qbase
KDI
Table 2.1.: Classifications – NoSQL Taxonomy by Stephen Yen (cf. [Yen09])
A similar taxonomy which is less fine-grained and comprehensive than the classification above can be found
in the article “Databases in the cloud” by Ken North (cf. [Nor09]). Table 2.2 summarizes his classification
of datastores that additionally include some datastores available in cloud-computing environments only.
Category Matching databases
Distributed Hash Table, Key-Value Data Stores memcached
MemcacheDB
Project Voldemort
Scalaris
Tokyo Cabinet
Entity-Attribute-Value Datastores Amazon SimpleDB
Google AppEngine datastore
Microsoft SQL Data Services
Google Bigtable
Hadoop
HyperTable
HBase
2. The NoSQL-Movement | 25
Category Matching databases
Amazon Platform Amazon SimpleDB
Document Stores, Column Stores Sybase IQ
Vertica Analytic Database
Apache CouchDB
Table 2.2.: Classifications – Categorization by Ken North (cf. [Nor09]
Similarly to the classifications mentioned above Rick Cattel subsumes different NoSQL databases primarily
by their data model (cf. [Cat10]) as shown in table 2.3.
Category Matching databases
Key-value Stores Redis
Scalaris
Tokyo Tyrant
Voldemort
Riak
Document Stores SimpleDB
CouchDB
MongoDB
Terrastore
Extensible Record Stores Bigtable
HBase
HyperTable
Cassandra
Table 2.3.: Classifications – Categorization by Rick Cattell (cf. [Cat10]
2.3.2. Categorization by Ben Scofield
Blogger Alex Popescu summarizes a presentation by Ben Scofield who gave a generic introduction to NoSQL
databases along with a categorization and some ruby examples of different NoSQL databases (cf. [Sco10]).
The categorization is in fact a short comparison of classes of NoSQL databases by some nonfunctional
categories (“(il)ities“) plus a rating of their feature coverage. Popescu summarizes Scofield’s ideas as
presented in table 2.4.
2. The NoSQL-Movement | 26
Performance Scalability Flexibility Complexity Functionality
Key-Value Stores high high high none variable (none)
Column stores high high moderate low minimal
Document stores high variable (high) high low variable (low)
Graph databases variable variable high high graph theory
Relational databases variable variable low moderate relational algebra
Table 2.4.: Classifications – Categorization and Comparison by Scofield and Popescu (cf. [Pop10b],
[Sco10])
2.3.3. Comparison by Scalability, Data and Query Model, Persistence-Design
In his blog post “NoSQL ecosystem” Jonathan Ellis discusses NoSQL datastores by three important as-
pects:
1. Scalability
2. Data and query model
3. Persistence design
Scalability
Ellis argues that it is easy to scale read operations by replication of data and load distribution among
those replicas. Therefore, he only investigates the scaling of write operations in databases that are really
distributed and offer automatic data partitioning. When data size exceeds the capabilities of a single
machine the latter systems seem to be the only option to him if provided no will to partition data manually
(which is not a good idea according to [Oba09b]). For the relevant distributed systems which provide
auto-sharding Ellis sees two important features:
• Support for multiple datacenters
• Possibility to add machines live to an existing cluster, transparent for applications using this cluster
By these features Ellis compares a selection of NoSQL datastores fulfilling the requirements of real distri-
bution and auto-sharding (cf. table 2.5).
Datastore Add Machines Live Multi-Datacenter Support
Cassandra x x
HBase x
Riak x
Scalaris x
Voldemort Some code required
Table 2.5.: Classifications – Comparison of Scalability Features (cf. [Ell09a])
2. The NoSQL-Movement | 27
The following NoSQL stores have been excluded in this comparison as they are not distributed in the way
Ellis requires (at the time of his blog post in November 2009): CouchDB, MongoDB, Neo4j, Redis and
Tokyo Cabinet. Nonetheless, these systems can find use as a persistence layer for distributed systems,
according to him. The document databases MongoDB and CouchDB supported limited support for auto-
sharding at the time of his investigation (MongoDB out of the box, CouchDB by partitioning/clustering
framework Lounge). Regarding Tokyo Cabinet, Ellis notices that it can be used as a storage backend for
Project Voldemort.
Data and Query Model
The second area Ellis examines is the data model and the query API offered by different NoSQL stores.
Table 2.6 shows the results of his investigation pointing out a great variety of data models and query
APIs.
Datastore Data Model Query API
Cassandra Columnfamily Thrift
CouchDB Document map/reduce views
HBase Columnfamily Thrift, REST
MongoDB Document Cursor
Neo4j Graph Graph
Redis Collection Collection
Riak Document Nested hashes
Scalaris Key/value get/put
Tokyo Cabinet Key/value get/put
Voldemort Key/value get/put
Table 2.6.: Classifications – Comparison of Data Model and Query API (cf. [Ell09a])
Ellis makes the following remarks concerning the data models and query APIs of these systems:
• The columnfamily model, implemented by Cassandra and HBase is inspired by the corresponding
paragraph in the second section of Google’s Bigtable paper (cf. [CDG
+
06, Page 2]). Cassandra omits
historical versions in contrast to Bigtable and introduces the further concept of supercolumns. In
Cassandra as well as HBase rows are sparse
11
, which means that they may have different numbers
of cells and columns do not have to be defined in advance.
• The key/value model is easiest to implement but may be inefficient if one is only interested in
requesting or updating part of the value associated with a certain key. Furthermore, it is difficult to
build complex data structures on top of key/value stores (as Ellis describes in another blog post, cf.
[Ell09b]).
11
See e.g. the Wikipedia-article on Sparse arrays
2. The NoSQL-Movement | 28
• Ellis sees document databases being the next step from key/value stores as they allow nested
values. They permit to query data structures more efficiently than key/value stores as they do not
necessarily reply whole BLOBs when requesting a key.
• The graph database Neo4j has a unique data model in Ellis’ selection as objects and their rela-
tionships are modelled and persisted as nodes and edges of a graph. Queries fitting this model well
might be three orders faster than corresponding queries in the other stores discussed here (due to
Emil Eifrem, CEO of the company behind Neo4j, cf. [Eif09]).
• Scalaris is unique among the selected key/value stores as it allows distributed transactions over
multiple keys.
Persistence Design
The third aspect by which Ellis compares his selection of NoSQL datastores is the way they store data (see
table 2.7).
Datastore Persistence Design
Cassandra Memtable / SSTable
CouchDB Append-only B-tree
HBase Memtable / SSTable on HDFS
MongoDB B-tree
Neo4j On-disk linked lists
Redis In-memory with background snapshots
Riak ?
Scalaris In-memory only
Tokyo Cabinet Hash or B-tree
Voldemort Pluggable (primarily BDB MySQL)
Table 2.7.: Classifications – Comparison of Persistence Design (cf. [Ell09a])
Ellis considers persistence design as particularly important to estimate under which workloads these databases
will perform well:
In-Memory Databases are very fast (e.g. Redis can reach over 100.000 operations per second on a
single machine) but the data size is inherently limited by the size of RAM. Another downside is that
durability may become a problem as the amount of data which can get lost between subsequent disk
flushes (e.g. due to server crashes or by losing power supply) is potentially large. Scalaris addresses
this issue by replication but—as it does not support multiple datacenters—threats like power supply
failures remain.
Memtables and SSTables work in the following way: write operations are buffered in memory (in a
Memtable) after they have been written to an append-only commit log to ensure durability. After
a certain amount of writes the Memtable gets flushed to disk as a whole (and is called SSTable
then; these ideas are taken from Google’s Bigtable paper, cf. [CDG
+
06, Sections 5.3 and 5.4]). This
2. The NoSQL-Movement | 29
persistence strategy has performance characteristics comparable to those of in-memory-databases
(as—compared to disk-based strategies—disk seeks are reduced due to the append-only log and
the flushing of whole Memtables to disk) but avoids the durability difficulties of pure in-memory-
databases.
B-trees have been used in databases since their beginning to provide a robust indexing-support. Their
performance characteristics on rotating disks are not very positive due to the amount of disk seeks
needed for read and write operations. The document-database CouchDB uses B-trees internally but
tries to avoid the overhead of disk seeks by only appending to B-trees, which implies the downside
that only one write operation at a time can happen as concurrent reads to different sections of a
B-tree are not allowed in this case.
Categorization Based on Customer Needs
Todd Hoff (cf. [Hof09b]) cites blogger James Hamilton who presents a different approach to classify NoSQL
datastores (cf. [Ham09]) subsuming databases by customer requirements:
Features-First This class of databases provides a (large) number of high level features that make the
programmer’s job easier. On the downside, they are difficult to scale. Examples include: Oracle,
Microsoft SQL Server, IBM DB2, MySQL, PostgreSQL, Amazon RDS
12
.
Scale-First This sort of databases has to scale from the start. On the downside, they lack particular
features and put responsibility back to the programmer. Examples incude: Project Voldemort, Ringo,
Amazon SimpleDB, Kai, Dynomite, Yahoo PNUTS, ThruDB, Hypertable, CouchDB, Cassandra,
MemcacheDB.
Simple Structure Storage This class subsumes key/value-stores with an emphasis on storing and retriev-
ing sets of arbitrary structure. The downside according to Hamilton is that “they generally don’t
have the features or the scalability of other systems”. Examples include: file systems, Cassandra,
BerkelyDB, Amazon SimpleDB.
Purpose-Optimized Storage These are databases which are designed and built to be good at one thing,
e. g. data warehousing or stream processing. Examples of such databases are: StreamBase, Vertica,
VoltDB, Aster Data, Netezza, Greenplum.
Hamilton