Quorum আর leaderless replication — R + W > N, read repair আর hinted handoff

১ · Leader ছাড়া replication — Dynamo-র লক্ষ্য, coordinator আর preference list

পর্ব ২২-এ তিন ধরনের replication দেখেছেন; শেষটি ছিল leaderless replication — যেখানে কোনো একটি কপি লেখার ক্রম ঠিক করে না। সেখানে শুধু ছবিটা ছিল; এই পর্বে তার যন্ত্রপাতি: কয়টি কপিতে লিখলে আর কয়টি থেকে পড়লে নতুন মান পাওয়ার নিশ্চয়তা আসে, কপি বন্ধ থাকলে কী হয়, আর পুরোনো কপি কীভাবে নিজে থেকে ঠিক হয়।

একটি অনুরোধের পথ

প্রতিটি key-কে hash করে একটি ring-এ বসানো হয়, আর ring-এ ঘড়ির কাঁটার দিকে হেঁটে প্রথম N টি ভিন্ন সার্ভার হয় সেই key-এর কপি রাখার তালিকা — preference list (পর্ব ১৬-এ ring, virtual node আর এই তালিকা বানানো দেখেছেন; এখানে আর পুনরাবৃত্তি নয়)। N হলো replication factor. একটি অনুরোধ যে node সামলায়, সে coordinator node — সাধারণত preference list-এর প্রথম সচল node. Dynamo paper দুটি পথ বর্ণনা করে: client একটি সাধারণ load balancer দিয়ে যেকোনো node-এ যায়, আর সেই node দরকার হলে অনুরোধটি coordinator-এর কাছে পাঠায়; অথবা partition চেনে এমন client library সরাসরি coordinator-এ যায় — এক hop কম (পর্ব ২৩-এর request routing).

লেখার সময় coordinator নতুন মানটি একটি সংস্করণ-চিহ্নসহ নিজের কাছে লেখে (সে নিজেও replica), তারপর বাকি replica-দের পাঠায়; মোট W টি ack হলেই client-কে “OK”. পড়ার সময় সে replica-দের জিজ্ঞেস করে, R টি উত্তর এলে সংস্করণ মিলিয়ে সবচেয়ে নতুনটি ফেরত দেয়। Coordinator একটি ভূমিকা, স্থায়ী পদ নয় — একটি মরলে পরের node সেই কাজ নেয়, failover-এর সিদ্ধান্ত লাগে না।

“সবচেয়ে নতুন” চিনতে প্রতিটি মানের সাথে একটি সংস্করণ-চিহ্ন যায়। Dynamo রাখত vector clock — কোন node কতবার এই key বদলেছে, তার তালিকা; Cassandra-ধাঁচের store রাখে প্রতিটি column-এর timestamp. কোনটি কী হারায়, অংশ ৭-এ; vector clock-এর পুরো তত্ত্ব পর্ব ৩৯-এ।

২ · N, W, R আর R + W > N — পড়া কেন নতুন লেখা ছোঁয়

তিনটি সংখ্যাই পুরো নকশা: N — একটি key-এর কয়টি কপি; W — কয়টি replica-র ack পেলে লেখা সফল; R — কয়টি replica-র উত্তর পেলে পড়া শেষ। লেখা আসলে N টির সবাইকেই পাঠানো হয়; W শুধু বলে client কতক্ষণ অপেক্ষা করবে। একইভাবে পড়ার অনুরোধ সাধারণত সবাইকে যায়, আর প্রথম R টি উত্তর এলেই কাজ শেষ। এখানে W আর R গোনা হয় কেবল key-এর নির্ধারিত N টি replica থেকে — এর নাম strict quorum; ব্যতিক্রমটি অংশ ৫-এ।

প্রমাণ (pigeonhole): লেখার দল 𝒲, পড়ার দল ℛ — দুটিই N টি replica-র উপসেট। দুটির মিলন N-এর বেশি হতে পারে না: |𝒲 ∪ ℛ| ≤ N. আবার |𝒲 ∩ ℛ| = |𝒲| + |ℛ| − |𝒲 ∪ ℛ| ≥ W + R − N. R + W > N হলে ডান দিক অন্তত ১, তাই অন্তত একটি সাধারণ replica আছে — এটাই quorum intersection. সেই replica-র কাছে সম্পন্ন লেখাটি আছে (সে ack দিয়েছিল), আর coordinator সংস্করণ মিলিয়ে নতুনটি বাছে — তাই উত্তরে নতুন মান আসে। R + W ≤ N হলে এমন দুটি দল বানানো যায় যাদের মাঝে কেউ নেই; তখন একটি stale read সম্ভব। প্রমাণে চারটি লুকানো শর্ত আছে: দলগুলো নির্ধারিত N টি থেকেই (strict), লেখাটি পড়া শুরুর আগে সম্পন্ন, সংস্করণগুলো তুলনা করা যায়, আর ack দেওয়া replica পরে নতুন মানটি হারায় না। অংশ ৪-এ দেখবেন, বাস্তবে প্রতিটিই কখনো না কখনো ভাঙে।

আরেকটি শর্ত মাঝে মাঝে লাগে: W > N/২ হলে যেকোনো দুটি লেখার দলও মেলে, তাই দুটি লেখা একে অপরকে “দেখে” ক্রম ঠিক করতে পারে। ১৯৭৯ সালের প্রথম দিকের quorum-ভিত্তিক নকশায় এটি থাকত (ভাবনার প্রশ্ন ০১)। Dynamo ইচ্ছা করে এটি বাধ্যতামূলক রাখেনি — W = ১-ও চলে — কারণ একসাথে দুটি লেখা ঠেকানোর বদলে সে দুটিকেই রেখে পরে মেলায় (অংশ ৭)।

সূত্রের ওপর ভরসা না করে সব সম্ভাবনা গুনে দেখা যাক। নিচের প্রোগ্রাম N = ৩ আর N = ৫-এর প্রতিটি (W, R)-এর জন্য সব সম্ভাব্য লেখার দল আর পড়ার দল জোড়া বানিয়ে সবচেয়ে কম মিল (worst-case overlap) বের করে, সাথে কয়টি replica বিকল থাকলেও লেখা বা পড়া চলে:

// Every (W, R) choice for N replicas: how many replicas do a write set and a read set
// share in the WORST case? Checked by brute force over all subsets, not by the formula.
const bits = m => { let c = 0; for (; m; m &= m - 1) c++; return c; };
function subsets(n, k) {                       // all k-element subsets of {0..n-1} as bitmasks
  const out = [];
  for (let m = 0; m < (1 << n); m++) if (bits(m) === k) out.push(m);
  return out;
}
for (const N of [3, 5]) {
  const cols = Array.from({ length: N }, (_, i) => i + 1);
  console.log(`N = ${N}: worst-case overlap of write set and read set (0 = stale read possible)`);
  console.log("        " + cols.map(R => `R=${R} `).join("") + "  write works while");
  const smallest = [];
  for (let W = 1; W <= N; W++) {
    let row = `W=${W}     `;
    for (const R of cols) {
      let min = N;
      for (const w of subsets(N, W)) for (const r of subsets(N, R)) min = Math.min(min, bits(w & r));
      row += `  ${min} `;
      if (min > 0 && W + R === N + 1) smallest.push(`(${W},${R})`);
    }
    console.log(row + `  ${N - W} replicas down`);
  }
  console.log("read OK " + cols.map(R => `  ${N - R} `).join("") + "  <- read works while this many down");
  console.log("smallest always-overlapping (W,R): " + smallest.join(" ") + "\n");
}

N = 3: worst-case overlap of write set and read set (0 = stale read possible)
        R=1 R=2 R=3   write works while
W=1       0   0   1   2 replicas down
W=2       0   1   2   1 replicas down
W=3       1   2   3   0 replicas down
read OK   2   1   0   <- read works while this many down
smallest always-overlapping (W,R): (1,3) (2,2) (3,1)

N = 5: worst-case overlap of write set and read set (0 = stale read possible)
        R=1 R=2 R=3 R=4 R=5   write works while
W=1       0   0   0   0   1   4 replicas down
W=2       0   0   0   1   2   3 replicas down
W=3       0   0   1   2   3   2 replicas down
W=4       0   1   2   3   4   1 replicas down
W=5       1   2   3   4   5   0 replicas down
read OK   4   3   2   1   0   <- read works while this many down
smallest always-overlapping (W,R): (1,5) (2,4) (3,3) (4,2) (5,1)

৩ · ব্যর্থতায় quorum-এর হিসাব আর tail latency

কয়টি node বিকল হলে কী থামে

Strict quorum-এ লেখার জন্য W টি replica-র নাগাল লাগে, তাই লেখা সহ্য করে N − W টি বিকল; পড়া সহ্য করে N − R টি। প্রতিটি replica স্বাধীনভাবে p সম্ভাবনায় সচল ধরলে, লেখা সফল হওয়ার সম্ভাবনা হলো “N টির মধ্যে অন্তত W টি সচল”: Σ_k=W..N C(N, k) p^k (১ − p)^N−k. ধরা যাক p = ০.৯৯:

• N = ৩, W = ২: ৩p²(১ − p) + p³ = ০.০২৯৪০৩ + ০.৯৭০২৯৯ = ০.৯৯৯৭০২ — বিভ্রাটের সম্ভাবনা ০.০০০২৯৮, একটি replica-র ০.০১-এর চেয়ে প্রায় ৩৪ গুণ কম।
• N = ৩, W = ৩: p³ = ০.৯৭০২৯৯ — একটি replica-র চেয়েও খারাপ! সবার ack চাওয়া মানে তিনটির যেকোনোটির ব্যর্থতাই আপনার ব্যর্থতা।
• N = ৫, W = ৩: প্রায় ০.৯৯৯৯৯০ — দুটি বিকল সহ্য করে।

এই হিসাবের বড় অনুমান “স্বাধীন ব্যর্থতা”। একই rack, একই বিদ্যুৎ বা একই ভুল config সব কপিকে একসাথে ফেলে দিলে হিসাব ভেঙে পড়ে (পর্ব ৫-এর correlated failure) — তাই preference list-এ ভিন্ন rack বা zone বাছা হয়। আর network দুই ভাগ হলে ছোট ভাগটি quorum বানাতেই পারে না — strict quorum সেখানে consistency রাখতে availability ছেড়ে দেয়, যা CAP-এর কথা (পর্ব ৪০)।

সবচেয়ে দ্রুত W টি — লেজ কাটার কৌশল

লেখা যায় তিনজনের কাছেই, কিন্তু অপেক্ষা শুধু W টির। মানে latency হলো তিনটি উত্তরের মধ্যে W-তম দ্রুতটির সময় — গণিতে একে order statistic বলে। ধরা যাক প্রতিটি replica স্বাধীনভাবে ৫% সময় ধীর (garbage collection, ডিস্কের ব্যস্ততা, ব্যস্ত প্রতিবেশী)। তাহলে লেখা ধীর হবে তখনই, যখন দ্রুত replica W টির কম:

• W = ১: তিনটিই ধীর — ০.০৫³ = ০.০১২৫%
• W = ২: অন্তত দুটি ধীর — ৩ × ০.০৫² × ০.৯৫ + ০.০৫³ = ০.৭২৫%
• W = ৩: অন্তত একটি ধীর — ১ − ০.৯৫³ = ১৪.২৬%

একক replica-র ৫% ধীরতা W = ২-এ নামে প্রায় সাত ভাগের এক ভাগে, W = ৩-এ ওঠে প্রায় তিন গুণে। এটি পর্ব ৪-এর fan-out-এর উল্টো পিঠ: সবার উত্তর চাইলে সবচেয়ে ধীরটি সময় ঠিক করে, কয়েকটির চাইলে দ্রুতরা। Hedged request একই বুদ্ধি — দেরি হলে আরেকটি replica-কেও জিজ্ঞেস করা। দাম: সব অনুরোধ সব replica-তে যায়, তাই খরচ কম W-তেও কমে না।

নিচের সিমুলেটরে তিনটি replica: R1 আর R2 কাছে আর দ্রুত, R3 একটু ধীর (round trip ২ ms + গড়ে ৪ ms এলোমেলো)। প্রতিটি অনুরোধে ১% সম্ভাবনায় কোনো উত্তর নেই, আর ১% সম্ভাবনায় ৬০ ms-এর একটি বিরতি (যেমন garbage collection). Client লেখা সফল হওয়ার ১ ms পরে পড়ে; লেখাটি একটি replica-তে পৌঁছায় তার round trip-এর অর্ধেক সময়ে। তিন বিন্যাস (W, R) = (১, ১), (২, ২), (৩, ১) — ২০,০০০টি করে লেখা-পড়া, seed নির্দিষ্ট:

// 3 replicas, no leader. A write goes to all 3 and succeeds after W acks. The client reads
// 1 ms after its write succeeded, asking all 3; the read returns after the R fastest replies.
function rng(seed) {                                   // mulberry32: seeded, repeatable
  return () => { 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 REP = [{ base: 1, mean: 1 }, { base: 1, mean: 2 }, { base: 2, mean: 4 }]; // round trip ms
const DOWN = 0.01, PAUSE = 0.01;            // per request: 1% no reply, 1% a 60 ms pause
function call(rand, r) {                    // round-trip time of one request to replica r
  if (rand() < DOWN) return Infinity;
  const t = REP[r].base - REP[r].mean * Math.log(1 - rand());
  return rand() < PAUSE ? t + 60 : t;
}
const pct = (a, p) => a[Math.floor(p / 100 * a.length)].toFixed(1).padStart(6);
const show = (a, fail) => [50, 99, 99.9].map(p => pct(a, p)).join("") + String(fail).padStart(5);
const H = x => ["50", "99", "99.9"].map(p => (x + p).padStart(6)).join("") + " fail";
console.log("(W,R)  " + H("w") + " |" + H("r") + " | stale");
for (const [W, R] of [[1, 1], [2, 2], [3, 1]]) {
  const rand = rng(41), wl = [], rl = []; let wFail = 0, rFail = 0, stale = 0;
  for (let i = 0; i < 20000; i++) {
    const wRtt = [0, 1, 2].map(r => call(rand, r));
    const tw = [...wRtt].sort((a, b) => a - b)[W - 1];      // W-th fastest ack
    if (tw === Infinity) { wFail++; continue; } else wl.push(tw);
    const tr = tw + 1, rRtt = [0, 1, 2].map(r => call(rand, r));
    const got = [0, 1, 2].filter(r => rRtt[r] < Infinity).sort((a, b) => rRtt[a] - rRtt[b]);
    if (got.length < R) { rFail++; continue; }
    rl.push(rRtt[got[R - 1]]);
    // replica r is fresh if the write reached it (half its RTT) before the read did
    if (!got.slice(0, R).some(r => wRtt[r] / 2 <= tr + rRtt[r] / 2)) stale++;
  }
  [wl, rl].forEach(a => a.sort((x, y) => x - y));
  console.log(`(${W},${R})  ${show(wl, wFail)} |${show(rl, rFail)} | ${stale}`);
}

(W,R)     w50   w99 w99.9 fail |   r50   r99 r99.9 fail | stale
(1,1)     1.5   4.0   6.2    0 |   1.5   4.0   5.9    0 | 883
(2,2)     2.6   9.3  22.9    4 |   2.6   9.3  24.2    5 | 0
(3,1)     5.5  63.8  71.6  597 |   1.5   4.0   6.3    0 | 0

৪ · Quorum থাকলেও linearizable নয় — পাঁচটি ফাঁক

Linearizability (পর্ব ৪০) চায়: সব কপি মিলে যেন একটিই কপি, আর একটি লেখা বা পড়া শেষ হওয়ার পরে শুরু হওয়া প্রতিটি পড়া অন্তত সেই মান বা তার চেয়ে নতুন দেখবে। নতুনদের সবচেয়ে সাধারণ ভুল: “R + W > N, তাই strongly consistent.” অংশ ২-এর প্রমাণের চারটি লুকানো শর্ত মনে করুন — বাস্তবে সেগুলো ভাঙার পাঁচটি পরিচিত পথ:

1. চলমান লেখার সাথে পড়া: প্রমাণ শুধু সম্পন্ন লেখার কথা বলে। লেখা চলাকালীন একজন পাঠক নতুন মান, আর তাঁর পরে আসা আরেকজন পুরোনো মান পেতে পারেন — নিচের stepper-এ।
2. ব্যর্থ আংশিক লেখা: লেখাটি একটি replica-তে পৌঁছাল, W টিতে নয়; client পেল “ব্যর্থ”। কিন্তু সেই একটি কপি মুছে ফেলা (rollback) হয় না — পরের পড়ায় কখনো সেটি আসে, কখনো আসে না। “ব্যর্থ” লেখাও টিকে যেতে পারে।
3. একসাথে দুটি লেখা: একই key-তে দুটি লেখা একসাথে এলে কোনটি “পরে”, তা ঠিক করার কেউ নেই। LWW একটিকে নিঃশব্দে ফেলে দেয়, আর ঘড়ির পার্থক্যে আসলে পরেরটিই হারাতে পারে (অংশ ৭)।
4. Sloppy quorum: নির্ধারিত replica-র বদলে অন্য node-এর ack গোনা হলে লেখার দলটি N টির বাইরে চলে যায় — প্রমাণের প্রথম শর্তই ভাঙে (অংশ ৫)।
5. নতুন কপি হারানো: নতুন মান পাওয়া একটি replica-র ডিস্ক নষ্ট, আর তাকে একটি পুরোনো কপি থেকে নতুন করে বানানো হলো — নতুন মানের কপি এখন W টির কম, overlap-এর গ্যারান্টি চুপচাপ উধাও।

ষষ্ঠ ধাপের কৌশলটি তাত্ত্বিকভাবে প্রমাণিত: Attiya, Bar-Noy ও Dolev-এর অ্যালগরিদম (সংক্ষেপে ABD; JACM ১৯৯৫) দেখায়, সংখ্যাগরিষ্ঠ quorum-এ প্রতিটি পড়া ফেরার আগে পাওয়া মান আবার লিখে দিলে একটি একক register-এর পড়া-লেখা linearizable হয় — অর্ধেকের কম node বিকল হলেও। Cassandra-ধাঁচের store-এ QUORUM পড়ায় অমিল পেলে ফেরার আগে মেরামত করা হয় বলে documentation-এ বলা হয়; খুঁটিনাটি সংস্করণভেদে আলাদা। কিন্তু ABD-ও “মান এখনো ৫ থাকলে তবেই নতুন মান লেখা” (compare-and-set), অনন্য username বা সিট বুকিংয়ের মতো কাজ পারে না — সেখানে সবার একমত হওয়া লাগে, অর্থাৎ consensus (পর্ব ৪২)। Cassandra-র “lightweight transaction” এজন্যই ভেতরে Paxos ব্যবহার করে, প্রকাশিত documentation অনুযায়ী।

৫ · Sloppy quorum আর hinted handoff — বন্ধ replica-র লেখা কে রাখে

D বন্ধ থাকলে কী হয়? N = ৩, W = ২-এ B আর C দিয়েই W পূর্ণ, তাই লেখা সফল। কিন্তু তিনটি কপির বদলে এখন দুটি — আরেকটি বিকল হলে durability ঝুঁকিতে। Dynamo-র উত্তর: preference list-এ পরের সুস্থ node (ring-এ D-র পরে E) লেখাটি সাময়িক রাখবে, সাথে একটি নোট — “আসল মালিক D”. এই নোট বা hint নিয়ে লেখা পৌঁছে দেওয়াই hinted handoff. Paper অনুযায়ী E এমন লেখা একটি আলাদা local database-এ রাখে, মাঝে মাঝে দেখে, আর D ফিরেছে জানলে (failure detection, পর্ব ৪৪) তাকে পাঠিয়ে নিজের কপি মুছে ফেলতে পারে।

Strict থেকে sloppy — যখন দুটি বন্ধ

এবার C আর D দুটিই বন্ধ। Strict quorum-এ শুধু B সচল — W = ২ হয় না, লেখা ব্যর্থ। Dynamo এখানে আরেক ধাপ যায়: পড়া আর লেখা হয় preference list-এর “প্রথম N টি সুস্থ node”-এ, যারা ring-এ প্রথম N টি না-ও হতে পারে। তাহলে B, E, F লেখা নেয়, B আর E-র ack-এ W = ২ — লেখা সফল। একে বলে sloppy quorum. লাভ: “সবসময় লেখা নেওয়া” প্রায় সত্যি হয়। দাম: ack দেওয়া দলটি (B, E) আর পরে C, D ফিরে এলে পড়ার দলটি (C, D) মেলে না — R + W > N থাকলেও পুরোনো মান। Sloppy quorum তাই durability-র নিশ্চয়তা দেয় (লেখা কোথাও W টি কপিতে আছে), পড়ার নিশ্চয়তা নয়, যতক্ষণ hint পৌঁছায়নি।

Hint চিরকাল রাখা যায় না। Cassandra-ধাঁচে একটি সময়-সীমা থাকে (লেখার সময়ের default প্রায় ৩ ঘণ্টা; সংস্করণভেদে মিলিয়ে নিন), এর বেশি বন্ধ থাকা node-এর লাগে পুরো মেরামত। Hinted handoff তাই ক্ষণিকের বিকলতার ওষুধ; বাকিটা পরের অংশের anti-entropy-র কাজ।

৬ · Read repair আর anti-entropy — Merkle tree দিয়ে অমিল খোঁজা

Read repair — পড়তে পড়তে মেরামত

পড়ার সময় coordinator কয়েকটি replica-র উত্তর তুলনা করে; কোনোটি পুরোনো পেলে নতুন মানটি তাকে লিখে দেয় — read repair. ধরা যাক D কোনোভাবে v2 পায়নি (hint হারিয়েছে), আর সংস্করণ-চিহ্ন একটি version vector: {B:2} মানে B এই key দুবার বদলেছে।

কিছু ব্যবস্থা bandwidth বাঁচাতে একটি replica-র কাছে পুরো ডেটা আর বাকিদের কাছে শুধু তার hash (digest) চায় (Cassandra-ধাঁচ)। সীমাটি স্পষ্ট: যে key কেউ পড়ে না, সে কখনো ঠিক হয় না — আর সেই ভুল কপিই হয়তো একদিন একমাত্র কপি হবে।

Anti-entropy — পুরো খাতা মেলানো, কিন্তু চালাকি করে

তাই পেছনে চলে আরেকটি প্রক্রিয়া: replica-রা নিয়মিত জোড়ায় জোড়ায় নিজেদের ডেটা তুলনা করে যার যা নেই তা পাঠায় — anti-entropy. সরল পথে প্রতিটি key আর মান পাঠিয়ে তুলনা — কোটি key-তে প্রতি রাউন্ডে বিপুল ডেটা, অথচ সাধারণত অমিল হাতে গোনা কয়েকটি। শুরুর analogy-র তিন ভাইয়ের মতো: আগে মাসের মোট মেলান; মিললে কাজ শেষ। না মিললে দুই সপ্তাহ-জোড়ার মোট, তারপর যে সপ্তাহ মেলেনি তার দিনগুলো।

এই চিন্তার যন্ত্র Merkle tree — Ralph Merkle-এর নামে, ১৯৭০-এর দশকের শেষ দিকে প্রস্তাবিত hash tree. Key-গুলোকে কয়েকটি key range-এ ভাগ করে প্রতিটি পরিসরের ডেটার একটি hash হয় পাতা (leaf); দুটি সন্তানের hash জুড়ে আবার hash করলে বাবা-node; এভাবে ওপরে একটি root. কোনো একটি key বদলালে তার পাতা থেকে root পর্যন্ত পুরো পথের hash বদলায়, বাকি সব একই থাকে। দুটি replica প্রথমে root মেলায়; সমান হলে কাজ শেষ, আলাদা হলে দুই সন্তান মেলায় আর কেবল অমিল সন্তানের নিচে নামে। Dynamo paper অনুযায়ী প্রতিটি node তার রাখা প্রতিটি key range-এর জন্য আলাদা Merkle tree রাখে, আর দুই node একই পরিসরের root মিলিয়ে কাজ শুরু করে। Paper নিজেই একটি দুর্বলতা স্বীকার করে: node যোগ বা বাদ হলে অনেক পরিসর বদলায়, তখন tree নতুন করে হিসাব করতে হয় (পর্ব ১৬-এর স্থির partition কৌশল এই খরচ কমায়)।

নিচে ৬৪টি key, ১৬টি পরিসরে (প্রতিটিতে ৪টি) ভাগ করা — replica A আর B, যাদের মধ্যে মাত্র দুটি key আলাদা (k13 আর k50). Hash হিসেবে FNV-1a 32-bit — সরল, দ্রুত, কিন্তু ক্রিপ্টোগ্রাফিক নয়; শুধু demo-র জন্য। প্রোগ্রাম প্রতিটি স্তরে কোন node-গুলো তুলনা হলো আর কোনগুলো মেলেনি, তা দেখায়:

// Anti-entropy with a Merkle tree: 64 keys in 16 key ranges (4 keys each) on replicas A, B.
// B differs in 2 keys. Hash = FNV-1a 32-bit: simple and NOT cryptographic (demo only).
function fnv1a(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; }
  return h.toString(16).padStart(8, "0");
}
const A = {}; for (let k = 0; k < 64; k++) A["k" + k] = "v" + k;
const B = { ...A, k13: "v13-new", k50: "v50-old" };     // the 2 differing keys
function tree(db) {                       // levels[0] = root ... levels[4] = 16 leaf ranges
  let lvl = [];
  for (let r = 0; r < 16; r++) {
    let s = ""; for (let k = 4 * r; k < 4 * r + 4; k++) s += "k" + k + "=" + db["k" + k] + ";";
    lvl.push(fnv1a(s));
  }
  const levels = [lvl];
  while (lvl.length > 1) {
    lvl = lvl.filter((_, i) => i % 2 === 0).map((h, j) => fnv1a(h + lvl[2 * j + 1]));
    levels.unshift(lvl);
  }
  return levels;
}
const ta = tree(A), tb = tree(B);
let todo = [0], compared = 0;              // node indexes to compare at this level
for (let d = 0; d < ta.length; d++) {
  const diff = todo.filter(i => ta[d][i] !== tb[d][i]);
  compared += todo.length;
  console.log(`level ${d}: compare ${todo.map(i => `#${i} ${ta[d][i]}${ta[d][i] === tb[d][i] ? "=" : "!="}${tb[d][i]}`).join("  ")}`);
  todo = d < ta.length - 1 ? diff.flatMap(i => [2 * i, 2 * i + 1]) : diff;
}
console.log(`ranges to sync: ${todo.join(", ")} (keys ${todo.map(r => `k${4 * r}-k${4 * r + 3}`).join(", ")})`);
console.log(`Merkle: ${compared} hashes compared, ${todo.length * 4} keys sent`);
console.log(`naive : all 64 keys (or all 16 range hashes) compared, every round`);
console.log(`2^20 ranges, 2 bad: Merkle <= ${1 + 2 * 2 * 20} hashes, naive ${2 ** 20} range hashes`);

level 0: compare #0 3ee6e4b3!=ae5fdcf5
level 1: compare #0 ad75a2cb!=37eae559  #1 096a11fe!=2bc2f0d9
level 2: compare #0 cb53b94e!=f9e9d40f  #1 0ff8ff83=0ff8ff83  #2 a8948b84=a8948b84  #3 3752ebc0!=97cbd77c
level 3: compare #0 08d173c5=08d173c5  #1 30e1c49c!=aaecabdb  #6 8c845ded!=9a619492  #7 1893b2c6=1893b2c6
level 4: compare #2 a69e1fb7=a69e1fb7  #3 43e42c3d!=2c01ac70  #12 5ce96101!=c2f4e959  #13 cc843f3d=cc843f3d
ranges to sync: 3, 12 (keys k12-k15, k48-k51)
Merkle: 15 hashes compared, 8 keys sent
naive : all 64 keys (or all 16 range hashes) compared, every round
2^20 ranges, 2 bad: Merkle <= 81 hashes, naive 1048576 range hashes

৭ · একসাথে হওয়া লেখা আর delete — version vector, sibling আর tombstone

Leaderless-এ দুজন ব্যবহারকারী (বা একজনের দুটি ফোন) একই key-তে প্রায় একসাথে লিখলে দুটি coordinator দুটি লেখা ছড়ায়, আর replica-রা সেগুলো ভিন্ন ক্রমে পায়। শেষে সব কপিকে একই মানে পৌঁছাতে হবে — কোনটিতে? দুটি প্রচলিত উত্তর:

Dynamo-তে এই চক্রটি API-তেই বাঁধা: get(key) একটি মান বা কয়েকটি sibling ফেরত দেয়, সাথে একটি context (তাদের vector clock). অ্যাপ sibling মিলিয়ে (cart-এর ক্ষেত্রে union) put(key, context, value) করলে নতুন লেখাটির vector সব পুরোনোকে ঢেকে দেয়, আর sibling মিলিয়ে যায়। Vector অসীম না বাড়াতে paper একটি সীমা (উদাহরণে ১০টি জোড়া) পেরোলে সবচেয়ে পুরোনো জোড়া ফেলে দেয় — তাত্ত্বিকভাবে ঝুঁকিপূর্ণ, তবে paper-এর ভাষ্যে বাস্তবে সমস্যা দেখা যায়নি। Vector clock আর version vector-এর সূক্ষ্ম পার্থক্য পর্ব ৩৯-এ; sibling না রেখেই নিজে থেকে মিলে যায় এমন data type (CRDT) পর্ব ৪৬-এ। পর্ব ২২-এর multi-leader demo-তে একই নিয়ম চালিয়ে দেখেছেন।

Delete — মৃত ডেটা কেন জেগে ওঠে

Leaderless store-এ delete মানে মান সরিয়ে ফেলা নয়; একটি বিশেষ লেখা — tombstone, “এই key মৃত” চিহ্ন (পর্ব ১৯-এর LSM-tree-এ দেখেছেন)। কেন? ধরুন B আর C থেকে মানটি সোজা মুছে দেওয়া হলো, কিন্তু D তখন বন্ধ ছিল। পরে anti-entropy দেখবে: “D-র কাছে আছে, B আর C-র কাছে নেই” — আর কাউকে মুছতে না বলে D-র কপি ফিরিয়ে আনবে! Tombstone থাকলে তুলনায় বোঝা যায় মুছে ফেলাটাই নতুন খবর। কিন্তু tombstone চিরকাল রাখলে ডিস্ক ভরে, তাই একটি grace সময় পরে compaction তাদের ফেলে দেয় — Cassandra-ধাঁচে লেখার সময়ের default প্রায় ১০ দিন। নিয়মটি তাই কড়া: প্রতিটি replica-তে পুরো মেরামত (anti-entropy) grace সময়ের চেয়ে ঘন ঘন চালাতে হবে; নইলে grace পেরোনোর পর ফেরা একটি পুরোনো replica মুছে ফেলা ডেটা আবার ছড়িয়ে দিতে পারে।

৮ · Tunable consistency — প্রতিটি অনুরোধে ONE, QUORUM না ALL

N স্থির থাকে টেবিল বা bucket-এর জন্য, কিন্তু W আর R অনেক ব্যবস্থায় প্রতিটি অনুরোধে বলে দেওয়া যায় — tunable consistency (পর্ব ২০-এ প্রথম দেখেছেন)। Cassandra-ধাঁচের store-এ এর নাম consistency level; documentation-এ প্রচলিত কয়েকটি (তালিকা আর অর্থ সংস্করণভেদে মিলিয়ে নিন):

একটি হিসাবের ফাঁদ: দুটি ডেটা সেন্টারে RF ৩ করে মোট ৬টি কপি। QUORUM = ⌊৬ ÷ ২⌋ + ১ = ৪ — অর্থাৎ প্রতিটি অনুরোধে অন্য ডেটা সেন্টারের অন্তত একটি replica-র অপেক্ষা, আর দূরের সংযোগ বিচ্ছিন্ন হলে লেখা থামে। LOCAL_QUORUM = ২, শুধু নিজের ৩টির মধ্যে; দ্রুত আর স্থানীয়, কিন্তু দুই ডেটা সেন্টারের লেখার মধ্যে overlap-এর নিশ্চয়তা নেই। Riak-ধাঁচে প্রতিটি অনুরোধে r, w-এর সাথে primary replica-র ack বাধ্য করার বিকল্প (pr, pw) থাকে বলে documentation-এ বলা হয়।

একটি কাল্পনিক ride-sharing অ্যাপে একই store-এ ডেটাভেদে আলাদা পছন্দ:

৯ · AI-এর যুগে quorum-নকশা যাচাই

“একটি highly available key-value store নকশা করো” লিখলে AI প্রায় সবসময় বলে: “Cassandra নিন, QUORUM দিন, strong consistency পাবেন, সাথে Kafka আর Redis.” শুনতে পেশাদার; কিন্তু quorum-এর আলোচনায় AI কয়েকটি ভুল প্রায় নিয়ম করে করে:

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

• N, W, R থেকে overlap (W + R − N) আর বিকলতার সহনশীলতা (N − W, N − R) নিজে হিসাব করেছি, অংশ ২-এর প্রোগ্রামে মিলিয়েছি
• Availability আর tail latency-র সম্ভাবনা সূত্রে নিজে হিসাব করেছি; স্বাধীন ব্যর্থতার অনুমান কোথায় ভাঙে (একই rack, zone, config) লিখেছি
• Failure-mode পর্যালোচনা করেছি: চলমান লেখা, ব্যর্থ আংশিক লেখা, sloppy quorum, একসাথে দুটি লেখা, হারানো কপি, ফিরে আসা মুছে ফেলা ডেটা
• কোন কাজে quorum যথেষ্ট নয় (অনন্যতা, compare-and-set) চিহ্নিত করে সেখানে consensus বা single-leader রেখেছি
• প্রতিটি setting আর default documentation-এ মিলিয়েছি; সম্ভব হলে অংশ ৩-এর মতো ছোট সিমুলেশন বা load test-এ stale read মেপেছি