CRDT — কনফ্লিক্ট-ফ্রি রেপ্লিকেটেড ডেটা টাইপ পরিচিতি

১ · সমস্যা — কনকারেন্ট রাইট কে জেতে?

L16-এ দেখেছি মাল্টি-মাস্টার রেপ্লিকেশনে একাধিক নোড লেখা গ্রহণ করতে পারে — এটি রাইট অ্যাভেইলেবিলিটি বাড়ায়, কিন্তু একটি নতুন সমস্যা তৈরি করে: যদি রেপ্লিকা A ও রেপ্লিকা B একই সময়ে (নেটওয়ার্ক পার্টিশনের কারণে একে অপরকে না জেনে) একই ডেটায় ভিন্ন ভিন্ন আপডেট করে, তাহলে যখন তারা পরে সিঙ্ক হবে — কার আপডেট জিতবে?

একটি সহজ সমাধান হলো ম্যানুয়াল কনফ্লিক্ট রেজোলিউশন (ইউজারকে জিজ্ঞেস করা) বা একটি কেন্দ্রীয় সমন্বয়ক — কিন্তু এতে অ্যাভেইলেবিলিটি ও অটোমেশন দুটোই ক্ষতিগ্রস্ত হয়। CRDT একটি গাণিতিকভাবে গ্যারান্টিযুক্ত বিকল্প দেয়।

২ · CRDT — merge যেভাবে সবসময় একই ফলাফলে "কনভার্জ" করে

CRDTConflict-free Replicated Data Typeএমন একটি ডেটা স্ট্রাকচার যার merge অপারেশন কমিউটেটিভ (ক্রম গুরুত্বপূর্ণ নয়), অ্যাসোসিয়েটিভ (গ্রুপিং গুরুত্বপূর্ণ নয়) ও আইডেম্পোটেন্ট (একই মার্জ একাধিকবার চালালেও ফলাফল বদলায় না) — ফলে কনকারেন্ট আপডেট সবসময় একই সামঞ্জস্যপূর্ণ ফলাফলে কনভার্জ করে। -এর মূল আইডিয়া হলো ডেটা স্ট্রাকচারটি এমনভাবে ডিজাইন করা যাতে তার merge() ফাংশন সবসময় নিরাপদ হয় — কোন রেপ্লিকা "আগে" বা "পরে" মার্জ হলো তাতে কিছু যায় আসে না, ফলাফল সবসময় একই থাকবে।

৩ · G-Counter — একটি গ্রো-অনলি কাউন্টার CRDT

সবচেয়ে সহজ CRDT হলো G-Counter (grow-only counter) — যেমন একটি "মোট ভিউ কাউন্ট" যা শুধু বাড়ে, কখনো কমে না। প্রতিটি রেপ্লিকা নিজের ইনক্রিমেন্ট গোনে একটি পৃথক কাউন্টারে (একটি dict-এর মতো {replica_id: count}), যাতে দুটি রেপ্লিকা একে অপরের কাউন্টার সরাসরি না ছুঁয়ে স্বাধীনভাবে ইনক্রিমেন্ট করতে পারে।

• increment(replica_id) — শুধু সেই রেপ্লিকার নিজস্ব কাউন্টার ১ বাড়ায়।
• merge(state1, state2) — প্রতিটি replica_id-এর জন্য দুই স্টেটের elementwise max নেওয়া হয় (নিরাপদ, কারণ একটি রেপ্লিকার নিজস্ব কাউন্টার শুধু বাড়ে, তাই max নেওয়া কখনো তথ্য হারায় না)।
• value() — সব রেপ্লিকার কাউন্ট যোগ করে মোট ভ্যালু বের করা হয়।

def increment(state, replica_id, amount=1):
    new_state = dict(state)
    new_state[replica_id] = new_state.get(replica_id, 0) + amount
    return new_state

def merge(state1, state2):
    keys = set(state1) | set(state2)
    return {k: max(state1.get(k, 0), state2.get(k, 0)) for k in keys}

def value(state):
    return sum(state.values())

# দুইটি রেপ্লিকা, প্রতিটি স্বাধীনভাবে ইনক্রিমেন্ট করছে
s1 = {}
s1 = increment(s1, "replica_1")
s1 = increment(s1, "replica_1")
s1 = increment(s1, "replica_1")   # replica_1 নিজে ৩ বার ইনক্রিমেন্ট করল

s2 = {}
s2 = increment(s2, "replica_2")
s2 = increment(s2, "replica_2")   # replica_2 নিজে ২ বার ইনক্রিমেন্ট করল

print(f"replica_1 এর স্টেট (merge-এর আগে): {s1}")
print(f"replica_2 এর স্টেট (merge-এর আগে): {s2}")

merged_1_then_2 = merge(s1, s2)
merged_2_then_1 = merge(s2, s1)

print(f"\nmerge(s1, s2) = {merged_1_then_2}  → value = {value(merged_1_then_2)}")
print(f"merge(s2, s1) = {merged_2_then_1}  → value = {value(merged_2_then_1)}")

assert merged_1_then_2 == merged_2_then_1, "কমিউটেটিভিটি ভেঙে গেছে!"
expected_total = 3 + 2
assert value(merged_1_then_2) == expected_total

print(f"\nদুই দিক থেকেই merge একই ফলাফল দিল (commutative) — মোট = {value(merged_1_then_2)} "
      f"(প্রত্যাশিত {expected_total} এর সাথে মিলেছে)")

৪ · LWW-Register — সরল কিন্তু নিখুঁত নয়

সব ডেটার জন্য G-Counter-এর মতো "শুধু বাড়ে" মডেল খাটে না — কখনো কখনো আমাদের একটি সাধারণ ভ্যালু (যেমন "ইউজারের প্রোফাইল নাম") সেট করতে হয়, যেখানে নতুন ভ্যালু পুরনোটিকে সম্পূর্ণ প্রতিস্থাপন করে। এর জন্য LWW-RegisterLast-Write-Wins Registerএকটি CRDT যেখানে প্রতিটি লেখাকে একটি টাইমস্ট্যাম্প দিয়ে ট্যাগ করা হয়, এবং merge সবসময় সবচেয়ে বেশি (পরে) টাইমস্ট্যাম্পযুক্ত ভ্যালুটি রাখে। ব্যবহৃত হয় — প্রতিটি রাইট একটি টাইমস্ট্যাম্প বহন করে, merge সবসময় সবচেয়ে নতুন টাইমস্ট্যাম্পের ভ্যালু রাখে।