We’re sorry we missed you at re:Invent, but we can still meet!

分散型レートリミッターが欲しいとおっしゃいましたか?

Momentoに支えられた分散型レートリミッターを構築する。

プラティク・アガルワル
著者

Share

レート・リミッターは、コンピューター・サイエンスで私が最も好きなトピックのひとつです。ツイッターのニュースフィードを見ていても、ライブビデオをストリーミングしていても、レートリミッターとやりとりしている可能性はゼロではありません。レートリミッターはあなたを監視し、あなたのトラフィックについて決定を下し、あなたが騒ぎすぎたら当然停止させます。

レートリミッターの何が問題なのか?

レート制限の必要性は、あらゆるサービスの健全性と品質を維持するという基本的な要件に由来します。これがなければ、リソースは簡単に過負荷になり、サービスの低下や完全な失敗につながります。これは、分散システム、ウェブサービス、マルチテナント・アプリケーションなど、クライアントからのリクエストの量や頻度が大きく変化するアプリケーションでは特に重要です。また、分散型サービス拒否(DDoS)攻撃など、ある種のサイバー攻撃を防御する上でも重要な要素となります。

ステートレス・レートリミッターによるスロットリングの課題

レート制限の一般的なタイプの1つは、1つのホストからデータベースへのリクエスト数を制御することです。例えば、ホストが10台あり、データベースが1秒あたり最大1000クエリを処理できる場合、各ホストのクエリレートを1秒あたり100クエリに制限することができます。しかし、ステートレス・レート・リミッターは簡単なソリューションですが、動的で分散した環境では不十分です。システム全体の状態に気づかず、孤立して動作するため、非効率で不公平になる可能性があります。このような硬直的なアプローチでは、変動する需要やシステムの変化に対応できず、リソースが十分に活用されなかったり、不必要なスロットリングが行われたりすることが多くあります。システムがより複雑になるにつれ、より適応性が高く、意識的で、ステートフルなレート制限ソリューションの必要性が明らかになります。そこで、Momento Cacheのようなサービスを活用することで、よりスマートで応答性の高いレートリミッターを構築するのに必要なツールが提供されます。

モメントが救う

例えば、分散型のレートリミッターを作成し、各ユーザーのTPM(transactions-per-minute)を効率的に管理したいとします。私たちは、Momentoの機能を活用しながらも、メカニズムが異なる2つの異なるアプローチでこの道を冒険します。

私たちが推奨する最初のアプローチは、MomentoのincrementupdateTTL APIを利用します。この方法は効率的であるだけでなく、非常に正確です。これは、各ユーザとタイムウィンドウのために一意に構築されたキーをインクリメントし、分の最初のリクエストにTTL(time-to-live)を設定することに依存します。


/**
   * Generates a unique key for a user (baseKey) for the current minute. This key will server as the Momento cache key where we will store the amount of calls that have been made by a user for a given minute.
   */
generateMinuteKey(baseKey: string): string {
	const currentDate = new Date();
	const currentMinute = currentDate.getMinutes();
	return `${baseKey}_${currentMinute}`;
}

リクエストは、カウントがあらかじめ決められた上限に達するまで許可され、その時点でスロットリングが実施されます。


public async isLimitExceeded(id: string): Promise {
	const currentMinuteKey = this.generateMinuteKey(id);
	// we do not pass a TTL to this; we don't know if the key for this user was present or not
	const resp = await this._client.increment(
		RATE_LIMITER_CACHE_NAME,
		currentMinuteKey
	);

	if (resp instanceof CacheIncrement.Success) {
		if (resp.value() <= this._limit) {
			// If the returned value is 1, we know this was the first request in this minute for the given user. So we set the TTL for this minute's key to 60 seconds now.
			if (resp.value() === 1) {
				await this._client.updateTtl(
					RATE_LIMITER_CACHE_NAME,
					currentMinuteKey,
					RATE_LIMITER_TTL_MILLIS
				);
			}
			// we are below the limit, so we can allow the request
			return false;
		}
	} else if (resp instanceof CacheIncrement.Error) {
		throw new Error(resp.message());
	}

	// the user has exhausted their limit for the current minute
	return true;
}

2つ目のアプローチは、Redisが推奨するような伝統的な方法からヒントを得ており、getincrement APIに依存しています。その目的は似ているが、この方法は、古典的な読み取り-変更-書き込み操作に固有の競合状態の影響を受けやすいため、特に高負荷時には精度が落ちることがあります。


public async isLimitExceeded(id: string): Promise {
	const currentMinuteKey = this.generateMinuteKey(id);

	// read current limit
	const getResp = await this._client.get(
		RATE_LIMITER_CACHE_NAME,
		currentMinuteKey
	);

	if (getResp instanceof CacheGet.Hit) {
		// cache hit! Check if value is less than limit
		if (parseInt(getResp.value(), 10) <= this._limit) {
			await this._client.increment(RATE_LIMITER_CACHE_NAME, currentMinuteKey);
			// we are below the limit, allow request!
			return false;
		}
	} else if (getResp instanceof CacheGet.Miss) {
		// a miss indicates first call to key, so we set TTL now to 1 min
		await this._client.increment(
			RATE_LIMITER_CACHE_NAME,
			currentMinuteKey,
			1,
			{
				ttl: RATE_LIMITER_TTL_MILLIS,
			}
		);
		// first request, we are below the limit, allow request!
		return false;
	} else if (getResp instanceof CacheGet.Error) {
		throw new Error(getResp.message());
	}

	// the user has exhausted their limit for the current minute
	return true;
}

我々の広範なシミュレーションは、最初のアプローチの優位性を強調しています。競合が多いシナリオでは、完璧な精度を維持するだけでなく、賞賛に値する遅延指標を示しています。2番目のアプローチは、時折わずかにレイテンシが低くなるものの、競合が増えると一貫して精度が低下します。

まとめ

効率的な分散レートリミッターを追求した結果、Momentoが提供する魅力的なソリューションにたどり着きました。厳密なテストを通じて、MomentoのincrementupdateTTLのAPIを活用することで、特に負荷の高いシナリオにおいて、精度と耐障害性に優れた堅牢なレートリミッターが得られることを発見しました。

スロットリングを実装する良い方法をお探しですか?私たちのサンプルコードを使って、Momento Cacheに支えられたレートリミッターを構築しましょう。ハッピーコーディング!

Share