Building Blocksপড়তে ১০ মিনিট লাগবে

কনসিস্টেন্ট হ্যাশিং (Consistent Hashing)

সার্ভার যোগ করার অর্থ এই নয় যে সবকিছু এলোমেলো করতে হবে
scope:বিল্ডিং ব্লক (Building Block)difficulty:ইন্টারমিডিয়েট (Intermediate)

সিম্পল হ্যাশিং (Simple Hashing) নিয়ে সমস্যা

কল্পনা করুন, আপনার ৪টি সার্ভার আছে এবং আপনি সেগুলোতে ডেটা রেন্ডমলি ভাগ করে রাখতে চান। এর সবচেয়ে সাধারণ উপায়: server = hash(key) % 4। "anika" কী (Key)-টিকে হ্যাশ করলে ২ পাওয়া যায়, তাই এটি সার্ভার ২-এ যায়। খুব সহজ।

কিন্তু যখন আপনি আরেকটি সার্ভার যোগ করেন তখন কী হবে? হিসাবটি বদলে গিয়ে হবে hash(key) % 5। হুট করেই আপনার প্রায় প্রত্যেকটি কী অন্য কোনো সার্ভারের দিকে নির্দেশ করবে। "anika" হয়তো এখন সার্ভার ২-এর পরিবর্তে সার্ভার ৩-এ যাবে। এর মানে হলো আপনার অধিকাংশ ডেটাই এক সার্ভার থেকে অন্য সার্ভারে স্থানান্তরিত করতে হবে — যা ডেটার এক বড়সড় পুনর্বিন্যাস (Reshuffling)।

বাস্তব সিস্টেমগুলোতে এই ধরনের রিশাফলিং এক ভয়ংকর ব্যাপার। চিন্তা করুন, ১০০টি সার্ভার এবং বিলিয়ন বিলিয়ন কী সংবলিত একটি ক্যাশ ক্লাস্টারের কথা। একটি মাত্র সার্ভার যোগ করলে সব ক্যাশ ডেটা ইনভ্যালিডেট (Invalidate) হয়ে যাবে, ফলে ক্যাশ স্ট্যাম্পেড (Cache stampede) বা ক্যাশের উপর এমন এক প্রবল চাপ পড়বে যা আপনার ডেটাবেসকে নিমেষেই ডাউন করে দিতে পারে।

কনসিস্টেন্ট হ্যাশিং অত্যন্ত সুন্দরভাবে এই সমস্যার সমাধান করে।

▸ mod N হ্যাশিংয়ের ক্ষেত্রে সমস্যা

হ্যাশ রিং (The Hash Ring)

সংখ্যার একটি লাইনের পরিবর্তে ০ থেকে 2^32 পর্যন্ত একটি বৃত্তের (Ring) কথা কল্পনা করুন। সার্ভার এবং কী, দুটিকেই একটি হ্যাশ ফাংশন ব্যবহার করে এই রিংয়ের ওপর বসানো হয়।

এটি কীভাবে কাজ করে:

  1. সার্ভারগুলোকে রিংয়ে বসান। সার্ভারের নাম/আইপি-কে হ্যাশ করে তার পজিশন নির্ণয় করুন। ধরুন, সার্ভার A-এর পজিশন ১০,০০০; সার্ভার B-এর ৪০,০০০ এবং সার্ভার C-এর ৮০,০০০।
  2. কী-গুলোকে রিংয়ে বসান। প্রতিটি কী-কে হ্যাশ করে তার পজিশন বের করুন। ধরুন "anika" কী-টির পজিশন হয়েছে ২৫,০০০।
  3. মালিককে খুঁজে বের করুন। কী-এর পজিশন থেকে ঘড়ির কাঁটার দিকে (Clockwise) চলতে থাকুন যতক্ষণ না কোনো সার্ভার পাওয়া যায়। ২৫,০০০ পজিশনে থাকা "anika" ঘড়ির কাঁটার দিকে চলতে চলতে ৪০,০০০ পজিশনে থাকা সার্ভার B-কে পাবে। এর মানে, সার্ভার B হলো "anika"-এর মালিক।

এখন আসি মূল জাদুতে: যখন আপনি কোনো সার্ভার যোগ করবেন বা সরিয়ে নেবেন, তখন শুধু নতুন সার্ভার ও আগের সার্ভারের মধ্যবর্তী কী-গুলোই সরানোর প্রয়োজন হবে। সবকিছু রিশাফলিং করার বদলে, মোট ডেটার খুব সামান্য অংশই এর দ্বারা প্রভাবিত হবে।

▸ হ্যাশ রিংয়ে সাজানো সার্ভার
▸ কীগুলো ঘড়ির কাঁটার দিকে ঘুরতে ঘুরতে কাছাকাছি সার্ভারকে খুঁজে বের করে

কনসিস্টেন্ট হ্যাশিংয়ের ইমপ্লিমেন্টশন

import hashlib
from bisect import bisect_right


class ConsistentHash:
    def __init__(self, num_virtual_nodes=150):
        self.num_vnodes = num_virtual_nodes
        self.ring = {}        # hash_value -> server_name
        self.sorted_keys = [] # sorted hash positions on the ring


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


    def add_server(self, server: str):
        """Add a server to the ring with virtual nodes."""
        for i in range(self.num_vnodes):
            vnode_key = f"{server}:vnode{i}"
            h = self._hash(vnode_key)
            self.ring[h] = server
            self.sorted_keys.append(h)
        self.sorted_keys.sort()


    def remove_server(self, server: str):
        """Remove a server and its virtual nodes."""
        for i in range(self.num_vnodes):
            vnode_key = f"{server}:vnode{i}"
            h = self._hash(vnode_key)
            del self.ring[h]
            self.sorted_keys.remove(h)


    def get_server(self, key: str) -> str:
        """Find which server owns this key (walk clockwise)."""
        if not self.ring:
            raise Exception("No servers available")
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h)
        if idx == len(self.sorted_keys):
            idx = 0  # Wrapped around the ring
        return self.ring[self.sorted_keys[idx]]


# Demo
ch = ConsistentHash(num_virtual_nodes=150)
ch.add_server("server-A")
ch.add_server("server-B")
ch.add_server("server-C")


# Check where keys land
for key in ["user:1", "user:2", "user:3", "photo:42", "session:abc"]:
    print(f"{key} -> {ch.get_server(key)}")


print("\n--- Adding server-D ---")
ch.add_server("server-D")
for key in ["user:1", "user:2", "user:3", "photo:42", "session:abc"]:
    print(f"{key} -> {ch.get_server(key)}")
# Only ~25% of keys should be remapped (1/4 since there are 4 servers)
Output
user:1 -> server-A
user:2 -> server-C
user:3 -> server-B
photo:42 -> server-A
session:abc -> server-C

--- Adding server-D ---
user:1 -> server-A
user:2 -> server-C
user:3 -> server-D
photo:42 -> server-A
session:abc -> server-C
▸ একটি সার্ভার যুক্ত করা — সবচেয়ে কম ডেটা স্থানান্তর

ভার্চুয়াল নোড (Virtual Nodes)

প্রাথমিক কনসিস্টেন্ট হ্যাশিং-এ একটি বড় সমস্যা দেখা যায়: সার্ভারগুলো রিংয়ের ওপর অসমভাবে ছড়িয়ে থাকতে পারে। যদি সার্ভার A এবং সার্ভার B একে অপরের ভীষণ কাছাকাছি চলে আসে, তাহলে দেখা যাবে সার্ভার A খুব ছোট একটা অংশ সামলাচ্ছে, অন্যদিকে সার্ভার C রিংয়ের বিশাল একটা অংশ জুড়ে আছে। এতে করে সার্ভারগুলোর মধ্যে লোড ডিস্ট্রিবিউশন আনব্যালান্সড হয়ে যায়।

ভার্চুয়াল নোড এই সমস্যার সমাধান করে। রিংয়ে প্রতিটি সার্ভারকে একবার করে না বসিয়ে, সেগুলো অনেকবার (হতে পারে ১০০-২০০টি কপি) বসানো হয়। প্রতিটি কপিকেই একটি ভার্চুয়াল নোড বলা হয়। সার্ভার A এর জন্য "A:vnode0", "A:vnode1", ..., থেকে শুরু করে "A:vnode149" পর্যন্ত পজিশন থাকে।

সার্ভারপ্রতি ১৫০টি করে ভার্চুয়াল নোড থাকার ফলে পজিশনগুলো রিংজুড়ে খুব সমানভাবে ছড়িয়ে থাকে। ফলে লোড ডিস্ট্রিবিউশনটিও অনেক বেশি ইউনিফর্ম হয় — সাধারণত দুই সার্ভারের মধ্যে ৫-১০% এর বেশি ভ্যারিয়্যান্স থাকে না।

ভার্চুয়াল নোড ব্যবহার করে হেটেরোজিনিয়াস সার্ভার (Heterogeneous servers) বা ভিন্ন ভিন্ন সক্ষমতার সার্ভার হ্যান্ডেল করাটাও সহজ হয়। একটি শক্তিশালী সার্ভারকে ৩০০টি ভার্চুয়াল নোড দেওয়া যেতে পারে, যেখানে তুলনামূলক দুর্বল একটি সার্ভারকে ১০০টি ভার্চুয়াল নোড দেওয়া হলো, যার ফলে শক্তিশালী সার্ভারটি অনেক বেশি ট্র্যাফিক রিসিভ করতে পারে।

▸ সমানভাবে লোড বিতরণের জন্য ভার্চুয়াল নোড
Note: ভার্চুয়াল নোডকে এভাবে ভাবতে পারেন: মিউজিকাল চেয়ার খেলায় একটি বাচ্চা একটি মাত্র চেয়ার দখল করার বদলে, প্রতিটি বাচ্চাকে একাধিক চেয়ারে তার জ্যাকেট রাখতে দেওয়া হয়। যখন গান থামে, তখন কোনো বাচ্চার পক্ষে চেয়ার পাওয়ার সম্ভাবনা অনেক বেড়ে যায় — এবং চেয়ারগুলো দারুণভাবে সব খেলোয়াড়দের মধ্যে সমান হারে দখল হয়।

সার্ভার যোগ-বিয়োগের সময় আসলে কী ঘটে?

সার্ভার যোগ করা: নতুন যোগ করা সার্ভারটি তার ঠিক ঘড়ির কাঁটার দিকের প্রতিবেশী সার্ভার থেকে কিছু কী নিজের দায়িত্বে নিয়ে নেয়। ঠিক ওই নির্দিষ্ট কীগুলো ছাড়া অন্য আর কোনো কিছুই নড়ে না। N সংখ্যক সার্ভারের ক্ষেত্রে, একটি সার্ভার যোগ করলে মোট কী-এর মাত্র ~1/N অংশ জায়গা পরিবর্তন করে। এর সাথে মডুলার হ্যাশিংয়ের তুলনা করে দেখুন, যেখানে প্রায় প্রতিটি কী-কেই জায়গা পরিবর্তন করতে হতো!

সার্ভার রিমুভ করা: যে সার্ভারটিকে রিমুভ করা হলো, তার কাছে থাকা কীগুলো সেটির ঘড়ির কাঁটার দিকের প্রতিবেশী সার্ভারের কাছে চলে যায়। এক্ষেত্রেও শুধুমাত্র ~1/N অংশ কী প্রভাবিত হয়।

চলুন, ১০০টি সার্ভার এবং ১মিলিয়ন (১০ লক্ষ) কী নিয়ে অংকটি করে দেখি:

  • মডুলার হ্যাশিং: একটি সার্ভার যোগ করা হলো → প্রায় ৯,৯০,০০০টি (৯৯%) কী জায়গা বদলায়।
  • কনসিস্টেন্ট হ্যাশিং: একটি সার্ভার যোগ করা হলো → প্রায় ১০,০০০টি (১%) কী জায়গা বদলায়।

এটি ৯৯ গুণ কম! একটি ক্যাশ ক্লাস্টারে এর মানে হলো আপনার ক্যাশের ৯৯% একদম অক্ষত থাকবে এবং সেগুলো ইনভ্যালিড হবে না। এর ফলে আপনার ডেটাবেসে কোনো প্রভাবই পড়বে না।

বাস্তব অ্যাপ্লিকেশন (Real-World Use Cases)

ডিস্ট্রিবিউটেড সিস্টেমের আনাচকানাচে কনসিস্টেন্ট হ্যাশিং ব্যবহার করা হয়:

অ্যামাজন ডাইনামো ডিবি (Amazon DynamoDB) — স্টোরেজ নোডগুলোতে ডেটা বণ্টন করতে কনসিস্টেন্ট হ্যাশিং ব্যবহার করে। একটি নোড যোগ করা হলে বা রিমুভ করা হলে, শুধু আশপাশের পার্টিশনগুলোতে প্রভাব পড়ে।

অ্যাপাচি ক্যাসান্ড্রা (Apache Cassandra) — প্রতিটি নোডকে একটি হ্যাশ রিংয়ে বসানো হয়। পার্টিশন কী-এর হ্যাশের ওপর নির্ভর করে ডেটাগুলো স্বয়ংক্রিয়ভাবে নিজেদের মধ্যে বণ্টন করে নেয়। কোনো নোড যুক্ত করার সময় খুব সামান‍্য ডেটাই মাইগ্রেশন করতে হয়।

আকামাই CDN — এটি কনসিস্টেন্ট হ্যাশিংয়ের একেবারে শুরুর দিকের ব্যবহারকারীদের একটি! কোন এর সার্ভার কোন কন্টেন্ট ক্যাশ করে রাখবে তা ঠিক করতে তারা কনসিস্টেন্ট হ্যাশিং ব্যবহার করে। এটি তাদের ১৯৯৭ সালের অরিজিনাল পেপারে উল্লেখ রয়েছে।

ডিসকর্ড (Discord) — নির্দিষ্ট সার্ভার প্রসেসে ইউজারদের রাউট করার কাজে কনসিস্টেন্ট হ্যাশিং ব্যবহার করে। যখন তারা ক্যাপাসিটি বৃদ্ধি করে, তখন খুব অল্প সংখ্যক ইউজারকেই নতুন সার্ভিসের সাথে ব্যালেন্স করতে হয়।

লোড ব্যাল্যান্সার (Load Balancers) — কিছু কিছু লোড ব্যাল্যান্সার সেশন অ্যাফিনিটি (Session Affinity) নিশ্চিত করার জন্য কনসিস্টেন্ট হ্যাশিং ব্যবহার করে। সিম্পল হ্যাশ-মডের রিশাফলিং এর ঝামেলা এড়িয়ে একই কী (যেমন ইউজার আইডি, সেশন আইডি) সবসময় একই ব্যাকএন্ড সার্ভারে ম্যাপ করা হয়।

Note: ইন্টারভিউ টিপস: আপনি যখন কোনো ইন্টারভিউতে কনসিস্টেন্ট হ্যাশিংয়ের কথা তুলবেন, তখন এটি কেন দরকার (ভয়াবহ রিশাফলিং এড়ানোর জন্য), এটি কীভাবে কাজ করে (হ্যাশ রিং, ঘড়ির কাঁটার দিকে চেক করা) তা সুস্পষ্টভাবে ব্যাখ্যা করবেন। এবং হ্যাঁ, ভার্চুয়াল নোড (ইভেন ডিস্ট্রিবিউশন) এর কথা উল্লেখ করতে কখনোই ভুলবেন না। বোনাস পয়েন্ট হিসেবে 1/N অংশ কী জায়গা পরিবর্তনের ব্যাপারটি উল্লেখ করতে পারেন।

Key Metrics

কী লুকআপ (Key lookup)
সাজানো রিংয়ে বাইনারি সার্চ
\(O(\log N)\) \(O(\log N)\)
সার্ভার যুক্ত করা
V = প্রতি সার্ভারে ভি-নোড (virtual nodes) এর সংখ্যা
\(O(V \log N)\) \(O(V \log N)\)
সার্ভার বাদ দেওয়া
V সংখ্যক ভি-নোড মুছে ফেলুন
\(O(V \log N)\) \(O(V \log N)\)
সার্ভার যুক্ত করার সময় কীর স্থান পরিবর্তন (Modular)
প্রায় সবকিছু জায়গা বদলায়
~(N-1)/N keys —
সার্ভার যুক্ত করার সময় কীর স্থান পরিবর্তন (Consistent)
খুব সামান্যই পরিবর্তন হয়
~1/N keys —
সার্ভার প্রতি স্থান (Space per server)
১৫০-২০০টি ভি-নোড সাধারণত রাখা হয়
\(O(V)\) \(O(V)\)

ছোট কুইজ

১০টি সার্ভারে কনসিস্টেন্ট হ্যাশিং ব্যবহার করার সময় যখন একটি ১১তম সার্ভার যোগ করা হয়, আপনার কী মনে হয় ঠিক কত শতাংশ কী জায়গা বদলায়?

পড়া চালিয়ে যান