Partitioning and Consistent Hashing: How Keys Move When Nodes Change

Learning outcome

You can explain why hash(key) % N reshuffles almost everything when N changes, how a consistent-hash ring with virtual nodes limits movement to about 1/N of the keys, and where this shows up in .NET systems: cache clusters, sharded rate-limit counters, SignalR and job partitions.

Intuition

Several cases in this course need to spread keys over nodes: short codes over database shards, rate-limit counters over Redis nodes, tenants over databases. If adding one node moves 80% of the keys, every cache misses at once and every counter resets. Consistent hashing places nodes and keys on the same ring, so a new node takes over only the arc next to it.

flowchart LR
    K["key: user:42"] --> H["hash (64-bit)"] --> R["ring: first node position >= hash"]
    R --> N1["cache-a#17"]
    R -. "after adding cache-e,<br/>only keys on its arcs move" .-> N2["cache-e#3"]

Deep dive

• Modulo placement is fine for a fixed number of partitions (for example 64 logical partitions mapped to fewer physical nodes). It is bad when N itself changes.
• Ring: hash each node name to positions on a 64-bit ring; a key belongs to the first node position at or after the key's hash, wrapping around. Use a stable hash such as MD5, xxHash or Murmur, never string.GetHashCode(), which is randomized per process in .NET.
• Virtual nodes: with one position per node, arcs are uneven. Giving each physical node many positions evens out the load and lets you weight bigger nodes with more positions.
• Where you meet it:
  • Redis Cluster uses 16,384 hash slots (a fixed-partition scheme, not a ring), and clients such as StackExchange.Redis route by slot.
  • Azure Cosmos DB and Event Hubs/Kafka partition by a partition key; the number of partitions is the unit of parallelism.
  • Your own code: choosing a shard for a tenant or a short code, or routing a user to a SignalR group owner.
• Hot keys are not fixed by any hash: one celebrity user or one tenant still lands on one node. Fixes are key splitting (append a suffix and aggregate), a local in-process cache in front, or a dedicated node.
• Rebalancing moves data. The ring tells you which keys move; you still have to copy them (or accept cache misses) and handle reads during the move.

Code example: modulo vs ring with 100,000 keys

// Consistent hashing vs modulo hashing: load balance and how many keys move when a node is added.
using System.Security.Cryptography;
using System.Text;

static ulong H(string s) => BitConverter.ToUInt64(MD5.HashData(Encoding.UTF8.GetBytes(s)), 0);
var keys = Enumerable.Range(0, 100_000).Select(i => $"user:{i}").ToArray();
string[] four = { "cache-a", "cache-b", "cache-c", "cache-d" };
string[] five = four.Append("cache-e").ToArray();

// 1. Modulo: node = hash % N
string Mod(string k, string[] nodes) => nodes[H(k) % (ulong)nodes.Length];
int movedMod = keys.Count(k => Mod(k, four) != Mod(k, five));
Console.WriteLine($"modulo 4 -> 5 nodes: {movedMod:N0} of {keys.Length:N0} keys moved ({100.0 * movedMod / keys.Length:F1}%), ideal is {100.0 / 5:F1}%");

// 2. Consistent hashing ring with v virtual nodes per server
foreach (var v in new[] { 1, 10, 100, 1000 })
{
    var r4 = Ring(four, v); var r5 = Ring(five, v);
    var load = keys.GroupBy(k => Lookup(r4, k)).ToDictionary(g => g.Key, g => g.Count());
    double mean = keys.Length / 4.0;
    double sd = Math.Sqrt(load.Values.Select(c => (c - mean) * (c - mean)).Average());
    int moved = keys.Count(k => Lookup(r4, k) != Lookup(r5, k));
    int movedToNew = keys.Count(k => Lookup(r4, k) != Lookup(r5, k) && Lookup(r5, k) == "cache-e");
    Console.WriteLine($"ring vnodes={v,4}: load per node min={load.Values.Min():N0} max={load.Values.Max():N0} (stddev {100 * sd / mean:F1}% of mean); add node: {100.0 * moved / keys.Length:F1}% moved, all to the new node: {moved == movedToNew}");
}

static SortedList<ulong, string> Ring(string[] nodes, int vnodes)
{
    var ring = new SortedList<ulong, string>();
    foreach (var n in nodes) for (int i = 0; i < vnodes; i++) ring[H($"{n}#{i}")] = n;
    return ring;
}
static string Lookup(SortedList<ulong, string> ring, string key)
{
    ulong h = H(key); var ks = ring.Keys;
    int lo = 0, hi = ks.Count - 1;                      // first ring position >= h (binary search), wrap to 0
    if (h > ks[hi]) return ring.Values[0];
    while (lo < hi) { int mid = (lo + hi) / 2; if (ks[mid] < h) lo = mid + 1; else hi = mid; }
    return ring.Values[lo];
}

Output (.NET 10)

modulo 4 -> 5 nodes: 80,031 of 100,000 keys moved (80.0%), ideal is 20.0%
ring vnodes=   1: load per node min=16,253 max=34,184 (stddev 30.7% of mean); add node: 5.2% moved, all to the new node: True
ring vnodes=  10: load per node min=15,937 max=30,795 (stddev 22.6% of mean); add node: 23.6% moved, all to the new node: True
ring vnodes= 100: load per node min=21,019 max=27,760 (stddev 10.0% of mean); add node: 17.6% moved, all to the new node: True
ring vnodes=1000: load per node min=24,068 max=25,533 (stddev 2.3% of mean); add node: 19.6% moved, all to the new node: True

Code walkthrough

• Going from 4 to 5 nodes with modulo moved 80,031 of 100,000 keys (80.0%). The ideal is 20.0%: only the share the new node should own.
• With one ring position per node, load ranged from 16,253 to 34,184 keys per node (stddev 30.7% of the mean), and the new node took only 5.2% because its single arc happened to be short.
• At 100 virtual nodes the spread narrowed to 21,019-27,760 and 17.6% moved; at 1,000 it was 24,068-25,533 (stddev 2.3%) and 19.6% moved, close to the ideal 20%.
• In every ring run, all moved keys went to the new node (True). No key moved between old nodes, which is the property that keeps the other caches warm.
• The exact percentages depend on the hash and node names; the trend (more virtual nodes, smoother load and movement close to 1/N) is what you quote.

Failure modes

• Using GetHashCode() for placement: each process computes a different value, so two API instances route the same key to different shards.
• Too few virtual nodes, then one node gets twice the load of another.
• Ignoring hot keys: perfect hashing still sends one key to one node.
• Changing the hash function or node names during a deploy, which moves everything at once.
• Forgetting that a ring does not copy data; a new cache node starts empty and the database sees the misses.

Interview angle

"How do you add a cache node without a thundering herd?" Answer: "Consistent hashing with virtual nodes, so about 1/N of keys move and only to the new node. Then warm it, or let it fill gradually behind request coalescing so the misses do not all hit the database at once. For a fixed key space I would rather use fixed logical partitions mapped to nodes, like Redis Cluster's 16,384 slots."

Practice questions

1. Why is string.GetHashCode() unsafe for shard selection in .NET?

Answer: Since .NET Core, string hashing is randomized per process, so different instances (and restarts) get different values.

2. You go from 10 to 11 nodes with a ring. Roughly what fraction of keys moves?

Answer: About 1/11 (about 9%), all of it to the new node, given enough virtual nodes.

3. What do virtual nodes fix and what do they not fix?

Answer: They fix uneven arc sizes (load balance and weighting). They do not fix a single hot key.

4. When is plain modulo acceptable?

Answer: When the number of partitions is fixed for the life of the data, for example 64 logical partitions that you later map to physical nodes.

Revision checklist

• Adding one node to reach N nodes: modulo moves about (N-1)/N of keys; a balanced ring moves about 1/N to the new node.
• Virtual nodes even out load; stable hash only.
• Hot keys need splitting or local caching.
• Fixed slots (Redis Cluster 16,384) are an alternative to a ring.

Related on TechInterviewNotes

• Lesson: Sharding
• Lesson: Replication
• Lesson: Load balancers, caching, SQL vs NoSQL and indexing
• Lesson: Data stores and consistency

References

• Redis Cluster specification: hash slots
• Azure Cosmos DB: partitioning and horizontal scaling
• String.GetHashCode remarks