Alki, or how we learned to stop worrying and love cold metadata

A Metadata Store That Skips the SSD Tax

Dropbox’s product metadata has long lived in Edgestore, an in-house database built on MySQL with SSDs. Edgestore serves single-object reads with low latency and high throughput, but its architecture has scaling limits that become increasingly expensive to push against. As data grows, the system must be split into ever more clusters, and each split doubles the physical footprint of the entire fleet. Edgestore is also sharded across a fixed set of MySQL databases, with clusters serving subsets of those shards via a primary host and secondary replicas.

By late 2017, Edgestore had been split from 256 clusters with 8 shards per cluster into 512 clusters with 4 shards per cluster. That move grew the fleet from roughly 1,500 to over 3,000 database hosts, counting local and geo-diverse replicas. Capacity projections suggested another split would be required in under two years, driven by growth from new products and Dropbox’s own expansion.

The problem was not just cost; it was logistics. Each split requires buying and installing a massive number of machines, pulling in hardware, datacenter, networking, and database teams. And Edgestore’s architecture only permits two more splits before reaching one shard per cluster, at which point no further expansion is possible. The team was heading toward a capacity crunch.

Several options were considered to avoid the next split. A replacement storage engine called Panda, which would support incremental capacity expansion, was in the works underneath Edgestore. But building, validating, and migrating to it would take multiple engineer-years. Other ideas, like compressing the data model, switching from InnoDB to MyRocks, upgrading MySQL to 5.7 for hole punching, or running MySQL on zfs, were explored. The team deemed most of these too risky or too hard to validate safely across a large fleet. Schema tweaks offered only modest gains at the cost of long-term maintainability.

Audit Logs Were the Real Driver

Examining what actually sat in Edgestore made the path forward clearer. The largest dataset by far was customer audit logs, which power features that give Dropbox Business admins visibility into how their data is used and shared. These logs support search via insights dashboards, event subscriptions through the get_events API, and activity report generation.

Writes to audit logs are high-volume, and the data is retained for years. But the access pattern changes sharply with age. Recent events are read randomly and frequently; old events are rarely read at all, and when they are, they tend to be accessed as large sequential batches. Edgestore, optimized for random single-object reads, was never a good fit for that second pattern. The SSDs underneath, with their performance mostly unused, made storage costly. Worse, large teams generating high event volumes created write contention that hit MySQL throughput limits.

A two-tier design emerged as the answer. Data would land in a hot storage tier optimized for random reads and writes. Over time, it would move to a cold tier built for low cost and efficient sequential reads, accepting slower random access.

Why Not Off-the-Shelf?

The team examined HBase and Cassandra running on spinning disks. In principle, either could work, but operating either at scale with high durability was not something the team could master and tool up for in the available time. Off-the-shelf systems optimized for cold data also tended to handle high volumes of random reads and writes poorly, which is precisely what audit logs need right after ingestion.

Those constraints shaped the design of Alki: a generic metadata store that could serve more than audit logs, built quickly with limited resources, and deployed in a short timeline. The team wanted to reduce metadata storage costs while avoiding the next expensive split of Edgestore.

A Two-Tier Storage Design

Rather than searching for one system that could serve both fast, frequent access and cheap, infrequent access, Alki combines two storage technologies with complementary strengths. The architecture mirrors a log-structured merge-tree (LSM tree): a hot tier handles high-throughput random writes and reads, while a cold tier provides inexpensive capacity. In Alki, those tiers are Amazon DynamoDB and Amazon S3, with the control plane orchestrated by AWS Step Functions and Dropbox's Blackbird batch processing system.

LSM Tree Mechanics

LSM-tree storage is a well-established pattern, underlying systems like Cassandra, HBase, and BigTable. Its core idea is to append new writes to an in-memory sorted table (often a red-black tree), which can be searched and updated in logarithmic time.

Memory is limited and volatile, so the in-memory table is periodically flushed to disk as a sorted run of records. Over time, many such runs accumulate on disk, complicating reads: a lookup must search the in-memory table and every on-disk run whose key range might contain the target, then merge the results. For example, finding a key like Blackberry might require checking runs spanning <Apple,...Tomato> and <Banana,...Zucchini> but not <Chard,...Watermelon>, since the key falls outside that run's range.

As runs multiply, so does read amplification, since each lookup must scan more runs. To counter this, compaction merges smaller runs into larger ones, in a process similar to the merge phase of a merge sort. One simple approach — merging everything into a single global run — would be inefficient, since each new flush would require rewriting the entire data set. Instead, a logarithmic compaction scheme (e.g., merging every two small runs into one medium run, every two medium runs into one large run, and so on) keeps the number of runs bounded logarithmically, balancing write amplification from compaction against read amplification from too many runs.

Alki's Architecture

The key trick of LSM trees is leveraging multiple storage tiers: a hot tier with fast, random access (and correspondingly higher cost) and a cold tier with cheap capacity but slower I/O, where reading or writing 10 MB costs about the same as 1 KB. Alki applies this to cloud storage, using DynamoDB as the hot store and S3 as the cold store, with Step Functions and Blackbird handling orchestration and offline ETL.

Daily Lifecycle

At the start of each day, Alki dynamically creates a DynamoDB table to serve as the active hot run. Writes accumulate there until the end of the day, when the run is sealed and offloaded to S3 as a sorted cold run, after which the hot table is deleted. Cold runs are periodically compacted in the background to reduce their total number.

Typical LSM implementations store data on disk in an indexed file format (like SSTable), where an index maps keys to data offsets. A naive blob-store version of this would require multiple reads per lookup. Alki instead keeps the index in the hot store as internal metadata. Since the index itself can grow large depending on the key-to-value size ratio, records are batched into blobs and the index stores only a sparse mapping: one key per blob, corresponding to the first record in that blob. A lookup finds the last index entry with a key less than or equal to the requested key, then reads that blob (which may or may not contain the target). This trades storage cost against the possibility of unnecessary blob reads.

Why AWS

AWS services were chosen primarily for low maintenance overhead: fully managed systems let the team prototype and build quickly, and direct access to AWS support engineers provided idiomatic usage guidance. DynamoDB and S3 are both horizontally scalable in storage and throughput, which proved critical during migration when traffic exceeded 100 times steady state. However, the hot and cold stores are implementation details — either tier could be swapped for another system with similar properties.

Data Plane and Control Plane

Because the underlying systems are managed, Alki's data plane is stateless: it simply translates API requests into reads and writes against DynamoDB and S3. The offline control plane (offload and compaction) runs on Blackbird and Step Functions, and since the hot store is horizontally scalable, offload doesn't need to meet strict deadlines — failures in the batch layer incur extra storage cost but never cause unavailability or data loss. Similarly, extended compaction downtime only degrades read latency slightly.

Verification and Immutability

Before a new run becomes visible, Alki verifies the transition with a series of checks comparing pre- and post-data: keys must be sorted, record counts must match, and hashes of (key, value) pairs must agree. The hashing uses an order-independent function built on arithmetic over large prime moduli (conceived by former teammate Robert Escriva, whose implementation is open sourced). This allows hash computations to be parallelized across chunks of a run, and for compaction, an expected hash can be computed simply by modulo-summing the hashes of each input run. Verifying large-scale batch transformations is much easier because data in a run is immutable once sealed.

Development and Migration

The team rolled out Alki and migrated audit log data from Edgestore in phases, delivering incremental value to surface unknowns early.

Phase 0: Benchmarking

Before committing to DynamoDB and S3, the team benchmarked several hot and cold store candidates, ruling out backends with performance limitations at scale and building relationships with AWS solutions architects early.

Phase 1: Double Writes

With a basic write path into the hot store implemented, Alki was integrated into the live audit log path: writes went to Edgestore first, then attempted to write to Alki. Since offload wasn't implemented yet, ingested data was dropped after a period to avoid hot storage costs. Alki write failures didn't count against external API success rates, but the integration exposed issues with bursty gRPC traffic and DynamoDB capacity provisioning early on.

Phase 2: Double Reads with Edgestore as Source of Truth

Once a read path existed, Alki began performing shadow reads on live traffic, comparing results against Edgestore. Initially, missing records were common because Alki wasn't durable yet; after offload and cold reads were implemented, the missing-record rate dropped sharply, confirming the design. This phase also produced tooling for investigating mismatched reads, which proved valuable for debugging ingestion and read paths. After validation, Alki began durably ingesting audit logs while reads still relied on Edgestore, and a batch upload API migrated historical data directly into Alki's cold store.

Phase 3: Double Reads with Alki as Source of Truth

After migrating all data, shadow reads continued for a few more weeks before switching both reads and writes to Alki. The double-read/double-write setup remained active for several more weeks to enable rollback if needed — though the rollback wasn't necessary. Notably, Alki handled ingestion spikes more gracefully than Edgestore; Alki reads often returned more complete data.

Phase 4: Alki Only

Once confident in Alki's reliability, writes to Edgestore were turned off and the migrated data was deleted from the legacy system.

Current Status and Roadmap

Alki now stores roughly 350 TB of user data (pre-replication, excluding indexes) at about one-sixth the per-GB-per-year cost of Edgestore. That reduction comes directly from leaning on the inexpensive economics of cold blob storage.

Several other cold metadata workloads at Dropbox are being onboarded to the system. Many logging use cases have long retention windows but see almost no reads after an initial ingestion period, making them natural fits for Alki's design.

Future work includes building automation that can detect cold metadata in Edgestore and the in-development Panda key-value store, then migrate that data into Alki without manual intervention.

Contributors and reviewers who helped shape the project: Anuradha Agarwal, James Cowling, William Ehlhardt, Alex Grach, Stas Ilinskiy, Alexey Ivanov, Anirudh Jayakumar, Gevorg Karapetyan, Olga Kechina, Zack Kirsch, Preslav Le, Jonathan Lee, Cheng Li, Monica Pardeshi, Olek Senyuk, Lakshmi Kumar T, Lawrence Xing, and Sunny Zhang.