Weekly Paper Notes — one of the top picks from the 2026-10-31 CS paper digest. Area: Databases.

Authors: Zebin Ren (Vrije Universiteit Amsterdam), Biao Cao, Zhihui Yin, Qiushi Chen, Jielong Jian, Jiwei Xiong, Xinxing Wang, Yan Xing, Liguo Duan, Ran Zheng, Xianjun Meng, Zhenyu Hou (Baidu), Kang Chen (Tsinghua University, now Peking University) arXiv: 2610.32247 · PDF

TL;DR

Most large storage systems now keep their namespace in a distributed database: Facebook’s Tectonic on ZippyDB, Google’s Colossus on Bigtable, HopsFS on NDB. Baidu did the same. Its second-generation metadata layer was a general-purpose transactional database in the TiDB/CockroachDB mould (SQL proxies, multi-Raft, RocksDB, snapshot-isolation MVCC) shared by its object store (BOS), its hierarchical object store (Mantle) and its POSIX file system (CFS).

This paper is the design of what replaced it. MetaDB is still a Raft-replicated, range-sharded transactional KV database, but three layers are rebuilt around how file-system metadata actually behaves. Shards split only at directory boundaries, so single-directory operations stay on one node, and the read-modify-write logic for those operations runs on the storage node rather than a coordinator. Hot parent-directory counters and timestamps are taken off the transaction path and aggregated asynchronously, with quota and secondary-index updates shipped out of band through a Raft-logged queue. Finally, MVCC versions live only in memory, so bulk deletes produce one LSM tombstone instead of two, and a compaction trigger targets the narrow key ranges where deletes cluster.

The result is 2.2–4.1× the throughput of the previous system and roughly half the metadata machines. It has been in production for over five years, the multi-shard transaction rate on hierarchical namespaces fell from 100% to 0.79–4.37%, and the largest cluster runs over 1,000 nodes holding tens of trillions of records.

What problem is the paper actually attacking?

The “put the namespace in a database” pattern became standard because it hands replication, failover and elasticity to someone else. The trouble is that a general-purpose database sees file-system metadata as rows with no structure, and the paper names three places where that costs real performance.

The data model. A directory tree is hierarchical, but range or hash sharding splits by key range or size. A large directory gets cut across shards, and an operation as common as create (insert a child, update the parent’s num_children and mtime) becomes a distributed transaction. Baidu’s traces show over 97% of tree-modifying operations touch a single directory; cross-directory rename is under 3%. Directory sizes are bounded too, with even the largest under a billion entries, so keeping each directory on one shard is feasible.

The transaction model. ACID applied uniformly to every field creates hotspots. ML pipelines (the paper mentions Kubeflow) create tens of thousands of files in one directory at once, and every create has to lock the same parent record. The old system did about 60K create QPS when requests were spread out and about 6K when they all hit one directory, a 10× drop. Meanwhile quota and secondary-index updates were committed atomically with the primary update even though they live on other shards and quotas only settle hourly for billing.

The storage engine. Metadata transactions finish in under 10 ms, but an MVCC engine built for long-running transactions persists every version and every MVCC tombstone to the LSM tree, which then adds its own tombstone on physical deletion. Object storage sees enormous TTL-driven deletes, and because many customers prefix object names with timestamps, those deletes are dense and contiguous in key space. During a bulk-delete phase, a 1,000-entry listdir went from under 100 ms to about 6 seconds while scanning over tombstones, and RocksDB’s level-driven compaction couldn’t clean them up fast enough.

None of these points is new in isolation. HopsFS already partitions by parent inode ID and suffers lock contention on parent records. InfiniFS colocates parent attributes with children. The LSM delete-performance problem has its own literature (Lethe, among others). What the paper contributes is a single database that addresses all three at once and has run that way for years at exabyte scale. The CFS (EuroSys 2023) and Mantle papers describe namespace layers built on this database under the name TafDB; this paper is the database underneath them.

The mechanism: three structural fixes

1. Directory-aligned sharding and pushdown

MetaDB stores the namespace in a MetaTable keyed by (PID, name): parent inode ID, then entry name. A directory’s own attributes are stored as a special child named _attr_, so the attributes sit right next to the directory’s children in key order. Two auxiliary tables, QuotaTable and SecondaryIndexTable, hold per-user quota counters and data-plane-file-to-metadata mappings.

Sharding is range-based, with one change: a schema-level group_key (set to the parent ID) defines where splits are allowed. When a shard outgrows its size threshold, it splits at a group_key boundary, never in the middle of a directory. In a microbenchmark, plain size-based sharding dropped single-directory create throughput from 6.0K to 0.4K QPS the moment a split separated a directory’s entries, while the directory-aligned policy held 6.0K throughout.

That creates unsplittable “jumbo shards” for huge directories. MetaDB handles those operationally: the scheduler detects hot jumbo shards, moves them to under-used nodes and evicts unrelated replicas so the whole machine serves that directory. If one directory still outgrows a machine, operators can split it manually and accept distributed transactions for it. The largest production CFS shards are 179 GB with 901M records.

Once a directory and its attributes are guaranteed colocated, the read-modify-write of a mkdir (read parent attributes, insert child, write parent back) no longer needs a coordinator round-trip. MetaDB pushes the whole operation down to the backend node that owns the shard. That alone gave 25% lower latency with one client and 34% lower latency plus 29% higher throughput at 256 clients.

2. Taking hot and auxiliary updates off the critical path

MetaDB’s asynchronous updating framework: on the leader, a create_file appends to the Raft log, applies to local storage, and enqueues auxiliary updates into an async queue; an async sink dispatcher groups them by target and batch-sends to async index nodes on other leaders; replicas can rebuild the queue by replaying the Raft log. The asynchronous bypass for quota and index updates. Auxiliary updates are persisted in the Raft log with the primary update, applied locally, then drained by a sink that batches them per destination shard. Source: Ren, Cao, Chen et al. — arXiv:2610.32247, Figure 7.

Quotas and secondary indexes are derived data on other shards. MetaDB generates their update requests while processing the primary operation, persists them in the same Raft log entry, applies the primary update locally, and pushes the auxiliary requests into an in-memory queue. A background sink groups them by destination and sends batches. The Raft log isn’t truncated until the sink confirms delivery, so a new leader can rebuild the queue by replaying the log after a failover. Replays may resend requests already applied; each request carries a timestamp that the destination records, which makes application idempotent. In the paper’s measurements the queue held fewer than 100 pending items at 16K QPS, which works out to under 10 ms of lag against a tolerance of minutes.

The parent-directory hotspot gets a related trick. num_children is a sum of deltas and mtime is a max over commit timestamps, so concurrent updates commute. Instead of locking the parent’s _attr_ record, each operation logs its delta to Raft and drops it in an in-memory queue; a background thread folds the deltas and writes them in batches. On the read path, the node merges the persisted attribute record with any pending deltas before returning it, so clients still see current values. Concurrent mkdir into a single directory ran 10.7× faster than the lock-based version.

It’s worth being clear about the consistency trade. Directory attributes stay linearizable from the client’s point of view because of the read-side merge. Quotas and secondary indexes are eventually consistent with a bounded lag. The paper argues this matches how those fields are used (hourly billing, debugging lookups), and the production table reports the worst-case lag per cluster.

3. A storage engine sized to metadata lifetimes

Diagram contrasting a conventional engine, where a delete marks an MVCC tombstone that MVCC GC later turns into an LSM tombstone cleaned by slow native RocksDB compaction, with MetaDB, where in-memory MVCC deletes directly into an LSM tombstone that locality-aware compaction purges quickly. Conventional MVCC-on-LSM pays for each delete twice (an MVCC tombstone, then an LSM tombstone) and waits on level-driven compaction. MetaDB keeps versions in memory and compacts the hot deleted ranges directly. Source: Ren, Cao, Chen et al. — arXiv:2610.32247, Figure 9.

Because metadata transactions are short, MetaDB keeps all MVCC versions and MVCC tombstones in an in-memory layer. When a memtable flushes, it writes only the latest committed value per key; a delete becomes a single RocksDB tombstone. The memtable is held a bit longer than the 5-second transaction timeout so no in-flight reader loses the versions it needs, and anything not yet flushed is recoverable from the Raft log. (RocksDB’s own WAL is disabled; Raft is the only log.)

The second half is compaction. MetaDB tracks key ranges with heavy recent deletions and, once a narrow range crosses a threshold, issues a compaction for just that range instead of waiting for level saturation or compacting the entire shard. In a 150-minute experiment deleting at 5K QPS, the baseline accumulated 14M tombstones and listdir hovered around 5 seconds. In-memory MVCC alone cut LSM writes by about 60% but still drifted to 10–12M tombstones. Locality-aware compaction alone kept it to 1–8M. Both together stayed under 2M tombstones with listdir peaking at 0.7 s.

Results

On a 10-node production cluster driven by mdtest (20 clients, 50 threads each), MetaDB reduced latency by 23–75% and delivered 2.2–4.1× the throughput of the old general-purpose database across mkdir, dirstat, rmdir, create and delete. An appendix compares against TiDB as well.

The production numbers carry more weight. The nine deployments in Table 1 include BOS clusters of roughly 400–575 nodes managing 1.3–1.8 trillion records and hundreds of petabytes each, with peaks near 2M read and 0.7M write QPS. On hierarchical namespaces, multi-shard directory transactions dropped from 100% under the old system to 0.79–2.37% on CFS and 3.13–4.37% on Mantle, where path resolution still needs index entries on other shards. A 21-day trace of two CFS clusters shows listdir falling from 8–18 ms to 0.5–4 ms and create/mkdir/delete/rmdir roughly halving, though the authors note the GP-DB cluster was much smaller by then, so it isn’t a controlled comparison.

Lessons from five years in production

Section 8 is the part I’d point a platform team at. A few of the lessons:

  • Build small, don’t fork big. Baidu hit the same three mismatches on its own Generation 2 database and, for a separate HDFS-like system, on CockroachDB. Rather than keep modifying a codebase of millions of lines, they wrote MetaDB from scratch on RocksDB in about 150K lines. The cost is reimplementing features when requirements change; their metadata requirements haven’t changed much.
  • Keep SQL as an interface, drop the SQL engine. Clients only ever issue about 20 fixed statement shapes, so MetaDB maps each one straight to an execution path and skips parsing, optimisation and planning on every request.
  • Partition the control plane early. With millions of Raft groups in one cluster, per-shard heartbeats and scheduling overwhelmed a single Manager. They split clusters into Cells with local managers and kept the global manager to range-to-cell routing.
  • Central services fail in correlated ways. A batch of proxy restarts with cold routing caches once overloaded the Manager, which led to the MetaCache tier. A timestamp oracle on the write path was replaced with Hybrid Logical Clocks so a TSO failure can’t block writes.
  • Tight coupling can be cheaper than clean layering. An early design kept the directory index outside the database and needed cross-system two-phase commit for mkdir. Moving it into internal tables saved, by their estimate, six months of work for a ten-engineer team.

Why this matters

The general lesson is that “use a distributed SQL database for your metadata” is a sound starting point and a poor end state. The three fixes are each fairly simple: split on semantic boundaries, identify which fields commute and stop locking them, and size MVCC retention to your actual transaction lifetimes. None needs new theory. What the paper shows is how much they’re worth together at real scale, which is the kind of number you rarely get outside a production paper.

Anyone running file or object metadata on CockroachDB, TiDB, FoundationDB or Spanner will recognise all three pathologies. The cheapest pieces to borrow are (parent, name) keys with a colocated _attr_ row, split constraints that respect a grouping key (several of those databases already expose something similar), and moving derived counters onto an idempotent, log-backed async path. The in-memory MVCC idea is harder to retrofit, since it depends on hard bounds on transaction duration that a general-purpose database can’t assume.

The obvious open question is cross-directory rename, the remaining source of distributed transactions on CFS. The paper keeps it on the slow path, which is fine at 3% of operations, but it’ll matter more for workloads that move large trees.

Read alongside

📄 arXiv abstract · 📄 PDF

Part of the Weekly CS Paper Digest series. Summary written from a close read of the preprint; figures cropped from the arXiv PDF and reproduced here under fair use for educational commentary.