منهجية التصميم
الـhashing المتسق
الساعة الثالثة فجراً، وأحد خوادم الـcache العشرة لديك يتعطل. مزعج — لكن ما يزال لديك تسعة. لكن مع قاعدة التوجيه المدرسية، هذا العطل أعاد للتوّ توزيع كل مفتاح تقريباً في الـcache. نسبة الإصابة تنهار، وقاعدة البيانات تحتها تتلقى عاصفة القراءات كاملة بينما تُعاد تسخين الـcaches. جهاز واحد فشل؛ والأسطول كله اهتز. توجد طريقة توجيه تجعل خسارة عقدة واحدة تكلّفك حصتها فقط ولا شيء أكثر.
القاعدة الساذجة هي server = hash(key) mod N. بسيطة وحتمية ومتوازنة تماماً — حتى يتغير N. انتقل من 10 خوادم إلى 11 فيتغير المقسوم عليه، ويختلف hash(key) mod 10 عن hash(key) mod 11 في نحو 90% من المفاتيح. كل مفتاح يختلف يجب أن ينتقل: إخفاقات cache في كل مكان، أو ترحيل بيانات ضخم في قاعدة بيانات مقسّمة (sharded). وأنت تضيف سعة جديدة عادة عندما تكون تحت ضغط أصلاً — وهذه بالضبط اللحظة التي تؤلم فيها إعادة الخلط هذه أكثر.
- خذ مجال مخرجات دالة الـhash — مثلاً من 0 إلى 2³²−1 — واثنِه على شكل دائرة.
- طبّق الـhash على كل خادم (عبر عنوان IP أو الاسم) ليحتل موضعاً على الدائرة. وطبّق الـhash على كل مفتاح على الدائرة نفسها، بالدالة نفسها.
- كل مفتاح يتبع أول خادم تصادفه وأنت تمشي باتجاه عقارب الساعة من موضع المفتاح.
- لتجد بيت المفتاح: طبّق الـhash عليه، ثم ابحث ثنائياً (binary search) في مواضع الخوادم المرتّبة عن أول نقطة باتجاه عقارب الساعة — بتعقيد O(log N).
أضف خادماً حادي عشر إلى الحلقة فيحطّ في نقطة واحدة على الدائرة. لا يستولي إلا على القوس الواقع بينه وبين الخادم السابق عكس عقارب الساعة — نحو 1/11 من فضاء المفاتيح في المتوسط. أما الخوادم العشرة الأخرى فتحتفظ بكل مفاتيحها. واحذف خادماً فينتقل قوسه إلى الخادم التالي باتجاه عقارب الساعة: مجدداً ينتقل نحو 1/N من المفاتيح فقط، وإلى جار واحد بالضبط. مفاتيح الخوادم التسعة الأخرى لا يمسّها شيء في الحالتين.
الحلقة الخام مع عدد قليل من الخوادم متخبطة: التوزيع العشوائي قد يعطي خادماً قوساً أكبر بعدة أضعاف من قوس آخر، وكل الخوادم تُعامل كأنها بنفس القوة. الحل هو الـvirtual nodes — طبّق الـhash على كل خادم فيزيائي في 100–200 نقطة (server1#1 وserver1#2 و…) منتشرة حول الدائرة. الأقواس تتعادل إحصائياً، فتهبط حصة كل خادم ضمن بضعة بالمئة من العدل. ومكافأة إضافية: أعطِ آلة أقوى عقداً افتراضية أكثر فتمتص مفاتيح أكثر بنفس النسبة — ترجيح للسعة مجاناً.
تريد ثلاث نسخ من كل مفتاح؟ من موضع المفتاح، امشِ باتجاه عقارب الساعة وخذ أول ثلاثة خوادم فيزيائية مختلفة — متخطياً الـvirtual nodes التي تعود لآلة اخترتها سلفاً. نسختان على الصندوق نفسه ليستا replication؛ بل جنازة مشتركة. هكذا تضع أنظمة عائلة Dynamo نسخها، ولها فائدة جانبية: عندما تموت عقدة، تكون عقدها الافتراضية متناثرة، فيمتص الناجون حملها بشرائح رفيعة موزعة على كثيرين بدل أن يسحق جاراً واحداً.
توجيه mod N يجعل كل تغيير في العضوية حدثاً شاملاً — يتحرك خادم واحد فتُعاد قرعة كل المفاتيح. أما الـconsistent hashing فيجعله حدثاً محلياً: تغيّر عقدة لا يلمس إلا الأقواس المجاورة لها على الحلقة. استبدلت إعادة خلط شاملة بتسليم محلي، وكان الثمن قائمة مرتّبة وبحثاً ثنائياً.
لديك 4 خوادم، لكل منها 100 عقدة افتراضية. أُزيل خادم واحد. ما الكسر التقريبي من المفاتيح الذي يجب أن ينتقل، ولماذا؟ (نحو الربع — 1/N. كل خادم فيزيائي يملك ~100 نقطة من أصل 400 على الحلقة، فيحكم ~25% من الأقواس. إزالته تُيتّم أقواسه بالضبط، وكل قوس ينزلق إلى العقدة الافتراضية التالية باتجاه عقارب الساعة — فينتقل ~25% من المفاتيح موزعة على الخوادم الثلاثة الناجية بدل أن تُلقى على خادم واحد.)
احفظ ثلاث حركات. الخوادم والمفاتيح على الدائرة نفسها؛ والمفتاح يمشي باتجاه عقارب الساعة إلى خادمه. تغييرات العضوية تكلّف ~1/N من فضاء المفاتيح، لا تقريباً كلّه. والـvirtual nodes تشتري التوازن وترجيح السعة وامتصاصاً رشيقاً للأعطال. لهذا تسكن هذه الفكرة داخل عملاء Memcached وCassandra ومقسّم DynamoDB وشبكات CDN وموازنات الحمل الحديثة.
اعثر على المواضع التي يستخدم فيها نظامك الـconsistent hashing أصلاً — عميل الـcache، قاعدة البيانات المقسّمة، نمط التوجيه في الـload balancer. اقرأ إعداداته وتحقق هل الـvirtual nodes مفعّلة وكم عقدة يحصل عليها كل خادم. إن كان العدد ضئيلاً أو صفراً، فدوّن كم ستكلّفك عملية التوسّع القادمة من مفاتيح منتقلة، وأحضر هذا الرقم إلى مراجعة المعمارية القادمة.
منهجية التصميم