Data & Infrastructureপড়তে ১৪ মিনিট লাগবে

কি-ভ্যালু (Key-Value) স্টোর ডিজাইন

রেডিস বা ডায়নামো ডিবি-র মতো বিশ্বব্যাপী একটি ডিস্ট্রিবিউটেড হ্যাশ ম্যাপ তৈরি করা

scope:বাস্তব সিস্টেমdifficulty:অ্যাডভান্সড

সমস্যাটি বোঝা

একটি কি-ভ্যালু (Key-Value) স্টোর ডিস্ট্রিবিউটেড সিস্টেমগুলোর মধ্যে সবচেয়ে সহজ কিন্তু সবচেয়ে শক্তিশালী একটি সিস্টেম। রেডিস (Redis), ডায়নামো ডিবি (DynamoDB), বা এথসিডি-এর (etcd) কথা চিন্তা করুন — এটি মূলত একটি বিশাল হ্যাশ ম্যাপ, যা একসাথে অনেকগুলো মেশিনে বা কম্পিউটারে ছড়িয়ে থাকে।

এর API-টি দেখতে বেশ সহজ মনে হলেও এর ভেতরের কাজগুলো খুব জটিল হয়ে থাকে:

put(key, value) — একটি ভ্যালু স্টোর করা
get(key) — একটি ভ্যালু ফিরিয়ে আনা
delete(key) — একটি ভ্যালু মুছে ফেলা
এর সাথে অপশনাল হিসেবে থাকে: TTL (time-to-live) — যা নির্দিষ্ট সময় পর স্বয়ংক্রিয়ভাবে (auto-expire) কি বা ডেটা মুছে ফেলে

ফাংশনাল রিকয়ারমেন্টস:

এমন কি-ভ্যালু পেয়ার যুক্ত করা যেখানে কি-গুলো (keys) স্ট্রিং হিসেবে এবং ভ্যালুগুলো (values) ব্লাইন্ড ডেটা বা ওপেক ব্লব (সর্বোচ্চ প্রায় ১ MB) হিসেবে স্টোর হয়।
get, put এবং delete অপারেশন বা নির্দেশ সাপোর্ট করতে হবে।
TTL-ভিত্তিক স্বয়ংক্রিয়ভাবে কি বা ডেটা মুছে ফেলার সুবিধা থাকতে হবে।

নন-ফাংশনাল রিকয়ারমেন্টস:

লো ল্যাটেন্সি (Low latency): ডেটা পড়া (read) ও লেখা (write) উভয়ের কাজই ১০ মিলিসেকেন্ডের (ms) মধ্যে সম্পূর্ণ হতে হবে।
উচ্চ প্রাপ্যতা (High availability): একটি সার্ভার বা নোড বা মেশিন নষ্ট হলেও যেন স্টোরটি কাজ করতে পারে।
টিনয়েবল কনসিস্টেন্সি (Tunable consistency): সিস্টেমের ধরন অনুসারে ইউজাররা যেন স্ট্রং কনসিস্টেন্সি (Strong consistency) ও ইভেনচুয়াল কনসিস্টেন্সি (Eventual consistency) নিজেদের ইচ্ছেমতো বেছে নিতে পারেন।
স্কেলেবিলিটি (Scalability): সমান্তরাল বা হরাইজোন্টাল স্কেলিংয়ের মাধ্যমে লাখ লাখ কি ও ভ্যালু একসাথে হ্যান্ডেল করার সক্ষমতা থাকতে হবে।

▸ ধারণা: একটি ডিস্ট্রিবিউটেড হ্যাশ ম্যাপ

সিঙ্গেল সার্ভার বনাম ডিস্ট্রিবিউটেড স্টোর

মাত্র একটি সার্ভার দিয়ে একটি কি-ভ্যালু স্টোর বানানো বেশ সহজ — এর জন্য কেবল মেমরিভিত্তিক একটি হ্যাশ ম্যাপ তৈরি করতে হয়। তবে এই আর্কিটেকচারের কিছু বড় সমস্যা আছে:

মেমরি (Memory): একটি সার্ভারে হয়তো ২৫৬ GB র‍্যাম থাকতে পারে। কিন্তু যদি ১০০ TB ডেটা রাখার প্রয়োজন পড়ে, তখন কী হবে?
অ্যাভেইলেবিলিটি (Availability): যদি সার্ভারটি নষ্ট হয়ে যায়, তবে এর মধ্যে থাকা সব ডেটাই হারিয়ে যাবে।
থ্রুপুট (Throughput): একটি সার্ভার বড়জোর ১০০K (১ লাখ) অপারেশন বা কাজ প্রতি সেকেন্ডে (ops/sec) করতে পারে। যদি সেকেন্ডে ১০ মিলিয়ন বা ১ কোটি অপারেশনের দরকার হয়, তখন কী করা উচিত?

একটি সিঙ্গেল সার্ভারের সীমাবদ্ধতা কাটিয়ে ওঠার জন্য দুটি মূল কৌশল ব্যবহার করা হয়:

পার্টিশনিং বা শার্ডিং (Partitioning/Sharding): ডেটাকে একাধিক নোড বা মেশিনের মধ্যে ভাগ করে দেওয়া হয়, যাতে প্রতিটি নোড মূল ডেটার একটি ছোট অংশ (subset) বহন করে। কোন নোডে কোন ডেটা রাখা হবে তা ঠিক করার জন্য আমরা কনসিস্টেন্ট হ্যাশিং (consistent hashing) ব্যবহার করি।
রেপ্লিকেশন (Replication): প্রতিটি ডেটার কপি কয়েকটি নোডে (সাধারণত ৩টি-তে) সেভ করা হয়, যাতে একটি নোড নষ্ট হলেও অন্যগুলো থেকে ডেটা পাওয়া যায়। তবে এর ফলে ডেটার কপিগুলো সব সময় আপডেট রাখার (Sync) চ্যালেঞ্জ দেখা দেয়।

পার্টিশনিং এবং রেপ্লিকেশন — এই দুইয়ের মিশ্রণেই ডিস্ট্রিবিউটেড কি-ভ্যালু স্টোরগুলোর স্কেলিং এবং ফল্ট-টলারেন্স (নির্ভরযোগ্যতা) নিশ্চিত করা হয়।

▸ কনসিস্টেন্ট হ্যাশিং দিয়ে ডেটা পার্টিশনিং

Click chart to zoom

রাইট পাথ (Write path): কোঅর্ডিনেটর কি-গুলোর হ্যাশ বের করে এবং তিনটি (N=3) রেপ্লিকা নোডে রাইট রিকোয়েস্ট পাঠায়। অন্তত দুটি নোড (W=2) থেকে কনফার্মেশন বা ACK পাওয়ার পর সফলতার মেসেজ দেয়।

রেপ্লিকেশন ও কোরাম কনসেনসাস (Quorum Consensus)

প্রতিটি কি-এর একটি কপি N সংখ্যক নোডে (সাধারণত N=3) সেভ করা হয়। কিন্তু কোনো ডেটা রাইট বা রিড সফল হয়েছে, তা বোঝার জন্য কয়টি নোড থেকে আমাদের সিগন্যাল বা কনফার্মেশনের দরকার হবে?

কয়টি নোড থেকে কনফার্মেশন দরকার, এই বিষয়টিই কোরাম (quorum) এর দ্বারা নির্ধারিত হয়:

W (রাইট কোরাম): ডেটা সফলভাবে সেভ হয়েছে এমন মেসেজ রিটার্ন করার জন্য অন্তত কয়টি নোড থেকে ACK বা কনফার্মেশন আসতে হবে।
R (রিড কোরাম): সঠিকভাবে ডেটা পড়তে হলে অন্তত কয়টি নোড সার্ভ করা ডেটার সাথে সম্মতি জানাতে হবে।
N (রেপ্লিকেশন ফ্যাক্টর): মোট যতগুলো রেপ্লিকেশন বা কপির দরকার।

যাদুকরী ফর্মুলা: W + R > N, যা এই সিস্টেমকে অত্যন্ত নিখুঁতভাবে (strong consistency) ডেটা সেভ ও রিড করতে সাহায্য করে।

সবচেয়ে পরিচিত কিছু কনফিগারেশন বা সেটিংস:

স্ট্রং কনসিস্টেন্সি (Strong consistency): W=2, R=2, N=3 → সব সময় একদম সর্বশেষ আপডেটেড ডেটাই পাওয়া যায়।
হাই রাইট অ্যাভেইলেবিলিটি (High write availability): W=1, R=3, N=3 → রাইট খুব দ্রুত হয়, কিন্তু রিড হতে একটু সময় নেয়।
হাই রিড অ্যাভেইলেবিলিটি (High read availability): W=3, R=1, N=3 → রাইট হতে সময় লাগে, তবে রিড হয় অত্যন্ত দ্রুত।
ইভেনচুয়াল কনসিস্টেন্সি (Eventual consistency): W=1, R=1, N=3 → রিড এবং রাইট দুই-ই খুব দ্রুত হয়, তবে মাঝে মাঝে পুরোনো ডেটা পাওয়ার একটা চান্স থেকে যায়।

অ্যামাজনের ডায়নামো ডিবি (DynamoDB) বাই ডিফল্ট N=3 ব্যবহার করে। তবে ক্যাসান্দ্রা (Cassandra) আপনাকে প্রতিটি রিকোয়েস্টের জন্য কোরাম বা W এবং R টিউন করার সুযোগ দেয়। এই টিউনেবিলিটির (tunability) কারণেই এই সিস্টেমগুলো এতটা ফ্লেক্সিবল ও দরকারী।

▸ রেপ্লিকেশন ও কোরাম কনসেনসাস

কনফ্লিক্ট বা দ্বন্দ্ব মেটানো এবং ফেইলিয়ুর নিয়ন্ত্রণ করা (Failure Handling)

যখন একাধিক রেপ্লিকা বা নোড আলাদাভাবে ডেটা রাইট করতে শুরু করে, তখন সেগুলোর মধ্যে অসামঞ্জস্যতা (conflict) দেখা দেওয়া অনিবার্য। তাহলে এই সমস্যা কীভাবে সমাধান করা যায়?

ভেক্টর ক্লকস (Vector Clocks): প্রতিটি নোড একটি লজিক্যাল সময়ের (logical clock) হিসাব রাখে। যখনই কোনো ভ্যালু রাইট বা লেখা হয়, ভেক্টর ক্লক একটু এগিয়ে যায়। ডেটা রিড বা পড়ার সময়, যদি দুটি ডেটার ভার্সনের ভেক্টর ক্লক একই রকম না কাশী হয় (অর্থাৎ কোনটা আগে লেখা হয়েছে তা বোঝা না যায়), তখন ক্লায়েন্ট বা ইউজারকেই ম্যানুয়ালি সেই কনফ্লিক্ট ঠিক করতে হয় (যেমন, দুটি শপিং কার্ট একত্রিত করা)। Amazon-এর Dynamo ডেটাবেস এই পদ্ধতিটি ব্যবহার করে।

লাস্ট-রাইট-উইনস (LWW): এটি আরও সহজ একটি পদ্ধতি — প্রতিটি রাইট অপারেশনের সাথে একটি টাইমস্ট্যাম্প যুক্ত থাকে, এবং সবার শেষে লেখা বা সর্বশেষ টাইমস্ট্যাম্পের ডেটাটিকেই আসল বলে ধরে নেওয়া হয়। ক্যাসান্দ্রা এই পদ্ধতিটি ব্যবহার করে। এটি ইমপ্লিমেন্ট করা সহজ, তবে ঘড়ির হিসেবে সামান্য গড়মিল থাকলে ডেটা হারানোর ঝুঁকি থাকে।

নেটওয়ার্ক ড্রপ হলে বা ফেইলিয়ুর ডিটেকশন — গসিপ প্রোটোকল: সিস্টেমে থাকা নোডগুলো নির্দিষ্ট সময় পর পর একে অন্যের সাথে মেসেজ আদান-প্রদান করে। যদি কোনো একটি নোডের কাছ থেকে বেশ কিছুক্ষণ ধরে মেসেজ না আসে, তবে ধরে নেওয়া হয় যে নোডটি ডাউন হয়ে গেছে। এই সিস্টেমটি বিকেন্দ্রীকৃত বা ডিসেন্ট্রালাইজড (decentralized) — অর্থাৎ, কোনো একক পয়েন্ট অফ ফেইলিয়ুর নেই।

ফেইলিয়ুর নিয়ন্ত্রণ বা হ্যান্ডলিং করা:

হিন্টেড হ্যান্ডঅফ (Hinted Handoff): যদি কোনো রেপ্লিকা নোড কিছুক্ষণের জন্য বন্ধ হয়ে যায়, তখন অন্য একটি নোড সেই ডেটাটিকে একটি 'হিন্ট (hint)' হিসেবে সেভ করে রাখে এবং পরবর্তীতে সেই নষ্ট নোডটি আবার চালু হলে তার কাছে ডেটাগুলো পাঠিয়ে দেয়।
রিড রিপেয়ার (Read Repair): ডেটা রিড করার সময়, যদি রেপ্লিকাগুলো বিভিন্ন ভার্সনের ডেটা রিটার্ন করে, তখন কোঅর্ডিনেটর সবচেয়ে নতুন ডেটাটি খুঁজে বের করে অন্যান্য পুরনো (stale) রেপ্লিকাগুলো আপডেট করে দেয়।
অ্যান্টি-এনট্রপি (Anti-Entropy / Merkle Trees): নোডগুলো পর্যায়ক্রমে বা রুটিনমাফিক নিজেদের ডেটার মারকেল ট্রির (Merkle trees) একটি হিসাব চেক করে। সে হিসেবে কোনো অমিল ধরা পড়লে, ব্যাকগ্রাউন্ডে তা ঠিক করে নেওয়া হয়।

▸ উচ্চ প্রাপ্যতা এবং ফেইলিয়ুর হ্যান্ডলিংসহ সম্পূর্ণ আর্কিটেকচার

কনসিস্টেন্ট হ্যাশিংসহ একটি সাধারণ ইন-মেমরি KV স্টোর (পাইথন উদাহরণ)

import hashlib
from bisect import bisect_right

class ConsistentHash:
    """ভার্চুয়াল নোডসহ কনসিস্টেন্ট হ্যাশ রিং।"""
    def __init__(self, nodes: list[str], vnodes: int = 150):
        self.ring: dict[int, str] = {}
        self.sorted_keys: list[int] = []
        for node in nodes:
            for i in range(vnodes):
                key = self._hash(f"{node}:{i}")
                self.ring[key] = node
        self.sorted_keys = sorted(self.ring.keys())

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_nodes(self, key: str, n: int = 3) -> list[str]:
        """কোন কি-এর দায়িত্বে থাকা এন (N) সংখ্যক আলাদা নোড খুঁজুন।"""
        if not self.sorted_keys:
            return []
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h) % len(self.sorted_keys)
        nodes = []
        seen = set()
        while len(nodes) < n:
            node = self.ring[self.sorted_keys[idx]]
            if node not in seen:
                nodes.append(node)
                seen.add(node)
            idx = (idx + 1) % len(self.sorted_keys)
        return nodes

class KVStore:
    """কোরাম রিডস/রাইটসহ ডিস্ট্রিবিউটেড KV স্টোর।"""
    def __init__(self, nodes: list[str], n=3, w=2, r=2):
        self.n, self.w, self.r = n, w, r
        self.ring = ConsistentHash(nodes)
        # নোড প্রতি স্টোরেজ হওয়ার একটি সিমুলেশন
        self.storage: dict[str, dict[str, str]] = {node: {} for node in nodes}

    def put(self, key: str, value: str) -> bool:
        nodes = self.ring.get_nodes(key, self.n)
        acks = 0
        for node in nodes:
            self.storage[node][key] = value  # রাইট করার একটি সিমুলেশন
            acks += 1
        return acks >= self.w  # কি কোরাম মেনে কাজ শেষ হয়েছে?

    def get(self, key: str) -> str | None:
        nodes = self.ring.get_nodes(key, self.n)
        responses = []
        for node in nodes:
            val = self.storage[node].get(key)
            if val is not None:
                responses.append(val)
        if len(responses) >= self.r:
            return responses[0]  # বাস্তবে এখানে সবচেয়ে নতুন ভার্সনটি বেছে নেওয়া হবে
        return None

# ডেমো
store = KVStore(["node-1", "node-2", "node-3", "node-4"])
store.put("user:1001", '{"name": "Alice"}')
store.put("session:abc", '{"token": "xyz"}')

print(f"user:1001 → {store.get('user:1001')}")
print(f"session:abc → {store.get('session:abc')}")
print(f"'user:1001'-এর নোডসমূহ: {store.ring.get_nodes('user:1001')}")
print(f"কোরাম: W={store.w}, R={store.r}, N={store.n}")
print(f"স্ট্রং কনসিস্টেন্সি: W+R > N → {store.w}+{store.r} > {store.n} = {store.w+store.r > store.n}")

Output

user:1001 → {"name": "Alice"}
session:abc → {"token": "xyz"}
'user:1001'-এর নোডসমূহ: ['node-2', 'node-4', 'node-1']
কোরাম: W=2, R=2, N=3
স্ট্রং কনসিস্টেন্সি: W+R > N → 2+2 > 3 = True

Note: ক্যাপ থিওরেম-এর (CAP Theorem) ব্যবহারিক প্রয়োগ: আপনি কখনোই একসাথে কনসিস্টেন্সি (Consistency), অ্যাভেইলেবিলিটি (Availability) এবং পার্টিশন টলারেন্স (Partition tolerance) এর সুবিধা পাবেন না। যখন একটি নেটওয়ার্ক পার্টিশন বা ডাউন থাকে, তখন আপনাকে যেকোনো দুটির মধ্যে একটি বেছে নিতে হয় — CP সিস্টেমগুলো (যেমন: etcd, ZooKeeper) কনসিস্টেন্সি বজায় রাখার জন্য ডেটা রাইট করা বা ডেটা রিসিভ করা বন্ধ করে দেয়; আর AP সিস্টেমগুলো (যেমন: Cassandra, DynamoDB) ডেটা রাইট হওয়া চালু রাখে এবং পরে ডেটা সিঙ্ক করে সবকিছু একত্র করে। বাস্তবিক ব্যবহারের অধিকাংশ ক্ষেত্রে KV স্টোরগুলো এই AP সিস্টেম ব্যবহার করে এবং প্রতিটি রিকোয়েস্টের ওপর ভিত্তি করে কনসিস্টেন্সিকে টিউন (tune) করে নেওয়ার সুযোগ দেয়।