Key-Value Store (DynamoDB) ডিজাইন

ধরো তোমার একটা shopping cart বানাতে হবে যেটা কোনো অবস্থাতেই "Add to cart" fail করবে না — Black Friday-তে data center-এর একটা অংশ down থাকলেও না। এই ধরনের "always writable, highly available" দরকার থেকেই Amazon তৈরি করেছিল Dynamo, যার বাণিজ্যিক রূপ DynamoDB। চলো এমন একটা distributed key-value store ডিজাইন করি।

১. সমস্যা বোঝা (Requirements)

Functional requirements:

• get(key) এবং put(key, value) — সহজ key-value interface।
• Value হতে পারে blob (যেমন serialized cart object)।
• কোনো complex join বা SQL দরকার নেই।

Non-functional requirements:

• High availability — write প্রায় সবসময় সফল হবে ("always writable")।
• Partition tolerance — network ভাগ হলেও চলবে।
• Horizontal scalability — commodity hardware যোগ করেই বাড়বে।
• Tunable consistency — কোথাও strong, কোথাও eventual — application ঠিক করবে।
• Low latency — single-digit millisecond।

CAP theorem-এর আলোকে: network partition-এ DynamoDB availability-কে অগ্রাধিকার দেয় (AP system), strong consistency-কে নয়। তাই eventual consistency মেনে নিতে হয়।

২. স্কেল আন্দাজ (Estimation)

ধরি: 100 million active user
প্রতি user-এর গড় cart data: 5 KB
মোট data = 100M * 5 KB = ~500 GB (replication ছাড়া)

Replication factor N = 3
=> মোট storage = 500 GB * 3 = ~1.5 TB

Traffic:
peak 500,000 read/s + 100,000 write/s
একটি node ~10,000 op/s handle করলে
=> দরকার ~60 node (headroom সহ 100+)

Data ছোট হলেও traffic বিশাল — তাই বহু node-এ ছড়িয়ে দেওয়া আর প্রতিটি node-এর load সমান রাখা মূল চ্যালেঞ্জ।

৩. API ডিজাইন

get(key, consistencyLevel) -> {value, context}
  - context হলো version metadata (vector clock)
  - consistencyLevel: ONE | QUORUM | ALL

put(key, value, context, consistencyLevel) -> ok
  - context ফেরত দিতে হয় যাতে server জানে কোন version-এর উপর লেখা হচ্ছে
  - এতে conflict detection সম্ভব হয়

delete(key, context)

context/version metadata-টাই হলো DynamoDB-র জাদু — এটা দিয়ে concurrent update ধরা পড়ে।

৪. ডেটা মডেল

Concept	বর্ণনা
key	partition নির্ধারণ করে (hash করা হয়)
value	opaque blob (application নিজে interpret করে)
version (vector clock)	কোন node কতবার update করেছে তার history
coordinator node	যে node request handle করে ও replicate করে
preference list	যে N node এই key host করবে তাদের তালিকা

Choice: আমরা schema-less, blob-based model নিচ্ছি কারণ requirement-এ join/query নেই — শুধু key দিয়ে দ্রুত lookup চাই। এই simplicity-ই horizontal scaling সহজ করে।

৫. হাই-লেভেল ডিজাইন

মূল components:

• Partitioning layer (consistent hashing ring): key কোন node-এ যাবে তা ঠিক করে।
• Replication: প্রতিটি key ring-এ পরের N-1 distinct node-এ copy হয় (preference list)।
• Coordinator: client request যে node-এ আসে, সেটা coordinator হয়ে quorum-এ read/write করে।
• Gossip protocol: node-রা একে অন্যের membership ও health জানে।
• Failure handling: hinted handoff (temporary failure) আর read repair / anti-entropy (permanent inconsistency)।

Write flow:

1. Client put করে কোনো coordinator-এ।
2. Coordinator key hash করে preference list-এর N node বের করে।
3. সব N node-এ write পাঠায়, কিন্তু W node থেকে ack পেলেই client-কে success বলে।
4. একটা node down থাকলে hinted handoff চালু হয়।

৬. গভীরে (Deep Dive)

ক. Consistent Hashing দিয়ে Partitioning

Node আর key দুটোকেই একই hash space-এ (একটা ring) বসানো হয়। একটা key-এর জন্য ring-এ clockwise প্রথম যে node, সেটাই দায়িত্বশীল।

সাধারণ hashing-এ (hash(key) % N) একটা node যোগ/বাদ দিলে প্রায় সব key remap হয়। Consistent hashing-এ গড়ে শুধু K/N key সরে। আরও সমতা আনতে virtual node ব্যবহার হয় — একটা physical node ring-এ অনেক জায়গায় বসে, ফলে load সমান বণ্টিত হয় আর হেটেরোজিনিয়াস hardware সামলানো যায়।

খ. Quorum ও Tunable Consistency

প্রতিটি key N node-এ replicate হয়। তিনটা সংখ্যা গুরুত্বপূর্ণ:

• N = replica সংখ্যা।
• W = কতগুলো node থেকে write ack লাগবে।
• R = কতগুলো node থেকে read করতে হবে।

মূল নিয়ম: R + W এর চেয়ে বড় N হলে read quorum আর write quorum অন্তত একটা node share করবে, ফলে সর্বশেষ লেখা value পড়া যাবে (strong-ish consistency)।

N = 3
W = 2, R = 2  -> R + W = 4, যা N (3) এর চেয়ে বড়  => consistent পড়া
W = 1, R = 1  -> R + W = 2, যা N এর কম  => দ্রুত কিন্তু stale পড়তে পারে
W = 3, R = 1  -> দ্রুত read, ধীর write
W = 1, R = 3  -> দ্রুত write, ধীর read

এভাবে application নিজের প্রয়োজন অনুযায়ী latency বনাম consistency tune করে।

গ. Conflict Resolution: Vector Clock

যেহেতু availability-র জন্য একই key দুই জায়গায় concurrent লেখা হতে পারে, conflict অনিবার্য। DynamoDB vector clock দিয়ে এটা detect করে — প্রতিটি value-র সাথে [(nodeA, 2), (nodeB, 1)] মতো version counter থাকে।

• যদি একটা version অন্যটার সম্পূর্ণ ancestor হয় → automatically নতুনটা জেতে।
• যদি দুটো version concurrent হয় (কেউ কারো ancestor নয়) → conflict, দুটোই client-কে ফেরত দেওয়া হয়। Client application-level merge করে (যেমন shopping cart-এ দুই version-এর item একত্র করা)।

এটাই "last write wins" এর চেয়ে নিরাপদ, কারণ blind overwrite-এ data হারায় না।

ঘ. Failure Handling

• Gossip: node-রা periodically একে অন্যকে ping করে membership ও failure শেয়ার করে — কোনো central master লাগে না।
• Hinted handoff: preference list-এর কোনো node down থাকলে আরেকটা node সাময়িকভাবে write ধরে রাখে (hint হিসেবে) আর আসল node ফিরলে handoff করে দেয় — এতে write কখনো fail করে না।
• Read repair ও Merkle tree anti-entropy: read-এর সময় ভিন্ন version দেখলে সঠিকটা দিয়ে stale replica আপডেট হয়; background-এ Merkle tree দিয়ে replica গুলোর পার্থক্য efficiently মিলিয়ে নেওয়া হয়।

৭. বটলনেক ও স্কেলিং

• Hot key: এক key-তে বিপুল traffic হলে সেই partition গরম হয়। সমাধান — caching layer, অথবা write coalescing, কিংবা সেই key আলাদা handling।
• Coordinator load: এক coordinator-এ load জমলে client-side load balancing বা token-aware routing দিয়ে directly সঠিক node-এ যাওয়া যায়।
• Anti-entropy খরচ: Merkle tree তুলনা CPU/network খায়; এটা off-peak time-এ throttle করা ভালো।
• Eventual consistency-র বাস্তবতা: stale read application-কে সামলাতে হবে। যেখানে দরকার সেখানে R + W এর চেয়ে বড় N দিয়ে quorum read করো।

৮. সারসংক্ষেপ

DynamoDB-ধাঁচের store হলো একটা AP system — partition tolerance ও availability-কে strong consistency-র চেয়ে বেশি গুরুত্ব দেয়। মূল building block: consistent hashing (partition + কম reshuffle), N/R/W quorum (tunable consistency), vector clock (conflict detection), আর gossip + hinted handoff + read repair (failure resilience)। মনে রাখো — সব কিছুর কেন্দ্রে একটা trade-off: তুমি consistency কমিয়ে availability ও latency কিনছো।