ValkeyとSliding Window Logを利用したレートリミットの実装

この記事は、enechain Advent Calendar 2025の23日目の記事です。

はじめに

こんにちは、enechainのApplication Platform Deskでエンジニアをしているchocoです。

APIの設計を行う際、レートリミットが必要になる事があると思います。そして、その実装方法として様々なパターンが存在します。
今回、Sliding Window Logを利用したレートリミットを実装する機会があったので、その技術選定の経緯や実装内容を共有したいと思います。実装例は記事用に実際のものから一部変更していますが、ご参考になれば幸いです。
なお、我々のチームではMemoryStoreとしてValkeyを利用しており、アルゴリズムの実装にはSorted Setを利用しました。 アプリケーションコードは、Go言語で実装しています。

レートリミットアルゴリズム比較

レートリミットアルゴリズムはいくつかあり、一般的なものだとトークンバケットなどがあります。
トークンバケットは、一定間隔でトークンを追加し、リクエストが来た際にトークンを消費することでレートリミットを実現します。リクエストを均等に分散させるのに適しています。
今回実装するレートリミットでは、ある期間内のリクエストをカウントし、上限を超えた場合にリクエストを拒否する必要がありました。リクエストを均等に分散させることではなく、ある期間内のリクエスト数を厳密に制限するために、Window系のアルゴリズムを検討しました。
また、時間の幅を表現しやすいという点でも、Window系のアルゴリズムを選択しました。

Sliding Window Logを理解するには、Fixed Window Logとの違いを理解すると分かりやすいです。 まずは、Fixed Window Logから説明します。

Fixed Window Log

Fixed Window Logは、一定の時間枠（ウィンドウ）ごとにリクエスト数をカウントし、その枠内でのリクエスト数が設定された上限を超えた場合にリクエストを拒否する方法です。
例えば、1分間に100回のリクエストを許可する場合、1分ごとにリクエスト数をリセットし、再度100回を超えた場合に拒否します。ウィンドウが切り替わるタイミングで、再度上限までリクエストが可能になります。

Sliding Window Log

Sliding Window Logは、リクエストのタイムスタンプを記録し、そのタイムスタンプに基づいてリクエスト数をカウントします。
時間枠が可変的で常に現在の時刻から一定期間前までのリクエスト数をカウントします。
ウィンドウの切り替えのタイミングでバーストを発生させることがなく、より均等にリクエストを分散させることができます。

例: Limit=3, Window=1sec

記録されたタイムスタンプ:
  - リクエストA ← カウント(時間経過でウィンドウ外へ)
  - リクエストB ← カウント
  - リクエストC ← カウント

リクエストD: Aがウィンドウの外へ -> カウントが3になるため許可
次のリクエストE: ウィンドウ内がいっぱいなので拒否

特徴	Fixed Window Log	Sliding Window Log
実装	簡単	やや複雑。メモリの消費が大きい
リクエストの分布	ウィンドウが開くたびにリクエストが集中する可能性がある	リクエストが均等に分布するため、より厳密なレートリミットが可能

今回のレートリミットを適用するAPIは、厳密にリクエスト数を制限したく、時間の切れ目でリミット上限までリトライ可能なFixed Window Logではなく、Sliding Window Logを採用しました。
Sliding Window Logはタイムスタンプをメモリに保持するため、メモリ消費が大きい点がデメリットですが、TTLを超えたキーは削除可能なことや、エントリーはそれほど大きくならないことから許容範囲内だと判断しました。

Sorted Set

Sliding Window Logの実装を行う上で便利なSorted Setというデータ構造についても紹介します。

Sorted Setとは

Sorted Setは、各メンバーにスコアが関連付けられたデータ構造です。 RedisのSorted Setと同様に、ValkeyのSorted Setもメンバーをスコアに基づいてソートが可能です。

rate_limit:user_123
  ├── req_a1b2c3d4 : 1734500000000000000 // メンバー : スコア
  ├── req_e5f6g7h8 : 1734500060000000000
  └── req_i9j0k1l2 : 1734500120000000000

Sliding Window Log と Sorted Set

Sliding Window Logでは、各リクエストのタイムスタンプを記録し、そのタイムスタンプに基づいてリクエスト数をカウントします。
またウィンドウ外のエントリーを削除する必要があります。 ValkeyのSorted Setを利用して、各リクエストのタイムスタンプをスコアとして格納し、特定の時間範囲内のリクエストを簡単に扱うことができます。
過去のエントリーを削除する際も、Sorted Setの範囲削除を利用することで、効率的に古いエントリーを削除できます。

実装例

ValkeyのSorted Setを利用したSliding Window Logのレートリミット実装例です。
Goでは valkey-go を使用します。
実装例では、ログインチャレンジのようなレスポンスの成否が重要なAPIを想定します。

インターフェース

以下のようなインターフェースを定義します。

type Limiter interface {
    Check(ctx context.Context, key string, limit int, window time.Duration, now time.Time) error
    Record(ctx context.Context, key string, limit int, window time.Duration, now time.Time) error
    Clear(ctx context.Context, key string) error
}

Record

Sliding Window Logのアルゴリズムを実装するメインの関数です。
ウィンドウ外の古いエントリーを削除しつつ新しい試行を記録し、リミットを超えている場合はエラーを返します。
スコアにタイムスタンプを入れます。 今回はスコアがあればいいので、メンバーには適当なUUIDを割り当てています。

func (c *valkeyClient) Record(ctx context.Context, key string, limit int, window time.Duration, now time.Time) error {
    windowStart := strconv.FormatFloat(float64(now.Add(-window).UnixNano()), 'f', 0, 64)
    nowUnix := float64(now.UnixNano())

    results := c.client.DoMulti(ctx,
        c.client.B().Zremrangebyscore().Key(key).Min("-inf").Max(windowStart).Build(),
        c.client.B().Zadd().Key(key).ScoreMember().ScoreMember(nowUnix, uuid.NewString()).Build(),
        c.client.B().Zcard().Key(key).Build(),
        c.client.B().Expire().Key(key).Seconds(int64(window.Seconds())).Build(),
    )

    for _, res := range results {
        if err := res.Error(); err != nil {
            return err
        }
    }

    count, err := results[2].AsInt64()
    if err != nil {
        return err
    }

    if count > int64(limit) {
        return ErrRateLimitExceeded
    }

    return nil
}

コマンド	説明
Zremrangebyscore()	ウィンドウ外のエントリーを削除
Zadd()	新しいエントリーを追加
Zcard()	ウィンドウ内のエントリー数をカウント
Expire()	TTL

Check

ウィンドウ内のカウントを確認し、リミットを超えている場合はエラーを返します。
記録は行わず、チェックのみを行います。

func (c *valkeyClient) Check(ctx context.Context, key string, limit int, window time.Duration, now time.Time) error {
    windowStart := strconv.FormatFloat(float64(now.Add(-window).UnixNano()), 'f', 0, 64)

    count, err := c.client.Do(ctx,
        c.client.B().Zcount().Key(key).Min("(" + windowStart).Max("+inf").Build(),
    ).AsInt64()
    if err != nil {
        return err
    }

    if count >= int64(limit) {
        return ErrRateLimitExceeded
    }

    return nil
}

Minに(プレフィックスを付けることで、windowStartを含まない（exclusive）範囲を指定しています。
これにより、RecordのZREMRANGEBYSCORE（windowStart以下を削除）と一貫した動作になります。

Clear

リミットを超えてこない正常のリクエストの場合は、キーを削除できるようにしておきます。
クリアしたいキーは、一意に決まっていないとValkeyのパフォーマンスが悪化するので、キーの生成に必要な情報を逐一取れない場合は、RDB等で管理すると良いです。

func (c *valkeyClient) Clear(ctx context.Context, key string) error {
    return c.client.Do(ctx, c.client.B().Del().Key(key).Build()).Error()
}

Limiterの利用例

今回の実装では、厳密な処理のカウントは求めず、アトミック性はない設計になっています。
ただし、最後にCheck()を呼び出して並列リクエストに対応しておきます。doSomething()の間にもRecord()でログが溜まっていくので、並列リクエストもウィンドウに収めてCheck()で処理することができます。

limiter := NewRateLimiter(client)
now := time.Now()

// check early if already exceeded
if err := limiter.Check(ctx, userKey, limit, time.Hour, now); err != nil {
    return err
}

if err := limiter.Record(ctx, userKey, limit, time.Hour, now); err != nil {
    return err
}

result, err := doSomething()

if err := limiter.Check(ctx, userKey, limit, time.Hour, now); err != nil {
    return err
}

if err == nil {
    limiter.Clear(ctx, userKey)
}

おわりに

この記事では、ValkeyのSorted Setを利用したSliding Window Logのレートリミット実装について紹介しました。
今回は、レスポンスの成否に焦点を当てた実装例を示しましたが、より厳密に回数を制限したい場合には、Luaを利用してトランザクション化することも考えられます。
また、Sliding Window Log以外のレートリミットアルゴリズムもありますので、別途用途に合わせて実装してみたいと思います。

参考

• Valkey Sorted Sets
• Rate Limiting in System Design

---

enechainでは、事業拡大のために共に挑戦する仲間を募集しています。興味がある方はぜひお声がけください！