すぐに理解できます: 電流制限におけるリーキーバケットとトークンバケットアルゴリズム

[[346652]]

この記事は、陳建宇氏が執筆したWeChatパブリックアカウント「私の脳は揚げ魚です」から転載したものです。この記事を転載する場合は、Nao Nao Jin Jian Yu Leの公開アカウントまでご連絡ください。

序文

理論的には、外部または内部に機能を提供するすべてのリソース ポイントは、特定のトラフィック制御の対象となる必要があります。そうしないと、ビジネスの継続的な反復において、突然のトラフィックが発生する可能性があります (年初に一部の業界で突然の変化が起こり、ビジネス トラフィックが急増したのと同じように)。

バーストトラフィック

フロー制限がない場合、奇妙な問題が発生します。実際、システムはこのトラフィックの波に耐えられず、徐々に崩壊し、システム障害につながります。

現実のシナリオ

現実世界で最も一般的なシナリオは、日常生活のあらゆる場所で見られる電源タップとコンセントです。これらの内蔵ヒューズは電流ヒューズとも呼ばれ、主に過負荷保護の役割を果たします。電流が異常に一定の高さと温度まで上昇すると、ヒューズが溶けて電流を遮断し、回路の安全な動作を保護します。

そのため、現実の世界には、ソフトウェア エンジニアリングにおける電流制限や回路遮断に似たシナリオが多く存在し、これも量を制御して、量が制限を超えたときに遮断するものです。実際の人生で、他にも似たような例に遭遇したことがあるかどうか考えてみませんか?

[[346653]]

ヒューズ（インターネットからの画像）

漏れやすいバケツ

リーキー バケット アルゴリズムは、ネットワークのトラフィック シェーピングやレート制限によく使用されるアルゴリズムです。主な目的は、ネットワークにデータが注入されるレートを制御し、ネットワーク上のバースト トラフィックを平滑化することです。

リーキー バケット アルゴリズムは、アルゴリズムを通じてトラフィック アクセスを制御し、バースト トラフィックを比較的穏やかになるように整形およびデバリングして、ネットワークに安定したフローを提供します。

リーキー バケット アルゴリズムのストレージ バケットは、主に、バケットの容量、バケットから水が流出する速度、およびバケットの初期の満杯度という 3 つのパラメーターによって定義されます。

中心となる概念は、まさにその名の通り、「漏れやすいバケツ」です。

geeksforgeeksからの画像

バースティフロー

上の図では、タップはバーストフローを表しています。ネットワーク内に規制のないバースト トラフィックが存在する場合、バースト データに似たシナリオが発生します。ホストは 2 秒間に 12 Mbps の速度でデータを送信し、合計 24 Mbit のデータになります。次に、ホストは 5 秒間送信を停止し、その後 3 秒間 2 Mbps でデータを送信し、最終的に合計 6 Mbit のデータを送信します。

したがって、ホストは 10 秒間に合計 30 Mbit のデータを送信します。しかし、ここで問題があります。それは、データの転送がスムーズではなく、大きなピークがあるということです。すべてのトラフィックがこのように送信されると、一部は干ばつで死に、一部は洪水で死に、これはシステムにとって特に好ましいことではありません。

固定フロー

Bursty Flow シーンの問題を解決します。流出速度と容量が固定された、漏れやすいバケツが登場しました。

上の図では、リーキー バケットはトラフィックをスムーズにするために、同じ 10 秒間 3 Mbps でデータを送信し続けます。水（流れ）が速すぎるのに、水の流れ（漏水）が十分速くない場合、最終的には水が直接あふれてしまうことになり、要求の拒否/順番待ちのように見えます。また、バケツが空の場合、バケツの容量制限に達する水を一気に注ぎ込む可能性があり、このときにもピークが発生することがあります。

簡単に言えば、水漏れするバケツのようなものです。水は流れ込みますが、バケツから流れ出る水量は決まっています。容量がいっぱいであれば水は排出されますが、そうでなければ流れは流れ続けます。

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

トークン バケット アルゴリズムは、ネットワーク内のトラフィック シェーピングやレート制限によく使用されるアルゴリズムでもあります。その主な目的は、ネットワークに送信されるデータの量を制御し、バースト データの送信を可能にすることです。

トークン バケット アルゴリズムは、一定の割合でトークンをバケットに入れます。新しいリクエストが到着して処理する必要がある場合、処理を続行する前に、まずバケットから使用可能なトークンを取得する必要があります。バケット内に利用可能なトークンがない場合、リクエストは拒否され、キュー内で待機されます。

画像はgateoverflowより

1. トークンは 1/r 秒ごとにバケットに追加されます。
2. バケットには最大 b 個のトークンを保持できます。バケットがいっぱいの場合、新しく追加されたトークンは破棄されます (つまり、新しいトークンは必要ありません)。
3. ホストが n バイトのパケットを送信する場合、バケット内に n 個のトークンがあれば、必要なトークンが取得され、n バイトが正常に送信されます。
4. 使用可能なトークンが n バイト未満の場合、バケットからトークンは取得されず、要求は拒否/キューに入れられます。

リーキーバケットとトークンバケット

リーキー バケット アルゴリズムとトークン バケット アルゴリズムは、本質的には、大量のトラフィックによってシステムがクラッシュするのを防ぐためのトラフィック シェーピングまたはレート制限を目的としていますが、この 2 つのアルゴリズムの主な違いは、フロー制限の方向が逆であることです。

トークン バケットは、トラフィックの平均流入速度を制限し、ある程度の突発的なトラフィックを許可します。最大速度は、バケットの容量とトークンが生成される速度です。リーキーバケットは、比較的固定されているトラフィックの流出率を制限します。

したがって、これも問題を引き起こします。いくつかのシナリオでは、リーキー バケットの漏洩率は比較的固定されているため、リーキー バケット アルゴリズムはネットワーク リソースを効果的に使用できません。したがって、ネットワークの状態が比較的良好で、混雑がない場合、リーキー バケットは依然として制限されており、量を増やす方法はありません。トークン バケット アルゴリズムは異なります。平均レートを制限しながら、ある程度のバースト トラフィックをサポートできます。

要約する

ソフトウェア システムでは、電流制限はトラフィック シェーピングとレート制限を指すことが多く、これは非常に一般的な制御方法です。一般的には、初期段階では、統一されたフレームワーク、ゲートウェイ、メッシュに統合されます。したがって、ビジネスに携わる学生は、その後の迅速な使用/アクセスを容易にするために、この点を考慮することをお勧めします。結局のところ、ビジネス トラフィックのバーストは常に突然発生し、悪意のある攻撃である可能性もあります。

この記事で言及されているリーキー バケットとトークン バケットは、どちらも非常に一般的な方法ですが、個別に分析されています。しかし、ソフトウェア開発の観点から見ると、この 2 つを統合してそれぞれの利点を組み合わせることができると思いますか?