حدود المعدل مع بايثون وريديس

في هذه المقالة ، سنلقي نظرة على بعض خوارزميات حد المعدل المستندة إلى Python و Redis ، من أبسط تطبيق إلى خوارزمية معدل الخلية العامة المتقدمة (GCRA ). سنستخدم redis-py



للتفاعل مع Redis ( pip install redis) . أقترح استنساخ المستودع الخاص بي لتجربة قيود الاستعلام.

المهلة

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



باستخدام Python و Redis ، يمكنك تنفيذ هذه الخوارزمية على النحو التالي:

1. التحقق من وجود مفتاح القيد.
2. إذا كان موجودا، ثم تهيئة مع قيمة الحد ( رديس SETNX ) وتاريخ انتهاء الصلاحية ( رديس EXPIRE ).
3. نقوم بتقليل هذه القيمة مع كل طلب لاحق ( Redis DECRBY ).
4. يتم إيقاف الاستعلامات فقط عندما تنخفض القيمة إلى ما دون الصفر.
5. بعد فترة زمنية محددة ، يتم حذف المفتاح تلقائيًا.

from datetime import timedelta
from redis import Redis

def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    if r.setnx(key, limit):
        r.expire(key, int(period.total_seconds()))
    bucket_val = r.get(key)
    if bucket_val and int(bucket_val) > 0:
        r.decrby(key, 1)
        return False
    return True

يمكنك أن ترى كيف يعمل هذا الرمز عند محاكاة حد 20 طلبًا في 30 ثانية (لتوضيح الأمر ، أضع الوظيفة في وحدة نمطية).

import redis
from datetime import timedelta
from ratelimit import time_bucketed

r = redis.Redis(host='localhost', port=6379, db=0)
requests = 25

for i in range(requests):
    if time_bucketed.request_is_limited(r, 'admin', 20, timedelta(seconds=30)):
        print ('Request is limited')
    else:
        print ('Request is allowed')

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



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

خوارزمية دلو التسرب

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



كيف تعمل الخوارزمية



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

خوارزمية التحكم في معدل الخلية المعمم

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



تتعقب GCRA الحد المتبقي باستخدام ما يسمى بوقت الوصول النظري (TAT) لكل طلب:

tat = current_time + period

ويحد من الطلب التالي إذا كان وقت الوصول أقل من TAT الحالي. يعمل هذا بشكل جيد إذا كان التكرار هو طلب / فترة واحدة ، عندما يتم تقسيم الطلبات إلى فترات. لكن في الواقع ، عادةً ما يتم حساب الترددات كحد / فترة. على سبيل المثال ، إذا كان التكرار هو 10 طلبات / 60 ثانية ، فيمكن للمستخدم إجراء 10 طلبات في أول 6 ثوانٍ. وبتكرار طلب واحد / 6 ثوانٍ ، سيتعين عليه الانتظار 6 ثوانٍ بين الطلبات.



لتتمكن من إرسال مجموعة من الطلبات في غضون فترة قصيرة والحفاظ على الحد الأقصى لعددهم لفترة بحد أكبر> 1 ، يجب تقسيم كل طلب على نسبة الفترة / الحد ، وبعد ذلك new_tatسيتم حساب وقت الوصول النظري التالي ( ) بشكل مختلف. دعنا نشير إلى وقت وصول الطلب على النحو التالي t:

• new_tat = tat + period / limitإذا تم تجميع الطلبات ( t <= tat)
• new_tat = t + period / limitإذا لم يتم تجميع الطلبات ( t > tat)

بالتالي:

new_tat = max(tat, t) + period / limit

سيتم طلب محدودة، إذا new_tatأكبر من مجموع الوقت الحالي والفترة: new_tat > t + period. عندما new_tat = tat + period / limitنحصل tat + period / limit > t + period. لذلك ، تحتاج إلى تقييد الاستعلامات فقط عندما tat - t > period - period / limit.

      period — period / limit
      <----------------------->
--|----------------------------|--->
  t                           TAT

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



الآن دعونا نبني النسخة النهائية من الكود!

from datetime import timedelta
from redis import Redis

def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    period_in_seconds = int(period.total_seconds())
    t = r.time()[0]
    separation = round(period_in_seconds / limit)
    r.setnx(key, 0)
    tat = max(int(r.get(key)), t)
    if tat - t <= period_in_seconds - separation:
        new_tat = max(tat, t) + separation
        r.set(key, new_tat)
        return False
    return True

استخدمنا Redis TIME لأن GCRA تعتمد على الوقت ، ونحن بحاجة إلى التأكد من أن الوقت الحالي متسق عبر عمليات النشر المتعددة (يمكن أن تؤدي الاختلافات في الساعة بين الأجهزة المختلفة إلى نتائج إيجابية خاطئة).



يوضح هذا الرمز أداء GCRA عند 10 طلبات / 60 ثانية.

import redis
from datetime import timedelta
from ratelimit import gcra

r = redis.Redis(host='localhost', port=6379, db=0)
requests = 10

for i in range(requests):
    if gcra.request_is_limited(r, 'admin', 10, timedelta(minutes=1)):
        print ('Request is limited')
    else:
        print ('Request is allowed')

لا تحدد الخوارزمية الطلبات العشرة الأولى ، ولكن سيتعين عليك الانتظار لمدة 6 ثوانٍ على الأقل لتقديم الطلب التالي. حاول تشغيل البرنامج النصي بعد مرور بعض الوقت وقم بتغيير قيمة الحد والنقطة (على سبيل المثال ، limit = 1و period=timedelta(seconds=6)).



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

def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    period_in_seconds = int(period.total_seconds())
    t = r.time()[0]
    separation = round(period_in_seconds / limit)
    r.setnx(key, 0)
    try:
        with r.lock('lock:' + key, blocking_timeout=5) as lock:
            tat = max(int(r.get(key)), t)
            if tat - t <= period_in_seconds - separation:
                new_tat = max(tat, t) + separation
                r.set(key, new_tat)
                return False
            return True
    except LockError:
        return True

الكود الكامل موجود على جيثب .