クラウドMacでiOSトークンバケットを検証:仮想時間と境界値

クラウドMacでiOSトークンバケットを検証:仮想時間と境界値

クラウドMacでiOSトークンバケットを検証:仮想時間と境界値

リモートでテストを実行していると、レート制限のテストで、本来拒否されるはずのリクエストがまれにもう1回通ってしまうことがあります。マシンの負荷のせいにしがちですが、実際には sleep でトークンの補充タイミングを推測していることが原因かもしれません。スレッドの再開が数ミリ秒遅れるだけで、テストは補充境界をまたいでしまいます。iOSのリクエスト受付部分からトークンバケットを純粋な状態機械として切り出し、クラウドMac上で明示的な時刻を与えれば、アルゴリズムの不具合とスケジューリングの遅延を切り分けられます。

まず容量と補充の契約を定める

この記事では、離散的に補充するトークンバケットを使います。容量はトークン2個、250ミリ秒ごとに1個を補充し、作成時は満杯とします。リクエストごとに指定数のトークンを消費し、残数が足りなければ即座に拒否します。キューイングは行いません。補充周期は初期化時刻を起点とし、トークンを消費してもリセットしません。

短時間のバーストを制限しつつ、しばらく使っていなかった後には少数のタスクを続けて実行したい場合に適したモデルです。一方、任意のスライディングウィンドウ内で実行回数を必ず一定以下に抑えたい場合には適しません。両者では境界での挙動が異なります。

クライアント側のレート制限が制御できるのは、自身がリクエストを送るペースだけです。サーバー側のクォータ検証の代わりにはなりません。プロセスを再起動すると満杯に戻るため、これだけでデバイス間やプロセス間のレート制限を実現したともいえません。

時刻には単調増加する整数のミリ秒値を使い、カレンダー時刻は参照しません。以下の実装では、過去に戻る時刻入力を拒否し、テストフィクスチャの誤りによって状態が知らないうちに変わることを防ぎます。

時刻を注入できるコアを実装する

次のコードを TokenBucketChecks.swift として保存します。コアはネットワークにアクセスせず、スレッドを待機させず、アプリのライフサイクルにも依存しません。容量と補充間隔はどちらもゼロより大きいことが、インスタンス生成時の契約です。外部から設定を受け取る場合は、検証を済ませてからインスタンスを作成してください。

import Dispatch
import XCTest

struct TokenBucket {
    let capacity: UInt64
    let interval: UInt64
    private(set) var tokens: UInt64
    private var last: UInt64

    init(capacity: UInt64, interval: UInt64, now: UInt64) {
        precondition(capacity > 0 && interval > 0)
        self.capacity = capacity
        self.interval = interval
        self.tokens = capacity
        self.last = now
    }

    mutating func take(_ cost: UInt64 = 1, at now: UInt64) -> Bool {
        guard now >= last else { return false }

        let steps = (now - last) / interval
        if steps > 0 {
            let room = capacity - tokens
            if steps >= room {
                tokens = capacity
            } else {
                tokens += steps
            }
            last += steps * interval
        }

        guard cost > 0 && cost <= tokens else { return false }
        tokens -= cost
        return true
    }
}

ここでは、まず空き容量と比較してからトークンを加算しています。長時間使われなかった場合でも、単純な加算によるオーバーフローを避けられます。steps * interval は now - last を超えないため、補充の基準時刻を進めても、入力された現在時刻を超えることはありません。

残数が上限に達しても余分なトークンは蓄積しませんが、補充周期の位相は維持します。たとえば249ミリ秒の時点で消費しても、250ミリ秒の時点で補充されます。これはモデルとして明示的に選んだ挙動であり、連続的な平均レートを厳密に保証するものではありません。

実際に待つ代わりに境界値をテストする

続けて、以下のテストを同じファイルに追加します。最初のテストではバースト容量と補充境界を、2つ目では長時間未使用だった場合と不正な入力を確認します。各アサーションには、それぞれ根拠を説明できる明示的な時刻を使います。クラウド上のマシンがその瞬間にどれだけ混雑しているかには依存しません。

final class BucketTests: XCTestCase {
    func testBurstAndRefill() {
        var bucket = TokenBucket(capacity: 2, interval: 250, now: 0)
        XCTAssertTrue(bucket.take(at: 0))
        XCTAssertTrue(bucket.take(at: 0))
        XCTAssertFalse(bucket.take(at: 249))
        XCTAssertTrue(bucket.take(at: 250))
        XCTAssertTrue(bucket.take(at: 749))
        XCTAssertTrue(bucket.take(at: 750))
        XCTAssertFalse(bucket.take(at: 750))
    }

    func testIdleCapAndInvalidInputs() {
        var bucket = TokenBucket(capacity: 2, interval: 250, now: 0)
        XCTAssertTrue(bucket.take(2, at: 0))
        XCTAssertTrue(bucket.take(at: 10_000))
        XCTAssertTrue(bucket.take(at: 10_000))
        XCTAssertFalse(bucket.take(at: 10_000))

        let before = bucket.tokens
        XCTAssertFalse(bucket.take(at: 9_999))
        XCTAssertEqual(bucket.tokens, before)
        XCTAssertFalse(bucket.take(0, at: 10_000))
        XCTAssertFalse(bucket.take(3, at: 10_000))
    }
}

XCTMain([
    testCase([
        ("testBurstAndRefill", BucketTests.testBurstAndRefill),
        ("testIdleCapAndInvalidInputs", BucketTests.testIdleCapAndInvalidInputs)
    ])
])

フル版Xcodeに付属する開発ツールで実行します。

xcrun swift TokenBucketChecks.swift

合否はコマンドの終了コードで判定し、ログに特定の語が出たかどうかでは判断しません。このスクリプトが検証するのは、共通で使うSwiftのアルゴリズムです。iOSのテストターゲットに移すときは、テストメソッドを残し、スクリプト末尾の XCTMain を削除して、テストランナーにテストケースを検出させます。

さらに、容量が1の場合、1回で容量分を使い切る場合、初期化時刻がゼロではない場合、UInt64.max に近い時刻を入力する場合も追加するとよいでしょう。失敗するテストを通すために「数ミリ秒の誤差を許容する」といった緩和をしてはいけません。それでは、決定的なテストを再び実時間のタイミングに依存するテストに戻してしまいます。

単調時計と直列化したリクエスト受付につなぐ

本番コードでは、DispatchTime.now().uptimeNanoseconds / 1_000_000 からミリ秒値を取得できます。初期化時と、その後のリクエスト時には、必ず同じ時刻源を使います。サーバー時刻、壁時計、アプリ起動後の相対カウントを混在させてはいけません。

複数のタスクで同じバケットを共有する場合は、時刻の取得、補充、消費を同じactorメソッド内で行い、その途中に await を挟まないようにします。ロックを使う場合も、時刻はロックを取得してから読み取ります。先に時刻を取得すると、その呼び出しが後からクリティカルセクションに入り、時刻が逆行したと判定される可能性があります。

休止中と再作成時のルールを明確にする

この記事では、システムのスリープ中にも必ずトークンが蓄積するとは保証しません。製品の要件としてスリープ時間も含める必要がある場合は、その意味に合う時計を別途選び、個別にテストしてください。アプリの終了後にバケットを作り直すと、残数は満杯に戻ります。それを許容できない場合は、追加の永続化プロトコルが必要であり、残数だけを保存しても不十分です。

失敗を次の対処につながる結論にする

変更を提出する前に、次の項目を1つずつ確認します。初期状態で許可されるバースト数が容量と一致すること。補充の1ミリ秒前には拒否されること。補充境界では許可されること。複数周期が経過しても容量を超えないこと。消費数ゼロと容量を超えるリクエストが拒否されること。時刻が逆行しても状態が変わらないこと。

アプリに組み込んだ後だけ失敗するなら、まずバケットを複数作成していないか、リクエストのたびにインスタンスを作り直していないか、リトライが共通の受付処理を迂回していないかを確認します。テストは通るのにリクエスト間隔が短すぎるなら、待機を追加して差異を隠すのではなく、容量と補充間隔を見直すべきです。

最後に、アルゴリズムのテスト結果と組み込み後のテスト結果を分けて記録します。前者が答えるのは「状態遷移が正しいか」、後者が答えるのは「すべてのリクエストが本当に同じレート制限の入口を通っているか」です。この2つを分離すれば、リモートでのテストも再現性を保ちやすくなり、次にリグレッションが起きたときも原因を絞り込みやすくなります。

よくある質問

補充のテストにsleepを使わない理由は?

sleep後にスレッドが正確な時刻に再開するとは限りません。整数の時刻を渡せば、補充の1ミリ秒前や境界ちょうどを確実に検証できます。

この実装は並行呼び出しに対応していますか?

そのままでは対応していません。時刻の取得、補充、消費を同じactorまたはロックの中で直列に実行してください。

プロジェクトに合ったMacを選ぶ

ネイティブビルドやシミュレーターでの動作確認が必要なら、Apple Silicon搭載の専有物理Macをレンタルして検証するのがおすすめです。長期にわたって毎日使い、利用場所も固定なら、購入もあわせて検討するとよいでしょう。まずは日単位で試し、継続利用が決まったら月払い・四半期払いを検討できます。

リモートMacをレンタル

プロジェクトの段階に合ったプランを選ぶ

まずは機種、利用期間、接続方法を確認してから、レンタルをご検討ください。