Transformer Math

Deep Dive A — Dual-Write Migration Strategy

Approach

The dual-write layer is active for the entire migration window (target: <7 days). The core mechanism is a write fan-out at the ingestion point: every item the Embedder Service processes is written to both the old index and the new index atomically from the perspective of the inbound item stream. This guarantees that the new index never falls behind on fresh content — only on the existing corpus, which the offline backfill pipeline catches up. The state machine proceeds in five phases:

1. Dual-write on: every item ingested after migration start is written to both indexes. The old index remains the read source (100% weight). The new index accumulates fresh items but has zero coverage on historical corpus.
2. Backfill runs: the offline pipeline re-embeds the full corpus in priority order — recency first, because recent items have the highest query probability. At 10M items/day steady state and 100M item corpus, backfill throughput must exceed 100M items / 7 days = ~165 items/sec^ⁱ sustained. This is a throughput target, not just a latency target — it drives the embedder GPU count for the migration window.
3. Blended read phase: once new index coverage passes 50%, the retrieval layer blends results from both indexes using a sliding weight controlled by a feature flag per consumer: day 1 at 10% new, day 3 at 50% new, day 6 at 90% new. Blending is at result-set level (merge and re-rank by similarity score), not request level (routing). Consumer eval runs continuously during this window on the golden query set to gate each weight increment.
4. Cutover gate:flip to 100% new index only when new index recall@k meets or exceeds old index on all consumer golden query sets, AND canary traffic (5% of production) shows no engagement regression (<0.5pp CTR drop for ads, no session depth regression for recsys).
5. Decommission: old index offline, dual-write layer removed, storage reclaimed within 24 hours of cutover. The 24-hour grace period allows a fast rollback if the cutover reveals a production issue not caught by the canary.

Trade-off: backfill throughput vs. migration window cost

The non-obvious trade-off is not “how fast can you backfill” but “what does each day of dual-write cost vs. the risk of cutting over with incomplete coverage.”Running dual-write for 7 days on a 100M item corpus at 768 dims means 100M × 768 × 4 bytes × 2 indexes ≈ 600GB of extra live storage^ⁱ, plus the embedder GPU time to process the backfill. That storage cost scales linearly with migration window length. The temptation is to cut the window short by accepting partial coverage (e.g., cutting over at 90% corpus coverage). The non-obvious danger: the missing 10% is not random — it is the oldest, least-recently-updated items, which are precisely the long-tail catalog content that search depends on for rare queries. A 90%-coverage cutover produces normal aggregate recall but catastrophic recall on long-tail queries.

Failure mode

Index skew during dual-write: a network partition or embedder crash causes a write to succeed on the old index but fail on the new index, creating silent divergence. The new index silently underrepresents items that arrived during the outage. Because the old index is still the primary read source during early phases, this divergence is invisible — users see correct results. But when the blended weight shifts to 50%+ new, those missing items drop out of results.

Detection metric

Per-index write success rate, tracked per shard per minute. Alert threshold: new index write success rate falls below 99.5% of old index write success rate for more than 2 minutes. Secondary check: consistency job samples 1% of items hourly, compares both indexes, alerts if item-level divergence exceeds 0.5%. A diverged item is re-queued for the embedder with high priority.

Mitigation

The blended-read feature flag is the rollback lever — any consumer can be reverted to 100% old index in seconds, independent of other consumers, with no infrastructure change. Secondary-effect callout: reverting one consumer (e.g., ads) while keeping others on the new index means the dual-write layer must remain active and storage costs continue to accrue until the slowest consumer completes migration. Budget for this in the 7-day window estimate.

Real-world example

Pinterest's Unifying Visual Embeddings migration (inferred from the Pinterest Engineering blog) unified multiple per-product visual embedding models into a single platform serving visual search, related pins, and ad retrieval. The migration required that all three consumers cut over from their own bespoke indexes to the shared platform index simultaneously, because the unified model produced a shared embedding space — partial migration would mean consumers were comparing vectors from different spaces. The lesson applied here: if any consumer cannot complete within the migration window, the entire migration must be deferred, not partially shipped. The per-consumer eval gate exists precisely to catch this before dual-write storage costs compound.

Deep Dive B — HNSW Index Sharding & Rebuild Cadence

Approach

HNSW (Hierarchical Navigable Small World) is the dominant production ANN algorithm because it achieves sub-linear query time via a layered proximity graph. The top layers are sparse long-range links for fast traversal; the bottom layer is a dense neighborhood graph for precision. At M=16 (max neighbors per node) and ef_construction=200 (search width during build), recall@10 of ~0.95 is achievable at ~1ms/query on a single CPU core^ⁱ (per Malkov & Yashunin 2018, Table 2). The operational challenge is not building the index — it is maintaining recall quality over time as the live corpus changes, and distributing query load across shards fairly.

Sharding strategy

Shard by item ID hash, not content cluster. Content-based sharding (e.g., by category or embedding cluster centroid) is tempting for locality but creates hot shards during viral events: all queries for the viral topic land on the shard whose centroid is nearest, saturating it while other shards sit idle. Hash-based sharding distributes items and queries uniformly in expectation.

• Hot/cold tiers:recent items (last 30 days) on GPU/DRAM hot shards; older items on CPU-RAM cold shards. The majority of real-time queries hit recent content — a viral pin from today, not a pin from 2019. The hot shard absorbs the latency-sensitive load; cold shards serve long-tail catalog queries at a more relaxed latency budget (<100ms vs. <30ms).
• Per-consumer shard replicas: each consumer owns a dedicated replica of each shard, with ef_search tuned to its recall target. Ads replica: ef_search=128 for 0.90 recall@5^ⁱ. Recsys replica: ef_search=64 for 0.75 recall@50. One consumer cannot saturate another's shard. This is the critical isolation invariant — a shared shard with a single ef_search must be set to the tightest SLO (ads), which over-serves recsys and wastes GPU cycles.

Rebuild cadence

HNSW is append-friendly: new items can be inserted online without a full rebuild. Deletions are the problem. HNSW does not support true node removal — deleted items remain as “tombstones” in the graph. Traversal still visits tombstone nodes, wasting ef_search budget on items that will never be returned. As tombstone rate climbs, recall degrades silently — the graph is intact, queries succeed, but a growing fraction of traversal steps are wasted on deleted items.

• Rebuild trigger:tombstone rate >10% of shard item count, OR recall@k on the golden query set drops more than 2pp from the post-build baseline. The tombstone rate is cheap to compute (item count delta); the recall check is expensive but catches drift that tombstone rate misses (e.g., distribution shift without deletion).
• Rebuild procedure: build new index offline from clean corpus (exclude tombstones), swap atomically via the dual-write layer, decommission old. Rebuild time scales with corpus size and M: at M=16, ef_construction=200, a 50M-item shard rebuilds in approximately 30–60 minutes on a 32-core CPU node (community estimate based on Weaviate HNSW benchmarks). Schedule rebuilds during off-peak windows; hot shards can serve from the old index during rebuild via the same dual-write swap mechanism used for model migrations.

Failure mode: hot shard during viral event

Even with hash-based partitioning, a viral event can overload a single shard if the viral content hashes disproportionately to one shard (hash collision clusters are rare but possible at scale), or if a flood of writes for viral items all arrive in a short window and the shard's write-lock serializes insertions. The manifestation: per-shard CPU climbs to 100%, query latency on that shard jumps from ~5ms to >200ms^ⁱ, while other shards look healthy. Aggregate P95 latency looks acceptable because it is diluted across shards — this is why aggregate metrics are insufficient.

Detection metric

Per-shard query latency P95, tracked per consumer per minute. Alert threshold: any shard P95 exceeds 3× its 7-day rolling baseline for more than 3 minutes. Secondary: per-shard CPU utilization alert at 80% sustained >5 minutes.

Mitigation

Shard-split: detect the hot shard, rehash its item ID range into two sub-shards (even/odd split), and use the backfill pipeline to populate both sub-shards within hours. The dual-write layer routes new writes to both sub-shards during the split. Secondary-effect callout: a shard split increases the total shard count, which increases the fan-out for scatter-gather queries — every query now touches more shards. Monitor per-query scatter-gather latency after a split; if fan-out cost exceeds the savings from load reduction, the split threshold was triggered too early and the alert threshold should be raised.

Real-world example

The Weaviate HNSW benchmark documents rebuild timing for HNSW at varying corpus sizes and M values. At M=16 on a 10M-vector dataset, full index rebuild completes in under 10 minutes on modern hardware, but at 100M vectors the build time grows super-linearly (graph construction is O(N log N)) and the rebuild window must be planned into the operational schedule — it cannot be triggered reactively during a production incident. The operational lesson: set tombstone-rate alerts at 8% (not 10%) so rebuilds are scheduled proactively, not triggered in the middle of peak traffic.