لو الـ Redis cluster بتاعك عنده 10 مليون مفتاح موزّعين على 10 سيرفرات، وأضفت سيرفر حادي عشر، الطريقة العادية hash(key) % N هتنقل 90% من المفاتيح وتفجّر الـ DB ورا الـ cache. Consistent Hashing بينقل 9% بس. هذه الـ 81% فرق هي اللي خلّت Cassandra و DynamoDB و Akamai CDN يبنوا عليها أنظمتهم.

Consistent Hashing — الحل اللي بيخلّي الـ Cache Cluster ميقعش لمّا تكبّر

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

الـ modulo hashing الكلاسيكي server = hash(key) % N بيشتغل ممتاز لمّا الـ N ثابت. المشكلة تبدأ لحظة ما تغيّر N. أي سيرفر يتضاف أو يطلع، كل المفاتيح تقريبًا بتتحرّك. النتيجة: cache miss storm، الـ DB بياخد ضربة 50x فجأة، وممكن السيستم كله يقع.

المثال البسيط الأول — موزّع البريد في عمارة 10 طوابق

تخيّل عمارة فيها 10 ساكنين، وموزّع البريد بيحط الجواب اللي عليه رقم الجواب في الشقة (رقم_الجواب % 10). كل حاجة تمام. جاء يوم وانتقل ساكن جديد، فبقوا 11. الموزّع غيّر القاعدة لـ % 11. النتيجة: تقريبًا كل جواب قديم بقى في شقة غلط. لو حد جه يدوّر على جوابه القديم في الشقة الصح حسب القاعدة الجديدة، مش هيلاقيه.

الـ Consistent Hashing بيقول: بدل ما تقسم على N، اعمل دايرة فيها 2^32 موضع، وحط كل ساكن في موضع واحد على الدايرة بناءً على hash(اسمه). كل جواب كمان ليه موضع على نفس الدايرة، والساكن المسؤول عنه هو أول ساكن تلاقيه لو مشيت مع عقارب الساعة. لمّا يدخل ساكن جديد، هو بياخد بس الجوابات اللي وقعت في القوس الصغير اللي قبله. الباقي ميتحركش.

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

Consistent Hashing اتقدّمت في ورقة Karger et al. 1997 — "Consistent Hashing and Random Trees" في MIT لحل مشكلة التوزيع في web caches. التعريف الرسمي:

• المساحة: حلقة (ring) من 0 لـ 2^32 - 1، يعني فضاء hash بحجم 32-bit (في التطبيق العملي).
• كل عقدة (node) بتتحط على الحلقة في موضع hash(node_id).
• كل مفتاح (key) بيتحط على الحلقة في موضع hash(key).
• المفتاح بيتعيّن لأقرب عقدة في اتجاه عقارب الساعة (clockwise successor).

الخاصية الأساسية اللي بتثبتها الورقة: لو ضفت عقدة، توقّع نقل K/N مفتاح فقط، حيث K = إجمالي المفاتيح و N = عدد العقد. مقارنة بـ K(N-1)/N في modulo hashing. على 10 مليون مفتاح و 10 سيرفرات، الفرق هو 1 مليون مقابل 9 ملايين.

الكود — قياس الفرق فعليًا على Python 3.12

الكود ده بيبني الـ ring بـ hashlib.md5 ويقارن نسبة المفاتيح اللي بتتحرّك بين الطريقتين لمّا نضيف سيرفر.

import hashlib
import bisect

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

    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 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]]

def modulo_node(key, n):
    h = int(hashlib.md5(key.encode()).hexdigest(), 16)
    return f"node-{h % n}"

# قياس فعلي: 1 مليون مفتاح، نضيف سيرفر جديد
KEYS = [f"user:{i}" for i in range(1_000_000)]

# قبل: 10 سيرفرات. بعد: 11 سيرفر
ring_before = ConsistentHashRing([f"node-{i}" for i in range(10)])
ring_after  = ConsistentHashRing([f"node-{i}" for i in range(11)])

moved_consistent = sum(
    1 for k in KEYS if ring_before.get_node(k) != ring_after.get_node(k)
)
moved_modulo = sum(
    1 for k in KEYS if modulo_node(k, 10) != modulo_node(k, 11)
)

print(f"Consistent Hashing moved: {moved_consistent / len(KEYS):.2%}")
print(f"Modulo Hashing moved:     {moved_modulo / len(KEYS):.2%}")

المخرجات الفعلية على جهاز عادي:

Consistent Hashing moved: 9.12%
Modulo Hashing moved:     90.91%

التحسّن: 10x أقل في عدد المفاتيح اللي بتتنقل عبر الشبكة وقت إعادة الموازنة. على cluster فيه 50 سيرفر، الرقم بيقرب من 2% مقابل 98%.

Virtual Nodes — ليه عدد 150 مش رقم عشوائي

المشكلة الثانية اللي بتظهر: لو حطّيت كل سيرفر مرة واحدة على الـ ring، التوزيع هيبقى غير عادل. سيرفر ممكن ياخد 30% من الـ ring وآخر ياخد 5%. الحل اسمه virtual nodes (vnodes): كل سيرفر فيزيائي بيتحط على الـ ring 100 لـ 200 مرة بأسامي مختلفة (node-0#1, node-0#2...).

المثال البسيط للـ vnodes

تخيّل 5 محلات ميخدموا 1000 زبون، وكل زبون بيروح أقرب محل ليه على شارع دائري. لو كل محل في موقع واحد، ممكن واحد منهم يبقى تحت برج سكني وياخد 600 زبون والباقي يقتسموا 400. لو كل محل عمل 100 فرع موزّعين على الشارع، التوزيع بيقرب من 200 زبون لكل محل بفارق ±5%.

الرقم العلمي

وثّقت Cassandra في documentation الرسمي (CASSANDRA-7032) إن vnodes = 256 بيدّي توزيع بفارق أقل من 5% standard deviation. DynamoDB بتستخدم 100. Riak كانت بتستخدم 64 وبدّلتها لـ 256. القاعدة العملية: ابدأ بـ 150، وارفعها لو شفت imbalance أكبر من 10% بين السيرفرات.

Trade-offs الحقيقية — بتكسب إيه وبتخسر إيه

• المكسب: rebalancing رخيص جدًا. إضافة سيرفر = نقل K/N مفتاح بس.
• المكسب: resilience. لو سيرفر وقع، بس جزء صغير من الـ ring هو اللي يتأثر.
• الخسارة: ذاكرة. 50 سيرفر × 150 vnode = 7500 إدخال في الـ ring. على 32-bit hash، ده ~ 60KB. مش مشكلة، بس مش zero-cost.
• الخسارة: lookup صار O(log V) بدل O(1)، حيث V = عدد الـ vnodes الإجمالي. على 10000 vnode، ده 13 مقارنة. عمليًا أقل من 5 ميكروثانية.
• الخسارة: hot keys مش بتتحل بالـ ring لوحده. لو مفتاح واحد بياخد 80% من الـ traffic، الـ ring هيوديه على سيرفر واحد. تحتاج طبقة فوقها (consistent hashing with bounded loads — Mirrokni 2018).

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

• Cluster ثابت ميتغيّرش: لو عندك 4 سيرفرات وعمرك ما هتغيّر العدد، modulo hashing أبسط وأسرع. لا داعي للتعقيد.
• Strong consistency أهم من availability: الـ ring بيحب الـ partitioning، مش الـ replication. لو محتاج 2-phase commit عبر السيرفرات، الـ ring مش الإجابة.
• Range queries: الـ hash بيكسر الترتيب الطبيعي للمفاتيح. لو محتاج تجيب "كل المفاتيح من user:1000 لـ user:2000" من سيرفر واحد، استخدم range partitioning زي اللي في HBase.
• Keys فيها skew طبيعي عالي: لو 10 مفاتيح بياخدوا 90% من الترافيك، الـ ring مش هيحلّها. خد قرار على مستوى الـ application: cache في الـ client، أو شارد الـ hot key نفسه.

الأنظمة اللي بتستخدمه فعلًا في production

• Apache Cassandra: token ring بـ Murmur3 hash و 256 vnode افتراضيًا.
• Amazon DynamoDB: partitioning مبني على نسخة مطوّرة من الـ ring (Dynamo paper, 2007).
• Akamai CDN: الورقة الأصلية اتنشرت تحديدًا لحل مشكلتهم في توزيع الـ web cache.
• Discord: سيشن routing على ملايين الـ voice channels.
• Memcached clients (libketama): أشهر تطبيق client-side للـ ring.

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

افتح أي cache layer عندك دلوقتي. لو شايف hash(key) % N في الكود وعندك خطة تكبير الـ cluster، بدّله بـ ring بـ 150 vnode لكل سيرفر باستخدام مكتبة جاهزة زي uhashring في Python أو hashring في Node. شغّل قياس قبل وبعد، وقارن نسبة المفاتيح المنقولة. لو لقيت الرقم أعلى من 2K/N، تأكد إن الـ vnodes متوزّعة صح ومش بتتحسب من نفس الـ seed.

المصادر

• Karger, D., et al. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. MIT — STOC '97.
• DeCandia, G., et al. (2007). Dynamo: Amazon's Highly Available Key-value Store. SOSP '07.
• Apache Cassandra Documentation — Virtual Nodes (CASSANDRA-7032).
• Mirrokni, V., Thorup, M., Zadimoghaddam, M. (2018). Consistent Hashing with Bounded Loads. Google Research.
• Last9 Engineering Blog (2024). Consistent Hashing in Practice — Production Lessons.
• RFC على libketama من Last.fm — التطبيق الأشهر للـ ring في memcached clients.