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.

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);

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.