Why we built Chrono

Dropbox's metadata teams have spent years improving the foundational storage layer. Building an incrementally scalable key-value store avoided doubling hardware as we grew. But growth projections showed that soon the volume of read queries per second (QPS) would outpace what the storage machines could sustainably serve. Caching was the natural answer — but not a straightforward one.

Internal clients of Dropbox metadata depend on a read-after-write guarantee: after a successful write to a key, an immediate read of that key (with no intervening writes) must return the just-written value, never something stale. Weakening that guarantee would force a costly audit and rewrite across every client team. Traditional caching approaches fail this test. We needed a cache that is both scalable and consistent. The result is Chrono, a caching system built on top of Panda, our key-value storage system. Chrono serves high-volume read traffic while enabling linearizable reads via Panda followers, which also unlocks new high-throughput metadata workloads for search and AI.

Why consistent caching is hard

Transparent caching at the database layer doesn't provide read-after-write guarantees by default. Write-then-cache ordering can leave stale data if the coordinating server crashes between the storage write and the cache update. Even simple cache pre-invalidation fails. Consider key K holding value v1 in both storage and cache:

  • A writer invalidates the cache for K, then attempts to write K=v2.
  • Reader 1 misses the cache, reads v1 from storage.
  • The writer completes the storage write.
  • Reader 2 misses the cache, reads v2 from storage, and populates the cache with K=v2.
  • Reader 1 then populates the cache with K=v1 — stale relative to storage.

Panda APIs that make Chrono possible

Panda is a multi-version concurrency control (MVCC) store. Every successful write gets a commit timestamp, and every record is tied to the timestamp of the write that created it. Commit timestamps for a given key strictly increase with successive writes. Clients can read at a specific snapshot timestamp. Three APIs are essential:

  • Write: Write(keys, values, maxPermittedCommitTimestamp) -> commitTimestamp. The client supplies keys and values; if Panda's chosen commit timestamp exceeds the optional maxPermittedCommitTimestamp, the write fails.
  • Snapshot read: Get(key(s), readTimestamp) -> record(s). Reads the value at a specific point in time. Sufficiently old timestamps allow reads to be served by Panda followers.
  • GetLatest: GetLatest(key(s)) -> (record(s), readTimestamp). Returns the latest records at a transactionally consistent point in time, along with that read timestamp. The returned timestamp is always greater than or equal to the commit timestamps of the returned records. Any write that linearizes after this call gets a strictly greater commit timestamp.

GetLatest aims to return the highest correct read timestamp, generally close to real time. Two GetLatest calls minutes apart — with no intervening write — return the same record and commit timestamp but a fresher read timestamp the second time. Reusing that read timestamp in a snapshot read yields identical records.

Chrono at a glance

Chrono reports the latest write attempt timestamp for every key in the storage system. It exposes two APIs:

  • Attempt(key, attempt_ts) — A client must notify Chrono before writing to Panda. The attempt_ts becomes the maxPermittedCommitTimestamp for the subsequent write. A reasonable choice is Now() + 5s: far enough ahead that the write won't fail, near enough that caching isn't blocked too long. Loose clock synchronization only affects liveness, not safety.
  • LatestAttemptTimestamp(key) -> ts — Returns an upper bound on the highest observed attempt timestamp for the key.

Chrono doesn't store value data — that's left to a lossy, possibly stale key-value cache such as Memcache or Redis. To keep LatestAttemptTimestamp monotonic even across crashes and restarts, Chrono persists and periodically advances an upper bound timestamp in storage (Panda). An Attempt() with a timestamp above the persisted bound fails. On restart, Chrono returns the persisted bound as its minimum, ensuring timestamps never regress.

Architecture and scaling

Two components work together:

  • Chrono Server: handles the two APIs above. It manages lifecycle (bootstrap and readiness) and keeps a timestamp table mapping keys to the highest observed attempt timestamp. The table hashes keys into slots; each slot stores a single value for all keys in that equivalence class. This aliasing slightly inflates timestamps but strictly bounds memory usage.
  • Memcache: holds the key → <readTS, value> mapping.

Decoupling the data cache from write-attempt tracking means each can scale independently. Low cache hit rates from insufficient memory are fixed by scaling Memcache without touching Chrono. Both systems are sharded and horizontally scalable in practice, each with its own dedicated box in the architecture diagram.

Read and write paths through Chrono

Chrono's protocol lets any client, like Edgestore, coordinate with Chrono, Memcache, and Panda to serve consistent cached reads. The write path is:

  1. The client picks an attempt_ts slightly above time.Now() — accounting for clock skew and network latency — and calls Attempt(key, attempt_ts). This must succeed before continuing.
  2. The client commits to Panda with Write(key, value, maxPermittedCommitTimestamp=attempt_ts).

The read path begins with two parallel lookups. The client calls LatestAttemptTimestamp(key) for LatestAttemptTS and Memcache.Get(key). If Memcache returns a value, the client checks freshness by comparing the Memcache entry's readTS against LatestAttemptTS. A fresh cache hit serves the value directly. On a miss or stale cache:

  1. Send GetLatest(key) to storage to get a fresh (val, readTS) pair.
  2. Populate (key, readTS, val) into Memcache.

A concrete walkthrough

  1. A client writing key K with value val calls chrono.Attempt(K, attempt_ts=10), expecting the commit timestamp to stay at or below 10.
  2. The client writes with Write(K, val, maxPermittedCommitTimestamp=10).
  3. Storage commits the write, responding with commit timestamp 9.
  4. A read for K queries Chrono — getting LatestAttemptTimestamp(K)=10 — and Memcache, which misses.
  5. The client calls storage.GetLatest(K), receiving val and readTS=11, then stores K → val, readTS=11 in Memcache.
  6. The next read compares the Memcache readTS=11 against Chrono's LatestAttemptTimestamp(K)=10. Since 11 > 10, the Memcache value is fresh and served directly.

Even on a Memcache miss, clients can issue a snapshot read at a timestamp at least as high as Chrono's LatestAttemptTimestamp. That guarantees observation of all linearized prior writes, and because most reads target recently written keys, significant traffic shifts from Panda leaders to followers.

Why the cache stays correct

Chrono's consistency guarantee rests on two invariants around every write to a key K in Panda:

  1. Before a write with commit timestamp T_commit succeeds, Chrono must have received a successful Attempt(K, T_attempt) call where T_commit <= T_attempt, enforced via maxPermittedCommitTimestamp.
  2. If LatestAttemptTimestamp(K) is called after some successful attempt, the returned value is at least that attempt's T_attempt.

With those two facts, consider a key K in Memcache carrying a value (or tombstone) and a read timestamp T_read. If a client read for K observes T_read >= LatestAttemptTimestamp(K), the cached value can be served. The proof is by contradiction: if the cached value were stale, a newer write with commit timestamp T_commit_newer > T_read would have been linearized before the read. That write would have required a prior successful Attempt(K, T_attempt_newer) with T_commit_newer <= T_attempt_newer. The read's LatestAttemptTimestamp(K) call would then return a value at least as high as T_attempt_newer, meaning LatestAttemptTimestamp(K) >= T_attempt_newer >= T_commit_newer > T_read. That contradicts the condition needed to serve from cache, so no such newer write can exist.

Verification approach

The team used TLA+, a formal specification language for concurrent systems, to model and verify the caching protocol's design. Formal modeling alone, however, does not guarantee a correct implementation. To close that gap, the team also built self-checking workloads and verifiers that continuously test internal invariants and read-after-write behavior in both stage and production environments when reads are served from cache.

What the project taught us

  • Strong semantics carry a cost. Read-after-write guarantees are expensive; clients should be steered toward tolerating slight staleness from the start. The tradeoff between ease of development and platform sustainability favors not offering strong guarantees unless clients truly need them.
  • TLA+ helps but has limits. The model proved correctness during the design phase, but incorrect environment assumptions or unmodeled startup sequences can still hide bugs. An earlier protocol iteration had a buggy startup sequence that the steady-state model missed; it was caught only through human inspection, and modeling the startup sequence afterward quickly exposed the invariant violation.
  • Operational scale is the real bottleneck. Most engineering effort went into sharded-system operational issues rather than Chrono itself: designing a sharding scheme that bundles Memcache requests to reduce fanout and latency, and debugging and mitigating hot spots in Chrono and Memcache pods.