Part 2 · ডেটাবেস 📖 ১৩ মিনিট পড়া 📝 ২০টি কুইজ

Consistent Hashing

Server যোগ/সরালে minimum data move — distributed system-এর জাদু।

📝 কুইজে যান

আপনি ৪টি cache server-এ data বিতরণ করছেন: shard = hash(key) % 4। হঠাৎ এক server fail — এখন ৩টি। সূত্র বদলে % 3। কিন্তু এতে প্রায় সব key-এর shard বদলে গেছে — ৭৫% data move করতে হবে! এই সমস্যার সমাধান Consistent Hashing।

সাধারণ Hashing-এর সমস্যা

Modulo-based hashing-এ:

  • Server N থেকে N+1: প্রায় সব key-এর location বদলায়।
  • ৪ → ৫ server-এ ~৮০% key reshuffle।
  • Resharding = downtime + massive data movement।

Consistent Hashing কী?

Consistent Hashing (১৯৯৭, MIT) — একটি hashing technique যেখানে server যোগ/সরালে শুধু K/N data remap হয় (K = total keys, N = total servers)। অন্যদের location অপরিবর্তিত।

কীভাবে কাজ করে?

Step 1: Hash Ring

একটি virtual circular ring কল্পনা করুন — ০ থেকে 2³² পর্যন্ত (hash space)।

Step 2: Server Placement

প্রতিটি server-এর IP/name-এর hash → ring-এ একটা position।

Server A (hash=10°) / 0° ----+---- 90° | | 270° -+---+- 180° \\ Server B (hash=200°) Server C (hash=300°)

Step 3: Key Placement

Key-এর hash → ring-এ position। তারপর clockwise এগিয়ে first server-এ যায়।

Step 4: Server যোগ/সরালে

নতুন server যোগ → ring-এর একটা specific section-এর key-গুলো নতুন server-এ যায়। বাকি সব key অপরিবর্তিত।

Virtual Nodes (vNodes)

Naive consistent hashing-এ ৩টি server-এ uniformly distribute হবে না — কেউ ৫০%, কেউ ১০%। সমাধান:

প্রতিটি physical server-কে ring-এ ১০০-৫০০ virtual node position দেওয়া। প্রতিটি vNode আলাদা hash position।

  • সুবিধা: Better load distribution।
  • Heterogeneous server: Powerful server-এ বেশি vNode → বেশি traffic।
  • Smooth rebalance: Server fail হলে — তার vNode-গুলোর data many server-এ ছড়িয়ে যায়।

সুবিধা

  • Minimal remapping: Server যোগ/সরালে — শুধু K/N data move।
  • Scalability: Cluster gradually grow।
  • Fault tolerance: Server fail = তার data automatically next server-এ।
  • Load balancing: Uniform distribution (vNode-এ)।
  • No central coordinator: Distributed-friendly।

Replication-এর সাথে

প্রতিটি key shorter path-এর প্রথম N server-এ replicate হয়। একটা fail হলে next server থেকে serve।

Key X → Server A (primary), Server B (replica), Server C (replica) A fail → B promotes / C reads

Consistent vs Naive Hashing

Naive (modulo)

  • Server change = ~80% remap
  • Static cluster-এ OK
  • Implementation সহজ
  • Distributed scale-এ unsuitable

Consistent Hashing

  • Server change = K/N remap
  • Dynamic cluster-এ ideal
  • Implementation complex
  • Distributed system standard

বাস্তব ব্যবহার

  • Amazon DynamoDB: Internally consistent hashing।
  • Apache Cassandra: Cassandra-র key distribution-এর core।
  • Memcached: Client-side consistent hashing।
  • Akamai CDN: Server selection।
  • Discord: Cassandra cluster (consistent hashing দিয়ে)।
  • Apache Riak: Distributed KV store।

আধুনিক বিকল্প

Rendezvous Hashing

Highest Random Weight (HRW) — প্রতি key-এ সব server-এর hash compute করে highest-কে select। সরল কিন্তু O(N)।

Jump Hash

Google-এর জন্য তৈরি — খুব fast, কিন্তু server অর্ডার fixed।

Maglev Hashing

Google's load balancer hashing।

Implementation

সরল pseudo-code:

class ConsistentHash: def __init__(self): self.ring = SortedDict() # hash → server def add_server(self, server, vnodes=150): for i in range(vnodes): h = hash(f"{server}#{i}") self.ring[h] = server def get_server(self, key): h = hash(key) # Find first server with hash >= h (clockwise) idx = self.ring.bisect_right(h) if idx == len(self.ring): idx = 0 return self.ring.values()[idx]

সাধারণ ভুল ধারণা

  1. "Consistent hashing automatic load balance": Without vNode → uneven distribution।
  2. "Implementation সরল": Production-grade hard — বাঁচানোর জন্য library use করুন।
  3. "Always uses MD5/SHA": Fast non-crypto hash (MurmurHash, xxHash) preferred।

Best Practices

  • Virtual nodes ব্যবহার করুন (১০০-৫০০ vNode per physical server)।
  • Fast non-cryptographic hash (MurmurHash3)।
  • Replication factor 3 (typical)।
  • Monitor per-server load — uneven হলে vNode count adjust।
  • Established library (jump hash, hashring) — reinvent করবেন না।

📌 চ্যাপ্টার সারমর্ম

  • Consistent Hashing = server change-এ minimal data movement।
  • Hash ring + clockwise lookup।
  • Virtual nodes uniform distribution + smooth failover।
  • DynamoDB, Cassandra, Memcached — সবাই use করে।
  • Distributed cache/DB-এর foundation।