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