ある期間でのあるWeb APIに対するアクセス回数上限を与えたときのスロットリングについて、一例ではあるがRack::Attack (v6.3.1)で採用されているしくみについて調べた。
ここでは、ある期間において特定のクライアントからのアクセスを一定回数以下に制限することをスロットリングと呼ぶことにする*1。あるAPIにスロットリングをかけるときは、ある期間において経過した時間を計算しながら、その期間中にあるクライアントからエンドポイントに来たアクセスの回数をサーバサイドのキャッシュに記録する必要がある。
結論
スロットリングしたい期間をperiod（単位は秒）とする。
「periodで与えられる期間だけ有効なカウンタ」を作ることができれば、そのカウンタにアクセス回数を記録することで、あるクライアントから上限を超える回数のアクセスが来ているかどうか検証できる。つまりスロットリングが実現できる。
カウンタの実現方法
特定期間において経過した時間を計算する
剰余を使ってタイマーを作ることで実現する。
まず、アクセスが来た時点でのUNIX時間t*2を取得する。このとき、tをperiodで割ったときの剰余rを計算すると、当然のことながら0 <= r < periodがつねに成り立つ。つまり、1秒ごとに数値が増え、period - 1の次は0に戻るようなタイマーができる。Rubyで書くと次のようになる。
r = t % period # 1秒ごとに増加するタイマー。値は0からperiod - 1を繰り返す
そして、periodからrの値を引くと、1秒ごとにperiodから数値が減り、1の次は値がperiodに戻るようなタイマーができる。
(period - r).to_i # 1秒ごとに減少するタイマー。値はperiodから1を繰り返す
アクセス回数の記録時に、このタイマーから得られる値ををキャッシュの有効期限として設定することで、その期間における残り時間を表現できる。
なお、Rack::Attackでは実装上の理由でタイマーの最大値に1秒のバッファを持たせている*3。
特定期間のアクセス回数を記録する
除算を使って、特定の期間だけ得られるキーを作り、そのキーを使ってキャッシュにアクセス回数を記録する。
先ほど取得したUNIX時間tをperiodで割ったときの商qを仮に毎秒計算してみると、剰余が0 <= r < periodになる連続した範囲ごとにqの値が同じになる。
q = (t / period).to_i # periodの期間中はつねに同じ値
つまり、ある期間の間はqの値が同じになるので、アクセス元の情報とqの組み合わせをその期間のクライアントからのアクセス回数のキーとすると、あるクライアンのある期間におけるアクセス回数データを一意に特定できる。このキャッシュの有効期限を、先ほど計算した有効期限として設定すればよい。
以上より、periodで与えられる期間だけ有効なカウンタを作ることができる。このカウンタを利用してスロットリングを実現する。
参考
- Rack::Attack 6.3.1
Rack::Attack::Throttlematched_by?から呼び出しているcache.countが「periodで与えられる期間だけ有効なカウンタ」での計数を実現している
Rack::Attack::Cachekey_and_expirtyで時刻に基づいて経過時間とキャッシュのキーを計算し、do_countでカウンタを操作している
