هذا المقال يتطلب مستوى محترف. لو بتشتغل على 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% من المفاتيح

لو عملت نفس التجربة بـ hash(key) % N هتلاقي النسبة قريبة من 80%. الفرق ده هو اللي بيفصل بين الـ DB اللي بتفضل واقفة والـ DB اللي بتقع وقت الـ scaling.

ليه Virtual Nodes مش رفاهية

لو حطّيت كل سيرفر كنقطة واحدة على الحلقة، التوزيع بيطلع غير متوازن: ممكن سيرفر يشيل 40% والتاني 12%. السبب إن المواقع عشوائية مش متباعدة بانتظام. الحل إنك تحط لكل سيرفر عدد كبير من النقاط الافتراضية (vnodes)، كل واحدة بـ hash مختلف، وكلها بتأشّر لنفس السيرفر الحقيقي. الافتراض إن 100 إلى 200 vnode لكل سيرفر بينزّل الانحراف المعياري في التوزيع لأقل من 5%. في الكود فوق استخدمنا 150، وده الرقم اللي بتستخدمه مكتبات زي Ketama عمليًا.

الـ trade-offs اللي لازم تعرفها

• ذاكرة مقابل توازن: كل vnode entry في الـ ring بياخد ذاكرة. 200 سيرفر × 150 vnode = 30 ألف entry. بتكسب توزيع متوازن، بتخسر ذاكرة وزمن إعادة بناء الحلقة عند كل تغيير.
• زمن البحث: الـ get بقى O(log V) بدل O(1) بتاعة الـ modulo. على 30 ألف نقطة، ده ~15 مقارنة، أقل من ميكروثانية. مقبول، بس مش مجاني.
• إعادة التوزيع مش صفر: Consistent Hashing بيقلّل الحركة، مش بيلغيها. لسه فيه k/n مفتاح بتتحرك، والـ DB لازم تستحمل الموجة الصغيرة دي.
• hot keys: لو مفتاح واحد عليه ضغط شرس، أي خوارزمية توزيع مش هتنقذك. ده مشكلة منفصلة محتاجة replication أو local cache.

متى لا تستخدم هذه الطريقة

لو عدد السيرفرات عندك ثابت ومش هيتغير (مثلاً جدول داخلي ثابت)، الـ hash % N أبسط وأسرع ومفيش سبب تعقّد حياتك. كمان لو محتاج توزيع دقيق ومضبوط بنسب محددة لكل سيرفر بسبب اختلاف أحجام الأجهزة، فكّر في bounded-load consistent hashing أو rendezvous hashing بدلها. وأخيرًا، لو بياناتك صغيرة وكلها تدخل في سيرفر واحد، الموضوع كله over-engineering.

الخطوة التالية

افتح طبقة الـ caching عندك ودوّر على % N في كود التوزيع. لو لقيتها وعندك أكتر من سيرفر بيتغير عددهم، استبدلها بالـ ConsistentHash فوق وشغّل تجربة الـ 100 ألف مفتاح قبل وبعد إضافة سيرفر. لو النسبة طلعت قريبة من 1/N، انت كده وفّرت على الـ DB موجة miss كاملة في كل scaling event.

المصادر

• Karger et al., "Consistent Hashing and Random Trees" (1997) — الورقة الأصلية وخاصية إعادة توزيع k/n مفتاح فقط.
• DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (2007) — استخدام Consistent Hashing مع Virtual Nodes في الإنتاج.
• High Scalability — Consistent hashing algorithm: شرح الحلقة والبحث في اتجاه عقارب الساعة.
• Carlos Galdino — Consistent Hashing: تفصيل دور الـ virtual nodes في توازن الحمل.