URLリダイレクトのキャッシュ戦略：L1 LRUとL2 Redis

URL短縮サービスのリダイレクト層は、キャッシュ戦略そのものがアーキテクチャであると言える、数少ない本番システムの1つです。ホットパス上で意味のある処理は他にほとんどありません。すべてのリクエストはキー（短縮スラグ）を解決し、遷移先URLを読み取り、301または302を返却するだけです。それ以外はすべてオブザーバビリティと記帳処理に過ぎません。中央値のリクエストが800マイクロ秒で済むか、12ミリ秒かかるかを左右するのはキャッシュです。

本稿では、Elidoのedge-redirectサービスを支えるキャッシュ戦略について解説します。2つの階層、ヒット率よりもテールレイテンシの最適化を優先して選ばれたエビクションポリシー、見た目以上にシンプルなワーミング戦略、そして18ヶ月の運用で実際に遭遇した失敗モードについて説明します。p95リダイレクト15ms未満の指標ではレイテンシバジェット全体をカバーしましたが、本稿ではキャッシュに特化した深掘りを行います。

なぜ2層なのか#

リダイレクトサービスの最も単純なキャッシュアーキテクチャは、リダイレクトプロセスとオリジンデータベースの間にRedisクラスターを1つ置く単層構造です。データベースにヒットしないすべてのリクエストはRedisにヒットし、Redisにヒットしないリクエストはデータベースにヒットします。Redisへのホップは、同じリージョン内であれば約1ms増加します。

2層キャッシュでは、Redisの前段にインプロセスレイヤーを追加します。第1層（L1）はリダイレクトプロセスのアドレス空間内に存在します。L1でヒットすれば、ネットワークのラウンドトリップなしで、数百ナノ秒で遷移先URLを返却できます。L1でミスした場合はRedis（L2）にフォールバックし、サブミリ秒のレイテンシで処理されます。L2でもミスした場合は、正規のPostgresデータベースに対するオリジンgRPCコールが発生します。

単層にするか2層にするかの選択は、本質的にテールレイテンシをどこまでフラットにする必要があるかという問いに集約されます。Redisは高速ですが、無料ではありません。負荷がかかるとRedisへの1msのp50は4〜6msのp99になり、ネットワークに競合が発生すればp99.9は20msを超えることもあります。p95 < 15msを目標とするSLOにおいて、すべてのRedisヒットはバジェットの大部分を消費します。p99.9 < 50msを目指す場合、Redisのテールが支配的な要因となります。

インプロセスのLRUは、トラフィックの80%以上を占める高頻度キーを吸収します。Elidoのトラフィック分布では、リクエストボリュームの上位1,000個の短縮リンクがリダイレクトリクエストの70%以上を占めています。これらのキーをインプロセスで提供するのは容易であり、ロングテールをRedisに任せてもp95を悪化させることはありません。

L1：プロセスごとのLRU#

L1キャッシュには、CaddyやDgraphでも採用されているアドミッションポリシー付きLRUであるRistrettoを使用しています。これを選んだ理由は3つあります。

並列読み取りがCPUコア数に合わせて線形にスケールする。 単純なsync.Mapキャッシュは、典型的なエッジPOPマシンで約4M ops/secで頭打ちになりますが、Ristrettoはベンチマークで30M+を維持します。
TinyLFUアドミッションポリシーにより、1回限りのスキャンワークロードがホットキーを追い出すのを防ぎます。10,000個のユニークなスラグを1回ずつ巡回するボットのクロールによって、真に頻度の高いリンクがキャッシュから押し出されることはありません。
キー数ではなくメモリ使用量で制限できる。「100,000エントリまで保存」ではなく「256MBまで使用」と設定できるため、キャパシティプランニングにおいて重要です。

実際に運用している設定は以下の通りです。

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10Mカウンター → 約1Mアイテムを追跡
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCountersはTinyLFUの頻度追跡テーブルのサイズです。Ristrettoのドキュメントにある経験則では、期待されるアイテム数の10倍に設定します。256MBの予算でリンクレコードが平均200バイトの場合、満杯時にキャッシュは約1.3Mエントリを保持します。

L1エントリのTTLは60秒です。これは意図的に短く設定されています。リダイレクトの遷移先はダッシュボードからいつでも変更可能であり、L1キャッシュはインバリデーション（無効化）のパスが最も遅いレイヤーだからです（Redisはパブリッシュによって無効化できますが、L1は各プロセスに存在するため、協調的な無効化パスが必要です）。

TTLが60秒ということは、遷移先の更新後に最悪の場合でも60秒で最新の状態になることを意味します。ほとんどのユースケースではこれで十分ですが、ライブキャンペーン中の即時の遷移先変更など、これが許容されないユースケースのために、ダッシュボードのインバリデーションボタンを押すとフリート全体のすべてのL1キャッシュをパージするファンアウトが実行されます。このファンアウトには、各エッジプロセスが起動時に購読するRedisのpub/subチャネルを使用します。

L2：リードレプリカ付きRedisクラスター#

L2はRedisクラスターで、各リージョン（FRA、ASH、SGP）にデプロイされています。読み取りはローカルレプリカに行われ、書き込みはリージョンのプライマリに行われ、Redisの標準的な非同期モデルで複製されます。

データフォーマットは軽量です。L2におけるリダイレクトレコードは以下のようになります。

KEY:   redirect:f.elido.me:abc123
VALUE: {"d":"https://shop.example.com/spring","f":0,"v":12}

遷移先URL、フラグ（ボットフィルタリングの有効化、パスワード要求など。uint16にパック）、およびバージョンの3つのフィールドです。バージョンはPostgresの行バージョンであり、読み取り時に古いキャッシュエントリを検知するために使用されます。

L2のTTLは24時間です。L2には機能するインバリデーションパスがあるため、L1よりもはるかに長く設定されています。オリジンデータベースでリンクが作成または更新されると、APIがリージョンのインバリデーションチャネルにRedis pub/subメッセージを発行し、リダイレクトプロセスはL1エントリを破棄します。L2エントリはAPIレイヤーによって直接上書きされます。

pub/subによるインバリデーションには、「損失の可能性がある」という微妙な性質があります。インバリデーションメッセージが発行された時にリダイレクトプロセスが再起動中だった場合、そのメッセージは届かず、そのプロセスのL1キャッシュは最大60秒間、古い値を返し続ける可能性があります。TTLがバックストップ（最終防衛線）として機能するため、古さは限定的であり、これは許容範囲内としています。

各POPのRedisクラスターのサイズは小規模です。FRAでは3つのプライマリノードと3つのレプリカが稼働しており、データセット全体は約4GBに収まります。通常の負荷下でのキャッシュヒット率（L1 98%、L2 1.8%、オリジン 0.2%）では、Redisに求められるスループットは中程度であり、通常はPOPあたりピーク時で15k ops/sec程度です。これは、必要であれば1つのプライマリノードに集約しても十分対応可能な容量です。

エビクションポリシーの選択#

RistrettoのTinyLFUアドミッションポリシーは、テールレイテンシにおいて最も重要な選択です。

素朴なLRUは、空きを作る必要がある場合に常に「最も古く使用された（Least Recently Used）」キーを追い出します。これはアクセスパターンが均一であれば問題ありません。最近使われたキーが再び使われる可能性が最も高いからです。しかし、以下の2つの特定のパターンでは破綻します。

スキャンワークロード。ボットのクロールなどで50,000個のユニークなスラグに短時間で次々とアクセスが発生した場合、素朴なLRUではすべてのホットキーが追い出され、二度とアクセスされないクロール用のキーに置き換わってしまいます。キャッシュヒット率は急落し、オリジンへの負荷が急増し、リクエストの多くがスローパスを通るためp95が跳ね上がります。
バースト的なホットキー。普段はアクセスが少ないリンクが、ソーシャルメディアでの拡散やTVCMなどで30秒間に100kリクエストを突然受ける場合、これを迅速にキャッシュする必要があります。素朴なLRUでは、既存のホットキーの1つを追い出してしまいます。

TinyLFUはこれら両方に対応します。アドミッションポリシーがキーの頻度を追跡し、新しいキーが追い出し候補のキーよりも頻度が高い場合にのみキャッシュに受け入れます。1回限りのボットクロールでは、クロール用キーの頻度カウントが1であるため、ホットキーが追い出されることはありません。バースト的なホットキーは、その頻度が追い出し候補を超えた時点でキャッシュに入りますが、これは数百回のリクエスト内で発生します。

代償として、新しく人気が出たリンクの最初の100〜500リクエストは、アドミッションポリシーがキャッシュを決定するまで低速（L2またはオリジンへのフォールバック）になります。ほとんどのユースケースではこれが正しいトレードオフです。リンクが急増することが事前に分かっているキャンペーンなどのために、後述するプリウォーム（予熱）エンドポイントを用意しています。

キャッシュワーミング#

L2キャッシュは、新しいRedisクラスターが立ち上がる際にコールドスタートします。スナップショットからのワーミングは行っておらず、クラスター再起動後の最初の5分間は、キャッシュが自然に埋まるまでオリジントラフィックが増加します。

L1キャッシュは、リダイレクトプロセスが再起動する際（デプロイ、OOMキル、スケールアップ）にコールドスタートします。プロセス再起動後の最初の30秒間は、ほとんどのリクエストがL2にフォールバックし、その後の60秒間でL1がホットキーのワーキングセットで満たされます。オリジン負荷へのコールドスタートの寄与はわずかです（ほとんどのエッジプロセスはキャッシュTTLよりもはるかに長い間稼働し続けます）。

例外として、キャンペーンマネージャーが急増が予想されるリンク（TVCMのURL、プレスリリースのURL、ローンチ発表など）を事前に公開する場合、ダッシュボードに「プリウォーム」のトグルを用意しています。これをオンにすると、各POPのエッジリダイレクトサービスに対してno-opリダイレクトが発行され、事前にL1が投入されます。これは派手な機能ではありませんし、滅多に必要ありません。オートスケーラーが予期せぬトラフィックの急増を適切に処理するからです。プリウォームは、キャッシュが冷えていることによる最初の60秒間のレイテンシを避けたい、事前に予測可能な急増への対策です。

L1がキャパシティに達した時#

256MBのL1キャッシュは、典型的なエッジPOPでは1分以内に満杯になります。満杯になると、新しいキーが来るたびにTinyLFUアドミッションポリシーが既存のキーを追い出すかどうかを判断します。

興味深い観察結果として、我々の分布では、ウォームアップが完了するとL1のヒット率は約98%でプラトー（安定）に達します。残りの2%のミスはロングテールです。トラフィックの30%未満しか占めない約30%のリンクであり、TinyLFUの頻度しきい値を超えられなかったものです。これらはL1でミスし、L2でヒットします。L2でのヒット率は約99%です。最終的に、全リクエストのわずか0.2%がオリジンに到達します。

この分布を、高負荷のボットトラフィック、バイラルな急増、定常状態という3つのワークロード形状で測定しましたが、L1ヒット率は95%から99%の間で推移しました。L2ヒット率は98%〜99.5%でより安定しています。したがって、リダイレクト層からの合計オリジン負荷は、着信リクエストボリュームの約0.5%に抑えられており、これがオリジンのキャパシティプランニングにおいて重要な数値となります。

キャッシュインバリデーションの詳細#

インバリデーションのフローは、外部からアーキテクチャを見た時に最も誤解されやすい部分です。その詳細は以下の通りです。

APIが遷移先URLを変更するPATCH /v1/links/{id}を受け取ると、以下の3つが順番に実行されます。

Postgresが変更をコミットし、新しい行バージョンを設定します（UPDATE links SET destination = ?, version = version + 1 WHERE id = ?）。
Redisに直接書き込みが行われ、すべてのリージョンのRedisクラスターで新しい値が反映されます。APIからの書き込みは、ライトスルーレイヤーを通じて各リージョンのRedisにファンアウトされます。
pub/subインバリデーションが発行され、各リージョンのinvalidate:redirectチャネルに流れます。エッジリダイレクトプロセスは起動時にこのチャネルを購読しており、そのキーのL1エントリを破棄します。

この順番が重要です。Postgresを優先することで、正規のストアが確実に新しい値を保持します。パブリッシュの前にRedisのライトスルーを行うことで、パブリッシュを見逃したプロセスがRedisから読み取った場合でも新しい値を取得できるようにします。パブリッシュはL1の同期を維持するための最適化であり、TTLはパブリッシュが失敗した場合のバックストップです。

既知のレースコンディションとして、リダイレクトプロセスがRedisから読み取っている最中（L1ミスのため）に、並行してインバリデーションのパブリッシュが発生するケースがあります。読み取り結果は、パブリッシュがわずかに早ければ新しい値になり、わずかに遅ければ古い値になります。古い値が返され、L1にキャッシュされた場合、そのプロセスでは次の60秒間、古い値が提供され続ける可能性があります。これは許容されています。読み取りとパブリッシュの競合に対して同期ロックをかけるという代替案は、全リクエストにレイテンシを追加することになり、0.01%未満のインバリデーションにしか影響しないエッジケースを避けるための代償としては大きすぎるからです。

古さの許容範囲が極めて狭いユースケース（法的理由による遷移先URLの削除、遷移先が突然悪意のあるサイトになった場合など）のために、ダッシュボードの「キャッシュをパージ」アクションは、より積極的なインバリデーションを実行します。フリート全体のすべてのL1読み取りを100ms停止し、すべてのL1からキーを削除してから再開します。これは滅多に使用されず、秒あたりの実行回数に制限がかかっています。

実際に遭遇した失敗モード#

18ヶ月の運用履歴の中で、現在の構成を形作るきっかけとなった3つの失敗事例を記録しておきます。

古いレプリカを伴うRedisプライマリのフェイルオーバー。運用4ヶ月目に、FRAクラスターのプライマリノードが故障しました。Sentinel主導のフェイルオーバーにより、30秒以内にレプリカが昇格しました。しかし、故障の瞬間にレプリカはプライマリから約200ms遅れており、フェイルオーバー直前に発行された数百件のインバリデーションが昇格後のレプリカに届いていませんでした。結果として、約0.3%のリダイレクトが古い遷移先を返してしまう短い時間が生じました。解決策として、現在はレプリカをmin-replicas-to-write 1およびmin-replicas-max-lag 10で運用しています。これにより、書き込みの可用性がわずかに低下する代わりに、レプリケーションラグの保証を厳格にしています。

合成モニタリングスキャンによるL1キャッシュのスラッシング。9ヶ月目に、サードパーティのアップタイムモニタリングサービスの設定ミスにより、ある顧客のワークスペース内のすべての短縮リンクが1分間に1回プローブされる事態が発生しました。その顧客は18,000個の短縮リンクを持っていました。プローブパターンは60秒ごとに全スキャンを行うものでした。その影響で、3つのエッジPOPでL1キャッシュヒット率が98%から71%に低下しました。スキャンパターンによって、プローブされたすべてのキーがキャッシュに受け入れられてしまったためです。解決策として、キャッシュ受け入れレイヤーの前にUser-Agentベースのフィルタリングを追加しました。既知のモニタリングUser-Agentはキャッシュをバイパスし、直接L2から提供されるようにしました。これはTinyLFUのエッジケースであり、スキャンキーが真にホットなキーを追い出すのに十分な頻度を持っているように見えてしまった例です。

長時間デプロイ中のpub/sub切断。13ヶ月目に、想定よりも長くかかったデプロイ（約4分）により、いくつかのエッジプロセスがRedisプライマリのフェイルオーバー後も古いpub/subチャネルに接続されたままになりました。新しいプライマリに発行されたインバリデーションがそれらのプロセスに届かず、デプロイ期間中、L1キャッシュが古い値を返し続けました。解決策として、pub/sub接続にハートビートを導入し、ハートビートを逃した場合には自動再接続するようにしました。また、念のための予防策としてデプロイ時にL1をフラッシュするようにしました。

検討したが不採用となったもの#

評価したものの、採用しなかった代替案をいくつか挙げます。

インプロセスキャッシュのみで、Redisは置かない。テスト済み。L2がないと、個々のプロセスにおけるミス率が高くなりすぎ、オリジンデータベースのキャパシティを3〜5倍増強する必要がありました。オリジンのキャパシティ削減効果を考えると、Redisの追加コストはわずかです。

リダイレクトキャッシュにCloudflareやFastlyのようなCDNを使用する。ステージングでテスト済み。キャッシュヒット時のCDNのリージョンレイテンシ（1〜2ms）はRedisとほぼ同等ですが、インバリデーションの話が格段に悪化しました（CDNのパージには分単位のレイテンシが発生し、URLごとのパージコストもかかります）。CDNはレイテンシもヒット率も改善することなく、複雑さだけを増大させました。

L1をさらに大きくする。256MBの予算は、プロセスごとのメモリエンベロープに合わせてサイズ設定されています。これを2倍にしても、ヒット率は2倍にはなりません。ホットなワーキングセットはすでに収まっているからです。我々の分布では、収益逓減（収穫逓減）は128MBあたりから始まっており、256MBあればトラフィックの増加に対しても十分な余裕があります。

オブザーバビリティ#

各エッジプロセスごとに追跡しているメトリクスは以下の通りです。

cache_l1_hit_total、cache_l1_miss_total — プロセスごとの算出ヒット率。
cache_l2_hit_total、cache_l2_miss_total — リージョンごとの算出ヒット率。
cache_origin_request_total — オリジンへのリクエストボリューム。SLOターゲットは全リクエストの1%未満。
cache_invalidation_total{source="pubsub|ttl|purge"} — メカニズムごとのインバリデーション回数。
cache_l1_memory_bytes — L1キャッシュが実際に使用しているメモリ。設定予算の90%でアラート。

すべてのメトリクスはPrometheusによってスクレイピングされ、オブザーバビリティガイドのダッシュボードセットで可視化されています。リージョンレベルのGrafanaダッシュボードには時間経過によるリージョンのキャッシュヒット率が表示され、プロセスごとのダッシュボード（インシデント時に使用）には、個々のL1ヒット率とメモリ使用量が表示されます。

この戦略をいつ使い、いつ使わないべきか#

2層キャッシュが適しているのは、以下のような場合です。

ワークロードが読み取りヘビーで、ロングテールなキー分布を持っている。
ホットなワーキングセットがプロセスのメモリ（数百メガバイト）に収まる。
キャッシュミスが高コストであり、第2層を設けることでデータベースの負荷を大幅に削減できる。
L1のTTLだけでは許容できないほど、古さに対する要件が厳しい。

以下のような場合には適していません。

ホットなワーキングセットがプロセスのメモリに収まらない。この場合、L1ミスが頻繁に発生してL2にフォールバックするため、L1を置くメリットがほとんどありません。
読み取りに対して書き込みが非常に頻繁である。インバリデーションのコストが支配的になります。
データがリクエストごとにユニークである（キャッシュのメリットが全くない）。

URL短縮サービスのワークロードについては、4つの「適している」条件がすべて当てはまっており、上記の構成は18ヶ月の本番環境の成長に耐えてきました。他のワークロードにおいては、階層の数やエビクションポリシーの再評価が必要です。