ক্যাপস্টোন — একটি distributed key-value store নকশা আর simulator

১ · সমস্যা আর পরিধি — “ভান্ডার” কী করবে, কী করবে না

মডিউল ৯-এর আগের সাতটি case study-তে key-value store ছিল একটি তৈরি যন্ত্র। URL shortener-এ ছোট code থেকে লম্বা URL, chat-এ প্রতিটি কথোপকথনের বার্তা, news feed-এ তৈরি করে রাখা timeline, notification-এ একই বার্তা দুবার না পাঠানোর চিহ্ন, ride-sharing-এ চালকের সর্বশেষ অবস্থান, video streaming-এ ভিডিওর metadata. আর ticket booking-এ দেখেছেন, কোথায় এমন store যথেষ্ট নয়। এবার যন্ত্রটির ঢাকনা খুলে নিজে একটি বানাব।

নাম দেওয়া যাক “ভান্ডার” (কাল্পনিক)। এটি একটি key-value store: প্রতিটি মান একটি key-এর নিচে থাকে, আর key দিয়েই পড়া, লেখা বা মোছা হয়। নকশা এগোবে পর্ব ৬-এর কাঠামোয় — পরিধি, হিসাব, API, ছবি, তারপর গভীরে। “গভীরে” অংশটি এখানে সাত টুকরো; প্রতিটি আগের কোনো পর্বের ধারণা, এক বাক্যে প্রয়োগ আর link-সহ। নতুন হলো টুকরোগুলো একসাথে কীভাবে বসে, আর একটি আরেকটির ওপর কী চাপ দেয়।

Functional requirement

• get(key) — মান ফেরত দেয়। একসাথে হওয়া লেখায় একাধিক মান থাকলে সবগুলো, সাথে context নামের একটি সংস্করণ-চিহ্ন।
• put(key, value, context) — মান লেখে; আগের পড়ার context সাথে দিলে store বোঝে এই লেখা কোন সংস্করণের পরে এসেছে।
• delete(key, context) — মোছে; ভেতরে এটিও একটি বিশেষ লেখা।
• প্রতিটি অনুরোধে consistency বাছাই — ONE, QUORUM বা ALL; একে বলে tunable consistency.

Non-functional requirement (ধরা যাক)

পরিধির বাইরে (অংশ ৯-এর “নিজে বাড়ান”-এ): একাধিক key জুড়ে transaction, value-এর field ধরে খোঁজা, key-এর ক্রমে range scan, একাধিক region, SQL. এগুলো বাদ রাখাই পরিধি ঠিক করা।

২ · হিসাব আর API — সংখ্যা থেকে তিনটি ক্রিয়া

সূত্রগুলো পর্ব ৩-এর; এখানে প্রয়োগ। অনুমান স্পষ্ট লেখা থাকলে আপত্তি এলে কোন সংখ্যা বদলাতে হবে তা দেখা যায়। “পরে” চাপুন:

সংখ্যাগুলো একটি ছোট script-এ মিলিয়ে নেওয়া। “একটি node সেকেন্ডে ২০ হাজার কাজ” কিন্তু অনুমান — আসল সংখ্যা আসে নিজের hardware-এ load test থেকে।

API — client যা দেখে

বাইরে থেকে তিনটি ক্রিয়া। ভেতরে node-দের মধ্যে আর client library থেকে node-এ সাধারণত একটি binary RPC (পর্ব ৯); বোঝার সুবিধার জন্য নিচে HTTP-রূপে দেখানো হলো:

GET /v1/kv/carts/cart:42?consistency=QUORUM
200 OK
{ "values": [["rice","oil"], ["rice","salt"]],      // দুটি sibling
  "context": "eyJBIjoyLCJCIjoxfQ" }                 // client-এর কাছে অস্বচ্ছ

PUT /v1/kv/carts/cart:42?consistency=QUORUM
{ "value": ["oil","rice","salt"], "context": "eyJBIjoyLCJCIjoxfQ" }
204 No Content

DELETE /v1/kv/carts/cart:42?consistency=QUORUM   (context সাথে)
204 No Content                                    // ভেতরে tombstone লেখা হয়

তিনটি নকশার সিদ্ধান্ত এই ছোট API-তেই লুকানো। প্রথম, context: get যে সংস্করণ-চিহ্ন দেয়, put তা ফেরত দেয় — একে বলে causal context. এতেই store বোঝে নতুন লেখাটি কোন কোন সংস্করণ “দেখে” লেখা হয়েছে (অংশ ৬)। দ্বিতীয়, values একটি তালিকা — একসাথে হওয়া লেখা থাকলে store সিদ্ধান্ত নেয় না, client-কে দেখায়। তৃতীয়, retry: timeout-এর পর একই put আবার পাঠালে খারাপ হলে একই মানের দুটি sibling হয়, যা client সহজেই মেলায়; তবে counter-এর “এক বাড়ানো”-য় idempotency key লাগবে (অংশ ৬)।

Data model আর partition key

Store-এর কাছে value একটি byte-এর থলি (পর্ব ২০)। প্রতিটি item: key, value বা sibling-তালিকা, vector clock, আর মোছা হলে tombstone-চিহ্ন। Partition key পুরো key-টি; তার hash ঠিক করে item কোন node-এ যাবে (পর্ব ২৩)। দাম: পাশাপাশি key আলাদা node-এ ছড়ায়, তাই range scan চলে না।

৩ · Architecture-এর সিদ্ধান্ত — leaderless quorum, না প্রতি shard-এ Raft

সবচেয়ে বড় সিদ্ধান্ত replication-এর ধরন। দুটি পরিচিত পথ: Amazon-এর Dynamo paper (২০০৭)-এর leaderless replication, যেখানে যেকোনো replica লেখা নেয় আর R ও W টির উত্তরে কাজ সফল (পর্ব ৪১); আর key-পরিসর ভাগ করে প্রতিটি ভাগে একটি করে Raft group — Multi-Raft — যেখানে প্রতিটি ভাগের একজন leader সব লেখার ক্রম ঠিক করে (পর্ব ৪২)।

পুরো ছবি

প্রতিটি node একই software চালায়, কোনো “master” নেই। ভেতরে চারটি অংশ:

সিদ্ধান্তের তালিকা — বিকল্পসহ

৪ · টুকরো ১: Partitioning — ring, virtual node আর node যোগ-বিয়োগ

প্রয়োগ এক বাক্যে: প্রতিটি node ring-এ V টি virtual node হিসেবে বসে, আর key যায় ঘড়ির কাঁটার দিকে প্রথম token-এর node-এ (পর্ব ১৬-এ ring, token আর প্রমাণ দেখেছেন)। প্রশ্ন এখানে সংখ্যার: V কত, আর পঞ্চম node এলে কত ডেটা সরবে? নিচের simulator ২০ হাজার key চারটি node-এ ভাগ করে, তারপর E যোগ করে। অবস্থান ঠিক করে FNV-1a hash, key বানায় একটি seeded PRNG (mulberry32) — প্রতিবার একই ফল:

// Part 1: ring with V virtual nodes per server. Spread of keys, and keys moved when E joins.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
function hash(s) {                                   // FNV-1a 32-bit + a final mix step
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) h = Math.imul(h ^ s.charCodeAt(i), 0x01000193);
  h = Math.imul(h ^ (h >>> 16), 0x85ebca6b); h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
function ring(servers, V) {                          // sorted tokens: [position, server]
  const t = [];
  for (const s of servers) for (let v = 0; v < V; v++) t.push([hash(s + ":" + v), s]);
  return t.sort((a, b) => a[0] - b[0]);
}
function owner(tokens, h) {                          // first token clockwise (binary search)
  let lo = 0, hi = tokens.length;
  while (lo < hi) { const m = (lo + hi) >> 1; if (tokens[m][0] < h) lo = m + 1; else hi = m; }
  return tokens[lo % tokens.length][1];
}
const rnd = mulberry32(61), K = 20000;
const keys = Array.from({ length: K }, () => hash("user:" + Math.floor(rnd() * 1e9)));
const four = ["A", "B", "C", "D"], five = [...four, "E"];
console.log("V".padEnd(6) + four.map(s => s.padStart(6)).join("") + "stddev".padStart(12) + "max/mean".padStart(10) + "moved".padStart(10));
for (const V of [1, 10, 100]) {
  const r4 = ring(four, V), r5 = ring(five, V), cnt = { A: 0, B: 0, C: 0, D: 0 };
  let moved = 0;
  for (const h of keys) { const o = owner(r4, h); cnt[o]++; if (owner(r5, h) !== o) moved++; }
  const c = four.map(s => cnt[s]), mean = K / 4;
  const sd = Math.sqrt(c.reduce((s, x) => s + (x - mean) ** 2, 0) / 4);
  console.log(String(V).padEnd(6) + c.map(x => String(x).padStart(6)).join("") + "   " +
    String(Math.round(sd)).padStart(9) + "    " + (Math.max(...c) / mean).toFixed(2).padStart(6) +
    "   " + (100 * moved / K).toFixed(1).padStart(6) + "%");
}
const naive = keys.filter(h => h % 4 !== h % 5).length;      // hash mod N: 4 -> 5 servers
console.log("naive hash mod N (4 -> 5 servers) moves " + (100 * naive / K).toFixed(1) + "% of keys; ideal is 20.0%");

V          A     B     C     D      stddev  max/mean     moved
1        219 11397  1848  6536        4361      2.28     32.5%
10      5957  3624  4654  5765         937      1.19     10.2%
100     5065  5387  5022  4526         308      1.08     17.0%
naive hash mod N (4 -> 5 servers) moves 80.1% of keys; ideal is 20.0%

সিদ্ধান্ত: প্রতি node-এ ২৫৬টি virtual node (ধরা যাক), ২৪টি node-এ ৬,১৪৪টি token. বেশি token-এর দাম: membership-এ বড় তালিকা, anti-entropy-তে বেশি key-পরিসর। Cassandra-ধাঁচে সংখ্যাটি config-এ ঠিক হয়; default সংস্করণভেদে আলাদা।

Node যোগ হলে — কোন পরিসর কার হাতে যায়

যোগ দেওয়া মানে token বসানো আর পুরোনোদের থেকে ডেটা আনা — node bootstrap. ছোট একটি ring-এ দেখা যাক: অবস্থান ০ থেকে ৯৯, প্রতি node-এ একটি token, N = ৩, E বসবে ৫০-এ:

বাদ দেওয়া দুই রকম। পরিকল্পিত decommission-এ উল্টো streaming: যাওয়ার আগে node নিজের পরিসর নতুন replica-দের দিয়ে যায়। হঠাৎ বিকলতায় সাথে সাথে ডেটা সরানো ভুল — বেশিরভাগ বিকলতা ক্ষণিকের, আর প্রতিবার ring বদলালে বিশাল streaming শুরু হতো। Dynamo paper-ও বলে, স্থায়ী যোগ-বিয়োগ স্পষ্টভাবে ঘোষণা করা হয়; ক্ষণিকের বিকলতা সামলায় অংশ ৭-এর hint আর repair. Rebalancing-এর অন্য কৌশল পর্ব ২৩-এ।

৫ · টুকরো ২: Replication — preference list আর R, W

প্রয়োগ: প্রতিটি key-এর N = ৩ কপি, ring-এ ঘড়ির কাঁটার দিকে প্রথম তিনটি আলাদা physical node-এ — একই node-এর দুটি virtual node বাদ দিয়ে (preference list, পর্ব ২২)। তিনটি কপি তিনটি আলাদা rack বা availability zone-এও, নইলে একটি বিদ্যুৎ-বিভ্রাটেই তিনটি যায় — পর্ব ৫-এর correlated failure. লেখা সফল W টি ack-এ, পড়া R টি উত্তরে, আর R + W > N হলে পড়ার দল আর লেখার দল অন্তত একটি replica-তে মেলে — প্রমাণ পর্ব ৪১-এ।

প্রশ্নটি এবার সংখ্যার: একটি replica বন্ধ থাকলে কোন (R, W)-এ কী হয়? নিচের simulator একটি key-এ ১০ হাজার রাউন্ড চালায় — প্রতি রাউন্ডে একটি put, ঠিক পরেই একটি get. প্রতিটি বার্তার latency এলোমেলো: সাধারণত ১ থেকে কয়েক ms, ৩% বার্তায় ৪০ থেকে ৮০ ms (ধরা যাক GC pause বা ব্যস্ত ডিস্ক)। Replica ২ রাউন্ড ৩০০০ থেকে ৫৯৯৯ পর্যন্ত বন্ধ। যথেষ্ট replica না থাকলে অনুরোধ ১০০ ms-এ timeout হয়ে ব্যর্থ:

// Part 2: quorum put then get on N = 3 replicas. Replica 2 is down for rounds 3000-5999.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const N = 3, ROUNDS = 10000, TIMEOUT = 100;
const p99 = a => { const s = [...a].sort((x, y) => x - y); return s[Math.ceil(0.99 * s.length) - 1]; };
function run(R, W) {
  const rnd = mulberry32(2026);                      // same latencies for every (R, W)
  const lat = () => 1 + -Math.log(1 - rnd()) + (rnd() < 0.03 ? 40 + 40 * rnd() : 0); // ms
  const has = [0, 0, 0];                             // version held by each replica
  let acked = 0, putOk = 0, getOk = 0, stale = 0; const pl = [], gl = [];
  for (let v = 1; v <= ROUNDS; v++) {
    const up = [true, !(v >= 3000 && v < 6000), true];
    const w = [0, 1, 2].map(i => ({ i, t: lat() })).filter(x => up[x.i]).sort((a, b) => a.t - b.t);
    if (w.length >= W) {                             // success after the W-th fastest ack
      const T = w[W - 1].t; acked = v; putOk++; pl.push(T);
      for (const x of w) if (x.t <= T) has[x.i] = v; // the slower replicas apply it later
    } else pl.push(TIMEOUT);
    const r = [0, 1, 2].map(i => ({ i, t: lat() })).filter(x => up[x.i]).sort((a, b) => a.t - b.t);
    if (r.length >= R) {
      getOk++; gl.push(r[R - 1].t);
      if (Math.max(...r.slice(0, R).map(x => has[x.i])) < acked) stale++;
    } else gl.push(TIMEOUT);
    for (const x of w) has[x.i] = v;                 // in-flight writes land before the next round
  }
  console.log(`(R,W)=(${R},${W})  put ok ${(100 * putOk / ROUNDS).toFixed(1)}%  get ok ${(100 * getOk / ROUNDS).toFixed(1)}%` +
    `  put p99 ${p99(pl).toFixed(1)} ms  get p99 ${p99(gl).toFixed(1)} ms  stale reads ${stale}`);
}
for (const [R, W] of [[1, 1], [2, 2], [1, 3]]) run(R, W);

(R,W)=(1,1)  put ok 100.0%  get ok 100.0%  put p99 3.1 ms  get p99 3.2 ms  stale reads 6116
(R,W)=(2,2)  put ok 100.0%  get ok 100.0%  put p99 61.3 ms  get p99 61.1 ms  stale reads 0
(R,W)=(1,3)  put ok 70.0%  get ok 100.0%  put p99 100.0 ms  get p99 3.2 ms  stale reads 0

৬ · টুকরো ৩: Versioning আর conflict — vector clock, sibling, LWW আর CRDT

Leaderless store-এ দুটি client একই key-এ প্রায় একসাথে লিখতে পারেন — বিশেষ করে network partition-এর সময়। কোনটি “পরে”, ঘড়ি দেখে বলা যায় না (পর্ব ৩৯)। “ভান্ডার” প্রতিটি সংস্করণের সাথে একটি vector clock রাখে: কোন coordinator এই key কতবার বদলেছে তার তালিকা। দুটি clock তুলনায় একটি আরেকটির আগে, পরে, অথবা দুটি concurrent — একসাথে হওয়া। Concurrent হলে store দুটিই রাখে — এরা siblings — আর পরের get-এ client-কে দুটিই দেখায়। Store-এর কাজে এটি আসলে version vector; Dynamo paper নাম দিয়েছিল vector clock, আর এই পর্বে দুটি নাম একই অর্থে।

নিচের simulator একটি কাল্পনিক অনলাইন দোকানের cart:42 নিয়ে: প্রথমে চাল, তারপর network ভাগ — A একদিকে, B আর C অন্যদিকে। দুই দিকে দুজন দুটি আলাদা জিনিস যোগ করেন। তারপর ভাগ জোড়া লাগে:

// Part 3: versioning cart:42 with vector clocks. Partition {A} | {B, C}, siblings, client merge.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const show = c => "{" + Object.keys(c).sort().map(k => k + ":" + c[k]).join(", ") + "}";
const leq = (a, b) => Object.keys(a).every(k => a[k] <= (b[k] || 0));       // a happened before or equal b
const join = cs => cs.reduce((m, c) => { for (const k in c) m[k] = Math.max(m[k] || 0, c[k]); return m; }, {});
const store = { A: [], B: [], C: [] };               // each replica keeps a list of versions (siblings)
function apply(node, ver) {                          // keep only versions not dominated by another
  const all = [...store[node], ver].filter((x, i, arr) => arr.findIndex(y => show(y.c) === show(x.c)) === i);
  store[node] = all.filter(x => !all.some(y => y !== x && leq(x.c, y.c) && show(x.c) !== show(y.c)));
}
function put(coord, context, items, to) {            // the coordinator bumps its own entry
  const c = { ...context }; c[coord] = (c[coord] || 0) + 1;
  const ver = { c, items };
  for (const n of to) apply(n, ver);
  console.log(`put via ${coord} ${JSON.stringify(items)} clock ${show(c)}`); return ver;
}
const state = () => ["A", "B", "C"].map(n => n + "=" + store[n].map(v => show(v.c)).join(" & ")).join("  ");
const v1 = put("A", {}, ["rice"], ["A", "B", "C"]);           console.log("  " + state());
console.log("-- partition: {A} | {B, C}; both sides keep taking writes");
const v2 = put("A", v1.c, ["rice", "oil"], ["A"]);
const v3 = put("B", v1.c, ["rice", "salt"], ["B", "C"]);     console.log("  " + state());
console.log("-- partition heals; anti-entropy copies versions both ways");
for (const n of ["A", "B", "C"]) { apply(n, v2); apply(n, v3); }
console.log("  " + state());
console.log(`  v2 vs v3: ${leq(v2.c, v3.c) ? "v2 <= v3" : leq(v3.c, v2.c) ? "v3 <= v2" : "concurrent -> siblings"}`);
const got = store.C, ctx = join(got.map(v => v.c));
const merged = [...new Set(got.flatMap(v => v.items))].sort();
console.log(`get via C -> ${got.length} siblings, context ${show(ctx)}, client merges to ${JSON.stringify(merged)}`);
const rnd = mulberry32(2026), order = ["A", "B", "C"].map(n => [rnd(), n]).sort((a, b) => a[0] - b[0]).map(x => x[1]);
const v4 = put("C", ctx, merged, order);  console.log(`  delivered in order ${order.join(",")}  ` + state());
v2.ts = "10:00:05"; v3.ts = "10:00:07";             // wall-clock stamps from two different nodes
const lww = v2.ts > v3.ts ? v2 : v3, lost = lww === v2 ? v3 : v2;
console.log(`LWW instead (${v2.ts} vs ${v3.ts}): keeps ${JSON.stringify(lww.items)}, silently drops ${JSON.stringify(lost.items)}`);

put via A ["rice"] clock {A:1}
  A={A:1}  B={A:1}  C={A:1}
-- partition: {A} | {B, C}; both sides keep taking writes
put via A ["rice","oil"] clock {A:2}
put via B ["rice","salt"] clock {A:1, B:1}
  A={A:2}  B={A:1, B:1}  C={A:1, B:1}
-- partition heals; anti-entropy copies versions both ways
  A={A:2} & {A:1, B:1}  B={A:1, B:1} & {A:2}  C={A:1, B:1} & {A:2}
  v2 vs v3: concurrent -> siblings
get via C -> 2 siblings, context {A:2, B:1}, client merges to ["oil","rice","salt"]
put via C ["oil","rice","salt"] clock {A:2, B:1, C:1}
  delivered in order B,A,C  A={A:2, B:1, C:1}  B={A:2, B:1, C:1}  C={A:2, B:1, C:1}
LWW instead (10:00:05 vs 10:00:07): keeps ["rice","salt"], silently drops ["rice","oil"]

প্রতিটি keyspace-এ আলাদা conflict-নীতি

Counter-এ sibling চলে না: দুই দিকে ১০ থেকে দুজনে ১ করে বাড়ালে দুটি sibling-ই ১১, অথচ উত্তর ১২. সমাধান G-Counter-এর মতো CRDT — প্রতিটি replica শুধু নিজের ঘর বাড়ায়, merge প্রতিটি ঘরের বড়টি নেয়, মান সব ঘরের যোগফল; কমানোও লাগলে PN-Counter, যেখানে বাড়ানো আর কমানোর এমন দুটি আলাদা তালিকা (পর্ব ৪৬)। “ভান্ডার”-এ তাই counters নামের keyspace-এ put-এর বদলে increment(key, delta, request_id) — request_id রাখতে হয়, কারণ retry-তে একই বাড়ানো দুবার গোনা চলবে না।

দুটি বাস্তব সমস্যা। এক, clock বড় হতে থাকে; Dynamo paper একটি সীমা পেরোলে সবচেয়ে পুরোনো ঘর ফেলার কথা বলে (প্রশ্ন ৩)। দুই, delete: মোছা মানে tombstone লেখা, কারণ শুধু মুছে দিলে পুরোনো কোনো replica-র কপি repair-এর সময় মানটি “ফিরিয়ে” আনত। Tombstone কখন চূড়ান্তভাবে মোছা নিরাপদ, তা অংশ ৮-এর সাথে জড়ানো।

৭ · টুকরো ৪ ও ৫: ব্যর্থতা সামলানো আর membership — hint, repair আর gossip

প্রয়োগ, তিনটি স্তরে (যন্ত্রপাতি আর প্রমাণ পর্ব ৪১-এ): ক্ষণিকের বিকলতায় sloppy quorum আর hinted handoff — বন্ধ replica-র লেখা পরের সুস্থ node একটি নোটসহ রাখে; প্রায়ই পড়া key-এ read repair — পড়ার সময় পুরোনো কপি পেলে ঠিক করে দেওয়া; আর বাকি সবকিছুর জন্য পেছনে চলা anti-entropy, যেখানে প্রতিটি key-পরিসরের Merkle tree তুলনা করে শুধু অমিল অংশ পাঠানো হয়। কে বন্ধ, সে খবর আসে membership থেকে: প্রতিটি node gossip protocol-এ প্রতি সেকেন্ডে কয়েকজনের সাথে তালিকা বিনিময় করে, আর phi accrual failure detector heartbeat-এর দেরি দেখে সন্দেহের মাত্রা দেয় (পর্ব ৪৪)। নিচে একটি লেখা, যখন D বন্ধ:

এবার সব অংশ একসাথে। নিচের mini store-এ পাঁচটি node, প্রতিটির ৮টি virtual node, N = ৩, W = ২, R = ২. Workload: ৩০০টি key-এ ৮,০০০টি অনুরোধ, অর্ধেক put. D বন্ধ থাকে অনুরোধ ২০০০ থেকে ৫৯৯৯ পর্যন্ত, আর তার মাঝে E-ও বন্ধ ৪০০০ থেকে ৫৯৯৯. ফেরার পর gossip-এ খবর ছড়িয়ে hint পৌঁছাতে লাগে ৩০০টি অনুরোধের সময়, যার নাম DETECT. তিনটি নীতি পাশাপাশি — strict quorum, hint ছাড়া sloppy quorum, আর sloppy quorum + hinted handoff:

// Part 4: mini store. 5 nodes, ring (8 vnodes each), N=3, W=2, R=2. D down 2000-5999, E down 4000-5999.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const hash = s => { let h = 0x811c9dc5; for (const ch of s) h = Math.imul(h ^ ch.charCodeAt(0), 0x01000193);
  h = Math.imul(h ^ (h >>> 16), 0x85ebca6b); h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35); return (h ^ (h >>> 16)) >>> 0; };
const NODES = ["A", "B", "C", "D", "E"], N = 3, W = 2, R = 2, OPS = 8000, KEYS = 300, DETECT = 300;
const tokens = NODES.flatMap(n => [...Array(8).keys()].map(v => [hash(n + ":" + v), n])).sort((a, b) => a[0] - b[0]);
const walk = k => { const h = hash("k" + k), out = [];            // distinct nodes clockwise from the key
  for (let i = tokens.findIndex(t => t[0] >= h), j = 0; out.length < 5; j++) {
    const n = tokens[((i < 0 ? 0 : i) + j) % tokens.length][1]; if (!out.includes(n)) out.push(n); } return out; };
const down = { D: [2000, 6000], E: [4000, 6000] }, up = (n, t) => !(down[n] && t >= down[n][0] && t < down[n][1]);
function run(mode) {                                 // "strict", "sloppy, no handoff", "sloppy + hints"
  const rnd = mulberry32(54), has = {}, acked = {}, hints = [];
  NODES.forEach(n => has[n] = {});
  let ok = 0, tries = 0, stale = 0, delivered = 0;
  for (let t = 0; t < OPS; t++) {
    for (const n in down) if (mode === "sloppy + hints" && t === down[n][1] + DETECT)   // gossip says n is back
      for (const h of hints.filter(h => h.to === n && !h.done)) { has[n][h.k] = Math.max(has[n][h.k] || 0, h.v); h.done = true; delivered++; }
    const k = Math.floor(rnd() * KEYS), isPut = rnd() < 0.5, w = walk(k), home = w.slice(0, N);
    const set = mode === "strict" ? home.filter(n => up(n, t)) : w.filter(n => up(n, t)).slice(0, N);
    const pick = set.map(n => [rnd(), n]).sort((a, b) => a[0] - b[0]).map(x => x[1]);   // fastest replies first
    tries++;
    if (isPut) {
      for (const n of set) has[n][k] = t + 1;        // partial writes stay even if the put fails
      if (mode === "sloppy + hints") set.filter(n => !home.includes(n)).forEach((n, i) =>
        hints.push({ to: home.filter(x => !up(x, t))[i], k, v: t + 1 }));
      if (set.length >= W) { ok++; acked[k] = t + 1; }
    } else if (set.length >= R) {
      ok++; if (Math.max(...pick.slice(0, R).map(n => has[n][k] || 0)) < (acked[k] || 0)) stale++;
    }
  }
  console.log(mode.padEnd(19) + `availability ${(100 * ok / tries).toFixed(2)}%  stale reads ${stale}` +
    `  hints stored ${hints.length}  delivered ${delivered}`);
}
["strict", "sloppy, no handoff", "sloppy + hints"].forEach(run);

strict             availability 93.29%  stale reads 0  hints stored 0  delivered 0
sloppy, no handoff availability 100.00%  stale reads 28  hints stored 0  delivered 0
sloppy + hints     availability 100.00%  stale reads 13  hints stored 1847  delivered 1847

সরলীকরণ: বার্তা তাৎক্ষণিক, বিকল্প node hint-এর ডেটাও পড়ায় দেয়, read repair আর anti-entropy নেই, “সবচেয়ে দ্রুত দুটি” মানে এলোমেলো দুটি। আর gossip-এর তালিকা consensus নয় — দুটি node কিছুক্ষণ ভিন্ন তালিকা দেখতে পারে; তাই “কে সচল” দিয়ে শুধু কাকে পাঠাবেন তা ঠিক করুন, ডেটার মালিকানা নয় (পর্ব ৪৪)।

৮ · টুকরো ৬ ও ৭: প্রতিটি node-এর storage আর operations

টুকরো ৬ — LSM storage আর Bloom filter

প্রয়োগ: প্রতিটি node-এ একটি LSM-tree (পর্ব ১৯)। লেখা আগে WAL-এ, তারপর RAM-এর memtable-এ; memtable ভরলে একটি অপরিবর্তনীয়, সাজানো SSTable হয়ে ডিস্কে নামে। পড়া memtable থেকে, তারপর নতুন থেকে পুরোনো SSTable. প্রতিটি SSTable-এর সাথে একটি Bloom filter বলে দেয় “এই key এখানে অবশ্যই নেই”, ফলে বেশিরভাগ ফাইলে ডিস্ক ছুঁতেই হয় না (পর্ব ৪৫)। প্রতি key-এ ১০ bit আর ৭টি hash-এ false-positive হার (১ − e^{−৭/১০})^৭ ≈ ০.৮২% — অংশ ২-এর হিসাবে node-প্রতি ১৫৬ MB.

কেন LSM? প্রতিটি put তিনটি node-এ লেখা, hint আর streaming-ও লেখা; LSM এলোমেলো লেখাকে একটানা লেখায় বদলায়। অপরিবর্তনীয় ফাইল আরও তিনটি কাজ সহজ করে: streaming-এ পুরো ফাইল পাঠানো, Merkle tree-র জন্য স্থির ডেটা, আর সস্তা snapshot. দাম হলো পেছনের compaction — পুরোনো ফাইল মিশিয়ে নতুন ফাইল লেখা, যা ডিস্ক আর CPU খায় আর মাঝে মাঝে p99 বাড়ায়।

টুকরো ৭ — Operations: মাপা, বদলানো আর ফিরিয়ে আনা

কী মাপবেন (পর্ব ৫০)। SLI: সফল get আর put-এর অনুপাত; get আর put-এর আলাদা p99, প্রতিটি consistency level-এ আলাদা করে; নমুনা নিয়ে মাপা stale read-এর হার (যেমন read repair কতবার পুরোনো কপি পেল)। SLO: ৩০ দিনে ৯৯.৯% সফল, আর সেই হিসাবে error budget. পেছনের স্বাস্থ্য: জমা hint-এর সংখ্যা ও বয়স, শেষ সফল repair-এর বয়স, compaction-এর জমা কাজ, ডিস্ক কতটা ভরা, আর node-প্রতি অনুরোধের ভাগ।

Upgrade (পর্ব ৫৩)। Rolling-ভাবে একটি করে node: memtable ডিস্কে নামানো, বন্ধ, নতুন সংস্করণ, চালু, hint পৌঁছানো আর p99 স্বাভাবিক হওয়া পর্যন্ত অপেক্ষা, তারপর পরেরটি — একই preference list-এর দুটি বন্ধ হলে strict quorum ভাঙে। পুরোনো আর নতুন সংস্করণকে একে অপরের বার্তা বুঝতে হবে, তাই format বদলায় পেছনে-সামঞ্জস্য রেখে (পর্ব ১২)।

Backup (পর্ব ৫১)। Replication backup নয় — ভুল মোছা তিন কপিতেই ছড়ায়। SSTable অপরিবর্তনীয় বলে snapshot সস্তা: ফাইলগুলোর hard link নিয়ে অন্য account বা region-এর object storage-এ কপি। কঠিন অংশ: সব node-এর snapshot একই মুহূর্তের নয়, তাই restore-এর পর repair লাগে; আর snapshot-এর পরের লেখার জন্য commit log জমাতে হয়। Restore-এর মহড়া ছাড়া RTO অজানা।

৯ · নিজে বাড়ান — প্রজেক্ট, বিস্তার, ভাঙন আর নিজের মূল্যায়ন

চারটি simulator একটি প্রজেক্টের কঙ্কাল। পছন্দের ভাষায় একটি প্রক্রিয়ার ভেতরে কয়েকটি “node” দিয়ে শুরু করুন, পরে আসল network আর ডিস্কে যান; প্রতিটি ধাপে ব্যর্থতা ঘটিয়ে নিশ্চয়তা যাচাইয়ের একটি পরীক্ষা লিখুন।

প্রজেক্ট চেকলিস্ট

• ধাপ ১: ring + virtual node; key-ভাগের standard deviation আর node যোগে সরানো key মাপা
• ধাপ ২: N টি replica, preference list-এ আলাদা physical node আর আলাদা zone; W আর R গুনে put/get
• ধাপ ৩: vector clock, sibling ফেরত দেওয়া, context দিয়ে put; একটি keyspace-এ LWW, একটিতে PN-Counter
• ধাপ ৪: sloppy quorum, hint queue (আকার আর সময়ের সীমাসহ), read repair, একটি key-পরিসরের Merkle tree তুলনা
• ধাপ ৫: gossip-এ membership, heartbeat counter, phi-এর সীমা; seed node দিয়ে যোগ দেওয়া
• ধাপ ৬: প্রতি node-এ WAL + memtable + SSTable + Bloom filter; crash-এর পর WAL থেকে ফেরত
• ধাপ ৭: metric (সফলতার হার, p99, hint, repair-এর বয়স), একটি node করে upgrade, snapshot থেকে restore-এর মহড়া
• পরীক্ষা: এলোমেলো node বন্ধ, network ভাগ, ধীর বার্তা — প্রতিবার লিখে রাখা “OK” পাওয়া কোনো লেখা হারাল কি না

তিনটি বিস্তার

কী ভাঙতে পারে — আর ১০ গুণ বড় হলে

• Hot key: একটি ভাইরাল key-এর সব অনুরোধ একই তিন node-এ; virtual node এটি ছড়ায় না (প্রশ্ন ২)।
• বড় value বা লম্বা sibling-তালিকা: আকার আর sibling-সংখ্যার সীমা না থাকলে একটি key-ই node-কে ধীর করে।
• ১০ গুণ, ২৪০টি node: সবার সাথে সবার heartbeat O(n²), তাই gossip; repair-এর খরচ ডেটার সাথে বাড়ে, তাই পরিসর ভাগ করে সপ্তাহজুড়ে ছড়ানো।
• একসাথে বিকলতা: একই ভুল config সব node-এ গেলে replication বাঁচায় না; বাঁচায় ধাপে ধাপে config বদল।
• নিরাপত্তা (প্রতিরক্ষা): node-দের মধ্যে mTLS, ডিস্কে encryption, keyspace-প্রতি অনুমতি আর tenant-প্রতি rate limit (পর্ব ৫২, পর্ব ৪৯)।
• খরচ: তিন কপি মানে তিন গুণ ডিস্ক; আবার বানানো যায় এমন cache-ধরনের keyspace-এ N = ২ বা TTL যথেষ্ট।

নিজের মূল্যায়ন — rubric

১০ · AI-এর যুগে — AI-এর লেখা KV store নকশা আর কোড যাচাই

“একটি distributed key-value store নকশা করো আর কোড লেখো” — AI কয়েক সেকেন্ডে ring, replica আর একটি ছোট প্রোগ্রাম দেবে, যা প্রায়ই চলে আর প্রায়ই ভুল। এখানকার ভুল স্বাভাবিক অবস্থায় দেখা দেয় না; দেখা দেয় বিকলতায়, একসাথে হওয়া লেখায় আর node যোগের মুহূর্তে। খুঁজুন:

AI-এর দেওয়া KV store নকশা বা কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• হিসাব নিজে আবার করেছি — বিশেষ করে replica-গুণ আর ব্যস্ততার সীমা; অংশ ২-এর সংখ্যার সাথে মিলিয়েছি
• কোডটি চালিয়েছি, আর ভাগের standard deviation, সরানো key, p99 আর stale read নিজে মেপেছি
• Failure-mode পর্যালোচনা: একটি ও দুটি node বন্ধ, network ভাগ, ধীর replica, node যোগের মাঝপথ, hint holder-এর মৃত্যু
• Consistency-র প্রতিটি দাবি যাচাই করেছি: কোথায় linearizable, কোথায় শুধু eventual; ACID-এর C আর CAP-এর C আলাদা রেখেছি
• Delete, tombstone আর repair-এর সময়সূচি একসাথে পড়েছি; প্রতিটি পণ্যের setting documentation-এ মিলিয়েছি
• প্রতিটি অংশের পেছনে একটি requirement আছে; বাকিগুলো বাদ