Database Reference
In-Depth Information
When a value associated with a key needs to be retrieved, first we calculate the hash of
the key, which again corresponds to a place on the circle. In order to place or retrieve a
key, one simply moves around the circle in a clockwise direction unless the next node is
found. If no node is found in the given hash space, the first node is considered the place to
store in, or retrieve from, as shown in the following diagram:
This way, each node becomes responsible for taking care of keys between itself and its
previous node. This implementation of consistent hashing leads to a few issues: first, it
may lead to uneven distribution of load as, if a key is not able to find a position, it will al-
ways go to the first node; second, it will also increase the difference in the performance of
various nodes impacting the overall system. To address the issue of uneven load, Dy-
namoDB uses a variant of consistent hashing, where it assigns a node to multiple points
on the hash ring circle instead of on a single point as we saw in the basic algorithm earlier.
DynamoDB puts multiple virtual nodes on the ring, which would represent a single phys-
ical machine. Doing so helps in making distribution of data even across the cluster.
