固定窓

一定時間ごとに数え直す

一番書きやすい方式が固定窓です。

1分ごとに区切って、その区間に来た回数を数えます。上限を超えたら断り、次の区間に入ったら0から数え直します。

# 時刻 ÷ 60 が同じなら同じ区間
# 59秒と60秒は別の区間になる

覚えておくのは区間ごとの数字1つだけなので、置き場所も要りません。

弱点が1つあります。区間の境目で2倍通ります。

境目で2倍通る

1分3回までとします。59秒に3回叩き、60秒にもう3回叩きます。

どちらの区間も3回ずつなので、全部通ります。ところが実際には2秒のあいだに6回通っています。

わざとやる相手はいます。上限を破る目的なら、境目を狙うのが一番簡単です。

わざとでなくても起きます。毎分0秒ちょうどに動く定時処理が複数あると、境目に自然と集まります。

弱点を知ったうえで選ぶなら固定窓でよく、許せないなら次回の方式にします。

それでも使われている

弱点があるのに、固定窓は実際によく使われます。

理由は持ち物の少なさです。覚えるのは区間ごとの数字1つだけで、通した時刻を並べて持つ必要がありません。

相手が100万人いても、数字が100万個あるだけです。次の区間に入れば全部捨てられます。

台が増えたときに効きます。

数字1つなら、台をまたいで足し合わせるのも簡単です。時刻の並びだと、全部の台から見える置き場所が要ります。

制限を入れるために新しい壊れ所を1つ足すことになるので、そこを避けられるのは大きな利点です。

演習

時刻つきの要求と上限・区間の長さから、通すか断るかを決めます。

1. その要求が属する区間は at ÷ window_seconds の整数部分
2. 同じ区間で通した回数が limit に達していたら "blocked"、まだなら "allowed" にして回数を1増やす
3. allowed と blocked には、それぞれの件数の合計を入れる