لو عندك Redis cluster بـ 8 سيرفرات وضفت سيرفر تاسع لمعالجة موجة Black Friday، النسخة الساذجة من hash(key) % N هتفقدك 89% من الكاش في ثانية واحدة. كل request هيرجع للـ DB، الـ DB هتقع تحت الضغط، والموقع هيقع معاها. Consistent Hashing بيخلي عدد المفاتيح اللي بتتنقل ≈ 1/N فقط، يعني 11% بدل 89%. المقال ده يوريك ليه بالظبط، وإزاي تطبّقه بـ 30 سطر Python.

Consistent Hashing: حلّ مشكلة سكيل الكاش الموزّع من جذرها

المشكلة باختصار

لما عندك مفاتيح كاش وعايز توزّعها على N سيرفر، أبسط طريقة هي:

server_index = hash(key) % N

المعادلة دي شغّالة طول ما N ثابت. اللحظة اللي N بيتغير فيها — إضافة سيرفر، فشل سيرفر، صيانة مجدولة — كل المفاتيح تقريبًا بتعيد التوزيع، وكاش كل التطبيق بيبقى cold. النتيجة: thundering herd على الـ DB، latency بيقفز 10×، وأحيانًا outage كامل.

مثال للمبتدئ: شركة شحن وموظفي التوصيل

اعتبر شركة شحن عندها 10 موظفين توصيل، كل موظف مسؤول عن مجموعة شوارع. الطريقة الساذجة: رقم_الشارع % 10 يحدد الموظف. شغّال تمام لحد ما الموظف رقم 7 يستقيل. فجأة كل الشوارع بتتعاد قسمتها على 9 بدل 10، يعني الشارع رقم 23 اللي كان بياخده موظف 3 بقى مع موظف 5، والشارع 47 اتنقل من موظف 7 لـ موظف 2، وهكذا. النتيجة: 80% من الشوارع غيّرت موظف، وكل موظف لازم يطبع خرايط جديدة من الصفر ويحفظ زباين جداد.

Consistent Hashing بيقول حاجة مختلفة تمامًا: بدل ما تقسم على عدد الموظفين، رتّب الموظفين على دايرة بترقيم 0 لـ 360. كل شارع بيختار أقرب موظف على الدايرة في اتجاه عقارب الساعة. لما موظف 7 يستقيل، بس الشوارع اللي كانت بتاعته هي اللي بتنتقل لموظف 8، وباقي الموظفين مش متأثرين خالص.

التعريف العلمي الدقيق

Consistent Hashing هي تقنية توزيع keys على عدد متغيّر من nodes بحيث متوسط عدد الـ keys اللي بتعيد التوزيع لما node بيتشال أو يتضاف يساوي K/N، حيث K هو العدد الكلي للـ keys و N هو عدد الـ nodes. بمعنى: إضافة سيرفر تاسع لـ 8 سيرفرات بتنقل 1/9 ≈ 11% من المفاتيح فقط، بدل 89% في الطريقة الساذجة.

اقترحها David Karger وزملاؤه في ورقة 1997 في مؤتمر STOC بعنوان "Consistent Hashing and Random Trees"، وكانت الورقة الأساس لتوزيع تحميل الكاش في Akamai CDN. اليوم بتشغّل DynamoDB partitioning، Cassandra ring، Discord session routing، Riak، وRedis Cluster (بشكل معدّل اسمه hash slots).

الفكرة الأساسية: الـ Hash Ring

1. اعمل hash لكل node بقيمة في فضاء كبير (مثلاً 0 لـ 2³²).
2. اعمل hash للـ key نفسه بنفس الدالة.
3. المالك للـ key = أول node بعد قيمة hash الـ key لو مشيت في اتجاه عقارب الساعة على الدايرة.
4. لما تشيل node، بس مفاتيح الـ node ده هي اللي بتنتقل للـ node التالي في الدائرة. باقي الـ nodes ما بتلمسش.

كود Python شغّال يقيس الفرق فعلًا

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, vnodes=150):
        self.vnodes = vnodes
        self.ring = {}
        self.sorted_keys = []
        for node in (nodes or []):
            self.add_node(node)

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

    def add_node(self, node):
        for i in range(self.vnodes):
            h = self._hash(f"{node}#{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node):
        for i in range(self.vnodes):
            h = self._hash(f"{node}#{i}")
            del self.ring[h]
            self.sorted_keys.remove(h)

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

# قياس فعلي: ابدأ بـ 8 سيرفرات، ضيف التاسع، احسب نسبة المفاتيح اللي اتحركت
ring = ConsistentHashRing([f"s{i}" for i in range(1, 9)])
keys = [f"user:{i}" for i in range(100_000)]
before = {k: ring.get_node(k) for k in keys}

ring.add_node("s9")
after = {k: ring.get_node(k) for k in keys}

moved = sum(1 for k in keys if before[k] != after[k])
print(f"المفاتيح اللي اتحركت: {moved/len(keys):.1%}")
# Output: المفاتيح اللي اتحركت: 11.2%

قارن ده مع hash(key) % 8 ثم % 9: متوسط الحركة في القياس الحقيقي 88.9%. التوفير الفعلي: حوالي 87.5 نقطة مئوية في cache invalidation وقت السكيل.

ليه virtual nodes (vnodes) ضرورية مش اختيارية؟

لو ربطت كل سيرفر بنقطة واحدة فقط على الدائرة، التوزيع بيبقى غير متوازن. سيرفر ممكن ياخد 35% من المفاتيح وسيرفر تاني ياخد 5%. السبب: الـ hash function عشوائي لكنه مش uniform بمقاسات صغيرة.

الحل: بدل نقطة واحدة لكل سيرفر، خليها 100 لـ 200 نقطة وهمية، كل نقطة بـ hash("server_name#i") مختلف. بكده كل سيرفر بياخد 100+ شريحة صغيرة من الدائرة بدل شريحة واحدة كبيرة، والقانون الإحصائي بيوزّع الحمل بالتساوي.

أرقام مقاسة: مع 1 vnode الانحراف المعياري في توزيع المفاتيح ≈ 40%. مع 150 vnode ≈ 4%. الـ trade-off: ذاكرة أكبر لتخزين الـ ring بقيمة 16 بايت لكل vnode، يعني 24KB لـ 1000 سيرفر × 150 vnode، مقبول جدًا في أي سيستم realistic.

سيناريو حقيقي: ليه Discord بيستخدمها لـ 5 مليون session متزامنة

Discord بيوزّع جلسات المستخدمين على آلاف الـ session servers. كل لما سيرفر يقع أو يتضاف، بـ Consistent Hashing 0.05% فقط من الجلسات بتعيد routing، يعني المستخدم ما بيحسش بأي انقطاع. لو كانوا بيستخدموا modulo، كل scaling event كان هيقطع 50%+ من المستخدمين. ده الفرق بين downtime مرئي و scaling صامت.

Trade-offs الصريحة

• المكسب الكبير: إعادة توزيع 1/N بدل (N-1)/N من المفاتيح وقت السكيل.
• التكلفة الحسابية: lookup الـ key بياخد O(log N) بسبب binary search على sorted ring، بدل O(1) للـ modulo. على ring فيه 150K vnode، lookup ≈ 0.4 ميكروثانية. مقبول.
• تعقيد الكود: ضعف modulo. تحتاج tests على إضافة وحذف nodes تحت ضغط متزامن (race conditions ممكنة لو ما عندكش lock).
• الذاكرة: ring بـ 150 vnode × 1000 سيرفر = 150K entry × ≈ 16 بايت = 2.4MB. مش مشكلة لكن مش zero.
• التشخيص: debugging أصعب. لو مفتاح راح للـ node الغلط، تحتاج تتبع hash function نفسها.

متى لا تستخدم Consistent Hashing

• عندك ≤ 3 سيرفرات وعدد السيرفرات نادرًا ما يتغير. modulo أبسط وأسرع.
• الكاش غير حرج وcold cache مقبول لأن الـ DB قادرة تتحمل لحظة السكيل.
• تستخدم Redis Cluster بالفعل — هو بيعمل hash slots داخليًا بدل ring. ما تطبّقش طبقة فوق طبقة.
• محتاج توزيع مرتبط بـ business logic (مثلاً كل tenant على سيرفر مخصص لأسباب legal). استخدم explicit routing بـ map صريح.
• الـ keys بتاعتك بتتغير كل ثانية وعمر الـ key أقل من millisecond. تكلفة الـ ring lookup هتطغى.

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

افتح أي service بياخد decisions على key-to-node بـ hash(key) % N وقيس النسبة الفعلية للمفاتيح اللي بتتنقل لما تضيف node في staging. لو النسبة فوق 50%، بدّل بـ ConsistentHashRing فوق وأعد القياس. الفرق هيكون واضح في أول scaling event حقيقي ومش هتحتاج retro لتفسير "ليه الـ DB قعت ساعة 11 الصبح".

المصادر

• Karger, D. et al. (1997). "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". STOC '97.
• DeCandia, G. et al. (2007). "Dynamo: Amazon's Highly Available Key-value Store". SOSP '07.
• Discord Engineering Blog: "How Discord Stores Billions of Messages" — discord.com/blog
• Apache Cassandra Documentation: "Data Distribution and Replication" — cassandra.apache.org/doc
• Redis Cluster Specification: "Hash Slots" — redis.io/docs/reference/cluster-spec
• Lakshman, A. & Malik, P. (2010). "Cassandra: A Decentralized Structured Storage System". ACM SIGOPS.