في بعض الأحيان ، عند تطوير منتج ذي حمولة كبيرة ، ينشأ موقف عندما يكون من الضروري معالجة أكبر عدد ممكن من الطلبات ، بل تحديد عدد الطلبات لكل وحدة زمنية. في حالتنا ، هذا هو عدد إشعارات الدفع المرسلة إلى المستخدمين النهائيين. قراءة المزيد عن خوارزميات الحد من معدل ، إيجابيات وسلبيات - تحت خفض.
أولا ، قليلا عنا. Pushwoosh هي خدمة b2b للتواصل بين عملائنا ومستخدميهم. نوفر للشركات حلولًا شاملة للتواصل مع المستخدمين من خلال إشعارات الدفع والبريد الإلكتروني وقنوات الاتصال الأخرى. بالإضافة إلى إرسال الرسائل بالفعل ، نحن نقدم أدوات لتقسيم الجمهور ، وجمع الإحصاءات ومعالجتها ، وأكثر من ذلك بكثير. للقيام بذلك ، من الصفر ، أنشأنا منتجًا عالي التحميل عند تقاطع العديد من التقنيات ، جزء صغير منها PHP و Golang و PostgreSQL و MongoDB و Apache Kafka. العديد من حلولنا فريدة من نوعها ، على سبيل المثال ، الإخطارات عالية السرعة. نقوم بمعالجة أكثر من 2 مليار طلب API يوميًا ، ولدينا أكثر من 3 مليارات جهاز في قاعدة البيانات الخاصة بنا ، وعلى مدار الوقت الكامل أرسلنا أكثر من 500 مليار إشعار إلى هذه الأجهزة.
وهنا نصل إلى موقف يتعين فيه تسليم الإخطارات إلى ملايين الأجهزة في أسرع وقت ممكن (كما هو الحال في السرعة العالية المذكورة بالفعل) ، ولكننا نحد من السرعة بشكل مصطنع بحيث لا تدخل خوادم عملائنا عند فتح الإشعار في نفس الوقت تحميل.
هنا ، تأتي خوارزميات مختلفة للحد من الأسعار في عوننا ، مما يسمح لنا بتحديد عدد الطلبات لكل وحدة زمنية. كقاعدة عامة ، يتم استخدام ذلك ، على سبيل المثال ، عند تصميم واجهة برمجة التطبيقات ، حيث يمكننا بهذه الطريقة حماية النظام من الزيادة العرضية أو الضارة للطلبات ، ونتيجة لذلك يحدث تأخير أو رفض الخدمة لعملاء آخرين. إذا تم تطبيق الحد من الأسعار ، فسيحدد جميع العملاء بعدد ثابت من الطلبات لكل وحدة زمنية. بالإضافة إلى ذلك ، يمكن استخدام الحد من الأسعار عند الوصول إلى أجزاء من النظام المرتبطة بالبيانات الحساسة ؛ وبالتالي ، إذا تمكن المهاجم من الوصول إليها ، فلن يتمكن من الوصول بسرعة إلى جميع البيانات.
هناك العديد من الطرق المختلفة لتطبيق الحد من الأسعار. في هذه المقالة ، سننظر في إيجابيات وسلبيات الخوارزميات المختلفة ، وكذلك المشاكل التي قد تنشأ عند توسيع نطاق هذه الحلول.
طلب معالجة خوارزميات الحد الأقصى للسرعة
دلو متسرب (دلو متسرب)
Leaky Bucket عبارة عن خوارزمية توفر الطريقة الأبسط والأكثر سهولة للحد من سرعة المعالجة باستخدام قائمة انتظار ، والتي يمكن تمثيلها على أنها "مجموعة" تحتوي على طلبات. عند تلقي طلب ، تتم إضافته إلى نهاية قائمة الانتظار. عند فواصل زمنية منتظمة ، تتم معالجة العنصر الأول في قائمة الانتظار. هذا هو المعروف أيضا باسم طابور FIFO . إذا كانت قائمة الانتظار ممتلئة ، فسيتم تجاهل الطلبات الإضافية (أو "تسرب").
تكمن ميزة هذه الخوارزمية في أنها تعمل على تسهيل تفجّر الطلبات ومعالجتها بنفس السرعة تقريبًا ، ومن السهل تنفيذها على خادم واحد أو موازن التحميل ، فهي فعالة في استخدام الذاكرة ، نظرًا لأن حجم قائمة الانتظار لكل مستخدم محدود.
ومع ذلك ، مع زيادة حادة في حركة المرور ، قد يتم تعبئة قائمة الانتظار بالطلبات القديمة وحرمان النظام من القدرة على معالجة الطلبات الأكثر حداثة. كما أنه لا يضمن معالجة الطلبات في أي وقت محدد. بالإضافة إلى ذلك ، إذا قمت بتحميل موازنات لتوفير التسامح مع الخطأ أو زيادة الإنتاجية ، فعليك تنفيذ سياسة تنسيق وضمان تقييد عالمي بينها.
يوجد تنوع في هذه الخوارزمية - رمز الجرافة ("الجرد مع الرموز" أو "خوارزمية سلة العلامات").
في مثل هذا التطبيق ، تتم إضافة الرموز المميزة إلى "الجرافة" بسرعة ثابتة ، وعند معالجة الطلب ، يتم حذف الرمز المميز من "الجرافة" ؛ إذا لم يكن هناك عدد كافٍ من الرموز ، فسيتم تجاهل الطلب. يمكنك ببساطة استخدام الطابع الزمني كرموز.
هناك أشكال مختلفة تستخدم العديد من "الجرافات" ، في حين أن كلا من الأحجام ومعدل استلام الرموز المميزة فيها يمكن أن يختلفا عن "الجرافات" الفردية. إذا لم يكن هناك عدد كافٍ من الرموز المميزة في "المجموعة الأولى" لمعالجة الطلب ، فسيتم التحقق من وجودها في الثانية ، وما إلى ذلك ، ولكن يتم تقليل أولوية معالجة الطلب (كقاعدة عامة ، يتم استخدام ذلك في تصميم واجهات الشبكة عندما يمكنك ، على سبيل المثال ، تغيير قيمة الحقل حزمة معالجة DSCP ).
الفرق الرئيسي من تطبيق Leaky Bucket هو أن الرموز يمكن أن تتراكم عندما يكون النظام خاملاً ويمكن أن تحدث رشقات نارية في وقت لاحق ، في حين ستتم معالجة الطلبات (نظرًا لوجود عدد كافٍ من الرموز) ، بينما يُضمن Leaky Bucket حتى في حالة التوقف.
نافذة ثابتة
تستخدم هذه الخوارزمية نافذة n ثانية لتتبع الطلبات. عادةً ، يتم استخدام قيم مثل 60 ثانية (دقيقة) أو 3600 ثانية (ساعة). يزيد كل طلب وارد العداد لهذه النافذة. إذا تجاوز العداد قيمة عتبة معينة ، فسيتم تجاهل الطلب. عادةً ما يتم تحديد النافذة من خلال الحد الأدنى للفاصل الزمني الحالي ، أي عندما يبلغ عرض النافذة 60 ثانية ، ينتقل الطلب الذي يصل الساعة 12:00:03 إلى النافذة 12:00:00.
ميزة هذه الخوارزمية هي أنها توفر معالجة الطلبات الأكثر حداثة ، دون الاعتماد على معالجة الطلبات القديمة. ومع ذلك ، يمكن أن تؤدي زيادة عدد الزيارات المفاجئة بالقرب من حدود النافذة إلى مضاعفة عدد الطلبات التي تتم معالجتها ، نظرًا لأنها تتيح طلبات كل من النافذة الحالية والإطار التالي لفترة قصيرة من الوقت. بالإضافة إلى ذلك ، إذا كان العديد من المستخدمين ينتظرون إعادة ضبط عداد النوافذ ، على سبيل المثال ، في نهاية الساعة ، فيمكنهم إثارة زيادة في التحميل في الوقت الحالي نظرًا لحقيقة وصولهم إلى واجهة برمجة التطبيقات في نفس الوقت.
انزلاق سجل
تتضمن هذه الخوارزمية تتبع الطوابع الزمنية لكل طلب مستخدم. يتم تخزين هذه السجلات ، على سبيل المثال ، في مجموعة تجزئة أو جدول ويتم فرزها حسب الوقت ؛ يتم تجاهل السجلات خارج الفاصل الزمني المراقبة. عندما يصل طلب جديد ، نحسب عدد السجلات لتحديد عدد الطلبات. إذا كان الطلب خارج الكمية المسموح بها ، فسيتم تجاهله.
تكمن ميزة هذه الخوارزمية في أنها لا تخضع للمشاكل التي تنشأ عند حدود الإطار الثابت ، أي أنه سيتم التقيد الصارم بالحد الأقصى للسرعة. بالإضافة إلى ذلك ، نظرًا لأن طلبات كل عميل تتم مراقبتها بشكل فردي ، لا يوجد نمو في ذروة الحمل في بعض النقاط ، وهي مشكلة أخرى في الخوارزمية السابقة.
ومع ذلك ، يمكن أن يكون تخزين المعلومات حول كل طلب باهظًا ، بالإضافة إلى ذلك ، يتطلب كل طلب حساب عدد الطلبات السابقة ، والتي من المحتمل أن تكون على المجموعة بأكملها ، ونتيجة لذلك فإن هذا النهج لا يتناسب بشكل جيد مع التعامل مع رشقات كبيرة من حركة المرور ورفض هجمات الخدمة.
انزلاق النافذة
هذا هو النهج المختلط الذي يجمع بين التكلفة المنخفضة لمعالجة النافذة الثابتة والمعالجة المتقدمة لحالات الحدود Sliding Log . كما هو الحال في الإطار الثابت البسيط ، فإننا نتتبع العداد لكل نافذة ، ثم نأخذ في الاعتبار القيمة المرجحة لتكرار طلب النافذة السابقة بناءً على الطابع الزمني الحالي لتخفيف رشقات المرور. على سبيل المثال ، إذا انقضى 25٪ من وقت النافذة الحالية ، فإننا نأخذ بعين الاعتبار 75٪ من طلبات السابقة. تتيح لنا كمية صغيرة نسبياً من البيانات اللازمة لتتبع كل مفتاح إمكانية القياس والعمل في مجموعة كبيرة.
تسمح لك هذه الخوارزمية بتقييد معدل الفائدة ، مع الحفاظ على الأداء الجيد. بالإضافة إلى ذلك ، هذه طريقة مفهومة لنقل معلومات العملاء حول الحد من عدد الطلبات ، وكذلك تجنب المشاكل التي تنشأ عند تنفيذ خوارزميات الحد من الأسعار الأخرى.
الحد من معدل في النظم الموزعة
سياسات المزامنة
إذا كنت ترغب في تعيين الحد الأقصى للسعر العام عند الوصول إلى مجموعة تتكون من عدة عقد ، فأنت بحاجة إلى تطبيق سياسة تقييد. إذا كانت كل عقدة تتبع فقط القيود الخاصة بها ، فيمكن للمستخدم تجاوزها ببساطة عن طريق إرسال الطلبات إلى عقد مختلفة. في الواقع ، كلما زاد عدد العقد ، زاد احتمال أن يتمكن المستخدم من تجاوز الحد العام.
أسهل طريقة لوضع حدود هي تكوين "جلسة لاصقة" على الموازن بحيث يتم توجيه المستخدم إلى العقدة نفسها. عيوب هذه الطريقة هي عدم تحمل الخطأ ومشاكل القياس عند تحميل عقد نظام المجموعة بشكل زائد.
أفضل حل ، والذي يسمح بقواعد أكثر مرونة لموازنة الحمل ، هو استخدام مستودع بيانات مركزي (حسب اختيارك). يمكنه تخزين عدادات عدد الطلبات لكل نافذة ومستخدم. المشاكل الرئيسية لهذا النهج هي الزيادة في وقت الاستجابة بسبب طلبات التخزين وظروف السباق.
شروط السباق
واحدة من أكبر المشاكل مع مستودع البيانات المركزي هو إمكانية ظروف السباق عند المنافسة. يحدث هذا عند استخدام نهج get-then-set الطبيعي ، والذي تقوم فيه باستخراج العداد الحالي ، وتزيده ، ثم ترسل القيمة الناتجة إلى المتجر. تكمن مشكلة هذا النموذج في أنه خلال الوقت المطلوب لإكمال الدورة الكاملة لهذه العمليات (أي ، القراءة ، الزيادة والكتابة) ، قد تأتي طلبات أخرى ، حيث يتم تخزين العداد بقيمة غير صالحة (أقل). يتيح ذلك للمستخدم إرسال طلبات أكثر من خوارزمية الحد من المعدل.
إحدى الطرق لتجنب هذه المشكلة هي تعيين قفل حول المفتاح المعني ، ومنع الوصول إلى قراءة أو كتابة أي عمليات أخرى إلى العداد. ومع ذلك ، يمكن أن يصبح هذا عنق الزجاجة سريعًا في الأداء ولا يتطور بشكل جيد ، خاصة عند استخدام الخوادم البعيدة ، مثل Redis ، كمخزن إضافي للبيانات.
هناك طريقة أفضل بكثير تتمثل في تحديد - get-get ، الذي يعتمد على العوامل الذرية ، والذي يسمح لك بزيادة سريعة وفحص العداد دون التدخل في العمليات الذرية.
تحسين الأداء
عيب آخر لاستخدام مستودع بيانات مركزي هو الزيادة في وقت الاستجابة بسبب التأخير في التحقق من العدادات المستخدمة في الحد من الأسعار ( وقت ذهابا وإيابا ، أو "تأخير ذهابا وإيابا "). لسوء الحظ ، حتى التحقق من التخزين السريع مثل Redis سيؤدي إلى تأخير إضافي لعدد قليل من المللي ثانية لكل طلب.
لجعل تعريف القيد مع الحد الأدنى من التأخير ، من الضروري إجراء اختبارات في الذاكرة المحلية. يمكن القيام بذلك عن طريق تخفيف الظروف للتحقق من السرعة واستخدام نموذج ثابت في نهاية المطاف.
على سبيل المثال ، يمكن لكل عقدة إنشاء دورة مزامنة بيانات يتم خلالها مزامنتها مع المستودع. تنقل كل عقدة بشكل دوري قيمة العداد لكل مستخدم والإطار الذي تأثر ، إلى المتجر ، والذي سيقوم بتحديث القيم تلقائيًا. ثم يمكن للعقدة تلقي قيم جديدة وتحديث البيانات في الذاكرة المحلية. ستتيح هذه الدورة في النهاية تحديث جميع العقد في الكتلة.
يجب أن تكون الفترة التي تتم فيها مزامنة العقد قابلة للتخصيص. ستؤدي فواصل التزامن الأقصر إلى تقليل التباين في البيانات عندما يتم توزيع الحمل بالتساوي عبر عدة عقد من الكتلة (على سبيل المثال ، في حالة تحديد الموازن للعقد وفقًا لمبدأ "الجولة المستديرة") ، بينما تؤدي الفواصل الزمنية الأطول إلى تحميل حمل أقل للقراءة / الكتابة للتخزين وخفض التكلفة في كل عقدة لتلقي البيانات المتزامنة.
مقارنة بين خوارزميات الحد من الأسعار
على وجه التحديد ، في حالتنا ، يجب ألا نرفض طلبات العميل الخاصة بواجهة برمجة التطبيقات ، ولكن على أساس البيانات ، على العكس من ذلك ، لا تنشئها ؛ ومع ذلك ، ليس لدينا الحق في "فقدان" الطلبات. للقيام بذلك ، عند إرسال إشعار ، نستخدم المعلمة send_rate ، والتي تشير إلى الحد الأقصى لعدد الإخطارات التي سنرسلها في الثانية الواحدة عند الإرسال.
وبالتالي ، لدينا عامل معين يؤدي العمل في الوقت المخصص (في المثال الخاص بي ، القراءة من ملف) ، والذي يستقبل واجهة RateLimitingInterface كمدخلات ، ونقول ما إذا كان من الممكن تنفيذ طلب ما في وقت معين ومدة تشغيله.
interface RateLimitingInterface { public function __construct(int $rate); public function canDoWork(float $currentTime): bool; }
يمكن العثور على جميع أمثلة الكود على جيثب هنا .
سأشرح لك على الفور سبب حاجتك لنقل شريحة زمنية إلى Worker. الحقيقة هي أنه من المكلف للغاية تشغيل برنامج خفي منفصل لمعالجة إرسال رسالة واحدة بحد أقصى للسرعة ، لذلك يتم استخدام send_rate بالفعل كمعلمة "عدد الإشعارات لكل وحدة زمنية" ، والتي تتراوح بين 0.01 و 1 ثانية ، اعتمادًا على الحمل.
في الواقع ، نقوم بمعالجة ما يصل إلى 100 طلب مختلف مع send_rate في الثانية الواحدة ، مع تخصيص 1 / N ثانية لكل مقدار من الوقت ، حيث N هو عدد مرات الدفع التي تمت معالجتها بواسطة هذا البرنامج الخفي. المعلمة الأكثر إثارة للاهتمام بالنسبة لنا أثناء المعالجة هي ما إذا كان سيتم احترام send_rate (يُسمح بالأخطاء الصغيرة في اتجاه واحد أو آخر) والحمل على أجهزتنا (الحد الأدنى لعدد مرات الوصول إلى المخازن ووحدة المعالجة المركزية واستهلاك الذاكرة).
للبدء ، دعنا نتعرف على النقاط الزمنية التي يعمل فيها العامل حقًا. من أجل البساطة ، عالج هذا المثال ملفًا مكونًا من 10000 سطر مع send_rate = 1000 (أي ، نقرأ 1000 سطر في الثانية من الملف).
في اللقطات ، تحدد العلامات اللحظات وعدد مكالمات fget لجميع الخوارزميات. في الواقع ، يمكن أن يكون هذا نداءً لقاعدة بيانات أو موردًا تابعًا لجهة خارجية أو أي استفسارات أخرى ، نرغب في الحد منها لكل وحدة زمنية.
على مقياس X - الوقت من بداية المعالجة ، من 0 إلى 10 ثوان ، يتم تقسيم كل ثانية إلى أعشار ، وبالتالي يكون الجدول من 0 إلى 100).
نرى أنه على الرغم من حقيقة أن جميع الخوارزميات تتوافق مع مراعاة send_rate (لهذا الغرض فهي مصممة) ، فإن " الإطار الثابت وسجل المنزلق " يعطيان "الحمولة بأكملها في وقت واحد تقريبًا ، وهو ما لا يناسبنا كثيرًا ، في حين أن رمز الجرافة والانزلاق يقوم Windows بتوزيعها بالتساوي لكل وحدة زمنية (باستثناء ذروة التحميل في وقت البدء ، بسبب نقص البيانات حول التحميل في النقاط السابقة من الوقت).
نظرًا لحقيقة أن الكود لا يعمل في الواقع مع نظام الملفات المحلي ، ولكن مع تخزين طرف ثالث ، قد يتأخر الجواب ، وقد تكون هناك مشكلات في الشبكة والعديد من المشكلات الأخرى ، وسنحاول التحقق من كيفية تصرف هذه الخوارزمية أو تلك عندما تستغرق الطلبات بعض الوقت لم يكن. على سبيل المثال ، بعد 4 و 6 ثوان.
هنا ، قد يبدو أن " النافذة الثابتة" لم تعمل بشكل صحيح ومعالجتها مرتين أكثر من الطلبات المتوقعة في أول ومن 7 إلى 8 ثوان ، ولكن في الواقع هذا ليس كذلك ، حيث يتم حساب الوقت من لحظة الإطلاق على الرسم البياني ، وتستخدم الخوارزمية الطابع الزمني يونيكس الحالي .
بشكل عام ، لم يتغير أي شيء بشكل أساسي ، لكننا نرى أن Token Bucket ينعم الحمل بسلاسة أكبر ولا يتجاوز الحد المحدد للسعر ، ولكن سجل Sliding في حالة التوقف يمكن أن يتجاوز القيمة المسموح بها.
استنتاج
درسنا جميع الخوارزميات الأساسية لتطبيق الحد من معدل ، كل منها لها إيجابيات وسلبيات ومناسبة لمختلف المهام. نأمل أنه بعد قراءة هذه المقالة ، سوف تختار أنسب الخوارزمية لحل مشكلتك.