Classification of NoSQL Databases

NoSQL databases can be broadly classified as:

1. Distributed vs. Not-distributed databases

Distributed databases take the responsibility of data partitioning (for scalability) and replication (for availability) and do not leave that to the client. Non-distributed databases leaves the responsibility of data partitioning and replication on the clients.

Table 1: Distributed and Non-distributed databases

Distributed	Not Distributed
Amazon Dynamo Amazon S3 Scalaris Voldemort CouchDb (thru Lounge) Riak MongoDb BigTable Cassandra HyperTable HBase	Redis Tokyo Tyrant MemcacheDb Amazon SimpleDb

2. Disk vs. Memory databases

An useful dimension is whether the database is memory-driven or disk-driven. This is important since in the latter case an explicit cache would be required, while in the former case data is not durable.

Table 2: Memory driven and disk driven databases

Memory	Configurable	Disk
Scalaris Redis	BigTable Cassandra Hbase HyperTable	CouchDb MongoDb Riak Voldemort

On one end of the spectrum is Scalaris which is entirely memory-driven, and Redis which is primarily memory oriented. Cassandra, BigTable, Hypertable, Hbase allow configuring how large the Memtable can get, so that provides a lot of control. CouchDb, MongoDb and Riak all use on-disk B+ trees, and Voldemort uses BDB and MySQL.

3. Data Model richness

On the basis of data model the various NoSQL databases can be grouped in following three groups.

3.1 Key-value Stores

These systems store values and an index to find them, based on a programmer-defined key. These data stores use a data model similar to the popular memcached distributed in-memory cache, with a single key-value index for all the data. Like memcached, none of these systems offer secondary indices or keys.

3.2 Document Stores

These systems store documents. The documents are indexed and a simple query mechanism may be provided. Document stores support more complex data than the key-value stores. The term “document store” is not ideal, because these systems store objects (generally objects without pointers, described in JSON notation), not necessarily documents. Unlike the key-value stores, they generally support multiple indexes and multiple types of documents (objects) per database, and they support complex values.

3.3 Column Stores

These systems store extensible records that can be partitioned across nodes. They are also refered as “Extensible Record Stores”. Their basic data model is rows and columns, and their basic scalability model is splitting both rows and columns over multiple nodes. Rows are split across nodes through conventional sharding, on the primary key. They typically split by range rather than a hash function (this means that queries on ranges of values do not have to go to every node). Columns of a table are distributed over multiple nodes by using “column groups”.

These may seem like a new complexity, but column groups are simply a way for the customer to indicate which columns are best grouped together. These two partitionings (horizontal and vertical) can be used simultaneously on the same table. The column groups must be pre-defined with the extensible record stores. However, that is not a big constraint, as new attributes can be defined at any time. Rows are not that dissimilar from documents: they can have a variable number of attributes (fields), the attribute names must be unique, rows are grouped into collections (tables), and an individual row’s attributes can be of any type.

Table 3: Classification of NoSQL databases based on data model

Key-Value store	Document store	Column-Store
Amazon Dynamo Amazon S3 Redis Scalaris Voldemort	SimpleDb Couchdb MongoDb Riak	Cassandra Google BigTable HBase Hyperbase

An Intro to NoSQL

What is NoSQL

For a quarter of a century, the relational database (RDBMS) has been the dominant model for database management. In the past, relation databases were used for nearly everything. Because of their rich set of features, query capabilities and transaction management they seemed to be fit for almost every possible task one could imagine to do with a database. But their feature richness is also their flaw, because it makes building distributed RDBMSs very complex. In particular it is difficult and not very efficient to make transactions and join operations in a distributed system.

This is why, there are now some non relational databases with limited feature sets and no full ACID support, which are more suitable for the usage in a distributed environment. These databases are currently called NoSQL databases. The need to look at Non SQL systems arises out of scalability issues with relational databases, which are a function of the fact that relational databases were not designed to be distributed (which is key to write scalability), and could thus afford to provide abstractions like ACID transactions and a rich high-level query model. All NoSQL databases try and address the scalability issue in many ways – by being distributed, by providing a simpler data / query model, by relaxing consistency requirements, etc.

The name first suggests that these databases do not support the SQL query language and are not relational. But it also means "Not Only SQL", which is not so aggressive against relational databases. This stands for a new paradigm: One database technology alone is not fit for everything. Instead it is necessary to have different kinds of databases for different demands. Most NoSQL databases are developed to run on clusters consisting of commodity computers and therefore have to be distributed and failure tolerant. To achieve this, they have to make different trade-offs regarding the ACID properties, transaction management, query capabilities and performance. They are usually designed to fit the requirements of most web services and most of them are schema free and bring their own query languages.

Why NoSQL

Even though RDBMS have provided database users with the best mix of simplicity, robustness, flexibility, performance, scalability, and compatibility, their performance in each of these areas is not necessarily better than that of an alternate solution pursuing one of these benefits in isolation. Today, the situation is slightly different. For an increasing number of applications, one of these benefits is becoming more and more critical; and while still considered a niche, it is rapidly becoming mainstream, so much so that for an increasing number of database users this requirement is beginning to eclipse others in importance. That benefit is scalability.

Relational databases scale well, but usually only when that scaling happens on a single server node. When the capacity of that single node is reached, you need to scale out and distribute that load across multiple server nodes. This is when the complexity of relational databases starts to rub against their potential to scale. Try scaling to hundreds or thousands of nodes, rather than a few, and the complexities become overwhelming, and the characteristics that make RDBMS so appealing drastically reduce their viability as platforms for large distributed systems.

Cloud computing also has placed new challenges on the database. The economic vision for cloud computing is to provide computing resources on demand with a "pay-as-you-go" model. A pool of computing resources can exploit economies of scale and a levelling of variable demand by adding or subtracting computing resources as workload demand changes. The traditional RDBMS has been unable to provide these types of elastic services. For cloud services to be viable, vendors have had to address this limitation, because a cloud platform without a scalable data store is not much of a platform at all. So, to provide customers with a scalable place to store application data, vendors had only one real option. They had to implement a new type of database system that focuses on scalability, at the expense of the other benefits that
come with relational databases.

Database Consistency

A database system is said to be in a consistent state if it satisfies all known integrity constraints. Integrity is defined as `the accuracy or correctness of data in the database`. There are two famous types of integrity constraints:

1. Entity integrity constraints (for example, no primary key value can be null)
2. Referential integrity constraints (a field in one table which refers to another table must refer to a field that exists in that table).

A database is in a correct state if it is both consistent and if it accurately reflects the true state of affairs in the real world. A database that is in a correct state will always be consistent. But consistent does not necessarily mean correct. A consistent database can be incorrect.

Different types of consistency exists:

Strong consistency means, that all processes connected to the database will always see the same version of a value and a committed value is instantly reflected by any read operation on the database until it is changed by another write operation.

Eventual Consistency is weaker and does not guarantee that each process sees the same version of the data item. Even the process which writes the value could get an old version during the inconsistency window. This behavior is usually caused by the replication of the data over different nodes.

Read-your-own-writes consistency, some distributed databases can ensure that a process can always read its own writes. For this, the database has to connect the same process always to nodes that already store the data written by this process.

A subtype of read-your-writes consistency is session consistency. Thereby it is only guaranteed that a process can read its own written data during a session. If the process starts a new session, it might see an older value during the inconsistency window.

Another variant of eventual consistency is monotonic read consistency, which assures that when a newly written value is read the first time, all subsequent reads on this data item will not return any older values. This type of consistency allows the database to replicate newly written data, before it allows the clients to see the new version.

Most of the NoSQL databases can only provide eventual consistency.