هذا المقال للمستوى المتوسط — هتحتاج تكون فاهم hash functions الأساسية وdictionaries في أي لغة، ومعندكش مشكلة في قراءة Python.
لو عندك Redis cluster بـ 4 سيرفرات وبتوزّع 10 مليون مفتاح بـ hash(key) % 4، كل حاجة تمام. اليوم اللي تضيف فيه سيرفر خامس، 80% من المفاتيح هتنتقل لسيرفر تاني فجأة. الـ cache بيبرد، الـ DB بتشتعل، والإنتاج بيقع 6 الصبح.
Consistent Hashing بيخلّي إضافة سيرفر جديد تنقل أقل من 2% من المفاتيح بدل 80%. المقال ده بيشرح الفكرة بمثال بسيط، يعدّي على التعريف العلمي، يدّيك كود Python في 50 سطر، وأرقام مقاسة فعلياً.
Consistent Hashing بدون كلام كتير
المثال البسيط: فندق فيه 4 طوابق
تخيّل فندق فيه 4 طوابق وعندك 100 ضيف. لو وزّعتهم بقاعدة "خد رقم الباس بورت ÷ 4 وخد الباقي"، كل طابق هياخد 25 ضيف تقريباً.
دلوقتي الفندق فتح طابق خامس. القاعدة بقت "÷ 5". النتيجة؟ تقريبًا كل ضيف غيّر طابقه. ده مش بس مرهق، ده يعني إن كل أمتعة الفندق لازم تتنقل في يوم واحد. وده بالظبط اللي بيحصل في الـ cache لما تضيف سيرفر بـ modulo hashing.
Consistent Hashing بيقترح فكرة مختلفة: حط كل الطوابق وكل الضيوف على دائرة. كل ضيف يروح لأقرب طابق بعده على الدائرة بترتيب عقارب الساعة. لما تفتح طابق خامس، الضيوف اللي بين الطابق الخامس والطابق اللي قبله في الدائرة هما بس اللي ينقلوا. باقي الفندق ما يتحركش.
التعريف العلمي بدون مجاملة
Consistent Hashing هي خوارزمية توزيع مقدّمة في ورقة Karger et al. سنة 1997 في MIT تحت عنوان "Consistent Hashing and Random Trees". الفكرة الأساسية:
- بنتخيّل فضاء hash كحلقة دائرية حجمها 2^32 (لو بنستخدم 32-bit hash) أو 2^128 (لو MD5).
- كل سيرفر بياخد موقع على الحلقة عبر
hash(server_id). - كل مفتاح بياخد موقع على الحلقة عبر
hash(key). - المفتاح بيتسند للسيرفر الأول اللي يجي بعده على الحلقة في اتجاه عقارب الساعة.
الافتراض اللي الخوارزمية مبنية عليه: hash() بتوزّع المفاتيح بتساوي تقريبي على الفضاء. لو الـ hash function ضعيفة (زي id % N على IDs متتابعة)، الموازنة هتكون سيئة بغض النظر عن أي حاجة تانية.
المشكلة الحقيقية: عدم التساوي بين السيرفرات
لو حطيت 4 سيرفرات على حلقة، التوزيع غالباً مش هيكون 25% لكل واحد. سيرفر ممكن ياخد 40% من المفاتيح وسيرفر تاني 12%. السبب: 4 نقاط على دائرة بتقسّمها لقطاعات غير متساوية.
الحل اسمه Virtual Nodes: كل سيرفر فعلي بيحجز 100-200 موقع على الحلقة بدل موقع واحد. بدل ما السيرفر s1 ياخد نقطة واحدة، بياخد s1:0, s1:1, ... s1:199.
Virtual Nodes بتقلّل الـ standard deviation في توزيع المفاتيح من تقريباً 30% (بدون vnodes) إلى أقل من 4% (مع 200 vnode لكل سيرفر). الرقم ده مذكور في ورقة Dynamo من Amazon (SOSP 2007).
