この記事で学んだことをメモる。
Patterns
TL;DR
📝 バッチリードはないのか？
1-1. DB の Indexing
率先して、どのカラムにインデックスを貼るべきか話せ。
調査時は、EXPLAIN ... クエリでクエリプランニングと実行ログを見られる。
1-2. DB の Vertical scaling
1-3. DB の Denormalization
例えば Feed などで使う。(TODO: Instagram Feed 使った方がいい?
問題点は、Eventual consitency と more storage cost。
NoSQLではこれをするのが前提。、RDBでは、PostのLike count などで用いられることが多い。
2-1. DB の Read replicas
Bonus: Redundancy.
2-2. DB の Sharding
⚠️ Scale Write のためにやることはあるが、Scale Readのやることはあまりない
Partitiona Keyを元にデータを複数のノードのデータベースに振り分ける。
以下のOperational complexityが伴う。
- manage shard maps
- rebalance data when adding/removing a shard
- cross shard query
📝 Functional Sharding、Geolocational Sharding もある。
3-1. Application-Level Caching (Redis)
Access Skew (アクセスの頻度の偏りがある)場合に導入する。
Cache invalidation strategy
- 1️⃣ Time-based expiration (= TTL)
- 2️⃣ Write-through invalidation with delete
- 3️⃣ Write-through invalidation with update
2️⃣ (write-through-delete) と 3️⃣ (write-through-update) を比較する。
- 2️⃣ (write-through-delete) だと、最初にデータを叩いたクライアントがDBからのクエリを実行する必要がある。従って、YouTube TopK の集計データなど時間がかかる場合 (= derived result) は 3️⃣ (write-through-update) を使うべき。
- 2️⃣ (write-through-delete) は、cache stampede problem によるDBの負荷のスパイクに対応する必要がある。
- 3️⃣ (write-through-update) だと、CDN, Redis といった全てのキャッシュレイヤーのデータへの上書きが必要になる。しかし、2️⃣ (write-through-delete) を使えば、それぞれのキャッシュの使用者が最新のバージョンを読みに行くことで、最新のバージョンを知ることができる。
- 3️⃣ (write-through-update) だと、レースコンディションにより、最新のDBデータより前のバージョンのDBデータによってキャッシュが上書きされる場合がある。2️⃣ (write-through-delete) だとこれは発生しない。
- 2️⃣と3️⃣のいずれも、DB と Redisへの DualWrite が必要となり、これらのatomicityの担保が課題となる。(TODO)
- 高スループットな集計・ランキングシステムにおいては、3️⃣ (write-through-update) を使うのが2026年のベストプラクティス。キャッシュは「消す」のではなく「バックグラウンドで常に最新状態に更新し続ける（Warm Cache）」。 ref. YouTube TopK - DD: How can we cut down on the number of queries to the database?
- 4️⃣ Versioned keys (= delete old vesioned cache)
後述の DD 
を参照。ソースデータの更新を即時見えるようにしたい時に使用する。
- 5️⃣ Write-behind invalidation
- 6️⃣ Tagged invalidation
まだ整理できていないので話さなさい。
3-2. CDN and Edge Caching
静的コンテンツに使われることが多いが、Modern CDN は動的コンテンツを返すこともできる。
問題点は、cache invalidation と コスト。
📝 Cache-Control headers tell a CDN how long to store a resource and whether to validate it before serving.
DD 
"What to do when your queries start taking longer as your dataset grows?" 🔥🔥
以下を使えるかこの順に見ていく。
- Optimize read performance within your database
- indexing
- hardward upgrades
- denormalization
- Scale your database horizontally
- read replicas
- database sharding
- Add external caching layers
- Application-Level Caching (Redis)
- CDN and Edge Caching
📝 Go ahead and mention which columns you'll add indexes to when you're outlining your database schema in an interview. Shows you're thinking ahead.
DD 
"How do you handle millions of concurrent reads for the same cached data?" 🔥🔥🔥
🟢 Soluion 1. Single Flight Pattern (in-memory request coalescing)
Caceh Stampede Problem の Single Flight Pattern と同じことをする。
🟢 Solution 2. Fanout on Write = Horizontal Scaling x Sub-sharding on Hot Key
Hot Key のみが、K+1個(事前固定)のシャードのレプリカを持つ。Readerはその中の一つのシャードレプリカから値を読み出す。
- Writer は基本的にサブシャード 0 に書き込む。しかし、local statistics を用いてあるキーが Hot Key だと検知できた場合は、そのキーへの書き込みをK+1個のサブシャードに書き込みを行う。
- Reader側は基本的にサブシャード 0 から読み込む。しかし、local statistics を用いてあるキーが Hot Key だと検知できた場合は、そのキーへの読み込みをサブシャード1-Kの中からランダムに選んだ一つから行う。もし、Hot Key 判定がfalse positiveでそのキーにサブシャードが存在しなかった場合は、サブシャード０にフォールバックする。(false negativeの時には、サブシャード0にリクエストが集中してしまう)
TODO: Taylor Swift ポストへのLikeのように事前にHot Keyになることがわかってる場合はどうするか？
いや、というか事前にリード時のホットキーになることがわかってるものしか無理では？ライト時にローカルの統計データをみると書いてあるが、リードとライトのサーバーが分かれてる場合もあるし、ライト時に将来リードがはねるかなんてわからないのでは。
The trade-off with fanout is memory usage and cache consistency. You're storing the same data multiple times, and invalidation becomes more complex since you need to clear all copies.
📝 これは、単一のHot Keyへのリクエスト数が増えた場合の話をしていうる。
もし純粋にキャッシュ全体の利用頻度が増えた場合は、Redis Clusterを用いてシャード数を増やせば良い。
c.f. 逆パターン: Scaling Writes の Fanout on Read = Split Hot Keys Dynamically
DD 
"What happens when multiple requests try to rebuild an expired cache entry simultaneously?" 🔥🔥🔥
= Cache Stampede Problem
DD "How do you handle cache invalidation when data updates need to be immediately visible?" 🔥🔥🔥
-> cache versioning を使う。
- DB の verionカラム
- Redis の
{model}:lastest_version -> 42record - Redis の
{model}:#{key}:v#{version} -> valrecords
を用いて実装する。
- Writerは、DBの値更新時、versionカラム値の更新とRedis内のlatest_versionキーのinvalidationを行う。
- Readerは、まず、Redisの中のlatest_version値、なければDBのverionカラムの値を読む。その後そのバージョンの探しているキーの値をRedisから、なければDBから読む。
ただし、
When versioning isn't practical — perhaps you're caching search results or aggregated data—you need explicit invalidation strategies. Another approach uses a deleted items cache, which is a much smaller working set of items that have been deleted, hidden, or changed.
なお、write-though よりも、cache versioning が好まれる。write-through では、全てのレイヤーのキャッシュを知っておき、そこへ上書きをする必要があるから。
🟢 Follow-up: CDN にキャッシュされている場合はどう即時反映するか？
新たに、アイテムの最新バージョンを返す API を実装する。(ex. GET /posts/:id/version)
FEはまず、このAPIを叩いて取得したいアイテムの最新バージョンを取得する。
そして、これをリクエストのパラメータキーに含め、APIコールをする。(ex. GET /posts/:id?v=44)
これは、CDNより後ろのRedisを一回叩くというプロセスが挟まるが、これはversionの2文字を返すだけなので、Postやましてや大容量データを返すよりも圧倒的にRedisの負荷が低くなる。しかし、この負荷を減らしたいのであれば、「Post投稿三時間以内」や「イベント開始三時間前」のみに限って、version指定を行うようにすれば良い。