উচ্চ লভ্যতার (High Availability) ডিস্ট্রিবিউটেড সিস্টেমে নেটওয়ার্ক বিচ্ছিন্ন হলেও লোকাল নোডে ডেটা লেখার সুবিধা দিতে হয়। কিন্তু পরবর্তীতে নেটওয়ার্ক পুনরায় চালু হলে বিভিন্ন সার্ভারে ঘটে যাওয়া বিপরীতমুখী পরিবর্তনের মধ্যে সংঘাত (Conflict) নিরসন করা অত্যন্ত জটিল ও ঝুঁকিপূর্ণ হয়ে ওঠে। ২০১১ সালে মার্ক শাপিরো এবং তাঁর গবেষক দল আবিষ্কার করেন কনফ্লিক্ট-ফ্রি রেপ্লিকেটেড ডেটা টাইপস (CRDTs)। বিমূর্ত বীজগণিতের বিকাশমান সেমিল্যাটিস (Join-Semilattice) এবং কজাল ব্রডকাস্টের শক্ত গাণিতিক ভিত্তির ওপর দাঁড়িয়ে CRDT নিশ্চিত করে স্ট্রং ইভেনচুয়াল কনসিস্টেন্সি (SEC): বিশ্বের যেকোনো প্রান্তে থাকা দুটি নোড যদি একই আপডেট বার্তাগুলো পায়, তবে কোনো সেন্ট্রাল সার্ভার বা কনসেনসাস অ্যালগরিদম ছাড়াই তাদের ডেটা নিখুঁতভাবে অভিন্ন রূপে রূপান্তরিত হবে।
১. স্ট্রং ইভেনচুয়াল কনসিস্টেন্সি এবং সেমিল্যাটিসের নিয়ম
সাধারণ ইভেনচুয়াল কনসিস্টেন্সিতে ডেটা সামঞ্জস্যপূর্ণ হতে অনেক সময় লাগে। কিন্তু CRDT নিশ্চিত করে তাৎক্ষণিক সমান্তরাল সামঞ্জস্য:
$$mathcal{U}_i = mathcal{U}_j implies mathcal{S}_i equiv mathcal{S}_j$$
স্টেট-বেসড CRDT (CvRDT) ও জয়েন-সেমিল্যাটিস
CvRDT-তে নোডগুলো একে অপরকে নিজেদের পুরো ডেটা স্টেট পাঠায় এবং একটি মার্জ অপারেটর $sqcup$ দিয়ে একত্র করে। এই স্টেট স্পেস একটি সেমিল্যাটিস তৈরি করে যা চারটি মৌলিক বীজগাণিতিক বৈশিষ্ট্য মেনে চলে:
- বিনিময়যোগ্যতা (Commutativity): ডেটা কোন ক্রমে পৌঁছাল তা ফলাফলে কোনো প্রভাব ফেলে না: $x sqcup y = y sqcup x$।
- সংযোজনযোগ্যতা (Associativity): ডেটা প্যাকেটের গ্রুপিংয়ে ফলাফল বদলায় না: $(x sqcup y) sqcup z = x sqcup (y sqcup z)$।
- আইডেমপোটেন্সি (Idempotence): একই ডেটা প্যাকেট ইন্টারনেটে দশবার পৌঁছালেও মান বাড়ে না বা নষ্ট হয় না: $x sqcup x = x$।
- মোনোটোনিক বৃদ্ধি (Monotonic Growth): লোকাল যেকোনো পরিবর্তনে ডেটার মান সময়ের সাথে গাণিতিক অর্ডারে কেবল সামনের দিকেই বৃদ্ধি পায়: $s le s sqcup ext{mutate}(s)$।
২. অপারেশন-বেসড CRDT (CmRDT)
পুরো স্টেট পাঠানোর বদলে যখন নোডগুলো কেবল নিজেদের অপারেশন বার্তাগুলো ($ ext{op}$) ব্রডকাস্ট করে, তখন তাকে CmRDT বলা হয়। যদি কনকারেন্ট অপারেশনগুলো বিনিময়যোগ্য (Commutative) হয়, তবে যেকোনো ক্রমে পৌঁছেও নোডগুলো একই স্টেটে পৌঁছায়।
৩. মৌলিক CRDT স্ট্রাকচারসমূহ
জি-কাউন্টার (Grow-Only Counter)
$n$ সংখ্যক নোডের ক্লাস্টারে প্রতিটি নোড কেবল নিজের ইনডেক্সের মান বাড়াতে পারে ($ec{V}[i] leftarrow ec{V}[i] + 1$)। দুটি নোড মার্জ করার সময় প্রতিটি অবস্থানের সর্বোচ্চ মানটি গ্রহণ করে:
$$ec{V}_A sqcup ec{V}_B = left[ max(ec{V}_A[1], ec{V}_B[1]), dots
ight]$$
এর ফলে কোনো লক ছাড়াই বৈশ্বিক কাউন্টার নিখুঁতভাবে হিসেব করা যায়।
অবজার্ভড-রিমুভড সেট (OR-Set)
একটি ডিস্ট্রিবিউটেড সেটে একই সাথে একটি আইটেম যোগ এবং বিয়োগ করা হলে কনফ্লিক্ট এড়াতে OR-Set ব্যবহৃত হয়। প্রতিবার কোনো আইটেম যোগ করার সময় একটি অনন্য আইডি (UUID) তৈরি করে ট্যাগ লাগিয়ে দেওয়া হয়। ডিলিট করার সময় কেবল সেই নির্দিষ্ট ট্যাগের আইডিগুলোকে মুছে ফেলার তালিকায় যোগ করা হয়। ফলে সমান্তরালভাবে ঘটা নতুন যোগ কোনোভাবেই হারিয়ে যায় না (Add-Wins Semantics)।
৪. সিকোয়েন্স CRDT ও কোলাবোরেটিভ টেক্সট এডিটিং
গুগল ডক্স, ফিগমা বা নোশনের মতো রিয়েল-টাইম মাল্টি-ইউজার টেক্সট এডিটরে হাজার হাজার মানুষ একসাথে লিখতে পারেন। সাধারণ ইনডেক্স ব্যবহার করলে একজন লিখলে অন্যের লেখার পজিশন এলোমেলো হয়ে যায়। আধুনিক Sequence CRDT (যেমন Yjs ও Automerge) প্রতিটি অক্ষরের জন্য একটি ভগ্নাংশিক অনন্য অবস্থান স্থানাঙ্ক ($ ext{id}_A < ext{id}_{ ext{new}} < ext{id}_B$) তৈরি করে। এর ফলে কোটি কোটি পরিবর্তন কোনো কেন্দ্রীয় সার্ভার ছাড়াই সুবিন্যস্ত ও নির্ভুলভাবে স্বয়ংক্রিয়ভাবে মিশে যায়।
