Bringing atomicity beyond a single shard
Edgestore, Dropbox’s metadata storage system, is built on thousands of MySQL nodes and exposes strongly consistent, transactional operations to application developers. Its core abstraction is the colo, a logical grouping of data items that are stored on the same physical shard. Reads and writes within a colo get full transactional guarantees at low latency.
But not every access pattern fits neatly into a colo. For example, if two users share content, the relationship between them and the shared items is inherently spread across shards—each user’s data lives on a different physical node. While applications could be designed around this limitation by manually coordinating at the application layer, it added friction and technical debt for those developers.
Dropbox has since deployed cross-shard transactions in Edgestore, enabling atomic operations across colos. The feature is now serving live traffic at over ten million requests per second. The implementation is based on two-phase commit with several key modifications to make it practical for a service operating at that scale.
A modified two-phase commit
The canonical protocol for distributed transactions is two-phase commit, which coordinates a leader and multiple participants—here, Edgestore shards. Dropbox extended it with an external transaction record. The modified flow looks like this:
- Transaction record. The leader durably writes a record indicating the start of a cross-shard transaction.
- Commit staging. Each participant durably records its willingness to commit and notifies the leader. Participants have not yet observed the final decision and must filter their reads to avoid exposing uncommitted state.
- Transaction decision. Once all participants have responded, the leader updates the transaction record to mark it committed—or aborted if any participant fails or times out.
- Commit application. The leader tells participants the final decision, and participants apply the changes (or discard staged state on abort).
Phase 0 and Phase 2a are additions to the classic protocol. They make the decision point explicit and centralized. Any concurrent operation can abort the transaction until the record leaves its pending state. This simplifies recovery: if the leader fails, the transaction is simply aborted, without the need to contact every participant to resolve an ambiguous state. It also improves latency for filtering, since a client can check a single node for the transaction’s state.
Three practical hurdles
Two-phase commit is conceptually straightforward but heavy to implement. Three problems dominate:
- How to determine transaction state efficiently.
- How to limit the write amplification from staging and applying commits.
- How to minimize the filtering cost for ordinary reads.
Centralized transaction state
Storing the transaction record as an ordinary Edgestore object solved the first problem. Because the record lives on a single shard and inherits Edgestore’s strong consistency, a concurrent request only needs to contact that one node to know whether a transaction is pending, committed, or aborted. The worst case for filtering is now two nodes: the local participant and the node hosting the record. The record can even be collocated with one of the participants.
Copy-on-write staging
Staging a commit in a naive way—by materializing a full copy of the modified data—would double write costs. Edgestore’s MySQL schema does not have native support for storing duplicate versions of an object, so a side table with full object copies would need to be written during staging and then copied back into the primary tables on apply. Dropbox avoided that entirely.
Instead, mutations are written to a separate staging table, and the primary tables are only updated once the commit is applied. This copy-on-write approach cuts write amplification by up to 95% compared to materializing full copies upfront.
Cheap reads in the common case
Filtering is the read-side cost of ensuring a client does not observe data tied to an incomplete transaction. In a typical steady state, few records have in-flight mutations. The staging table tends to stay small—roughly proportional to the current cross-shard transaction load—so it fits in memory. A read incurs only a local existence check against that table and can be served from the same node. Only when a staged commit is present must the reader wait for or assist in applying it, at which point it contacts at most one other node.
Proving correctness before going live
Validating a design on paper is one thing; proving it holds up in a system that has backed Dropbox traffic for years is another. Because Edgestore underpins almost every request, the rollout strategy had to verify consistency, correctness, and performance assumptions without risking live data. That meant building two separate validation tracks: an offline harness for formal consistency guarantees, and a production shadowing mechanism to test the implementation under real load.
The offline consistency harness
The central promise of this project was cross-shard transactions that are atomic and strictly serializable. To prove that to ourselves, we built an offline test harness that ran continuously in our build environment — consuming multiple years of CPU time — to catch any violations of those guarantees.
The harness works from a simple theoretical foundation. Given a complete history of all mutations, you can construct a precedence graph: create a node for each transaction and draw a directed edge from one transaction to another if it performs an operation on shared data before the other does. If the graph has a cycle, serializability is violated; a valid serial ordering exists only when the graph is acyclic.
To extend this to atomicity, the harness replaces transaction nodes with nodes for each participant in the transaction. If each participant's stored mutations encode information about the other participants — as directed edges radiating outward — then the subgraph for any single transaction should form a complete, directed graph. Missing or dangling edges signal an atomicity violation.
We implemented the harness by adding two fields to special Edgestore objects: one holding the transaction identifier (populated by introspecting RPC headers) to supply the directed edges, and another for the expected participant list. A test client issued transactions across random subsets of these objects while updating both fields. Application-level multiversioning preserved the full mutation history for later analysis, and random fault injection was layered in to broaden coverage of error paths. Read-only threads with extra logic were added to check the strict portion of the strict serializability guarantee.
The effort unearthed several bugs, ranging from a dropped error to a subtle flaw in the read filtering protocol — issues that would have been nearly impossible to root-cause outside a simulated environment. It was expensive in CPU time, but it paid off.
Shadow validation in production
Consistency verification ran in parallel with two other checks: whether the copy-on-write implementation correctly materialized transactions and whether two-phase commit inlined into Edgestore would maintain acceptable latency and lock behavior. Both questions were critical — a faulty materialization path could leave commit application unable to reconstruct user write APIs, and any major performance regression could destabilize upstream applications.
The key insight was to repurpose two-phase commit itself for validation. In a modified "validation" version of the protocol, the commit staging phase performs the shadow write and immediately deletes the staged commit as part of the existing Edgestore API's own transaction, without ever communicating back to the leader. The commit application phase becomes a no-op because the data is already written and unstaged. Read filtering checks for shadow transactions but discards the result since the transaction is already committed.
This approach achieved two goals at once. Externally, transaction semantics were unchanged, so client behavior was identical. Internally, Edgestore experienced the full extra coordination and lock load of a two-phase commit, letting us measure real performance impact without user-facing risk. Traffic doing pseudo-two-phase commits could also be increased gradually in a controlled manner.
The validation protocol also served as a correctness oracle for the shadow representation. Because the modified commit staging wrote a MySQL transaction that contained both the original API result and the shadow representation, the two could be pulled atomically from the MySQL binary log and compared. Any mismatch between the conversion of the original data and the shadow would expose a bug. This process identified several existing API features that were incompatible with cross-shard transactions, allowing the gaps to be fixed before the new protocol went live.
Where two-phase commit fits — and where it doesn't
Two-phase commit worked well for Edgestore partly because of pre-existing characteristics that may not generalize. The data was already well-collocated, so true cross-shard transactions were actually rare — only 5-10% of all Edgestore transactions touched more than one shard. If that fraction were higher, upstream applications might not have tolerated the added latency and lock contention. In many cases, cross-shard transactions also replaced more expensive application-level protocols, making the change a net performance win while simplifying developer logic.
Read filtration overhead was also mitigated by Edgestore's strongly-consistent caching layer, which absorbs more than 95% of client reads. Systems without such a cache, or those optimized for simpler write patterns, may find two-phase commit unwieldy. Storage-level multiversioning or consistency abstractions in an intermediary service layer between clients and the storage engine may be better alternatives — a direction our team is exploring for the next-generation metadata store, built as a simple key-value primitive with a suite of metadata services on top offering varying consistency levels and developer control.
A scalable transactional primitive, retrofitted
For a strongly consistent, distributed metadata store serving 10 million requests per second across multiple petabytes of metadata, writes spanning physical storage nodes are unavoidable. Dropbox's original best-effort approach to multi-shard writes shifted too much complexity onto application developers, so the engineering team built cross-shard transactions instead. The underlying protocol is not new, but retrofitting it into a production system required creative implementation and validation strategies. The up-front diligence made it possible to evolve a core system while preserving safety standards for user data.
