System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive)

This guide already has a traced solution for each of these five problems — Designing a Web Crawler, Designing Uber, Designing WhatsApp/Messenger, Designing Dropbox, Designing Typeahead, and Designing Search — plus a first resolution-mechanisms page (System Design Problems — The Recurring Resolution Mechanisms) that named seven cross-cutting fixes: reconciliation, watermarked read-time merge, leases with fencing tokens, compare-and-set booking, ordered-queue FCFS, 301-vs-302, and celebrity fan-out thresholds. Those traced pages are good at showing the happy path and naming where the hard part lives — but several of them name a mechanism and stop one layer short of how it actually works: the crawler page's cross-reference to bounded producer-consumer is a dead link stub, not an explanation; the chat page mentions a “user→connection map” without ever describing what happens to it when a gateway server dies; the Dropbox page shows chunk-hash-dedup but never confronts what happens to those hashes when you insert one byte near the start of the file. This page is that missing layer for five more problems: it does not repeat what the traced pages and Part I already cover well (driver-assignment concurrency, token-vs-leaky-bucket mechanics, and payment reconciliation are each covered in depth elsewhere and only cross-referenced here) — it resolves the mechanisms those pages left as an exercise for the reader, and supersedes the crawler page's intuition layer without editing that page.

Mechanism (adaptive re-crawl): the full derivation — modeling each page's edits as a Poisson process, estimating its change rate online via a shrink-on-change/extend-on-no-change backoff, and ranking the frontier by freshness value × P(changed) — is traced in depth on this guide's Web Crawler Freshness: Re-crawl Scheduling & Change Detection page; the one-line version worth repeating here is that crawl frequency should track a per-URL estimate of change rate, not a global constant — a news homepage and a static documentation page do not deserve the same clock, and a single global interval either starves the fast-changing page or wastes budget re-fetching the static one.

Mechanism (bounded frontier as back-pressure): the URL frontier is a producer-consumer queue at planetary scale — parser threads discover outlinks (the producer side) faster than politeness-limited fetchers can drain them (the consumer side) whenever a crawl hits a link-dense site (a forum, a calendar with infinite next-month links, a site with heavy cross-linking). If the frontier is unbounded, exactly the failure mode this guide's Back-Pressure Mechanisms page describes takes over: memory grows without limit as millions of low-priority URLs pile up behind a politeness rate-limit on one popular domain, and the crawler eventually OOMs on state it will get to in six months anyway. The fix is the same one that page teaches generically, applied here: cap the frontier's size per host and in aggregate, and when a bounded segment is full, don't block the whole crawl waiting for one domain to drain — drop (or defer to cold storage) the lowest-priority discovered URLs first, ranked by the same freshness-value × importance score the re-crawl scheduler already computes. A crawler is one of the rare systems where dropping a discovered URL is nearly free (a well-linked page will be rediscovered from another path before its priority score would have earned it a fetch slot anyway) — which is exactly why bounding the frontier and shedding low-value URLs is the correct choice, versus blocking, which would stall the whole worker pool behind one dense host's politeness limit.

Mechanism (edge cache-miss handling for URL dedup): the traced crawler page correctly names a sharded Bloom filter as the way "have I seen this URL?" stays cheap across billions of URLs and a distributed worker fleet — but a single canonical dedup store, even sharded, is still a network hop from every worker for every single discovered link, and most discovered links are not novel (the same nav-bar, footer, and pagination links repeat across thousands of pages on one site). Production crawlers add a second, local tier: each worker keeps a small edge cache — an LRU-bounded local Bloom filter or hash set of URLs it has recently seen — and checks it first, before ever contacting the canonical shard. A hit in the edge cache is resolved with zero network calls. A miss in the edge cache does not mean "definitely new" — it only means "not recently seen by this worker" — so a miss always falls through to the canonical sharded store, which is authoritative, before the URL is treated as genuinely new and enqueued. The edge cache trades a small false-miss rate (a URL this worker saw an hour ago has since aged out of its local LRU) for removing the canonical store's network round-trip from the common case, at the cost of one extra check on the canonical store's critical path whenever the local cache can't rule a URL out — the same asymmetric "cheap local check, authoritative fallback on miss" shape this page uses again for search index segments in §6.

Mechanism (atomic driver assignment): "two riders must never be matched to the same driver" is a read-modify-write race — two dispatchers both read "available," both write "assigned" — and this guide's Dispatch & Assignment: the double-booking race page traces all four fixes for it in depth (compare-and-set on a single row, pessimistic SELECT…FOR UPDATE, a reservation with a TTL for the seconds a driver spends deciding, and a distributed lock with a fencing token when the driver's state spans services) alongside the judgment call between them. That page is the full treatment; nothing here repeats it beyond the one line that matters for ride-hailing specifically: because a driver's accept/decline takes several real seconds, the correct default is the reservation-with-TTL pattern (mark the driver offered with an expiry, confirm with a second CAS on accept), not holding a row lock across a human decision.

Mechanism (hot-shard mitigation for a dense region): a geohash grid with uniform cell size turns a dense downtown-at-rush-hour region into a hot shard the same way a hash-partitioned key-value store gets a hot key — every driver-location write and every rider-match query for that one popular geohash prefix lands on whichever single shard owns it, while shards covering sparse suburbs sit nearly idle. Two mechanisms fix this, and they are not the same fix: (a) variable-precision cells — use a coarse (short) geohash prefix for sparse regions, where one cell can safely cover a wide area without overloading its shard, and a finer (longer) prefix for dense regions, splitting the busy area into many smaller cells so no single cell holds an outsized share of drivers or requests; this is exactly the density-adaptive subdivision a quadtree gives you for free, and a fixed-depth geohash grid does not. (b) Distributing a dense region's cells across shards — even after finer subdivision, don't place all of one busy district's sub-cells on one shard by naively range-partitioning on the geohash string's shared prefix (adjacent cells share a prefix, so a naive range-partition re-creates the hot shard one level down); instead assign cells to shards by hashing the full cell id (a form of consistent hashing over geo-cells, not over the geohash's sort order), so a dense district's dozens of sub-cells land spread across many shards instead of stacking back onto one. The two combine: split downtown into enough cells that no single cell is itself hot, then scatter those cells across the cluster so the shard boundary and the density boundary don't coincide.

Mechanism (disconnection/billing resilience): a trip that loses connectivity mid-ride — the driver's phone drops signal in a tunnel or dies — must still bill correctly, and "wait for the app to tell us the trip ended" is not a safe design because the app might never tell you again. The fix has the identical shape as the payment-reconciliation mechanism this guide's Part I resolution-mechanisms page traces for a stalled payment call: keep the trip's billing state durable and server-side, not derived only from a final client message. Concretely: the server, not the phone, is the source of truth for trip state — each GPS ping updates a durable trip_state record (route so far, elapsed time, last-known position, last-ping timestamp) written to a store that survives the app's connection dying; the fare is computed from that accumulated server-side trace, not from a single "trip complete" event the client sends at the end. When pings stop arriving, the trip does not hang forever waiting for a close event — a timeout-driven reconciliation job, structurally the same one Part I traces for payments, scans trips with no ping past a grace window (e.g. 90 seconds) and transitions them to a DISCONNECTED → RECONCILING state: it estimates the endpoint from the last known position plus expected route (or, if the driver's app later reconnects and flushes buffered pings it queued locally while offline, replays those to fill the gap before finalizing), computes the fare from best-available data, and only then marks the trip BILLED. The mechanism that generalizes: a client-driven "trip ended" event is a convenience, never the durability boundary — the durability boundary is the server's own accumulated state plus a reconciliation job that resolves the case a client message can't reach, which is silence.

Mechanism (burst-vs-smoothing, briefly): this guide's Rate Limiting Algorithms: Token Bucket vs Leaky Bucket page traces the full update rules and a from-scratch numeric example (capacity 10, refill 5/s, a burst of 20) showing that both algorithms admit the same 10 requests and reject the same 10 — the difference is entirely in when downstream sees them: a token bucket hands its admitted burst to downstream instantly, a leaky bucket trickles the same admitted requests out at a constant rate over 2 seconds. The one-line decision rule that page ends on: let the burst through when downstream can absorb it and legitimate clients spike (token bucket); erase the burst when downstream is fragile or fixed-capacity (leaky bucket).

Mechanism (fail-open vs fail-closed when the limiter backend is down): a centralized rate limiter almost always means a shared Redis instance holding the token/leaky-bucket state so the limit is enforced consistently across every app server — and that Redis instance is now a dependency the request path calls on every single request. When it becomes unreachable (network partition, Redis restart, an overloaded replica failing over), the limiter has exactly two ways to answer "can this request through?" when it genuinely cannot check: fail-open (treat "unknown" as "admit" — let every request through unchecked until Redis recovers) or fail-closed (treat "unknown" as "reject" — return 429/503 to everything until Redis recovers). Neither is universally correct, and the choice is a statement about which failure mode is cheaper for that specific endpoint: fail-open on a public API means a Redis outage instantly removes your only protection against abusive or runaway traffic at the exact moment you can least verify what's calling you — the outage that took down your rate limiter is frequently correlated with a traffic spike that made you need it in the first place. Fail-closed on that same endpoint means a Redis blip (a few seconds of a failover) turns into a full outage for every legitimate caller, converting a small infrastructure hiccup into a total availability incident for a control mechanism that exists to protect capacity, not to be the single point that removes all capacity. The mitigation that most production limiters actually reach for is neither pure extreme: keep each app server's last-known-good local state (an in-memory approximation of the bucket, refreshed on every successful Redis check) and fall back to a conservative local-only limiter derived from that snapshot for the duration of the outage — strict enough to still shed egregious abuse, loose enough not to reject all legitimate traffic, buying time until Redis recovers without betting the whole request path on one dependency's availability.

The judgment call, explicitly: fail-closed for endpoints where the limiter is a correctness/cost boundary (a paid third-party API you're billed per call for, a write path that can corrupt state under flood); fail-open (or the local-approximation middle ground) for endpoints where availability for legitimate users matters more than perfect enforcement during a rare, short outage (a public read API where the limiter's job is fairness, not survival) — and either way, alert loudly on the fallback path being active, because "the rate limiter is unenforced" or "the rate limiter is rejecting everything" are both incidents, not steady states.

Mechanism (connection-map failure/refresh): the traced WhatsApp/Messenger page correctly names a user → which-server/connection map as the routing layer that lets a sender's gateway find a recipient's live WebSocket — but that map is itself state that must survive a gateway server dying with hundreds of thousands of live connections attached to it. The mechanism: each gateway server periodically renews a short TTL entry in the shared connection-map store (e.g. user:U42 → gateway-7, expires in 30s, refreshed on a heartbeat well inside that window) for every connection it holds, rather than writing the mapping once at connect time and trusting it forever. When gateway-7 crashes, it stops renewing every entry it owned; those entries simply expire on their own TTL within the heartbeat window — no explicit cleanup process has to detect the crash and race to delete stale entries, which matters because detecting "is this server actually dead, or just slow?" reliably is its own hard problem this design sidesteps entirely. The affected clients' WebSocket connections drop (TCP itself notices the peer is gone), each client's own reconnect logic opens a new connection to a (likely different) gateway server, and that new gateway writes a fresh mapping entry — user:U42 → gateway-19 — overwriting the expired one. Any message for U42 sent in the gap between the crash and the client's reconnect finds either a stale mapping (which the TTL bounds to at most one heartbeat interval) or no mapping at all, and falls through to the same offline-delivery path (inbox queue + push notification) the traced page already uses for a genuinely offline recipient — a dead gateway and an offline phone look identical from the sender's side, which is precisely why this design doesn't need a special case for it.

Mechanism (ordering + dedup via per-conversation sequence numbers): the traced page flags "ordering & exactly-once feel" as a hard part without a mechanism; the standard fix is a monotonically increasing sequence number scoped to the conversation, not to the sender or a global clock. The sender (or a per-conversation sequencer service) attaches the next sequence number when a message is created; the recipient's client keeps last_seen_seq per conversation and applies three rules on receipt: seq == last_seen_seq + 1 → accept and render immediately, advance last_seen_seq; seq ≤ last_seen_seq → a duplicate (a retried delivery after an ack was lost in transit) — drop it silently, never re-render; seq > last_seen_seq + 1 → a gap (an earlier message is still in flight or was delayed) — hold the new message in a small out-of-order buffer and request or wait for the missing sequence numbers before rendering anything past the gap, so the UI never shows message 7 before message 6 arrives. This is the same causal-ordering shape as a TCP receive window applied at the application/conversation level instead of the byte-stream level, and it is what makes "exactly-once feel" achievable on top of a network that only offers at-least-once delivery: the sequence number, not the transport, is what makes a duplicate detectable and a gap visible.

Delivery guarantees: the honest guarantee a chat system offers end-to-end is at-least-once, not exactly-once — a message can be delivered twice (a client resends because its ack was lost, even though the server did receive the first copy) but the sequence-number dedup above collapses that into exactly-once as observed by the user. Combined with the online/offline split (push immediately over a live connection, store-and-forward via the inbox queue otherwise) and the sent/delivered/read receipt chain the traced page describes, the full stack is: at-least-once transport + idempotent sequence-based dedup + a durable per-user inbox for the offline case = an effectively-exactly-once, ordered experience built entirely from unreliable, at-least-once parts.

Mechanism: the traced Dropbox page already shows the payoff of chunk-hash-dedup — split a file into chunks, hash each, skip uploading any chunk whose hash the server has already seen — but it doesn't confront how the chunk boundaries themselves get chosen, and that choice is the entire mechanism. Fixed-size chunking (cut every N bytes — byte 0–4095 is chunk 1, 4096–8191 is chunk 2, and so on) is simple, but it ties every chunk boundary to an absolute byte offset in the file. The moment you insert or delete even one byte anywhere before the end — a single character typed at the top of a document — every boundary after that point shifts by the size of the edit. The chunker doesn't know an edit happened at a specific spot; it just re-slices at the same fixed offsets, which now fall in different places relative to the actual content, so every chunk from the edit point onward hashes to something the dedup store has never seen — a one-byte edit forces a full re-upload of the rest of the file, exactly defeating the point of chunking.

Content-defined chunking (CDC) fixes this by making the boundary a property of the bytes themselves, not their offset. A rolling hash (classically a Rabin fingerprint) is computed over a sliding window as the chunker scans the file; a boundary is declared at any position where the rolling hash matches a fixed pattern (e.g. its low 13 bits are all zero, which on random-ish data happens roughly every 2^13 = 8192 bytes on average, giving a target chunk size without a fixed one). Because the trigger condition depends only on the local window of bytes, not on how far into the file you are, inserting bytes earlier in the file does not move where a downstream trigger pattern occurs in the byte stream itself — the same sequence of bytes that triggered a boundary before the edit still triggers one after it, just at a shifted absolute offset that the chunker naturally re-finds by scanning content rather than counting bytes. Only the chunk(s) actually touching the edit change; everything after re-chunks identically to before and re-hashes to values already in the dedup store.

Traced, with real values — inserting 3 bytes near the start of a file with four content-defined chunks:

Both re-chunkings start from the same original file (chunks c1=a7, c2=b3, c3=f1, c4=9e). After 3 bytes are inserted near the very start: fixed-size chunking keeps its boundaries at the same byte offsets, so the content on both sides of every boundary has shifted by 3 bytes relative to what used to be there — all four chunks hash to new values (k2, m9, q4, r0) and the dedup store has never seen any of them, so all 4 re-upload. Content-defined chunking re-scans for the same rolling-hash trigger patterns: the pattern that used to sit at the end of c1 now sits 3 bytes later in the raw offset, but it's the same bytes in the same relative position to the edit, so the chunker finds it and closes c1 there — c1 alone changes (new hash k2, since the insert landed inside it). From that point on, the trigger pattern that used to end c1 is gone, but the trigger patterns for the c2/c3, c3/c4, and c4/end boundaries are all bytes that were never touched by the edit — the rolling hash finds them at exactly the same relative position in the untouched remainder of the file, so c2, c3, and c4 hash identically to before (b3, f1, 9e) and the dedup check against the existing store skips uploading all three. Net result for a 3-byte edit: fixed-size re-uploads 4 of 4 chunks; content-defined re-uploads 1 of 4 — and that ratio gets more lopsided, not less, the larger the file, because content-defined chunking's re-upload cost is bounded by the number of edits, not the file size.

The dedup mechanism, made explicit: after chunking (either way), each chunk is hashed (SHA-256 or similar) and the hash becomes its content address. Before uploading a chunk, the client asks the server (or checks a local cache of recently-uploaded hashes, the same edge-cache-then-canonical-check shape as §1's crawler dedup) "do you already have a chunk with this hash?" — if yes, skip the upload entirely and just record that hash in this file's chunk list; if no, upload it once. Because the address is a hash of content, not a path or a filename, two completely unrelated files that happen to share a chunk (the same boilerplate header in two documents, the same asset bundled into two app builds) store that chunk exactly once, globally, regardless of which files reference it — deduplication is a side effect of content-addressing, not a separate pass.

Mechanism (segment-visibility / near-real-time indexing): the traced Search page notes the index is "built/updated incrementally" with "segment merges (LSM-like)" but doesn't say when a newly-indexed document actually becomes searchable — and the answer is deliberately not "instantly." An inverted index (Lucene/Elasticsearch-style) is built as a sequence of immutable segments: new documents are appended to an in-memory buffer, and a periodic refresh (commonly every ~1 second by default) flushes that buffer into a new, immutable, searchable segment and swaps it into the set of segments a query scans. Between refreshes, a just-indexed document exists in the write buffer but is invisible to search — this is the deliberate seam that makes "near-real-time," not real-time, the honest claim: shortening the refresh interval makes documents visible sooner at the cost of creating many small segments faster (more segment-merge/compaction work, since small segments are periodically merged into larger ones to keep query-time segment-scanning cheap), so the refresh interval is a genuine latency-vs-write-amplification knob, not a free dial to turn to zero.

Mechanism (incremental update path for trending terms): the traced Typeahead page's precomputed top-K-per-trie-node design is deliberately read-optimized — ranking is computed offline from query logs and merged into the trie periodically — which is exactly wrong for a term that is suddenly trending right now (breaking news, a live event) if "periodically" means an hourly or daily batch job. The fix layered on top, without abandoning the precomputed trie: maintain a small, separate real-time counter layer — a sketch (a count-min sketch or simple decaying counters) keyed by recent query prefixes, updated synchronously as queries arrive, with old counts decayed on a short half-life (minutes, not hours) so a term's trending boost fades once the volume that earned it passes. At query time, a prefix's suggestions are ranked by blending the trie's stable, offline-computed popularity score with the real-time layer's current boost, rather than by either signal alone — the trie carries the long-term signal (what people generally search for this prefix), the real-time layer carries the short-term spike, and the periodic batch merge eventually folds a sustained spike into the trie itself once it's proven durable rather than a flash-in-the-pan.

Mechanism (Bloom-filter false-positive cost + mitigation, applied to segment skip): this guide's Bloom-filter pages already derive the sizing math and the canonical LSM-tree application (a per-SSTable filter skips a disk seek for keys that definitely aren't in that file); the identical shape applies to search segments — each segment can carry a Bloom filter over the terms it contains, so a query for a rare term skips scanning segments whose filter says "definitely not here" without ever touching their posting lists. The cost specific to this application: a false positive here doesn't return a wrong answer (the filter only ever gates whether a segment gets scanned at all; a false "maybe" just means that segment's actual posting list is checked and comes back empty) — so unlike a filter guarding a security decision, the failure mode is purely a wasted scan of one segment, not an incorrect result. The mitigation is therefore just the standard sizing trade-off: size each segment's filter for the false-positive rate that keeps wasted scans rare enough (the same m, k derivation as any Bloom filter), and rebuild the filter when a segment is merged into a larger one during compaction, since a stale filter sized for a smaller segment's term count drifts toward a worse false-positive rate as more terms accumulate.

Mechanism (tail-latency amplification of scatter-gather): the traced page's one-line warning — "scatter-gather latency = the slowest shard" — is worth deriving, because the effect is sharper than intuition suggests. If a query fans out to N shards and each shard independently answers within its own p99 latency with probability 0.99, the probability that all N shards answer within that same p99 window is 0.99^N, not 0.99 — because the query isn't done until the slowest of the N responds. At N=1, that's 99%, matching the per-shard p99 by definition. At N=100 shards (a common document-sharded index at scale), 0.99^100 ≈ 0.366: fewer than 4 in 10 queries complete within what any single shard would call its "99th-percentile" latency — the fan-out itself has manufactured a new, much worse effective tail out of shards that are each individually fast almost all of the time. This is exactly why the traced page's mention of hedged requests matters operationally, not just as a name to drop: sending a duplicate request to a second replica of whichever shard hasn't answered after, say, the median latency, and taking whichever copy answers first, converts one slow shard's rare GC pause or page fault from "this query now waits for the outlier" into "this query takes the fast path from the hedge instead."

Mechanism (why BM25/TF-IDF — the ranking derivation): relevance ranking starts from an intuition, then two corrections. The intuition: a term that appears many times in this document (term frequency, TF) matters more to that document's relevance for the query than a term appearing once; and a term that appears in only a few documents overall (a high inverse document frequency, IDF — conventionally log(N / df) for N total documents and df documents containing the term) is more informative for distinguishing relevant documents than a term like "the" that's in nearly every document and therefore tells you almost nothing. TF-IDF multiplies the two per term and sums across query terms: a document scores well when it repeats query terms that are also globally rare. BM25 corrects two failure modes of raw TF-IDF: (1) TF alone rewards a document linearly for repeating a term 50 times versus 5 times, but the tenth occurrence of a term tells you far less additional information than the second did — BM25 saturates TF with a term tf · (k1+1) / (tf + k1 · (…)) that flattens toward a ceiling as tf grows, tunable via k1 (typically ~1.2–2.0); (2) raw TF also silently favors long documents, which mechanically contain more term occurrences of everything without necessarily being more relevant — BM25 normalizes for document length against the average document length in the corpus (doclen / avgdoclen, weighted by a tunable b, typically ~0.75), so a term appearing twice in a 50-word snippet scores higher than the same raw count in a 5,000-word page.

Worked, with real numbers — scoring the query "system design" against a short document:

Quantity	Value	Where it comes from
Corpus size N	10,000 docs	given
Docs containing "system" (df)	4,000	given
Docs containing "design" (df)	500	given
IDF("system") = ln(N/df)	ln(10000/4000) = ln(2.5) ≈ 0.92	common; contributes little
IDF("design") = ln(N/df)	ln(10000/500) = ln(20) ≈ 3.00	rare; contributes much more per occurrence
tf("system") in doc D, tf("design") in doc D	3, and 2	given (raw counts in D)
doc D length / avg doc length	120 / 200 = 0.6	D is shorter than average — length-norm boosts it
BM25 term weight (k1=1.5, b=0.75), "system"	3·2.5 / (3 + 1.5·(1−0.75+0.75·0.6)) ≈ 7.5/4.05 ≈ 1.85	saturating TF component, length-normalized
BM25 term weight, "design"	2·2.5 / (2 + 1.5·(1−0.75+0.75·0.6)) ≈ 5.0/3.05 ≈ 1.64	fewer raw occurrences, but...
Score contribution: IDF × weight	"system": 0.92×1.85≈1.70 — "design": 3.00×1.64≈4.91	multiply each term's IDF by its saturated, length-normalized weight
BM25(D, "system design")	1.70 + 4.91 ≈ 6.61	sum across query terms

Read the result, not just the arithmetic: "design" occurred fewer times in D than "system" (2 vs 3) but contributes nearly three times the score, purely because it's rare across the corpus (IDF 3.00 vs 0.92) — this is the mechanism, not a coincidence: BM25 is explicitly built so a document's relevance is driven by matching rare, informative terms, saturated so that repeating a term doesn't linearly inflate the score, and normalized so a short, dense-on-topic document isn't out-scored by a long document that mentions the same terms only because it's long.

Mechanism (a weighted-count formula + the reconcile/drift mechanism for approximate counts): a displayed result count ("About 1,230,000 results") or a live "trending" volume is rarely computed by scanning every matching row on every request — at query volume, systems instead sample events at some rate r (e.g. log and count only 1 in every 100 query events, r = 0.01) and scale the sampled count back up: estimated_total = sampled_count × (1/r). Worked example: a trending-terms tracker samples 1% of search-query events (r = 0.01) and observes 340 sampled occurrences of a term in the last 5 minutes — the weighted estimate is 340 × (1/0.01) = 34,000 actual occurrences, computed from 100× less event volume than an exact count would require. This estimate necessarily drifts from ground truth — sampling variance means the true count could genuinely be 33,200 or 34,900 for the same underlying rate, and the drift compounds if the real-time sampled layer and an eventual exact batch recompute disagree at their boundary, which is the identical read-time-merge-plus-watermark problem this guide's Part I resolution-mechanisms page derives in full for a stats feed's real-time/batch split (the batch layer's watermark W marks how far its exact recompute has progressed; the sampled/real-time layer only contributes events after W). The reconciliation mechanism is the same one, applied here: periodically, an exact batch job recomputes the true count for a window that has fully closed, and the displayed value is swapped from the sampled estimate to the exact count for anything at or before the batch's watermark — so what the user sees is a live, admittedly-approximate number for "just now" that gets quietly corrected to exact once the batch catches up, rather than a number that is permanently wrong or one that requires exact counting at full query volume.

None of these five problems benefit from CP (strict consistency at the cost of availability) as a default stance, and the reasons differ just enough to be worth naming per-problem rather than citing CAP once and moving on. Crawler: the frontier and dedup store are AP by nature — a Bloom filter is already probabilistic (false positives are tolerated), and a stale or slightly-duplicated crawl of a page costs a wasted fetch, never a correctness incident; there is no case here for paying availability to get exactness. Ride-hailing: the single assignment decision (one driver, one rider) is the one place that must behave CP-like — hence the compare-and-set/lease mechanism, which is a targeted, single-row consistency guarantee, not a system-wide one; everything else (location updates, ETA estimates) is AP, tolerating a few seconds of staleness gladly in exchange for write throughput. Chat: delivery is AP with a correctness patch bolted on top — at-least-once transport (available under partition) plus sequence-number dedup (a cheap, local correctness fix) beats trying to make the transport itself exactly-once and strictly ordered, which would mean blocking message delivery on cross-region consensus for every message. File-sync: chunk storage is AP and idempotent by construction (content-addressing means a duplicate write of the same chunk is a no-op, so eventual convergence across replicas is safe without coordination) while the small amount of true per-file metadata (which chunk-list is the file's current version) is where any real consistency requirement concentrates, mirroring the lease/fencing-token pattern from Part I. Search: is explicitly PACELC's "else" branch in action even absent a partition — the segment-refresh interval is a live latency-vs-consistency trade a team tunes deliberately (shorter refresh = fresher results, more merge overhead; longer refresh = cheaper indexing, staler results) with no partition in sight, which is precisely the scenario PACELC adds on top of CAP to describe. Layered on top of all five, the tail-latency-under-fan-out derivation from §6 (p^N) applies unchanged to any of them that fans a single logical request across many shards or many drivers/candidates — ride matching's "query cell + 8 neighbors" and search's "query all N index shards" both pay the same tax, and hedged requests are the same fix in both places.

• Crawler: an unbounded frontier "to be safe" reproduces the exact OOM failure the bounded-queue back-pressure mechanism exists to prevent — bound it and shed low-priority URLs instead.
• Ride-hailing: splitting a hot geohash cell finer without also redistributing the resulting sub-cells across shards just recreates the hot shard one level down, because adjacent fine cells still share a prefix under naive range partitioning.
• Ride-hailing billing: treating the client's "trip ended" message as the only durability boundary means a dropped phone silently loses the ability to bill — the server-side accumulated trip state plus a reconciliation sweep is the actual boundary.
• Rate limiter: picking fail-open or fail-closed globally, once, for every endpoint is a category error — a payment-adjacent limiter and a public read-API limiter should not fail the same way.
• Chat: scoping the sequence number to the sender or a global clock instead of per-conversation breaks the ordering guarantee the moment two conversations interleave or two devices for the same user send concurrently.
• File-sync: assuming any chunking scheme dedups well against small edits — only content-defined chunking survives an insert/delete; fixed-size chunking degrades to "re-upload everything downstream of the edit."
• Search: expecting a document to be searchable the instant it's indexed contradicts how segment-based indexes actually work — there is always a refresh-interval seam, and shrinking it has a real merge-overhead cost, not a free lunch.
• Search: quoting a per-shard p99 as the system's overall latency ignores that scatter-gather across N shards manufactures a much worse effective tail (p^N) — the fix is hedged requests or fewer/larger shards, not wishing the math away.

Token bucket vs leaky bucket (recap of the decision, not the mechanics): reach for a token bucket when the endpoint's downstream can absorb a burst up to the bucket's capacity and legitimate clients are expected to spike (a public API quota) — you accept an instantaneous flood in exchange for never queueing a legitimate fast client. Reach for a leaky bucket when downstream is fragile, fixed-capacity, or itself rate-sensitive (a legacy backend, a partner's hard cap) — you accept queueing latency on the last-admitted request in exchange for downstream never seeing a spike larger than one request at a time. This guide's Rate Limiting Algorithms page has the full traced numbers; the fail-open/fail-closed choice in §3 above is the same kind of judgment call one layer up the stack, applied to what happens when the enforcement mechanism itself is unavailable rather than to which enforcement mechanism to run.

Fixed-size vs content-defined chunking: fixed-size chunking is simpler to implement (no rolling hash, no variable chunk sizes to account for in storage bookkeeping) and is the right choice when files are write-once/immutable or always replaced wholesale rather than edited in place (a build artifact, a video file uploaded once) — there's no small in-place edit for content-defined chunking to protect against, so its extra complexity buys nothing. Content-defined chunking earns its cost — a rolling hash computed over every byte scanned, and variable chunk sizes that complicate storage layout slightly — specifically for files that get small, localized edits over time while staying largely the same (documents, code repositories, VM disk images, database backups): the traced example in §5 shows the payoff directly, 1-of-4 chunks re-uploaded instead of 4-of-4 for the same one edit, and that ratio only improves as the file gets larger relative to the edit size. The decision reduces to one question: does this file get edited in place, or only replaced wholesale? Edited in place → content-defined chunking; replaced wholesale → fixed-size chunking is simpler and loses nothing.

• Most of these five problems' "hard parts" are one of a small set of recurring mechanisms wearing a different costume: bounded-queue back-pressure (crawler frontier), lease/CAS-style atomicity (driver assignment, chunk metadata), reconciliation against silence (payment timeouts and dropped-trip billing), and a two-tier cache-then-authoritative-check (crawler URL dedup, search segment skip).
• A mechanism that "names" a fix without describing how it behaves under failure (a connection map with no refresh story, a chunker with no boundary-shift story, a rate limiter with no story for when its own backend is down) is not yet a design — it's a label. The failure-mode behavior is usually where the actual engineering judgment lives.
• Fan-out (scatter-gather across search shards, querying a geo-cell's neighbors, broadcasting a ride offer to several drivers) always manufactures a worse effective tail latency than any single participant's own tail — p^N is the formula to reach for, and hedged requests are the standard mitigation, not a novelty.
• Content-defined chunking, per-conversation sequence numbers, and BM25's saturation-plus-length-normalization are three instances of the same higher-level move: make the mechanism a function of the content/position that actually matters (byte patterns, conversation-scoped order, term rarity) instead of a proxy that breaks under edits, concurrency, or document length.

Related pages

• Designing a Web Crawler — Frontier, Dedup & Politeness, Traced — System Design — the traced crawler page this section adds the missing back-pressure/dedup layer to
• Designing Uber — Geospatial Matching, Traced — System Design — the traced ride-hailing page this section's hot-shard and billing fixes extend
• Designing Search — The Inverted Index, Traced — System Design — the traced search page this section's segment-refresh and BM25 mechanisms extend
• Bloom Filters — How They Work (Examples & Sizing) — System Design — sizing math behind the crawler dedup filter and the search segment-skip filter
• System Design Problems — The Recurring Resolution Mechanisms (Deep Dive) — System Design — Part I of this two-part resolution-mechanisms series

I just read a lesson on **System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive)** (System Design) and want to truly understand it. Explain System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **System Design Problems II — Crawler, Ride-Hailing, Chat, File-Sync & Search: Resolution Mechanisms (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.