【GCP】Cloud Tasksのトークンバケットアルゴリズムについてまとめた

はじめに

Cloud Tasksのキューでは、「最大ディスパッチ数」や「最大同時ディスパッチ数」、「バッチサイズ」などを設定します。
公式ドキュメントを確認すると、キュー処理ではトークンバケットアルゴリズムを使用していて、そのための設定値とのことでした。
トークンバケットアルゴリズムがよく分かっていなかったので、今回は調べたことをまとめています。

トークンバケット

トークンバケットとは、バースト性のあるリクエストも一定量以下で流れるよう調整するアルゴリズムです。
Cloud Tasksのキュー処理や AWSのAPI Gatewayでも使われています。

詳細なアルゴリズムに関してはwiki等を参照していただければです。
https://ja.wikipedia.org/wiki/トークンバケット

ここではキュー処理を例にトークンバケットの概要図を示します。

• バケット
  トークンを保持するコンテナ
• バケットサイズ
  トークンを保持できる数
• トークン
  リクエストの度に消費されるもの
• レート
  トークンを補充するスピード

流れとしては下記になります。

• キューの処理をする際にトークンを1つ消費する
• トークンが存在する限り、キューの処理をする
• トークンが存在しない場合は、キューの処理は待たされる
• トークンは一定時間毎、補充される

バケットサイズが大きければ一度に多く処理ができ、レートが大きければ待ちが少なくなります。
これからも分かるようにバケットサイズとレートの調整をすることで、リクエスト数が急激に増加しても一定量の処理を流すことが可能です。

Cloud Tasksの設定項目

Cloud Tasksでは同じ意味の単語が複数あり、少し混乱しました。
queue.yamlで設定する場合とAPIで設定する場合で異なるようです。
queue.yamlのリファレンス
APIのリファレンス

処理速度の定義はこちらの公式ドキュメントに記載があります。
https://cloud.google.com/tasks/docs/configuring-queues?hl=ja#tokens

バケットサイズ

トークンを保持できる数のことです。
queue.yamlではbucket_size、APIではmax_burst_sizeと定義されています。

こちらの公式ドキュメントにあるのですが推奨値は処理レートを 5 で割った値になっています。

注意点としてはGCPのコンソールやAPIからは設定する場合はrateから自動的に(レート/5で)設定されますが、queue.yamlでキューを構築する場合はデフォルト値の5になります。
そのため、queue.yamlを使用する場合は明示的にbucket_sizeを指定する必要があります。

また、GCPのコンソールからはバケットサイズは修正できないようです。

レート(最大ディスパッチ数)

トークンを補充するスピードのことです。
queue.yamlではrate、APIではmax_dispatches_per_secondと定義されています。
GCPのコンソールでは最大ディスパッチ数と記載されています。

queue.yamlでは秒、分、時間、日の単位で設定できますが、最終的には秒毎になるようです。
60/m で作成した場合はコンソールでは次のような表示になっていました。

（しっかり動作確認できていませんが）1分毎に60個のトークンが補充されるのではなく、1秒毎に1個のトークンが補充される形になるようです。

最大同時ディスパッチ数

最大同時に実行できるタスク数のことです。
queue.yamlではmax_concurrent_requests、APIではmax_concurrent_dispatchesと定義されています。

こちらはトークンバケットアルゴリズムとは関係ない設定項目ですが、処理数の調整するためのものです。

イメージしづらいので、再度図を書きます。

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

• レートは実行中のタスクがあるか関係なく、トークンを補充
• トークンがあれば、タスクの処理を実施

するので、重いタスクを実行すると同時実行数が増えてしまいます。
Cloud Tasksでは、最大同時ディスパッチ数を設定することで実行中タスク数も考慮してくれるようになります。

例えば、最大同時ディスパッチ数を5に設定した場合、同時に実行できるタスクは5つになります。
トークンが存在していてもキューは待ちの状態になり、実行中のタスクの完了を待つ形になります。

おわりに

トークンバケットのアルゴリズムはシンプルだったので理解できました。
どちらかというとCloud Tasksでの用語の対応付けが分かりづらかったです。(レートと呼んだり、最大ディスパッチ数と呼んだり)

参考

• https://www.slideshare.net/AmazonWebServicesJapan/20190514-aws-black-belt-online-seminar-amazon-api-gateway-230113575
  AWSのAmazon API Gatewayの資料ですが、58ページ目にトークンバケットアルゴリズムの資料があります。
• https://addsict.hatenablog.com/entry/2018/09/24/125820
  こちらの記事がとても分かりやすかったです
• https://qiita.com/miyahara/items/31e5b8b4e7bc951ccf7e