Consistent hashing — ring, virtual node আর rendezvous hashing

১ · সমস্যা — key কোন সার্ভারে যাবে, আর hash mod N-এর ফাঁদ

একটি কাল্পনিক ride-sharing অ্যাপের কথা ভাবুন। প্রতিবার অ্যাপ খুললে ব্যবহারকারীর profile লাগে, তাই সেটি database-এ না গিয়ে একটি cache-এ রাখা হয়। ব্যবহারকারী কোটি ছাড়িয়েছে, একটি cache সার্ভারে আর আঁটে না — তাই ৪টি cache সার্ভার, আর ডেটা তাদের মধ্যে ভাগ করা (sharding). এখন প্রতিটি অনুরোধে app server-কে এক মুহূর্তে বলতে হবে: user:42-এর profile কোন cache সার্ভারে আছে?

চারজনকেই জিজ্ঞেস করা যায় — কিন্তু তাতে চার গুণ অনুরোধ। একটি কেন্দ্রীয় তালিকা রাখা যায় (“কোন key কোথায়”) — কিন্তু কোটি key-এর তালিকা নিজেই একটি বড় সার্ভিস, আর প্রতিটি অনুরোধে তাকে জিজ্ঞেস করা মানে নতুন একটি bottleneck. সবচেয়ে সুন্দর উত্তর হলো এমন একটি নিয়ম, যা যে কেউ নিজেই হিসাব করে বের করতে পারে: node = f(key).

এমন নিয়মের কাছে চাওয়া চারটি: একই key-এ সবাই একই উত্তর পাবেন (deterministic); প্রতিটি সার্ভার মোটামুটি সমান key পাবে (balance); সার্ভার যোগ, বাদ বা বিকল হলে যত কম সম্ভব key-এর ঠিকানা বদলাবে; আর হিসাব হবে দ্রুত, অল্প memory-তে।

প্রথম দুটি সহজেই মেলে hash mod N দিয়ে: key-এর hash নিন, সার্ভারের সংখ্যা N দিয়ে ভাগ করুন, ভাগশেষই সার্ভারের নম্বর। Hash function কীভাবে key থেকে সংখ্যা বানায়, তা DSA কোর্সের Hash table পর্বে আছে।

সমস্যাটি তৃতীয় চাওয়ায় — নড়াচড়ায়। ছোট উদাহরণ: ছয়টি key-এর hash ধরা যাক ৫, ২০, ৩৮, ৫০, ৭৭ আর ৯৫।

ছয়টির পাঁচটিই সরল, আর মজার ব্যাপার — একটিও নতুন সার্ভার ৪-এ যায়নি; সবাই পুরোনো সার্ভারদের মধ্যেই অদলবদল হলো। নতুন সার্ভারে একটিও না যাওয়াটা এই ছোট উদাহরণের কাকতাল (গড়ে ১/৫ ভাগ key নতুন সার্ভারে যায়); কিন্তু এত বেশি key সরা কাকতালীয় নয়, সাধারণ সূত্রেই আসে:

Cache-এর জন্য এর মানে ভয়ংকর। ধরা যাক আগে hit ratio ৯৫% ছিল। ৪ থেকে ৫টি সার্ভার করার মুহূর্তে ৮০% key ভুল সার্ভারে খোঁজা হবে, তাই hit নেমে আসে ০.৯৫ × ০.২ = ১৯%-এ — cache miss ৫% থেকে ৮১%, অর্থাৎ database-এর চাপ হঠাৎ প্রায় ১৬ গুণ (০.৮১ ÷ ০.০৫ = ১৬.২)। ঠিক যখন বাড়তি traffic সামলাতে সার্ভার যোগ করলেন, তখনই database ডুবে যাওয়ার ঝুঁকি — একটি ক্লাসিক cache stampede.

২ · Hash ring — সার্ভার আর key একই বৃত্তে

Consistent hashing-এর মূল চাল একটাই: সার্ভারের নম্বর গোনা বাদ দিন। তার বদলে hash-এর সব সম্ভাব্য মান — 32-bit hash-এ 0 থেকে 2³² − 1 — একটি বৃত্তের ওপর সাজান, যেখানে সবচেয়ে বড় মানের পরে আবার 0 আসে। এই পুরো পরিসর হলো hash space, আর বৃত্তটি ring.

• প্রতিটি সার্ভারের নাম বা ঠিকানার hash = ring-এ তার অবস্থান (একে অনেক সিস্টেমে token বলে)।
• প্রতিটি key-এর hash = ring-এ key-এর অবস্থান।
• নিয়ম: key-এর অবস্থান থেকে ঘড়ির কাঁটার দিকে এগোলে প্রথম যে সার্ভার পড়ে, সেই key-এর মালিক। শেষ মান পেরিয়ে গেলে বৃত্ত ঘুরে শুরু থেকে (wrap-around).

নিচের stepper-এ ছোট একটি ring: hash-এর মান ধরা হলো মাত্র 0 থেকে 99, চারটি সার্ভার আর ছয়টি key — আগের টেবিলের সেই একই ছয়টি hash-মান।

খুঁটিনাটি: key-এর hash কোনো সার্ভারের অবস্থানের সমান হলে সেই সার্ভারই মালিক — “প্রথম যে অবস্থান সমান বা বড়”। মালিক জানতে শুধু সার্ভারগুলোর অবস্থান জানলেই চলে; key-এর তালিকা কারও কাছে রাখতে হয় না।

৩ · সার্ভার যোগ বা বাদ — কেন মাত্র প্রায় K/N key সরে

এবার আসল পরীক্ষা: একই ring-এ একটি সার্ভার যোগ করুন, তারপর একটি সরিয়ে দিন। প্রতিটি ধাপে খেয়াল করুন কোন key নড়ল আর কোনটি নড়ল না।

key  hash  mod 4  mod 5
k1      5    1 B    0 A   সরল
k2     20    0 A    0 A   থাকল
k3     38    2 C    3 D   সরল
k4     50    2 C    0 A   সরল
k5     77    1 B    2 C   সরল
k6     95    3 D    0 A   সরল

এটিই consistent hashing-এর মূল প্রতিশ্রুতি, Karger-দের paper-এ যার নাম monotonicity: যোগের সময় key শুধু পুরোনো সার্ভার থেকে নতুনে যায়, পুরোনোদের নিজেদের মধ্যে কখনো নয়। এবার গড়ের হিসাব।

তবে “প্রত্যাশিত” শব্দটি গুরুত্বপূর্ণ: একটিমাত্র অবস্থানে নতুন সার্ভারের বৃত্তাংশ ভাগ্যক্রমে খুব ছোট বা খুব বড় হতে পারে। নিচের প্রোগ্রাম নির্দিষ্ট seed থেকে ১০,০০০টি key বানিয়ে দুই পদ্ধতিতেই ৪ থেকে ৫টি সার্ভারে যায়; ring-এ প্রতিটি সার্ভার ১০০টি জায়গায় (virtual node — অংশ ৪)। Hash হলো FNV-1a 32-bit, তারপর MurmurHash3-এর fmix32 নামের একটি mixing ধাপ, যাতে প্রায় একই রকম নাম (S0#1, S0#2) থেকেও ring-এ দূরে দূরে অবস্থান আসে।

// 10,000 keys, servers 4 -> 5: how many keys change server? mod-N vs ring.
function h32(s) {                // FNV-1a 32-bit, then MurmurHash3's fmix32 to mix bits
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
let seed = 16; function rand() { // mulberry32: small seeded PRNG for the keys
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
const keys = Array.from({ length: 10000 }, () => "user:" + Math.floor(rand() * 1e9));
function ring(n, v) {            // n servers, v virtual nodes each, sorted by position
  const pts = [];
  for (let s = 0; s < n; s++) for (let i = 0; i < v; i++) pts.push([h32("S" + s + "#" + i), s]);
  return pts.sort((a, b) => a[0] - b[0]);
}
function owner(pts, x) {         // first point clockwise from x (binary search, wrap)
  let lo = 0, hi = pts.length;
  while (lo < hi) { const m = (lo + hi) >> 1; if (pts[m][0] < x) lo = m + 1; else hi = m; }
  return pts[lo % pts.length][1];
}
const r4 = ring(4, 100), r5 = ring(5, 100);
let mod = 0, modNew = 0, rg = 0, rgNew = 0;
for (const k of keys) {
  const x = h32(k);
  if (x % 4 !== x % 5) { mod++; if (x % 5 === 4) modNew++; }
  const a = owner(r4, x), b = owner(r5, x);
  if (a !== b) { rg++; if (b === 4) rgNew++; }
}
const pct = (c) => (100 * c / keys.length).toFixed(1) + "%";
console.log("mod-N  moved " + pct(mod) + "   to new server " + pct(modNew) + "   between old servers " + pct(mod - modNew));
console.log("ring   moved " + pct(rg) + "   to new server " + pct(rgNew) + "   between old servers " + pct(rg - rgNew));
console.log("theory mod-N 1 - 1/5 = 80.0%, minimum possible 1/5 = 20.0%");

mod-N  moved 80.1%   to new server 20.1%   between old servers 59.9%
ring   moved 21.9%   to new server 21.9%   between old servers 0.0%
theory mod-N 1 - 1/5 = 80.0%, minimum possible 1/5 = 20.0%

৪ · Virtual node — অসম ভাগকে সমান করা

প্রতিটি সার্ভারের একটিমাত্র অবস্থান থাকলে দুটি সমস্যা। প্রথমত, এলোমেলো বিন্দুর মাঝের ফাঁক খুব অসমান: N-টি এলোমেলো বিন্দুতে সবচেয়ে বড় বৃত্তাংশের প্রত্যাশিত মাপ গড়ের প্রায় H_N = 1 + 1/2 + … + 1/N গুণ; N = ১০-এ প্রায় ২.৯ গুণ, আর সবচেয়ে ছোটটি গড়ের মাত্র ১/N ভাগ। দ্বিতীয়ত, বিকল সার্ভারের পুরো ভার যায় একটিমাত্র প্রতিবেশীতে।

সমাধান: প্রতিটি আসল সার্ভারকে ring-এ V জায়গায় বসান — নাম বদলে বদলে hash নিন (S3#0, S3#1, …), প্রতিটি একটি virtual node. Key-এর নিয়ম একই: ঘড়ির কাঁটার দিকে প্রথম বিন্দু, আর সেই বিন্দু যে আসল সার্ভারের, key তার।

কেন কাজ করে: এখন প্রতিটি সার্ভারের ভাগ একটি নয়, V-টি বৃত্তাংশের যোগফল। মোট N·V-টি বিন্দু, তাই একেকটি বৃত্তাংশের গড় মাপ 1/(N·V), আর এলোমেলো ফাঁকের ছড়ানোও মোটামুটি গড়ের সমান। স্বাধীন V-টি টুকরো যোগ করলে গড় বাড়ে V গুণ, কিন্তু ছড়ানো বাড়ে মাত্র √V গুণ — ক্রিকেটে একটি ইনিংস দেখে ব্যাটারকে বিচার করা আর ১০০ ইনিংসের গড় দেখার মতো। ফলে:

এখানে ছড়ানোর মাপ standard deviation (sd). N = ১০-এ সূত্রটি দেয়: V = ১-এ প্রায় ৯০%, V = ১০-এ ৩০%, V = ১০০-এ ৯.৫%, V = ১,০০০-এ ৩.০%. অর্থাৎ ভাগ ১০ গুণ বেশি সমান করতে বিন্দু লাগে ১০০ গুণ। নিচের প্রোগ্রাম ১০টি সার্ভার আর ১,০০,০০০টি key দিয়ে চারটি V-এর জন্য সত্যিকারের ভাগ মাপে।

// 10 servers, 100,000 keys: how even is the load with V virtual nodes per server?
function h32(s) {                // FNV-1a 32-bit, then MurmurHash3's fmix32 to mix bits
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
let seed = 16; function rand() { // mulberry32: small seeded PRNG for the keys
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
const N = 10, K = 100000;
const xs = Array.from({ length: K }, () => h32("user:" + Math.floor(rand() * 1e9)));
console.log("V      points    min    max  std dev  max/avg  sd/avg");
for (const V of [1, 10, 100, 1000]) {
  const pts = [];
  for (let s = 0; s < N; s++) for (let i = 0; i < V; i++) pts.push([h32("S" + s + "#" + i), s]);
  pts.sort((a, b) => a[0] - b[0]);
  const cnt = new Array(N).fill(0);
  for (const x of xs) {          // owner = first point clockwise (binary search)
    let lo = 0, hi = pts.length;
    while (lo < hi) { const m = (lo + hi) >> 1; if (pts[m][0] < x) lo = m + 1; else hi = m; }
    cnt[pts[lo % pts.length][1]]++;
  }
  const avg = K / N;
  const sd = Math.sqrt(cnt.reduce((s, c) => s + (c - avg) ** 2, 0) / N);
  console.log(String(V).padEnd(6) + String(N * V).padStart(7) + String(Math.min(...cnt)).padStart(7) +
    String(Math.max(...cnt)).padStart(7) + sd.toFixed(0).padStart(9) +
    (Math.max(...cnt) / avg).toFixed(2).padStart(9) + ((100 * sd / avg).toFixed(1) + "%").padStart(8));
}
console.log("average per server = " + K / N + " keys");

V      points    min    max  std dev  max/avg  sd/avg
1          10    224  24526     8472     2.45   84.7%
10        100   5376  14921     2665     1.49   26.7%
100      1000   8387  11381      843     1.14    8.4%
1000    10000   9394  10539      323     1.05    3.2%
average per server = 10000 keys

V কত হবে — trade-off

• Memory: ring-এ N·V-টি (token, সার্ভার) জোড়া; ১০০ × ২৫৬ = ২৫,৬০০টি, প্রতিটি ১৬ byte ধরলে প্রায় ৪০০ KB — তুচ্ছ।
• Lookup: log₂(N·V) তুলনা (অংশ ৫); V দশ গুণ করলে মাত্র প্রায় ৩.৩টি তুলনা বাড়ে।
• Metadata আর টুকরো: পুরো ring সবাইকে জানাতে বার্তা বড় হয়, আর database-এ প্রতিটি ছোট বৃত্তাংশ আলাদাভাবে কপি বা মেলাতে কাজ বাড়ে।

তাই লক্ষ্য থেকে উল্টো হিসাব করুন: sd গড়ের c ভাগের মধ্যে রাখতে V ≈ (N − 1)/(N·c²) ≈ 1/c². ৫% চাইলে V ≈ ৪০০, ১০% চাইলে ১০০। বাস্তব সিস্টেমে V প্রায়ই কয়েক ডজন থেকে কয়েকশো — সংস্করণ আর ব্যবহারভেদে আলাদা।

ভিন্ন ক্ষমতার সার্ভার — weight

Virtual node-এর একটি বাড়তি উপহার: ক্ষমতা অনুযায়ী ভাগ। যে মেশিনের RAM দ্বিগুণ, তাকে দিন 2V-টি বিন্দু — সে প্রায় দ্বিগুণ বৃত্তাংশ পাবে। নতুন সার্ভারকে ধীরে ধীরে চাপে আনতেও এটি কাজে লাগে: শুরুতে অল্প কয়েকটি বিন্দু, cache গরম হতে থাকলে (cache warming) ধাপে ধাপে বাড়ানো, যাতে হঠাৎ একসাথে অনেক miss না হয়।

৫ · Lookup খরচ, replication আর preference list

কোডে ring কোনো বৃত্ত নয় — একটি সাজানো array: প্রতিটি ঘরে (token, আসল সার্ভার)। Key-এর মালিক খোঁজা মানে “প্রথম যে token key-এর hash-এর সমান বা বড়” খোঁজা — এটি binary search, প্রতি ধাপে অর্ধেক বাদ (বিস্তারিত DSA কোর্সের Linear আর binary search পর্বে)। খুঁজতে খুঁজতে array-এর শেষ পেরিয়ে গেলে, অর্থাৎ key-এর hash সব token-এর চেয়ে বড় হলে, উত্তর প্রথম ঘর — এটিই wrap-around.

Lookup O(log(N·V)) — ১০০ × ২৫৬ = ২৫,৬০০ token-এ ⌈log₂ ২৫,৬০০⌉ = ১৫টি তুলনা; memory O(N·V); আর সার্ভার যোগ-বাদে V-টি token যোগ বা মুছে array আবার সাজানো, যা কালেভদ্রে হয়।

নিচের stepper-এ ছোট একটি ring (hash ধরা হলো 0–999): তিনটি সার্ভার, প্রত্যেকের দুটি virtual node — A: ১০৫ আর ৯৩০, B: ২৯০ আর ৬১০, C: ৪৫০ আর ৮৪৫.

Replication: পরের কয়েকটি ভিন্ন সার্ভার

একটি key-এর একটিমাত্র কপি রাখলে সেই সার্ভার বিকল হলেই ডেটা হারায়। তাই replication: key-এর প্রথম মালিক থেকে ঘড়ির কাঁটার দিকে হেঁটে প্রথম RF-টি ভিন্ন আসল সার্ভারে কপি রাখা, যেখানে RF হলো replication factor. এই ক্রমিক তালিকাই preference list — Amazon-এর Dynamo paper (DeCandia ও সহকর্মীরা, SOSP ২০০৭) এই নামটিই ব্যবহার করে। বাস্তবে তালিকা বানানোর সময় একই rack বা একই availability zone-এর সার্ভারও বাদ দেওয়া হয়, যাতে একটি বিদ্যুৎ-বিভ্রাটে সব কপি একসাথে না হারায়।

Virtual node-এ প্রতিটি বৃত্তাংশের preference list-এ ভিন্ন ভিন্ন প্রতিবেশী, তাই একটি সার্ভার বিকল হলে নতুন কপি বানানোর কাজ অনেক সার্ভার একসাথে ভাগ করে নেয় — মেরামত দ্রুত হয়।

৬ · Rendezvous hashing — প্রতিটি সার্ভারকে নম্বর, সর্বোচ্চ জেতে

Ring ছাড়াও একই সমস্যার একটি চমৎকার সরল সমাধান আছে। প্রতিটি key-এর জন্য প্রতিটি সার্ভারকে একটি নম্বর (score) দিন — score = hash(key, server), অর্থাৎ key আর সার্ভারের নাম একসাথে জুড়ে hash. যে সার্ভারের score সবচেয়ে বড়, key তার। এর নাম rendezvous hashing, বা highest random weight (HRW) hashing. David Thaler ও Chinya Ravishankar (University of Michigan) এটি প্রস্তাব করেন — ১৯৯৬ সালের একটি technical report-এ, পরে ১৯৯৮ সালে IEEE/ACM Transactions on Networking-এ (সাল আর শিরোনাম সূত্রভেদে সামান্য আলাদা লেখা হয়)।

নিচের stepper-এ key user:42 আর চারটি সার্ভার। Score হিসাব করা হয়েছে অংশ ৭-এর প্রোগ্রামের একই h32 দিয়ে: h32("user:42|S0") ইত্যাদি, তারপর 2³² দিয়ে ভাগ করে ০ থেকে ১-এর মধ্যে আনা।

প্রতিটি key-এ প্রতিটি সার্ভারের জেতার সম্ভাবনা 1/N, স্বাধীনভাবে — তাই ভাগের অসমতা আসে শুধু key-এর এলোমেলো নমুনা থেকে, ring-এর ফাঁক থেকে নয়। দুটি বাড়তি কথা:

• Weight: একটি পরিচিত রূপে score = −w ÷ ln(u), যেখানে u = hash ÷ 2³² আর w সার্ভারের weight; তখন জেতার সম্ভাবনা weight-এর সমানুপাতিক।
• দাম — O(N) lookup: প্রতিটি key-এ সব সার্ভারের hash; ১০০ সার্ভারে তুচ্ছ, হাজার হাজার সার্ভারে ধীর — তখন সার্ভারদের দলে ভাগ করে দুই স্তরে rendezvous চালানো হয়।

৭ · Jump hash, Maglev আর bounded load — বিশেষ প্রয়োজনের বিকল্প

Jump consistent hash — memory ছাড়াই

২০১৪ সালে Google-এর John Lamping ও Eric Veach একটি ছোট paper প্রকাশ করেন: “A Fast, Minimal Memory, Consistent Hash Algorithm” (arXiv). তাঁদের jump consistent hash একটি 64-bit key আর bucket-এর সংখ্যা n নিয়ে 0 থেকে n − 1-এর একটি bucket ফেরত দেয় — কোনো ring নেই, table নেই, মাত্র কয়েক লাইনের loop.

ধারণাটি: ভাবুন bucket একটি একটি করে বাড়ছে — ১, ২, … n. প্রতিবার n থেকে n + 1 হলে key 1/(n + 1) সম্ভাবনায় নতুন bucket-এ “লাফ” দেয়, নইলে জায়গায় থাকে — ঠিক ন্যূনতম নড়াচড়া। কোন ধাপে লাফ, তা ঠিক করে key দিয়ে seed করা একটি ছোট pseudo-random generator; algorithm সরাসরি পরের লাফের জায়গায় চলে যায়, তাই গড়ে প্রায় ln n-বার loop ঘোরে।

সীমা: যোগ বা বাদ করা যায় শুধু শেষের bucket; মাঝের bucket ৩-এর সার্ভার বিকল হলে তাকে বাদ দেওয়ার উপায় নেই। তাই এটি মানায় যেখানে প্রতিটি bucket নিজেই একটি replicated shard-দল — যেকোনো node যখন-তখন হারাতে পারে এমন cache cluster-এ নয়।

নিচের প্রোগ্রাম দুটি দাবি একসাথে যাচাই করে: ৫টি সার্ভার থেকে S2 বাদ দিলে rendezvous hashing-এ কী সরে, আর jump hash-এ bucket ১০ থেকে ১১ করলে কী সরে। Jump hash-এর 64-bit গুণ JavaScript-এ নির্ভুল রাখতে BigInt ব্যবহার করা হয়েছে, আর hash, seed ও key আগের প্রোগ্রামগুলোর মতোই।

// Rendezvous (HRW): remove 1 of 5 servers. Jump hash: grow 10 -> 11 buckets.
function h32(s) {                // FNV-1a 32-bit, then MurmurHash3's fmix32 to mix bits
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
let seed = 16; function rand() { // mulberry32: small seeded PRNG for the keys
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
const keys = Array.from({ length: 10000 }, () => "user:" + Math.floor(rand() * 1e9));
function hrw(key, servers) {     // score = hash(key, server); the highest score wins
  const sc = servers.map((s) => h32(key + "|" + s));
  return servers[sc.indexOf(Math.max(...sc))];
}
function jump(key, n) {          // Lamping & Veach (2014); key is a 64-bit BigInt
  let b = -1, j = 0;
  while (j < n) {
    b = j; key = BigInt.asUintN(64, key * 2862933555777941757n + 1n);
    j = Math.floor((b + 1) * (2147483648 / (Number(key >> 33n) + 1)));
  }
  return b;
}
const all = ["S0", "S1", "S2", "S3", "S4"], four = ["S0", "S1", "S3", "S4"];
const count = {}; let moved = 0, notFromS2 = 0, jMoved = 0, notToNew = 0;
for (const k of keys) {
  const a = hrw(k, all); count[a] = (count[a] || 0) + 1;
  if (a !== hrw(k, four)) { moved++; if (a !== "S2") notFromS2++; }
  const x = BigInt(h32(k)), j11 = jump(x, 11);
  if (jump(x, 10) !== j11) { jMoved++; if (j11 !== 10) notToNew++; }
}
console.log("HRW, 5 servers: " + all.map((s) => s + "=" + count[s]).join(" "));
console.log("HRW, S2 removed: moved " + (moved / 100).toFixed(1) + "%, moved but not from S2: " + notFromS2);
console.log("jump 10 -> 11: moved " + (jMoved / 100).toFixed(1) + "% (ideal 1/11 = 9.1%), not to bucket 10: " + notToNew);

HRW, 5 servers: S0=2031 S1=1959 S2=2014 S3=2046 S4=1950
HRW, S2 removed: moved 20.1%, moved but not from S2: 0
jump 10 -> 11: moved 8.8% (ideal 1/11 = 9.1%), not to bucket 10: 0

Maglev hashing — প্রতিটি packet-এ এক ধাপে উত্তর

Google-এর software load balancer Maglev-এর paper (Eisenbud ও সহকর্মীরা, NSDI ২০১৬) একটি ভিন্ন পথ দেখায়। L4 load balancer-কে প্রতিটি packet-এর জন্য backend বাছতে হয়, তাই binary search-ও তার কাছে ধীর। Maglev hashing আগে থেকেই M ঘরের একটি lookup table ভরে রাখে, যেখানে M একটি prime আর N-এর চেয়ে অনেক বড় (paper-এর উদাহরণে ৬৫,৫৩৭)। প্রতিটি backend-এর নিজের একটি পছন্দের ক্রম থাকে, আর backend-রা পালা করে পরের পছন্দের খালি ঘর দখল করে — ফলে প্রত্যেকে প্রায় ঠিক M/N ঘর পায়। Lookup মানে শুধু table[hash mod M]. দাম: backend বদলালে ring-এর চেয়ে কিছুটা বেশি ঘর বদলায়, তাই চলমান সংযোগ ঠিক রাখতে আলাদা connection-tracking-ও রাখা হয় (paper অনুযায়ী)। Envoy-র মতো proxy-তে ring hash আর Maglev দুটোই load balancing policy হিসেবে পাওয়া যায় (সংস্করণভেদে আলাদা)।

Bounded load — কেউ যেন গড়ের বেশি না পায়

২০১৬ সালে Vahab Mirrokni, Mikkel Thorup ও Morteza Zadimoghaddam “Consistent Hashing with Bounded Loads” প্রকাশ করেন (arXiv; পরে SODA ২০১৮)। Bounded-load hashing-এ প্রতিটি সার্ভারের একটি ধারণক্ষমতা থাকে: এই মুহূর্তের মোট কাজ m আর সার্ভার n হলে ⌈(1 + ε)·m/n⌉, যেমন ε = ০.২৫ মানে গড়ের সোয়া গুণ। Ring-এ key-এর প্রথম সার্ভার ভরা থাকলে কাজটি যায় পরের সার্ভারে, সেটিও ভরা হলে তার পরেরটিতে। ফলে কোনো সার্ভারের চাপ গড়ের (1 + ε) গুণ ছাড়ায় না, অথচ বেশিরভাগ key নিজের সার্ভারেই থাকে। ε যত ছোট, ভাগ তত সমান, কিন্তু নড়াচড়া তত বেশি। এটি সবচেয়ে কাজের request বা connection ভাগে, যেখানে যেকোনো সার্ভার কাজটি করতে পারে।

৮ · বাস্তবে কোথায়, আর সীমা — hot key আর membership

যেখানে দেখা যায়

• Distributed cache: Memcached-এর সার্ভারগুলো একে অপরকে চেনে না; কোন key কোথায় যাবে তা ঠিক করে client library (client-side সিদ্ধান্ত) — যেমন Last.fm-এর প্রকাশিত libketama (২০০৭ নাগাদ), যার “ketama” নামটি অনেক library আর proxy-তে রয়ে গেছে। বহু-স্তরের cache পর্ব ৩০ (Distributed cache)-এ।
• Dynamo-ধাঁচের key-value store: Dynamo paper (২০০৭) ring, virtual node আর preference list একসাথে ব্যবহার করে; Apache Cassandra-তেও token ring আছে, প্রতি node-এর token-সংখ্যা num_tokens setting-এ (ডিফল্ট সংস্করণভেদে বদলেছে)। পর্ব ৬১-র ক্যাপস্টোনে আপনি নিজেই এমন একটি store নকশা করবেন।
• CDN: একটি edge location-এর অনেকগুলো cache সার্ভারের মধ্যে কোন URL কে রাখবে, তা ঠিক করতে (পর্ব ১৭ — CDN আর edge).
• Load balancer: একই ব্যবহারকারী বা URL-কে বারবার একই backend-এ পাঠাতে (cache-এর সুবিধা বা sticky session); algorithm-গুলোর তুলনা পর্ব ১৪ (Load balancing)-এ, session-এর প্রশ্ন পর্ব ১৫ (Stateless বনাম stateful)-এ।

# Illustrative only: Nginx picks an upstream by consistent hashing of the URI.
# "consistent" switches hash from mod-N style to the ketama ring (see the docs).
upstream image_cache {
    hash $request_uri consistent;
    server 10.0.3.11:8080;
    server 10.0.3.12:8080;
    server 10.0.3.13:8080 weight=2;   # bigger machine: more points on the ring
}

সবাই ring ব্যবহার করে না। Redis Cluster প্রতিটি key-কে ফেলে ১৬,৩৮৪টি hash slot-এর একটিতে (key-এর CRC16 mod 16384, অফিসিয়াল documentation অনুযায়ী), আর কোন slot কোন node-এ তা একটি table-এ থাকে; নতুন node এলে কয়েকটি slot পুরোপুরি সরানো হয়। Kafka-র ডিফল্ট partitioner key-যুক্ত message-এ hash mod partition-সংখ্যা ব্যবহার করে, তাই partition বাড়ালে বেশিরভাগ key-এর partition বদলে যায় — তার documentation-এ এ নিয়ে সাবধান করা আছে। দুটির মিল: key থেকে ঘর (slot বা partition)-এর নিয়ম কখনো বদলায় না, বদলায় শুধু ঘরের মালিক। এই “নির্দিষ্ট অনেক ঘর” কৌশল আর rebalancing পর্ব ২৩-এ।

সীমা ১ — hot key

Consistent hashing key-এর সংখ্যা সমান করে; প্রতিটি key-তে সমান traffic এলে তবেই চাপও সমান। বাস্তবে traffic খুব অসমান — অল্প কিছু key-তেই বেশিরভাগ অনুরোধ (hot set). একটি কাল্পনিক খবরের সাইটে ক্রিকেট ফাইনালের live score-এর key-তে হঠাৎ মোট অনুরোধের বড় অংশ এলে, সেই একটি hot key যে সার্ভারে আছে সেটিই ডোবে। V বাড়িয়ে লাভ নেই — key তো একটাই। প্রতিকার: app server-এ অল্প TTL-এর local cache, hot key-এর কয়েকটি কপি (score#1 … score#4) আলাদা সার্ভারে, একসাথে আসা miss জুড়ে একটি অনুরোধ, আর request-ভাগে bounded load — প্রতিটির দাম ভাবনার প্রশ্ন ৪-এ।

সীমা ২ — সবাই একই তালিকা দেখছে তো?

সব নিয়মই ধরে নেয় যে প্রতিটি client-এর কাছে একই সার্ভার-তালিকা, অর্থাৎ একই membership. একটি app server নতুন সার্ভার D-র খবর পেয়েছে, আরেকটি পায়নি — তখন একই key দুই জায়গায় যায়, একটির invalidation অন্যটিতে পৌঁছায় না। আবার health check একবার ব্যর্থ হলেই সার্ভার বাদ, পরের বার আবার যোগ — এমন দোলাচলে বারবার key সরে। প্রতিকার আর বিস্তারিত আছে নিচের ভাবনার প্রশ্ন ৫-এ।

সীমা ৩ — সরানোর দাম আর hash-এর মান

Cache-এ একটি key সরা মানে একটি miss; database-এ মানে আসল ডেটা কপি — যা পেছনে, গতি বেঁধে করতে হয়। আর hash function হতে হবে সব process আর সংস্করণে হুবহু এক। ভাষার নিজস্ব hash প্রায়ই চলে না: Python-এ string-এর hash() ডিফল্টভাবে প্রতিটি process-এ আলাদা salt নেয়; আর Java-র String.hashCode সব জায়গায় এক হলেও server1 আর server2-এর hash পাশাপাশি — ring-এ গুচ্ছ হয়ে বসে।

৯ · AI-এর যুগে — consistent hashing-এর কোড আর দাবি যাচাই

AI কয়েক সেকেন্ডে গোছানো ring-কোড দেয়, সাথে প্রায়ই “Redis, Kafka আর microservice”-এর পরামর্শ। তার ভুলগুলো খুব নির্দিষ্ট, আর প্রায় সবই একটি ছোট simulation চালালেই ধরা পড়ে:

AI-এর ring-কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• নিজে হিসাব মিলিয়েছি: N থেকে N + 1-এ mod N সরায় N/(N + 1), ring প্রায় 1/(N + 1)
• কোড চালিয়ে দেখেছি যোগের সময় পুরোনো সার্ভারদের মধ্যে একটিও key সরে না
• Hash function নির্দিষ্ট, সব process আর সংস্করণে এক; randomized built-in hash নেই
• বাছাই করা V-তে sd/গড় মেপেছি, আর memory (N·V) ও lookup (log₂ N·V) হিসাব করেছি
• Wrap-around আর “hash ঠিক token-এর সমান” — দুই প্রান্তের ক্ষেত্র test করেছি
• Preference list-এ সার্ভার অনন্য, প্রয়োজনে আলাদা rack বা zone
• Hot key, membership-মতভেদ আর সার্ভার বিকল হওয়ার পরের চাপ নিয়ে failure-mode পর্যালোচনা করেছি