なにしたの？(要約)
「過去24時間で〇件」というタイプのレートリミットがある外部API を実行予約して使いたいときに、いもす法を使ってレートリミットの超過判定をしました。
いもす法に必要な累積和は、以下のコマンドで計算しました
SUM (count) OVER (ORDER BY time) AS accumulate
実装はいちばん下にあります。
目次
前提条件
・PostgreSQL の文法を知っていること (WITH, UNION ALL, ウインドウ関数 などを使います)
・累積和や、いもす法について知っていること
いもす法についてはこちらなどがわかりやすいと思っています。
通常は配列でやるものなので、これらの記事も配列が使われています。注意です。
https://imoz.jp/algorithms/imos_method.html
https://note.com/kirimin_chan/n/n7663e3bb8a05
背景
外部API にはレートリミットが設定されているものが多いですね。
レートリミットにはいろいろなタイプがありますが、その中の一つに「過去24時間で〇件」というものがあります。
これだけでは大したことないと思うのですが、今回はアプリ側の機能で、日時を指定して API を実行する必要がありました。実行予約というやつです。
さらに、その判定を SQL でやる必要もありました。
これをするには少し工夫が必要です。というのも、実行予約があるので、未来に API の実行予定があります。もちろん、過去も見る必要があります。つまり、レートリミットを判定するには、「過去24時間」と「未来の24時間」を合計した48時間のうち、任意の24時間の範囲を抜き取ったときの API 実行回数を取得する必要がありますね。
...説明が難しく、判定にも工夫が必要です。
要するに「実行予約があるから未来も見なきゃいけない」ということです。
この記事では、その判定をいもす法を使ってやっています。
なぜいもす法？
なぜいもす法が出てくるのでしょうか。
この背景をわかっていないと、実装だけ見てもわかりにくいかと思います。
ひとまず、どうしたら「過去24時間で〇件」の判定をできるか考えてみましょう。 API の実行時間とその24時間後を以下のように表します。
ここでは仮に「過去24時間で1件」のレートリミットとしましょう。
すると、次の期間はAPIを実行できません。
もしかしたらここで少し疑問に思う方もいるかもしれません。ですが、ゆっくり考えるとわかるかと思います。
図中の「APIを実行できない期間」のどこかで API を実行すると、レートリミットを超えてしまう期間が発生してしまいます。
以下のような場合ですね。
実行できるタイミングはあるけれど、そうすると未来に実行予約している API が実行されなくなってしまいます。
ではレートリミットの条件を「過去24時間で3件」に増やしてみましょう。
API の実行状況を先ほどと同じような図で表します。
上図の場合の「API を実行できない期間」が、なぜこの範囲になるかわかりましたでしょうか。この範囲は、API が 3件かさなる期間の [開始点から24時間前] ～ [終了点] になっています。この期間に API を実行すると、レートリミットにより他のどれかが実行できなくなってしまいます。
さて、API を実行できる期間を考えるときは、重なっている API の数をかぞえましたよね。この回数はどうやったら計算できるでしょうか。少し難しいかと思います。横軸が TIMESTAMP なのも、難しい要因になっています。
といっても、記事のタイトルからしていもす法ですね。いもす法を使うとこれらを効率的に計算できます。
背景がわかっていないと何をしているかわかりにくいので、長々と書いてしまいました。次はいよいよアルゴリズムの動き方です。
いもす法での判定方法
続いて、いもす法をつかってどのようにレートリミットを判定するかを書きます。
といっても、いもす法がわかっていればそんなに難しくありません。
まず、実行したい API の実行時刻を time として、
time - 24h ~ time + 24h の期間に実行されたり予約されている API を取得します。
SQL で書きますが、このとき同時に、いもす法でつかう +1 も用意します。
SELECT
api_call_at
,1
FROM
api_table
WHERE
api_call_at >= time - '1 day'::INTERVAL AND
api_call_at < time + '1 day'::INTERVAL
;
上のように、取得した API について、API の実行時間を +1、実行時間の24h後を -1 とします。
次に累積和を計算します。ここはまさにいもす法ですね。
すると、出てくる値が各時間での API の実行回数になります。この値は、上のほうの図で言う、「重なっている件数」のことです。あとは、累積和のなかの最大値がレートリミットよりも小さければ、 time の時刻に API を実行することができます。
実装
WITH api_table AS (
SELECT
api_call_at - '1 day'::INTERVAL AS api_call_at
,1 AS count
FROM
api_table
WHERE
api_call_at >= time - '1 day'::INTERVAL AND
api_call_at < time + '1 day'::INTERVAL
UNION ALL
SELECT
api_call_at + '1 day'::INTERVAL AS api_call_at
,-1 AS count
FROM
api_table
WHERE
api_call_at >= time - '1 day'::INTERVAL AND
api_call_at < time + '1 day'::INTERVAL
)
SELECT
MAX(imos.accumulate)
FROM (
SELECT
SUM (api_table.count) OVER (ORDER BY api_table.api_call_at) AS accumulate
FROM
api_table
) AS imos
;
大まかに説明すると、 +1 と -1 とで同じ条件でテーブルを検索した後に UNION ALL でつなげています。そのあと、 OVER と SUM で累積和を計算して MAX で最大値を取得しています。もしレートリミットを超過したかどうかを boolean で返したい場合は、最後に比較演算をしてください。
少し複雑ですが、このようにすればいもす法を実装できました。
-1 のほうの検索条件を変えるとさらに高速化できるのですが、対称性を意識してここでは書きませんでした。理解していればわかるはずで、逆に、理解せずに高速化をすると不具合のもとになるので、、、余裕があれば考えてみてください。