لو الـ 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 ويقارن نسبة المفاتيح اللي بتتحرّك بين الطريقتين لمّا نضيف سيرفر.
