Database Reference
In-Depth Information
Fig. 3.4
Partitioning and
replication of keys in
dynamo ring
Key K
A
G
B
Nodes B, C
and D store
keys in
range (A,B)
including
K.
F
C
E
D
Dynamo system relies on simple read and write operations to a data item that is
uniquely identified by a key. State is stored as binary objects (blobs) identified by
unique keys. No operations span multiple data items.
Dynamo's partitioning scheme relies on a variant of consistent hashing mecha-
nism [
158
] to distribute the load across multiple storage hosts. In this mechanism,
the output range of a hash function is treated as a fixed circular space or “ring”
(i.e. the largest hash value wraps around to the smallest hash value). Each node
in the system is assigned a random value within this space which represents its
“position” on the ring. Each data item identified by a key is assigned to a node by
hashing the data item's key to yield its position on the ring, and then walking the
ring clockwise to find the first node with a position larger than the item's position.
Thus, each node becomes responsible for the region in the ring between it and its
predecessor node on the ring. The principle advantage of consistent hashing is that
departure or arrival of a node only affects its immediate neighbors and other nodes
remain unaffected.
In the Dynamo system, each data item is replicated at N hosts where N is a
parameter configured “per-instance”. Each key k is assigned to a coordinator node.
The coordinator is in charge of the replication of the data items that fall within
its range. In addition to locally storing each key within its range, the coordinator
replicates these keys at the .N
1/ clockwise successor nodes in the ring. This
results in a system where each node is responsible for the region of the ring between
it and its N th predecessor. As illustrated in Fig.
3.4
, node B replicates the key k at
nodes C and D in addition to storing it locally. Node D will store the keys that fall
in the ranges .A; B, .B; C , and .C; D. The list of nodes that is responsible for
storing a particular key is called the preference list. The system is designed so that
every node in the system can determine which nodes should be in this list for any
particular key.
3.3
NoSQL Open Source Projects
In practice, most NoSQL data management systems which are introduced by the
key players (e.g. BigTable, Dynamo, PNUTS) are meant for their internal use only
and are thus, not available for public users. Therefore, many open source projects
