CRDTs (Conflict-free Replicated Data Types)
- ●CRDT এমন ডেটা স্ট্রাকচার যা একাধিক replica-তে স্বাধীনভাবে edit করলেও coordination ছাড়াই স্বয়ংক্রিয়ভাবে merge হয়ে এক অবস্থায় converge করে।
- ●মূল গণিত — merge অপারেশন commutative, associative ও idempotent হলে, যেকোনো ক্রমে update এলেও ফলাফল একই থাকে।
- ●Counter, set, sequence ইত্যাদি CRDT collaborative editing ও offline-first অ্যাপে কাজে লাগে।
সমস্যাটা কী?
ভাবো Google Docs-এ তুমি আর তোমার বন্ধু একই ডকুমেন্ট একসাথে edit করছো। তুমি শুরুতে লিখছো, সে মাঝখানে মুছছে, দুজনের ইন্টারনেট মাঝে মাঝে কাটছে। তবু কয়েক সেকেন্ড পর দুজনের স্ক্রিনে ঠিক একই লেখা দেখা যায়, কিছু হারায় না। এটা কীভাবে সম্ভব?
সাধারণ উপায় হবে একটা central server-কে judge বানানো — সবাই তার কাছে পাঠাবে, সে ক্রম ঠিক করবে। কিন্তু এতে latency বাড়ে, server ডাউন হলে কেউ edit করতে পারে না, আর offline edit তো অসম্ভব।
আমরা চাই — প্রতিটা replica স্বাধীনভাবে, এমনকি offline থেকেও edit করুক, পরে যখন সংযোগ হবে তখন কোনো central coordinator ছাড়াই সব edit আপনাআপনি conflict-free ভাবে merge হোক, আর সবাই একই চূড়ান্ত অবস্থায় পৌঁছাক। এই অসম্ভব-শোনানো জিনিসটাই CRDT সম্ভব করে।
মূল ধারণা
CRDT (Conflict-free Replicated Data Type): এমনভাবে ডিজাইন করা ডেটা স্ট্রাকচার, যেখানে concurrent update গুলো এমন একটি গাণিতিক নিয়ম মেনে merge হয় যে, replica-রা যেকোনো ক্রমে update পেলেও শেষে নিশ্চিতভাবে একই অবস্থায় converge করে — কোনো coordination ছাড়াই।
জাদুটা গণিতে। merge অপারেশনকে এমন হতে হবে যে সে তিনটা গুণ মানে:
- Commutative: A merge B সমান B merge A — ক্রম গুরুত্বপূর্ণ নয়।
- Associative: গ্রুপিং গুরুত্বপূর্ণ নয়।
- Idempotent: একই update দুবার এলেও ফল বদলায় না — তাই duplicate message-ও নিরাপদ।
এই তিনটা থাকলে update যে ক্রমেই, যতবারই আসুক, সব replica একই ফলাফলে মেলে। এই অবস্থাকে গণিতে বলে semilattice, আর merge হলো তার "join"।
কীভাবে কাজ করে
দুই ঘরানা
| ঘরানা | কী পাঠায় | সুবিধা | অসুবিধা |
|---|---|---|---|
| State-based (CvRDT) | পুরো state পাঠিয়ে merge | সহজ, message হারালেও চলে | state বড় হলে ভারী |
| Operation-based (CmRDT) | শুধু অপারেশন পাঠায় | হালকা message | reliable delivery দরকার |
G-Counter (grow-only counter)
প্রতিটা replica নিজের জন্য আলাদা গণনা রাখে। ৩টা নোড হলে state একটা array:
নোড A: [A:3, B:1, C:0]
নোড B: [A:2, B:4, C:0]
merge (প্রতি entry-র max): [A:3, B:4, C:0]
মোট মান = 3 + 4 + 0 = 7
merge-এ সবসময় প্রতি entry-র সর্বোচ্চ নেওয়া হয় — এটা commutative ও idempotent। বিয়োগ করতে চাইলে PN-Counter (এক increment, এক decrement counter) লাগে।
Sets
- G-Set: শুধু যোগ করা যায়, কখনো মোছা যায় না।
- OR-Set (Observed-Remove Set): প্রতিটা add-কে unique tag দেয়; remove শুধু যে tag গুলো দেখেছে সেগুলো মোছে। ফলে "add বনাম concurrent remove" দ্বন্দ্বে add সাধারণত জেতে।
Sequence CRDT
text editing-এর জন্য সবচেয়ে জটিল। প্রতিটা character-কে একটা unique, ক্রমে-সাজানো position-id দেওয়া হয় (RGA, LSEQ, কিংবা Logoot)। দুই জায়গায় একই অবস্থানে নতুন character এলেও তাদের id ভিন্ন থাকে, তাই merge-এ একটা সুনির্দিষ্ট ক্রমে বসে যায় — অক্ষর হারায় না।
প্রকারভেদ
ভাবো গ্রামের একটা সমিতির টাকা গোনা, যেখানে তিনটা শাখা (ঢাকা, খুলনা, রাজশাহী)। প্রতি শাখা নিজের ঘরে নিজের আদায় আলাদা খাতায় লেখে — কেউ কারো জন্য অপেক্ষা করে না। মাস শেষে তিনটা খাতা মেলানোর সময় প্রতিটা শাখার নিজের লাইনের সর্বশেষ বড় সংখ্যাটা নেওয়া হয়, তারপর যোগ। যে ক্রমেই খাতা মেলাও না কেন, একই খাতা দুবার মেলালেও — মোট একই থাকে। কোনো শাখা আরেক শাখার সংখ্যায় হাত দেয় না বলে কখনো দ্বন্দ্ব হয় না। এটাই G-Counter-এর CRDT আচরণ।
কৌশল
CRDT বেছে নেওয়ার সময় মনে রাখার কৌশল:
- শুধু যোগ? G-Counter বা G-Set যথেষ্ট, সবচেয়ে সস্তা।
- যোগ-বিয়োগ দুটোই? PN-Counter বা OR-Set।
- Text/list? sequence CRDT (RGA/Yjs/Automerge), কিন্তু metadata খরচ বেশি, tombstone জমে।
- State নাকি Operation? network অবিশ্বস্ত হলে state-based নিরাপদ; bandwidth সংকটে operation-based।
বিকল্প পদ্ধতি OT (Operational Transformation) — পুরোনো Google Docs যা ব্যবহার করত — কাজ করে কিন্তু central server-নির্ভর ও বাস্তবায়ন কুখ্যাতভাবে কঠিন; CRDT decentralized ও offline-friendly।
কখন ব্যবহার করবে / করবে না
ব্যবহার করবে — real-time collaborative editing, offline-first মোবাইল অ্যাপ (পরে sync), multi-region distributed cache/counter, যেখানে availability ও local edit গুরুত্বপূর্ণ।
ব্যবহার করবে না — যেখানে strict business invariant দরকার (যেমন "balance কখনো negative হবে না"); CRDT eventual consistency দেয়, কিন্তু এমন global constraint একা নিশ্চিত করতে পারে না।
CRDT মানে "conflict নেই" — কিন্তু এর মানে এই নয় যে merge-এর ফলাফল সবসময় ব্যবসায়িকভাবে "সঠিক"। OR-Set-এ concurrent add ও remove হলে হয়তো add জিতবে, যা হয়তো ইউজার চায়নি। আর sequence CRDT-তে মুছে ফেলা অক্ষরের tombstone জমে metadata ফুলে যেতে পারে — garbage collection ছাড়া long-lived ডকুমেন্ট ভারী হয়ে যায়। তাই merge semantics ভালো করে বুঝে তবেই ব্যবহার করো।
বাস্তব উদাহরণ
- Yjs / Automerge: জনপ্রিয় CRDT library, বহু collaborative editor এর ভিত্তি।
- Redis (Active-Active / CRDB): multi-region replication-এ CRDT-based counter ও set ব্যবহার করে।
- Riak: CRDT data type (counter, set, map) built-in দেয়।
- Apple Notes / Figma-জাতীয় অ্যাপ: device-জুড়ে offline edit sync-এ CRDT-সদৃশ কৌশল ব্যবহার করে।
ইন্টারভিউতে collaborative editing বা offline sync নিয়ে প্রশ্ন এলে CRDT-র নাম তুলে বলো — "merge অপারেশনকে commutative, associative ও idempotent বানালে central coordinator ছাড়াই সব replica converge করে।" তারপর OT-র সাথে তুলনা করে দেখাও CRDT কেন decentralized ও offline-friendly। এই গাণিতিক ভিত্তিটা স্পষ্ট বলতে পারলে তুমি আলাদা হয়ে যাবে।
মূল শব্দ (Key Terms)
মিনি কুইজ
1. CRDT-এর merge অপারেশনের জন্য কোন গাণিতিক বৈশিষ্ট্যগুলো জরুরি?
2. একটি grow-only counter (G-Counter) কীভাবে concurrent increment merge করে?
3. CRDT কেন collaborative editing-এ জনপ্রিয়?