はじめに
Amazon EventBridgeでは、AWS内のサービスにイベントを送信できる。API Destinationを使うと、AWS外のサービスにもイベントの送信が可能であり、様々なサービス間の連携や疎結合なアプリケーションの作成に一役買っている。EventBridgeは世界中で使われており、数千万から数億もの膨大な数のイベントを管理していると考えられる。そんな膨大な数のイベントをどのように管理し、しかも非常に安価で提供しているのだろうか。EventBridgeは定められた時刻でのイベント送信と、いつ発生するか分からないイベントによって駆動されるイベント送信があるが、今回は定められた時刻でのイベント送信だけを題材とし、アルゴリズムについて考察する。恐らくEventBridgeでも使われているであろう、階層タイミングホイールというアルゴリズムについて説明する。
素朴な実装
真っ先に思いつく実装としては、全探索だろう。これを方法1とする。方法1では、EventBridgeが1分ごとにイベントを送信しているとすると、すべてのイベントを1分ごとに全探索し、その時刻に送信すべきイベントを見つけてきてイベントを送信すれば良い。続いて思いつく実装としては、12:00に送信するイベント、12:01に送信するイベント、12:02に送信するイベント、…というように1分ごとに送信するべきイベントのリストを予め作っておくことである。これを方法2とする。
しかし、方法1も方法2も計算量の点で問題がある。
方法1では、下図に示すように1億件程度なら1分ごとに全探索しても良いように思える。競技プログラミング経験者からすると、10^8くらいなら1秒以内に計算できるという感覚があるだろう。しかし、探索したイベントのほとんどはその時刻に送信しないイベントである。Copilotに試算してもらったところ、毎分のイベント送信は1-3%程度なので、全探索しても96%程度はその時刻に送信しないイベントであり、全探索は無駄である。この数値がどの程度信用できるかは不明だが、毎時送信のイベントや毎日送信のイベントが多いほど、全探索は無駄が多いということになる。さらに、その規模の計算を常時回し続けていると、計算リソースも必要となり、EventBridgeの安価な料金設定は実現できない。大赤字となってしまう。
方法2についても、同様である。方法2では、1分ごとにその時刻に送信する予定のリストを参照すれば良い。しかし、そのリストを作る際に全探索で1億の計算を回す必要があり、しかもリストは1分ごとに1つ消費されるので1分ごとに1つ新しいリストを作る必要があるため、結局1分ごとに1億の計算を回す必要があるのだ。これでは方法1と同じである。むしろリストを作っているだけメモリを多く使ってしまって無駄である。
ではどうするか、2つ目で紹介した実装方法を少し改良すれば良い。実装方法を次の章で紹介する。
階層タイミングホイール
このような状況で使えるのが、階層タイミングホイール（Hierarchical Timing Wheel）という実装方法である。この方法では、先ほど述べたような12:00に送信するイベントのリスト、12:01に送信するイベントのリスト、12:02に送信するイベントのリスト、…を作成する。しかし、現在時刻から遠い時刻に送信する予定のイベントは1分刻みではなくもっと粗い刻み方でリストを作るのである。たとえば13時台に送信するイベントのリスト、14時台に送信するイベントのリスト、…といったようにである。13時が近づくと、13時台に送信するイベントのリストを参照し、13:00に送信するイベントのリスト、13:01に送信するイベントのリスト、…というように細かい区切りに分ける。このやり方により、すべてのイベントのリストにアクセスする回数が減り、計算量が大幅に縮小できる。
方法2と階層タイミングホイールの計算量を比較してみたが、720倍くらい違う。
なお、これは推測であり、実際にEventBridgeでこのアルゴリズムが使われているかは不明である。しかし、階層タイミングホイールは大量のタイマーイベントを送信する際によく使われるアルゴリズムであり、EventBridgeといえば大量のタイマーイベントを送信するサービスの最たるものであるので、このアルゴリズムが使われている可能性は高い。
まとめ
• Amazon EventBridgeでは、世界中のユーザが設定したイベントの送信を行う。どうやって世界中にある大量のイベントを管理するか推測してみた。
• 愚直な方法として
• 方法1：全イベントを毎分全探索し、時刻と一致するイベントを送信。
• 方法2：予め時刻ごとのイベントのリストを作っておく。
が考えられるが、どちらも計算量の観点で優れていない。
• 階層タイミングホイールという方法で、大幅に計算量を縮小させることができた。実行時刻が現在時刻と近い場合は細かい時間幅で管理し、遠い場合は粗い時間幅で管理する方法である。
• 公式に名言されているわけではないが、おそらくこの方法がEventBridgeでも用いられている。