如何应对突发流量：漏桶算法和令牌桶算法

API7.ai

January 5, 2023

OpenResty (NGINX + Lua)

以前の記事では、コードの最適化とキャッシュ設計について学びました。これらはアプリケーションの全体的なパフォーマンスに密接に関連しており、私たちの注意を払う価値があります。しかし、実際のビジネスシナリオでは、バーストトラフィックがパフォーマンスに与える影響も考慮する必要があります。ここでのバーストトラフィックは、ニュース速報やプロモーションなどからの通常のトラフィックである場合もあれば、DDoS攻撃などの異常なトラフィックである場合もあります。

OpenRestyは現在、主にWAF（Webアプリケーションファイアウォール）やAPIゲートウェイなどのWebアプリケーションのアクセス層として使用されています。これらは、前述の通常および異常なバーストトラフィックに対処しなければなりません。結局のところ、バーストトラフィックを処理できないと、バックエンドサービスが簡単にダウンし、ビジネスが適切に応答しなくなります。そこで今日は、バーストトラフィックに対処する方法を見ていきます。

トラフィック制御

トラフィック制御は、WAFやAPIゲートウェイにとって必須の機能です。これは、いくつかのアルゴリズムを通じて流入トラフィックを導き、制御することで、上流サービスが適切に機能することを保証し、システムの健全性を維持します。

バックエンドの処理能力は限られているため、コスト、ユーザーエクスペリエンス、システムの安定性など、複数の側面を考慮する必要があります。どのアルゴリズムを使用しても、正常なユーザーリクエストが遅くなったり、拒否されたりする可能性があり、ユーザーエクスペリエンスの一部を犠牲にすることになります。したがって、ビジネスの安定性とユーザーエクスペリエンスのバランスを取りながら、トラフィックを制御する必要があります。

実際、現実の世界には多くの「トラフィック制御」の事例があります。例えば、中国の春節の帰省ラッシュでは、地下鉄駅、鉄道駅、空港などの交通ハブに人々が殺到します。これらの交通手段の処理能力は限られているため、乗客は列に並び、バッチごとに駅に入る必要があります。これにより、乗客の安全と交通の正常な運営が確保されます。

これは乗客のエクスペリエンスに影響を与えますが、全体としてシステムの効率的で安全な運営を確保します。例えば、列に並ばず、バッチごとに入場させず、代わりに一斉に入場させた場合、システム全体がダウンする結果になるでしょう。

技術に戻ると、例えば、上流サービスが1分間に10,000リクエストを処理するように設計されていると仮定します。ピーク時にエントリーポイントでフロー制御がない場合、タスクのスタックが1分間に20,000に達すると、この上流サービスの処理性能は1分間に5,000リクエストに低下し、さらに悪化し、最終的にはサービスが利用できなくなる可能性があります。これは私たちが望む結果ではありません。

このようなバーストトラフィックに対処するために使用される一般的なトラフィック制御アルゴリズムは、リーキーバケットアルゴリズムとトークンバケットアルゴリズムです。

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

まず、リーキーバケットアルゴリズムを見てみましょう。これは、一定のリクエストレートを維持し、バーストトラフィックを平滑化することを目的としています。しかし、どのように実現されるのでしょうか？まず、リーキーバケットアルゴリズムのWikipediaの紹介から以下の概念的な抽象化を見てみましょう。

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

クライアントのトラフィックを、時には速く、時には遅い不確実な流量の水道管から流れる水と想像することができます。外部のトラフィック処理モジュール、つまり水を受け取るバケツには、底に穴が開いています。これがリーキーバケットアルゴリズムの名前の由来で、以下の利点があります。

第一に、バケツに流れ込む水が細流であろうと洪水であろうと、バケツから流れ出る水の速度は一定であることが保証されます。この安定したトラフィックは上流サービスにとって友好的であり、これがトラフィックシェーピングの目的です。

第二に、バケツ自体には一定の容量があり、ある程度の水を蓄積することができます。これは、クライアントリクエストがすぐに処理できない場合にキューに入れることができることを意味します。

第三に、バケツの容量を超える水はバケツに受け入れられず、流れ去ります。ここでの対応する比喩は、クライアントリクエストがキュー長を超える場合、クライアントに直接失敗メッセージを返すことです。この時点で、サーバー側はそれほど多くのリクエストを処理できず、キューイングは不要になります。

では、このアルゴリズムはどのように実装すべきでしょうか？OpenRestyに付属するresty.limit.reqライブラリを例に取りましょう。これはリーキーバケットアルゴリズムで実装されたレートリミットモジュールです。次の記事でこれについてさらに紹介します。今日は、以下のコード行を簡単に見てみましょう。これらがキーとなる部分です。

local elapsed = now - tonumber(rec.last)
excess = max(tonumber(rec.excess) - rate * abs(elapsed) / 1000 + 1000,0)
if excess > self.burst then
    return nil, "rejected"
end
-- return the delay in seconds, as well as excess
return excess / rate, excess / 1000

これらのコード行を簡単に読んでみましょう。elapsedは現在と最後のリクエストの間のミリ秒数で、rateは1秒あたりに設定したレートです。rateの最小単位は0.001秒/リクエストであるため、上記のコードを実装するには1000を掛けて計算する必要があります。

excessはキューに残っているリクエストの数を示し、0はバケツが空で、キューにリクエストがないことを意味します。burstはバケツ全体の容量を指します。excessがburstより大きい場合、バケツがいっぱいになり、流入するトラフィックは直接破棄されます。excessが0より大きくburstより小さい場合、キューに入って処理を待ち、ここで返されるexcess/rateは待機時間です。

このように、burstのサイズを調整することで、バーストトラフィックのキューの長さを制御できますが、バックエンドサービスの処理能力は変わりません。ただし、もちろん、ビジネスシナリオによって、ユーザーにリクエストが多すぎるため後で再試行するように伝えるか、ユーザーに長い時間待たせるかは異なります。

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

トークンバケットアルゴリズムとリーキーバケットアルゴリズムは、バックエンドサービスがバーストトラフィックに打ち負かされないようにするという同じ目的を持っていますが、両者の実装方法は異なります。

リーキーバケットアルゴリズムは、エンドポイントIPを使用してトラフィックとレート制限の基礎を行います。このようにして、各クライアントのリーキーバケットアルゴリズムの出口レートは固定されます。しかし、これには問題があります。

ユーザーAのリクエストが頻繁で、他のユーザーのリクエストがまれである場合、リーキーバケットアルゴリズムはAのリクエストの一部を遅くしたり拒否したりします。その時点でサービスがそれらを処理できる場合でも、全体のサービス圧力がそれほど高くない場合でもです。

ここでトークンバケットが役立ちます。

リーキーバケットアルゴリズムがトラフィックを平滑化することに焦点を当てているのに対し、トークンバケットはバーストトラフィックをバックエンドサービスに通過させることができます。トークンバケットの原理は、一定のレートでトークンをバケツに入れ、バケツがいっぱいでない限りトークンを入れ続けることです。このようにして、エンドポイントからのすべてのリクエストは、バックエンドが処理する前にトークンバケットからトークンを取得する必要があります。バケツ内にトークンがない場合、リクエストは拒否されます。

ただし、OpenRestyはそのライブラリでトークンバケットを使用してトラフィックとレートを制限することを実装していません。したがって、ここではUPYUNがオープンソース化したトークンバケットベースのレート制限モジュールlua-resty-limit-rateを簡単に紹介します。

local limit_rate = require "resty.limit.rate"

-- global 20r/s 6000r/5m
local lim_global = limit_rate.new("my_limit_rate_store", 100, 6000, 2)

-- single 2r/s 600r/5m
local lim_single = limit_rate.new("my_limit_rate_store", 500, 600, 1)

local t0, err = lim_global:take_available("__global__", 1)
local t1, err = lim_single:take_available(ngx.var.arg_userid, 1)

if t0 == 1 then
    return -- global bucket is not hungry
else
    if t1 == 1 then
        return -- single bucket is not hungry
    else
        return ngx.exit(503)
    end
end

このコードでは、グローバルトークンバケットとngx.var.arg_useridをkeyとするトークンバケットの2つのトークンバケットを設定しています。これら2つのトークンバケットの組み合わせには、以下の主な利点があります。

  • グローバルトークンバケットにまだトークンがある場合、ユーザーのトークンバケットを決定する必要がなく、バックエンドサービスが正常に動作できる限り、ユーザーからのバーストリクエストを可能な限り多く処理できます。
  • グローバルトークンバケットがない場合、リクエストを無差別に拒否することはできないため、個々のユーザーのトークンバケットを決定し、バーストリクエストが多いユーザーのリクエストを拒否する必要があります。これにより、他のユーザーのリクエストが影響を受けないようにします。

明らかに、トークンバケットはリーキーバケットよりも柔軟性があり、バーストトラフィックをバックエンドサービスに通過させることができます。ただし、もちろん、両者にはそれぞれ長所と短所があり、状況に応じて使用することを選択できます。

NGINXのレート制限モジュール

これら2つのアルゴリズムを理解したところで、最後にNGINXでレート制限を実装する方法を見てみましょう。NGINXでは、limit_reqモジュールが最も一般的に使用されるレート制限モジュールです。以下は簡単な設定です。

limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;

server {
    location /search/ {
        limit_req zone=one burst=5;
    }
}

このコードは、クライアントのIPアドレスをkeyとして、oneという名前の10Mのメモリ空間を要求し、レートを1秒あたり1リクエストに制限します。

サーバーのロケーションでは、oneのレート制限ルールも参照され、brustが5に設定されています。レートが1r/sを超える場合、同時に5リクエストをキューに入れることができ、一定のバッファ領域を提供します。brustが設定されていない場合、レートを超えるリクエストは直接拒否されます。

このNGINXモジュールはリーキーバケットに基づいているため、上記で説明したOpenRestyのresty.limit.reqと本質的に同じです。

まとめ

NGINXのレート制限の最大の問題は、動的に変更できないことです。結局のところ、設定ファイルを変更した後、それを有効にするために再起動する必要があります。これは急速に変化する環境では受け入れられません。したがって、次の記事では、OpenRestyでトラフィックとレート制限を動的に実装する方法を見ていきます。

最後に、WAFとAPIゲートウェイの観点から、通常のユーザーリクエストと悪意のあるリクエストを識別するためのより良い方法はあるでしょうか？通常のユーザーからのバーストトラフィックの場合、バックエンドサービスを迅速にスケールアップしてサービスの容量を増やすことができますが、悪意のあるリクエストの場合、アクセス層で直接拒否する方が良いでしょう。

この記事を同僚や友人に転送して、学びと進歩を共有してください。