Cloud infrastructure / distributed systems deep dive

Cloud infrastructure / distributed systems deep dive

2026-09-20

Consistent hashing at scale: why a 6-byte point can reclaim 100 TB of RAM

A cache router wants stable backend assignment when servers change. The usual fix—many virtual points per server—solves load imbalance by turning memory into a hidden bill. Cloudflare’s Pingora work shows the full engineering loop: quantify variance, pack the hot struct, stop adding points when collisions dominate, then migrate rings without detonating the cache.

1. The concrete problem

Suppose a CDN stores a cacheable object in exactly one backend per data center. A request key must consistently choose that backend, otherwise every request becomes a miss somewhere. The naive mapping is hash(key) % server_count; adding one server changes the modulus, so almost every key moves. The original Ketama implementation describes this as effectively wiping the cache when the server list changes, and replaces it with a continuum of server points.

Consistent hashing changes the blast radius: hash each server to multiple positions in a 32-bit space, hash each key once, then choose the next point clockwise. Adding a server only steals the intervals immediately before its points. That is the right stability property, but a point must also remember which server owns it.

Cloudflare reports that its Pingora Backend Router had many rings because eligibility depends on combinations of features. In the cited incident, some processes held roughly 6 GB of ring data; the eventual change reclaimed more than 100 TB of RAM across the fleet.[1]

2. The ring and its data flow

The hot path is deliberately boring:

1. Build-time or control-plane input supplies backend IDs and weights.
2. For each backend, generate k × weight virtual points by hashing a stable representation such as backend-id + replica-number.
3. Sort points by their 32-bit hash.
4. For a request, hash the cache key and binary-search the first point at or after that value; wrap to element zero if necessary.
5. Use the point’s owner index to fetch the backend endpoint from a separate array.

The separation between point and backend is important. A point does not need to duplicate an IP address, socket settings, health state, or weight. It needs only a hash and an index. In Pingora’s source, the crate exposes the ring abstraction and a configurable second implementation; the repository also includes benchmarks and tests for the crate.[2]

struct Point {
    hash:  u32,  // ordering key in the continuum
    index: u32,  // backend-table index
}

points.sort_unstable_by_key(|p| p.hash);
let i = lower_bound(points, hash(key));
let p = points[i % points.len()];
let backend = backends[p.index as usize];

There are two distinct correctness contracts: the ring must be deterministic for every process that consumes it, and the point array must stay sorted after construction. A fast lookup on a non-identical ring is still a wrong lookup.

3. Why virtual points exist

With one point per server, each server receives one random interval. Random intervals are noisy: one server can own a huge slice and another a tiny slice. Virtual points sum many random intervals, so their relative error falls.

For N equal-weight servers and k points per server, Cloudflare gives the coefficient of variation as:

CV(k) = sqrt((N - 1) / (N * k + 1))

The useful intuition is not the exact derivation: doubling points does not halve every operational problem, and the last improvements become expensive. Weighting changes the expected share, not the need for enough samples. If server S1 should receive w times the traffic of S2, give S1 approximately w times as many points. The old Ketama README documents this same weighted-continuum model, using allocated memory as an example weight.[3]

4. The 8-byte-to-6-byte struct

The obvious optimization is to reduce the owner index from 32 bits to 16 bits. If a ring never addresses more than 65,535 backends, the range is sufficient:

struct PointV2 {
    hash:  u32,
    index: u16,
}

But this is still typically 8 bytes in memory. Struct layout obeys alignment: a type containing a 4-byte field usually gets a size rounded to a multiple of 4, so two bytes of tail padding remain. A smaller field does not automatically mean a smaller object.

Cloudflare’s safe compact representation stores exactly six bytes and exposes decoding methods:

struct Point([u8; 6]);

impl Point {
    fn hash(&self) -> u32 {
        u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
    }

    fn index(&self) -> u16 {
        u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
    }
}

The byte array has alignment 1, so there is no tail padding. The tradeoff is explicit serialization logic and a hard capacity boundary. An alternative such as #[repr(packed)] can create unaligned-field hazards; the Cloudflare article points to Rust’s representation guidance and chooses byte storage instead.[1]

5. The limit: diminishing returns and collisions

The variance formula imagines a continuous ring. The implementation uses a finite 32-bit hash space. As the number of points grows, collisions become likely by the birthday-paradox effect. A collision means two virtual points occupy one coordinate; one contribution is lost or must be tie-broken, so the measured distribution no longer follows the ideal formula.

This creates a practical optimization boundary: measure both load error and collision rate. Cloudflare reports that reducing points per server by 90% produced no appreciable error in its workload, while avoiding the expensive region where extra points bought little improvement and increased collisions.[1]

Do not silently change the hash function, byte order, server canonicalization, or tie-breaking rule. Any of those changes creates a new ring, even when the backend list is textually identical. Treat ring version and construction parameters as observable identity.

6. Production migration and failure modes

A better ring is not a free cache-preserving upgrade. Changing point counts moves keys. If every request switches to the new ring immediately, the cache behaves as if it were cold and origin traffic can spike.

The safe pattern is dual-ring migration:

1. Build old and new rings in the same process.
2. Choose the ring using a stable request or key hash, not an unsticky random percentage.
3. Roll out by small validation locations, then larger data-center groups.
4. Keep a reversible switch and ring-version counters until origin traffic and hit ratio are stable.
5. Delete the old ring only after the migration reaches 100% and rollback is no longer needed.

Cloudflare describes this exact shape: both ring versions coexisted, traffic and location were controlled independently, and operators watched backend selection, memory, startup time, cache behavior, and origin traffic.[1]

Failure modes worth testing

• Non-deterministic construction: different process order or random seeds produce inconsistent routing.
• Index overflow: a 16-bit owner index wraps or is rejected when backend count exceeds the design limit.
• Weight explosion: a large disk or GPU weight creates millions of points and increases build latency and collisions.
• Empty or one-point ring: binary search and wrap logic need explicit handling.
• Health churn: rebuilding on every health update may turn a memory optimization into CPU churn; consider bounded rebuilds or a separate eligibility layer.
• Rollback mismatch: old and new rings use different backend snapshots, so switching back does not restore the previous assignment.

Security implications

Consistent hashing is not an authorization mechanism. A malicious or compromised control-plane actor who changes backend membership, weights, or the canonical server string can redirect traffic. Authenticate ring updates, bind them to an auditable configuration version, and treat the ring as routing policy. If cache keys contain tenant-sensitive material, also ensure that cache namespace and backend eligibility are part of the ring input; stability must not override isolation.

7. Reproducible lab

Goal: observe why virtual points reduce imbalance, why six-byte storage matters, and why finite hashes eventually collide.

Prerequisites: Python 3.11+; no third-party packages.

mkdir -p /tmp/ketama-lab && cd /tmp/ketama-lab
cat > lab.py <<'PY'
import hashlib, bisect, struct, sys

N = int(sys.argv[1]) if len(sys.argv) > 1 else 100
K = int(sys.argv[2]) if len(sys.argv) > 2 else 160
SPACE = 2**32

def h(s):
    return int.from_bytes(hashlib.blake2s(s.encode(), digest_size=4).digest(), 'big')

points = sorted((h(f"node-{i}-replica-{r}"), i) for i in range(N) for r in range(K))
coords = [p[0] for p in points]
counts = [0] * N
for q in range(200_000):
    x = h(f"key-{q}")
    j = bisect.bisect_left(coords, x) % len(points)
    counts[points[j][1]] += 1
mean = sum(counts) / N
cv = (sum((x - mean)**2 for x in counts) / N) ** 0.5 / mean
collisions = len(points) - len(set(coords))
print(f"servers={N} points={len(points)} measured_cv={cv:.4f} collisions={collisions}")
print(f"u32 Point bytes={N*K*8:,} packed Point bytes={N*K*6:,}")

for n, f in (("u32", "<II"), ("u16", "<IH")):
    print(n, struct.calcsize(f), "bytes per logical point")
PY
python3 lab.py
python3 lab.py 100 1
python3 lab.py 2048 10000

Expected observations: the 160-point run should have a much lower measured coefficient of variation than the 1-point run; the byte calculation shows exactly 25% savings from 8 to 6 bytes; the 2,048-server / 10,000-point run has 20,480,000 nominal coordinates and should visibly report collisions in a 32-bit space.

Variation 1: change digest_size=4 to digest_size=8 and set SPACE=2**64 if you extend the experiment to use 64-bit coordinates; collisions should become much less visible, but every point’s hash field doubles in size.

Variation 2: add weighted nodes by changing the inner range to range(K * weight[i]). Watch the heavy node’s share approach its target while memory and collision pressure scale with the weight.

Takeaway

Consistent hashing is often introduced as a clever ring. In production it is a sampled load-distribution data structure, a memory layout, and a rollout protocol at the same time. The winning optimization is not “use fewer points” or “pack a struct” in isolation. It is: measure the error budget, choose the smallest representation that preserves the routing contract, stop before the finite hash space fights back, and migrate as if cache locality were state that must be drained—not a switch that can be flipped.