Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 47 ยท SQL and NoSQL on Hadoop

Choosing a NoSQL Store

Compare key-value, document, wide-column and graph databases, and learn consistent hashing and the Dynamo and Cassandra ideas behind scalable stores.

"NoSQL" is not one technology. It is a family of databases that gave up some feature of classic relational systems (fixed schemas, joins, multi-row transactions) to gain something else: easy scaling over many machines, flexible data shapes, or speed for one kind of access. Choosing well means knowing which family fits your access pattern.

This lesson walks through the four main families, then explains the idea that lets most of them spread data over many servers: consistent hashing, together with the replication and consistency tricks from Amazon's Dynamo paper and Cassandra. It follows HBase: Wide-Column Storage.

No NoSQL server runs on the site. The code in plain blocks is read-only. The runnable examples are stand-ins that model the algorithms in Python.

The four families

Four families of NoSQL

Key-value Get and put by key. Fastest and simplest.
Document JSON-like records you can query by field.
Wide-column Sorted rows with families of columns.
Graph Nodes and edges, built for relationships.

Pick by the questions you will ask, not by fashion.

1 / 2

Key-value stores

The model is a giant dictionary: get(key), put(key, value), delete(key). The value is opaque bytes to the database. Because there is only one access path, the store can be extremely fast and easy to partition. Use it for sessions, caches, shopping carts, feature flags. You cannot ask "all carts with more than three items" without scanning everything.

Document stores

A record is a self-describing document, usually JSON, with nested fields and lists. You can index and query fields inside it. This fits data whose shape varies, such as product catalogs, and it avoids joins by embedding related data (an order contains its lines). The cost is duplication: if the same customer name is embedded in a million orders, renaming means a million updates.

Wide-column stores

As in HBase and Cassandra, rows are found by a key and hold sparse columns grouped in families. Data is stored sorted, which makes range reads inside a key cheap and writes very fast thanks to LSM trees. They shine for time series and event logs at huge volume, and are weak at ad-hoc queries.

Graph databases

Here the relationships are the data. Finding "friends of friends who live in Oslo" is a quick walk over edges, where a relational database would need repeated self-joins. Choose a graph database when queries are about paths, neighbors and patterns. They are less suited to simply spreading a huge dataset over many machines.

Here is a quick comparison of how the same user record might look in each of the first three:

TEXT
key-value   user:1001                -> "{\"name\":\"Mina\",\"city\":\"Lyon\"}"   (opaque to the store)
document    users/1001               -> { name: "Mina", city: "Lyon", tags: ["admin"] }
wide-column row 'u1001'  info:name   -> "Mina"   info:city -> "Lyon"   stats:logins -> 42

Scaling out: partitioning

To hold more data than one machine can, a store splits it into partitions (shards) and places them on different nodes. The simplest rule is node = hash(key) % N. It has a nasty flaw: when you add or remove a node, N changes and almost every key moves. Moving most of your data just because you added one server is far too expensive.

Consistent hashing

Consistent hashing fixes this. Imagine the output of the hash function as a ring of numbers that wraps around. Each node is placed on the ring at the hash of its name. A key is hashed onto the same ring and belongs to the first node found going clockwise. When a node joins or leaves, only the keys between it and its neighbor move; all other keys stay where they are. On average only about 1/N of the keys move.

A plain ring can be uneven, since a few random points may leave one node with a large arc. The standard remedy is virtual nodes (vnodes): each physical server is placed on the ring many times (say 100 to 256 points), so the arcs average out and a failed node's load is spread over many survivors.

flowchart LR
    K["key 'user:42'<br/>hash -> ring position"] --> N["walk clockwise<br/>to next node point"]
    N --> O["owner node A"]
    O --> R["replicas: next 2<br/>distinct nodes"]

The key's position on the ring decides its owner and its replicas.

The first stand-in builds a ring and measures how many keys move when a node is added, compared with the naive modulo rule.

Python Consistent hashing versus hash modulo N

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run it: the ring moves roughly a fifth of the keys, which is the share the new node must take over, while the modulo rule reshuffles most of them. Exact numbers depend on the hash, but the gap is always large.

The Dynamo and Cassandra ideas

Amazon's Dynamo design, which Cassandra and others adopted, combines consistent hashing with a few more ideas:

  • Replication on the ring. Each key is stored on its owner and the next N-1 distinct nodes clockwise (a replication factor, often 3). Any node can act as the coordinator for a request.
  • Tunable consistency. A write goes to N replicas and succeeds when W acknowledge. A read asks R replicas. If R + W > N, every read overlaps at least one replica that has the latest write. With N=3, W=2, R=2 you get that overlap; with W=1, R=1 you get speed but may read stale data. This is the practical side of the CAP trade-off in Distributed Systems in Plain Words.
  • Eventual consistency repair. Replicas that missed a write are fixed by read repair (the coordinator notices differing replies and updates the stale one), hinted handoff (a neighbor holds writes for a node that is down) and background anti-entropy with Merkle trees.
  • Gossip. Nodes exchange membership and health information with a few random peers each second, so there is no central master. HBase has a master and strong per-row consistency; Cassandra is masterless and favors availability.

In CQL (Cassandra's SQL-like language) you choose consistency per query. Read-only syntax:

TEXT
CREATE KEYSPACE shop WITH replication = {'class': 'NetworkTopologyStrategy', 'dc1': 3};
CONSISTENCY QUORUM;
SELECT * FROM shop.orders WHERE customer_id = 1001;

The stand-in below checks the quorum rule by brute force.

Python Quorum reads and writes: when is a read fresh?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whenever R + W > N, the freshness is 100%. Otherwise some reads miss the newest value.

A decision guide

Ask these questions in order:

  1. Is the data relational with joins and transactions? Stay with a relational database (or Hive for analytics).
  2. Is access purely by key? A key-value store.
  3. Do records vary in shape and you query inside them? A document store.
  4. Huge write volume, time series, key-range reads? A wide-column store.
  5. Are the questions about relationships and paths? A graph database.

Many systems use several stores at once (polyglot persistence): for example a relational database for orders, a key-value cache in front, and a wide-column store for events.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is hash(key) % N a poor way to assign keys to nodes in a growing cluster?

    When N changes, most keys get a new remainder, so most data would have to move. Consistent hashing moves only about 1/N of the keys.
  2. 2. What do virtual nodes do on a consistent-hashing ring?

    With many points per server, arcs average out and a failed server's load spreads over many others.
  3. 3. With N=3 replicas, which setting guarantees that a read sees the latest acknowledged write?

    R + W must be greater than N. With W=2 and R=2 the read set and the write set always share at least one replica.
  4. 4. Which family is the best fit for 'friends of friends who live in Oslo'?

    Graph databases store relationships as first-class edges, so walking several hops is cheap.

Summary

  • NoSQL families trade relational features for scale or flexibility: key-value, document, wide-column and graph each match different access patterns.
  • Consistent hashing places nodes and keys on a ring so adding or removing a node moves only about 1/N of the keys; virtual nodes even out the load.
  • Dynamo-style stores replicate each key to N nodes, tune consistency with R + W > N, repair with read repair and hinted handoff, and use gossip instead of a master.
  • Choose by access pattern, and mix stores when needed.

Next: Getting Data In: Sqoop, Flume, NiFi and Kafka.