固定窓

一定時間ごとに数え直す

固定窓は、時計の決まった区切りで要求数を数える方式です。席の予約サービスで1分ごとに数えるなら、0秒以上60秒未満と、60秒以上120秒未満は別の区間です。

利用者ごとに、その区間で通した回数を持ちます。回数が上限に達したら断り、次の区間では0から数えます。通した時刻を1件ずつ並べて保存する必要はありません。

区間の境目には弱点があります。前の区間で上限まで使った直後でも、次の区間に入ればまた上限まで通せます。短い間に、上限の2倍が通ることがあります。

「時計の1分ごとに上限」と「直近のどの1分を取っても上限」は違う条件です。後者を守りたいときは、固定窓だけでは足りません。

少ない持ち物にも条件がある

固定窓で覚えるのは、利用者ごとの区間番号と回数です。古い区間の状態は期限を付けて消せるため、要求の時刻を全部持つ方式より保存量を抑えられます。

複数台で同じ利用者の要求を受けるなら、共有のカウンタが必要です。各台で別々に上限まで通すと、サービス全体では台数分の回数が通ってしまいます。

上限の確認と回数の加算も、ひとまとまりに行います。別々に行うと、同時に来た要求がどちらも残り枠を見つけ、上限を超えて通ることがあります。

予約サービスで解いてみる

DAU 3万人、1人1日6回なら平均は約2 QPSです。ピーク係数50で約100 QPS、1台が毎秒40件なら3台で毎秒120件を処理できます。

月5万円の予算内でこの構成を用意できたとしても、固定窓の境目で集中する要求は別に考えます。平均や通常のピークに収まることは、短い間の集中に耐える証拠にはなりません。

空席の問い合わせを、1人あたり1分6回までにする例を解きます。これは1日の利用回数とは別の設定です。この利用者は、それまで両区間を使っていないものとします。

まず区間ごとの回数を上限と比べます。そのあと、境目の短い時間に通った合計を求めます。

各区間は6件ずつなので、6＋6＝12件が全部通ります。59秒から61秒までの2秒間だけを見ると、1分の上限の2倍です。

境目を狙う相手に加え、決まった時刻に動く問い合わせでも集中は起きます。下流がこの12件を受けられないなら、区間ごとの回数だけを見て安心はできません。

無料の空席 API に回数の目安を設け、境目の集中を許せるなら固定窓は候補です。厳密に直近の時間内の回数を守るなら、窓をずらして数える方式を選びます。