PHPでAPIインターフェースのフローを制限する方法

インターフェース電流制限とは何ですか?

それでは、電流制限とは何でしょうか?名前が示すように、電流制限は、一定期間内の同時トラフィックと合計トラフィックを含むトラフィックを制限することです。ブロードバンド パッケージのトラフィックが 1 G であるのと同じように、使い果たされると消滅するため、周波数を制御します。使用量と 1 回の合計トラフィックの消費量。電流制限を通じて、システムの QPS を適切に制御でき、それによってシステムまたはインターフェイス サーバーの安定性を保護するという目的を達成できます。

インターフェース電流制限に一般的に使用されるアルゴリズム

カウンター方式

カウンター方式は、現在のアルゴリズムの中で最も単純で簡単です。制限アルゴリズム 実装されたアルゴリズム。たとえば、インターフェイス A の場合、1 分間のアクセス数は 100 を超えてはいけないと規定します。次に、これを行うことができます: 最初に、カウンター counter を設定できます。リクエストが来るたびに、カウンターは 1 ずつ増加します。カウンターの値が 100 より大きく、リクエストと最初のリクエストの間の間隔が 100 である場合、まだ 1 分以内であれば、リクエストが多すぎることを意味します; リクエストと最初のリクエストの間の間隔が 1 分を超えていて、カウンタの値が依然として電流制限範囲内にある場合は、カウンタをリセットします。具体的なアルゴリズムは次のとおりです。

疑似コードは次のとおりです。

class CounterDemo{
    private  $timeStamp;
    public  $reqCount=0;
    public  $limit=100;//时间窗口内最大请求数
    public $interval=1000; //时间窗口 ms
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        if($now<$this->timeStamp+$this->interval){
            //时间窗口内
            $this->reqCount++;
            return $this->reqCount<=$this->limit;
        }else{
            // 超时后重置
            $this->timeStamp=time();
            $this->reqCount=1;
            return true;
        }
    }
}

このアルゴリズムは単純に見えますが、非常に深刻な問題があります。重大度の問題です。下の図を参照してください:

上の図から、悪意のあるユーザーがいると仮定して、彼は 0:59 に 100 個のリクエストを即座に送信し、再度送信していることがわかります。 1:00 に 100 件のリクエストを受信すると、このユーザーは実際には 1 秒間に 200 件のリクエストを送信しました。先ほど規定したのは、1 分あたり最大 100 リクエスト、つまり 1 秒あたり最大 1.7 リクエストです。ユーザーは、タイム ウィンドウのリセット ノードでバースト リクエストを行うことで、レート制限を即座に超えることができます。ユーザーはアルゴリズムのこの抜け穴を利用して、アプリケーションを瞬時に圧倒する可能性があります。

関連する推奨事項: "php チュートリアル "

賢い友人なら、今の問題は実際には統計の精度が低すぎることにあることに気づいたかもしれません。では、この問題にうまく対処するにはどうすればよいでしょうか?言い換えれば、重大な問題の影響を軽減するにはどうすればよいでしょうか?以下でスライディング ウィンドウ アルゴリズムを見てみましょう。

スライディング ウィンドウ アルゴリズム

#上の図では、赤い長方形のボックス全体が時間ウィンドウを表しています。時間枠は 1 分です。次に、時間ウィンドウを分割します。たとえば、図では、スライディング ウィンドウを 6 つのグリッドに分割し、各グリッドが 10 秒を表します。 10 秒ごとに、タイム ウィンドウが 1 フレーム右にスライドします。各グリッドには独自の独立したカウンターがあり、たとえば、リクエストが 0:35 秒に到着すると、0:30 から 0:39 までの対応するカウンターが 1 ずつ増加します。

それでは、スライディング ウィンドウは、先ほどの重大な問題をどのように解決するのでしょうか?上の図を見ると、0:59 に到着した 100 件のリクエストは灰色のグリッドに収まり、1:00 に到着したリクエストはオレンジ色のグリッドに収まります。時間が 1:00 になると、ウィンドウが 1 つ右に移動します。このときのタイム ウィンドウ内のリクエストの総数は 200 で、制限の 100 を超えているため、現在の制限が次のとおりであることがわかります。この時点でトリガーされます。

カウンタ アルゴリズムをもう一度おさらいすると、カウンタ アルゴリズムが実際にはスライディング ウィンドウ アルゴリズムであることがわかります。ただ、時間枠をさらに分割していないため、グリッドは 1 つだけです。

スライディング ウィンドウのグリッドをさらに分割すると、スライディング ウィンドウの回転がよりスムーズになり、電流制限の統計がより正確になることがわかります。

リーキー バケット アルゴリズム

リーキー バケット アルゴリズム。リーキー バケットとも呼ばれます。リーキー バケット アルゴリズムを理解するために、Wikipedia でアルゴリズムの概略図を見てみましょう:

図から、アルゴリズム全体が実際には次のようになっていることがわかります。とてもシンプルです。まず、水が入ってきて水が出ていく、固定容量のバケツがあります。流入する水については、どれくらいの水が流入するのか、どれくらいの速さで流入するのかを予測することはできません。しかし、流出する水については、このバケツで水の流出速度を固定することができます。また、バケツがいっぱいになると余分な水が溢れてしまいます。

アルゴリズム内の水を実際のアプリケーションのリクエストに置き換えると、リーキー バケット アルゴリズムが本質的にリクエストの速度を制限していることがわかります。リーキー バケット アルゴリズムを使用すると、インターフェイスがリクエストを一定の速度で処理することを保証できます。したがって、リーキーバケットアルゴリズムには本質的に重大性の問題はありません。具体的な疑似コードの実装は次のとおりです:

class LeakyDemo{
    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 水漏出的速度
    public  $water;// 当前水量(当前累积请求数)
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->water=max(0,$this->water-($now-$this->timeStamp)*$this->rate);// 先执行漏水，计算剩余水量
        $this->timeStamp=$now;
        if(($this->water+1)<$this->capacity){
            // 尝试加水,并且水还未满
            $this->water+=1;
            return true;
        }else{
            // 水满，拒绝加水
            return false;
        }
    }
}

トークン バケット アルゴリズム

令牌桶算法，又称token bucket。为了理解该算法，我们再来看一下维基百科上对该算法的示意图：

从图中我们可以看到，令牌桶算法比漏桶算法稍显复杂。首先，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。

具体的伪代码实现如下：

class TokenBucketDemo{
    private  $timeStamp;
    public  $capacity;// 桶的容量
    public  $rate; // 令牌放入的速度
    public  $tokens;// 当前令牌的数量
    public function __construct()
    {
        $this->timeStamp = time();
    }
    public  function grant(){
        $now=time();
        $this->tokens=min(0,$this->tokens+($now-$this->timeStamp)*$this->rate);// 先执行漏水，计算剩余水量
        $this->timeStamp=$now;
        if($this->tokens<1){
            // 若不到1个令牌,则拒绝
            return false;
        }else{
            // 还有令牌，领取令牌
            $this->tokens -= 1;
            return true;
        }
    }
}

临界问题

我们再来考虑一下临界问题的场景。在0:59秒的时候，由于桶内积满了100个token，所以这100个请求可以瞬间通过。但是由于token是以较低的 速率填充的，所以在1:00的时候，桶内的token数量不可能达到100个，那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问题。下图比较了计数器（左）和令牌桶算法（右）在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率，但是下一个突发速率必须要等桶内有足够的token后才能发生。

总结

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。

令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。

以上がPHPでAPIインターフェースのフローを制限する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。