wehub-resource-sync
370 lines
13 KiB
HTML
370 lines
13 KiB
HTML
<!-- Copyright 2026 Anthropic PBC · SPDX-License-Identifier: Apache-2.0 -->
|
||
<!doctype html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta charset="utf-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1">
|
||
<title>Consistent hashing — an interactive explainer</title>
|
||
<style>
|
||
:root {
|
||
--ivory: #FAF9F5;
|
||
--slate: #141413;
|
||
--clay: #D97757;
|
||
--oat: #E3DACC;
|
||
--olive: #788C5D;
|
||
--sky: #6A8CAF;
|
||
--gray-150:#F0EEE6;
|
||
--gray-300:#D1CFC5;
|
||
--gray-500:#87867F;
|
||
--gray-700:#3D3D3A;
|
||
--serif: ui-serif, Georgia, "Times New Roman", serif;
|
||
--sans: system-ui, -apple-system, "Segoe UI", Roboto, sans-serif;
|
||
--mono: ui-monospace, "SF Mono", Menlo, Consolas, monospace;
|
||
}
|
||
* { box-sizing: border-box; margin: 0; padding: 0; }
|
||
body {
|
||
background: var(--ivory);
|
||
color: var(--gray-700);
|
||
font-family: var(--sans);
|
||
font-size: 15px;
|
||
line-height: 1.65;
|
||
-webkit-font-smoothing: antialiased;
|
||
padding: 56px 24px 120px;
|
||
}
|
||
.page {
|
||
max-width: 1100px;
|
||
margin: 0 auto;
|
||
display: grid;
|
||
grid-template-columns: minmax(0, 1fr) 240px;
|
||
gap: 48px;
|
||
}
|
||
@media (max-width: 960px) { .page { grid-template-columns: 1fr; } aside { order: 2; position: static; } }
|
||
|
||
/* ── header ───────────────────────────── */
|
||
.eyebrow {
|
||
font-family: var(--mono);
|
||
font-size: 11px;
|
||
letter-spacing: 0.08em;
|
||
text-transform: uppercase;
|
||
color: var(--gray-500);
|
||
margin-bottom: 10px;
|
||
}
|
||
h1 {
|
||
font-family: var(--serif);
|
||
font-weight: 500;
|
||
font-size: 33px;
|
||
color: var(--slate);
|
||
letter-spacing: -0.01em;
|
||
margin-bottom: 12px;
|
||
}
|
||
.lead { max-width: 640px; margin-bottom: 8px; }
|
||
h2 {
|
||
font-family: var(--serif);
|
||
font-weight: 500;
|
||
font-size: 22px;
|
||
color: var(--slate);
|
||
margin: 40px 0 12px;
|
||
}
|
||
p { margin-bottom: 12px; max-width: 680px; }
|
||
code { font-family: var(--mono); font-size: 13px; }
|
||
.term {
|
||
border-bottom: 1.5px dotted var(--clay);
|
||
cursor: help;
|
||
color: var(--slate);
|
||
}
|
||
|
||
/* ── demo panel ───────────────────────── */
|
||
.demo {
|
||
border: 1.5px solid var(--gray-300);
|
||
border-radius: 14px;
|
||
background: #fff;
|
||
padding: 24px;
|
||
margin: 12px 0 8px;
|
||
}
|
||
.demo-grid {
|
||
display: grid;
|
||
grid-template-columns: 320px 1fr;
|
||
gap: 28px;
|
||
align-items: center;
|
||
}
|
||
@media (max-width: 760px) { .demo-grid { grid-template-columns: 1fr; } }
|
||
|
||
svg.ring { display: block; width: 100%; max-width: 320px; }
|
||
.ring .track { fill: none; stroke: var(--gray-300); stroke-width: 14; }
|
||
.ring .arc { fill: none; stroke-width: 14; transition: stroke-dasharray 300ms ease; }
|
||
.ring .node { stroke: #fff; stroke-width: 2; transition: cx 300ms, cy 300ms, opacity 200ms; }
|
||
.ring .key { fill: var(--slate); transition: cx 300ms, cy 300ms; }
|
||
.ring .lbl { font-family: var(--mono); font-size: 10px; fill: var(--gray-500); }
|
||
|
||
.controls { font-size: 13px; }
|
||
.controls .row { display: flex; align-items: center; gap: 12px; margin-bottom: 14px; }
|
||
.controls label { width: 64px; color: var(--gray-500); font-family: var(--mono); font-size: 11px; }
|
||
.controls .val { font-family: var(--mono); font-size: 12px; color: var(--slate); width: 28px; }
|
||
.controls input[type=range] { flex: 1; accent-color: var(--clay); }
|
||
.controls button {
|
||
appearance: none;
|
||
border: 1.5px solid var(--gray-300);
|
||
background: var(--gray-150);
|
||
border-radius: 6px;
|
||
font-family: var(--mono);
|
||
font-size: 11px;
|
||
padding: 6px 10px;
|
||
cursor: pointer;
|
||
margin-right: 6px;
|
||
}
|
||
.controls button:hover { background: var(--oat); }
|
||
|
||
.readout {
|
||
border-top: 1px solid var(--gray-300);
|
||
margin-top: 16px;
|
||
padding-top: 14px;
|
||
font-size: 13px;
|
||
}
|
||
.readout b { color: var(--slate); }
|
||
.moved { color: var(--clay); font-family: var(--mono); }
|
||
|
||
/* ── compare table ────────────────────── */
|
||
table {
|
||
border-collapse: collapse;
|
||
width: 100%;
|
||
max-width: 640px;
|
||
font-size: 13.5px;
|
||
margin: 12px 0;
|
||
}
|
||
th, td { text-align: left; padding: 10px 12px; border-bottom: 1px solid var(--gray-300); }
|
||
th { font-family: var(--mono); font-size: 11px; text-transform: uppercase; letter-spacing: 0.06em; color: var(--gray-500); font-weight: 500; }
|
||
td.bad { color: #B04A3F; }
|
||
td.good { color: var(--olive); }
|
||
|
||
/* ── glossary ─────────────────────────── */
|
||
aside {
|
||
position: sticky;
|
||
top: 32px;
|
||
align-self: start;
|
||
border: 1.5px solid var(--gray-300);
|
||
border-radius: 12px;
|
||
background: #fff;
|
||
padding: 18px 18px 8px;
|
||
}
|
||
aside .label {
|
||
font-family: var(--mono);
|
||
font-size: 10px;
|
||
letter-spacing: 0.1em;
|
||
text-transform: uppercase;
|
||
color: var(--gray-500);
|
||
margin-bottom: 12px;
|
||
}
|
||
aside dl dt {
|
||
font-family: var(--serif);
|
||
font-size: 15px;
|
||
color: var(--slate);
|
||
margin-top: 0;
|
||
}
|
||
aside dl dd {
|
||
font-size: 12.5px;
|
||
line-height: 1.5;
|
||
color: var(--gray-700);
|
||
margin: 2px 0 14px;
|
||
}
|
||
aside dl dt.hl, aside dl dt.hl + dd { background: rgba(217,119,87,0.10); margin-left: -8px; margin-right: -8px; padding-left: 8px; padding-right: 8px; border-radius: 4px; }
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="page">
|
||
|
||
<main>
|
||
<div class="eyebrow">Research & Learning · concept explainer</div>
|
||
<h1>Consistent hashing, in one ring</h1>
|
||
<p class="lead">
|
||
You have <em>K</em> keys spread across <em>N</em> cache servers. A server dies, or you add one. How many
|
||
keys have to move? With naive <code>hash(key) mod N</code> the answer is "almost all of them." Consistent
|
||
hashing gets it down to roughly <code>K / N</code>. Here's why.
|
||
</p>
|
||
|
||
<h2>The trick: hash onto a circle, not a line</h2>
|
||
<p>
|
||
Map both <span class="term" data-term="node">nodes</span> and keys onto the same
|
||
<span class="term" data-term="ring">ring</span> (the hash output space, wrapped around). A key belongs to
|
||
the first node found by walking clockwise from the key's position. When a node leaves, only the keys in
|
||
its <span class="term" data-term="arc">arc</span> reassign — to the next node round — and everything else
|
||
stays put.
|
||
</p>
|
||
|
||
<div class="demo">
|
||
<div class="demo-grid">
|
||
<svg class="ring" id="ring" viewBox="0 0 260 260"></svg>
|
||
<div class="controls">
|
||
<div class="row">
|
||
<label>nodes</label>
|
||
<input id="nSlider" type="range" min="2" max="8" value="4">
|
||
<span class="val" id="nVal">4</span>
|
||
</div>
|
||
<div class="row">
|
||
<label>keys</label>
|
||
<input id="kSlider" type="range" min="10" max="60" value="32" step="2">
|
||
<span class="val" id="kVal">32</span>
|
||
</div>
|
||
<div>
|
||
<button id="rm">remove a node</button>
|
||
<button id="add">add a node</button>
|
||
<button id="reset">reset</button>
|
||
</div>
|
||
<div class="readout" id="readout">
|
||
<b>4</b> nodes · <b>32</b> keys · <span class="moved">—</span> moved on last change
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<p style="font-size:13px; color:var(--gray-500); max-width:640px;">
|
||
Colored arcs show ownership. Removing a node hands its arc to its clockwise neighbor; every dot outside
|
||
that arc keeps its color. That's the whole idea.
|
||
</p>
|
||
|
||
<h2>Versus <code>mod N</code></h2>
|
||
<table>
|
||
<thead><tr><th></th><th>hash mod N</th><th>consistent hashing</th></tr></thead>
|
||
<tbody>
|
||
<tr><td>Keys moved when N→N+1</td><td class="bad">~ (N−1)/N of all keys</td><td class="good">~ 1/(N+1)</td></tr>
|
||
<tr><td>Hot-spot risk</td><td class="good">even by construction</td><td>uneven — fix with <span class="term" data-term="vnode">virtual nodes</span></td></tr>
|
||
<tr><td>Lookup cost</td><td class="good">O(1)</td><td>O(log N) (binary search on ring)</td></tr>
|
||
<tr><td>Used by</td><td>array sharding, simple LB</td><td>Dynamo, Cassandra, Memcached clients, Envoy</td></tr>
|
||
</tbody>
|
||
</table>
|
||
|
||
<h2>Where you'll meet it</h2>
|
||
<p>
|
||
Any time you're spreading state across a pool that changes size: cache fleets, partitioned queues, object
|
||
storage, request routing with sticky sessions. The
|
||
<span class="term" data-term="vnode">virtual-node</span> variant (each physical node owns many small arcs
|
||
instead of one big one) is what production systems actually run, because it smooths out load and makes
|
||
rebalancing even gentler.
|
||
</p>
|
||
</main>
|
||
|
||
<!-- glossary -->
|
||
<aside>
|
||
<div class="label">Glossary</div>
|
||
<dl id="gloss">
|
||
<dt data-g="ring">Ring</dt>
|
||
<dd>The hash function's output range, treated as a circle so the value after <code>max</code> is <code>0</code>.</dd>
|
||
<dt data-g="node">Node</dt>
|
||
<dd>A server placed on the ring at <code>hash(node_id)</code>. Owns every key between it and its anticlockwise neighbor.</dd>
|
||
<dt data-g="arc">Arc</dt>
|
||
<dd>The stretch of ring a node owns. Removing a node merges its arc into the next node's.</dd>
|
||
<dt data-g="vnode">Virtual node</dt>
|
||
<dd>Placing each physical node at many ring positions so arcs are small and evenly sized.</dd>
|
||
<dt data-g="successor">Successor</dt>
|
||
<dd>The first node clockwise from a given point — the owner of any key landing there.</dd>
|
||
</dl>
|
||
</aside>
|
||
|
||
</div>
|
||
|
||
<script>
|
||
/* ── tiny deterministic hash so the demo is stable ── */
|
||
function h(s) {
|
||
let x = 2166136261;
|
||
for (let i = 0; i < s.length; i++) { x ^= s.charCodeAt(i); x = (x * 16777619) >>> 0; }
|
||
return x / 4294967296;
|
||
}
|
||
const COLORS = ["#D97757", "#788C5D", "#6A8CAF", "#C2A83E", "#B04A3F", "#87867F", "#3D6E6E", "#A67C52"];
|
||
const CX = 130, CY = 130, R = 100, RKEY = 78;
|
||
const TAU = Math.PI * 2;
|
||
|
||
const ring = document.getElementById("ring");
|
||
const nSlider = document.getElementById("nSlider");
|
||
const kSlider = document.getElementById("kSlider");
|
||
const nVal = document.getElementById("nVal");
|
||
const kVal = document.getElementById("kVal");
|
||
const readout = document.getElementById("readout");
|
||
|
||
let nodes = [], keys = [], lastOwner = {};
|
||
|
||
function pt(r, t) { return [CX + r * Math.sin(t * TAU), CY - r * Math.cos(t * TAU)]; }
|
||
|
||
function ownerOf(t) {
|
||
const sorted = [...nodes].sort((a, b) => a.t - b.t);
|
||
for (const n of sorted) if (n.t >= t) return n;
|
||
return sorted[0];
|
||
}
|
||
|
||
function buildNodes(n) {
|
||
nodes = [];
|
||
for (let i = 0; i < n; i++) nodes.push({ id: "n" + i, t: h("node-" + i), color: COLORS[i % COLORS.length] });
|
||
}
|
||
function buildKeys(k) {
|
||
keys = [];
|
||
for (let i = 0; i < k; i++) keys.push({ id: "k" + i, t: h("key-" + i) });
|
||
}
|
||
|
||
function arcPath(t0, t1) {
|
||
const [x0, y0] = pt(R, t0), [x1, y1] = pt(R, t1);
|
||
let d = t1 - t0; if (d <= 0) d += 1;
|
||
const large = d > 0.5 ? 1 : 0;
|
||
return `M ${x0} ${y0} A ${R} ${R} 0 ${large} 1 ${x1} ${y1}`;
|
||
}
|
||
|
||
function render(moved) {
|
||
const sorted = [...nodes].sort((a, b) => a.t - b.t);
|
||
let svg = `<circle class="track" cx="${CX}" cy="${CY}" r="${R}"/>`;
|
||
|
||
for (let i = 0; i < sorted.length; i++) {
|
||
const cur = sorted[i];
|
||
const prev = sorted[(i - 1 + sorted.length) % sorted.length];
|
||
svg += `<path class="arc" stroke="${cur.color}" d="${arcPath(prev.t, cur.t)}"/>`;
|
||
}
|
||
for (const k of keys) {
|
||
const o = ownerOf(k.t);
|
||
const [x, y] = pt(RKEY, k.t);
|
||
svg += `<circle class="key" r="3.5" cx="${x}" cy="${y}" fill="${o.color}"/>`;
|
||
}
|
||
for (const n of sorted) {
|
||
const [x, y] = pt(R, n.t);
|
||
svg += `<circle class="node" r="9" cx="${x}" cy="${y}" fill="${n.color}"/>`;
|
||
}
|
||
svg += `<text class="lbl" x="${CX}" y="18" text-anchor="middle">0</text>`;
|
||
ring.innerHTML = svg;
|
||
|
||
readout.innerHTML =
|
||
`<b>${nodes.length}</b> nodes · <b>${keys.length}</b> keys · ` +
|
||
`<span class="moved">${moved == null ? "—" : moved + " (" + Math.round(moved / keys.length * 100) + "%)"}</span> moved on last change`;
|
||
}
|
||
|
||
function diffAndRender() {
|
||
let moved = 0;
|
||
for (const k of keys) {
|
||
const o = ownerOf(k.t).id;
|
||
if (lastOwner[k.id] && lastOwner[k.id] !== o) moved++;
|
||
lastOwner[k.id] = o;
|
||
}
|
||
render(moved);
|
||
}
|
||
|
||
function reset() {
|
||
buildNodes(+nSlider.value);
|
||
buildKeys(+kSlider.value);
|
||
lastOwner = {};
|
||
for (const k of keys) lastOwner[k.id] = ownerOf(k.t).id;
|
||
nVal.textContent = nSlider.value;
|
||
kVal.textContent = kSlider.value;
|
||
render(null);
|
||
}
|
||
|
||
nSlider.oninput = () => { nVal.textContent = nSlider.value; buildNodes(+nSlider.value); diffAndRender(); };
|
||
kSlider.oninput = () => { kVal.textContent = kSlider.value; buildKeys(+kSlider.value); lastOwner = {}; for (const k of keys) lastOwner[k.id] = ownerOf(k.t).id; render(null); };
|
||
document.getElementById("rm").onclick = () => { if (nodes.length > 2) { nodes.splice(Math.floor(Math.random() * nodes.length), 1); diffAndRender(); } };
|
||
document.getElementById("add").onclick = () => { if (nodes.length < 12) { const i = nodes.length; nodes.push({ id: "n" + Date.now(), t: Math.random(), color: COLORS[i % COLORS.length] }); diffAndRender(); } };
|
||
document.getElementById("reset").onclick = reset;
|
||
|
||
/* glossary highlight */
|
||
document.querySelectorAll(".term").forEach(el => {
|
||
const g = el.dataset.term;
|
||
el.addEventListener("mouseenter", () => document.querySelector(`dt[data-g="${g}"]`)?.classList.add("hl"));
|
||
el.addEventListener("mouseleave", () => document.querySelector(`dt[data-g="${g}"]`)?.classList.remove("hl"));
|
||
});
|
||
|
||
reset();
|
||
</script>
|
||
</body>
|
||
</html>
|