Knowledge Guide
Home › Hands-On Builds › SD Design Labs

Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss

Sharded Service — Route, Measure, Rebalance

Every system-design answer eventually says the same sentence: "we shard by hash(tenant_id) % N." It is said so often it stops sounding like a decision and starts sounding like a fact of nature. It isn't. It's a specific, fragile choice with two failure modes that show up the moment the system is real instead of imagined: a hot key — one tenant, one celebrity account, one viral row — sends 10× the traffic of its neighbors and pins one shard while the other N−1 idle; and a shard count change — you add capacity, or you lose a node — under naive % N reshuffles almost every key in the cluster at once, turning a routine scaling event into a cache-flushing, connection-storming incident. This lab builds a single in-memory router, points real traffic at it, and measures both failures and both fixes: key salting for the hot key, and a consistent-hashing ring with virtual nodes for the rebalance storm. Every claim below is a printed number from a program that ran, in Java and in Go, not a comment asserting what "should" happen.

1. The Trap — "hash and mod" is a sentence, not a system

The one-line version of sharding is shard = hash(key) % N. It is correct, it is simple, and it is the thing every naive implementation reaches for first — because for a uniformly random key space with a fixed N, it actually works: Movement 1 below measures a max/min imbalance ratio of 1.000 across 100,000 keys on 8 shards. The trap is believing that "works for uniform keys at fixed N" generalizes to production, where neither assumption holds:

Scope for this lab. One in-memory router process, no real network, no real database — the point is the routing math and its measured consequences, not the transport. Four things get built and measured: (1) baseline mod-N distribution, (2) a hot key and its fix via key salting, (3) consistent hashing with virtual nodes vs. naive mod-N on a shard add, (4) a shard removal (loss) and the resulting remap. Out of scope: actual data migration between shards (this lab measures which keys move, not the bytes-on-the-wire cost of moving them), and replication/quorum within a shard (that's the companion quorum lab).

2. Scope it like a senior — the questions that reshape the design

3. Reason to the design — from a mod operation to a ring

Simplest thing that could work: shard = hash(key) % N. Zero state beyond N itself, O(1) lookup, and — as Movement 1 shows — a genuinely flat distribution when keys are uniform and N is stable. Ship this until either assumption breaks.

First break — a hot key. One key concentrates a large share of traffic; every request for it lands on the same shard regardless of hashing quality. The fix is not a better hash function (the key is one value; any deterministic hash sends it to exactly one bucket) — it's making the key not one value. Key salting: the caller (or a thin wrapper) rewrites hot-key into one of hot-key#0 .. hot-key#15, chosen round-robin or randomly per request. Each salted variant hashes independently and lands on a (probably) different shard. Reads now have to fan out to all 16 sub-keys and merge — a real cost, paid only for the keys that need it — but writes and the routing load are spread. Movement 2 measures the before/after: imbalance ratio drops from 6.4× to 1.5× with a 16-way split.

Second break — N changes. Salting doesn't help here; the problem now is that % N has no relationship to % (N+1). The fix is to stop hashing into a flat array and instead hash onto a ring: every shard occupies one or more points on a fixed, large hash space (say, 0 to 2³²−1), and a key's owner is whichever shard's point comes next, clockwise, from the key's own hash. Adding a shard means adding its point(s) to the ring — it only steals the arc between its new point and the previous point's owner, leaving every other arc, and every other key's owner, untouched. Movement 3 measures the difference directly on the same 100,000 keys: naive mod-N moves 88.9% on an 8→9 shard add; the ring moves 8.6% — roughly what you'd expect for the new shard claiming its fair ~1/9th share of the space, and an order of magnitude better than naive.

Third refinement — virtual nodes. One point per physical shard means that shard's owned arc-length is whatever the gap happens to be to its single neighbor — pure luck, and with only a handful of shards the variance is large (one shard might own 40% of the ring, another 5%). Give each physical shard many points (this lab uses 500 vnodes per shard) scattered across the ring, and by the law of large numbers each shard's total owned arc-length converges toward its fair 1/N share, without changing the fundamental property: removing or adding a shard still only touches the arcs adjacent to that shard's own vnodes.

The backstop — shard loss is just a ring removal, not a special case. A crashed or decommissioned shard is handled by the exact same mechanism as an add, run in reverse: delete its vnodes from the ring, and every key that used to resolve to one of those points now resolves to whichever vnode is next clockwise — automatically, with no coordinator decision required about where each orphaned key goes. Movement 4 measures it: removing 1 of 8 shards moves 13.4% of keys (close to the lost shard's fair 1/8 = 12.5% share) to the surviving shards, and — the number that actually matters operationally — 0 keys become unroutable. The ring degrades gracefully; nothing needs a global rebalance decision to keep serving traffic.

4. Build it — Java

One deterministic 32-bit hash (FNV-1a, so the numbers are reproducible run-to-run and identical in shape across languages), a plain mod-N router, and a consistent-hashing Ring backed by a TreeMap so "next point clockwise" is a single ceilingEntry lookup with wraparound. Java 8, no var, no records — plain classes, exactly like the rest of this guide's labs.

import java.util.*;

public class ShardDemo {

    // ---------- Deterministic hash (FNV-1a, 32-bit) ----------
    static long fnv1a(String s) {
        long hash = 2166136261L;
        for (int i = 0; i < s.length(); i++) {
            hash ^= (s.charAt(i) & 0xff);
            hash = (hash * 16777619L) & 0xffffffffL;
        }
        return hash;
    }

    static int modShard(String key, int n) {
        return (int) (fnv1a(key) % n);
    }

    // ---------- Consistent hash ring with virtual nodes ----------
    static class Ring {
        final TreeMap<Long, String> points = new TreeMap<Long, String>();
        final int vnodes;
        Ring(int vnodes) { this.vnodes = vnodes; }

        void addShard(String shard) {
            for (int i = 0; i < vnodes; i++) {
                points.put(fnv1a(shard + "#" + i), shard);
            }
        }
        void removeShard(String shard) {
            Iterator<Map.Entry<Long, String>> it = points.entrySet().iterator();
            while (it.hasNext()) {
                if (it.next().getValue().equals(shard)) it.remove();
            }
        }
        String owner(String key) {
            if (points.isEmpty()) return null;
            long h = fnv1a(key);
            Map.Entry<Long, String> e = points.ceilingEntry(h);
            if (e == null) e = points.firstEntry(); // wrap around the ring
            return e.getValue();
        }
        Ring copy() {
            Ring r = new Ring(vnodes);
            r.points.putAll(points);
            return r;
        }
    }

    static double maxMinRatio(Map<String, Integer> counts) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int v : counts.values()) { max = Math.max(max, v); min = Math.min(min, v); }
        if (min == 0) return Double.POSITIVE_INFINITY;
        return (double) max / min;
    }

    public static void main(String[] args) {
        int N = 8;          // shards
        int M = 100_000;     // distinct keys
        int V = 500;         // virtual nodes per shard

        List<String> keys = new ArrayList<String>(M);
        for (int i = 0; i < M; i++) keys.add("key-" + i);

        System.out.println("== Movement 1: route M keys by hash(key) % N, measure the distribution ==");
        Map<String, Integer> baseline = new TreeMap<String, Integer>();
        for (int i = 0; i < N; i++) baseline.put("shard-" + i, 0);
        for (String k : keys) {
            String s = "shard-" + modShard(k, N);
            baseline.merge(s, 1, Integer::sum);
        }
        System.out.println("  shards=" + N + " keys=" + M);
        System.out.println("  counts = " + baseline);
        System.out.printf("  max/min imbalance ratio = %.3f  (close to 1.0 = balanced)%n", maxMinRatio(baseline));

        System.out.println();
        System.out.println("== Movement 2: inject a HOT KEY, measure the imbalance, then fix with salting ==");
        int totalRequests = 200_000;
        int hotFraction = 40; // hot key gets 40% of all traffic
        int hotCount = totalRequests * hotFraction / 100;
        Random rnd = new Random(42);

        Map<String, Integer> hot = new TreeMap<String, Integer>();
        for (int i = 0; i < N; i++) hot.put("shard-" + i, 0);
        for (int r = 0; r < totalRequests; r++) {
            String key = (r < hotCount) ? "hot-key" : "key-" + rnd.nextInt(M);
            String s = "shard-" + modShard(key, N);
            hot.merge(s, 1, Integer::sum);
        }
        System.out.println("  requests=" + totalRequests + ", hot key share=" + hotFraction + "%");
        System.out.println("  counts (BEFORE fix) = " + hot);
        System.out.printf("  max/min imbalance ratio (BEFORE) = %.3f  <- one shard is overloaded%n", maxMinRatio(hot));

        int splitFactor = 16; // salt the hot key into 16 sub-keys
        Map<String, Integer> salted = new TreeMap<String, Integer>();
        for (int i = 0; i < N; i++) salted.put("shard-" + i, 0);
        rnd = new Random(42);
        for (int r = 0; r < totalRequests; r++) {
            String key;
            if (r < hotCount) {
                key = "hot-key#" + (r % splitFactor); // spread the hot key across sub-keys
            } else {
                key = "key-" + rnd.nextInt(M);
            }
            String s = "shard-" + modShard(key, N);
            salted.merge(s, 1, Integer::sum);
        }
        System.out.println("  counts (AFTER salting, split=" + splitFactor + ") = " + salted);
        System.out.printf("  max/min imbalance ratio (AFTER)  = %.3f  <- rebalanced%n", maxMinRatio(salted));

        System.out.println();
        System.out.println("== Movement 3: consistent hashing (vnodes) vs naive mod-N on shard ADD ==");
        int naiveChanged = 0;
        for (String k : keys) {
            if (modShard(k, N) != modShard(k, N + 1)) naiveChanged++;
        }
        double naiveFrac = (double) naiveChanged / M;
        System.out.printf("  naive mod-N remap:     %d / %d keys moved (%.1f%%)  <- almost everything reshuffles%n",
                naiveChanged, M, naiveFrac * 100);

        Ring ringN = new Ring(V);
        for (int i = 0; i < N; i++) ringN.addShard("shard-" + i);
        Ring ringN1 = ringN.copy();
        ringN1.addShard("shard-" + N); // add one more shard

        int chChanged = 0;
        for (String k : keys) {
            if (!ringN.owner(k).equals(ringN1.owner(k))) chChanged++;
        }
        double chFrac = (double) chChanged / M;
        System.out.printf("  consistent hashing:    %d / %d keys moved (%.1f%%)  <- only the new shard's fair share%n",
                chChanged, M, chFrac * 100);
        System.out.printf("  theoretical target ~= 1/(N+1) = %.1f%%  -- naive is ~%.0fx worse%n",
                100.0 / (N + 1), naiveFrac / chFrac);

        System.out.println();
        System.out.println("== Movement 4: SHARD LOSS -- remove a shard, measure remap + no unroutable keys ==");
        Map<String, String> before = new HashMap<String, String>();
        for (String k : keys) before.put(k, ringN.owner(k));

        Ring afterLoss = ringN.copy();
        afterLoss.removeShard("shard-0");

        int moved = 0, unroutable = 0;
        Map<String, Integer> redistribution = new TreeMap<String, Integer>();
        for (String k : keys) {
            String owner = afterLoss.owner(k);
            if (owner == null) unroutable++;
            else redistribution.merge(owner, 1, Integer::sum);
            if (owner == null || !owner.equals(before.get(k))) moved++;
        }
        System.out.println("  removed shard-0; keys formerly on shard-0 must land on their next ring neighbor");
        System.out.printf("  keys moved        = %d / %d (%.1f%%)  <- ~= the lost shard's fair share (1/N = %.1f%%)%n",
                moved, M, 100.0 * moved / M, 100.0 / N);
        System.out.println("  unroutable keys   = " + unroutable + "  <- ring still covers every key");
        System.out.println("  post-loss counts  = " + redistribution);
    }
}

Compile and run: javac ShardDemo.java && java ShardDemo. The whole design lives in one method, Ring.owner: ceilingEntry(h) finds the first vnode at or after the key's hash, and the null fallback to firstEntry() is the wraparound that makes the "ring" actually circular instead of a line with an edge case at the top.

4b. Build it — Go

Same hash, same numbers, same ring semantics. Go has no built-in sorted map, so the ring is a slice of (hash, shard) points kept sorted, and Owner does the "first point ≥ key's hash, wrapping to index 0" lookup with sort.Search — the binary-search equivalent of Java's ceilingEntry.

package main

import (
	"fmt"
	"math/rand"
	"sort"
)

// ---------- Deterministic hash (FNV-1a, 32-bit) ----------

func fnv1a(s string) uint64 {
	var hash uint64 = 2166136261
	for i := 0; i < len(s); i++ {
		hash ^= uint64(s[i])
		hash = (hash * 16777619) & 0xffffffff
	}
	return hash
}

func modShard(key string, n int) int {
	return int(fnv1a(key) % uint64(n))
}

// ---------- Consistent hash ring with virtual nodes ----------

type ringPoint struct {
	hash  uint64
	shard string
}

type Ring struct {
	points []ringPoint // kept sorted by hash
	vnodes int
}

func NewRing(vnodes int) *Ring {
	return &Ring{vnodes: vnodes}
}

func (r *Ring) sortPoints() {
	sort.Slice(r.points, func(i, j int) bool { return r.points[i].hash < r.points[j].hash })
}

func (r *Ring) AddShard(shard string) {
	for i := 0; i < r.vnodes; i++ {
		r.points = append(r.points, ringPoint{fnv1a(fmt.Sprintf("%s#%d", shard, i)), shard})
	}
	r.sortPoints()
}

func (r *Ring) RemoveShard(shard string) {
	out := r.points[:0]
	for _, p := range r.points {
		if p.shard != shard {
			out = append(out, p)
		}
	}
	r.points = out
}

func (r *Ring) Owner(key string) string {
	if len(r.points) == 0 {
		return ""
	}
	h := fnv1a(key)
	idx := sort.Search(len(r.points), func(i int) bool { return r.points[i].hash >= h })
	if idx == len(r.points) {
		idx = 0 // wrap around the ring
	}
	return r.points[idx].shard
}

func (r *Ring) Copy() *Ring {
	cp := &Ring{vnodes: r.vnodes, points: make([]ringPoint, len(r.points))}
	copy(cp.points, r.points)
	return cp
}

func maxMinRatio(counts map[string]int) float64 {
	max, min := -1<<62, 1<<62
	for _, v := range counts {
		if v > max {
			max = v
		}
		if v < min {
			min = v
		}
	}
	if min == 0 {
		return -1 // signal "infinite"
	}
	return float64(max) / float64(min)
}

func sortedKeysCounts(counts map[string]int) string {
	keys := make([]string, 0, len(counts))
	for k := range counts {
		keys = append(keys, k)
	}
	sort.Strings(keys)
	out := "map["
	for i, k := range keys {
		if i > 0 {
			out += " "
		}
		out += fmt.Sprintf("%s:%d", k, counts[k])
	}
	return out + "]"
}

func main() {
	N := 8         // shards
	M := 100000    // distinct keys
	V := 500       // virtual nodes per shard

	keys := make([]string, M)
	for i := 0; i < M; i++ {
		keys[i] = fmt.Sprintf("key-%d", i)
	}

	fmt.Println("== Movement 1: route M keys by hash(key) % N, measure the distribution ==")
	baseline := map[string]int{}
	for i := 0; i < N; i++ {
		baseline[fmt.Sprintf("shard-%d", i)] = 0
	}
	for _, k := range keys {
		s := fmt.Sprintf("shard-%d", modShard(k, N))
		baseline[s]++
	}
	fmt.Printf("  shards=%d keys=%d\n", N, M)
	fmt.Println("  counts =", sortedKeysCounts(baseline))
	fmt.Printf("  max/min imbalance ratio = %.3f  (close to 1.0 = balanced)\n", maxMinRatio(baseline))

	fmt.Println()
	fmt.Println("== Movement 2: inject a HOT KEY, measure the imbalance, then fix with salting ==")
	totalRequests := 200000
	hotFraction := 40 // hot key gets 40% of all traffic
	hotCount := totalRequests * hotFraction / 100
	rnd := rand.New(rand.NewSource(42))

	hot := map[string]int{}
	for i := 0; i < N; i++ {
		hot[fmt.Sprintf("shard-%d", i)] = 0
	}
	for r := 0; r < totalRequests; r++ {
		var key string
		if r < hotCount {
			key = "hot-key"
		} else {
			key = fmt.Sprintf("key-%d", rnd.Intn(M))
		}
		s := fmt.Sprintf("shard-%d", modShard(key, N))
		hot[s]++
	}
	fmt.Printf("  requests=%d, hot key share=%d%%\n", totalRequests, hotFraction)
	fmt.Println("  counts (BEFORE fix) =", sortedKeysCounts(hot))
	fmt.Printf("  max/min imbalance ratio (BEFORE) = %.3f  <- one shard is overloaded\n", maxMinRatio(hot))

	splitFactor := 16 // salt the hot key into 16 sub-keys
	salted := map[string]int{}
	for i := 0; i < N; i++ {
		salted[fmt.Sprintf("shard-%d", i)] = 0
	}
	rnd = rand.New(rand.NewSource(42))
	for r := 0; r < totalRequests; r++ {
		var key string
		if r < hotCount {
			key = fmt.Sprintf("hot-key#%d", r%splitFactor) // spread the hot key across sub-keys
		} else {
			key = fmt.Sprintf("key-%d", rnd.Intn(M))
		}
		s := fmt.Sprintf("shard-%d", modShard(key, N))
		salted[s]++
	}
	fmt.Printf("  counts (AFTER salting, split=%d) = %s\n", splitFactor, sortedKeysCounts(salted))
	fmt.Printf("  max/min imbalance ratio (AFTER)  = %.3f  <- rebalanced\n", maxMinRatio(salted))

	fmt.Println()
	fmt.Println("== Movement 3: consistent hashing (vnodes) vs naive mod-N on shard ADD ==")
	naiveChanged := 0
	for _, k := range keys {
		if modShard(k, N) != modShard(k, N+1) {
			naiveChanged++
		}
	}
	naiveFrac := float64(naiveChanged) / float64(M)
	fmt.Printf("  naive mod-N remap:     %d / %d keys moved (%.1f%%)  <- almost everything reshuffles\n",
		naiveChanged, M, naiveFrac*100)

	ringN := NewRing(V)
	for i := 0; i < N; i++ {
		ringN.AddShard(fmt.Sprintf("shard-%d", i))
	}
	ringN1 := ringN.Copy()
	ringN1.AddShard(fmt.Sprintf("shard-%d", N)) // add one more shard

	chChanged := 0
	for _, k := range keys {
		if ringN.Owner(k) != ringN1.Owner(k) {
			chChanged++
		}
	}
	chFrac := float64(chChanged) / float64(M)
	fmt.Printf("  consistent hashing:    %d / %d keys moved (%.1f%%)  <- only the new shard's fair share\n",
		chChanged, M, chFrac*100)
	fmt.Printf("  theoretical target ~= 1/(N+1) = %.1f%%  -- naive is ~%.0fx worse\n",
		100.0/float64(N+1), naiveFrac/chFrac)

	fmt.Println()
	fmt.Println("== Movement 4: SHARD LOSS -- remove a shard, measure remap + no unroutable keys ==")
	before := make(map[string]string, M)
	for _, k := range keys {
		before[k] = ringN.Owner(k)
	}

	afterLoss := ringN.Copy()
	afterLoss.RemoveShard("shard-0")

	moved, unroutable := 0, 0
	redistribution := map[string]int{}
	for _, k := range keys {
		owner := afterLoss.Owner(k)
		if owner == "" {
			unroutable++
		} else {
			redistribution[owner]++
		}
		if owner == "" || owner != before[k] {
			moved++
		}
	}
	fmt.Println("  removed shard-0; keys formerly on shard-0 must land on their next ring neighbor")
	fmt.Printf("  keys moved        = %d / %d (%.1f%%)  <- ~= the lost shard's fair share (1/N = %.1f%%)\n",
		moved, M, 100.0*float64(moved)/float64(M), 100.0/float64(N))
	fmt.Println("  unroutable keys   =", unroutable, " <- ring still covers every key")
	fmt.Println("  post-loss counts  =", sortedKeysCounts(redistribution))
}

Run: go run shard.go (clean under go vet). Movements 1, 3, and 4 print byte-identical numbers to the Java run — same hash function, same deterministic key set, same ring math. Movement 2's hot-key numbers differ in the third digit because Java's Random and Go's math/rand don't produce the same sequence for the same seed; the shape of the result (~6.4× imbalance collapsing to ~1.5×) is identical.

5. Break it by running it — the four measured numbers

Here is the Java run, in full:

== Movement 1: route M keys by hash(key) % N, measure the distribution ==
  shards=8 keys=100000
  counts = {shard-0=12498, shard-1=12501, shard-2=12500, shard-3=12498, shard-4=12501, shard-5=12500, shard-6=12501, shard-7=12501}
  max/min imbalance ratio = 1.000  (close to 1.0 = balanced)

== Movement 2: inject a HOT KEY, measure the imbalance, then fix with salting ==
  requests=200000, hot key share=40%
  counts (BEFORE fix) = {shard-0=15151, shard-1=14964, shard-2=95009, shard-3=14926, shard-4=15066, shard-5=14863, shard-6=15086, shard-7=14935}
  max/min imbalance ratio (BEFORE) = 6.392  <- one shard is overloaded
  counts (AFTER salting, split=16) = {shard-0=20151, shard-1=29964, shard-2=25009, shard-3=19926, shard-4=25066, shard-5=24863, shard-6=30086, shard-7=24935}
  max/min imbalance ratio (AFTER)  = 1.510  <- rebalanced

== Movement 3: consistent hashing (vnodes) vs naive mod-N on shard ADD ==
  naive mod-N remap:     88864 / 100000 keys moved (88.9%)  <- almost everything reshuffles
  consistent hashing:    8584 / 100000 keys moved (8.6%)  <- only the new shard's fair share
  theoretical target ~= 1/(N+1) = 11.1%  -- naive is ~10x worse

== Movement 4: SHARD LOSS -- remove a shard, measure remap + no unroutable keys ==
  removed shard-0; keys formerly on shard-0 must land on their next ring neighbor
  keys moved        = 13403 / 100000 (13.4%)  <- ~= the lost shard's fair share (1/N = 12.5%)
  unroutable keys   = 0  <- ring still covers every key
  post-loss counts  = {shard-1=11983, shard-2=13734, shard-3=15028, shard-4=11857, shard-5=15696, shard-6=15500, shard-7=16202}

Movement 1 — the baseline is genuinely flat. 100,000 distinct keys over 8 shards land within ±3 of the 12,500 mean per shard; the max/min ratio is 1.000. This is the case that makes "just hash and mod" look sufficient — and for a fixed key set and fixed shard count, it is.

Movement 2 — one hot key breaks it completely, and salting fixes it. With 40% of 200,000 requests aimed at a single key, shard-2 (where that key happens to hash) absorbs 95,009 requests while the coldest shard gets 14,863 — a 6.392× imbalance driven entirely by one logical key. Rewriting that one key into 16 salted variants (hot-key#0 .. hot-key#15) before routing spreads the same 80,000 hot requests across up to 16 different shard assignments; the post-fix ratio drops to 1.510. It isn't perfectly flat — with only 16 salts and 8 shards, a couple of shards get slightly luckier than others — but it went from "one shard is doing 6× the work" to "shards differ by at most 50%," and increasing the split factor tightens it further at the cost of a wider fan-out read.

Movement 3 — the reshuffle-on-resize gap, measured, not asserted. Going from 8 to 9 shards under naive % N moves 88,864 of 100,000 keys (88.9%) — essentially the entire key space reassigns owners for a single added node. The identical 8→9 change on the consistent-hashing ring moves 8,584 keys (8.6%) — within a rounding error of the theoretical 1/(N+1) = 11.1% a perfectly even ring would hit, and ~10× less data movement than naive mod-N for the exact same capacity change.

Movement 4 — a shard loss degrades gracefully, and nothing goes dark. Deleting shard-0's 500 vnodes from the 8-shard ring moves 13,403 keys (13.4%) — close to the lost shard's fair 1/8 = 12.5% share — to the seven survivors, redistributed unevenly across them (500 vnodes per shard leaves some sampling variance, visible in the post-loss counts ranging from 11,857 to 16,202). The number that matters most operationally is unroutable keys = 0: every key that used to belong to the dead shard now resolves, automatically, to whichever surviving vnode is next clockwise — no coordinator step, no "which shard should own this now" decision, and no key left without an owner.

6. Defend under drilling

7. Selection & trade-offs — consistent hashing vs. rendezvous hashing

Consistent hashing with a ring isn't the only way to get the "~K/N keys move on an N change" property. Rendezvous hashing (a.k.a. Highest Random Weight, HRW) gets the identical bound with a completely different mechanism: for a key, compute a combined score hash(key, shard) for every currently-live shard, and assign the key to whichever shard scores highest. Add or remove a shard and only the keys that scored that shard highest (or would now score the added shard highest) move — no ring, no vnodes, no stored structure at all beyond "the current list of live shards."

PropertyRing + virtual nodes (this lab)Rendezvous hashing (HRW)
State to maintainA sorted structure of V × N points; must be updated (insert/delete) on every shard add/removeNone beyond the current shard list — nothing to build or repair
Lookup costO(log(V·N)) — one binary search / ceilingEntryO(N) — must score every live shard to find the max
Remap on N change~1/(N±1) of keys (measured: 8.6% for 8→9)~1/(N±1) of keys — same bound, different mechanism
Load balance smoothnessDepends on vnode count; needs tuning (this lab: 500/shard) to keep variance lowNaturally smooth for any N because every shard is scored independently each time; no vnode tuning knob needed
Coordination for a lookupEvery node needs the same ring snapshot to agree on ownershipEvery node needs the same live-shard list to agree on ownership — same requirement, slightly smaller data to keep in sync
Reach for it whenN is large (hundreds+ of physical shards, e.g. a big cache/KV fleet) where O(N) scoring gets expensive and O(log n) mattersN is small-to-moderate (tens of shards, typical service-level partitioning) where "no ring to build" beats "faster lookup," and you want to avoid vnode-count tuning entirely

The judgment call: both give you the core property this lab measured — bounded remap instead of naive mod-N's near-total reshuffle. The ring wins on raw lookup speed at large N because it turns "which shard" into a binary search instead of a linear scan; rendezvous wins on operational simplicity because there is no data structure to build, tune (vnode count), or keep consistent beyond the shard list itself. A third option worth naming in an interview even though it's out of scope here: jump consistent hash (Google, 2014) gets O(1) memory and O(log N) time with zero stored state, but it only supports adding shards or removing the highest-numbered one — it can't gracefully remove an arbitrary shard from the middle, which is exactly the shard-loss scenario Movement 4 measures, so it's the wrong tool for "a random node died," and the right one only for "we're monotonically growing a fixed, ordered pool."

8. Acceptance criteria — you're done when

9. You can now defend

Re-authored/deepened for this guide. Reference code compiled and executed before publishing: Java (javac ShardDemo.java && java ShardDemo, JDK 8 target) clean; Go (go vet shard.go, go run shard.go) clean. Movements 1, 3, and 4 produce byte-identical numbers across both languages (same FNV-1a hash, same deterministic key set); Movement 2's hot-key counts differ in the low digits only because Java's Random and Go's math/rand use different PRNG sequences for the same seed — reproduced from the runs, not asserted from memory. Sources: David Karger et al., "Consistent Hashing and Random Trees" (STOC 1997) — the original ring construction, designed for web-cache load distribution; Karger et al. (Akamai), the virtual-nodes refinement for smoothing load variance at low shard counts; David G. Thaler & Chinya V. Ravishankar, "A Name-Based Mapping Scheme for Rendezvous" (1996) — the HRW/rendezvous alternative; John Lamping & Eric Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (Google, 2014) — jump consistent hash and its append/remove-highest-only constraint. See also the guide's quorum lab for the replication layer this lab's routing sits on top of, and the distributed rate limiter lab for another place per-key routing decisions show up under load.

🎯 STRICT STANDOUT — Sharded Service (Hands-On H5)

Why this lab: “hash % N” is not a system. This page is rare because it prints measurements for imbalance, salting, consistent-hash remap, and shard loss — and those numbers were recomputed offline in calibration (FNV-1a, M=100000, N=8, V=500).

1. Runnable contract (K11)

  • route(key) → shard for mod-N and for consistent-hash ring with virtual nodes.
  • Metrics: per-shard request counts; max/min imbalance ratio; fraction of keys remapped on N→N+1 and on shard remove.
  • Hot-key mitigation: salt key#0..#S-1 with documented read fan-out cost.

Verified offline (calibration 2026-07-15):

  • Movement 1 uniform: max/min ≈ 1.000 (page 1.000) ✓
  • Movement 2 hot 40% traffic: before ≈ 6.449 (page 6.4×); after 16-way salt ≈ 1.539 (page 1.5×) ✓
  • Movement 3 add shard 8→9: mod-N moves 88.9%; CH moves 8.6% ✓
  • Movement 4 lose 1/8: moves 13.4% (≈ fair 12.5% share); unroutable = 0 ✓

Small wording gaps (6.4 vs 6.449, 1.5 vs 1.539) are rounding — not material K1 defects.

2. Failure under partition / load (K12)

  • Hot key: traffic skew ≠ keyspace skew; more shards do not fix one key → one shard.
  • mod-N reshard: ~89% move on +1 shard → cache cold, connection storms.
  • Shard loss: ring must keep 0 unroutable; moved fraction ≈ lost share; in-flight state on lost shard still needs replication (out of pure routing lab).

3. When-NOT (K13)

  • N fixed forever and keys uniform → mod-N is simpler; skip ring complexity.
  • Single node fits → do not shard for fashion.
  • Need perfect balance with tiny N → more vnodes help, but measurement beats lore; rendezvous/jump hash may fit constraints better.

4. Hostile panel

  1. Why vnodes=500? — smooths arc length variance; show lumpy ring with vnodes=1.
  2. Salt read cost? — fan-out S subkeys and merge; only for hot keys.
  3. Does CH move data for free? — no; it bounds which keys move; migration still costs bandwidth.

5. Drills

Re-run ShardDemo; change V and remeasure post-loss balance; implement rendezvous hashing and compare remap %.

🔩 Production depth — Sharded Service (measured)

Spine: distributed-correctness · private lab · not a tool list

Production angle

Sharding is how systems scale writes — and how they create hot partitions and reshard outages. This lab’s value is measured humility: hash % N is easy until membership changes or one key owns 40% of traffic.

Worked failure: “just add a shard”

  1. Peak traffic; team scales N=8 → N=9 with mod-N.
  2. ~89% of keys remap; caches cold; DB connections storm; SEV.

Contrast: consistent hashing + virtual nodes moves ~order 1/N of keys. Your lab numbers exist to make this argument with evidence, not vibes.

Hot key failure

Celebrity tenant pins one shard. Salting/spreading trades fan-out reads for balance — document the cost.

Invariants

  • Every key maps to a live shard under declared membership.
  • Membership change cost is estimated before the change window.
  • Unroutable keys = 0 under clean ring design when a shard dies (or explicit failover).

When-NOT

Data fits one primary happily; premature sharding is operational debt. Prefer vertical scale until metrics force the cut.

Related: Partitioning theory · Flash-sale · Tenant isolation in payments.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss** (Hands-On Builds) and want to truly understand it. Explain Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build a Sharded Service — Hash Routing, Hot Keys, Consistent Hashing & Shard Loss** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design Flash-Sale Inventory (overs