هذا المقال يتطلب مستوى محترف. لو بتشتغل على caching موزّع أو sharding لقواعد بيانات، الكلام ده بيخصك مباشرة.
Consistent Hashing: وزّع المفاتيح من غير ما تنهار الكاش
لو شيلت أو ضفت سيرفر واحد على Cache موزّع بـ hash(key) % N، انت على وشك تعيد توزيع تقريبًا كل المفاتيح في نفس اللحظة. النتيجة: cache miss storm بيضرب ال_database ورا الكاش ويوقّعها. Consistent Hashing بيحل ده بحيث إن إضافة سيرفر بتحرّك 1/N من المفاتيح فقط بدل ~80%.
المشكلة باختصار
الطريقة الشائعة لتوزيع مفتاح على N سيرفر هي server = hash(key) % N. سهلة وسريعة. لكنها بتفشل في لحظة واحدة: لما N تتغير. لو كان عندك 4 سيرفرات وضفت الخامس، المقام بقى 5 بدل 4، فناتج % N اتغير لمعظم المفاتيح. كل مفتاح اتغيّر سيرفره يبقى cache miss، والطلب بيروح للـ DB. على 4 سيرفرات + 1 جديد، النسبة اللي بتتحرك بتوصل لحوالي 80%.
الفكرة بمثال بسيط الأول
تخيّل ساعة حائط دائرية. حطّينا عليها 3 موظفين في مواقع مختلفة على الإطار. وصل خطاب، نحطّه عند رقمه على الإطار، وبعدين نمشي مع عقارب الساعة لحد ما نوصل لأول موظف قدامنا، وهو اللي يستلمه. لو موظف راح في إجازة، الخطابات اللي كانت بتروح له بس هي اللي تنتقل للموظف اللي بعده على الدائرة. باقي الموظفين مالهومش دعوة، وخطاباتهم ما اتحركتش. ده بالظبط هو Consistent Hashing.
علميًا: بنرسم فضاء hash دائري من 0 لـ 2^32. كل سيرفر بياخد موقع على الدائرة من hash(server_id). كل مفتاح بياخد موقعه من hash(key)، وبيتبع أول سيرفر في اتجاه عقارب الساعة. الخوارزمية اتنشرت أول مرة في ورقة David Karger وزملائه سنة 1997، وانتشرت عمليًا بعد ورقة Amazon Dynamo سنة 2007. الخاصية الأساسية: عند تغيّر عدد السيرفرات من n، بيتحرك k/n مفتاح فقط (k = عدد المفاتيح)، مش كلهم.
كود Python شغّال
تطبيق كامل بـ ring مرتّب و binary search للبحث في O(log V)، حيث V عدد النقاط على الحلقة.
import hashlib
from bisect import bisect, insort
class ConsistentHash:
def __init__(self, nodes=None, vnodes=150):
self.vnodes = vnodes # نقاط افتراضية لكل سيرفر
self.ring = {} # hash -> اسم السيرفر
self._sorted = [] # قائمة الـ hashes مرتّبة
def _hash(self, key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#{i}")
self.ring[h] = node
insort(self._sorted, h)
def remove(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#{i}")
del self.ring[h]
self._sorted.remove(h)
def get(self, key):
if not self.ring:
return None
h = self._hash(key)
idx = bisect(self._sorted, h) % len(self._sorted)
return self.ring[self._sorted[idx]]
# قياس فعلي: كام مفتاح بيتنقل لما نضيف سيرفر خامس؟
ch = ConsistentHash()
for n in ["s1", "s2", "s3", "s4"]:
ch.add(n)
keys = [f"user:{i}" for i in range(100_000)]
before = {k: ch.get(k) for k in keys}
ch.add("s5")
moved = sum(1 for k in keys if ch.get(k) != before[k])
print(f"اتحرك {moved/len(keys)*100:.1f}% من المفاتيح")
# الناتج التقريبي: اتحرك 19.8% من المفاتيح
