MetaDB: Putting File-System Structure Back into Distributed Databases

MetaDB: Putting File-System Structure Back into Distributed Databases Zebin Ren1,* , Biao Cao2,*,† , Kang Chen 3, †, ‡ , Zhihui Yin2 , Qiushi Chen2 , Jielong Jian2 , Jiwei Xiong2 , Xinxing Wang2 , Yan Xing2 , Liguo Duan2 , Ran Zheng2 , Xianjun Meng2 , and Zhenyu Hou2

arXiv:2610.32247v1 [cs.DB] 23 Oct 2026

1 Vrije Universiteit Amsterdam

2 Baidu (China) Co., Ltd.

Abstract Storage systems in production increasingly rely on distributed databases for metadata management, yet our experience at Baidu shows that treating a general-purpose database as a black box leaves substantial performance and efficiency untapped. File-system metadata exhibits directory-tree locality, differentiated consistency requirements, and clustered deletions that general-purpose databases largely ignore. We thus propose MetaDB, a metadata-aware distributed transactional database that serves as the shared metadata layer for Baidu’s large-scale storage systems. MetaDB addresses three key mismatches between general-purpose databases and metadata workloads: Data Model Mismatch, Transaction Model Mismatch, and Storage Implementation Mismatch. To bridge these gaps, MetaDB combines ① tree-topology-induced sharding and execution, ② semantic-aware off-critical-path processing, and ③ a lifecycle-aware storage engine with in-memory MVCC and locality-aware compaction. MetaDB achieves 2.2×–4.1× the throughput of our previous general-purpose database and halves the number of metadata machines. Deployed in production at Baidu for over five years, MetaDB unifies metadata management across the company’s storage fleet and scales to over 1,000 metadata nodes, tens of trillions of metadata records, and exabyte-scale storage in a single cluster.

1

Introduction

Distributed storage systems are fundamental to modern cloud infrastructure, but efficiently managing massive metadata remains challenging. Many systems therefore adopt distributed relational or key-value databases for file-system metadata management (e.g., Tectonic [33], Colossus [6], Mantle [25], ACOS [17]). This decoupled architecture reduces development complexity by delegating state management, elasticity, *Equal contribution. † Corresponding author. ‡ Work done while the author was at Tsinghua University.

3 Peking University

and fault tolerance to database systems, while still providing high scalability and reliability. At Baidu, we also use this paradigm to manage metadata for our exabyte-scale cloud storage infrastructure, including our cloud file system (CFS) and object storage services (BOS and Mantle) (§2.1). We therefore built and deployed a unified general-purpose distributed database as the common metadata layer across all our storage systems. However, our production experience shows that treating the database as a “black box” for metadata workloads leaves substantial performance untapped and causes severe bottlenecks. Because general-purpose databases are designed for generic relational or key-value data, they overlook the unique structural, semantic, and dynamic properties of file-system metadata. We identify three mismatches between generalpurpose databases and metadata workloads. First, the flat data model of traditional databases conflicts with the hierarchical tree structure of file-system metadata (Data Model Mismatch). General-purpose databases typically rely on range or hash sharding, often splitting entries of the same parent directory across shards and thereby turning highfrequency single-directory updates into expensive distributed transactions. Even when locality is preserved within a shard, the database lacks directory-tree semantics, so a single logical operation (e.g., file creation) can still incur multiple network round-trips for the required transactional steps. Second, the generic transaction model imposes a rigid, one-size-fits-all atomicity model for all records in a transaction. However, this model fails to accommodate the highly differentiated consistency requirements of metadata updates (Transaction Model Mismatch). Single metadata operations often trigger updates to parent-directory attributes and derived auxiliary metadata. Enforcing strict ACID guarantees across all these fields in a single transaction creates severe contention on shared parent-directory records. It also forces unnecessary multi-shard coordination for auxiliary metadata, even though such metadata can safely tolerate relaxed timeliness. Third, the underlying storage implementation mismatches metadata access patterns (Storage Implementation Mismatch).

Traditional Multi-Version Concurrency Control (MVCC) persists all tombstones to storage to support long-running transactions, whereas metadata transactions are short-lived (< 10 ms). Under cloud-scale consecutive bulk deletions, these persisted tombstones rapidly accumulate in the underlying Log-Structured Merge-tree (LSM-tree) and degrade range scans such as listdir. Such deletions also exhibit strong spatial locality (e.g., tens of megabytes within a 4 GB shard), but conventional compaction does not exploit this locality and thus cannot purge tombstones in time. To bridge these gaps, we propose MetaDB, a highperformance, metadata-aware distributed database at Baidu. Rather than treating the database as a generic black box, MetaDB co-designs the database engine around metadataspecific structures, semantics, and dynamics through the following three techniques. ① Tree-Topology-Induced Sharding and Execution. To resolve the data model mismatch, MetaDB aligns database shard boundaries with the directory tree via policy/size-based sharding, keeping single-directory operations within a single shard. We further push down transactional logic directly to the storage nodes, collapsing multi-round network coordination into a single remote execution. ② Semantic-Aware Off-Critical-Path Processing. To resolve the transaction model mismatch, MetaDB extracts aggregatable hotspot directory attributes and auxiliary metadata from the critical path. For hotspot parent-directory attributes, synchronous in-place updates are removed from the write critical path and replaced with asynchronous aggregation through an in-memory queue plus read-path reconciliation, reducing lock contention while preserving the latest visible state. We employ an asynchronous off-critical-path update mechanism: auxiliary metadata (quotas and indexes) are updated out-ofband without strict timeliness requirements, thereby avoiding multi-shard transactions. ③ Lifecycle-Aware Storage Engine. To resolve the storage implementation mismatch, MetaDB optimizes the storage engine specifically for metadata lifecycles. By introducing an in-memory MVCC layer, we prevent short-lived MVCC tombstones from being flushed to disk. Combined with localityaware range compaction, MetaDB promptly purges localized tombstones, sustaining low latency for listdir. By resolving the mismatches between databases and metadata workloads, MetaDB delivers 2.2×–4.1× the throughput of our previous general-purpose database. MetaDB has been deployed in Baidu’s production environment for over five years, unifying metadata management across our entire storage fleet. MetaDB reduces the number of cluster machines required for metadata management by approximately 50%. Today, a single MetaDB cluster scales to over 1,000 metadata machines, managing tens of trillions of records and supporting exabyte-scale storage. This paper makes the following key contributions: • We identify the root cause of metadata inefficiency in

general-purpose distributed databases as the loss of structural information along three dimensions: tree topology, transaction semantics, and operation dynamics. • We propose and implement three corresponding designs in MetaDB to restore the tree structure in the database. • We evaluate MetaDB on massive-scale production metadata workloads, demonstrating substantial performance improvements and resource savings over generalpurpose databases.

2

Background and Motivation

2.1

Metadata Management at Baidu

In large-scale distributed storage, metadata encompasses the structural and attribute information governing data management. This specifically includes the flat and hierarchical namespaces (e.g., flat object keys and directory trees), system attributes (e.g., access control, modification timestamps, and user quotas), and auxiliary secondary indexes 1 . The production environment at Baidu deploys two primary categories of storage infrastructure underpinned by distinct metadata management strategies: Cloud Object Storage: To accommodate diverse application demands, we provide two variants of namespace services. Object storage (BOS) offers a flat namespace ideal for keyvalue semantics. Hierarchical object storage (Mantle [25]) supports HDFS-like directory semantics. Architecturally, such a hierarchical namespace adopts a fully disaggregated design where clients are oblivious to data placement and cannot cache metadata locally. Thus, every metadata operation translates to a direct request to the backend metadata service, demanding high throughput and low latency. Distributed File Storage: Our distributed file storage (CFS [41]) provides a fully POSIX-compliant hierarchical namespace optimized for shared file access. Unlike the hierarchical namespace for cloud object storage, this namespace for distributed file storage utilizes a coupled architecture where clients can cache directory metadata and physical layout information to accelerate local path resolution. Despite these architectural differences in client-side caching and data layout, both Mantle and CFS inherently require a robust and scalable storage layer to persist their hierarchical directory trees. Unless otherwise specified, we use BOS, Mantle, and CFS in the remainder of this paper to refer specifically to their underlying namespace subsystems.

2.2

Metadata Databases Prior to MetaDB

The distributed databases powering Baidu’s metadata services underwent two generations of architectural evolution before the inception of MetaDB. 1 Secondary indexes are utilized to accelerate queries on specific attributes,

such as filtering objects by creation time for garbage collection.

se

e ir ir ttr te te ta crea dele mkd rmd nam re

Figure 1: Op distribution.

A B C D E

0.8 0.6 0.4 0.2 0.0 0 10

103

Size

106

109

Figure 2: Directory sizes.

Generation 1: Ad-hoc Design with Multiple Databases. Initially, BOS and CFS were served by separate metadata systems. For BOS, metadata was partitioned across N MySQL shards using static modulo hashing for simplicity. This design had three major limitations: (1) Inflexible Scalability: static hashing forced an expensive “double-the-cluster” (N → 2N) upgrade path to avoid massive data migration; (2) Lack of Atomicity: multi-node operations, such as cross-shard rename, lacked transactional guarantees and thus risked inconsistency; and (3) High Management Overhead: fragmented, systemspecific metadata silos imposed high operational and maintenance costs. Meanwhile, CFS used static subtree partitioning, which was highly vulnerable to workload hotspots. Generation 2: Unified Design with a General-Purpose Database. A dedicated metadata service (MDS) such as CephFS [42] targets hierarchical namespaces and does not fit BOS’s flat namespace, whereas a distributed transactional database can serve both. We therefore built a unified general-purpose distributed database, architecturally similar to TiDB [15] and CockroachDB [5], based on the open-source Doris project [2]. It used RocksDB as the local storage engine beneath a distributed SQL proxy layer, and provided dynamic sharding, multi-Raft replication for high availability, and MVCC with snapshot isolation for distributed transactions. While the system was functionally complete, production deployment exposed a key lesson: treating the underlying database as a “black box” creates severe performance bottlenecks for metadata workloads. Thus, we redesigned the database architecture around directory-tree semantics and built MetaDB. Its design is motivated by three fundamental architectural mismatches we observed in Generation 2.

2.3

Three Architectural Mismatches

2.3.1 Data Model Mismatch: Flat Sharding vs. Tree Topology. General-purpose databases view data as flat, independent records in tables, partitioning them by size or hash boundaries. This ignores the inherent topology of file systems. Spatial locality is destroyed by flat sharding. Figure 1 breaks down directory-tree-modifying operations across three representative CFS clusters, denoted by A, B, and C. Over 97% of all operations (e.g., mkdir, create, delete) are singledirectory operations; cross-directory rename accounts for less than 3%. Logically, a single-directory operation should only

50 40

Shard Object

30 20 10 0

A B C D E F G H I J

Latency (s)

1.0

Ratio (%)

A B C

CDF = P(X ≤ x)

Ratio (%)

60 50 40 30 20 10 0

6 5 4 3 2 1 0 0

5000 QPS

30 60 90 120 150 Time (minutes)

Figure 3: Ratio of objects Figure 4: The effect of conwith creation-time prefixes of secutive bulk deletion on 10 users (from A to J). listdir latency.

access localized data. However, generic size-based sharding arbitrarily fractures large directories across multiple shards, forcibly escalating these high-frequency, localized updates into expensive distributed transactions. Single-node containment is feasible. Figure 2 shows the directory size distribution of five users. The majority of directories are bounded in size, with even the largest containing fewer than one billion entries. This suggests that aligning database shard boundaries with directory boundaries is viable and keeps single-directory workloads within a single shard. 2.3.2 Transaction Model Mismatch: Rigid ACID vs. Relaxed Semantics. Traditional databases enforce a rigid onesize-fits-all transactional atomicity model. When this rigid semantics is applied blindly to metadata, it creates unnecessary bottlenecks. Single-shard hotspots. Modern Machine Learning (ML) workloads (e.g., Kubeflow [10]) frequently spawn tens of thousands of concurrent file creations within a single target directory. In a general-purpose database, every create operation must synchronously update the shared parentdirectory record, including attributes such as num_children and modify_time. We quantify this contention penalty. Without contention, the previous system processed ∼60K QPS for create. However, when all requests target the same directory, throughput drops to ∼6K QPS (a 10× drop). Unnecessarily strict atomicity for auxiliary metadata. Updates to primary metadata (see Figure 5) often trigger cascading updates to secondary indexes and user quotas (auxiliary metadata). General-purpose databases execute these synchronously within transactions, forcing distributed twophase commit (2PC) since indexes/quotas reside on separate shards. In reality, file system semantics can tolerate minutes of latency for quota and index updates. In our production deployment, quota records are used for post-paid billing and monitoring with hourly settlement, so several minutes of propagation delay between a primary metadata update and the corresponding quota update is acceptable. Thus, enforcing strict ACID guarantees here is an expensive over-design. 2.3.3 Storage Implementation Mismatch: Long-Lived MVCC vs. Transient Metadata. General-purpose storage

Auxiliary metadata QuotaTable UID name value 1 #DIR 2 1 #FILE 3 1 #SIZE -

/

Directory

A

File

C D

Primary metadata MetaTable PID name 0 A A_attr 1 B 1 C 1 _attr_ 3 D C_attr 3 E 3 _attr_

B E

Client

SecondaryIndexTable FID PID name 1001 1002 1003

1 3 3

type

1 2 3

dir file dir

links

2 4 5

file file 2

} }

3.1

Data Model

……

Leader Replica

BE node

BE node

……

……

Replica Replica

Raft groups

MetaDB adopts a range-partitioned data model in which records are sorted and stored by primary key. Three tables are defined in MetaDB as shown in Figure 5. MetaTable stores pri-

……

In-memory MVCC

Shard 2

engines (e.g., LSM-trees with MVCC) are designed for arbitrary transactional workloads, including potentially longrunning transactions and queries, making them poorly suited to the metadata lifecycle. Metadata exhibits massive consecutive bulk deletions. Object storage environments see frequent, large-scale range deletions driven by Time-To-Live (TTL) expirations or explicit bucket purges [1]. Figure 3 shows the ratio of shards with creation-time prefixes for object names, and the ratio of objects named with creation-time prefixes. This shows that many objects in our BOS clusters use time-based naming prefixes, which turns TTL expirations into dense, spatially continuous deletions in the database. Transient versions accumulate as tombstones. Although metadata transactions are exceptionally short (< 10 ms), traditional MVCC implementations preemptively flush multiversion states to disk to support potentially long-running queries, resulting in millions of unnecessary MVCC tombstones during bulk deletions. When foreground range scans (e.g., listdir) traverse these accumulated tombstones in the LSM-tree, they suffer severe read amplification. As demonstrated in Figure 4, the latency of a 1,000-item listdir spikes from < 100 ms to ∼6 seconds during a deletion phase. Furthermore, because these deletions are highly localized, the database’s generic full-shard compaction mechanism becomes too slow and resource-intensive to purge these tombstones in a timely manner.

MetaDB Design

BE node

Raft log

Shard 1

Figure 5: Metadata schema in MetaDB. In these tables, ID (identification) is the ‘inode ID’ of each file or directory, PID is the ID of the entry’s parent directory in the directory hierarchy, UID is the user ID for quota accounting, and FID is the ID of the file in the data plane (usually a separate system).

3

Client

Proxies

Metacaches

B D E

Manager ID

Client

KV storage engine

Figure 6: The architecture of a MetaDB cluster. Proxies handle client routing and SQL parsing. The Manager oversees cluster status and dynamic sharding. MetaCache provides high-speed routing resolution. Backend (BE) nodes manage data replication via Raft and persist data using an integrated in-memory MVCC and RocksDB storage engine.

mary metadata while QuotaTable and SecondaryIndexTable store auxiliary metadata. To support hierarchical namespaces, MetaTable maps the directory tree into a flat schema. Following prior file systems such as InfiniFS [27, 41], MetaDB separates access fields from attributes. The access fields (PID, name, ID) encode the directory hierarchy, while the remaining columns store attributes such as type, link count, and the number of children. In particular, the attributes of a directory are represented by a special entry named _attr_, whose parent is the directory that owns the attributes. MetaTable is keyed by (PID, name), so a directory’s _attr_ entry is colocated with all of its children. We choose this layout because a single-directory operation typically updates both a child entry and the attributes of its parent directory. Placing them together preserves locality and, combined with our policy/size-based sharding (§4.1), keeps common single-directory operations within a single shard. Beyond MetaTable, MetaDB maintains two auxiliary tables. QuotaTable tracks per-user resource usage for quota management. SecondaryIndexTable stores mappings from files in the data plane to their corresponding metadata entries, providing an auxiliary index for lookup and debugging.

3.2

Architecture

We describe the MetaDB architecture (Figure 6) through the lifecycle of a request. When a client issues a metadata operation, it connects to a randomly selected stateless Proxy for load balancing. The Proxy parses the lightweight SQL request, extracts the routing keys, and queries the MetaCache to locate the target records. MetaCache provides fast shard-routing and consults the central Manager only on a cache miss. Once the target backend (BE) node is identified, the Proxy forwards the request to the leader replica of the corresponding shard.

In the BE node, the request is first appended to the Raft log and replicated across a three-node Raft group to provide availability and durability [32]. After consensus, the operation is applied to the local storage engine. For primary metadata workloads that require both point lookups and range scans, each BE node integrates an in-memory MVCC layer with a single persistent RocksDB [13] instance per disk. To avoid double-logging, we disable RocksDB’s native Write-Ahead Log (WAL) and rely solely on the Raft log for durability [22, 39]. Raft log truncation is deferred until the corresponding data is safely persisted in the local single-node storage engine.

3.3

Addressing the Mismatches

To bridge the gap between traditional databases and metadata workloads, MetaDB introduces three core design pillars, each directly targeting one mismatch identified in §2.3. ① Tree-Topology-Induced Sharding and Execution (§4). To address the Data Model Mismatch, MetaDB uses a policy/size-based sharding mechanism that aligns shard boundaries with the directory tree topology and keeps the entries of a directory on the same shard. In addition, MetaDB pushes single-shard transactional logic into BE nodes to eliminate unnecessary network round-trips. ② Semantic-Aware Off-Critical-Path Processing (§5). To address the Transaction Model Mismatch, MetaDB removes aggregatable directory attributes and auxiliary metadata updates from the transactional critical path. Using an asynchronous bypass mechanism and an in-memory queue, it safely delays quota/secondary-index updates and resolves lock contention without sacrificing correctness. ③ Lifecycle-Aware Storage Engine (§6). To address the Storage Implementation Mismatch, MetaDB introduces an in-memory MVCC layer that prevents MVCC tombstones from reaching disk during bulk deletions. It further employs locality-aware range compaction to purge dense tombstone accumulations timely and ensure stable range-scan latency.

4

Tree-Topology-Induced Sharding and Execution

MetaDB co-designs the data placement and execution engine according to the directory tree topology. We introduce a policy/size-based sharding mechanism to confine singledirectory operations to a single shard (§4.1) and further push down the transactional execution logic directly into the storage nodes to eliminate network coordination overhead (§4.2).

4.1

Sharding Policy

Production metadata workloads exhibit strong spatial locality: our analysis shows that over 96% of directory-entry updates are single-directory operations (§2.3.1). Single-directory operations access only the target entry and the attributes of its

immediate parent directory. However, traditional size-based sharding splits shards at fixed size thresholds without considering directory-tree topology, often separating a parent directory from its children and thereby turning single-directory updates into distributed transactions. To preserve structural colocation, MetaDB implements a policy/size-based sharding mechanism. We introduce a schema-level attribute named group_key. When a shard exceeds the configured capacity threshold, MetaDB does not split it arbitrarily. Instead, the system splits the data at the group_key boundary. By using the parent directory identifier as the group_key, MetaDB explicitly anchors a directory’s attributes and its direct children within the same physical database shard. This keeps high-frequency single-directory operations in a single shard, avoiding distributed transactions. While structural colocation avoids distributed transactions for single-directory operations, it also creates jumbo shards: unsplittable shards caused by exceptionally large directories. These jumbo shards can become performance bottlenecks, so MetaDB uses two techniques to handle them: (1) Jumboshard-aware scheduling and isolation. MetaDB continuously monitors shard load to identify unsplittable jumbo shards. The scheduler migrates hot jumbo shards to under-utilized nodes and evicts unrelated replicas, eliminating resource contention and dedicating the full machine to the jumbo directory. (2) Workload-adjustable dual-mode sharding. By default, MetaDB keeps a directory in one shard to avoid distributed transactions. If a jumbo shard still exceeds a single machine’s capacity after isolation, operators can split it across shards manually, but updates to that directory may require distributed transactions. This serves as a fallback for extreme cases.

4.2 Single-Shard Transaction Logic Pushdown Our topology-aware sharding confines single-directory operations to a single physical node. However, executing these localized operations through a traditional database interface still incurs substantial overhead because generalpurpose databases use a coordinator-based transaction model. Metadata operations inherently follow a Read-ModifyWrite (RMW) pattern. For example, a mkdir must read the current parent-directory attributes, insert the new child entry, and write back the updated parent attributes. In a typical design, a stateless proxy or client coordinates this sequence of operations, requiring at least two network round-trips to fetch state and commit the modification. To eliminate this overhead, MetaDB pushes transaction logic down to the storage node. Because our sharding policy keeps a directory’s entries and attributes colocated, MetaDB can bypass the coordinator and directly execute the entire directory-tree operation on the BE node. The BE node performs the full RMW sequence locally, removing multi-round network coordination and thereby reducing network overhead to achieve ultra-low latency for single-directory operations.

append

Node Leader Raft log

log replay (recovery)

Async sink

Apply Async queue

Remote Node

Dispatcher

append create_file('/A/a')

Group by target

Batch send

disk

Replica Raft log

log replay (recovery)

create_file('/A/b')

Async Index Async Index

Other leaders

create_file('/A/c')

Apply

+1 +1 … +1

Batch flush

Persisted MetaTable Apply ATTR updates

Async queue Insert entries

PID

Name

ID

0

A

1

num_child -

1

_attr_

2

0->3

1

a

3

-

1

b

4

-

1

c

5

-

Figure 8: Asynchronous attribute update.

Figure 7: Asynchronous updating framework.

5

Semantic-Aware Off-Critical-Path Processing

General-purpose databases enforce a uniform and rigid ACID transaction model across all data fields. This choice creates performance bottlenecks for metadata workloads. Specifically, concurrent operations within the same directory result in concurrent updates to its attributes, leading to severe lock contention. Furthermore, maintaining derived auxiliary metadata in the same transaction with primary metadata updates results in expensive multi-shard transactions. To eliminate these bottlenecks, MetaDB adopts a semanticaware off-critical-path processing mechanism. By understanding the unique consistency requirements of different metadata fields, MetaDB extracts both aggregatable directory attributes and auxiliary metadata from the transaction and performs operations on these fields through off-critical-path processing.

5.1 Decoupled Asynchronous Auxiliary Updates Metadata operations maintain global auxiliary metadata such as user quotas and secondary indexes. Because this metadata usually resides on different shards from the primary metadata, updating it atomically with the primary metadata requires multi-shard transactions, which reduces throughput. Unlike primary metadata, this auxiliary metadata does not require atomicity with primary metadata updates. MetaDB therefore decouples quota and index updates from the primary metadata update transaction and processes them through an asynchronous bypass mechanism. As shown in Figure 7, MetaDB generates auxiliary metadata update requests during the primary metadata updates, persists them in the local Raft log, applies the primary metadata update to the single-node storage engine, and then enqueues the auxiliary metadata update requests into an in-memory asynchronous queue. An asynchronous sink drains this queue and batches requests by destination before forwarding them to remote shards, reducing network overhead. This bypass removes quota and index updates from the critical path and avoids the multi-shard transactions that are otherwise required. This design must handle two issues: lost updates and dupli-

cated updates. To avoid lost updates, each auxiliary metadata update request is first persisted in the Raft log before being appended to the in-memory queue. The Raft log is truncated periodically based on successful sink progress, while requests not yet applied on the quota/index shard are retained so they can be replayed after failures. Upon failure or leader change, the new leader replays the Raft log after the latest checkpoint to reconstruct the in-memory queue and resume the sink. Because checkpoints advance in batches, recovery may replay requests that have already been applied. To suppress such duplicates, each auxiliary update request carries a timestamp, which is recorded in the quota/index table to ensure that the same request is applied at most once. These mechanisms ensure that asynchronous auxiliary updates are neither lost nor applied more than once.

5.2 Conflict-Free Asynchronous Attribute Aggregation Directory tree modifications usually need to update parentdirectory attributes. For example, creating a file typically requires incrementing the num_children field and updating the modify_time field. A typical implementation often locks the parent-directory attribute record to ensure atomicity. Under high concurrency, a large number of modifications within the same directory contend on these shared attributes. MetaDB observes that these attribute updates (hotspots) have aggregatable semantics. For num_children, the final value is the sum of all deltas. For modify_time, the final value is the committed value with the largest timestamp. Thus, for concurrent modifications in the same directory, these attribute updates can be combined through aggregation. Based on this observation, MetaDB no longer synchronously updates parent-directory attribute records within transactions. Instead, it moves the updates of these attribute records off the critical path and updates them asynchronously. MetaDB first persists attribute changes in the Raft log for durability, then places them into an in-memory queue, where a background thread asynchronously aggregates them and writes them to the storage engine in batches. Specifically, num_children is aggregated by accumulating deltas, while modify_time is determined by maintaining the value committed with the largest timestamp. This design avoids hotspotattribute lock contention on the write path by removing at-

tribute updates from the foreground transaction. On the read path, before returning directory attributes to the client, the system merges persisted states with pending attribute changes in the in-memory queue, so that the client always reads the up-to-date values. Merging pending attribute changes in memory adds negligible latency. To ensure correctness, asynchronous attribute aggregation reuses the same asynchronous update framework with the same persistence guarantees as auxiliary metadata updates, ensuring that pending changes are neither lost nor applied more than once.

6

MVCC

Mark for deletion

MVCC GC

Slow Native RocksDB Compaction

Conventional MetaDB

Delete

Deleted

In-mem MVCC

Quick Delete directly

Deletion marker

Localityaware compaction

LSM tombstone

Figure 9: General architecture of preventing tombstones from accumulating in the LSM-tree-based storage engine.

Lifecycle-Aware Storage Engine

Our cloud object storage infrastructure experiences a massive volume of consecutive deletions driven by lifetime expiration policies and user-initiated purges. In a typical LSM-tree-based storage engine, these deletions trigger a rapid accumulation of tombstones, which degrades the latency of range scans like listdir. To resolve this Storage Implementation Mismatch, MetaDB redesigns the storage layer specifically for the lifecycle of metadata as shown in Figure 9. We introduce an in-memory MVCC mechanism to eliminate the persistence of redundant MVCC tombstones (§6.1) and a locality-aware compaction strategy to clean up LSM-tree tombstones (§6.2).

6.1

Delete

In-Memory MVCC

General-purpose distributed databases typically employ MVCC for concurrency control and LSM-trees for persistent storage [5, 15]. Under this architecture, a deletion operation first creates a logical MVCC tombstone, and the underlying LSM-tree then performs the physical deletion by writing its own tombstone. Because traditional databases must support long-running transactions, they routinely persist MVCC tombstones to disk. This creates a double-tombstone problem in which both MVCC and LSM-tree tombstones accumulate, significantly increasing read amplification. Because metadata transactions typically finish in a few milliseconds, MetaDB keeps multiple committed versions and MVCC tombstones only in memory. During a flush, the system prunes the in-memory multi-version state and persists only the latest committed state of each key to the persistent key-value store. For normal updates, this means writing only the latest committed version while discarding stale versions. For deletions, MetaDB does not persist the in-memory MVCC tombstone itself. Instead, it represents the deletion directly by committing an LSM-tree tombstone to persistent storage. As a result, MVCC tombstones do not accumulate in persistent storage, thereby eliminating the double-tombstone penalty and significantly reducing read amplification. Before flushing an in-memory table, MetaDB retains it slightly longer than the 5-second transaction timeout, so that all transactions that may still read its versions have completed. If a node fails before the flush completes, the committed

updates can be recovered by replaying the Raft log, whose entries are retained until the corresponding data have been durably persisted in the storage engine.

6.2

Locality-Aware Compaction

While in-memory MVCC eliminates redundant multi-version data, the underlying LSM-tree still generates one tombstone per deletion. Our production metadata workloads contain massive consecutive bulk deletions. These bulk operations generate long runs of consecutive tombstones that severely penalize the performance of range scans like listdir. Common LSM-tree compaction mechanisms are illequipped to handle this pattern. Native RocksDB compaction is triggered passively by level saturation. This delays tombstone cleanup and allows stale records to linger indefinitely [37]. Alternatively, forcing a full-shard compaction resolves the read amplification but incurs an unacceptable performance overhead for large database shards. To resolve this, we observe that consecutive metadata deletions exhibit strong spatial locality. Thus, instead of passively waiting for global thresholds or aggressively compacting entire shards, MetaDB dynamically tracks the specific key ranges experiencing heavy deletions. When the volume of deletions within a narrow tracked range surpasses a defined threshold, MetaDB proactively triggers a localized compaction strictly confined to that affected area. This targeted approach efficiently purges accumulated tombstones with minimal resource overhead. By cleaning up consecutive tombstones timely, MetaDB guarantees stable and predictable latency for range scans like listdir.

7 7.1

Evaluation Experimental Setup

In the experiments, we use the same type of machines as our production cluster. Our test cluster is configured with 4 BE nodes, 3 Manager nodes, and 3 Proxy nodes. Each node is configured with two Intel Xeon Platinum 8350C processors (64 cores), 256 GB of DDR4-2933 memory, one 480 GB

Coordinated Pushdown

Latency (ms)

9.94

10 5

0

2

4

6

8

Time (s)

10

12

14

0

16

7.2 Effectiveness of Tree-Topology-Induced Sharding and Execution Effectiveness of policy/size-based sharding. In this evaluation, we start with an empty directory, continuously create new files under it using four concurrent create operations, and record the throughput. Figure 10 compares the throughput of create under the same directory between size-based sharding and policy/size-based sharding. With size-based sharding, throughput drops from 6.0K QPS to 0.4K QPS after a split separates entries from the same directory. In contrast, policy/size-based sharding sustains 6.0K QPS throughout the run. This result shows that aligning shard boundaries with directory boundaries prevents common-case same-directory updates from turning into distributed transactions. Latency and throughput effect of single-shard transaction logic pushdown. We evaluate file creation using create under varying client loads, comparing coordinator-based execution with single-shard transaction logic pushdown. Each client has four threads where each thread creates files in a standalone directory to avoid lock contention on the directory’s attributes (§2.3). The average latency and throughput

0.74

1

2

4

71.10

40

0

8 16 32 64 28 56 1 2

4.40 4.00

1

2

Number of Clients

Figure 10: Throughput with create under the same directory.

4

8 16 32 64 28 56 1 2

Number of Clients

(a) Latency

(b) Throughput

Figure 11: Latency and throughput between coordinatorbased execution and pushdown for create. 60

QPS (K)

SATA SSD, one 4 TB NVMe SSD, and two 25 Gbps network connections. Each node runs CentOS 6.3 (Kernel 4.14.0). To comprehensively evaluate the performance benefits of MetaDB, we conduct a series of experiments using both synthetic microbenchmarks and real-world production traces. First, we separately examine the gains from our three core design pillars. Specifically, §7.2 evaluates the effectiveness of our tree-topology-induced sharding and transaction pushdown for single-directory operations. §7.3 shows how the semantic-aware off-critical-path processing improves system throughput under severe lock contention. §7.4 validates the lifecycle-aware storage engine and shows that it sustains stable, low latency for range scans during massive consecutive bulk deletions. Next, §7.5 evaluates the performance of MetaDB under stress tests in production environments. Finally, §7.6 shows nine representative production deployments, ratio of distributed transactions in two CFS and two Mantle clusters, tombstone dynamics on a production node, and production operation latency. We also compare the performance of MetaDB and TiDB in Appendix A.

60

20

0.99

0

91.60

Coordinated Pushdown

80

15.03

Txn Async

100 65.5

40 20 6.1

0

1 2 4 8 16 32 64 28 56 12 24 1 2 5 10

Number of Clients

Figure 12: Throughput of lock-based transactional operation execution and conflict-free asynchronous attribute aggregation.

#Pending items

QPS (K)

Size-based sharding Policy/size-based sharding

3

15

100

QPS (K)

20 6

4K 8K 16K

80 60 40 20 0

0

40

80

Time (s)

0

12

Figure 13: Number of pending quota updates in the asynchronous queue with asynchronous auxiliary updates over 120 s.

are shown in Figure 11. With a single client, logic pushdown achieves 25.3% lower latency and 10.0% higher throughput than coordinator-based execution, while with 256 clients, it achieves 33.9% lower latency and 28.8% higher throughput, respectively. This shows that single-shard transaction logic pushdown can reduce latency and increase throughput.

7.3 Effectiveness of Semantic-Aware OffCritical-Path Processing Effectiveness of conflict-free asynchronous attribute aggregation. In this experiment, we issue mkdir under the same directory with an increasing number of clients. Figure 12 compares the throughput of lock-based transactional operation execution (Txn) and conflict-free asynchronous attribute aggregation (Async) with concurrent mkdir under the same directory where each client sends four concurrent requests. Async achieves 10.7× the throughput of Txn, demonstrating that our asynchronous attribute aggregation can achieve higher throughput than lock-based transactional execution under high concurrency of operations in the same directory by avoiding contention on directory attributes. Latency of asynchronous updates. To quantify the lag between metadata updates and quota/index updates, we measure the number of pending quota updates at different create

#Tombstones (M)

14 12 10

Baseline +MEM-MVCC +Loc.Comp +All.Opti

8 6 4 2 0

0

30

60

90

Time (minutes)

120

150

Figure 14: Number of tombstones.

Avg latency (s)

6 5 4

Baseline +MEM-MVCC +Loc.Comp +All.Opti

3 2 1 0

0

30

60

90

Time (minutes)

120

150

140 120 100 80 60 40 20 0 0

Baseline +MEM-MVCC +Loc.Comp +All.Opti

30 60 90 120 150 Time (minutes)

2.0 #Reads (B)

#MVCC writes (M)

Figure 15: The effect on scan latency of bulk deletion.

1.5 1.0

Baseline +MEM-MVCC +Loc.Comp +All.Opti

0.5 0 0

30 60 90 120 150 Time (minutes)

Figure 16: Number of MVCC Figure 17: Number of comwrites. paction reads.

throughputs. Figure 13 shows the number of pending items in the asynchronous queue over a 120-second window at three throughput levels. The number of pending items increases with operation throughput, while the peak remains below 100. This indicates a latency of less than 10 ms at 16K QPS between the primary metadata being updated and the asynchronous updates being successfully sent to the remote shard. As the index and quota updates can tolerate minutes of latency after the primary metadata is updated, the latency cost of the asynchronous framework is acceptable even with high concurrency of metadata operations.

7.4 Effectiveness of Lifecycle-Aware Storage Engine To show how effectively in-memory MVCC reduces tombstone accumulation, we evaluate four configurations: ❶ Baseline: storage-backed MVCC with global compaction; ❷ MEM-MVCC: in-memory MVCC with global compaction; ❸ Loc.Comp: storage-backed MVCC with locality-aware compaction; and ❹ All.Opti: in-memory MVCC with locality-

aware compaction. We issue bulk deletions at 5K QPS while concurrently running a single listdir that returns 1K records. We record the number of tombstones in the storage engine, listdir latency, the number of KVs written to the storage engine, and the number of reads during compaction. Tombstone accumulation. Figure 14 shows the number of tombstones in the 150-minute experiment. Baseline accumulates tombstones rapidly, reaching 14M and continuing to grow as deletions proceed. With MEM-MVCC, the number of tombstones grows more slowly than Baseline. However, the count eventually reaches a similar level and fluctuates around 10M–12M, showing that RocksDB’s global compaction cannot clean up tombstones quickly enough since each compaction merges only two adjacent levels, leaving tombstones in the remaining levels untouched. Loc.Comp removes tombstones more frequently and completely, so it controls the tombstone count better than the previous two configurations, but the count still fluctuates between 1M and 8M. All.Opti achieves the most stable behavior. The number of tombstones remains consistently low, staying below 2M throughout the experiment, demonstrating the effectiveness of our design in preventing tombstone accumulation. Effect on listdir latency. Figure 15 shows the listdir latency under the same deletion workload as in Figure 14. Across all configurations, the listdir latency closely follows the tombstone accumulation trend. For both the Baseline and MEM-MVCC, the latency is higher and less stable than with the two locality-aware compaction configurations (Loc.Comp and All.Opti) as the number of tombstones accumulates, fluctuating around 5 s after sustained deletions. With Loc.Comp, listdir latency fluctuates between 1 s and 3 s. Enabling both MEM-MVCC and Loc.Comp (All.Opti) delivers the lowest and most stable latency, peaking at 0.7 s, matching the reduced tombstone counts observed earlier. This shows that our design can provide low and stable listdir latency by preventing tombstones from accumulating in LSM-tree-based storage. Reduction in KV writes with in-memory MVCC. Figure 16 shows the number of writes to the LSM-tree during the experiment, where writes grow as the total number of deletions increases over time. With in-memory MVCC enabled (MEMMVCC and All.Opti), the number of writes is about 60% lower than with storage-persisted MVCC (Baseline and Loc.Comp), showing that in-memory MVCC effectively reduces write volume, reducing write amplification. Impact on compaction reads. Figure 17 shows the number of reads from the LSM-tree during compaction. Loc.Comp has the highest number of reads since compaction is more frequently triggered in this configuration. With in-memory MVCC (MEM-MVCC and All.Opti), the number of reads is lower than that under the Baseline and Loc.Comp, owing to the reduced amount of data written to the LSM-tree.

1.3

0

6.2

22

.0

Delete QPS (K)

Table 1: Nine representative MetaDB deployments.

6 Delete QPS Tombstones

5 4

2

3 2

1

1 0

250

500

750

1000

1250

1500

1750

2000

0

Num Nodes

#Rec (B)

Max R QPS(K)

Max W QPS(K)

Data (PB)

Index gap

Time (minutes)

414 575 406 80 40 15 133 65 96

1,343 1,848 1,356 236 194 47 13 9 10

1,129 2,063 1,967 288 369 275 2,280 760 1,830

398 747 491 37 16 11 240 150 360

573 909 681 9 31 6 56 367 195

900 440 510 1610 1370 2110

Figure 19: Tombstones and delete throughput in production.

Overall Performance Stress Testing

We measure the latency and throughput in one production cluster with 10 BE nodes and issue metadata operations with mdtest, where mdtest is treated as a user in the corresponding cluster. For each test, we start 20 clients, each with 50 threads sending requests concurrently. Each client sends 2,000 requests in total. Figure 18 compares the latency and throughput of five metadata operations between the general-purpose database (GP-DB) and MetaDB. Compared with GP-DB, MetaDB reduces latency by 23.1%–75.0% and achieves 2.2×– 4.1× its throughput.

7.6

0.79 2.37 4.37 3.13

3

0

7.5

MetaDB (%)

100 100 100 100

4

(b) Throughput

Figure 18: Latency and throughput between general-purpose databases and MetaDB on our production cluster.

BOS1 BOS2 BOS3 CFS1 CFS2 CFS3 Mantle1 Mantle2 Mantle3

GP-DB (%)

CFS1 CFS2 Mantle1 Mantle2

mkdir dirstat rmdir createdelete

(a) Latency

ID

Workload .9

9.4

.5

23

6.7

3

30

0.0

10 .9

20

38

.5

40

Table 2: Multi-shard transaction ratios by workload.

GP-DB MetaDB

#Tombstones (M)

mkdirdirstatrmdircreatedelete

QPS (K)

1.0

1.0 0.2

0.25 0.00

0.6 0.3

0.50

.6

68

60

0.8

0.9

0.75

0.5

Latency (ms)

1.00

80

GP-DB MetaDB

1.25

0.4

1.50

MetaDB in Production

MetaDB has been deployed in production at Baidu for more than five years, unifying metadata management in distributed storage systems. Table 1 shows nine representative MetaDB deployments. BOS has the largest cluster among the three services, with ∼500 nodes, managing 1.3 to 1.8 trillion records and hundreds of PBs of data, with peaks of 2M read and 0.7M write QPS. CFS and Mantle are smaller than BOS in volume, with tens to hundreds of nodes, managing up to hundreds of billions of records, supporting up to 2M read and 360K write QPS. MetaDB can also handle extra-large shards. For example, the largest shards in the three CFS clusters are 179 GB, 38 GB and 52 GB, holding 901M, 142M and 194M records, respectively. The last column shows the maximum gap in the

number of queries between primary metadata updates and asynchronous index update requests being successfully sent to index shards, indicating that the latency of asynchronous updates is acceptable in the worst cases. To show that MetaDB can reduce the ratio of multi-shard transactions in production, we collect the ratio of multi-shard directory-modification transactions across four Mantle and CFS clusters, the two services with hierarchical namespaces, and report the results in Table 2. The fraction of multi-shard transactions drops from 100% to 0.79%–4.37%. For a file system built on the previous GP-DB, a single-directory modification touches records spread across multiple shards, and in Mantle it also updates a global quota index on another shard, so the modification becomes a multi-shard transaction. In contrast, MetaDB uses policy/size-based sharding to anchor a directory’s attributes and its direct children within the same shard (§4.1), and decouples asynchronous auxiliary updates to move quota and index updates off the transaction path (§5.1), so most single-directory modifications now stay within a single shard. The remaining fraction is higher in Mantle, where path resolution relies on additional index entries on other shards, so mkdir and rmdir span shards as well. In CFS, the only remaining multi-shard transactions come from cross-directory rename, whose ratio is low (Figure 1), so the fraction stays below 3%. Next, we show that the number of tombstones is well controlled in production. Figure 19 shows tombstone count and deletion throughput on a BE node that exhibits high deletion throughput in a BOS cluster which mainly serves ML training and search engines. The number of tombstones remains low, peaking at ∼6M and varying around 3M during continuous deletions mainly between 0.5K and 3K QPS. This shows that in-memory MVCC and locality-aware compaction can effectively control tombstone accumulation.

Avg latency (ms)

20 16 12 8 3 2 1 0

0

7

14

21

Time (day)

(a) GP-DB Avg latency (ms)

10

create

mkdir

delete

rmdir

dirstat

listdir

8 6 4 2 0

0

7

14

21

Time (day)

(b) MetaDB

Figure 20: Latency of the general-purpose database (GP-DB) and MetaDB in our production clusters over 21 days. To show the effect of MetaDB on latency in production, we trace the average latency of metadata operations on two CFS clusters for 21 days and show the results in Figure 20. Since most clusters are now running MetaDB, GP-DB only runs at a small scale, with 4 BE nodes, managing 1 billion directories and files. The MetaDB cluster has 50 BE nodes managing 50 billion directories and files. Both clusters primarily run large-scale data analysis workloads, such as bioinformatics and autonomous driving. MetaDB shows the largest improvement for listdir where the typical latency decreases from around 8–18 ms to 0.5–4 ms. The latencies of create, mkdir, delete, and rmdir drop from roughly 1.5 ms, 1.1 ms, 0.9 ms, and 0.8 ms under GP-DB to around 0.9 ms, 0.5 ms, 0.4 ms and 0.3 ms under MetaDB, respectively. MetaDB also shows a latency decrease in dirstat, where the latency decreases from around 0.5 ms to 0.4 ms. These results show the effectiveness of MetaDB in reducing operation latency in real production environments, even at a larger scale than GP-DB. It is worth noting that these production observations are not intended as strict performance comparisons.

8

Experiences and Lessons

Decoupling vs. Controlled Coupling? Decoupling directory management from the underlying database can increase the consistency-maintenance complexity and lead to redundant engineering. In an early hierarchical namespace design for object storage, we kept the directory indexing subsystem separate from the database, strictly enforcing the boundary between the directory semantic layer and the database layer. This separation caused two problems. First, operations such

as mkdir had to atomically update both the directory hierarchy in the indexing subsystem and the metadata records in the database, forcing a cross-system two-phase commit protocol with high engineering complexity. Second, the indexing subsystem had to implement its own replication, failure detection, and recovery, even though the database already provided these capabilities. We later integrated the directory indexing subsystem into MetaDB through internal tables and native transactions, allowing directory operations and metadata updates to complete within a single ACID transaction. This removed cross-system consistency issues, reused the database’s replication and recovery mechanisms, and saved roughly six months of work for a ten-engineer team. Building from Scratch vs. Modifying General-Purpose Distributed Databases? For metadata workloads, it is often better to build a simpler and more controllable specialized system than to deeply modify a large general-purpose database. Generation 2 (§2.2) showed these costs on a database we built ourselves, and AFS, our in-house HDFS-like file system, ran into the same mismatches (§2.3) on CockroachDB [40], which suggests the problem is not specific to one database. Adding metadata-specific mechanisms to such a system is costly. Mainstream open-source distributed transactional databases typically contain millions of lines of code [8, 15, 21], making invasive changes to their sharding, transaction, or storage layers expensive. Rather than keep modifying Generation 2, we therefore built MetaDB from scratch with RocksDB as the local storage engine. The codebase is ∼150K lines, less than one-tenth the size of comparable open-source distributed transactional databases. The trade-off is that when new requirements arise, we may need to implement features that a general-purpose database already provides. Because our metadata requirements and access patterns have changed little, this extra development cost has remained manageable. SQL Interface vs. Dedicated API? A metadata database can keep SQL for compatibility without running a general SQL engine. The storage services had accessed earlier metadata databases through SQL (§2.2), so keeping SQL eased their migration to MetaDB. In GP-DB, however, every request went through full parsing, semantic analysis, query optimization, and plan generation. The CPU cost was disproportionate to the metadata operations, since they use only ∼20 fixed SQL patterns. MetaDB therefore replaced the general SQL engine with a lightweight direct execution framework that maps each pattern to a storage execution path. Single Manager vs. Two-Tier Management? A control plane should be partitioned before shard growth makes it a bottleneck. Each shard has its own Raft group [14], as in CockroachDB [40], so the Manager’s heartbeat, reporting, replica scheduling, and routing workload grows with the shard count. A single cluster already holds millions of shards, and this number continues to grow. We therefore partitioned the physical cluster into independently managed Cells, each with a Local Manager for shard management. The Global Manager

maintains a small set of mappings from contiguous key ranges to Cells for global routing. For cross-Cell migration, it selects a range in the source Cell and coordinates with both Local Managers to move the shards in that range to the destination Cell’s BE nodes. Per-shard heartbeats and scheduling remain within each Cell, keeping the Global Manager off the per-shard control path. Central Services: Simplicity vs. Availability? A central service is simple to build, but on the critical path it can affect the whole cluster when it fails or is overloaded. In one incident, several Proxies crashed and restarted with empty routing caches, and their routing lookups overloaded the Manager. We therefore placed MetaCache, a scalable group of cache servers, in front of the Manager to serve these lookups. The TimeStamp Oracle (TSO) [35] in early versions of MetaDB had a similar risk. A TSO failure would block writes. We replaced it with a Hybrid Logical Clock (HLC) [24], which lets each node generate timestamps locally.

9

Related Work

Distributed Metadata Management. Some file systems build their own distributed metadata services. CephFS [42] and Lustre DNE [11] assign metadata to servers at subtree granularity and split a single directory across multiple metadata servers. CephFS also migrates subtrees according to runtime load. IndexFS [36] assigns metadata servers per directory and splits entries across servers with GIGA+ [34] as directories grow. LocoFS [26] separates directory metadata from file metadata to raise the throughput of file metadata operations. InfiniFS [27] colocates the parent directory’s content metadata with the metadata of its child files where possible, which reduces cross-node coordination for common updates. HopsFS [31] and Tectonic [33] build metadata services on general-purpose distributed databases, NDB [4] and ZippyDB [9] respectively. HopsFS typically partitions by parent directory ID, so the direct children of a directory reside in the same database shard. It uses row locks for isolation and twophase commit for atomic cross-shard updates. When many operations update the same directory, lock contention on the parent directory’s record limits throughput [31, 41]. Tectonic relies on shard-local atomic operations and does not guarantee atomic cross-directory rename. CFS [41] and Mantle [25], in contrast, run on MetaDB, a metadata-aware database (called TafDB in both papers), which lets common single-directory operations avoid cross-shard commits and reduces contention on parent directory attributes. The CFS and Mantle papers focus on the namespace layer. This paper presents the core design of the database beneath them and reports cross-service production evaluation and deployment experience. Distributed Databases. Most existing distributed databases are general-purpose systems rather than databases specialized for metadata workloads, such as Spanner [18], CockroachDB [5, 40], FoundationDB [7, 44], YugabyteDB [16],

TiDB [15, 21], DynamoDB [20, 23], and OceanBase [12, 43]. Unlike these systems, MetaDB is specialized around the semantics of metadata operations, including its sharding, transaction processing, and storage-engine behaviors. Asynchronous Auxiliary Metadata Maintenance. Prior work has used asynchronous index updates in databases to improve ingestion throughput, reduce synchronization overhead, or improve overall scalability [3, 28–30]. These works primarily focus on indexing performance or database scalability. In contrast, MetaDB uses asynchronous maintenance to restructure the metadata transaction path. It removes auxiliary metadata updates from the primary transaction by exploiting their relaxed timeliness requirements, thereby avoiding unnecessary multi-shard coordination. LSM-Tree-Based KV Store Deletion. Marked deletion degrades LSM-tree performance [13, 19]. Existing works enforce latency-bounded deletion for performance [37] or privacy [38, 45]. However, these retention-based strategies require intrusive engine modifications and incur high write amplification by eagerly compacting cold data. In contrast, MetaDB addresses this from the upper layer via localityaware compaction. Instead of rigid time windows, it targets deletion hotspots based on density. This triggers compaction only when necessary for read performance, avoiding the I/O overhead of time-driven approaches.

10

Conclusion

This paper presents MetaDB, a metadata-aware distributed database. MetaDB is co-designed around the file-system structural, semantic, and dynamic properties of metadata workloads. Our evaluation and deployment experience at Baidu show that this design substantially improves both performance and efficiency. MetaDB achieves 2.2×–4.1× the throughput of the previous general-purpose database, halves the number of metadata machines in production and sustains stable low latency for range scans under continuous bulk deletions. These results suggest that, for metadata management in storage systems, exposing and exploiting workload-specific structure inside the database is a key design principle for achieving both high performance and efficiency.

Acknowledgments We thank the anonymous reviewers and Jiancong Zheng for their insightful feedback. Zebin Ren is funded by the Dutch Research Council under grant numbers OCENW.KLEIN.561 and OCENW.KLEIN.209. We thank Meng Wang, Yongqiang Yang, Miao Yu, Xianhui Niu, Linjiang Lian, Guangjun Xie, Baolei Jia, and Pengfei Zheng for their contributions to the development of MetaDB. We also thank Rurue Ma, Chun Zhao, Yuhang Mu, and Liping Liu for their contributions to the development of MetaDB’s predecessor system.

References [1] Amazon s3. https://aws.amazon.com/s3/, Accessed: 2026-10-09. https://doris.apache.org, Ac[2] Apache doris. cessed: 2026-10-09. [3] Asynchronous indexing using hudi. https://www.onehouse.ai/blog/ asynchronous-indexing-using-hudi, Accessed: 2026-10-09. [4] Chapter 25 mysql ndb cluster 8.0. https: //dev.mysql.com/doc/refman/8.0/en/ mysql-cluster.html, Accessed: 2026-10-09. [5] Cockroachdb: Distributed sql for always-on customer experiences. https://www.cockroachlabs.com/, Accessed: 2026-10-09. [6] Colossus under the hood: a peek into google’s scalable storage system. https://cloud.google. com/blog/products/storage-data-transfer/ a-peek-behind-colossus-googles-file-system, Accessed: 2026-10-09. [7] Foundationdb gives you the power of acid transactions in a distributed database. https://www.foundationdb. org/, Accessed: 2026-10-09. [8] Github: Cockroachdb. https://github.com/ cockroachdb/cockroach, Accessed: 2026-10-09. [9] How we built a general purpose key value store for facebook with zippydb. https://engineering.fb. com/2021/08/06/core-infra/zippydb/, Accessed: 2026-10-09. [10] Kubeflow: The foundation of tools for ai platforms on kubernetes. https://www.kubeflow.org/, Accessed: 2026-10-09. [11] Lustre metadata service (mds). https://wiki. lustre.org/Lustre_Metadata_Service_(MDS), Accessed: 2026-10-09. [12] The multi-cloud distributed database for mission-critical workloads at any scale. https://en.oceanbase. com/, Accessed: 2026-10-09. [13] Rocksdb: A persistent key-value store for fast storage environments. https://rocksdb.org/, Accessed: 202610-09. [14] The design and implementation of multiraft. https://www.pingcap.com/blog/ design-and-implementation-of-multi-raft/, Accessed: 2026-10-09.

[15] Tidb, powered by pingcap. https://www.pingcap. com/, Accessed: 2026-10-09. [16] Yugabytedb: Distributed postgresql for modern apps. https://www.yugabyte.com/, Accessed: 2026-1009. [17] Benjamin Baron, Aline Bousquet, Eric Metens, Swapnil Pimpale, Nick Puz, Marc de Saint Sauveur, Varsha Muzumdar, and Vinay Ari. ACOS: apple’s geodistributed object store at exabyte scale. In André Brinkmann and Philip Shilane, editors, 24th USENIX Conference on File and Storage Technologies, FAST 2026, Santa Clara, CA, USA, February 24-26, 2026, pages 53–66. USENIX Association, 2026. [18] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson C. Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s globally-distributed database. In Chandu Thekkath and Amin Vahdat, editors, 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8-10, 2012, pages 251–264. USENIX Association, 2012. [19] Siying Dong, Andrew Kryczka, Yanqin Jin, and Michael Stumm. Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Trans. Storage, 17(4):26:1–26:32, 2021. [20] Mostafa Elhemali, Niall Gallagher, Nick Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somasundaram Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, and Akshat Vig. Amazon dynamodb: A scalable, predictably performant, and fully managed nosql database service. In Jiri Schindler and Noa Zilberman, editors, Proceedings of the 2022 USENIX Annual Technical Conference, USENIX ATC 2022, Carlsbad, CA, USA, July 11-13, 2022, pages 1037–1048. USENIX Association, 2022. [21] Dongxu Huang, Qi Liu, Qiu Cui, Zhuhe Fang, Xiaoyu Ma, Fei Xu, Li Shen, Liu Tang, Yuxing Zhou, Menglong Huang, Wan Wei, Cong Liu, Jian Zhang, Jianjun Li, Xuelian Wu, Lingyu Song, Ruoxi Sun, Shuaipeng Yu, Lei Zhao, Nicholas Cameron, Liquan Pei, and Xin Tang. Tidb: A raft-based HTAP database. Proc. VLDB Endow., 13(12):3072–3084, 2020.

[22] Kecheng Huang, Zhaoyan Shen, Zhiping Jia, Zili Shao, and Feng Chen. Removing double-logging with passive data persistence in lsm-tree based relational databases. In Dean Hildebrand and Donald E. Porter, editors, 20th USENIX Conference on File and Storage Technologies, FAST 2022, Santa Clara, CA, USA, February 22-24, 2022, pages 101–116. USENIX Association, 2022. [23] Joseph Idziorek, Alex Keyes, Colin Lazier, Somu Perianayagam, Prithvi Ramanathan, James Christopher Sorenson III, Doug Terry, and Akshat Vig. Distributed transactions at scale in amazon dynamodb. In Julia Lawall and Dan Williams, editors, Proceedings of the 2023 USENIX Annual Technical Conference, USENIX ATC 2023, Boston, MA, USA, July 10-12, 2023, pages 705–717. USENIX Association, 2023. [24] Sandeep S. Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone. Logical physical clocks. In Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro, editors, Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Cortina d’Ampezzo, Italy, December 16-19, 2014. Proceedings, volume 8878 of Lecture Notes in Computer Science, pages 17–32. Springer, 2014. [25] Jiahao Li, Biao Cao, Jielong Jian, Cheng Li, Sen Han, Yiduo Wang, Yufei Wu, Kang Chen, Zhihui Yin, Qiushi Chen, Jiwei Xiong, Jie Zhao, Fengyuan Liu, Yan Xing, Liguo Duan, Miao Yu, Ran Zheng, Feng Wu, and Xianjun Meng. Mantle: Efficient hierarchical metadata management for cloud object storage services. In Youjip Won, Youngjin Kwon, Ding Yuan, and Rebecca Isaacs, editors, Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles, SOSP 2025, Lotte Hotel World, Seoul, Republic of Korea, October 13-16, 2025, pages 928–943. ACM, 2025. [26] Siyang Li, Youyou Lu, Jiwu Shu, Yang Hu, and Tao Li. Locofs: a loosely-coupled metadata service for distributed file systems. In Bernd Mohr and Padma Raghavan, editors, Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017, Denver, CO, USA, November 12 - 17, 2017, page 4. ACM, 2017. [27] Wenhao Lv, Youyou Lu, Yiming Zhang, Peile Duan, and Jiwu Shu. Infinifs: An efficient metadata service for large-scale distributed filesystems. In Dean Hildebrand and Donald E. Porter, editors, 20th USENIX Conference on File and Storage Technologies, FAST 2022, Santa Clara, CA, USA, February 22-24, 2022, pages 313–328. USENIX Association, 2022. [28] Ajit Mathew and Changwoo Min. Hydralist: A scalable in-memory index using asynchronous updates and par-

tial replication. Proc. VLDB Endow., 13(9):1332–1345, 2020. [29] Syed Akbar Mehdi, Deukyeon Hwang, Simon Peter, and Lorenzo Alvisi. Scaledb: A scalable, asynchronous inmemory database. In Roxana Geambasu and Ed Nightingale, editors, 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023, Boston, MA, USA, July 10-12, 2023, pages 361–376. USENIX Association, 2023. [30] Xiao Mo and Hao Wang. Asynchronous index strategy for high performance real-time big data stream storage. In 3rd IEEE International Conference on Network Infrastructure and Digital Content, IC-NIDC 2012, Beijing, China, September 21-23, 2012, pages 232–236. IEEE, 2012. [31] Salman Niazi, Mahmoud Ismail, Seif Haridi, Jim Dowling, Steffen Grohsschmiedt, and Mikael Ronström. Hopsfs: Scaling hierarchical file system metadata using newsql databases. In Geoff Kuenning and Carl A. Waldspurger, editors, 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017, pages 89–104. USENIX Association, 2017. [32] Diego Ongaro and John K. Ousterhout. In search of an understandable consensus algorithm. In Garth Gibson and Nickolai Zeldovich, editors, Proceedings of the 2014 USENIX Annual Technical Conference, USENIX ATC 2014, Philadelphia, PA, USA, June 19-20, 2014, pages 305–319. USENIX Association, 2014. [33] Satadru Pan, Theano Stavrinos, Yunqiao Zhang, Atul Sikaria, Pavel Zakharov, Abhinav Sharma, Shiva Shankar P., Mike Shuey, Richard Wareing, Monika Gangapuram, Guanglei Cao, Christian Preseau, Pratap Singh, Kestutis Patiejunas, J. R. Tipton, Ethan Katz-Bassett, and Wyatt Lloyd. Facebook’s tectonic filesystem: Efficiency from exascale. In Marcos K. Aguilera and Gala Yadgar, editors, 19th USENIX Conference on File and Storage Technologies, FAST 2021, February 23-25, 2021, pages 217–231. USENIX Association, 2021. [34] Swapnil Patil and Garth A. Gibson. Scale and concurrency of GIGA+: file system directories with millions of files. In Gregory R. Ganger and John Wilkes, editors, 9th USENIX Conference on File and Storage Technologies, San Jose, CA, USA, February 15-17, 2011, pages 177–190. USENIX, 2011. [35] Daniel Peng and Frank Dabek. Large-scale incremental processing using distributed transactions and notifications. In Remzi H. Arpaci-Dusseau and Brad Chen, editors, 9th USENIX Symposium on Operating Systems

Design and Implementation, OSDI 2010, October 4-6, 2010, Vancouver, BC, Canada, Proceedings, pages 251– 264. USENIX Association, 2010.

editors, Proceedings of the Eighteenth European Conference on Computer Systems, EuroSys 2023, Rome, Italy, May 8-12, 2023, pages 331–346. ACM, 2023.

[36] Kai Ren, Qing Zheng, Swapnil Patil, and Garth A. Gibson. Indexfs: Scaling file system metadata performance with stateless caching and bulk insertion. In Trish Damkroger and Jack J. Dongarra, editors, International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2014, New Orleans, LA, USA, November 16-21, 2014, pages 237–248. IEEE Computer Society, 2014.

[42] Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos Maltzahn. Ceph: A scalable, high-performance distributed file system. In Brian N. Bershad and Jeffrey C. Mogul, editors, 7th Symposium on Operating Systems Design and Implementation (OSDI ’06), November 6-8, Seattle, WA, USA, pages 307– 320. USENIX Association, 2006.

[37] Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, and Manos Athanassoulis. Lethe: A tunable delete-aware LSM engine. In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 893–908. ACM, 2020. [38] Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. Enabling timely and persistent deletion in lsm-engines. ACM Trans. Database Syst., 48(3):8:1–8:40, 2023. [39] John Shawger, Arnav Jhingran, Andrea C. ArpaciDusseau, and Remzi H. Arpaci-Dusseau. XLL: crosslayer logging for data deduplication in consensus-based storage. In Srikanth Kandula and Hakim Weatherspoon, editors, 23rd USENIX Symposium on Networked Systems Design and Implementation, NSDI 2026, Renton, WA, May 4-6, 2026, pages 2619–2634. USENIX Association, 2026. [40] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. Cockroachdb: The resilient geo-distributed SQL database. In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 1493–1509. ACM, 2020. [41] Yiduo Wang, Yufei Wu, Cheng Li, Pengfei Zheng, Biao Cao, Yan Sun, Fei Zhou, Yinlong Xu, Yao Wang, and Guangjun Xie. CFS: scaling metadata service for distributed file system via pruned scope of critical sections. In Giuseppe Antonio Di Luna, Leonardo Querzoni, Alexandra Fedorova, and Dushyanth Narayanan,

[43] Zhenkun Yang, Chuanhui Yang, Fusheng Han, Mingqiang Zhuang, Bing Yang, Zhifeng Yang, Xiaojun Cheng, Yuzhong Zhao, Wenhui Shi, Huafeng Xi, Huang Yu, Bin Liu, Yi Pan, Boxue Yin, Junquan Chen, and Quanqing Xu. Oceanbase: A 707 million tpmc distributed relational database system. Proc. VLDB Endow., 15(12):3385–3397, 2022. [44] Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton, Andrew J. Beamon, Rusty Sears, John Leach, Dave Rosenthal, Xin Dong, Will Wilson, Ben Collins, David Scherer, Alec Grieser, Young Liu, Alvin Moore, Bhaskar Muppana, Xiaoge Su, and Vishesh Yadav. Foundationdb: A distributed unbundled transactional key value store. In Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava, editors, SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, pages 2653–2666. ACM, 2021. [45] Zichen Zhu, Subhadeep Sarkar, and Manos Athanassoulis. Acheron: Persisting tombstones in LSM engines. In Sudipto Das, Ippokratis Pandis, K. Selçuk Candan, and Sihem Amer-Yahia, editors, Companion of the 2023 International Conference on Management of Data, SIGMOD/PODS 2023, Seattle, WA, USA, June 18-23, 2023, pages 131–134. ACM, 2023.

Number of Clients

6

8

25

64

12

1

6

8

1.2

25

64

12

32

8

16

4

2

1

0

43.4

32

38.2

20

TiDB MetaDB

8

40

45 40 35 30 25 20 15 10 5 0

16

60

QPS (K)

QPS (K)

85.6

4

TiDB MetaDB

80

Number of Clients

Figure 21: Operation throughput with index updates with different concurrencies.

Figure 22: Throughput of operations under the same directory with different concurrencies.

3.0 TiDB MetaDB

Latency (s)

2.5 2.0 1.5 1.0 0.5 0.0

0

30

60

Time (minutes)

90

120

Figure 23: listdir latency with concurrent consecutive bulk deletion between TiDB and MetaDB.

A

Performance Comparison with TiDB

The TiDB version evaluated here requires a newer operatingsystem version than the one deployed in our production cluster. Thus, we set up a separate environment with a different set of machines for the experiments in this appendix. The MetaDB cluster is configured with 4 BE nodes, 3 Manager nodes, and 3 Proxy nodes, and the TiDB cluster is configured with 4 TiKV nodes, 3 PD nodes, and 3 TiDB nodes for TiDB v8.1. Both clusters contain the same type of machines, where each node is configured with two Intel Xeon 4314 processors (32 cores), 128 GB of DDR4-3200 memory, 8×4 TB NVMe SSDs, and two 25 Gbps network connections. Each node runs CentOS 7.5 (Kernel 4.14.0). Figure 21 compares the throughput of create with index updates between TiDB and MetaDB, where TiDB updates the index atomically with the primary metadata update within the same transaction and MetaDB updates the index asynchronously, and each client sends four concurrent requests. The throughput of MetaDB with 256 clients is 85.6K QPS, which is 2.2× TiDB’s throughput with 256 clients. This shows that our asynchronous index framework can deliver higher throughput than updating indexes atomically using transactions. Next, we compare the throughput between TiDB and MetaDB with concurrent mkdir under the same directory where each client sends four concurrent requests and present their throughput in Figure 22. MetaDB has better scalability

than TiDB, achieving 36.2× the peak throughput of TiDB for operations that modify the same row (i.e., the parent directory’s attribute). This demonstrates that MetaDB can achieve higher throughput than general-purpose databases under contention from concurrent operations within the same directory. Figure 23 compares the latency of listdir running concurrently with object deletions at 5K QPS on MetaDB and TiDB. MetaDB’s listdir latency stays below 0.7 s, which is lower and more stable than TiDB’s latency that peaks at 2.5 s and stays between 1 s and 2.5 s after the tombstones have accumulated for 30 minutes. This demonstrates that MetaDB is more effective at controlling listdir latency during consecutive bulk deletions than TiDB.

Related documents

• MetaDB: Putting File-System Structure Back into Distributed Databases#1447614
• Understanding Network File Systems (NFS): Architecture, Variations, and Implementation#77565
• SLFS: a Flexible, Low-Cost Distributed File System Using Serverless Designs#332500
• Specification and verification of isolation levels in distributed storage systems#1399425
• Icicle: Scalable Metadata Indexing and Real-Time Monitoring for HPC File Systems#10320