おもしろwebサービス開発日記

Ruby や Rails を中心に、web技術について書いています

APIに利用制限をかけるとしたらどういうやりかたがあるのか

この記事はSmartHR Advent Calendar 2020 11日目の記事です。

僕のお手伝いしているSmartHRでは、毎週バックエンドエンジニアが集まり、技術的なトピックについて共有、相談しあうミーティングを開催しています。そのミーティングでは僕がTipsなどを共有するコーナーが常設されています*1。

このエントリでは、そのコーナーで共有した内容をひとつ紹介します。

APIに制限をかける方法について

APIを外部に提供するとき、一定の制限をかけてユーザがAPIを乱用するのを防ぐことはよくあることではないでしょうか。素直に考えると「1時間に5000回までAPIを実行できる」のようなやり方を思いつきますね。GitHubのAPIもそのやり方ですし、SmartHRのAPIも同様です。

じゃあそれでいいのでは。となるかもしれませんが少し待ってください。いろんなクライアントがAPIを大量に叩くことを想像してみてください。12:00、13:00、14:00 のような時間ごとにAPI回数をリセットすると仮定すると、例えば12:00~12:01の間に大量にアクセスが来てそれぞれのクライアントがリミットに達し、残りの59分間はほとんどリクエストが来ない、みたいなことになりそうです。そうすると1分間の爆発的なアクセスのためだけにサーバを増強しなければなりません。

もうちょっとアクセスが均等になるような制限が欲しいと思いませんか？そこでLeaky Bucketアルゴリズムの登場です。

Leaky Bucketアルゴリズムとは

名前の通りAPIの利用を「穴の空いているバケツに水を入れる」と考えます。

次のようなアルゴリズムです。

  • APIを利用するとバケツに水が入ります
  • これ以上水を入れるとバケツから水があふれる！というときはAPIを利用することはできません
  • バケツには穴が空いており、時間ごとに水が減っていきます

このような制限をかけることでクライアントに「ちょっとずつAPIを使う」ことを強いることができます。

ではこれをどうやって実装すると良いでしょうか。素朴に実装しようとすると、クライアントごとにバケツの水量を記録しておき、API利用時にそれを増加させ、一定時間ごとに減少させるような形になるでしょう。しかしそれだと「一定時間ごとに減少させる」のコストが高くなってしまいます。

例えば「1分毎に各クライアントの水を100減らす」という実装をしたとします。このときクライアントの数が多くなると、1分ではすべての処理が完了しないかもしれません。つまりこの実装はクライアントが多い場合は現実的ではありません。

同等のアルゴリズムで「一定時間ごとに減少させる」を不要にしたのがGCRA(Generic Cell Rate Algorithm)です

GCRA

GCRAは計算不要で自動的に増える値である「現在時間」を使って、時間を計算することでAPIの利用可否を判断します。

GCRAは水ではなくセルという名前をつかいますが、アルゴリズム的には同じです。他にもいくつか覚えないといけない用語があります。

用語名 内容
理論到着時間(TAT) Tごとにセルが到着すると仮定したときの到着時間 。APIが実行されるたびにTの分加算される。現在時刻が加算前のTATより大きい場合もしくは初回は現在時刻+TがTATになる
T セルが放出される間隔
τ バケットの時間的な最大容量(バケットの最大容量 * T)

この用語でアルゴリズムを説明すると、「TAT-τが現在時刻以下であればAPI利用可能」となります。

なるほどわからん

具体的な数値をいれないとよくわからないですよね。仮の数値を入れて考えてみましょう。

前提

  • バケットの最大容量2セル
  • 1分毎に1のセルが放出される
    • つまりτは2分となる
  • APIをそれぞれ12:00:00, 12:00:01, 12:00:02に実行した

12:00:00のAPI実行時

  • TATは12:01(現在時刻+T)
  • TAT - τが12:01 - 2分 = 11:59となり、現在時刻(12:00:00)より前なのでAPI実行可能

12:00:01のAPI実行時

  • TATは12:02
  • TAT - τが12:02 - 2分 = 12:00となり、現在時刻(12:00:01)より前なのでAPI実行可能

12:00:02のAPI実行時

  • TATは12:03
  • TAT - τが 12:03 - 2分 = 12:01となり、現在時刻(12:00:02)より後なのでAPI実行不可。実行するには12:01まで待つ必要がある

まだわからない

「なんかいい感じに均等にAPI利用制限できるアルゴリズムがあり、その名前はleakey bucket(もしくはGCRA)である」と覚えておいてください

使ってみたいけどイチから実装するのめんどくさいのでgemないですか

Sidekiq Enterpriseのv2.2から、GCRAのアルゴリズムで制限をかける機能が使えるようになっています。もともとSidekiq Enterpriseの機能として利用制限をかけるものはあったのですが、それにGCRA(leaky bucket)用のアルゴリズムが追加された形です。この機能はsidekiqのワーカ以外でも使うことができます。

次のようなコード(The Leaky Bucket rate limiter | Mike Perhamから引用)をRack Middlewareとして利用すると簡単にAPIサーバにleaky bucketな制限をかけることができます。

class LeakyLimiter
  def initialize(app)
    @app = app
  end

  def call(env)
    remote_ip = env["REMOTE_ADDR"].tr(':', '_')
    begin
      limiter = Sidekiq::Limiter.leaky("ip-#{remote_ip}", 10, 10, wait_timeout: 0)
      limiter.within_limit do
        @app.call(env)
      end
    rescue Sidekiq::Limiter::OverLimit => ex
      [429, {
        "Content-Type" => "text/plain",
        "X-Rate-Limited-For" => ex.limiter.next_drip.to_s,
      }, ["Rate limited"]]
    end
  end
end

もしこれから外部にAPIを公開していくぞ！となったときにこの話を思い出してみてください。

まとめ

だいたいこのような感じで毎週なにかしら共有をしています。自分も参加してみたい！という方はこちらのリンクからどうぞ。

*1:毎週ネタをひねり出すのに苦労しています＞＜