NoSQL

All unapproved Citizendium articles may contain errors of fact, bias, grammar etc. A version of an article is unapproved unless it is marked as citable with a dedicated green template at the top of the page, as in this version of the 'Biology' article. Citable articles are intended to be of reasonably high quality. The participants in the Citizendium project make no representations about the reliability of Citizendium articles or, generally, their suitability for any purpose. This article is currently being developed as part of an Eduzendium student project. The course homepage can be found at CZ:Special_Topics_2010. To provide students with experience in collaboration, you are warmly invited to join in here, or to leave comments on the discussion page. The anticipated date of course completion is 13 August 2010. One month after that date at the latest, this notice shall be removed. Besides, many other Citizendium articles welcome your collaboration!

NoSQL refers to a number of non-relational distributed database architectures. NoSQL architectures usually store data as key-value pairs, rather than supporting relations. Some systems eliminate the guarantee of consistency (instead promising eventual consistency) in order to increase scalability. The distributed nature of NoSQL architectures makes such data stores highly scalable and fault-tolerant.

History

The word "NoSQL" (Not Only SQL) was first used by Carlo Strozzi in 1998 referring to a file-based database he was developing, which is actually a relational database without a SQL interface. Some meaningful events during the evolvement of NoSQL include: MultiValue (aka PICK) databases developed in 1965; BerkeleyDB is created in 1996; Mnesia is developed by Ericsson as a soft real-time database to be used in telecom ( it does not use SQL as query language); CouchDB is started in 2005 and provides a document database which moves to the Apache Foundation in 2008; Google BigTable is started in 2004; Tokyo Cabinet is a successor to QDBM by (Mikio Hirabayashi) started in 2006; the research paper on Amazon Dynamo is released in 2007; the document database MongoDB is started in 2007 as a part of an open source cloud computing stack; Facebooks open sources the Cassandra project in 2008; Redis is persistent key-value store started in 2009; Riak is another dynamo-inspired database started in 2009; HBase is a BigTable clone for the Hadoop project while Hypertable is another BigTable type database also from 2009. In 2009, Eric Evans re-used it to describe current surge in non-relational databases.

NoSQL vs. RDBMS

In many cases, NoSQL databases can process data more quickly than traditional relational database management systems. One reason for this is that data representation in NoSQL databases is much simpler than in relational systems. For example, a table in a relational database might have many columns, but data in a key-value store will always have only two parts: the key and the value. In addition, many NoSQL databases do not fully support ACID transactions. While this allows faster performance, it can also be risky in applications where precision is needed, such as in banking applications.

Disadvantages of NoSQL

NoSQL databases are fast for simple tasks, however, they may be time-consuming and difficult for more complex tasks because without SQL, they require manual query programming. NoSQL databases are not as reliable as relational databases since they don't natively support ACID properties. If users want to apply ACID restraints to a data set, they need additional programming. Consistency is another issue incurred by not supporting ACID. If users are not familiar with the technology, they might not be able to determine that the approach is better for their purposes. In addition, many open source NoSQL applications don't have customer support or management tools yet.

Relationship to cloud computing

The rise in popularity of NoSQL Databases has been associated closely with the growth of cloud computing. Relational databases are not well suited to scaling across a large cluster of servers due to difficulty ensuring consistency and referential integrity as well as query performance in a distributed relational environment. NoSQL databases on the other hand are designed with a distributed environment in mind making them a perfect fit for the large clusters of commodity hardware that make up the cloud.

Furthermore, the concessions made by cloud computing (immediate consistency in exchange for increased availability and partition tolerance) are also a good fit for many of the rich, non-OLTP applications that are sprouting up as part of the Web 2.0 movement and often hosted by cloud providers. The schemaless nature of NoSQL databases makes them an excellent tool for rapid prototyping and Agile development, both techniques commonly associated with cloud development, and since most leading implementations are FOSS, licensing for a large number of severs is not any issue.

The efficiency of NoSQL in the cloud has given rise to a new class of offerings known as Database as a Service (DaaS) from a number of providers. Most notably, both Amazon (SimpleDB) and Google (in Google App Engine) have variations on a DaaS offering.

Types of NoSQL Databases

Key-value Store

A key-value store maintains data as a pair consisting of an indexed key and a value. In general, key-value stores provide a single operation: fetching a single value using its key. Some key-value store implementations include mechanisms for performing a join on two distinct tables. Examples of key-value stores include Oracle's BerkeleyDB and Amazon's Dynamo.

BerkeleyDB

© Image
Distributed hash tables are used by many distribute key-value stores in order to spread data between many servers.

BerkeleyDB is an open source, transactional, embedded database engine. It is available as a library that can be included in any application. Data are represented as key/value pairs. The keys and values in BerkeleyDB can be any objects supported by the programming language. Data are stored in files on disk, as a single file for each key-value store. BerkeleyDB also provides the option to maintain data stores in memory only, if the store is small enough to fit in main memory.

BerkeleyDB provides a number of features competitive with relational databases, including support for transactions, two-phase locking, joins, and write ahead logging. These features make BerkeleyDB very reliable. The BerkeleyDB engine is used in a number of applications. The MySQL database management system offers BerkeleyDB as an option for the storage engine.

BerkeleyDB in itself does not provide a method for distributing data, but using a distributed hash table, it is possible to distribute data across multiple BerkeleyDB instances.

Project Voldemort

Project Voldemort is a distributed key-value store that uses BerkeleyDB as its storage engine. It is developed and used by LinkedIn, and is written in Java. Like many distributed key-value stores, Project Voldemort uses a distributed hash table to distribute data between multiple servers, and to provide replication functionality.

Interacting with a Project Voldemort DB is relatively simple:

String bootstrapUrl = "tcp://localhost:6666";
StoreClientFactory factory = new SocketStoreClientFactory(new ClientConfig().setBootstrapUrls(bootstrapUrl));

// create a client that executes operations on a single store
StoreClient client = factory.getStoreClient("my_store_name");

// do some random pointless operations
Versioned value = client.get("some_key");
value.setObject("some_value");
client.put("some_key", value);

Document-based Databases

While key-value stores are an excellent solution for storing data in a distributed environment with near-linear access, many problem spaces necessitate data access patterns other than simple key based indexing. Moreover, many applications require elements of the robust feature set typically associated with a RDBMS but without the tradeoffs necessitated by normalized relational data.

Document-based databases build on the basic concepts and architecture associated with key-value Stores but layer an advanced feature set on top of the core KV storage. Common document-based database features include (but are not limited to):

• Collections
• Ad-Hoc Queries
• Secondary Indexes
• Views and Aggregation

In a document-based database values in the underlying key-value storage are referred to as documents. In place of keys generated by the client application, document-based databases use system generated document ids (an analog to the Primary Key in an RDBMS table). As a result all application data in a document-based database is stored in the documents.

In order to support querying and other advanced operations, documents are stored as semi-structured data.

Semi-Structured Data

Historically data in computer systems was divided into two categories: structured (databases) and unstructured (free-form text). Structured data assigns semantic meaning to information based on the structure in which it is stored (e.g. the row layout of a relational database table). For instance, a database of users can easily support a query such as "all users with last name Robin" by investigating the first name column of the users table. A search against a text file could only identify occurrences of the word Robin with no way to determine if it's a first name, a last name, or neither.

Semi-structured data is a data storage strategy that assigns semantic meaning to information without the need for predefined structure. It does this by defining the semantics of the data along with the data itself. The most common format for semi-structured data is XML with JSON (javascript object notation) rapidly growing in popularity.

Collections

Despite the schemaless nature of NoSQL databases it is often convenient to segregate different entity types in a document-based store for ease of querying. This is achieved using collections (also referred to as buckets or domains). Documents within the same collection should represent the same type of entity and as such all have a similar (though not identical) structure.

Collections can be considered rough equivalent of relational tables, but while hierarchical entities must span several relational tables they are generally stored in a single collection (within a single document).

Ad-Hoc Queries

Because documents are stored as semi-structured data, document-based databases can support basic queries against attribute values (such as the earlier example without requiring a predefined data schema). The query language varies depending on the data format used by a particular database (e.g. XPath for XML, Javascript for JSON). At least one implementation (RavenDB) supports the use of LINQ queries popular on the Microsoft .NET platform.

Ad-hoc queries are used only in the case of simple search predicates (usually =, ≠, >, <). More advanced queries are achieved using views, generally based on variations of the MapReduce algorithm.

Secondary Indexes

In order to facilitate efficient queries on large data sets, many document-based databases support the ability to generate indexes on arbitrary data fields. Indexes are usually defined using a variation of the supported query language, for instance by replacing the search predicate with a boolean true in a Javascript query.

Like documents themselves indexes are generally distributed across all nodes in a cluster (although the specific strategy varies by implementation). Once generated, indexes are updated when data is inserted (or when nodes receive the latest data due to eventual consistency).

Views and Aggregation

Due to their distributed nature, document-based database are an excellent match for distributed aggregation algorithms such as MapReduce. In general any operation that would be performed against a relational database using a SQL GROUP BY clause and aggregate functions can be achieved using MapReduce against a document-based database. In fact the Apache Hive project contains functionality to translate ad-hoc queries written in a SQL-like syntax directly into MapReduce functions.

The language used to define the MapReduce functions varies by implementation, but Javascript is most common. The Map portion of the function is used to select an initial set of data from a specified collection while Reduce is used to consolidate the data and calculate any desired aggregate values.

Views are achieved by running MapReduce with a nominal pass-through Reduce function. Map functions can be used to perform substantial transformations on the document data before returning it to the result set. This power can be used in any number of ways, for instance picking only certain fields from a heterogenous collection to return a homogenous result. A single call to the Map function is permitted to produce several emits. Apache CouchDB has omitted an ad-hoc query function focusing instead on the substantially more powerful MapReduce engine.

Implementation Specific Features

• In-Place Document Editing
• Persistent Views
• Multi-Version Concurrency Control (MVCC)
• Advanced Conflict Resolution
• Configurable Consistency/Redundancy Options
• Simple References

Popular Document-Based Databases

• Software
  • Apache Couch DB (Erlang)
  • Mongo DB (C++)
  • Fleet DB (Clojure)
  • Riak (C and Erlang)
  • Raven (.NET, Supports LINQ)
• Database as a Service (DaaS)
  • Amazon SimpleDB (Erlang)
  • Cloudant - Hosted Couch DB
  • Mongo HQ - Hosted Mongo DB

Column-oriented Databases

The column oriented database stores entries by column as opposed to row-oriented databases. This optimizes the SQL databases by making data aggregation easier and maximizing disk performance. Examples of open-source and commercial column oriented databases include: Cassandra(Facebook), Big Table(Google), Hypertable(Open-source implementation of Big Table), Hbase(Open-source implementation of Big Table), etc.

Big Table

Bigtable is a distributed storage system for managing structured data, which is designed to scale to petabytes of data reliably. It has been developed by Google since 2005 and used for more than 60 Google products.

Bigtable is a multi-dimensional sorted map, which can be indexed by a row key, column key, and a timestamp. For example, if we want to store a large collection of web pages, we would use URLs as row keys, various aspects of web pages as column names and the contents of the web pages can be stored in column under the timestamps when they were fetched.Every read or write of data under a single row key is atomic. The columns can be dynamically added. The timestamps represent different versions of data which are assigned by client application. The older versions are garbage-collected. The rows are sorted lexicographically. Consecutive keys are grouped together as "tablets". Column keys are grouped into sets called "column families". Column key is named using syntax: family: qualifier. Access control and disk/memory accounting are at column family level. The data design includes creating and deleting tables and column families, changing cluster, table and column family metadata like access control rights. The client interactions include writing and deleting values, read values, scan row ranges, single-row transactions, map, reduce integration. Bigtable provides clients with a simple data model that supports dynamic control over data layout and format. Bigtable's implementation allows great performance and high availability, enables users to scale the capacity of their clusters by simply adding more machines to the system. Bigtable demonstrates significant advantages in building storage solution at Google.

 // Open the table
 Table *T = OpenOrDie("/bigtable/web/webtable");

 // Write a new anchor and delete an old anchor
 RowMutation r1(T, "com.cnn.www");
 r1.Set("anchor:www.c-span.org", "CNN");
 r1.Delete("anchor:www.abc.com");
 Operation op;
 Apply(&op, &r1);

 // Read from a table
 Scanner scanner(T);
 ScanStream *stream;
 stream = scanner.FetchColumnFamily("anchor");
 stream->SetReturnAllVersions();
 scanner.Lookup("com.cnn.www");
 for (; !stream->Done(); stream->Next()) {
   printf("%s %s %lld %s\n",
          scanner.RowName(),
          stream->ColumnName(),
          stream->MicroTimestamp(),
          stream->Value());
 }

Future perspective

During the next few years, NoSQL is expected to develop better application compatibility and management tools. NoSQL databases will mainly work with unstructured data that demands scalability. Since relational databases are more mature, NoSQL will not replace SQL in the future. Instead, NoSQL will primarily work on specialized projects which are distributed, involved with large amounts of data, or must scale.