أقفال موزعة باستخدام Redis

مرحبا هبر!



نلفت انتباهك اليوم إلى ترجمة لمقال معقد حول تنفيذ الأقفال الموزعة باستخدام Redis ونقترح التحدث عن احتمالات Redis كموضوع. تحليل خوارزمية Redlock تعتبر من مارتن Kleppman، مؤلف كتاب "عالية تحميل تطبيقات تعطى"، هنا .





الأقفال الموزعة هي بدائية مفيدة للغاية تستخدم في العديد من البيئات حيث يجب أن تعمل العمليات المختلفة على الموارد المشتركة بطريقة حصرية بشكل متبادل.



هناك عدد من المكتبات والمنشورات التي تصف كيفية تنفيذ DLM (Distributed Locking Manager) مع Redis ، لكن كل مكتبة تتخذ نهجًا مختلفًا والضمانات المقدمة ضعيفة جدًا مقارنة بما يمكن تحقيقه بتصميم أكثر تعقيدًا.



في هذه المقالة ، سنحاول وصف خوارزمية شرطية شرطية توضح كيفية تنفيذ الأقفال الموزعة مع Redis. سنتحدث عن خوارزمية تسمى Redlock، فهي تنفذ إدارة قفل موزعة ، وفي رأينا ، تعد هذه الخوارزمية أكثر أمانًا من نهج المثيل الفردي التقليدي. نأمل أن يقوم المجتمع بتحليلها وإبداء الملاحظات واستخدامها كنقطة انطلاق لتنفيذ مشاريع أكثر تعقيدًا أو بديلة.



عمليات التنفيذ



قبل الشروع في وصف الخوارزمية ، إليك بعض الروابط للتطبيقات الجاهزة. يمكن استخدامها كمرجع.

• Redlock-rb (تنفيذ روبي). هناك أيضًا شوكة Redlock-rb ، والتي تضيف حزمة (جوهرة) لسهولة التوزيع ، وليس لهذا الغرض فقط.
• Redlock-py (تطبيق Python).
• Aioredlock (تطبيق Asyncio Python).
• Redlock-php (تنفيذ PHP ).
• PHPRedisMutex ( PHP)
• cheprasov/php-redis-lock (PHP- )
• Redsync ( Go).
• Redisson ( Java).
• Redis::DistLock ( Perl).
• Redlock-cpp ( C++).
• Redlock-cs ( C#/.NET).
• RedLock.net ( C#/.NET). async lock.
• ScarletLock ( C# .NET )
• Redlock4Net ( C# .NET)
• node-redlock ( NodeJS). .

ضمانات الأمان والتوافر



سنقوم بمحاكاة تصميمنا بثلاث خصائص فقط نعتقد أنها توفر الحد الأدنى من الضمانات المطلوبة للاستخدام الفعال للأقفال الموزعة.

1. الملكية الأمنية: الاستبعاد المتبادل. يمكن لعميل واحد فقط الاحتفاظ بقفل في المرة الواحدة.
2. خاصية إمكانية الوصول أ: لا توجد عقبات. في النهاية ، يمكنك دائمًا الحصول على قفل ، حتى إذا فشل العميل الذي قام بتأمين المورد أو انتهى به الأمر في مقطع قرص آخر.
3. خاصية الوصول ب: التسامح مع الخطأ. أثناء تشغيل معظم عقد Redis ، يمكن للعملاء الحصول على أقفال وتحريرها.

لماذا لا يكون التنفيذ المستند إلى تجاوز الفشل كافياً في هذه الحالة

لفهم ما سنقوم بتحسينه ، دعنا نحلل الوضع الحالي مع معظم مكتبات التأمين الموزعة القائمة على Redis.



أسهل طريقة لقفل مورد باستخدام Redis هي إنشاء مفتاح في مثيل. عادةً ما يتم إنشاء مفتاح لمدة محدودة ، ويتم تحقيق ذلك باستخدام ميزة انتهاء الصلاحية المتوفرة في Redis ، لذلك يتم تحرير هذا المفتاح عاجلاً أم آجلاً (الخاصية 2 في قائمتنا). عندما يحتاج العميل إلى تحرير المورد ، فإنه يزيل المفتاح.



للوهلة الأولى ، يعمل هذا الحل بشكل جيد ، ولكن هناك مشكلة: هناك نقطة فشل واحدة في بنيتنا. ماذا يحدث إذا فشل مثيل Redis الرئيسي؟ دعنا نضيف متابع بعد ذلك! وسنستخدمه إذا لم يكن المضيف متاحًا. لسوء الحظ ، هذا الخيار غير قابل للتطبيق. من خلال القيام بذلك ، لن نتمكن من تنفيذ خاصية الاستبعاد المتبادل التي نحتاجها للأمان بشكل صحيح ، لأن النسخ المتماثل في Redis غير متزامن.



من الواضح أن حالة السباق تحدث في مثل هذا النموذج:

1. يكتسب العميل A قفلًا على السيد.
2. فشل السيد قبل نقل الكتابة إلى المفتاح إلى العبد.
3. تتم ترقية التابع إلى القائد.
4. يكتسب العميل B قفلًا على نفس المورد الذي تم قفله بالفعل بواسطة A. انتهاك الأمان!

في بعض الأحيان يكون من الطبيعي تمامًا أنه في ظروف خاصة ، مثل الفشل ، يمكن لعدة عملاء الاحتفاظ بقفل في نفس الوقت. في مثل هذه الحالات ، يمكنك تطبيق حل قائم على النسخ المتماثل. خلاف ذلك ، نوصي بالحل الموضح في هذه المقالة.



تصحيح تنفيذ أحادي المثيل



قبل أن نحاول التغلب على أوجه القصور في التكوين أحادي المثيل الموضح أعلاه ، دعنا نتعرف على كيفية التعامل مع هذه الحالة البسيطة ، نظرًا لأن هذا مقبول بالفعل في التطبيقات التي تكون فيها ظروف السباق مقبولة في بعض الأحيان ، و أيضًا لأن القفل على مثيل واحد يعمل كأساس للخوارزمية الموزعة الموصوفة هنا.



للحصول على قفل ، دعنا نفعل هذا:



SET resource_name my_random_value NX PX 30000



يقوم هذا الأمر بتثبيت مفتاح فقط إذا لم يكن موجودًا بالفعل (الخيار NX) ، مع تاريخ انتهاء صلاحية يبلغ 30000 مللي ثانية (الخيار PX). المفتاح مضبوط على " myrandomvalue". يجب أن تكون هذه القيمة فريدة عبر جميع العملاء وعبر جميع طلبات التأمين.

في الأساس ، يتم استخدام القيمة العشوائية لتحرير القفل بأمان ، باستخدام برنامج نصي يخبر Redis بحذف المفتاح فقط إذا كان موجودًا والقيمة المخزنة فيه هي بالضبط ما كان متوقعًا. يتم تحقيق ذلك باستخدام برنامج Lua النصي التالي:

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

هذا مهم لمنع تحرير قفل من قبل عميل آخر. على سبيل المثال ، قد يحصل العميل على قفل ، ثم يحظر في عملية تستمر لفترة أطول من القفل الأول (بحيث يكون للمفتاح وقت انتهاء صلاحيته) ، ثم يقوم لاحقًا بإزالة القفل الذي وضعه بعض العملاء الآخرين.

من غير الآمن استخدام DEL بسيط لأن العميل قد يزيل قفلًا يحتفظ به عميل آخر. على العكس من ذلك ، عند استخدام البرنامج النصي أعلاه ، يتم "توقيع" كل قفل بسلسلة عشوائية ، بحيث يمكن للعميل الذي قام بوضعه مسبقًا فقط إزالته.



ماذا يجب أن تكون هذه السلسلة العشوائية؟ أفترض أنه يجب أن يكون 20 بايت من / dev / urandom ، لكن يمكنك إيجاد طرق أقل تكلفة لجعل السلسلة فريدة بما يكفي للغرض الذي تفكر فيه. على سبيل المثال ، سيكون من الجيد زرع RC4 مع / dev / urandom ثم إنشاء دفق عشوائي زائف بناءً عليه. يتضمن الحل الأبسط الجمع بين وقت يونكس ميكروثاني بالإضافة إلى معرف العميل ؛ إنه ليس آمنًا تمامًا ، ولكنه ربما يكون على مستوى التحدي في معظم السياقات.



يُطلق على الوقت الذي نستخدمه كمقياس لعمر المفتاح "وقت انتهاء صلاحية القفل". هذه القيمة هي الوقت الذي سيتم بعده تحرير القفل تلقائيًا والوقت الذي يتعين على العميل فيه إكمال العملية قبل أن يتمكن عميل آخر بدوره من قفل المورد دون انتهاك ضمانات الاستبعاد المتبادل فعليًا. يقتصر هذا الضمان فقط على فترة زمنية معينة تبدأ من لحظة الحصول على القفل.



لذلك ناقشنا طريقة جيدة للحصول على قفل وتحريره. النظام (إذا كنا نتحدث عن نظام غير مخصص يتكون من مثيل واحد ومتاح دائمًا) يكون آمنًا. دعنا نوسع هذا المفهوم إلى نظام موزع حيث ليس لدينا مثل هذه الضمانات.



خوارزمية Redlock



تفترض النسخة الموزعة من الخوارزمية أن لدينا N رائد Redis. هذه العقد مستقلة تمامًا عن بعضها البعض ، لذلك لا نستخدم النسخ المتماثل أو أي نظام تنسيق ضمني آخر. لقد غطينا بالفعل كيفية الحصول على الأقفال وتحريرها بأمان في مثيل واحد. نحن نعتبر أن الخوارزمية ستستخدم هذه الطريقة عند العمل مع مثيل واحد كأمر مسلم به. في أمثلةنا ، قمنا بتعيين N على 5 ، وهي قيمة معقولة تمامًا. وبالتالي ، سنحتاج إلى استخدام 5 خبراء Redis على أجهزة كمبيوتر مختلفة أو أجهزة افتراضية للتأكد من أنها تعمل بشكل مستقل عن بعضها البعض.



للحصول على قفل ، يقوم العميل بتنفيذ العمليات التالية:

1. الحصول على الوقت الحالي بالمللي ثانية.
2. N , . 2, , , , , , . , 10 , ~ 5-50 . , , Redis: , .
3. , , ; , 1. , ( 3), , , , , , .
4. , , 3.
5. - ( N/2+1 , ), ( , , , ).

هل الخوارزمية غير متزامنة؟



تستند هذه الخوارزمية على افتراض أنه على الرغم من عدم وجود ساعة متزامنة تعمل عليها جميع العمليات ، إلا أن الوقت المحلي في كل عملية لا يزال يتدفق بنفس المعدل تقريبًا ، والخطأ صغير مقارنة بإجمالي الوقت الذي يتم بعده تحرير القفل تلقائيًا. هذا الافتراض مشابه جدًا للوضع المعتاد لأجهزة الكمبيوتر العادية: لكل كمبيوتر ساعة محلية ، وعادة يمكننا الاعتماد على حقيقة أن الفارق الزمني في أجهزة الكمبيوتر المختلفة صغير.



في هذه المرحلة ، يجب أن نكون أكثر حرصًا في صياغة قاعدة الاستبعاد المتبادل لدينا: لا يتم ضمان الاستبعاد المتبادل إلا إذا اكتمل العميل الذي يحمل القفل خلال الوقت الذي يكون فيه القفل صالحًا (تم الحصول على هذه القيمة في الخطوة 3) ، مطروحًا منه بعض الوقت الإضافي (الإجمالي عدة مللي ثانية للتعويض عن الفارق الزمني بين العمليات).



تشرح المقالة التالية المثيرة للاهتمام المزيد عن مثل هذه الأنظمة التي تتطلب فجوة زمنية: عقود الإيجار: آلية فعالة لتحمل الأخطاء لاتساق ذاكرة التخزين المؤقت للملفات الموزعة .



أعد المحاولة عند الفشل



عندما يفشل العميل في الحصول على القفل ، يجب أن يحاول القيام بذلك مرة أخرى ، مع تأخير عرضي ؛ يتم ذلك لمزامنة العديد من العملاء في نفس الوقت الذين يحاولون الحصول على قفل على نفس المورد (مما قد يؤدي إلى حالة انقسام الدماغ حيث لا يوجد فائزون). بالإضافة إلى ذلك ، كلما حاول العميل الحصول على قفل في معظم حالات Redis بشكل أسرع ، كلما كانت النافذة التي يمكن أن تحدث فيها حالة انقسام الدماغ أضيق (وكلما كانت إعادة المحاولة مطلوبة أقل). لذلك ، من الناحية المثالية ، يجب على العميل محاولة إرسال أوامر SET إلى مثيلات N في نفس الوقت باستخدام مضاعفة الإرسال.



يجدر التأكيد هنا على مدى أهمية قيام العملاء الذين لم يتمكنوا من الحصول على معظم الأقفال بتحرير الأقفال المكتسبة (جزئيًا) حتى لا يضطروا إلى انتظار تاريخ انتهاء صلاحية المفتاح قبل أن يتم الحصول على قفل المورد مرة أخرى (وإن حدث تجزئة للشبكة ويفقد العميل الاتصال بمثيلات Redis ، يتعين عليك دفع غرامة انتهاك وصول بينما يُتوقع أن تنتهي صلاحية المفتاح).



تحرير القفل يعد



تحرير القفل عملية بسيطة تتطلب منك ببساطة فتح جميع الحالات ، بغض النظر عما إذا كان العميل يعتقد أنه كان قادرًا على تأمين حالة معينة بنجاح.



اعتبارات السلامة



هل الخوارزمية آمنة؟ دعونا نحاول تخيل ما يحدث في سيناريوهات مختلفة.



أولاً ، لنفترض أن العميل كان قادرًا على الحصول على القفل في معظم الحالات. ستحتوي كل حالة على مفتاح له نفس العمر للجميع. ومع ذلك ، تم تثبيت كل مفتاح من هذه المفاتيح في لحظته الخاصة ، لذلك ستنتهي صلاحيتها في أوقات مختلفة. ولكن ، إذا تم تثبيت المفتاح الأول في وقت ليس أسوأ من T1 (الوقت الذي نختاره قبل الاتصال بالخادم الأول) ، وتم تثبيت المفتاح الأخير في وقت ليس أسوأ من T2 (الوقت الذي تم فيه تلقي استجابة من الخادم الأخير) ، فإننا تأكد من أن المفتاح الأول في المجموعة الذي ستنتهي صلاحيته سيستمر على الأقلMIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT... ستنتهي صلاحية جميع المفاتيح الأخرى لاحقًا ، لذا يمكننا التأكد من أن جميع المفاتيح ستكون صالحة في وقت واحد على الأقل لهذه المرة.



خلال الوقت الذي تظل فيه معظم المفاتيح صالحة ، لن يتمكن عميل آخر من الحصول على القفل ، نظرًا لأن عمليات N / 2 + 1 SET NX لا يمكن أن تنجح إذا كانت مفاتيح N / 2 + 1 موجودة بالفعل. لذلك ، إذا تم الحصول على القفل ، فمن المستحيل استعادته في نفس الوقت (قد ينتهك هذا خاصية الاستبعاد المتبادل).

ومع ذلك ، نريد التأكد من أن العديد من العملاء الذين يحاولون الحصول على قفل في وقت واحد لا يمكن أن ينجحوا في نفس الوقت.



إذا قام العميل بإغلاق معظم المثيلات ، أو إنفاق حوالي أو أكثر من الحد الأقصى لمدة القفل لهذا الوقت ، فسيؤدي ذلك إلى إبطال القفل وإلغاء حظر المثيلات. لذلك ، علينا فقط النظر في الحالة التي تمكن فيها العميل من حظر معظم الحالات في أقل من تاريخ انتهاء الصلاحية. في هذه الحالة ، فيما يتعلق بالحجة المذكورة أعلاه ، MIN_VALIDITYيجب ألا يتمكن أي عميل من إعادة الحصول على القفل في الوقت المناسب. لذلك ، سيتمكن العديد من العملاء من قفل مثيلات N / 2 + 1 في نفس الفترة الزمنية (التي تنتهي في نهاية المرحلة 2) فقط عندما يكون وقت قفل الأغلبية أطول من وقت TTL ، مما يؤدي إلى إبطال القفل.



هل يمكنك تقديم دليل رسمي للأمان ، أو الإشارة إلى خوارزميات مماثلة موجودة ، أو العثور على خطأ في ما سبق؟



اعتبارات



التوفر يعتمد توافر النظام على ثلاث خصائص رئيسية:

1. التحرير التلقائي للأقفال (مع انتهاء صلاحية المفاتيح): في النهاية ، ستتوفر المفاتيح مرة أخرى لاستخدامها في الأقفال.
2. حقيقة أن العملاء عادة ما يساعدون بعضهم البعض عن طريق إزالة الأقفال عندما لا يتم الحصول على القفل المطلوب ، أو الحصول عليه ، واكتمال العمل ؛ لذلك ، من المحتمل ألا نضطر إلى انتظار انتهاء صلاحية المفاتيح لاستعادة القفل.
3. حقيقة أنه عندما يحتاج العميل إلى إعادة محاولة الحصول على قفل ، فإنه ينتظر وقتًا أطول نسبيًا مما يتطلبه الحصول على معظم الأقفال. هذا يقلل من احتمالية حدوث انقسام في الدماغ عند التنافس على الموارد.

ومع ذلك ، يتعين عليك دفع غرامة مقابل التوافر المنخفض مساوٍ لوقت TTL في أجزاء الشبكة ، لذلك إذا كانت هناك أجزاء متجاورة ، فيمكن أن تصبح هذه العقوبة بحجم غير محدد. يحدث هذا عندما يكتسب العميل قفلًا ثم يتم ربطه بجزء آخر قبل أن يتمكن من تحريره.



من حيث المبدأ ، نظرًا لقطاعات الشبكة المتجاورة اللانهائية ، يمكن أن يظل النظام غير متاح لفترة زمنية غير محدودة.



الأداء وتجاوز الفشل و fsync



يستخدم العديد من الأشخاص Redis لأنهم بحاجة إلى توفير أداء عالٍ لخادم القفل ، على مستوى زمن الانتقال المطلوب للحصول على الأقفال وإصدارها ، بالإضافة إلى عدد عمليات الاستحواذ / الإصدار التي يمكن إجراؤها في الثانية. لتلبية هذا المطلب ، توجد إستراتيجية للتواصل مع خوادم N Redis لتقليل زمن الوصول. هذه إستراتيجية مضاعفة إرسال (أو تعدد إرسال رجل فقير ، والذي يضع المقبس في وضع عدم الحظر ، ويرسل جميع الأوامر ، ويقرأ الأوامر لاحقًا ، بافتراض أن وقت الذهاب والإياب بين العميل وكل حالة متشابهة).



صحيح ، هناك أيضًا اعتبار طويل الأجل لتخزين البيانات يجب مراعاته إذا كنا نريد إنشاء نموذج باسترداد موثوق به بعد الفشل.



لتوضيح المشكلة بشكل أساسي ، دعنا نفترض أننا نقوم بتكوين Redis بدون تخزين بيانات طويل المدى على الإطلاق. تمكن العميل من حظر 3 من أصل 5 مثيلات. تمت إعادة تشغيل إحدى الحالات التي تمكن العميل من حظرها ، وفي هذه اللحظة تظهر 3 مثيلات مرة أخرى لنفس المورد ، والتي يمكننا حظرها ، ويمكن للعميل الآخر ، بدوره ، حظر مثيل إعادة التشغيل ، منتهكًا خاصية الأمان التي تعني حصرية الأقفال.



إذا قمت بتمكين تقدم البيانات (AOF) ، فسوف يتحسن الموقف قليلاً. على سبيل المثال ، يمكنك ترقية الخادم عن طريق إرسال الأمر SHUTDOWN ثم إعادة تشغيله. نظرًا لأن عمليات انتهاء الصلاحية في Redis يتم تنفيذها بشكل جوهري بحيث يستمر الوقت في التدفق حتى عند إيقاف تشغيل الخادم ، فإن كل شيء على ما يرام مع جميع متطلباتنا. طبيعي طالما أن الإغلاق العادي مضمون. ماذا تفعل في حالة انقطاع التيار الكهربائي؟ إذا تم تكوين Redis افتراضيًا ، مع مزامنة fsync على القرص كل ثانية ، فمن المحتمل أنه بعد إعادة التشغيل سوف نفقد مفتاحنا. من الناحية النظرية ، إذا أردنا ضمان سلامة الأقفال عند إعادة تشغيل المثيل ، فيجب علينا التمكينfsync=alwaysفي إعدادات تخزين البيانات على المدى الطويل. سيؤدي هذا إلى قتل الأداء تمامًا ، إلى مستوى أنظمة CP المستخدمة تقليديًا لتنفيذ الأقفال الموزعة بشكل آمن.



لكن الوضع أفضل مما تراه العين. من حيث المبدأ ، تظل الخوارزمية آمنة لأنه عند إعادة تشغيل مثيل بعد فشل ، لم يعد يشارك في أي قفل نشط حاليًا.



لضمان ذلك ، نحتاج فقط إلى التأكد من أنه بعد الفشل ، يظل المثيل غير متاح لفترة من الوقت تتجاوز قليلاً الحد الأقصى لمدة البقاء التي نستخدمها. لذلك سننتظر انتهاء الصلاحية والإفراج التلقائي عن جميع المفاتيح التي كانت نشطة وقت الرفض.



باستخدام عمليات إعادة التشغيل المؤجلة ، من الممكن من حيث المبدأ تحقيق الأمن دون أي إصرار طويل المدى في Redis. لاحظ ، مع ذلك ، أن هذا يمكن أن يؤدي إلى عقوبة الوصول. على سبيل المثال ، إذا فشلت معظم المثيلات ، فسيصبح النظام غير متاح عالميًا لوقت TTL (ولا يمكن حظر أي مورد في هذا الوقت).



زيادة توافر الخوارزمية: تمديد القفل



إذا كان العمل الذي قام به العملاء يتكون من خطوات صغيرة ، فمن الممكن تقصير مدة القفل الافتراضية وتنفيذ آلية لتمديد الأقفال. بشكل أساسي ، إذا كان العميل مشغولاً بالحسابات وكانت قيمة انتهاء صلاحية القفل منخفضة بشكل خطير ، يمكنك إرسال نص برمجي لجميع الحالات في Lua لتوسيع TTL للمفتاح ، إذا كان المفتاح لا يزال موجودًا ، ولا تزال قيمته قيمة عشوائية تم الحصول عليها عند الحصول على القفل.



يجب على العميل اعتبار القفل على أنه تمت إعادة اكتسابه فقط إذا تم قفل معظم المثيلات بنجاح خلال فترة الصلاحية.



ومع ذلك ، من الناحية الفنية ، لا تتغير الخوارزمية في هذه الحالة ، لذلك يجب أن يكون الحد الأقصى لعدد المحاولات المتكررة للحصول على الأقفال محدودًا ، وإلا سيتم انتهاك خصائص إمكانية الوصول.