レートリミット¶

概要¶

レートリミットは、任意の処理に対して実行回数の制限を適用します。レートリミットが利用される典型的な例は、APIのリクエスト数の制御です。 APIのレートリミットとして最も一般的に用いられるのはTokenBucketアルゴリズムによるレートリミットです。

レートリミットはztime/zrateパッケージにより提供されています。

機能¶

1. LeakyBucket¶

本機能はLeakyBucketアルゴリズムによるレートリミットを実現します。

LeakyBucketのリミッター作成時に指定できるパラメータは以下の通りです。

queueSize: キューサイズ
interval: リクエストを処理する間隔（デキューの間隔）

アルゴリズムの概要は以下になります。

サイズNのキューを作成する。
キューはFIFOで処理される。
リクエストはキューに挿入される。
キューが満杯の場合、リクエストを拒否する。
一定のインターバルでキューの先頭からリクエストを取り出し処理する。

LeakyBucketは以下の2つのメソッドを持ちます。 AllowNowはキューが空の場合にのみ、有効なトークンを返します。従って、LeakyBucketを利用する場合は基本的にはWaitNowを利用し、リクエストが処理されるのを待機します。 AcceptはWaitNowのエイリアスです。

func AllowNow() Token
func WaitNow(ctx context.Context) Token
func Accept(ctx context.Context) Token

APIのレートリミットに使用する例は、LeakyBucketによるAPIレートリミットを参照してください。

2. MaxConcurrency¶

本機能はMaxConcurrencyアルゴリズムによるレートリミットを実現します。

Concurrencyのリミッター作成時に指定できるパラメータは以下の通り。

concurrency: 最大同時実行数

アルゴリズムの概要は以下になります。

N個のセマフォ変数を作成する。
リクエストは1つのセマフォ変数をロックし、処理を開始する。
セマフォ変数が全てロックされている場合、直ちに処理をエラーとするか、ロックを獲得できるまで待機する。
処理が完了するとセマフォ変数のロックを開放する。

Concurrencyリミッターは以下の2つのメソッドを持ちます。 AllowNowはセマフォ変数が全てロックされている場合は直ちに無効なトークンを返却、一方WaitNowはセマフォ変数のロックを獲得できるまで待機する。 AcceptはAllowNowのエイリアスです。

func AllowNow() Token
func WaitNow(ctx context.Context) Token
func Accept(ctx context.Context) Token

APIのレートリミットに使用する例は、ConcurrencyによるAPIレートリミットを参照してください。

3. TokenBucket¶

本機能はTokenBucketアルゴリズムによるレートリミットを実現します。 TokenBucketはAPIのレートリミットにおいて広く用いられているアルゴリズムです。 TokenBucketアルゴリズムはバースト（瞬間的な処理数の増加）を許容するアルゴリズムです。

TokenBucketのリミッター作成時に指定できるパラメータは以下の通りです。

bucketSize: バケットサイズ
fillRate: トークン補充レート（基本的には1秒間割合を指す）

アルゴリズムの概要は以下になります。

サイズNのトークン用バケットを作成する。
バケットには一定間隔でr個のバケットが補充される。
バケットが満杯であれば、それ以上トークンは補充されない。
リクエストはバケットから1つのトークンを消費して処理を開始する。
トークンが存在しなければ処理を開始できない。トークンの補充を待機するか直ちに処理を中断する。

TokenBucketリミッターは以下の2つのメソッドを持ちます。 AllowNowは1つのトークンを消費して処理を開始します。トークンが存在しなければ直ちに無効なトークンが返却されるため、処理は中断されます。一方、WaitNowは同様にトークンを消費して処理を開始しますが、トークンが存在しなければ補充されるまで待機します。 AcceptはAllowNowのエイリアスです。

func AllowNow() Token
func WaitNow(ctx context.Context) Token
func Accept(ctx context.Context) Token

APIのレートリミットに使用する例は、TokenBucketによるAPIレートリミットを参照してください。

4. FixedWindow¶

本機能はFixedWindowアルゴリズムによるレートリミットを実現します。 FixedWindowは一定区間における処理数を厳密に制限できる一方、異なる区間の境界において制限値の2倍の処理が実行される可能性のあるアルゴリズムです。

FixedWindowのリミッター作成時に指定できるパラメータは以下の通りです。

limit: 処理数上限

アルゴリズムの概要は以下になります。

サイズNのトークン用バケットを作成する。
バケットには一定間隔で満杯になるようにトークンが補充される。
リクエストはバケットから1つのトークンを消費して処理を開始する。
トークンが存在しなければ処理を開始できない。トークンの補充を待機するか直ちに処理を中断する。

FixedWindowリミッターは以下の2つのメソッドを持ちます。 AllowNowは1つのトークンを消費して処理を開始します。トークンが存在しなければ直ちに無効なトークンが返却されるため、処理は中断されます。一方、WaitNowは同様にトークンを消費して処理を開始しますが、トークンが存在しなければ補充されるまで待機します。 AcceptはAllowNowのエイリアスです。

func AllowNow() Token
func WaitNow(ctx context.Context) Token
func Accept(ctx context.Context) Token

APIのレートリミットに使用する例は、FixedWindowによるAPIレートリミットを参照してください。

セキュリティに関する特記事項¶

セキュリティに関する特記事項はありません。

性能に関する特記事項¶

性能に関する特記事項はありません。

実装例・使い方¶

LeakyBucketによるAPIレートリミット¶

以下の例は、LeakyBucketアルゴリズムによるAPIレートリミットの簡単な実装例です。必要に応じてパス単位などでレートリミットを適用することも可能です。

以下の例では、キューサイズが10、リクエストを処理するインターバルは100ミリ秒に設定されています。また、リクエストが受理された場合、0-100ミリ秒間の間でランダムに待機した後200ステータスを返却します。

package main

import (
    "log"
    "math/rand/v2"
    "net/http"
    "time"

    "github.com/aileron-projects/go/ztime/zrate"
)

func main() {
    queueSize := 10
    interval := time.Millisecond
    limiter := zrate.NewLeakyBucketLimiter(queueSize, interval)
    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        token := limiter.Accept(r.Context())
        defer token.Release()
        if token.OK() {
            time.Sleep(time.Duration(rand.Int64N(100)) * time.Millisecond)
            w.WriteHeader(http.StatusOK)
            _, _ = w.Write([]byte("ok"))
        } else {
            w.WriteHeader(http.StatusTooManyRequests)
            _, _ = w.Write([]byte("too many requests"))
        }
    })

    log.Println("server listens on localhost:8080")
    svr := &http.Server{
        Addr:        ":8080",
        Handler:     handler,
        ReadTimeout: 10 * time.Second,
    }
    if err := svr.ListenAndServe(); err != nil {
        panic(err)
    }
}

ConcurrencyによるAPIレートリミット¶

ConcurrencyアルゴリズムによるAPIレートリミットの簡単な実装例です。必要に応じてパス単位などでレートリミットを適用することも可能です。

以下の例では、同時処理数が10に設定されています。また、リクエストが受理された場合、0-100ミリ秒間の間でランダムに待機した後200ステータスを返却します。

package main

import (
    "log"
    "math/rand/v2"
    "net/http"
    "time"

    "github.com/aileron-projects/go/ztime/zrate"
)

func main() {
    concurrency := 10
    limiter := zrate.NewConcurrentLimiter(concurrency)
    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        token := limiter.Accept(r.Context())
        defer token.Release()
        if token.OK() {
            time.Sleep(time.Duration(rand.Int64N(100)) * time.Millisecond)
            w.WriteHeader(http.StatusOK)
            _, _ = w.Write([]byte("ok"))
        } else {
            w.WriteHeader(http.StatusTooManyRequests)
            _, _ = w.Write([]byte("too many requests"))
        }
    })

    log.Println("server listens on localhost:8080")
    svr := &http.Server{
        Addr:        ":8080",
        Handler:     handler,
        ReadTimeout: 10 * time.Second,
    }
    if err := svr.ListenAndServe(); err != nil {
        panic(err)
    }
}

TokenBucketによるAPIレートリミット¶

TokenBucketアルゴリズムによるAPIレートリミットの簡単な実装例です。必要に応じてパス単位などでレートリミットを適用することも可能です。

以下の例では、バケットサイズが10、トークン補充割合が10/秒に設定されています。また、リクエストが受理された場合、0-100ミリ秒間の間でランダムに待機した後200ステータスを返却します。

package main

import (
    "log"
    "math/rand/v2"
    "net/http"
    "time"

    "github.com/aileron-projects/go/ztime/zrate"
)

func main() {
    bucketSize := 10
    fillRate := 10
    limiter := zrate.NewTokenBucketLimiter(bucketSize, fillRate)
    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        token := limiter.Accept(r.Context())
        defer token.Release()
        if token.OK() {
            time.Sleep(time.Duration(rand.Int64N(100)) * time.Millisecond)
            w.WriteHeader(http.StatusOK)
            _, _ = w.Write([]byte("ok"))
        } else {
            w.WriteHeader(http.StatusTooManyRequests)
            _, _ = w.Write([]byte("too many requests"))
        }
    })

    log.Println("server listens on localhost:8080")
    svr := &http.Server{
        Addr:        ":8080",
        Handler:     handler,
        ReadTimeout: 10 * time.Second,
    }
    if err := svr.ListenAndServe(); err != nil {
        panic(err)
    }
}

FixedWindowによるAPIレートリミット¶

FixedWindowアルゴリズムによるAPIレートリミットの簡単な実装例です。必要に応じてパス単位などでレートリミットを適用することも可能です。

以下の例では、上限が10リクエスト/秒に設定されています。また、リクエストが受理された場合、0-100ミリ秒間の間でランダムに待機した後200ステータスを返却します。

package main

import (
    "log"
    "math/rand/v2"
    "net/http"
    "time"

    "github.com/aileron-projects/go/ztime/zrate"
)

func main() {
    limit := 10
    limiter := zrate.NewFixedWindowLimiter(limit)
    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        token := limiter.Accept(r.Context())
        defer token.Release()
        if token.OK() {
            time.Sleep(time.Duration(rand.Int64N(100)) * time.Millisecond)
            w.WriteHeader(http.StatusOK)
            _, _ = w.Write([]byte("ok"))
        } else {
            w.WriteHeader(http.StatusTooManyRequests)
            _, _ = w.Write([]byte("too many requests"))
        }
    })

    log.Println("server listens on localhost:8080")
    svr := &http.Server{
        Addr:        ":8080",
        Handler:     handler,
        ReadTimeout: 10 * time.Second,
    }
    if err := svr.ListenAndServe(); err != nil {
        panic(err)
    }
}

SlidingWindowによるAPIレートリミット¶

SlidingWindowアルゴリズムによるAPIレートリミットの簡単な実装例です。必要に応じてパス単位などでレートリミットを適用することも可能です。

以下の例では、上限が10に設定されています。また、リクエストが受理された場合、0-100ミリ秒間の間でランダムに待機した後200ステータスを返却します。

package main

import (
    "log"
    "math/rand/v2"
    "net/http"
    "time"

    "github.com/aileron-projects/go/ztime/zrate"
)

func main() {
    limit := 10
    limiter := zrate.NewSlidingWindowLimiter(limit)
    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        token := limiter.Accept(r.Context())
        defer token.Release()
        if token.OK() {
            time.Sleep(time.Duration(rand.Int64N(100)) * time.Millisecond)
            w.WriteHeader(http.StatusOK)
            _, _ = w.Write([]byte("ok"))
        } else {
            w.WriteHeader(http.StatusTooManyRequests)
            _, _ = w.Write([]byte("too many requests"))
        }
    })

    log.Println("server listens on localhost:8080")
    svr := &http.Server{
        Addr:        ":8080",
        Handler:     handler,
        ReadTimeout: 10 * time.Second,
    }
    if err := svr.ListenAndServe(); err != nil {
        panic(err)
    }
}

レートリミット¶

概要¶

機能¶

1. LeakyBucket¶

2. MaxConcurrency¶

3. TokenBucket¶

4. FixedWindow¶

セキュリティに関する特記事項¶

性能に関する特記事項¶

実装例・使い方¶

LeakyBucketによるAPIレートリミット¶

ConcurrencyによるAPIレートリミット¶

TokenBucketによるAPIレートリミット¶

FixedWindowによるAPIレートリミット¶

SlidingWindowによるAPIレートリミット¶

参考資料¶