কনসিস্টেন্ট হ্যাশিং

১ · সমস্যা — naive mod hashing

একটি ডিস্ট্রিবিউটেড ক্যাশ বা ডেটাবেসে N-টি সার্ভার থাকলে, একটি সহজ পদ্ধতি হলো Mod HashingMod Hashingএকটি কী কোন সার্ভারে যাবে তা ঠিক করতে hash(key) % N (N = সার্ভার সংখ্যা) ব্যবহার করা — সহজ, কিন্তু N বদলালে প্রায় সব ম্যাপিং ভেঙে যায়। — প্রতিটি কী-এর হ্যাশ মান নিয়ে সার্ভার সংখ্যা দিয়ে মড করে ফেলা, ফলাফল যা আসবে সেই সার্ভারে কী-টি সংরক্ষণ করা। এটি সহজ, কিন্তু একটি মারাত্মক দুর্বলতা আছে — যখনই N বদলায় (একটি সার্ভার যোগ বা বাদ দেওয়া হয়), প্রায় প্রতিটি কী-এর জন্য hash(key) % N-এর মান বদলে যায়, ফলে প্রায় সব কী ভিন্ন সার্ভারে "সরে যায়"।

২ · সমাধান — হ্যাশ রিং ও কনসিস্টেন্ট হ্যাশিং

Consistent HashingConsistent Hashingসার্ভার ও কী উভয়কেই একটি কাল্পনিক বৃত্তাকার হ্যাশ-স্পেস ("রিং")-এ ম্যাপ করার কৌশল, যেখানে প্রতিটি কী রিং-এ তার অবস্থান থেকে ক্লকওয়াইজ দিকে প্রথম যে সার্ভার পায় সেখানে সংরক্ষিত হয় — একটি সার্ভার যোগ/বাদ দিলে শুধু সংলগ্ন অংশের কীগুলোই প্রভাবিত হয়। পদ্ধতিতে একটি বিশাল বৃত্তাকার নাম্বার-স্পেস (রিং) কল্পনা করা হয়। প্রতিটি সার্ভারকে (তার নাম হ্যাশ করে) রিং-এর একটি পজিশনে বসানো হয়। একটি কী সংরক্ষণ করতে, সেই কী-টিকেও হ্যাশ করে রিং-এ বসানো হয়, এবং সেখান থেকে ক্লকওয়াইজ দিকে ঘুরে প্রথম যে সার্ভার পাওয়া যায় সেটিই তার মালিক।

একটি নতুন সার্ভার যোগ করলে, সে শুধু রিং-এর তার নিজের অবস্থান ও তার ঠিক আগের সার্ভারের মাঝের কী-গুলোকেই "দখল" করে — বাকি সব সার্ভারের মালিকানাধীন কী অপরিবর্তিত থাকে। এটাই মূল কারণ কেন এটি এত কম কী রিম্যাপ করে।

৩ · ওয়ার্কড এক্সাম্পল — ৩ থেকে ৪ সার্ভার

ধরুন $n$ সংখ্যক সার্ভার আছে এবং একটি নতুন সার্ভার যোগ করা হচ্ছে। naive mod hashing-এ গড়ে প্রায় $\dfrac{n}{n+1}$ ভগ্নাংশ কী রিম্যাপ হয়, আর কনসিস্টেন্ট হ্যাশিং-এ মাত্র $\dfrac{1}{n+1}$ ভগ্নাংশ কী রিম্যাপ হয়। $n=3$ হলে:

• naive mod hashing: $\dfrac{3}{4} = 75\%$ কী রিম্যাপ হয়
• কনসিস্টেন্ট হ্যাশিং: $\dfrac{1}{4} = 25\%$ কী রিম্যাপ হয়

এটি শুধু তত্ত্ব নয় — নিচের কোড সেলে উভয় পদ্ধতিই বাস্তবে সিমুলেট করে হিসাব করা হয়েছে, ধরে নেওয়া বা মুখস্থ করা নয়।

import hashlib
import bisect

def hash_val(text):
    return int(hashlib.md5(text.encode()).hexdigest(), 16)

# ---------- ১) Naive mod hashing ----------
def naive_server(key, num_servers):
    return hash_val(key) % num_servers

keys = [f"key-{i}" for i in range(5000)]

naive_changed = sum(
    1 for k in keys if naive_server(k, 3) != naive_server(k, 4)
)
naive_fraction = naive_changed / len(keys)

# ---------- ২) কনসিস্টেন্ট হ্যাশিং (হ্যাশ রিং + ভার্চুয়াল নোড) ----------
class HashRing:
    def __init__(self, servers, vnodes=150):
        self.vnodes = vnodes
        self.ring = {}
        self.sorted_positions = []
        for server in servers:
            self.add_server(server)

    def add_server(self, server):
        for i in range(self.vnodes):
            pos = hash_val(f"{server}#vnode{i}")
            self.ring[pos] = server
            bisect.insort(self.sorted_positions, pos)

    def get_server(self, key):
        pos = hash_val(key)
        idx = bisect.bisect(self.sorted_positions, pos)
        if idx == len(self.sorted_positions):
            idx = 0
        return self.ring[self.sorted_positions[idx]]

servers_3 = ["server-0", "server-1", "server-2"]
servers_4 = servers_3 + ["server-3"]

ring_3 = HashRing(servers_3)
ring_4 = HashRing(servers_4)

ch_changed = sum(
    1 for k in keys if ring_3.get_server(k) != ring_4.get_server(k)
)
ch_fraction = ch_changed / len(keys)

print(f"মোট কী: {len(keys):,}")
print(f"Naive mod hashing (৩→৪ সার্ভার) রিম্যাপ হয়েছে: {naive_changed:,} টি কী ({naive_fraction:.1%})")
print(f"কনসিস্টেন্ট হ্যাশিং (৩→৪ সার্ভার) রিম্যাপ হয়েছে: {ch_changed:,} টি কী ({ch_fraction:.1%})")

৪ · কোথায় ব্যবহৃত হয়

কনসিস্টেন্ট হ্যাশিং ডিস্ট্রিবিউটেড ক্যাশ (Memcached ক্লায়েন্ট লাইব্রেরি), ডিস্ট্রিবিউটেড ডেটাবেস (Cassandra, DynamoDB), এবং লোড ব্যালেন্সারে (কোন সার্ভার কোন ব্যাকএন্ড হ্যান্ডল করবে তা ঠিক করতে) ব্যাপকভাবে ব্যবহৃত হয়। L17-এ hash-based sharding-এ এই একই "রিব্যালেন্সিং" সমস্যা আবার ফিরে আসবে, যেখানে কনসিস্টেন্ট হ্যাশিং একটি প্রধান সমাধান।