PostgreSQL で API のレートリミット超過を効率的に判定する（いもす法）

# なにしたの？(要約)

「過去24時間で〇件」というタイプのレートリミットがある外部API を実行予約して使いたいときに、いもす法を使ってレートリミットの超過判定をしました。

いもす法に必要な累積和は、以下のコマンドで計算しました

```sql
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時間後を以下のように表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/689b7f3a-088d-9d01-0bd8-238ee4603578.png" width=90%>

ここでは仮に「過去24時間で1件」のレートリミットとしましょう。
すると、次の期間はAPIを実行できません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/a54f0a4a-4790-89ea-2e00-bbb4ed99a53a.png" width=90%>

もしかしたらここで少し疑問に思う方もいるかもしれません。ですが、ゆっくり考えるとわかるかと思います。
図中の「APIを実行できない期間」のどこかで API を実行すると、レートリミットを超えてしまう期間が発生してしまいます。
以下のような場合ですね。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/098f1b53-a45e-60be-c130-7444627ed454.png" width=90%>

実行できるタイミングはあるけれど、そうすると未来に実行予約している API が実行されなくなってしまいます。

ではレートリミットの条件を「過去24時間で3件」に増やしてみましょう。
API の実行状況を先ほどと同じような図で表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1748702/bd083612-0059-20ab-3acb-d2335cb37ae2.png" width="90%">

上図の場合の「API を実行できない期間」が、なぜこの範囲になるかわかりましたでしょうか。この範囲は、API が 3件かさなる期間の [開始点から24時間前] ～ [終了点] になっています。この期間に API を実行すると、レートリミットにより他のどれかが実行できなくなってしまいます。

さて、API を実行できる期間を考えるときは、重なっている API の数をかぞえましたよね。この回数はどうやったら計算できるでしょうか。少し難しいかと思います。横軸が TIMESTAMP なのも、難しい要因になっています。

といっても、記事のタイトルからしていもす法ですね。いもす法を使うとこれらを効率的に計算できます。

背景がわかっていないと何をしているかわかりにくいので、長々と書いてしまいました。次はいよいよアルゴリズムの動き方です。

# いもす法での判定方法

続いて、いもす法をつかってどのようにレートリミットを判定するかを書きます。

といっても、いもす法がわかっていればそんなに難しくありません。
まず、実行したい API の実行時刻を `time` として、
`time - 24h` ~ `time + 24h` の期間に実行されたり予約されている API を取得します。
SQL で書きますが、このとき同時に、いもす法でつかう +1 も用意します。

```sql
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 を実行することができます。

# 実装

```sql
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 のほうの検索条件を変えるとさらに高速化できるのですが、対称性を意識してここでは書きませんでした。理解していればわかるはずで、逆に、理解せずに高速化をすると不具合のもとになるので、、、余裕があれば考えてみてください。