Hash Partitioning

Each record's key is run through a hash function, and the result picks its node. Hashing scatters similar keys, so records and requests spread evenly, and any part of the system can compute where a key lives without asking anyone. The catch is what happens when the number of nodes changes. Below, compare plain hash mod N with fixed hash slots, and add or remove nodes to see how much data moves.

node = hash(key) mod NN = 4 nodes. A key keeps its node only while N stays the same.with N = 3N3N2N2N1N2N2with N = 4 (now)N2N1N4N1N2N1with N = 5N2N2N5N3N2N1the same six users, placed for three values of NAppNode 1Node 2Node 3Node 4

Each dot in a node is one user record, coloured by country. Add or remove a node and the records that change node glide to their new place, ringed so you can count them; the count appears under the app. A node turns red when it serves well above its share of requests.

What a resize costs
KB
GB

  1. 1. Total data

    users x data per user = 500M x 10 KB = 4.66 TB

  2. 2. Nodes, filled to 70%

    total / (one node x 70%), rounded up = 14 nodes

  3. 3. Adding one node with hash mod N

    a key stays put only if hash mod 14 equals hash mod 15, about 1 time in 15, so about N / (N + 1) of the data moves: 4.35 TB

  4. 4. Adding one node with fixed slots

    the new node takes 1 / (N + 1) of the slots, and only their data moves: 318 GB
  5. Moving data costs network, disk and time while the system is live. That is why systems that grow use fixed slots, consistent hashing or rendezvous hashing rather than plain mod N.
Where these formulas come from

Step 1 is the storage estimate from the back-of-the-envelope chapter of Alex Xu's System Design Interview, Vol. 1. Step 3 follows from how modulo behaves: for a well-mixed hash, the remainders by N and by N + 1 agree for about 1 key in N + 1. Step 4 assumes each node holds the same number of slots, which the rebalancing keeps true to within one slot.

Limits of hash partitioning

Range queries scatter

Hashing destroys order: users 1000 to 1100 end up on every node, so "give me this range" must ask them all. If range queries matter, range partitioning keeps neighbours together.

Resizing with mod N

Changing N moves most keys at once. Fixed slots fix that by adding one level of indirection: the hash picks a slot, and only the slot table changes.

One hot key

A hash spreads different keys, but every request for the same key goes to the same node. A celebrity, a viral post or a popular product needs caching or deliberate splitting.

Keys that belong together

Related keys, such as a user and their followers list, hash to different nodes, which makes multi-key operations cross nodes. Redis lets you hash only part of a key to keep them together.

How Redis and DynamoDB hash keys

Redis exposes its slots; DynamoDB hides its partitions but warns about hot keys.

Redis Cluster: 16,384 hash slots

In Redis Cluster, "The cluster's key space is split into 16384 slots", and a key's slot is CRC16(key) mod 16384. "Adding or removing a node is abstracted into the same operation: moving a hash slot from one node to another." Hash tags keep related keys together: {user1000}.following and {user1000}.followers land in the same slot, because only user1000 is hashed.

DynamoDB: a hash of the partition key

"DynamoDB uses the value of the partition key as input to an internal hash function", and "The output value from the hash function determines the partition in which the item will be stored." Its design guide warns that a key design that does not spread requests "can create "hot" partitions that result in throttling", giving as a bad example a device id where one device "is by far more popular than all the others."
Sources and credibility

All are official documentation: the Redis Cluster specification and Amazon's DynamoDB developer guide. Quoted phrases are short attributed quotations; everything else is described in our words.