Distributed key-value store ডিজাইন (Dynamo-ধাঁচ)

লক্ষ্য: একটি key-value store (put(key, value), get(key)) যা scale out করে, ব্যর্থতার মধ্যেও available থাকে, এবং tune করা যায় এমন consistency দেয়। এটি Amazon-এর Dynamo গবেষণাপত্রের ধারণা অনুসরণ করে, যা Cassandra ও Riak-কে প্রভাবিত করেছে।

Requirement

Node যোগ করে বিশাল data ও উচ্চ throughput।
কিছু node বন্ধ থাকলেও সবসময় লেখা-পড়া যায় (availability আগে)।
কম latency।
Tune-যোগ্য consistency।

Partitioning

Virtual node সহ consistent hashing ব্যবহার করুন: key ও node ring-এ বসে, প্রতিটি key ঘড়ির দিকে পরের node-এর। Node যোগ বা বাদ দিলে key-র সামান্য অংশই নড়ে।

Replication

প্রতিটি key ring-এ ধারাবাহিক N টি node-এ থাকে (যেমন N=3)। যেকোনো node request-এর coordinator হতে পারে।

Quorum: R, W ও N

W: কতগুলো replica write নিশ্চিত করবে।
R: কতগুলো replica read-এর উত্তর দেবে।
R + W > N হলে read ও write অন্তত একটি replica-তে মিলে যায়, তাই read সর্বশেষ write দেখে।

N=3 ধরে উদাহরণ: W=2, R=2 consistency দেয়; W=1, R=1 গতি ও availability দেয় কিন্তু পুরোনো read হতে পারে। ব্যবহারের ক্ষেত্র অনুযায়ী বাছুন।

ব্যর্থতায় টিকে থাকা

Sloppy quorum ও hinted handoff: replica বন্ধ থাকলে অন্য node সাময়িকভাবে "hint" সহ write নেয় এবং replica ফিরলে এগিয়ে দেয়। এতে write available থাকে।
Gossip দিয়ে ব্যর্থতা শনাক্ত: node-রা নিয়মিত heartbeat তথ্য বিনিময় করে, তাই কেন্দ্রীয় master ছাড়াই cluster জানে কে জীবিত।
Read repair: read পুরোনো replica ধরলে coordinator সেটি আপডেট করে।
Merkle tree দিয়ে anti-entropy: node-রা data-র tree hash তুলনা করে পেছনে সস্তায় পার্থক্য খুঁজে ঠিক করে।

Conflict

Availability আগে হলে দুই client আলাদা replica-তে একই key-তে ভিন্ন মান লিখতে পারে। সমাধান: last-write-wins (সহজ, data হারাতে পারে) অথবা vector clock যা সমান্তরাল সংস্করণ শনাক্ত করে যাতে অ্যাপ (বা CRDT) merge করতে পারে।

প্রতিটি node-এর storage engine

বেশিরভাগ এমন store LSM tree ব্যবহার করে:

Commit log-এ (টেকসই করতে) এবং in-memory memtable-এ লেখা।
ভরে গেলে memtable অপরিবর্তনীয় সাজানো ফাইলে (SSTable) flush।
Read আগে memtable, তারপর SSTable দেখে (Bloom filter key-হীন ফাইল এড়ায়)।
Compaction পেছনে ফাইল merge করে।

Write ক্রমিক বলে খুব দ্রুত।

লেনদেন

কঠোর consistency-র চেয়ে availability ও partition tolerance বাছা হয়। অ্যাপকে পুরোনো read ও conflict সামলাতে হবে।

মূল কথা: consistent hashing, N replica, tune-যোগ্য R/W quorum, hinted handoff, gossip, repair এবং LSM-tree engine মিলে scalable, available key-value store দেয়।

System Design সিরিজ, পর্ব ৪ (infrastructure ডিজাইন): 3 নম্বর (মোট 4)। আগের লেখা: Distributed cache ডিজাইন.