Clever Geek Handbook

Nilai batas dengan Python dan Redis



Pada artikel ini, kita akan melihat beberapa algoritma batas kecepatan berbasis Python dan Redis, dari implementasi yang paling sederhana hingga Algoritma Tingkat Sel Generik (GCRA ) lanjutan . Kami akan menggunakan redis-py



untuk berinteraksi dengan Redis ( pip install redis) . Saya sarankan untuk menggandakan repositori saya untuk bereksperimen dengan batas kueri.



Batas waktu



Pendekatan pertama untuk membatasi jumlah permintaan per periode adalah dengan menggunakan algoritme terbatas waktu: untuk setiap kunci pembatas (kunci tingkat, sesuatu yang unik, seperti nama panggilan atau alamat IP), penghitung (awalnya menetapkan nilai batas) dan tanggal kedaluwarsa disimpan secara terpisah (periode), yang menurun saat permintaan diterima.



Dengan Python dan Redis, Anda dapat mengimplementasikan algoritma ini sebagai berikut:



  1. Memeriksa keberadaan kunci kendala.
  2. Jika ada, maka inisialisasi dengan nilai batas ( Redis SETNX ) dan tanggal kedaluwarsa ( Redis EXPIRE ).
  3. Kami menurunkan nilai ini dengan setiap permintaan berikutnya ( Redis DECRBY ).
  4. Kueri dihentikan hanya jika nilainya di bawah nol.
  5. Setelah jangka waktu tertentu, kunci otomatis dihapus.


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


Anda dapat melihat bagaimana kode ini bekerja saat meniru batas 20 permintaan dalam 30 detik (untuk membuatnya lebih jelas, saya meletakkan fungsinya di modul). 



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')


Hanya 20 permintaan pertama yang tidak akan dibatasi, setelah itu Anda harus menunggu 30 detik agar permintaan baru dapat dikirim lagi.



Kerugian dari pendekatan ini adalah tidak membatasi frekuensi, tetapi jumlah permintaan yang dibuat oleh pengguna selama periode tertentu. Jika seluruh batas segera habis, Anda harus menunggu akhir periode.



Algoritme ember bocor



Ada pendekatan di mana kami dapat membatasi frekuensi dengan sangat hati-hati: ini adalah algoritme keranjang saat ini . Prinsip pengoperasiannya sama dengan ember bocor yang sebenarnya: kami menuangkan air (permintaan) ke dalam ember sampai ke tepinya, sementara sebagian air terus mengalir keluar melalui lubang di bagian bawah (biasanya dilakukan dengan proses latar belakang). Jika jumlah air yang dituangkan ke dalam ember lebih besar dari jumlah air yang keluar, maka ember tersebut terisi, dan jika sudah penuh, permintaan baru tidak lagi diterima.



Bagaimana Algoritma Bekerja



Anda dapat melewati pendekatan ini untuk solusi yang lebih elegan yang tidak memerlukan proses terpisah untuk meniru kebocoran: Algoritma Laju Sel Generik.



Algoritma Kontrol Kecepatan Sel Umum



GCRA dibuat dalam industri telekomunikasi, yang disebut dengan Asynchronous Transfer Mode (ATM). Ini digunakan oleh manajer jaringan ATM untuk menunda atau membuang sel - paket data kecil dengan ukuran tetap - yang mencapai tingkat yang lebih tinggi dari batas yang diberikan.



GCRA melacak batas yang tersisa menggunakan apa yang disebut Theoretical Arrival Time (TAT) dari setiap permintaan: 



tat = current_time + period


dan membatasi permintaan berikutnya jika waktu kedatangan kurang dari TAT saat ini. Ini berfungsi dengan baik jika frekuensinya 1 permintaan / periode, ketika permintaan dibagi menjadi beberapa periode. Namun kenyataannya frekuensi biasanya dihitung sebagai batas / periode. Misalnya, jika frekuensinya 10 permintaan / 60 detik, maka pengguna dapat membuat 10 permintaan dalam 6 detik pertama. Dan dengan frekuensi 1 permintaan / 6 detik, dia harus menunggu 6 detik di antara permintaan.



Untuk dapat mengirim sekelompok permintaan dalam waktu singkat dan mempertahankan batasan jumlah mereka untuk periode dengan batas> 1, setiap permintaan harus dibagi dengan rasio periode / batas, dan kemudian waktu kedatangan teoritis berikutnya ( new_tat) akan dihitung secara berbeda. Mari kita tunjukkan waktu kedatangan permintaan sebagai t:



  • new_tat = tat + period / limitjika permintaan dikelompokkan ( t <= tat)
  • new_tat = t + period / limitjika permintaan tidak dikelompokkan ( t > tat)


Karenanya: 



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


Permintaan akan terbatas, jika new_tatlebih besar daripada jumlah waktu saat ini dan periode: new_tat > t + period. Saat new_tat = tat + period / limitkita mendapatkan tat + period / limit > t + period. Oleh karena itu, Anda perlu membatasi kueri hanya jika tat - t > period - period / limit. 



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


Dalam hal ini, kami tidak perlu memperbarui TAT, karena permintaan terbatas tidak memiliki waktu kedatangan teoretis.



Sekarang mari kita buat versi terakhir kode! 



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


Kami menggunakan Redis TIME karena GCRA bergantung pada waktu, dan kami perlu memastikan waktu saat ini konsisten di beberapa penerapan (perbedaan jam antara mesin yang berbeda dapat menyebabkan kesalahan positif).



Kode ini menunjukkan kinerja GCRA pada 10 permintaan / 60 dtk. 



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')


Algoritme tidak membatasi 10 permintaan pertama, tetapi Anda harus menunggu setidaknya 6 detik untuk membuat permintaan berikutnya. Cobalah untuk menjalankan skrip setelah beberapa saat dan ubah nilai batas dan periode (misalnya, limit = 1dan period=timedelta(seconds=6)).



Untuk menjaga penerapannya tetap bersih, saya tidak menambahkan kunci antara menerima dan mengirim panggilan. Tetapi diperlukan untuk beberapa permintaan dengan kunci yang sama dan pada waktu yang sama. Dengan Lua, Anda dapat menambahkan penguncian sebagai pengelola konteks. 



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


Kode lengkapnya ada di GitHub .


More articles:


All Articles