15-research-concept-explainer.html

<!doctype html>
<html lang="zh-CN">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>一致性哈希 — 交互式讲解</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">研究与学习 · 概念讲解</div>
    <h1>一致性哈希，一个环讲清楚</h1>
    <p class="lead">
      你有 <em>K</em> 个键分散在 <em>N</em> 台缓存服务器上。一台挂了，或者加了一台，要迁移多少键？用朴素的 <code>hash(key) mod N</code>，答案是“几乎全部”。一致性哈希能把迁移量降到约 <code>K&nbsp;/&nbsp;N</code>。原理如下。
    </p>

    <h2>诀窍：哈希到一个环上，而不是一条线</h2>
    <p>
      把<span class="term" data-term="node">节点</span>和键都哈希到同一个 <span class="term" data-term="ring">环</span>上（哈希输出空间，首尾相连）。一个键属于从它的位置顺时针走遇到的第一个节点。节点离开时，只有它 <span class="term" data-term="arc">弧段</span>内的键需要重新分配，转给下一个节点，其他键纹丝不动。
    </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">移除节点</button>
            <button id="add">添加节点</button>
            <button id="reset">重置</button>
          </div>
          <div class="readout" id="readout">
            <b>4</b> nodes · <b>32</b> keys · <span class="moved">—</span> 上次变更迁移的键
          </div>
        </div>
      </div>
    </div>
    <p style="font-size:13px; color:var(--gray-500); max-width:640px;">
      彩色弧段表示归属关系。移除一个节点，它的弧段交给顺时针邻居，弧段外的每个点颜色不变。这就是核心思想。
    </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>N→N+1 时的键迁移量</td><td class="bad">约 (N−1)/N 的键</td><td class="good">约 1/(N+1)</td></tr>
        <tr><td>热点风险</td><td class="good">构造即均匀</td><td>不均匀，用<span class="term" data-term="vnode">虚拟节点</span>修复</td></tr>
        <tr><td>查找开销</td><td class="good">O(1)</td><td>O(log N)（环上二分查找）</td></tr>
        <tr><td>使用者</td><td>数组分片、简单负载均衡</td><td>Dynamo, Cassandra, Memcached 客户端, Envoy</td></tr>
      </tbody>
    </table>

    <h2>你会在哪里遇到它</h2>
    <p>
      只要你要把状态散布到一个会变化大小的池中：缓存集群、分区队列、对象存储、粘性会话路由。生产系统实际跑的是 <span class="term" data-term="vnode">虚拟节点</span>变体（每个物理节点占据多个小弧段而不是一个大弧段），因为它能平滑负载，让重平衡更柔和。
    </p>
  </main>

  <!-- glossary -->
  <aside>
    <div class="label">术语表</div>
    <dl id="gloss">
      <dt data-g="ring">环</dt>
      <dd>哈希函数的输出空间，视为一个圆，<code>max</code> 之后的值是 <code>0</code>。</dd>
      <dt data-g="node">节点</dt>
      <dd>放在环上 <code>hash(node_id)</code> 位置的服务器。拥有它与逆时针邻居之间的所有键。</dd>
      <dt data-g="arc">弧段</dt>
      <dd>一个节点拥有的环段。节点移除时，它的弧段并入下一个节点。</dd>
      <dt data-g="vnode">虚拟节点</dt>
      <dd>让每个物理节点占据环上多个位置，使弧段更小、更均匀。</dd>
      <dt data-g="successor">后继节点</dt>
      <dd>给定点顺时针方向的第一个节点，即该位置上任何键的拥有者。</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>