スライディングウィンドウアルゴリズムを用いたレート制限

レート制限シリーズのこの部分では、スライディングウィンドウアルゴリズムを導入し、Pythonで実装します.
私は、これらの3つのアルゴリズムがレート制限技術にかなり良いゲートウェイであると思うので、私はここでシリーズを終えるつもりです.

スライディングウィンドウ

以前の固定ウィンドウアルゴリズムとは異なり、このアルゴリズムは、固定時間単位に基づいて要求を制限しません.
固定ウィンドウに関する問題は、ウィンドウの端に巨大なバーストを許容することでした.なぜなら、リクエストのバーストを送信するために、現在のウィンドウと次のウィンドウの容量を組み合わせることができるからです.
スライディングウィンドウでは、以前のカウンタを考慮して、それを修正しようとすると、よりスムーズにフローを引き起こします.
例で説明しましょう.60秒の時間単位と50の容量を持つレートリミッタがあることを想像してください.
リクエストは00 : 01 : 20に入りました.現在の時間単位はまだ容量が残っているが、我々は以前のカウンタを学んだ結果も結果に影響を与えます.
前のカウンタは、ウィンドウにまだ占有されているスペースと同じくらいの影響を与えるだけです.私たちの例では、それは~ 67 %でしょう.
そのために、推定カウントを計算するために以下の式を使用する.
前のカウンタ*(時間単位-現在のカウンタへの時間)/現在のカウンタ
EC = 50 * 0.67 + 20 = 53.5
容量は50だったので、この要求は53.5＞50から低下している.
もう一つのリクエストが00 : 01 : 40に入ってきたら、ECは次のようになります.
ec = 50 * 0.34 + 20 = 37
この要求は37＜50以降である.

実装

この非常に単純な実装では、1秒の時間枠でパケットを制限するために、スライディングウィンドウを使用するレートリミッタを構築します.
インスタンス化されているときに3つの引数を持つクラスを定義することから始めます.

キャパシティ:2番目に通過できる許容されたパケットの数.

timeCount単位:秒単位の時間単位の長さ.

この関数は、パケットが転送されているときに呼び出されます.

droptle callback :この関数は、パケットを破棄するときに呼び出されます.

from time import time, sleep


class SlidingWindow:

    def __init__(self, capacity, time_unit, forward_callback, drop_callback):
        self.capacity = capacity
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

        self.cur_time = time()
        self.pre_count = capacity
        self.cur_count = 0

cur_timeは我々の現在の時間単位の端です.pre_countは前のカウンタです.我々は、レート制限器の冒頭で破裂するのを防ぐために、これを塗ります.cur_countは、新しい要求が来るとき、満たされる現在のカウンタです.
そして、魔法が起こるhandle()を定義します.

def handle(self, packet): #1
    if (time() - self.cur_time) > self.time_unit: #2
        self.cur_time = time()
        self.pre_count = self.cur_count
        self.cur_count = 0

    ec = (self.pre_count * (self.time_unit - (time() - self.cur_time)) / self.time_unit) + self.cur_count #3

    if (ec > self.capacity): #4
        return self.drop_callback(packet)

    self.cur_count += 1 #5
    return self.forward_callback(packet)

handleは1つのパラメタだけを受け入れます:パケット.

現在の時間単位が通過されるならば、新しい時間単位に切り替えてください.

は、与えられた式

に基づいて推定カウントを計算しますecが容量より大きい場合、パケットを落とす.そうでなければ、現在のカウンタに1を加え、パケットを転送する.

最終コード

from time import time, sleep


class SlidingWindow:

    def __init__(self, capacity, time_unit, forward_callback, drop_callback):
        self.capacity = capacity
        self.time_unit = time_unit
        self.forward_callback = forward_callback
        self.drop_callback = drop_callback

        self.cur_time = time()
        self.pre_count = capacity
        self.cur_count = 0

    def handle(self, packet):

        if (time() - self.cur_time) > self.time_unit:
            self.cur_time = time()
            self.pre_count = self.cur_count
            self.cur_count = 0

        ec = (self.pre_count * (self.time_unit - (time() - self.cur_time)) / self.time_unit) + self.cur_count

        if (ec > self.capacity):
            return self.drop_callback(packet)

        self.cur_count += 1
        return self.forward_callback(packet)


def forward(packet):
    print("Packet Forwarded: " + str(packet))


def drop(packet):
    print("Packet Dropped: " + str(packet))


throttle = SlidingWindow(5, 1, forward, drop)

packet = 0

while True:
    sleep(0.1)
    throttle.handle(packet)
    packet += 1

次のようにしてください.

Packet Forwarded: 0
Packet Forwarded: 1
Packet Dropped: 2
Packet Forwarded: 3
Packet Dropped: 4
Packet Forwarded: 5
Packet Dropped: 6
Packet Forwarded: 7
Packet Dropped: 8
Packet Forwarded: 9
Packet Dropped: 10
Packet Forwarded: 11
Packet Dropped: 12
Packet Forwarded: 13
Packet Dropped: 14
Packet Forwarded: 15
Packet Dropped: 16
Packet Forwarded: 17
Packet Dropped: 18
Packet Forwarded: 19
Packet Dropped: 20
Packet Forwarded: 21
Packet Dropped: 22
Packet Forwarded: 23

結論

このポストでは、スライディングウィンドウアルゴリズムについて学び、Pythonでそれを実装しようとしました.
このシリーズでは、トークンバケツ、固定ウィンドウ、およびスライドウィンドウをカバーしました.リークバケットやスライドログのような有名なアルゴリズムがあるにもかかわらず、私はこれらの3つはほとんどの律速アルゴリズムの基本的なアイデアをカバーしていると信じているので、ここでこのシリーズを終了することを決めた、そしてこのシリーズはまた、短くて簡単になると予想された.
あなたの時間に感謝します、そして、私はあなたの他のポストで会いたいです: