ユアマイスター株式会社エンジニアブログ

ユアマイスター株式会社のエンジニアが日々徒然。

PAYJP API の高負荷対策で出てきた「リーキーバケット(leaky bucketアルゴリズム)」について調べてみました。

どうも。ユアマイスター星(@inase17000)です。 どうやら世のエンジニアのQiita離れが少し進んできているようなので、技術的内容もこのブログに書いておこうかと。。。

先日、このようなアナウンスがありました。

payjp-announce.hatenablog.com

この中に登場する公式のPAY.JP API リファレンスで、以下のように言及されていました。

レートリミットは、leaky bucketアルゴリズム に従って実装されています。

恥ずかしながら、いままでこのリーキーバケットというものが何かを知らなかったので、ドキュメントにある例がなかなか頭に入ってきませんでした。こういうときは一度立ち止まって図にするなら自分の言葉にするなりアウトプット前提のインプットをすることで理解を進めたくなります。

ということで、簡単に調査した結果をまとめておこうと思います!

1. 定義

Wikipedia によると、下記のような概念のようです。

底に穴のあるバケツがあるとする。

バケツの容量は、そこに溜め込めるデータの量を示している。

バケツの大きさが b バイトだとすると、空の状態でb バイトまで溜め込めることを意味する。

空き容量より大きなパケットが到着した場合、捨てるかキューイングされる。空き容量より小さいパケットの場合はそのままバケツに入れる。

バケツの穴からは一定レートのデータ、例えば r バイト毎秒のデータが出て行く。

f:id:yourmystar_engineer:20200904224742p:plain
言葉の定義

2. サンプル

次にPay.JP APIリファレンスに記載のあったサンプルについて考えてみましょう。

各ゾーンに対するリクエストは一旦バケットに入り、入った順に流速の値に従って処理されていきます。

例) バケット10・流速1のゾーンに瞬間的に3リクエストが着信すると、1秒に1つずつ処理されていき、3秒後にすべてのリクエストが処理される。

これを図にすると、ちょうどこんな感じでしょう。

f:id:yourmystar_engineer:20200904224901p:plain
example1

流速を超えてリクエストを行うと、バケットの処理待ちリクエスト数が増加します。バケットの上限値を超えてしまう場合は、そのリクエストはエラーとなります。

例) バケット10・流速1のゾーンに瞬間的に12リクエストが着信すると、10番目まではバケットに入り、11,12番目のリクエストはエラーとなる。

これは定義のところにも記載のある、 空き容量より大きなパケットが到着した場合、捨てるかキューイングされる。 に該当するサンプルです。

例) バケット10・流速1のゾーンに、2リクエスト/秒の速度でリクエストを送り続けると、約10秒後にバケットがいっぱいになり、以降は半分程度がエラーとなる。

最後に応用編のサンプルはこんな感じになると思います。

f:id:yourmystar_engineer:20200904230820p:plain

t = 10 以降では1リクエストずつエラーになっていくのがよくわかりますね。

3. 今回のユアマイスター の対応

上記の理解をもとに、アプリケーションからのリクエストが多重に行われたときの毎秒あたりのリクエスト数を推算し、バケットから溢れ出るリクエストが存在する閾値を求めました。

また、Webの処理よりも、バッチ処理の場合のほうが同時刻でのリクエストを送信する可能性が高いため、あわせてバッチ処理のロジックを確認しました。

上記のサンプルを参考に、

  • バケット入りきらずエラーになってしまうものがないか。

  • 流速の処理を待ちきれずタイムアウトになりえるものがないか

を確認しました。いずれも問題ない状態でしたので、今回の仕様変更に対してアプリケーションの改修がいらないと判断しました。

以上、ちょっとした知識ではありますが、理解のために図示してみるだけで大幅に理解が進んだと感じます。

今後もこういったアウトプット前提のインプットを続けていきたいと思います!

ユアマイスター では一緒にはたらくエンジニアを募集しています。

▼お気軽にご連絡ください▼

https://corp.yourmystar.jp/recruit

お気軽にご連絡お待ちしてます!!