hash(key) % server_count -- the first thing everyone reaches for to spread keys across a cluster -- turns into a catastrophe the moment the cluster changes size, relocating almost every key at once;Learn Zig Series):Last episode ended with a warning I want to make good on. We had just built an LRU cache -- a hash map married to a doubly linked list, evicting the coldest entry the moment it runs out of room -- and I pointed out the quiet assumption underneath every single line of it: there is one cache, in one process, on one machine. The instant your data outgrows a single box and you need a dozen cache servers, or a hundred, a fresh problem appears that no amount of clever list-splicing solves. How do you decide which server owns a given key, in a way that survives servers being added and removed? The naive answer looks fine right up until it detonates. So today we defuse it. But we owe a debt first: episode 123 left you three exercises, and I promised full code, not hand-waving ;-)
Exercise 1 -- a time-to-live (TTL) cache. The task was to give each node an expiry tick and add a getFresh(key, now) that treats an expired-but-not-yet-swept entry as a miss. The deliberate design call I asked you to make: should a plain get resurrect a stale entry? My answer is no -- staleness should be honest, so I drop the plain get entirely and offer only getFresh, which evicts the moment it notices the entry has expired. That keeps len() truthful: an expired key does not linger, inflating your size, until some future put happens to knock it out. Here is the whole thing, the episode-123 cache with an expires_at field threaded through:
const std = @import("std");
fn TtlCache(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Node = struct {
key: K,
value: V,
expires_at: u64,
prev: ?*Node = null,
next: ?*Node = null,
};
gpa: std.mem.Allocator,
capacity: usize,
map: std.AutoHashMap(K, *Node),
head: ?*Node = null,
tail: ?*Node = null,
fn init(gpa: std.mem.Allocator, capacity: usize) Self {
std.debug.assert(capacity >= 1);
return .{ .gpa = gpa, .capacity = capacity, .map = std.AutoHashMap(K, *Node).init(gpa) };
}
fn deinit(self: *Self) void {
var cur = self.head;
while (cur) |node| {
const next = node.next;
self.gpa.destroy(node);
cur = next;
}
self.map.deinit();
}
fn detach(self: *Self, node: *Node) void {
if (node.prev) |p| p.next = node.next else self.head = node.next;
if (node.next) |n| n.prev = node.prev else self.tail = node.prev;
node.prev = null;
node.next = null;
}
fn pushFront(self: *Self, node: *Node) void {
node.prev = null;
node.next = self.head;
if (self.head) |h| h.prev = node;
self.head = node;
if (self.tail == null) self.tail = node;
}
fn evictLru(self: *Self) void {
const victim = self.tail orelse return;
self.detach(victim);
_ = self.map.remove(victim.key);
self.gpa.destroy(victim);
}
// remove a specific node from BOTH list and map (used for expiry)
fn drop(self: *Self, node: *Node) void {
self.detach(node);
_ = self.map.remove(node.key);
self.gpa.destroy(node);
}
fn put(self: *Self, key: K, value: V, expires_at: u64) !void {
if (self.map.get(key)) |node| {
node.value = value;
node.expires_at = expires_at;
self.detach(node);
self.pushFront(node);
return;
}
const node = try self.gpa.create(Node);
errdefer self.gpa.destroy(node);
node.* = .{ .key = key, .value = value, .expires_at = expires_at };
try self.map.put(key, node);
self.pushFront(node);
if (self.map.count() > self.capacity) self.evictLru();
}
// A fresh read: an expired entry is a miss AND gets swept out on the spot.
fn getFresh(self: *Self, key: K, now: u64) ?V {
const node = self.map.get(key) orelse return null;
if (now >= node.expires_at) {
self.drop(node);
return null;
}
self.detach(node);
self.pushFront(node);
return node.value;
}
fn len(self: *const Self) usize {
return self.map.count();
}
};
}
test "getFresh reports a miss and sweeps the entry once its TTL passes" {
const gpa = std.testing.allocator;
var cache = TtlCache(u32, u32).init(gpa, 4);
defer cache.deinit();
try cache.put(1, 100, 50); // key 1 is valid until tick 50
try std.testing.expectEqual(@as(?u32, 100), cache.getFresh(1, 10)); // still fresh
try std.testing.expectEqual(@as(usize, 1), cache.len());
try std.testing.expectEqual(@as(?u32, null), cache.getFresh(1, 60)); // expired -> miss
try std.testing.expectEqual(@as(usize, 0), cache.len()); // and swept out immediately
}
The only structural addition over episode 123 is drop, which erases a specific node from list and map in the right order -- read the key before you free the node, the same discipline evictLru already lived by. Notice how now >= node.expires_at makes the boundary a policy decision you can see and change: an entry expiring exactly at now counts as gone. Time here is an abstract u64 tick, not wall-clock, which is exactly how you want it for testing -- you advance "now" by hand and nothing is flaky.
Exercise 2 -- swap in the memory pool. Episode 123 argued that the eviction policy and the node allocation strategy are independent axes. Here is the proof: take the cache and replace the per-node gpa.create/gpa.destroy with a std.heap.MemoryPool(Node), which we met in episode 114. It hands out fixed-size nodes with stable addresses and O(1) create/destroy, and -- this is the nice part -- deinit gets simpler, because the pool frees all its backing memory in one shot, so we no longer walk the list destroying nodes one by one:
const std = @import("std");
fn PooledLru(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Node = struct {
key: K,
value: V,
prev: ?*Node = null,
next: ?*Node = null,
};
gpa: std.mem.Allocator,
capacity: usize,
map: std.AutoHashMap(K, *Node),
pool: std.heap.MemoryPool(Node),
head: ?*Node = null,
tail: ?*Node = null,
fn init(gpa: std.mem.Allocator, capacity: usize) Self {
std.debug.assert(capacity >= 1);
return .{
.gpa = gpa,
.capacity = capacity,
.map = std.AutoHashMap(K, *Node).init(gpa),
.pool = .empty,
};
}
fn deinit(self: *Self) void {
self.map.deinit();
self.pool.deinit(self.gpa); // frees every node at once
}
fn detach(self: *Self, node: *Node) void {
if (node.prev) |p| p.next = node.next else self.head = node.next;
if (node.next) |n| n.prev = node.prev else self.tail = node.prev;
node.prev = null;
node.next = null;
}
fn pushFront(self: *Self, node: *Node) void {
node.prev = null;
node.next = self.head;
if (self.head) |h| h.prev = node;
self.head = node;
if (self.tail == null) self.tail = node;
}
fn get(self: *Self, key: K) ?V {
const node = self.map.get(key) orelse return null;
self.detach(node);
self.pushFront(node);
return node.value;
}
fn put(self: *Self, key: K, value: V) !void {
if (self.map.get(key)) |node| {
node.value = value;
self.detach(node);
self.pushFront(node);
return;
}
const node = try self.pool.create(self.gpa);
errdefer self.pool.destroy(node);
node.* = .{ .key = key, .value = value };
try self.map.put(key, node);
self.pushFront(node);
if (self.map.count() > self.capacity) self.evictLru();
}
fn evictLru(self: *Self) void {
const victim = self.tail orelse return;
self.detach(victim);
_ = self.map.remove(victim.key);
self.pool.destroy(victim);
}
fn len(self: *const Self) usize {
return self.map.count();
}
};
}
test "pooled LRU behaves identically to the heap-allocated one" {
const gpa = std.testing.allocator;
var cache = PooledLru(u32, u32).init(gpa, 2);
defer cache.deinit();
try cache.put(1, 10);
try cache.put(2, 20);
try std.testing.expectEqual(@as(?u32, 10), cache.get(1)); // 1 is now MRU, 2 is LRU
try cache.put(3, 30); // overflow -> evict key 2
try std.testing.expectEqual(@as(?u32, null), cache.get(2));
try std.testing.expectEqual(@as(?u32, 10), cache.get(1));
try std.testing.expectEqual(@as(?u32, 30), cache.get(3));
try std.testing.expectEqual(@as(usize, 2), cache.len());
}
Every list method is byte-for-byte what it was -- the point of the exercise. Only three lines changed: the field type, the two allocation calls, and the freed deinit. On std.testing.allocator this test is still leak-checked, so if the pool's teardown missed anything the run would fail. Same interface, different engine underneath, and the list surgery never knew the difference.
Exercise 3 -- a segmented "2Q"-lite LRU. The weakness of a pure LRU is that a one-off scan -- some batch job that reads a million keys once and never again -- floods the cache and evicts everything genuinely hot. The fix: a probationary segment for newcomers and a protected segment for keys that have proven themselves by being accessed a second time. New keys land in probation; the moment a probationary key is read again it is promoted to protected. Eviction always eats the probationary tail first, so a parade of never-repeated keys churns through probation and never disturbs your protected hot set:
const std = @import("std");
fn SegmentedLru(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Seg = enum { probation, protected };
const Node = struct {
key: K,
value: V,
seg: Seg,
prev: ?*Node = null,
next: ?*Node = null,
};
// a tiny intrusive doubly linked list with a length counter
const List = struct {
head: ?*Node = null, // MRU
tail: ?*Node = null, // LRU
len: usize = 0,
fn detach(self: *List, node: *Node) void {
if (node.prev) |p| p.next = node.next else self.head = node.next;
if (node.next) |n| n.prev = node.prev else self.tail = node.prev;
node.prev = null;
node.next = null;
self.len -= 1;
}
fn pushFront(self: *List, node: *Node) void {
node.prev = null;
node.next = self.head;
if (self.head) |h| h.prev = node;
self.head = node;
if (self.tail == null) self.tail = node;
self.len += 1;
}
};
gpa: std.mem.Allocator,
prob_cap: usize,
prot_cap: usize,
map: std.AutoHashMap(K, *Node),
probation: List = .{},
protected: List = .{},
fn init(gpa: std.mem.Allocator, prob_cap: usize, prot_cap: usize) Self {
std.debug.assert(prob_cap >= 1 and prot_cap >= 1);
return .{
.gpa = gpa,
.prob_cap = prob_cap,
.prot_cap = prot_cap,
.map = std.AutoHashMap(K, *Node).init(gpa),
};
}
fn deinit(self: *Self) void {
var it = self.map.valueIterator();
while (it.next()) |np| self.gpa.destroy(np.*);
self.map.deinit();
}
fn get(self: *Self, key: K) ?V {
const node = self.map.get(key) orelse return null;
switch (node.seg) {
.protected => {
self.protected.detach(node);
self.protected.pushFront(node);
},
.probation => {
// the crucial second-access promotion
self.probation.detach(node);
node.seg = .protected;
self.protected.pushFront(node);
self.enforceProtected();
},
}
return node.value;
}
// protected overflowed -> demote its LRU back down into probation
fn enforceProtected(self: *Self) void {
if (self.protected.len <= self.prot_cap) return;
const demoted = self.protected.tail.?;
self.protected.detach(demoted);
demoted.seg = .probation;
self.probation.pushFront(demoted);
self.enforceProbation();
}
// probation overflowed -> evict its LRU from the cache entirely
fn enforceProbation(self: *Self) void {
if (self.probation.len <= self.prob_cap) return;
const victim = self.probation.tail.?;
self.probation.detach(victim);
_ = self.map.remove(victim.key);
self.gpa.destroy(victim);
}
fn put(self: *Self, key: K, value: V) !void {
if (self.map.get(key)) |node| {
node.value = value;
_ = self.get(key); // reuse the access + promotion path
return;
}
const node = try self.gpa.create(Node);
errdefer self.gpa.destroy(node);
node.* = .{ .key = key, .value = value, .seg = .probation };
try self.map.put(key, node);
self.probation.pushFront(node);
self.enforceProbation();
}
fn contains(self: *Self, key: K) bool {
return self.map.contains(key);
}
};
}
test "a scan of one-off keys cannot evict a promoted hot key" {
const gpa = std.testing.allocator;
var cache = SegmentedLru(u32, u32).init(gpa, 4, 4);
defer cache.deinit();
// insert a hot key and access it once -> promoted into protected
try cache.put(777, 1);
_ = cache.get(777);
// flood with 100 never-repeated keys; they all churn through probation
var i: u32 = 0;
while (i < 100) : (i += 1) {
try cache.put(1000 + i, i);
}
// the hot key survived; a plain LRU of size 8 would long since have lost it
try std.testing.expect(cache.contains(777));
try std.testing.expectEqual(@as(?u32, 1), cache.get(777));
}
The two segments each get their own List with a len counter, and the whole policy lives in two little "enforce" helpers that cascade: a promotion can overflow protected, which demotes into probation, which can overflow probation, which evicts. Each helper moves at most one node, so the cascade is bounded and cheap. The test is the payoff -- 777 gets promoted, then a hundred garbage keys stampede through, and because they never earn a second access they never leave probation, so 777 sits untouched in protected. A plain size-8 LRU would have evicted it within the first eight interlopers. That is the entire reason real caches (Caffeine, many database buffer pools) use a segmented or frequency-aware policy in stead of a naive LRU. Debt paid ;-) Now, the fleet.
Back to the problem I left you with. You have a set of cache servers -- call them cache-0 through cache-7 -- and a flood of keys, and every key must land on exactly one server, the same server every time, so that a later get finds the value a previous put left there. The textbook first attempt, the one that appears in every whiteboard interview, is to hash the key to a number and take it modulo the server count:
server_index = hash(key) % server_count
It is O(1), it is stateless, it spreads keys beautifully evenly, and it is a trap. The evenness is real but it is not the property that matters. The property that matters is stability under change. Servers are not eternal -- they crash, you add capacity on Black Friday, you scale down at 3am. And the moment server_count changes, the modulus changes, and hash(key) % 8 has essentially nothing to do with hash(key) % 9. Watch it happen, with a real count over a hundred thousand keys:
const std = @import("std");
test "modulo hashing reshuffles almost everything when the cluster grows by one" {
const total_keys: u64 = 100_000;
const before: u64 = 8;
const after: u64 = 9;
var moved: u64 = 0;
var k: u64 = 0;
while (k < total_keys) : (k += 1) {
const h = std.hash.Wyhash.hash(0, std.mem.asBytes(&k));
if (h % before != h % after) moved += 1;
}
const fraction = @as(f64, @floatFromInt(moved)) / @as(f64, @floatFromInt(total_keys));
// ideal would be ~1/9 (only the new node's share). reality is catastrophic:
try std.testing.expect(fraction > 0.85); // in practice ~0.888
}
Going from eight servers to nine, the ideal churn is about one key in nine relocating -- just enough to fill the newcomer with its fair share. What actually happens is that roughly eight keys in nine change hands, because % 8 and % 9 agree only where the two remainders happen to coincide. In a distributed cache that means: add one server, and almost your entire cache misses at once. Every client stampedes the backing database simultaneously to refill entries that were perfectly good a second ago -- a self-inflicted thundering herd that has taken down real systems. We saw a smaller cousin of this "obvious but quadratic-in-pain" pattern with quick-find two episodes ago. The modulo is fast; it is just fast at doing the wrong thing when the world shifts.
The fix is one of those ideas that feels obvious the instant you see it, and it dates back to a 1997 paper out of MIT that was originally about spreading web cache load. In stead of hashing into a small changing range [0, server_count), hash into a huge fixed range -- the full width of a u64, say -- and then imagine that range bent around into a circle so that the largest value wraps back to zero. This is the hash ring.
Now place things on it. Each server is hashed to a point on the ring (hash its name: hash("cache-3")). Each key is hashed to a point on the ring the same way. To decide which server owns a key, you start at the key's point and walk clockwise -- toward larger hash values -- until you bump into the first server point. That server owns the key. If you run off the top of the ring without finding one, you wrap around to the very first server point at the bottom. That is the whole rule: a key belongs to the next server clockwise.
Here is why it fixes the churn. When you add a new server, it drops onto one spot on the ring, and it only steals the keys sitting in the arc between it and the previous server counter-clockwise from it. Every other key on the ring is completely undisturbed, because their "next server clockwise" did not change. Remove a server and the mirror image happens: only that server's keys spill over to the next one clockwise, and nobody else moves. Adding or removing a node reshuffles roughly 1/n of the keys in stead of nearly all of them. That is the property the modulo lacked, and it is why this is called consistent hashing.
The mental model is a circle, but the implementation is refreshingly flat: a sorted array of ring points, each carrying its hash position and which node it belongs to. "Walk clockwise to the next server point" becomes "binary search for the first array entry whose hash is >= the key's hash" -- exactly the lower-bound search from episode 117 -- and "wrap around the top" becomes "if the search ran off the end, take index 0". Let us build it:
const std = @import("std");
const HashRing = struct {
const Point = struct { hash: u64, node: []const u8 };
gpa: std.mem.Allocator,
ring: std.ArrayList(Point), // kept sorted by hash
vnodes: u32, // virtual points placed per physical node
fn init(gpa: std.mem.Allocator, vnodes: u32) HashRing {
std.debug.assert(vnodes >= 1);
return .{ .gpa = gpa, .ring = .empty, .vnodes = vnodes };
}
fn deinit(self: *HashRing) void {
self.ring.deinit(self.gpa);
}
fn lessThan(_: void, a: Point, b: Point) bool {
return a.hash < b.hash;
}
// hash a node's r-th virtual point: "name#r" -> u64
fn pointHash(name: []const u8, replica: u32) u64 {
var buf: [128]u8 = undefined;
const label = std.fmt.bufPrint(&buf, "{s}#{d}", .{ name, replica }) catch unreachable;
return std.hash.Wyhash.hash(0, label);
}
fn addNode(self: *HashRing, name: []const u8) !void {
var r: u32 = 0;
while (r < self.vnodes) : (r += 1) {
try self.ring.append(self.gpa, .{ .hash = pointHash(name, r), .node = name });
}
std.mem.sort(Point, self.ring.items, {}, lessThan);
}
fn removeNode(self: *HashRing, name: []const u8) void {
var w: usize = 0;
for (self.ring.items) |p| {
if (!std.mem.eql(u8, p.node, name)) {
self.ring.items[w] = p;
w += 1;
}
}
self.ring.shrinkRetainingCapacity(w); // array stays sorted, just shorter
}
// first ring index whose hash >= target, wrapping past the top to index 0
fn locate(self: *const HashRing, target: u64) usize {
var lo: usize = 0;
var hi: usize = self.ring.items.len;
while (lo < hi) {
const mid = lo + (hi - lo) / 2;
if (self.ring.items[mid].hash < target) lo = mid + 1 else hi = mid;
}
if (lo == self.ring.items.len) lo = 0; // ran off the end -> wrap around
return lo;
}
fn nodeFor(self: *const HashRing, key: []const u8) []const u8 {
std.debug.assert(self.ring.items.len > 0);
const h = std.hash.Wyhash.hash(0, key);
return self.ring.items[self.locate(h)].node;
}
};
A few decisions worth defending. I store the node name directly in each Point rather than an integer id, so removeNode is a trivial one-pass compaction that filters out every point belonging to a name -- no index invalidation to reason about, no fixups. The locate function is a hand-written lower-bound binary search rather than a call into std.sort; I wrote it out because the wrap-around at the top is the ring, and burying it inside a stdlib call would hide the one line (if (lo == len) lo = 0) that makes a line into a circle. And pointHash formats "name#r" before hashing so that the same physical server produces vnodes different, scattered ring positions -- which brings us to the reason vnodes exists at all.
If you place exactly one point per server (vnodes = 1), the ring works but the load is unfair. Three or four random points on a circle almost never carve it into equal arcs -- one server gets a fat slice and drowns while another gets a sliver and idles. With only a handful of servers the imbalance can easily be two- or three-to-one, which is unacceptable when each "server" is a real machine with real memory you are paying for.
The fix is delightfully cheap: give each physical server many points on the ring -- virtual nodes, or replicas -- by hashing "cache-3#0", "cache-3#1", ... "cache-3#199" and dropping all of them onto the ring, every one pointing back to the same physical cache-3. Now each server is represented by a couple hundred little arcs scattered all around the circle, and the law of large numbers takes over: the sum of many small random arcs is far more even than one big random arc. A hundred to two hundred virtual nodes per server gets the load imbalance down to a few percent. Our HashRing already supports this -- it is the vnodes field -- so let us actually measure that the keys land evenly across five servers at 200 virtual nodes each:
test "virtual nodes even out the load across physical nodes" {
const gpa = std.testing.allocator;
var ring = HashRing.init(gpa, 200);
defer ring.deinit();
for ([_][]const u8{ "cache-0", "cache-1", "cache-2", "cache-3", "cache-4" }) |name| {
try ring.addNode(name);
}
var tally = std.StringHashMap(usize).init(gpa);
defer tally.deinit();
const total_keys = 50_000;
for (0..total_keys) |i| {
var kb: [24]u8 = undefined;
const key = std.fmt.bufPrint(&kb, "user:{d}", .{i}) catch unreachable;
const node = ring.nodeFor(key);
const gop = try tally.getOrPut(node);
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += 1;
}
var min: usize = std.math.maxInt(usize);
var max: usize = 0;
var it = tally.valueIterator();
while (it.next()) |v| {
min = @min(min, v.*);
max = @max(max, v.*);
}
// with 200 vnodes each, the busiest node carries well under 1.5x the lightest
try std.testing.expect(max * 2 < min * 3);
}
Fifty thousand keys across five servers is ten thousand each in a perfect world; the assertion demands the heaviest server carry less than 1.5x the lightest, and in practice the spread is far tighter than that. Crank vnodes down to 1 and re-run and you will watch the assertion fail as the ring goes lumpy -- a five-second experiment that makes the whole point of virtual nodes tangible. The cost is honest and bounded: vnodes times server_count points in the array, so 200 replicas across 50 servers is 10,000 entries, a binary search of depth 14. Nothing.
Even load is nice, but it is not the headline. The headline is minimal churn: adding or removing a server must move only that server's share of the keys and leave everyone else exactly where they were. This is the one thing modulo hashing spectacularly failed, so it is the one thing we test directly -- snapshot where twenty thousand keys land, add a server, and count how many keys changed hands:
test "consistent hashing moves only a small share of keys when a node joins" {
const gpa = std.testing.allocator;
var ring = HashRing.init(gpa, 200);
defer ring.deinit();
for ([_][]const u8{ "cache-0", "cache-1", "cache-2", "cache-3" }) |name| {
try ring.addNode(name);
}
const total_keys = 20_000;
const assigned = try gpa.alloc([]const u8, total_keys);
defer gpa.free(assigned);
for (0..total_keys) |i| {
var kb: [24]u8 = undefined;
const key = std.fmt.bufPrint(&kb, "key-{d}", .{i}) catch unreachable;
assigned[i] = ring.nodeFor(key);
}
try ring.addNode("cache-4"); // grow the cluster 4 -> 5
var moved: usize = 0;
for (0..total_keys) |i| {
var kb: [24]u8 = undefined;
const key = std.fmt.bufPrint(&kb, "key-{d}", .{i}) catch unreachable;
if (!std.mem.eql(u8, assigned[i], ring.nodeFor(key))) moved += 1;
}
const frac = @as(f64, @floatFromInt(moved)) / @as(f64, @floatFromInt(total_keys));
// ideal is 1/5 = 0.20 (only the newcomer's share). modulo would have moved ~0.9:
try std.testing.expect(frac < 0.30);
}
Going from four servers to five, the newcomer's fair share is one key in five, and the test confirms the actual churn sits under thirty percent -- a world away from the eighty-nine percent the modulo inflicted for the identical change. Every key that moved, moved onto the new server; not a single key was flung between two old servers. We can prove even that stronger claim on the removal side -- take a node out and assert that the only keys that moved are the ones it used to hold:
test "removing a node reassigns only the keys it was holding" {
const gpa = std.testing.allocator;
var ring = HashRing.init(gpa, 200);
defer ring.deinit();
for ([_][]const u8{ "cache-0", "cache-1", "cache-2", "cache-3", "cache-4" }) |name| {
try ring.addNode(name);
}
const total_keys = 20_000;
const assigned = try gpa.alloc([]const u8, total_keys);
defer gpa.free(assigned);
for (0..total_keys) |i| {
var kb: [24]u8 = undefined;
const key = std.fmt.bufPrint(&kb, "obj-{d}", .{i}) catch unreachable;
assigned[i] = ring.nodeFor(key);
}
ring.removeNode("cache-2");
var moved_from_survivors: usize = 0;
var moved_total: usize = 0;
for (0..total_keys) |i| {
var kb: [24]u8 = undefined;
const key = std.fmt.bufPrint(&kb, "obj-{d}", .{i}) catch unreachable;
if (!std.mem.eql(u8, assigned[i], ring.nodeFor(key))) {
moved_total += 1;
if (!std.mem.eql(u8, assigned[i], "cache-2")) moved_from_survivors += 1;
}
}
try std.testing.expectEqual(@as(usize, 0), moved_from_survivors); // survivors untouched
try std.testing.expect(moved_total > 0); // cache-2's keys did have to go somewhere
}
moved_from_survivors comes out to exactly zero. Not "small", not "close to zero" -- zero. Every key that once lived on cache-0, cache-1, cache-3 or cache-4 still resolves to the very same server after cache-2 vanished. Only cache-2's orphaned keys found new homes, each on whatever server sat next clockwise. That crisp, provable guarantee is the entire reason this structure underpins so much real infrastructure.
In C, consistent hashing is old and everywhere -- the canonical appearance is libketama, the memcached client ring from 2007 that fixed exactly the thundering-herd problem above for a large media site. The shape is what we built: a sorted array of { uint64 hash, server* } points, qsort to order it, and bsearch (or a hand-rolled lower bound) to find the successor. Virtual nodes are baked in by hashing "server:port-N" for many N. No allocator ceremony, no bounds checks -- and no one reminding you to keep the array sorted after a mutation, which is the bug our addNode prevents by always re-sorting.
In Rust, the sorted-array-of-points design maps cleanly onto a BTreeMap<u64, ServerId>, whose range(key_hash..).next() gives you the successor point directly and whose ordered iteration handles the wrap-around with a fallback to .iter().next(). The borrow checker is entirely at ease here -- there is no aliased mutable graph like the linked-list nightmare from last episode, just a value-keyed tree -- so this is one of the rare distributed-systems primitives that is genuinely pleasant in safe Rust. Crates like hashring ship precisely this.
In Go, you would reach for a []uint64 of sorted hashes plus a map[uint64]string from ring point to server, and sort.Search for the binary lower bound -- the standard library hands you every piece. The garbage collector means adding and removing nodes is just reslicing and map edits with nothing to free. Groupcache and countless service meshes run this pattern in production. Four languages, one structure, and the same load-bearing truth in each: hash servers and keys into one big fixed space, keep the server points sorted, and let every key walk clockwise to its owner. Bam, jonguh ;-)
Weighted nodes. Real clusters are heterogeneous -- a beefy 128GB box should own more keys than a tiny 16GB one. Extend addNode to take a weight and place vnodes * weight virtual points for that server in stead of a flat vnodes. Write a test that gives one server double the weight of the others and asserts it receives roughly (not exactly) twice the key share.
Bounded lookup, no scan. Add a nodesFor(key, count) that returns the first count distinct servers clockwise from a key -- the primitive every replicated store needs to pick where the N copies of a value live. Mind the wrap-around and skip virtual points that repeat a physical server you already collected. Test that on a 4-server ring, nodesFor(key, 3) always returns three different server names.
Measure the imbalance honestly. Write a helper that, given a ring and a key count, returns the ratio of the busiest server's load to the mean. Run it for vnodes of 1, 10, 50, 200 and 500, and print the ratio for each. Convince yourself of the diminishing return: going 1 -> 50 is night and day, 200 -> 500 barely moves the needle, and that plateau is why production systems park vnodes in the low hundreds.
We have now spent a long run of episodes filling a toolbox: hash maps, tries, B-trees, bloom and cuckoo filters, ring buffers, the sorting and searching and graph work, an LRU cache, and today a way to spread data across a whole fleet of machines without the cluster melting every time it resizes. That is a genuinely deep shelf of data structures -- and a toolbox is only worth anything when you build something real with it.
So next we stop collecting structures and start assembling one. Picture a heap of documents -- thousands of text files -- and the question every search box on earth has to answer in milliseconds: which of these documents contain the word you just typed? Scanning every file on every query is hopeless the moment the pile grows. The answer is a data structure that flips the whole problem inside-out, mapping words back to the documents that hold them, and it leans on precisely the hash maps and sorted lists we have been sharpening this whole time. We are going to build it from scratch, piece by piece, and by the end you will have written the beating heart of a search engine ;-)
Thanks for reading -- go add and remove a node or two, and watch how few keys actually flinch. De groeten! ;-)
@scipio