Consistent Hashing بالعربي: وزّع مفاتيحك على 100 سيرفر بدون reshuffle
لو بتستخدم hash(key) % N لتوزيع المفاتيح على servers، لما N يتغيّر حتى بواحد، بتنقل ~99% من البيانات. Consistent hashing بيحرّك 1/N بس. ده الفرق بين cache بيفضى كل ما سيرفر يقع، وبين cluster ثابت خلال الـ failover.
المشكلة باختصار
عندك 4 servers للـ cache. بتحسب hash(user_id) % 4 عشان تقرّر أي سيرفر يحتفظ بالـ session. واحد وقع. N بقت 3. hash(user_id) % 3 بيرجّع قيم مختلفة لـ 75% من المفاتيح. النتيجة: الـ cache miss rate بيطلع فجأة لـ 75%، وقاعدة البيانات بتشرب الضربة كلها في نفس اللحظة، وبتدخل في cascading failure.
في حالة حقيقية، Discord وقف عن modulo hashing ونقل Cassandra cluster بتاعهم لـ consistent hashing. وقت الـ failover نزل من دقائق لثواني، والـ p99 latency على reads ثبت بدل ما يطلع فوق 800ms. المصدر في آخر المقال.
الفكرة بمثال بسيط: رفوف المكتبة
تخيّل مكتبة فيها 4 رفوف. كل كتاب ليه رقم. الطريقة الشائعة: رقم_الكتاب % 4. الكتاب رقم 17 يروح للرف الأول (17 % 4 = 1). لو رف اتشال، N بقت 3. نفس الكتاب دلوقتي: 17 % 3 = 2. راح لرف تاني خالص. ولو حسبت على كل الكتب، هتلاقي تقريبًا ثلاثة أرباع المكتبة اتنقلت. يعني فريق نقل في يوم واحد.
Consistent hashing بيقول: خلي الرفوف على دايرة ساعة. الرف الأول عند الساعة 3، التاني عند 6، التالت 9، الرابع 12. كل كتاب كمان بياخد مكان على الدايرة حسب رقمه. قاعدة وحيدة: الكتاب بيروح لأقرب رف في اتجاه عقارب الساعة. لو رف الساعة 6 اتشال، الكتب اللي كانت بين الساعة 3 و 6 هي بس اللي تتنقل لرف الساعة 9. باقي المكتبة ما اتحركتش. النقل: ربع المكتبة تقريبًا، مش تلاتة أرباع.
التفسير العلمي الدقيق
الـ hash function (زي MurmurHash3 أو MD5 أو SHA-1) بترجّع رقم في فضاء كبير، عادة 32-bit أو 64-bit. بنتعامل مع الفضاء ده كحلقة: بعد القيمة العظمى بيرجع للصفر. كل سيرفر بياخد نقطة واحدة على الحلقة بـ hash(server_id). كل مفتاح بياخد نقطته بـ hash(key). المفتاح بيتخزن في أول سيرفر تلاقيه تمشي في اتجاه عقارب الساعة بعد نقطة المفتاح.
لما سيرفر يتشال، المفاتيح اللي بين نقطة السيرفر ده ونقطة السيرفر اللي قبله مباشرةً هي اللي تنتقل للسيرفر اللي بعده. عدديًا: K/N مفتاح بيتحرك من أصل K. لما تضيف سيرفر جديد، نفس الحساب: K/N بس.
مشكلة التوزيع غير المتوازن
لو السيرفرات وقعت على نقاط متقاربة، السيرفر اللي بعدهم هيكون مسؤول عن قوس كبير من الحلقة، فيأخد حمل أكبر بكتير من الباقي. الحل الصناعي: virtual nodes. كل سيرفر فيزيائي بياخد 100 إلى 200 موقع على الحلقة بدل موقع واحد، عن طريق hashing لـ server_id#0, server_id#1… إلخ. التوزيع بيبقى أنعم بكتير، ونسبة عدم التوازن بين السيرفرات بتنزل من ~35% عند vnode واحد لأقل من 5% عند 200 vnode. ده القياس الموثّق من ورقة Dynamo.