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

Databases were a chief component of the earliest computers. The earliest databases around the time when mainframe computers were prominent in the 1960s and 1970s had records with fixed individual fields. For example, a particular database might have had five fixed fields, such that a record might have data slots to hold a record's first name, last name, phone number, city, and employment status code. Accordingly, record number 10013 might have had the fields "Bill", "Robinson", 5551212, Vienna, and hired. To query the database, a search would be done on all the records sequentially to see if they met a specified condition. But what if one wanted to explore connections between records in one database with a separate database? That is, suppose there was information about Bill Robinson on a different database; was it possible to query both databases simultaneously? In 1970, Dr. E. F. Codd published a paper entitled A Relational Model of Data for Large Shared Data Banks. His IBM colleagues Donald Chamberlin and Raymond Boyce worked on a way to specify queries as relational expressions. As a result, a new way of analyzing databases known as Structured Query Language or SQL emerged which allowed users to search information across linked databases, and this proved to be a much more powerful and useful way of managing data. It didn't require database managers to rebuild new databases as new information came along; rather, they could link databases dynamically.

SQL became the dominant language for what was called "relational database systems." By the late 1990s, however, problems were beginning to emerge, particularly when databases became vast with records numbering in the hundreds of millions of pieces of data, and programmers were searching for better ways to get at data efficiently. One alternative to relational databases has been called the "NoSQL" data stores, and it was conceived as an alternative to SQL.

Datasets were growing exponentially. Sometimes users needed to know only pieces of the data, or to query some parts of databases but not others. How could questions be posed to these data sets efficiently? Programmers who had been used to the idea of "one size fits all" found that traditional solutions were becoming cumbersome.

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.

Only as the internet gave way to the masses and large scale concurrency and data generation ushered in a new era has the relational way of doing data management truly begun to break down, opening the door to alternatives.Michael Stonebraker, November 2009

NoSQL-type approaches could manage data that was distributed across multiple sites, sometimes including offline data stored on large disk drives. This was a so-called more scalable approach.

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 a current surge in non-relational databases. NoSQL databases tried to improve efficiency by removing the overhead and memory footprint of relational databases, thus speeding up searches. Other NoSQL approaches were more closely linked with programming languages and tied to web technologies, thus giving users new ways of querying data.

But it is not clear whether the NoSQL technologies will replace traditional SQL relational databases or whether these are new tools to take SQL in new directions. Analyst Roberto V. Zicari in the ODBMS Industry Watch journal sees the important focus for the database industry in finding "the right tool for the job", and believes this "mantra" for the software industry is an "important change in attitude."

Proponents of NoSQL approaches complain about relational databases being slow, expensive, heavily "taxing" of computer resources. Springsource engineer Jon Travis quipped "relational databases give you too much. They force you to twist your object data to fit a relational database management system." Travis sees NoSQL champions particularly among web and Java developers who have had to grow powerful data search capability without existing data storage solutions. They learned from firms such as Amazon and Google how to efficiently process large swaths of information –– including up to terabytes or even petabytes of information. Firms like Cloudant write software which tries to work when data is generated in a distributed way, possibly by sensor networks, web servers, mobile storage service; the idea is to help small companies manage "big data", according to Alexia Tsotsis of Tech Crunch.

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.

• Document stores have a database consisiting of a collection of (key, value) pairs along with a "payload".

• Key-value stores have records which consist of a pair including a key and a payload which are analyzed using distributed hash tables (or DHTs). Examples include Memcachedb and Dynamo.

With these arrangements, the result of using these databases yields one record at a time rather than a typical SQL query. The NoSQL approach means that relational databases can be scalable both vertically and horizontally on several servers. A traditional SQL approach means that data is held on one server. If a second server is used, then the problem of how to synchronize data from both servers must be dealt with. In a NoSQL approach, however, it's easier for them to work across a so-called cloud of servers, although they're somewhat limited to simpler requests for data. While a traditional relational database can be conceived as data organized in tables with rows (representing records) and columns (representing fields), NoSQL databases can be organized into objects, key–value pairs or tuples. A key benefit of NoSQL is marrying object-oriented programming to more traditional relational databases. Computerworld analyst David Intersimone believes, however, that relational databases will continue to be dominant in the foreseeable future, but concedes that NoSQL technologies may play a greater role.

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.

Analyst Joab Jackson of IDG News suggested that NoSQL querying can be done but sometimes users would have to think differently about how to do the query. Accordingly, there is a learning curve to using the new approach. NoSQL approaches using CouchDB allows users to build a web application without a so-called "middle tier"; it eliminates the Java stack.

Disadvantages of NoSQL include lack of consistency as well as insufficient support for relational data. "Queries require re-architecting and recoding of existing products," according to one source.

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.