CAP, PACELC আর consistency model — linearizable থেকে eventual

১ · “সর্বশেষ মান” বলতে আসলে কী বোঝায় — register, history আর একটি চুক্তি

পর্ব ২২-এ (Replication) দেখেছেন, একই ডেটার কয়েকটি কপি রাখলে কপিগুলো কিছুক্ষণ আলাদা থাকে। এই পর্বের প্রশ্ন আরও মৌলিক: কপিগুলো আলাদা থাকার সময়ে একটি পড়া কোন কোন মান ফেরত দিলে আমরা সেটিকে “ঠিক” বলব? উত্তর দিতে তিনটি শব্দ লাগবে।

• Register: সবচেয়ে সরল ডেটা — একটি ঘর, যেখানে একটি মান থাকে। দুটি কাজ: w(v) মানে মান v লেখা, r→v মানে পড়ে v পাওয়া। একটি key-value store-এর প্রতিটি key একেকটি register.
• কাজের সময়-পরিসর: network-এর কারণে কোনো কাজ এক মুহূর্তে ঘটে না। Client অনুরোধ পাঠায় (শুরু), কিছু পরে উত্তর পায় (শেষ)। মাঝের সময়ে কাজটি “চলছে” — client জানে না ঠিক কখন সার্ভারে প্রয়োগ হলো। দুটি কাজের পরিসর একটি আরেকটির ওপর পড়লে তারা একসাথে চলা (concurrent); একটি শেষ হওয়ার পর আরেকটি শুরু হলে প্রথমটি আগে।
• History: সব client-এর সব কাজের তালিকা, শুরু আর শেষের সময়সহ। এই পর্বে লিখব A: w(1) [0, 10] — client A মান 1 লিখল, অনুরোধ ০ ms-এ গেল, উত্তর এল ১০ ms-এ।

একটি consistency model আসলে একটি চুক্তি: কোন history বৈধ আর কোনটি নয়। চুক্তি যত কড়া, প্রোগ্রামারের জীবন তত সহজ — “একটিই কপি আছে” ভেবে কোড লেখা যায়। কিন্তু কড়া চুক্তি রাখতে কপিগুলোকে বেশি কথা বলতে হয়: তাতে সময় লাগে, আর network ভাঙলে কিছু অনুরোধ ফেরাতে হয়। CAP theorem এই দর-কষাকষির সবচেয়ে বিখ্যাত রূপ।

২ · CAP theorem নিখুঁতভাবে — Brewer-এর অনুমান আর Gilbert–Lynch-এর প্রমাণ

২০০০ সালে PODC সম্মেলনের মূল বক্তৃতায় Eric Brewer অনুমান (conjecture) দেন: ডেটা ভাগ করে রাখা একটি web সেবা একসাথে consistency, availability আর partition tolerance দিতে পারে না। ২০০২ সালে Seth Gilbert আর Nancy Lynch অনুমানটি নির্দিষ্ট সংজ্ঞায় বেঁধে প্রমাণ করেন। প্রমাণটি সত্য কেবল সেই সংজ্ঞাগুলোর ভেতরে, তাই সংজ্ঞাগুলো হুবহু জানা দরকার:

• C — consistency: প্রমাণে এর নাম atomic consistency, আজকের ভাষায় linearizability. প্রতিটি কাজ যেন তার শুরু আর শেষের মাঝের এক মুহূর্তে ঘটেছে, আর সব কাজ মিলে এমন একটি ক্রম আছে যা বাস্তব সময় মানে। ফল: একটি লেখা শেষ হওয়ার পর শুরু হওয়া প্রতিটি পড়া সেই লেখা (বা নতুনতর কিছু) দেখবে, যে কপি থেকেই পড়ুক।
• A — availability: চালু থাকা প্রতিটি node-এ আসা প্রতিটি অনুরোধ শেষ পর্যন্ত একটি উত্তর পাবে — error নয়, আসল উত্তর। সংজ্ঞায় সময়সীমা নেই, কিন্তু “অনন্তকাল অপেক্ষা” মানে উত্তর নেই।
• P — partition tolerance: network যত খুশি বার্তা হারাতে পারে — দুই দলের মাঝের সব বার্তাও। তবুও সিস্টেমকে C আর A-র প্রতিশ্রুতি রাখতে হবে। দলে ভাগ হওয়ার ঘটনাটিই network partition.

প্রমাণের যুক্তি — পাঁচ লাইনে

1. Node-গুলো দুটি দলে ভাগ হলো: G1 আর G2; মাঝের সব বার্তা হারায়। Register-এর শুরুর মান v0.
2. একজন client G1-এ w(v1) পাঠালেন। A বলে G1-কে উত্তর দিতেই হবে, G2-র খবর ছাড়াই; লেখা শেষ হলো।
3. তারপর আরেকজন client G2-তে পড়ার অনুরোধ পাঠালেন। A বলে G2-কেও উত্তর দিতে হবে।
4. G2 কোনো বার্তা পায়নি। তার চোখে এই ঘটনা আর “কেউ কিছু লেখেনি” ঘটনা হুবহু এক — দুটিকে আলাদা করার কোনো তথ্য তার কাছে নেই। তাই সে v0 ফেরত দেয়।
5. লেখা শেষ হওয়ার পরে শুরু হওয়া পড়া পুরোনো v0 পেল — linearizability ভাঙল। অতএব তিনটি একসাথে অসম্ভব।

যুক্তির প্রাণ চতুর্থ লাইন: যে তথ্য পৌঁছায়নি, কোনো algorithm তা জানতে পারে না। প্রমাণটি asynchronous network-এর মডেলে — ঘড়ি নেই, বার্তার দেরির সীমা নেই; সেখানে বার্তা হারিয়েছে না শুধু দেরি করছে, node তা বুঝতেই পারে না — পর্ব ৩৮-এর partial failure-এর মূল কথা এটিই।

DBMS কোর্সের Distributed database পর্বে দুই শহরের দুটি replica দিয়ে এর প্রথম পরিচয় আছে। এখানে বাস্তবের কাছাকাছি একটি ছবি: ৫টি replica, আর CP মোডে নিয়ম “৫টির অন্তত ৩টি (সংখ্যাগরিষ্ঠ) রাজি হলে তবেই কাজ” — Raft-ধাঁচের ব্যবস্থার মতো (পর্ব ৪২)। Network কেটে দুই দলে ভাগ হলো: N1–N3 আর N4–N5.

লক্ষ করুন, CP মোডেও সংখ্যাগরিষ্ঠের দিক পুরোদমে চলেছে। যেকোনো দুটি সংখ্যাগরিষ্ঠ দল (৫টির ৩টি করে) অন্তত একটি node-এ মেলে, তাই দুই দিকে পরস্পরবিরোধী দুটি সিদ্ধান্ত অসম্ভব — split-brain ঠেকে যায়। এটিই quorum (পর্ব ৪১) আর consensus-এর (পর্ব ৪২) ভিত্তি।

৩ · CAP-এর পাঁচটি ভুল ব্যাখ্যা — “তিনের দুই”, “CA ব্যবস্থা” আর আরও

CAP সম্ভবত distributed systems-এর সবচেয়ে বেশি ভুল বোঝা কথা। পাঁচটি ভুল বারবার দেখা যায়:

1. “তিনটির যেকোনো দুটি বেছে নিন।” একাধিক যন্ত্র network-এ যুক্ত থাকলে partition ঘটবে কি না, তা আপনার পছন্দ নয় — switch নষ্ট হয়, তার কাটে, ভুল config আসে। P বাদ দেওয়া মানে “partition-এ কী হবে, ঠিক করিনি”। Brewer নিজেই ২০১২ সালের “CAP Twelve Years Later” প্রবন্ধে “তিনের দুই”-কে বিভ্রান্তিকর বলেছেন।
2. “আমাদের ব্যবস্থা CA.” এক যন্ত্রের database-এ কথাটির মানে আছে, সেখানে partition নেই। কিন্তু তিন node-এর cluster-কে “CA” বললে আসল মানে: partition-এ আচরণ অনির্ধারিত — প্রায়ই দুটিই যায়, যেমন দুই দিকে দুই leader.
3. “CP মানে availability কম।” CAP-এর A কড়া — প্রতিটি চালু node-এর উত্তর; পর্ব ৫-এর availability (কত ভাগ অনুরোধ সফল) আলাদা মাপ। Client-রা সংখ্যাগরিষ্ঠের দিকে পৌঁছাতে পারলে CP ব্যবস্থার মাপা availability খুব উঁচু হয়; আবার “AP” ব্যবস্থাও bug বা overload-এ পুরো বন্ধ হতে পারে।
4. “Partition একটি বিরল, স্পষ্ট ঘটনা।” একটি node-এর চোখে partition আর একটি খুব ধীর node দেখতে হুবহু এক — উত্তর আসছে না। তাই CAP-এর বাছাই আসলে ঘটে প্রতিটি timeout-এ: আরও অপেক্ষা করব (C রক্ষা, A-র ঝুঁকি), নাকি হাতে যা আছে তা দিয়েই উত্তর দেব (A রক্ষা, C-র ঝুঁকি)? একটি GC-বিরতি বা ভিড়ে আটকে থাকা লিংকও “partition”. কে মৃত আর কে শুধু ধীর, অনুমানের কাজটি failure detector-এর — পর্ব ৪৪-এর membership আর failure detection পর্বে।
5. “পুরো সিস্টেম হয় CP, নয় AP.” বাছাই হয় প্রতিটি কাজে — একই অ্যাপে টাকা কাটা CP, like AP; একই database-এ লেখা linearizable কিন্তু follower থেকে পড়া পুরোনো। আর AP মানেই “শুধু eventual” নয় — partition-এও causal পর্যন্ত দেওয়া যায় (অংশ ৫)।

এবার সিমুলেটরে দুই মোডের দাম মাপা যাক। পাঁচটি replica; partition চলাকালীন ১,০০০টি অনুরোধ — অর্ধেক লেখা, অর্ধেক পড়া, ২০০টি key আর পাঁচটি node-এর যেকোনোটিতে সমান সম্ভাবনায়। ধরা যাক প্রতিটি client কেবল নিজের দিকের node-এর নাগাল পান। CP মোডে সংখ্যালঘু দিকের সব অনুরোধ ফেরত যায়; AP মোডে দুই দিকই নিজের মতো লেখা নেয়। বিভাজন দুটি: ৩|২ আর ৪|১; seed একই, তাই দুই মোডে হুবহু একই অনুরোধ।

// 5 replicas; a partition cuts off the last m of them. 1,000 requests arrive during it.
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 KEYS = 200, REQ = 1000;
console.log("split  mode  answered  rejected  avail.   stale reads  conflicting keys");
for (const m of [2, 1]) {                              // minority size: 3|2 split, then 4|1
  for (const mode of ["CP", "AP"]) {
    const rand = rng(41);                              // same workload for both modes
    const ver = [Array(KEYS).fill(0), Array(KEYS).fill(0)]; // [majority, minority] versions
    let ok = 0, rej = 0, stale = 0;
    for (let i = 0; i < REQ; i++) {
      const side = Math.floor(rand() * 5) >= 5 - m ? 1 : 0;  // 1 = minority side
      const key = Math.floor(rand() * KEYS), write = rand() < 0.5;
      if (mode === "CP" && side === 1) { rej++; continue; } // no majority: refuse
      ok++;
      if (write) ver[side][key]++;                     // each side keeps its own history
      else if (ver[side][key] < ver[1 - side][key]) stale++; // a newer write exists elsewhere
    }
    let conflicts = 0;                                 // after heal: both sides changed key
    for (let k = 0; k < KEYS; k++) if (ver[0][k] > 0 && ver[1][k] > 0) conflicts++;
    console.log(`${5 - m}|${m}`.padEnd(7) + mode.padEnd(6) + String(ok).padEnd(10) +
      String(rej).padEnd(10) + (100 * ok / REQ).toFixed(1).padStart(5) + "%   " +
      String(stale).padEnd(13) + conflicts + " of " + KEYS);
  }
}

split  mode  answered  rejected  avail.   stale reads  conflicting keys
3|2    CP    584       416        58.4%   0            0 of 200
3|2    AP    1000      0         100.0%   144          105 of 200
4|1    CP    792       208        79.2%   0            0 of 200
4|1    AP    1000      0         100.0%   86           80 of 200

৪ · PACELC — network ঠিক থাকলেও latency বনাম consistency

CAP শুধু partition-এর মুহূর্তের কথা বলে, অথচ বছরের বেশিরভাগ সময় network ঠিকই থাকে। তখন কি কোনো বাছাই নেই? Daniel Abadi ২০১২ সালের একটি প্রবন্ধে বিষয়টি একটি নামে গুছিয়ে দেন — PACELC: Partition হলে A না C; Else, অর্থাৎ স্বাভাবিক সময়ে, Latency না Consistency.

কেন স্বাভাবিক সময়েও বাছাই? Linearizable পড়া দিতে হলে store-কে নিশ্চিত হতে হয় যে তার কাছের কপিটিই সর্বশেষ — তার মানে leader বা সংখ্যাগরিষ্ঠের সাথে অন্তত একবার কথা বলা। সেই round trip-এর দাম আলোর গতি ঠিক করে, কোনো optimization নয়। একটি হিসাব — ধরা যাক: তিনটি region X, Y, Z-এ একটি করে replica; RTT X–Y ৩০ ms, Y–Z ৬০ ms, X–Z ৮০ ms; কাছের replica থেকে পড়ায় ১ ms; ব্যবহারকারীদের ৫০% X-এর কাছে, ৩০% Y-এর, ২০% Z-এর। সরল মডেলে linearizable পড়া মানে নিজের replica আর সবচেয়ে কাছের আরেকটি replica-র সম্মতি (৩টির ২টি):

একটি পাতায় পরপর ৫টি এমন পড়া হলে ৫ ms-এর জায়গায় ১৮৫ ms. সংখ্যাগরিষ্ঠের ধীরতম সদস্যের অপেক্ষায় tail latency (পর্ব ৪) আরও বাড়ে। এক ডেটা সেন্টারেও একই দর-কষাকষি ছোট আকারে আছে — পর্ব ২২-এর উদাহরণে sync commit ৬২ ms, async ১ ms.

৫ · Consistency model-এর সিঁড়ি — linearizable থেকে eventual

“Strong” আর “eventual” — এই দুই প্রান্তের মাঝে অনেকগুলো ধাপ, আর প্রতিটি ধাপ নির্দিষ্ট কিছু anomaly অনুমোদন করে, কিছু নিষেধ করে। নিচের ছবিতে ওপরেরটি কড়া; তীর মানে “ওপরেরটি মানলে নিচেরটিও আপনিই মানা হয়”।

Linearizability — এক কপির ভ্রম

Maurice Herlihy আর Jeannette Wing-এর ১৯৯০ সালের সংজ্ঞা। Client-এর চোখে মনে হবে ডেটার একটিই কপি, আর প্রতিটি কাজ শুরু ও শেষের মাঝে এক মুহূর্তে ঘটেছে। দুটি শর্ত: (ক) সব কাজ মিলে একটি ক্রম, যেখানে প্রতিটি পড়া ঠিক আগের লেখাটি দেখে; (খ) একটি কাজ আরেকটির শুরুর আগে শেষ হলে ক্রমেও সে আগে। দ্বিতীয় শর্তটিই “বাস্তব সময়” — ফোনে কেউ বললেন “আমি দেখেছি”, আপনি পরে দেখলে আপনিও দেখবেন। পুরোনো লেখায় একে strong consistency বলা হয়, যদিও বিভিন্ন পণ্যের documentation “strong” শব্দটি আলাদা অর্থে ব্যবহার করে।

Sequential consistency — এক ক্রম, কিন্তু ঘড়ি নয়

Leslie Lamport ১৯৭৯ সালে multiprocessor-এর memory-র জন্য সংজ্ঞাটি দেন: সব কাজ একটি একক ক্রমে সাজানো যায়, যেখানে প্রতিটি client-এর নিজের কাজের ক্রম ঠিক থাকে — কিন্তু সেই ক্রম বাস্তব সময়ের আগে-পরে মানবে, এমন কথা নেই। Sequential consistency-তে সবাই একই গল্প দেখেন, শুধু গল্পটি ঘড়ির সাথে না-ও মিলতে পারে। অংশ ৬-এ দেখবেন একটি history যা sequential, অথচ linearizable নয়।

Causal consistency — কারণ আগে, ফল পরে

দুটি লেখা happens-before সম্পর্কে যুক্ত হলে — একজন একটি পোস্ট পড়ে তার উত্তর লিখলেন, বা একই client পরপর দুটি লিখলেন — causal consistency-তে সবাই সেগুলো একই ক্রমে দেখবেন: প্রশ্নের আগে উত্তর কখনো নয়। কিন্তু সম্পর্কহীন দুটি লেখা — দুই শহরে দুজন একই সময়ে দুটি আলাদা পোস্ট — একেকজন একেক ক্রমে দেখতে পারেন। কারণ-ফল ধরে রাখতে প্রতিটি লেখার সাথে “কোনগুলো দেখে লিখেছি” তথ্য যায়, প্রায়ই vector clock বা dependency-তালিকা হিসেবে (পর্ব ৩৯-এর সময় আর ক্রম)। Ahamad ও সহকর্মীরা ১৯৯০-এর দশকে causal memory-র আনুষ্ঠানিক সংজ্ঞা দেন।

Session guarantee আর eventual consistency

আরও নিচে চারটি ছোট প্রতিশ্রুতি, প্রতিটি একজন client-এর নিজের অভিজ্ঞতা ঘিরে — session guarantees, অংশ ৭-এ। আর সবার নিচে eventual consistency: নতুন লেখা থামলে একসময় সব কপি একই মানে পৌঁছাবে। কখন, তার সীমা নেই; মাঝে কোন মান বা কোন ক্রম দেখা যাবে, কিছুই বলা নেই। নামটি জনপ্রিয় করেন Werner Vogels তাঁর ২০০৮ সালের “Eventually Consistent” লেখায়, যদিও ধারণাটি ১৯৯০-এর দশকের replication-গবেষণাতেই ছিল। এটি liveness প্রতিশ্রুতি (“শেষে ভালো কিছু ঘটবে”), safety নয় (“খারাপ কিছু ঘটবে না”) — তাই বাস্তবে এর সাথে প্রায় সবসময় session guarantee জুড়ে দেওয়া হয়।

Eventual-এর একটি কড়া রূপ আছে: strong eventual consistency — যে দুটি কপি একই পরিবর্তনগুলো পেয়েছে, ক্রম যা-ই হোক, তারা তখনই হুবহু এক। “শেষ পর্যন্ত” আর অস্পষ্ট থাকে না, আর conflict মেটানোর জন্য আলাদা কেউ লাগে না। CRDT ঠিক এটি দেয় — পর্ব ৪৬-এর Conflict resolution আর CRDT পর্বে দেখবেন।

৬ · Linearizability কাছ থেকে — linearization point, একটি checker আর তার দাম

একটি history linearizable কি না, যাচাইয়ের একটি সহজ উপায় আছে: প্রতিটি কাজের শুরু আর শেষের মাঝে একটি বিন্দু বেছে নিন — সেই মুহূর্তে কাজটি “একবারে ঘটে গেল” — যাতে বিন্দুগুলোর ক্রমে প্রতিটি পড়া ঠিক আগের লেখাটি দেখে। এই বিন্দুর নাম linearization point. এমন বিন্দু বাছা গেলে history linearizable; কোনোভাবেই না গেলে নয়। একটি কাল্পনিক বোর্ড পরীক্ষার ফল প্রকাশের ঘটনা দিয়ে দেখা যাক।

নিচের checker সব সম্ভাব্য ক্রম চেষ্টা করে দুটি প্রশ্ন করে — linearizable (বাস্তব সময় মেনে) আর sequential (শুধু প্রতি client-এর ক্রম মেনে) — আর পেলে একটি সাক্ষী-ক্রম (witness) ছাপে। H1 আর H2 উপরের দুটি ঘটনা; H3-এ একজন client নিজে 1 লিখে তারপর 0 পড়লেন।

// Brute-force checker for one register (initial value 0).
// Each operation: [client, "w" or "r", value, start, end] in ms.
const H = {
  H1: [["A", "w", 1, 0, 10], ["B", "r", 0, 2, 4], ["C", "r", 1, 6, 8]],
  H2: [["A", "w", 1, 0, 10], ["B", "r", 1, 2, 4], ["C", "r", 0, 6, 8]],
  H3: [["A", "w", 1, 0, 2], ["A", "r", 0, 3, 5]],
};
const perms = a => a.length < 2 ? [a] :
  a.flatMap((x, i) => perms([...a.slice(0, i), ...a.slice(i + 1)]).map(p => [x, ...p]));
function legal(order) {                    // every read returns the latest write before it
  let v = 0;
  for (const [, kind, val] of order) {
    if (kind === "w") v = val; else if (val !== v) return false;
  }
  return true;
}
function keeps(order, mustPrecede) {       // no pair appears in a forbidden order
  for (let i = 0; i < order.length; i++)
    for (let j = i + 1; j < order.length; j++)
      if (mustPrecede(order[j], order[i])) return false;
  return true;
}
const realTime = (a, b) => a[4] < b[3];                     // a ended before b started
const show = o => o.map(([c, k, v]) => `${c}:${k}(${v})`).join(" -> ");
for (const [name, h] of Object.entries(H)) {
  const sameClient = (a, b) => a[0] === b[0] && h.indexOf(a) < h.indexOf(b);
  const lin = perms(h).find(p => legal(p) && keeps(p, realTime));
  const seq = perms(h).find(p => legal(p) && keeps(p, sameClient));
  console.log(name + ": " + (lin ? "LINEARIZABLE      " + show(lin) : "NOT LINEARIZABLE"));
  console.log("    " + (seq ? "SEQUENTIAL        " + show(seq) : "NOT SEQUENTIAL"));
}

H1: LINEARIZABLE      B:r(0) -> A:w(1) -> C:r(1)
    SEQUENTIAL        B:r(0) -> A:w(1) -> C:r(1)
H2: NOT LINEARIZABLE
    SEQUENTIAL        C:r(0) -> A:w(1) -> B:r(1)
H3: NOT LINEARIZABLE
    NOT SEQUENTIAL

Linearizability-র দাম

এই নিশ্চয়তা বিনা মূল্যে আসে না। তিনটি দাম:

• Partition-এ সংখ্যালঘু দিক থামে — অংশ ২-এর প্রমাণ।
• প্রতিটি কাজে সমন্বয়ের latency — অংশ ৪-এর হিসাব। Leader-ভিত্তিক ব্যবস্থায় লেখা সংখ্যাগরিষ্ঠের log-এ না যাওয়া পর্যন্ত “OK” নয়, আর পড়ার আগেও leader-কে নিশ্চিত হতে হয় সে এখনো leader (Raft-এর read index বা lease, পর্ব ৪২ আর পর্ব ৪৩)। নইলে network-এ আলাদা হয়ে পড়া পুরোনো leader পুরোনো মান দেবে। Hagit Attiya আর Jennifer Welch ১৯৯৪ সালে দেখান, linearizable পড়া আর লেখাকে একসাথে network-এর বার্তা-দেরির চেয়ে দ্রুত করা যায় না, অথচ sequential consistency-তে অন্তত একটি ধরন, যেমন পড়া, স্থানীয়ভাবে করা যায়।
• “R + W > N” নিজে যথেষ্ট নয়। Quorum-এর ওভারল্যাপ নতুন মান খুঁজে পেতে সাহায্য করে, কিন্তু একসাথে চলা লেখা, last-write-wins আর ঘড়ির পার্থক্য থাকলে history তবুও linearizable না-ও হতে পারে — পর্ব ৪১-এ দেখবেন কী বাড়তি লাগে।

বিনিময়ে একটি দুর্লভ সুবিধা: Herlihy ও Wing দেখান linearizability “local” — প্রতিটি object আলাদাভাবে linearizable হলে পুরো ব্যবস্থাও linearizable. Sequential consistency-র এই গুণ নেই, তাই টুকরো জুড়ে বড় সিস্টেম বানাতে linearizability নিরাপদ ভিত্তি।

৭ · Session guarantee — একজন ব্যবহারকারীর চোখে চারটি প্রতিশ্রুতি

পর্ব ২২-এ (Replication, অংশ ৪) replication lag-এর তিনটি anomaly আর প্রতিকার দেখেছেন: read-your-writes (সময়-জানালা, LSN মিলিয়ে route), monotonic reads (এক replica-তে বাঁধা) আর consistent prefix. সেখানকার কৌশল এখানে আবার বলব না। এখানে প্রশ্ন: এগুলো সিঁড়ির কোথায় বসে, আর পুরো পরিবারটি কী?

Xerox PARC-এর Bayou প্রকল্পে Douglas Terry ও সহকর্মীরা ১৯৯৪ সালে চারটি session guarantee-র নাম দেন। প্রতিটি একটি session-এর (একজন ব্যবহারকারী বা একটি অ্যাপ-instance) পড়া-লেখার ক্রম ঘিরে; অন্য client-দের ব্যাপারে কোনো কথা নেই:

চারটি একসাথে, আর session-গুলোর মাঝে কারণ-ফল ছড়ালে, পাওয়া যায় causal-এর কাছাকাছি — তাই ছবি ৪০.১-এ এরা causal-এর নিচে। বাস্তবায়নের মূল যন্ত্র session token: client নিজের দেখা ও লেখা সর্বোচ্চ অবস্থান (version, LSN বা version vector) প্রতিটি অনুরোধে পাঠায়; replica সেখানে না পৌঁছালে অপেক্ষা করে বা এগিয়ে থাকা কপিতে পাঠায়। একই replica-তে বেঁধে রাখা (sticky session) সহজতর, কিন্তু replica মরলে বা ব্যবহারকারী অন্য ডিভাইসে গেলে নিশ্চয়তা হারায়।

কতবার কোন নিশ্চয়তা ভাঙে, একটি সিমুলেটরে গোনা যাক। একটি register, দুটি replica: লেখা যায় A-তে (leader), B সেই লেখা ২০–৯৯ ms পরে প্রয়োগ করে। তিনজন client (c1, c2, c3) প্রতি ১০ ms-এ একটি করে কাজ করেন — ৪০% লেখা, বাকিটা পড়া, A বা B থেকে সমান সম্ভাবনায়। প্রতিটি পড়ায় তিনটি প্রশ্ন: linearizable store হলে আরও নতুন মান আসত কি (LIN)? নিজের শেষ লেখার চেয়ে পুরোনো কি (RYW)? নিজের আগের পড়ার চেয়ে পুরোনো কি (MR)? এখানে লেখা A-তে তাৎক্ষণিক, তাই “পড়া শুরুর আগে শেষ হওয়া সর্বশেষ লেখা” ঠিক করে বলা যায়।

// One register, two replicas. Writes go to A; B applies each write 20-99 ms later.
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 rand = rng(40);
const W = [{ v: 0, tA: -1, tB: -1 }];                  // version 0 = initial value
const lastW = {}, lastR = {}, bad = { LIN: 0, RYW: 0, MR: 0 };
let reads = 0;
console.log("t    client  op       replica  got  newest  broken");
for (let t = 0; t < 400; t += 10) {                    // one operation every 10 ms
  const c = "c" + (1 + Math.floor(rand() * 3));
  if (rand() < 0.4) {                                   // write: new version on A at time t
    const v = W.length;
    W.push({ v, tA: t, tB: t + 20 + Math.floor(rand() * 80) });
    lastW[c] = v; continue;
  }
  const rep = rand() < 0.5 ? "A" : "B";
  const seen = w => (rep === "A" ? w.tA : w.tB) <= t;  // has this replica applied w?
  const got = W.filter(seen).pop().v;                  // value the replica returns
  const newest = W.filter(w => w.tA < t).pop().v;     // latest write finished before read
  const broken = [];
  if (got < newest) broken.push("LIN");                // a linearizable store returns newest
  if (got < (lastW[c] ?? 0)) broken.push("RYW");       // older than my own write
  if (got < (lastR[c] ?? 0)) broken.push("MR");        // older than what I read before
  lastR[c] = Math.max(lastR[c] ?? 0, got); reads++;
  broken.forEach(b => bad[b]++);
  if (broken.length) console.log(String(t).padEnd(5) + c.padEnd(8) + "read".padEnd(9) +
    rep.padEnd(9) + ("v" + got).padEnd(5) + ("v" + newest).padEnd(8) + broken.join(","));
}
console.log(`reads=${reads}  LIN broken=${bad.LIN}  RYW broken=${bad.RYW}  MR broken=${bad.MR}`);

t    client  op       replica  got  newest  broken
60   c3      read     B        v2   v4      LIN,RYW,MR
100  c3      read     B        v4   v5      LIN
110  c1      read     B        v4   v5      LIN,MR
130  c3      read     B        v4   v5      LIN,MR
200  c2      read     B        v7   v9      LIN
210  c2      read     B        v7   v9      LIN
230  c3      read     B        v7   v10     LIN,RYW
250  c3      read     B        v9   v11     LIN,RYW
280  c1      read     B        v11  v12     LIN,RYW
300  c2      read     B        v11  v13     LIN,RYW
320  c1      read     B        v12  v13     LIN
360  c1      read     B        v12  v14     LIN
reads=23  LIN broken=12  RYW broken=5  MR broken=3

৮ · Consistency বনাম isolation, আর কোন feature-এ কোন model

পর্ব ২৪-এ (Transaction আর isolation level) isolation level-এর সিঁড়ি দেখেছেন। দুটি সিঁড়ি দেখতে একরকম, কিন্তু প্রশ্ন আলাদা। Isolation জিজ্ঞেস করে: একসাথে চলা কয়েকটি transaction, যারা কয়েকটি সারি ছোঁয়, একে অপরের মাঝপথের কাজ কতটা দেখবে? Consistency model জিজ্ঞেস করে: একটি object-এর কয়েকটি কপি থেকে পড়া কতটা হালনাগাদ আর কোন ক্রমে?

দুটির পার্থক্যের বিস্তারিত উদাহরণ পর্ব ২৪-এর ভাবনার প্রশ্ন ৩-এ; Spanner (২০১২) দুটি একসাথে দেয় আর একে external consistency বলে।

কোন feature-এ কোন model — একটি কাল্পনিক super-app ধরে

টাকা পাঠানো, কেনাকাটা, চ্যাট আর feed — সব একটি অ্যাপে। সবখানে এক model মানে হয় সবখানে বেশি দাম, নয়তো টাকার জায়গায় ঝুঁকি। প্রতিটি feature-এর জন্য তিনটি প্রশ্ন: কোন ভুলে ক্ষতি (টাকা, আইন, আস্থা)? Partition-এ “পরে চেষ্টা করুন” ভালো, না “হয়তো পুরোনো”? স্বাভাবিক দিনে latency-র বাজেট কত?

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

“highly available আর consistent একটি ব্যবস্থার নকশা চাই” লিখলে AI প্রায়ই উত্তর দেয়: “CAP-এর তিনটির দুটি বাছতে হয়, আমরা AP নেব, Cassandra আর Kafka দিয়ে।” কথাগুলো পেশাদার শোনায়, কিন্তু এই বিষয়ে AI-এর ভুল বেশ নিয়মিত:

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

• প্রতিটি “consistent” শব্দের পাশে model-এর নাম আছে, আর ACID বনাম CAP অর্থ আলাদা করা হয়েছে
• প্রতিটি feature-এর জন্য partition-এর আচরণ (প্রত্যাখ্যান বনাম পুরোনো উত্তর) লেখা আছে, আর ব্যবহারকারীর বার্তাও
• RTT থেকে স্বাভাবিক সময়ের বাড়তি latency নিজে হিসাব করেছি (PACELC-এর E)
• Failure-mode পর্যালোচনা করেছি: পুরোনো leader, ঘড়ির পার্থক্য, LWW-এ হারানো লেখা, partition জোড়া লাগার পর মেলানো
• প্রতিটি পণ্যের দাবি documentation-এ মিলিয়েছি; সম্ভব হলে একটি ছোট simulation বা history-checker চালিয়েছি