Conflict resolution আর CRDT — last-write-wins থেকে convergent data type

১ · Conflict কোথা থেকে আসে — চারটি উৎস

একটি পরিবারের বাজারের ফর্দ ভাবুন, যা একটি কাল্পনিক অ্যাপে সবার ফোনে আছে। মা ফেরিঘাটে, নেটওয়ার্ক নেই; ফর্দে “ডিম” যোগ করলেন। একই সময়ে বাবা অফিসের ল্যাপটপে যোগ করলেন “চাল”। ঘণ্টাখানেক পরে মায়ের ফোন নেটওয়ার্ক পেল। এখন ফর্দে কী থাকবে? এখানে উত্তর সহজ — দুটিই। কিন্তু যদি মা “চিনি” কেটে দেন আর বাবা একই সময়ে চিনির পরিমাণ “২ কেজি” করেন? তখন দুই কপির মধ্যে একটি write conflict, আর কোনো একটি নিয়মে সব কপিকে একই উত্তরে আনতে হবে — conflict resolution.

এখানে “একসাথে” মানে ঘড়ির একই মুহূর্ত নয়। দুটি লেখা concurrent, যদি কোনোটির লেখক অন্যটির খবর না জেনে লিখে থাকেন — মাঝে দশ মিনিট বা দশ ঘণ্টা থাকলেও। আনুষ্ঠানিক সংজ্ঞাটি Lamport-এর happens-before সম্পর্ক; সেটি আর তা ধরার vector clock পর্ব ৩৯-এর বিষয়, এখানে আমরা ব্যবহার করব। Conflict চারটি জায়গা থেকে আসে:

চারটির কাঠামো একই: কয়েকটি replica বিচ্ছিন্ন অবস্থায় আলাদা বদল নেয় (diverge), যোগাযোগ ফিরলে মেলে (converge). নিচে সবচেয়ে সরল রূপ:

২ · প্রথম কৌশল: conflict এড়ানো — প্রতিটি key-এর একটি “বাড়ি”

সবচেয়ে ভালো conflict হলো যেটি কখনো ঘটে না। Conflict avoidance-এর ধারণা সরল: multi-leader সিস্টেমেও প্রতিটি key-এর একটি “বাড়ির” region বা replica ঠিক করে দিন, আর সেই key-এর সব লেখা সেখানেই পাঠান। ধরা যাক একটি কাল্পনিক ride-sharing অ্যাপের প্রতিটি ব্যবহারকারীর প্রোফাইল তাঁর নিবন্ধনের দেশের region-এ “বাস” করে। ঢাকার ব্যবহারকারীর প্রোফাইলের লেখা সবসময় ঢাকার কাছের region-এ; অন্য region-গুলো শুধু কপি পড়ে। প্রতিটি রেকর্ডের কার্যত একটিই leader — single-leader-এর নিরাপত্তা, কিন্তু region ভাগ করে।

এটি অনেক ক্ষেত্রেই যথেষ্ট — ব্যবহারকারীর নিজের ডেটা, একটি দোকানের মালামাল, একটি chat-এর বার্তা (পর্ব ৫৫)। কিন্তু চারটি জায়গায় ভাঙে:

• বাড়ি বিকল হলে: লেখা অন্য region-এ সরাতে হয়; পুরোনো বাড়ির না-পৌঁছানো লেখাগুলো ফিরে এলে নতুন বাড়ির লেখার সাথে conflict.
• বাড়ি বদলালে: ব্যবহারকারী দেশ বদলালেন বা নতুন region খুলল — সরানোর মুহূর্তে দুই জায়গাতেই লেখা যেতে পারে।
• ভাগ করা ডেটায়: group document বা ভাগ করা ফর্দের একক “মালিক” নেই; সব লেখা এক জায়গায় গেলে দূরের সদস্যের latency বাড়ে।
• Offline ফোনে: নেটওয়ার্কই নেই, “বাড়িতে” পাঠানোর প্রশ্নই ওঠে না।

এড়ানো না গেলে মেলানোর পথগুলো এক নজরে — প্রতিটি নিচের অংশগুলোতে বিস্তারিত:

৩ · Last-write-wins — সহজ মিল, নিঃশব্দ ক্ষতি

Last-write-wins (LWW)-এ প্রতিটি লেখার সাথে একটি timestamp যায়; দুটি সংস্করণ মুখোমুখি হলে বড় timestamp-এরটি টিকে থাকে, সমান হলে replica-র নাম দিয়ে নিষ্পত্তি। নিয়মটি নির্ধারিত, ক্রমের ওপর নির্ভর করে না, তাই সব কপি একই মানে মেলে — convergence নিশ্চিত। Apache Cassandra প্রতিটি column-এর মানের জন্য এভাবেই LWW ব্যবহার করে বলে তার documentation-এ বলা আছে। পর্ব ২২-এর demo-তে দেখেছেন, দুটি concurrent লেখার একটি LWW নিঃশব্দে ফেলে দেয়। এখানে আরও অস্বস্তিকর একটি সত্য মাপব: ঘড়ি ভুল হলে concurrent নয়, পরপর লেখাও হারায়।

দুটি replica, A আর B. B-র ঘড়ির ভুল (clock skew) seed দিয়ে এলোমেলো বাছা; replication-এ ১০০ ms লাগে। একটি key-তে ছয়টি সম্পাদনা, প্রতিটি আগেরটির ৬০ থেকে ৪০০ ms পরে, এলোমেলো replica-তে। প্রতিটি সম্পাদনা আগেরটি দেখে লেখা কি না (“saw-prev”) আর sync-এর পর সবাই কোন মান দেখছে, দুটিই ছাপা হবে; পাশে Lamport clock-এর হিসাব (পর্ব ৩৯): যা দেখেছে তার চেয়ে এক বড় সংখ্যা।

// LWW on two replicas: B's clock is off by a seeded amount. Which "later" edit is lost?
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 rand = mulberry32(46);
const skewB = Math.round((rand() - 0.5) * 1200);     // B's clock error: -600..+600 ms
const delay = 100;                                    // replication delay A <-> B (ms)
const writes = []; let real = 0;
for (let i = 1; i <= 6; i++) {
  real += Math.round(60 + rand() * 340);              // next edit 60..400 ms later
  const at = rand() < 0.5 ? "A" : "B";
  const seen = writes.filter(w => w.at === at || real - w.real >= delay); // already arrived
  const lam = 1 + Math.max(0, ...seen.map(w => w.lam)); // Lamport: beat everything seen
  writes.push({ id: "w" + i, at, real, ts: real + (at === "B" ? skewB : 0), lam,
                sawPrev: i === 1 ? "-" : seen.some(w => w.id === "w" + (i - 1)) ? "yes" : "no" });
}
const pick = (key, list) => list.reduce((a, b) =>
  (b[key] > a[key] || (b[key] === a[key] && b.at > a.at)) ? b : a);
console.log(`B clock skew ${skewB} ms, replication delay ${delay} ms`);
console.log("edit at  real  wall-stamp  lamport  saw-prev  value after sync (wall LWW)");
writes.forEach((w, i) => console.log(`${w.id}   ${w.at}  ${String(w.real).padStart(4)}  ` +
  `${String(w.ts).padStart(10)}  ${String(w.lam).padStart(7)}  ${w.sawPrev.padEnd(8)}  ` +
  pick("ts", writes.slice(0, i + 1)).id));
for (const [name, key] of [["wall-clock LWW", "ts"], ["Lamport LWW", "lam"]]) {
  const win = pick(key, writes);
  const lost = writes.filter(w => w.real > win.real).map(w => w.id);
  console.log(`${name}: final value from ${win.id}; later-in-real-time edits lost: ` +
    (lost.length ? lost.join(", ") : "none"));
}
const shown = new Set(writes.map((w, i) => pick("ts", writes.slice(0, i + 1)).id));
console.log("edits never shown after sync (wall LWW): " +
  writes.filter(w => !shown.has(w.id)).map(w => w.id).join(", "));

B clock skew -528 ms, replication delay 100 ms
edit at  real  wall-stamp  lamport  saw-prev  value after sync (wall LWW)
w1   A   371         371        1  -         w1
w2   A   701         701        2  yes       w2
w3   B   854         326        3  yes       w2
w4   B   916         388        4  yes       w2
w5   A  1229        1229        5  yes       w5
w6   B  1356         828        6  yes       w5
wall-clock LWW: final value from w5; later-in-real-time edits lost: w6
Lamport LWW: final value from w6; later-in-real-time edits lost: none
edits never shown after sync (wall LWW): w3, w4, w6

তাহলে LWW কি বাতিল? না — কোথায় নিরাপদ, সেটি জানা দরকার: (১) যে key একবারই লেখা হয় (key একটি UUID হলে concurrent লেখা কার্যত হয় না); (২) cache আর আনুমানিক মান, যেমন “ড্রাইভারের শেষ অবস্থান”, যার পরের update কয়েক সেকেন্ডেই আসছে; (৩) হারালেও ক্ষতি নেই এমন সেটিং, যেমন theme-এর রং। কিন্তু টাকা, গণনা, তালিকা বা ব্যবহারকারীর লেখায় LWW-এর হারানোটা একটি bug.

৪ · Siblings রেখে পড়ার সময় মেলানো — Dynamo-র shopping cart

LWW-এর উল্টো দর্শন: database কোনো সিদ্ধান্ত নেবে না, শুধু চিনবে কোন সংস্করণগুলো concurrent, আর সবগুলোই রেখে দেবে। এই একসাথে টিকে থাকা সংস্করণগুলোর নাম siblings. চেনার যন্ত্র version vector — প্রতিটি replica-র জন্য একটি counter; একটি vector অন্যটির প্রতিটি ঘরে সমান বা বড় হলে সেটি “নতুন” আর পুরোনোটি ফেলা যায়, নইলে দুটি concurrent (তুলনার নিয়ম পর্ব ৩৯-এ, leaderless store-এ siblings কীভাবে জন্মায় পর্ব ৪১-এ)। পড়ার সময় client সব sibling আর একটি মেলানো vector পায়; অ্যাপ সেগুলো মিলিয়ে একটি নতুন সংস্করণ লেখে, আর সেই vector সব sibling-কে ঢেকে দেয় বলে তারা মুছে যায়।

কেন ফিরে আসে, ধাপে ধাপে দেখুন। কার্টে দুধ আর চিনি; ফোন আর ল্যাপটপ দুটি আলাদা replica-র সাথে কথা বলছে, আর মাঝের network ভাগ হয়ে গেছে।

একই গল্প কোডে — version vector-এর তুলনা, union আর tombstone-এর ফল নিজে মিলিয়ে দেখুন:

// Dynamo-style shopping cart: concurrent versions kept as siblings, merged by union.
const covers = (a, b) => Object.keys(b).every(r => (a[r] || 0) >= b[r]);   // a has seen b?
const relation = (a, b) => covers(a, b) && covers(b, a) ? "equal" :
  covers(a, b) ? "first is newer" : covers(b, a) ? "second is newer" : "concurrent";
const bump = (vv, r) => ({ ...vv, [r]: (vv[r] || 0) + 1 });
const vmax = (a, b) => { const o = { ...a }; for (const r in b) o[r] = Math.max(o[r] || 0, b[r]); return o; };
const fmt = v => `[${v.items.join(", ")}] ${JSON.stringify(v.vv)}`;

let base = { items: ["milk", "sugar"], vv: { A: 1 } };          // both replicas start here
// Network split. Phone talks to replica A, laptop talks to replica B.
const onA = { items: base.items.filter(x => x !== "sugar"), vv: bump(base.vv, "A") };
const onB = { items: [...base.items, "rice"], vv: bump(base.vv, "B") };
console.log("replica A (phone removed sugar):", fmt(onA));
console.log("replica B (laptop added rice):  ", fmt(onB));
console.log("compare version vectors:", relation(onA.vv, onB.vv), "-> keep both as siblings");

// Read returns both siblings; the app merges them by union, then writes the result.
const union = [...new Set([...onA.items, ...onB.items])];
const merged = { items: union, vv: bump(vmax(onA.vv, onB.vv), "A") };
console.log("union merge:", fmt(merged));
console.log("deleted item back?", merged.items.includes("sugar") ? "YES, sugar reappeared" : "no");
console.log("merged vs siblings:", relation(merged.vv, onA.vv) + ",", relation(merged.vv, onB.vv));

// Fix attempt: carry a 'removed' list (tombstones) with each version.
onA.removed = ["sugar"]; onB.removed = [];
const removed = new Set([...onA.removed, ...onB.removed]);
console.log("union minus tombstones:", JSON.stringify(union.filter(x => !removed.has(x))));
console.log("user adds sugar again later:", JSON.stringify([...union, "sugar"]
  .filter((x, i, arr) => arr.indexOf(x) === i && !removed.has(x))), "(blocked by the tombstone)");

replica A (phone removed sugar): [milk] {"A":2}
replica B (laptop added rice):   [milk, sugar, rice] {"A":1,"B":1}
compare version vectors: concurrent -> keep both as siblings
union merge: [milk, sugar, rice] {"A":3,"B":1}
deleted item back? YES, sugar reappeared
merged vs siblings: first is newer, first is newer
union minus tombstones: ["milk","rice"]
user adds sugar again later: ["milk","rice"] (blocked by the tombstone)

নিজের merge function — লেখার সময়, না পড়ার সময়

Siblings-এর ভালো দিক হলো মেলানোর সিদ্ধান্ত যায় সেই জায়গায়, যে ডেটার অর্থ জানে — অ্যাপ। একটি merge function দুই জায়গায় চলতে পারে:

• পড়ার সময়: Database siblings ফেরত দেয়, অ্যাপ মেলায় বা ব্যবহারকারীকে বাছতে দেয়। Riak-এর মতো Dynamo-ধাঁচের store-এ siblings রাখার setting আছে বলে documentation-এ পাওয়া যায়; Apache CouchDB সব conflicting revision রেখে একটি নির্ধারিত “বিজয়ী” দেখায়, অ্যাপ চাইলে বাকিগুলো এনে মেটায়।
• লেখার সময়: Replica conflict দেখামাত্র অ্যাপের দেওয়া কোড চালায়। ঐতিহাসিক উদাহরণ Xerox PARC-এর Bayou (Terry ও সহকর্মীরা, SOSP ১৯৯৫): প্রতিটি লেখার সাথে একটি “dependency check” আর একটি “merge procedure” — যেমন সভাকক্ষের চাওয়া সময় দখল হলে তালিকার পরের বিকল্প সময় নেওয়া।

৫ · Strong eventual consistency আর CRDT-র গণিত

Eventual consistency শুধু বলে: লেখা থামলে শেষ পর্যন্ত সব কপি মিলবে — কবে, কোন নিয়মে, মাঝে কী হারাবে, তা বলে না। CRDT (conflict-free replicated data type) একটি কড়া নিশ্চয়তা দেয়, যার নাম strong eventual consistency (SEC): যে দুটি replica একই পরিবর্তনগুলো পেয়েছে, তারা যে ক্রমেই পাক, তখনই একই অবস্থায় — কোনো আলাদা মেটানোর ধাপ, কোনো sibling, কোনো coordination ছাড়াই। খেয়াল করুন, এটি CAP-এর C (linearizability) নয়: দুটি replica তখনো আলাদা জিনিস দেখাতে পারে, যদি তারা এখনো আলাদা পরিবর্তন পেয়ে থাকে।

State-based CRDT — অবস্থা পাঠান, join করুন

State-based CRDT (CvRDT)-এ প্রতিটি replica মাঝে মাঝে নিজের পুরো অবস্থা অন্যদের পাঠায়, আর গ্রহীতা নিজের অবস্থার সাথে একটি merge করে। শর্ত তিনটি:

• Commutative: merge(a, b) = merge(b, a) — কে কার কাছে আগে পাঠাল, তাতে কিছু যায় আসে না।
• Associative: merge(merge(a, b), c) = merge(a, merge(b, c)) — কোন পথে gossip ঘুরল, তাতে কিছু যায় আসে না (পর্ব ৪৪)।
• Idempotent: merge(a, a) = a — একই অবস্থা দুবার এলে ক্ষতি নেই; network-এর duplicate বা retry নিরাপদ (idempotency, পর্ব ৩৪)।

সঙ্গে একটি চতুর্থ শর্ত: প্রতিটি local update অবস্থাকে শুধু “ওপরে” তোলে, কখনো নামায় না। গণিতের ভাষায় অবস্থাগুলো একটি join-semilattice: একটি আংশিক ক্রম (যেমন “সেট A, সেট B-র উপসেট”), যেখানে যেকোনো দুটি অবস্থার একটি সবচেয়ে ছোট ঊর্ধ্বসীমা আছে — join, আর merge ঠিক সেটিই। সেটের জন্য join মানে union, সংখ্যার জন্য max.

Operation-based CRDT — কাজ পাঠান, কিন্তু ক্রম মেনে

Operation-based CRDT (CmRDT)-এ পুরো অবস্থা নয়, শুধু কাজটি যায়: “+১”, “চাল যোগ, tag b2”. বার্তা ছোট, কিন্তু network-এর কাছে দাবি বেশি। Concurrent কাজগুলোকে commute করতে হয় (+৩ আর +২ যেকোনো ক্রমে ৫)। আর প্রতিটি কাজ প্রতিটি replica-তে ঠিক একবার পৌঁছাতে হয় — “+১” দুবার এলে গণনা ভুল — এবং প্রায়ই কারণ-ফলের ক্রমে (causal delivery). উদাহরণ: replica C-তে “tag a1 মুছুন” যদি “দুধ যোগ, tag a1”-এর আগে পৌঁছায়, C তখন মোছার মতো কিছু পায় না; পরে যোগ এলে দুধ C-তে থেকে যায় চিরকাল, অথচ অন্য সবখানে নেই। তাই CmRDT সাধারণত একটি নির্ভরযোগ্য causal broadcast স্তরের ওপর বসে, যা vector clock দেখে বার্তা আটকে রাখে যতক্ষণ না তার কারণ-বার্তা আসে। ধারণাটি পর্ব ৩৫-এর event log-এর কাছাকাছি; পার্থক্য, সেখানে সাধারণত একটি মোট ক্রম, এখানে শুধু কারণ-ফলের আংশিক ক্রম।

দুইয়ের মাঝামাঝি delta-state CRDT (Almeida, Shoker ও Baquero-র ২০১৫ সালের দিকের কাজ): শুধু সাম্প্রতিক বদলের ছোট অংশ পাঠানো হয়, যা নিজেও একটি অবস্থা, তাই একই join দিয়ে জোড়া যায়।

৬ · Counter CRDT — G-Counter আর PN-Counter

একটি অনলাইন ক্লাসে কতজন যোগ দিলেন, তিনটি region-এর তিনটি replica গুনছে। সরল দুই উপায়ই ভাঙে। মান বসানো (“count = 42”) আসলে একটি register, LWW-তে একসাথে আসা বাড়ানো হারায়। “+১” বার্তা পাঠানো CmRDT হিসেবে চলে, কিন্তু at-least-once delivery-তে retry হলে একই “+১” দুবার গোনা হয়। G-Counter-এর কৌশল: প্রতিটি replica-র জন্য একটি আলাদা ঘর। Replica শুধু নিজের ঘর বাড়ায়; মান = সব ঘরের যোগফল; merge = ঘরে ঘরে বড় মানটি (element-wise max). একই replica-র ঘর শুধু বাড়ে, তাই বড়টিই সবচেয়ে নতুন।

কমানোও চাই? PN-Counter দুটি G-Counter রাখে: P-তে সব বাড়ানো, N-এ সব কমানো; মান = P-র যোগফল − N-এর যোগফল। দুটিই শুধু বাড়ে, তাই merge আগের মতোই ঘরে ঘরে max. নিচের সিমুলেটরে তিনটি replica offline অবস্থায় যোগ দেওয়া (+১) আর বেরিয়ে যাওয়া (−১) গোনে; তারপর চারবার এলোমেলো gossip-ক্রমে মেলে, আর সরল দুটি নিয়মের সাথে তুলনা:

// G-Counter and PN-Counter on 3 replicas: merge in any order, any number of times.
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 rand = mulberry32(46), R = ["A", "B", "C"];
const gMerge = (x, y) => { const o = { ...x };                  // element-wise max
  for (const r in y) o[r] = Math.max(o[r] || 0, y[r]); return o; };
const gVal = g => Object.values(g).reduce((s, v) => s + v, 0);
const pnMerge = (x, y) => ({ P: gMerge(x.P, y.P), N: gMerge(x.N, y.N) });
const pnVal = s => gVal(s.P) - gVal(s.N);
const same = (x, y) => R.every(r => (x.P[r] || 0) === (y.P[r] || 0) && (x.N[r] || 0) === (y.N[r] || 0));
// Offline, each replica counts people joining (+1) and leaving (-1) a live class
const st = {}; let trueTotal = 0;
for (const r of R) {
  st[r] = { P: {}, N: {} };
  for (let i = 0; i < 12; i++) {
    const k = rand() < 0.7 ? "P" : "N"; st[r][k][r] = (st[r][k][r] || 0) + 1;
    trueTotal += k === "P" ? 1 : -1;
  }
  console.log(`${r}: joins ${st[r].P[r] || 0}, leaves ${st[r].N[r] || 0}, local value ${pnVal(st[r])}`);
}
console.log("true total:", trueTotal);
for (let trial = 1; trial <= 4; trial++) {                      // random gossip orders
  const c = { ...st }, log = [];
  while (!(same(c.A, c.B) && same(c.B, c.C))) {
    const f = Math.floor(rand() * 3), from = R[f], to = R[(f + 1 + Math.floor(rand() * 2)) % 3];
    c[to] = pnMerge(c[to], c[from]); log.push(from + ">" + to);  // "to" pulls from "from"
  }
  console.log(`gossip ${log.join(" ")}: A=${pnVal(c.A)} B=${pnVal(c.B)} C=${pnVal(c.C)}, G=${gVal(c.A.P)}`);
}
const all = pnMerge(pnMerge(st.A, st.B), st.C), again = pnMerge(pnMerge(all, st.B), all); // re-deliver
console.log("merge the same states again:", pnVal(again), "(idempotent)");
const naiveSum = pnVal(st.A) + pnVal(st.B) + pnVal(st.C);
console.log("naive 'add totals' merge, once:", naiveSum, "| B delivered twice:", naiveSum + pnVal(st.B));
console.log("naive 'max of totals' merge:", Math.max(...R.map(r => pnVal(st[r]))));

A: joins 8, leaves 4, local value 4
B: joins 9, leaves 3, local value 6
C: joins 10, leaves 2, local value 8
true total: 18
gossip C>B A>C C>B B>C C>B B>A: A=18 B=18 C=18, G=27
gossip A>C B>A C>B B>C A>C B>C A>B B>A: A=18 B=18 C=18, G=27
gossip A>C C>A C>A B>A C>A B>A B>A B>C C>B: A=18 B=18 C=18, G=27
gossip C>A B>C A>B A>C C>A: A=18 B=18 C=18, G=27
merge the same states again: 18 (idempotent)
naive 'add totals' merge, once: 18 | B delivered twice: 24
naive 'max of totals' merge: 8

৭ · Set, register আর OR-Set — add-wins-এর কৌশল

Counter-এর পরে সবচেয়ে কাজের CRDT হলো set আর register. সবচেয়ে সরল G-Set: শুধু যোগ, merge = union — ছবি ৪৬.১ ঠিক এটাই। মোছা চাইলে 2P-Set: একটি যোগের G-Set আর একটি মোছার G-Set (tombstone); জিনিস আছে যদি যোগে থাকে কিন্তু মোছায় না থাকে। অংশ ৪-এর tombstone-প্রতিকার এটাই — মোছা জেতে, মোছা জিনিস আর ফেরে না: কার্টে অচল, “নিষিদ্ধ ID-র তালিকা”-য় ঠিক যা দরকার।

OR-Set (observed-remove set) দুটি সমস্যাই সমাধান করে। কৌশল: প্রতিটি যোগ একটি অনন্য tag পায় (replica-র নাম + একটি ক্রমিক সংখ্যা)। মোছা সেই মুহূর্তে যে tag-গুলো দেখা যাচ্ছে শুধু সেগুলোকে tombstone করে। জিনিস আছে, যদি তার অন্তত একটি tag tombstone-এর বাইরে থাকে। Merge = tag-গুলোর union আর tombstone-এর union. একসাথে এক জায়গায় মোছা আর অন্য জায়গায় নতুন যোগ হলে নতুন যোগের tag মোছার সময় কেউ দেখেনি, তাই সেটি টিকে যায় — add-wins.

একই ঘটনা দুইভাবে: একটি সরল set, যা কাজগুলো আসার ক্রমে প্রয়োগ করে, আর OR-Set:

// Same item, concurrent remove (replica A) and add (replica B): naive set vs OR-Set.
// 1) Naive set: each replica applies operations in the order they arrive.
const naive = (ops) => { const s = new Set(["milk"]);
  for (const [op, x] of ops) op === "add" ? s.add(x) : s.delete(x); return [...s]; };
const opA = ["remove", "milk"], opB = ["add", "milk"];
console.log("naive A (own remove, then B's add):", JSON.stringify(naive([opA, opB])));
console.log("naive B (own add, then A's remove):", JSON.stringify(naive([opB, opA])));

// 2) OR-Set: every add gets a unique tag; remove deletes only the tags it has seen.
const orNew = () => ({ adds: {}, removed: new Set() });
let seq = 0;
const orAdd = (s, x, rep) => { (s.adds[x] ||= new Set()).add(rep + ++seq); };
const orRemove = (s, x) => { for (const t of s.adds[x] || []) s.removed.add(t); };
const orHas = (s, x) => [...(s.adds[x] || [])].some(t => !s.removed.has(t));
const orMerge = (a, b) => { const m = orNew();
  for (const s of [a, b]) {
    for (const x in s.adds) for (const t of s.adds[x]) (m.adds[x] ||= new Set()).add(t);
    for (const t of s.removed) m.removed.add(t);
  } return m; };
const show = s => Object.keys(s.adds).map(x => `${x}{${[...s.adds[x]].join(",")}}`).join(" ") +
  ` removed{${[...s.removed].join(",")}} -> milk ${orHas(s, "milk") ? "present" : "absent"}`;

let A = orNew(); orAdd(A, "milk", "a");                // milk added once, tag a1
let B = orMerge(A, orNew());                           // B has synced: same state
orRemove(A, "milk");                                   // A removes the milk it has seen (a1)
orAdd(B, "milk", "b");                                 // meanwhile B adds milk again (b2)
console.log("OR-Set A before sync:", show(A));
console.log("OR-Set B before sync:", show(B));
console.log("OR-Set A after  sync:", show(orMerge(A, B)));
console.log("OR-Set B after  sync:", show(orMerge(B, A)));
A = orMerge(A, B); orRemove(A, "milk");                // a remove that HAS seen b2
console.log("A removes again, then sync:", show(orMerge(orMerge(A, B), A)));

naive A (own remove, then B's add): ["milk"]
naive B (own add, then A's remove): []
OR-Set A before sync: milk{a1} removed{a1} -> milk absent
OR-Set B before sync: milk{a1,b2} removed{} -> milk present
OR-Set A after  sync: milk{a1,b2} removed{a1} -> milk present
OR-Set B after  sync: milk{a1,b2} removed{a1} -> milk present
A removes again, then sync: milk{a1,b2} removed{a1,b2} -> milk absent

Register (একটি মান: নাম, ঠিকানা, theme) দুই রকম। LWW-Register মানের সাথে timestamp রাখে, merge বড়টি নেয় — অংশ ৩-এর LWW, CRDT-র পোশাকে। MV-Register concurrent মানগুলো version vector-সহ সবই রাখে — অংশ ৪-এর siblings-এর CRDT রূপ। এই ইটগুলো জুড়ে map বানানো যায়, যার প্রতিটি key-এর মান নিজেই একটি CRDT (কার্টের তালিকা OR-Set, প্রতিটি জিনিসের পরিমাণ PN-Counter) — JSON-ধাঁচের document CRDT এভাবেই গড়া।

৮ · টেক্সট, collaborative editing আর CRDT-র দাম

টেক্সট সবচেয়ে কঠিন, কারণ অবস্থান সরে যায়। লেখা “CAT”. Rumana অবস্থান ১-এ “H” ঢোকালেন (“CHAT” হবে); একই সময়ে Tanvir অবস্থান ০-তে “!” ঢোকালেন। Tanvir-এর কপি “!CAT”-এ Rumana-র কাজ “অবস্থান ১-এ H” হুবহু প্রয়োগ করলে হয় “!HCAT” — ভুল, কারণ সামনে একটি অক্ষর বেড়েছে। দুটি প্রধান পথ:

• Operational transformation (OT): আসা কাজটিকে ইতিমধ্যে প্রয়োগ হওয়া concurrent কাজ অনুযায়ী রূপান্তর করা — “অবস্থান ১” হয়ে যায় “অবস্থান ২”, ফল “!CHAT”. Ellis ও Gibbs ১৯৮৯ সালে ধারণাটি প্রকাশ করেন। বাস্তবের অনেক ব্যবস্থায় একটি কেন্দ্রীয় সার্ভার সব কাজের একটি ক্রম ঠিক করে, যাতে রূপান্তরের নিয়ম সহজ থাকে; কেন্দ্র ছাড়া নির্ভুল রূপান্তরের নিয়ম লেখা কুখ্যাতভাবে কঠিন, আর গবেষণায় প্রকাশিত কয়েকটি OT algorithm পরে ভুল প্রমাণিত হয়েছে বলে জানা যায়।
• Sequence CRDT: অবস্থানের বদলে প্রতিটি অক্ষর একটি অনন্য, স্থায়ী পরিচয় পায় (যেমন replica + ক্রমিক সংখ্যা)। কাজ হয় “C-এর পরিচয়ের পরে H”, সংখ্যার অবস্থান নয় — তাই সামনে কিছু বাড়লেও অর্থ বদলায় না। একই জায়গায় একসাথে দুটি ঢোকানো হলে পরিচয়ের একটি নির্ধারিত ক্রম ঠিক করে কে আগে। RGA (Roh ও সহকর্মীরা, ২০১১) ধাঁচে প্রতিটি অক্ষর তার বাঁ-পাশের অক্ষরের পরিচয় মনে রাখে; Logoot (২০০৯) ধাঁচে দুই প্রতিবেশীর মাঝে নতুন একটি “ভগ্নাংশ” অবস্থান বানানো হয়। মোছা অক্ষর সাধারণত tombstone হয়ে থাকে, যাতে কেউ তার পরে ঢোকাতে চাইলে পরিচয়টি খুঁজে পাওয়া যায়। (ধারণাটি এখানে সরল করে বলা; প্রতিটি algorithm-এর খুঁটিনাটি আলাদা।)

লেখার সময়ে বহুল আলোচিত দুটি open-source CRDT library হলো Automerge (JSON-ধাঁচের document; পেছনে Martin Kleppmann ও সহকর্মীদের গবেষণা) আর Yjs (Kevin Jahns-এর শুরু করা, টেক্সট-সম্পাদনায় জনপ্রিয়)। দুটিরই API, ফরম্যাট আর কার্যক্ষমতা সংস্করণভেদে বদলেছে, তাই documentation-এ মিলিয়ে নিন। Ink & Switch গবেষণাগোষ্ঠীর ২০১৯ সালের প্রবন্ধ “Local-first software” এই ধারার একটি দর্শন দেয়: local-first অ্যাপে ডেটার মূল কপি ব্যবহারকারীর নিজের device-এ, সার্ভার শুধু মেলানোর সহায়ক।

CRDT-র চারটি দাম

সংখ্যায় দেখুন: একটি কাল্পনিক mobile wallet-এর ব্যালান্স ১০০ টাকা, দুটি region-এ PN-Counter হিসেবে। Network ভাগ; দুই region-এ ৮০ টাকা করে কেনাকাটা, প্রতিটি নিজের কপিতে ১০০ ≥ ৮০ দেখে অনুমোদন দেয়। মেলানোর পর ১০০ − ৮০ − ৮০ = −৬০. CRDT নিখুঁত কাজ করেছে — দুটি কমানোই মনে রেখেছে; ভুলটি নকশার। মাঝামাঝি কৌশল bounded counter বা escrow: ১০০ টাকার “খরচের অধিকার” আগেই ভাগ করা (ধরা যাক ৫০ + ৫০), প্রতিটি region নিজের ভাগে স্বাধীন, ভাগ ফুরালে অন্যের কাছে চায়। সীমা কখনো ভাঙে না, কিন্তু এক region-এ ৮০ টাকার কেনাকাটায় তখন অন্যটির সাথে কথা বলতে হয়।

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

“Offline-এ চলা নোট অ্যাপের sync বানিয়ে দিন” লিখলে AI মুহূর্তে পরিপাটি নকশা দেয় — প্রায়ই “Kafka, Redis, microservices আর timestamp দিয়ে conflict মেটানো।” শুনতে পেশাদার, কিন্তু কিছু ভুল প্রায় নিয়ম করে আসে:

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

• প্রতিটি ডেটার জন্য লিখেছি: concurrent লেখা আদৌ সম্ভব কি না, আর এড়ানো (বাড়ির region) যথেষ্ট কি না
• LWW যেখানে আছে, সেখানে কী হারাতে পারে আর ঘড়ি কতটা ভুল হতে পারে, একটি ছোট সিমুলেশনে মেপেছি
• প্রতিটি CRDT-র একসাথে যোগ-মোছার semantics ব্যবহারকারীর প্রত্যাশার সাথে মিলিয়েছি (add-wins না remove-wins)
• Metadata আর tombstone-এর আকার হিসাব করেছি, আর কবে, কোন শর্তে পরিষ্কার হবে লিখে নিয়েছি
• যে invariant CRDT রাখতে পারে না, তার জন্য coordination বা escrow রেখেছি; failure-mode পর্যালোচনায় network ভাগ ধরে দুই দিকের লেখা হাতে মিলিয়েছি