An eventually consistent cache has two distinct failure modes. It can return an older value, and it can leave the caller unable to tell how old that value might be. The second problem moves complexity into every product. A developer adds retries, a distributed state machine assumes an update has arrived, or an asynchronous action overloads itself while polling for data that is still crossing regions.
Meta encountered this at the scale of millions of database shards and billions of read queries per second. TAO caches social-graph data in many regions, while an ordered pub-sub system named Wormhole propagates database changes. The pipeline provides durable, at-least-once, in-order delivery. Those guarantees are valuable, but one hot shard, overloaded publisher, or missing segment can delay all later entries behind it. Average lag can remain low while the long tail has no useful bound[1].
Skybridge adds a second replication path with a narrower job. It does not carry changed objects or replace Wormhole. It carries enough metadata to answer one question: did this cache key receive a recent write that the local cache may not have seen? That separation lets the primary stream optimize for durability and ordered recovery while Skybridge optimizes for timely evidence.
A freshness proof needs key-level evidence
TAO already attaches hybrid logical clocks (HLCs) to committed writes. MySQL advances an HLC for each shard, and Wormhole injects a heartbeat about every 500 milliseconds. A cache host can compare its replication watermark with the current time. If the watermark is newer than the two-second threshold, everything before that watermark has arrived and the local entry can be considered fresh.
The difficult case is a lagging watermark. Declaring every key on the shard stale is safe but expensive. Read traffic is skewed, so most cached objects have not changed during the missing interval. Refilling all of them turns a cache into a cross-region proxy, adds latency, creates a thundering herd toward the database, and can worsen the original lag.
Skybridge acts as a fine-grained staleness oracle. When the ordinary watermark cannot prove freshness, TAO asks whether the requested key appears among recent writes. A negative answer proves that the old-looking cache entry did not change. A positive answer provides the latest HLC so TAO can fetch an adequate version from its upstream path. The system therefore spends expensive refill capacity on the small subset of keys that may actually be stale.
This is not a second database. Skybridge retains key and HLC pairs, not values. Last-write-wins merging is sufficient because the cache only needs the newest known version for a key. The payload reduction is central to its footprint and replication latency.
Replication with gap detection changes the contract
The paper calls the weaker stream semantic replication with gap detection (RGD). It accepts out-of-order delivery and even data loss, provided loss is reliably visible. If Skybridge knows that an interval is incomplete, it returns an indeterminate result. TAO can then conservatively refill or, for a fail-closed request, return an error. Correctness depends on never reporting “no recent write” when the corresponding interval is silently missing.
Allowing disorder removes head-of-line blocking. Recent metadata can pass an older unavailable window because the stored tuples form an add-only set: insertion is idempotent, associative, and commutative. Duplicate delivery is harmless and arrival order does not affect the final set. The read path selects the maximum HLC for a key.
Gap detection starts at the writers. TAO writers use leases to establish which processes may write each shard and send heartbeats that close bounded windows. Skybridge can call a window complete only when it has evidence from every relevant lease holder. A missing heartbeat, writer crash, or lost batch leaves an explicit gap. Downstream replicas may fetch windows from several write-path or read-path peers, prioritize the newest metadata, and abandon an unavailable old window without pretending that it was complete.
The independence of the two paths matters. A fast side channel that shares the same publisher queues and recovery barriers as the main stream would suffer correlated lag. Skybridge instead takes metadata from the TAO write path and uses a separate replication topology. The durable path remains the source of object contents and eventual repair; the fast path supplies bounded, conservative evidence.
Local filters keep the oracle off the critical path
Calling a network service for every TAO read would merely move the bottleneck. Skybridge continuously publishes compact bloom filters of recent writes to TAO hosts. A lagging cache reader first checks its ordinary watermark and cached item HLC. If that is insufficient, a negative bloom-filter result can prove the key absent from the recent-write set with no extra network hop. Only possible matches require an in-region getWrites request.
The filter may return a false positive, but not a false negative for a complete interval. A false positive causes an unnecessary query; a false negative could expose stale data and is therefore excluded by construction. If the filter stream is incomplete, TAO does not use it as proof. This ordering converts the common case into host-local arithmetic and preserves a conservative escape path for uncertainty.
Memory usage sets the retention interval. Skybridge keeps a baseline history for all shards and extends retention selectively when repeated TAO requests show that one shard is approaching the limit. The production deployment retained roughly 93 to 109 seconds of writes as traffic varied. Shards lagging for several minutes eventually fall outside that window and require the ordinary upstream path.
The production result is a tail result
Meta measured the system for seven days across tens of regions. Without Skybridge, TAO provided two-second consistency for 99.993% of sampled checks and sometimes fell below 99.985%. Best-effort reads with Skybridge reached 99.9993%. Fail-closed reads, which return an error instead of serving data when the bound cannot be established, reached 99.99998%. At billions of reads, the remaining fraction still represents requests and therefore cannot be rounded away.
The filtering path is equally important. Wormhole watermarks alone proved 99.96% of reads current. Adding host-local bloom filters raised that value to 99.98%, eliminating tens of millions of potential queries each second. Including in-region Skybridge lookups proved 99.9996% current, so only 0.0004% needed an upstream freshness fetch.
Skybridge measured roughly 700 milliseconds at P99 replication lag; apart from several spikes, P99.99 remained around 1.5 seconds. A tier consumed 4.8 to 7.9 GB/s to ingest metadata for all committed writes, compared with 170 to 300 GB/s for Wormhole’s full stream into TAO. The complete Skybridge and lease system used 0.54% of TAO’s server footprint.
These numbers do not mean Skybridge makes TAO linearizable by default. Best-effort reads fail open when protective rate limits trip. A caller needing a hard contract can request fail-closed behavior and accept an error when freshness cannot be proven. Meta also offers a pattern that waits for the two-second interval before issuing such a read, approximating a primary-only or causal check without directing normal traffic to the primary database.
Overload control is part of consistency
A freshness mechanism can create its own metastable failure. If incomplete windows trigger many getWrites calls, those calls compete with replication and filter publishing. Slower replication then creates more incomplete windows and more calls. Skybridge gives replication the highest priority, bloom-filter delivery the next priority, and queries the lowest. Re-fetch traffic is rate-limited so recovery work cannot starve the evidence needed to exit the degraded state.
TAO also uses circuit breakers. Too many lease waits or expensive consistency checks cause default traffic to fail open, protecting latency and availability. Fail-closed requests reserve part of the capacity budget. This distinction makes the service contract explicit: the system can provide a strong answer for selected calls without allowing all readers to overload the database during a wide replication incident.
Operational bugs appeared in the lease plane as well. A misrouted TAO release caused writers to open unexpected leases, defeated delta compression, and overloaded the lease backend. Rate limits on lease changes prevented that control-plane surge from turning every downstream window incomplete. The lesson is that metadata is smaller than data, but it still needs admission control and priority isolation.
Clock uncertainty remains in the proof. Meta uses NTP and advances the effective threshold by 50 milliseconds to account for skew. If real skew exceeds the assumed margin, a physical-time freshness claim can be violated. More precise synchronization or a larger safety allowance changes the attainable bound.
Where the pattern applies
Skybridge works because the cache has an authoritative refill path, writes have comparable versions, and missing metadata can be detected. A system without one of those properties cannot copy the design by adding a bloom filter. Dynamic shard movement also requires the lease and gap protocol to coordinate with the resharding control plane. Global secondary indexes are harder because one result may depend on writes from millions of source shards and repair is not a single-key refill.
The reusable design point lies between eventual and synchronous replication. Keep the durable stream for truth, add an independent compact stream for recent-change evidence, and let uncertain reads fall back conservatively. The weaker stream becomes useful precisely because its weakness is observable. It may lose or reorder metadata, but it cannot silently turn an unknown interval into a freshness proof.
For operators, the meaningful dashboard is not average replication lag. It combines the fraction proven by watermarks, filters, and remote checks; fail-open and fail-closed rates; retention coverage; upstream refill pressure; clock-skew margin; and replication percentile. Those measurements show whether the two-second contract is being met and whether the mechanism is approaching the feedback loop that could break it.
Skybridge demonstrates that consistency can be strengthened without making every cache read synchronous. The cost is a second control system whose gaps, leases, retention, priorities, and clocks must be engineered as carefully as the data path. At Meta’s scale, that control system converts an unbounded promise into a two-second operational contract for nearly all reads.
Source and copyright notice
This article is an editorial analysis by Silicon & Systems. It restates the architecture, measurements, and limitations in our own words. No source sentence, table, or figure is reproduced; the figure was created for this article. The paper is available from the USENIX OSDI 2025 presentation page. Copyright remains with the authors, 2025.