A Comparative Survey of API Rate-Limiting Algorithms: Token Bucket, Leaky Bucket, and Sliding Window
تستعرض هذه الورقة وتقارن تجريبياً بين خمس خوارزميات شائعة الاستخدام لتحديد معدل واجهة برمجة التطبيقات (API)—وهي دلو الرموز (token bucket)، ودلو التسريب (leaky bucket)، والنافذة الثابتة (fixed window)، وسجل النافذة المنزلقة (sliding window log)، وعداد النافذة المنزلقة (sliding window counter)—لتقييم مقايضاتها بين القدرة على تحمل التدفق المفاجئ والدقة، مما يوفر في النهاية إرشادات لاختيار الخوارزمية الأكثر ملاءمة بناءً على خصائص حركة المرور وقيود النظام المحددة.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تعتمد الخدمات الرقمية الحديثة على توازن دقيق بين التوافر والحماية. فعندما يحاول الملايين من الأشخاص الوصول إلى موقع إلكتروني أو تطبيق في وقت واحد، يمكن للخوادم الكامنة خلف الكواليس أن تصبح مثقلة فوق طاقتها، تماماً مثل جسر ذي مسار واحد يزدحم فجأة بسبب تدفق مروري مفاجئ. ولمنع هذا الانهيار، يستخدم المهندسون آلية تسمى "تحديد معدل الطلبات" (rate limiting)، والتي تعمل كحارس بوابة. يقوم هذا الحارس بعدّ عدد الطلبات التي يرسلها مستخدم أو جهاز معين خلال فترة زمنية محددة، ويمنع أي طلبات تتجاوز حداً آمناً. والهدف من ذلك ليس معاقبة المستخدمين، بل ضمان بقاء النظام مستقراً للجميع، ومنع عدد قرا few من المستخدمين "الثقلاء" من استهلاك جميع الموارد المتاحة. ومع ذلك، لا تصل جميع حركات المرور (البيانات) في تدفق ثابت؛ فأحياناً تأتي في شكل دفعات مفاجئة وحادة، كما يحدث عند انتشار خبر عاجل أو عند إعادة محاولة نظام ما للاتصال بعد فشله. ويتمثل التحدي الذي يواجه المهندسين في تقرير كيفية التعامل مع هذه الدفعات: هل يجب أن يسمح النظام بمرور طفرة مؤقتة، أم يجب أن يفرض حداً ثابتاً بصرامة بغض النظر عن الموقف؟
تبحث دراسة حديثة أجراها عُمير سليم في القواعد الرياضية المختلفة المستخدمة لبناء حراس البوابات الرقمية هذه. ويركز البحث على خمس طرق محددة تُستخدم بشكل شائع في الصناعة، وهي: دلو الرموز (token bucket)، ودلو التسريب (leaky bucket)، وعداد النافذة الثابتة (fixed window counter)، وسجل النافذة المنزلقة (sliding window log)، وعداد النافذة المنزلقة (sliding window counter). لكل من هذه الطرق طريقة مختلفة في تتبع الوقت وعدّ الطلبات، مما يؤدي إلى سلوكيات مختلفة عند حدوث طفرة في حركة البيانات. ولفهم أي طريقة هي الأفضل، لم يعتمد المؤلف على النظرية وحدها، بل بنى محاكاة حاسوبية لاختبارها جميعاً تحت ظروف متطابقة. أنشأت المحاكاة تدفقاً واقعياً يضم أكثر من ألف طلب على مدار مائة ثانية. تضمن هذا التدفق تدفقاً خلفياً ثابتاً قدره ثمانية طلبات في الثانية، تخللته دفعتان متميزتان من النشاط: فترة مدتها خمس ثوانٍ قفز فيها حجم حركة البيانات إلى أربعين طلباً في الثانية، تلتها طفرة أكثر حدة لمدة ثانيتين وصلت فيها إلى ستين طلباً في الثانية. ومن خلال تمرير نفس نمط حركة البيانات هذا عبر كل خوارزمية من الخوارزميات الخمس، تمكنت الدراسة من قياس عدد الطلبات التي قبلتها كل طريقة بالضبط، وعدد الطلبات التي رفضتها، وكيف كان سلوك النظام أثناء الطفرات.
وكشفت النتائج عن انقسام واضح في كيفية تعامل هذه الخوارزميات مع ضغط طفرة حركة البيانات. فقد أظهر "دلو الرموز" و"دلو التسريب" أداءً متطابقاً تقريباً عند استخدامهما ببساطة لاتخاذ قرار بقبول أو رفض الطلب. سمحت كلتا الطريقتين للنظام باستيعاب الدفعات بشكل أكثر فعالية من غيرهما، حيث قبلتا إجمالي 844 طلباً من أصل 1,057 تم إرسالها، مما يعني نسبة قبول تبلغ حوالي 80 بالمائة. وخلال الدفعة الكبرى الأولى، سمحت هاتان الطريقتان بمرور 69 طلباً، وخلال الدفعة الثانية الأكثر حدة، سمحتا بمرور 38 طلباً. حدث هذا لأن هذه الخوارقات مصممة بـ "قدرة استيعابية" مدمجة لتخزين "إذن إضافي" للاستخدام المستقبلي، مما يسمح لها بتسوية الطفرات دون إبعاد المستخدمين فوراً. وفي المقابل، كان "سجل النافذة المنزلقة" الأكثر صرامة من بين جميع الطرق؛ إذ لم يسمح أبداً بأكثر من عشرة طلبات في ثانية واحدة، ملتزماً بدقة بالحد المقرر. وبينما وفر هذا أقصى قدر من الحماية ضد الحمل الزائد، إلا أنه جاء بتكلفة عالية: فقد رفض أكبر قدر من حركة البيانات، حيث قبل 67.9 بالمائة فقط من الطلبات. لقد كانت الطريقة الوحيدة التي تضمن عدم رؤية النظام لأي طفرة تتجاوز الحد، لكنها فعلت ذلك عبر رد الكثير من المستخدمين الشرعيين أكثر من الطرق الأخرى.
أما الطرق الثلاث المتبقية، فقد وقعت في منطقة وسطى، حيث أظهرت عيوباً يمكن التنبؤ بها بناءً على كيفية قياسها للوقت. فقد عانى "عداد النافذة الثابتة"، الذي يعيد ضبط عداده عند بداية كل ثانية جديدة، من خطأ توقيت عند الحدود الزمنية. ولأنه قد يعيد ضبط عداده تزامناً مع وصول دفعة من حركة البيانات، فقد سمح بطفرة مؤقتة تصل إلى خمسة عشر طلباً في ثانية واحدة، وهو ما يتجاوز الحد المقصود. وحاول "عداد النافذة المنزلقة" إصلاح هذه المشكلة من خلال النظر في الثانية السابقة أيضاً، لكنه عالج المشكلة جزئياً فقط، حيث بلغت ذروته ثلاثة عشر طلباً. ووجدت الدراسة أن اختيار الخوارزمية يعتمد كلياً على ما يحتاج النظام لحمايته. فإذا كان الهدف هو إرضاء المستخدمين والسماح بالدفعات الطبيعية من النشاط، مثل إعادة تحميل صفحة تحتوي على استدعاءات بيانات متعددة، فإن "دلو الرموز" هو الخيار الأفضل لأنه يوازن بين نسبة القبول العالية والأداء المستقر. أما إذا كان الهدف هو حماية نظام فرعي هش لا يمكنه تحمل أي طفرة على الإطلاق، فإن "سجل النافذة المنزلقة" هو الخيار الأفضل، رغم انخفاض نسبة قبوله للطلبات. وتخلص الأبحاث إلى أنه لا توجد أداة واحدة مثالية لكل مهمة؛ وبدلاً من ذلك، يجب على المهندسين اختيار الطريقة التي تتوافق مع مدى تحملهم لطفرات حركة البيانات وموارد الذاكرة المتاحة لديهم.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.