arXiv CS open access

DiaLSM: Towards Write-Stall-Free Performance via Shard-based LSM-tree

· arxiv_cs

arXiv CS · Papers

Log-Structured Merge-tree (LSM) aims to achieve high write throughput, but is known to experience the write stall problems when subjected to sustained write pressure. We quantify the occurrence probability and average duration of write stalls in LSM using a queuing model in the write--flush--compact

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

D IA LSM: Towards Write-Stall-Free Performance via Shard-based LSM-tree 2

Sungyong Park

Abstract—Log-Structured Merge-tree (LSM) aims to achieve high write throughput, but is known to experience the write stall problems when subjected to sustained write pressure. We quantify the occurrence probability and average duration of write stalls in LSM using a queuing model in the write–flush– compaction pipeline, moving beyond existing empirical analysis. The proposed model demonstrates that a monolithic LSM with a single pipeline cannot eliminate write stalls, revealing that internal sharding within the LSM offers an opportunity for fundamental write stall mitigation. To break this structural bottleneck, we propose D IA LSM, an internally shard-based LSM architecture. Instead of forcing all writes through one pipeline, D IA LSM splits the write–flush– compaction path into multiple independent shards and employs dynamic fallback redirection, allowing writes to proceed even when some shards stall. Implemented on RocksDB, D IA LSM achieves up to 2.4× higher throughput, 94% lower stalls, and significantly lower latency than state-of-the-art methods ADOC and Sub-Compaction, as demonstrated by db bench, YCSB, and Sysbench OLTP evaluations. Index Terms—Log-Structured Merge-tree, Key-Value Store, Modeling

I. I NTRODUCTION Monolithic LSM tree. Log-Structured Merge-tree (LSM tree) [1] is a write-optimized data structure widely used in NoSQL systems such as LevelDB [2], RocksDB [3], and Cassandra [4]. Although LSM trees are often described by data layout and compaction policies, they form a tightly coupled data pipeline. Incoming writes are first buffered in a Memtable, flushed as immutable SSTables to Level 0 (L0), and incrementally compacted into lower levels (L1–Ld) to maintain key order and control storage amplification. Crucially, these stages—write buffering, flushing, and compaction—are not independent. As illustrated in Figure 1, they are organized as a single, monolithic pipeline, where progress at each stage directly depends on the throughput of downstream stages. This architectural coupling, rather than any specific compaction policy or parameter choice, forms the structural foundation on which subsequent performance limitations arise. Write Stall. The core advantage of the LSM tree is that it provides stable write performance even under frequent random writes by relying on sequential writes and deferred sorting through background compaction. However, ironically, once the write load exceeds a certain threshold, the LSM tree can no longer accept writes and instead triggers a write stall [5]–[11] that blocks write requests. In this state, foreground write I/O ∗ This work was conducted while the author was at Sogang University. † Y. Kim is the corresponding author.

Layer

Korea Aerospace University, 2 Sogang University, 3 MangoBoost, 4 ETRI, 5 Temple University, 6 Arizona State University hsbyun@kau.ac.kr, {yhh, parksy, youkim}@sogang.ac.kr, safdar.jamil@mangoboost.io, mclee@etri.re.kr, xubin.he@temple.edu, zhichao.cao@asu.edu Write

Memory

Memtable (M)

Level 0

SST 1 (Ssst)

Memtable Growth Rate: λ - µflush Flush Rate: µflush

Immutable Memtable

…

SST N-trigger

…

Level d (d ≥ 1)

SST

…

SST

… ΔN

SST N-Stall

L0 Growth Rate: µflush - µcmp0(c0)

L0 Compaction Rate: µcmp0(c0)

…

arXiv:2609.14370v1 [cs.DB] 13 Sep 2026

Hongsu Byun1, ∗ , Safdar Jamil3 , Honghyeon Yoo2 , , Myungcheol Lee4 , Xubin He5 , Zhichao Cao6 , Youngjae Kim2, †

…

SST

Backlog Growth Rate: k·µcmp0(c0) - µcmpd(cd) Ld Compaction Rate: µcmpd(cd) (k ≤ 1)

Fig. 1: Description of the data pipeline in a monolithic LSM tree architecture. Layer refers to the Memtable and levels.

is blocked until internal flush or compaction operations make progress, temporarily preventing the system from responding to external requests and causing high latency. Depending on which layer of the internal pipeline, such as the Memtable, Level 0, or deeper levels, becomes the bottleneck, different types of stalls occur, leading paradoxically to a situation in which a write-optimized LSM tree halts its own writes under heavy workloads. Limitations of the Monolithic LSM tree. Existing solutions have proposed various techniques to mitigate write stalls. For example, ADOC [5] adjusts the Memtable size and the number of compaction threads, while Sub-Compaction [12] parallelizes L0-to-L1 compaction to better reduce compaction pressure at L0. Although these approaches reduce the frequency or duration of write stalls at specific layers, they share a fundamental limitation in that they operate within the structural constraint of a single LSM pipeline. That is, while they can change where and to what extent stalls occur, they cannot eliminate write stalls entirely. Modeling for Write Stall. Write stalls are not a problem of a suboptimal implementation or tuning heuristics, but a phenomenon that appears across the monolithic LSM tree architecture. However, empirical analysis [5], [10] alone is insufficient to explain why write stall persists and why it cannot be eliminated under any conditions. To systematically understand this behavior, we introduce a model that enables mathematical analysis of the LSM tree write path. We view the LSM tree write path, consisting of write– flush–compaction, as a single execution pipeline, and model situations in which foreground write processing is temporarily suspended due to flush or compaction using the notion of vacations in queueing theory [13]. The goal of this model

is not parameter tuning or performance prediction, but to show that write stalls are structurally inevitable as long as the single LSM pipeline structure is maintained. The detailed modeling in Section II-A explains why write stalls cannot be eliminated in monolithic LSM trees and derives why a new design direction is required. Sharding as a Structural Solution. To overcome limitation of monolithic LSM tree, we revisit sharding [14]–[17]— a proven scalability technique in distributed databases. By applying sharding within a single LSM instance, we decompose the write–flush–compaction pipeline into multiple independent pipelines, dramatically reducing stall probability and improving robustness. This allows write traffic to be loadbalanced and redirected across shards, ensuring progress even if individual shards stall. D IA LSM. In this paper, we present D IA LSM (DiamondLSM), a shard-based LSM architecture that structurally departs from the monolithic model. Like a diamond with many facets, D IA LSM partitions a single logical tree into multiple internal LSM shards. It significantly reduces write stalls in practice through two mechanisms: hash-based load balancing and the redirection of stalled writes to fallback shards. While theoretical corner cases exist where all shards might stall, in practice, this is extremely rare, making stalls negligible in frequency compared to monolithic designs. Challenges. With this structural shift, several core aspects that are naturally supported in monolithic LSM-trees require rethinking and redesign in a shard-based architecture, leading us to address the following critical challenges: • Indexing for Fallback Shards. Redirected writes complicate lookup processing, as keys may reside outside their primary shards. A mechanism is required for looking up keys located outside the primary shard. • Ensuring Read Latency. Lookups across primary and fallback shards can add extra latency. Read performance must also be guaranteed at the level of traditional LSM-tree. • Preserving Ordering. Hash-based sharding disrupts key locality, making it challenging to support ordered access patterns like range queries. • Providing Robustness. When a system crash occurs during redirection writing, data consistency may be broken. Failure recovery and consistency maintenance must be ensured. Contributions. This paper makes the following contributions. • We quantify write stall occurrence based on a queueing model in a monolithic LSM-tree with a single pipeline structure (§II-A). • We demonstrate that existing techniques induce cross-layer balloon effects, preventing write stall elimination (§II-B), and highlight the need for structural alternatives to fundamentally mitigate write stalls (§II-C). • We propose D IA LSM, a shard-based LSM design that significantly reduces write stalls through dynamic fallback writes, while introducing Clue Entries (CEs), lightweight pointers stored in primary shards to track redirected keys even during stall conditions (§III).

• We design a set of mechanisms that enable shard-based LSM by preserving global ordering, efficient range queries, and consistency, including CE L0 capping and CE caching to reduce lookup latency, parallel iterators without extra storage, and garbage collection and rollback policies to restore data to primary shards. We implemented D IA LSM atop RocksDB v8.3.2 and evaluated it with db bench and YCSB benchmark. In the FillRandom workload, D IA LSM reduced write stalls by 94.3% and achieved 2.4× higher throughput and 50% lower latency than ADOC. In the ReadRandomWriteRandom workload, it delivered 1.8× higher throughput. Across all YCSB workloads, D IA LSM outperformed ADOC, with up to 8.9× gains on YCSB-E due to improved range query performance. Furthermore, in Sysbench-based OLTP evaluations on RocksDBbased RDBMSs, D IA LSM achieves 2.2× higher throughput than ADOC under mixed read/write workloads. II. M ODELING W RITE S TALLS IN LSM TREES Empirical analysis [5]–[7], [10] cannot fully explain the underlying dynamics of LSM tree write stalls, as the interactions among buffering, flushing, and compaction are tightly coupled. To capture these dynamics systematically, we adopt a mathematical analysis model. This abstraction allows us to classify stall types, derive their occurrence characteristics, and establish closed-form expressions for stall time — laying the foundation for analysis and stall-mitigation design. The modeling is explained based on Figure 1. A. Vacation Queuing Model for LSM trees In LSM trees, write stalls correspond to periods during which write requests are temporarily blocked. In queuing theory, such interruptions are referred to as vacations [18], [19]. If a stall caused by flush or compaction is interpreted as the system “taking a break,” then the LSM write path can be naturally modeled as a vacation-based queuing system [13]. Since a vacation directly corresponds to a write stall, hereafter we will refer to a stall as a vacation. Three Types of Vacations. Write stalls are categorized into three types, depending on the layer where the bottleneck occurs in the LSM [5], [7], [20]. (1) Memtable Stall, (2) L0 Stall, and (3) Pending Stall. These three types of stall are characterized by their frequency (how often they occur) and duration (how long each stall lasts), both of which depend on specific system parameters such as Memtable size, L0 thresholds, and the number of background threads. Interdependent Pipelines. A key insight is that the three stages–write buffering, flushing, compaction–are not independent. Optimizations at one stage directly impact the others: (i) increasing flush throughput immediately reduces Memtable stalls but also injects data into L0 faster, thereby increasing L0-stall frequency; (ii) increasing L0 compaction throughput lowers L0 stalls but pushes data downstream faster, which increases the pressure on lower levels (raising pending stalls); moreover, under shared CPU/IO resources, allocating more to L0 compaction can reduce effective flush throughput, thereby

increasing Memtable stalls. This interdependency is precisely why a unified vacation model is necessary: it lets us reason about stalls as coupled phenomena rather than isolated events. Poisson Arrival Process. To characterize the write arrival pattern, we observe that in production key-value workloads such as Facebook’s RocksDB, the coefficient of variation (CV) of write inter-arrival times is close to 1 [21]–[23]; a CV near 1 indicates an exponential, memoryless distribution [24]. Because LSM stores receive writes from many independent and sparse client threads, the Palm-Khintchine theorem [25] implies that their superposition converges to a Poisson process [26]. We therefore model the LSM arrival process as Poisson with mean rate λ. Memtable Stall. Let the write arrival rate be λ(MB/s), the size of the active Memtable be M (MB), and the flush processing rate be µflush (MB/s). A Memtable stall occurs when the next Memtable becomes full before the flush of the previous one has completed, which happens under the condition λ > µflush . Accordingly, the average stall duration E[V (Mem) ](sec) and (Mem) (stalls/s) are given as follows: the frequency λv E[V (Mem) ] =

λ − µflush M , λ(Mem) = v µflush M

(1)

L0 Stall. In an LSM tree, L0-to-L1 compaction is triggered when the number of SSTables in L0 exceeds the compaction threshold Ntrigger (default1 : 4 SSTables). However, if the flush rate µflush continues to exceed the L0-to-L1 compaction rate µcmp0 (c0 )(MB/s) during compaction, the number of SSTables in L0 eventually reaches the write stall threshold Nstall (default: 36 SSTables). Here, c0 denotes the number of compaction threads assigned to L0 compaction. Since L0-to-L1 compaction is typically not parallelized, c0 = 1 by default. Let ∆N = Nstall − Ntrigger denote the gap between the two thresholds. To trigger an L0 stall, this gap must be filled with additional files at a net growth rate of µflush − µcmp0 (c0 ). Assuming the average size of an SSTable is SSST , the time required to accumulate ∆N · SSST corresponds to the average time between L0 stalls. The time to drain this accumulated data at rate µcmp0 (c0 ) corresponds to the stall duration. Accordingly, the average duration E[V (L0) ](sec) and frequency (L0) λv (stalls/s) of L0 stalls are given as follows: E[V (L0) ] =

µflush − µcmp0 (c0 ) ∆N · SSST , λ(L0) = v µcmp0 (c0 ) ∆N · SSST

(2)

Pending Stall. Let k · µcmp0 (c0 ) denote the rate at which data is pushed from L0 to deeper levels (Ld), and let µcmpd (cd )(MB/s) denote the compaction rate at Ld. Here, k represents the fraction of data retained after duplicate removal during L0-to-L1 compaction. The difference in these rates, k · µcmp0 (c0 ) − µcmpd (cd ), determines the rate at which the pending compaction backlog grows. When the backlog size exceeds a threshold Bth , a pending stall occurs. Assuming that a pending stall is cleared once Spend bytes from the accumulated backlog are processed at the Ld compaction rate, the average stall duration E[V (Pend) ](sec) and frequency 1 Hereafter, this default refers to the default configuration in RocksDB.

(Pend)

λv

(stalls/s) are given as follows:

E[V (Pend) ] =

k · µcmp0 (c0 ) − µcmpd (cd ) Spend , λ(Pend) = v µcmpd (cd ) Bth (3)

Base Stall Model. So far, we have modeled the durations of the three types of stalls using a vacation-based approach. By incorporating these stalls into an M/G/1 queue–Poisson arrivals (M), general service time (G), and a single server (1)– the average base stall time E[B]base is given as follows:  (Mem)  λv E[V (Mem) ] (Memtable Stall)   λ   E[B]base =  + λ(L0)  E[V (L0) ] (L0 Stall) v 1−ρ   (Pend) + λ(Pend) E[V ] (Pending Stall) v (4)

ρ = λ E[S] < 1

Here, λ denotes the average arrival rate, and E[S] represents the average service time required to safely record a request in the Memtable. The system utilization is given by ρ = λE[S]. λ is a correction factor derived from the mean The term 1−ρ residual time law of the M/G/1 queue, reflecting the fact that when the server is utilized at rate ρ, the queuing delay is 1 amplified by a factor of 1−ρ [27]. Finally, we define α as the probability that the LSM tree encounters a stall at an arbitrary time, and V̄ as the mean stall duration. Based on these definitions, α, V̄ , and E[B]base are expressed as follows.   (Mem) E[V ] i h (Pend) (L0) (L0)   , V̄ = α = λ(Mem) E[V ] λ λ v v v E[V (Pend) ] E[B]base =

λ α V̄ 1−ρ

(5) (6)

Coupling and Trade-offs. The model makes the interdependencies explicit. From the stall-frequency expressions, ∂λ(Mem) /∂µflush = −1/M < 0, v

(7)

∂λ(L0) /∂µflush = 1/(∆N SSST ) > 0 v

(8)

Thus, (i) raising µflush reduces Memtable stalls but increases L0 stalls; and (ii) raising µcmp0 reduces L0 stalls but increases pending stalls (and, under shared resource constraints, may also reduce µflush , increasing Memtable stalls). In practice, µflush , µcmp0 , and µcmpd are coupled through a bounded CPU/IO budget; allocating more threads or bandwidth to one stage typically reduces the effective throughput of another. B. The Limitations of Monolithic LSM-trees Armed with this model, we now analyze how two orthogonal state-of-the-art techniques — Sub-Compaction [12] and ADOC [5] — impact E[B]base , yet cannot eliminate stalls. Sub-Compaction. RocksDB reduces L0 stalls by parallelizing L0-to-L1 compaction. Each SSTable’s key range is partitioned into anchor points, with threads compacting independently [12]. This mitigates the sequential bottleneck from overlapping ranges. SC Under our model, the effective throughput is: µcmp0 (c0 ) = µcmp0 (1) p , where p is the parallelizable fraction. However, (1−p)+ c0

µcmp0 =100MB/s

µcmp0 =200MB/

(64MT, 1Sub) (512MT, 2Sub)

(512MT, 1Sub) (512MT, 8Sub)

0.5 0.0

µcmp0 =600MB/s

1.0

1.0 L0 Stall (stalls/s)

Memtable Stall (stalls/s)

Projection : Observation :

100

200 µflush (MB/s)

0.5 0.0

300

100

200 µflush (MB/s)

300

(a) Memtable and L0 Stall with L0 compaction throughput (µcmp0 ) µflush =250MB/s (64MT, 1Sub) (512MT, 2Sub)

0.5 0.0

µflush =300MB/s (512MT, 1Sub) (512MT, 8Sub)

1.0

1.0 L0 Stall (stalls/s)

Memtable Stall (stalls/s)

Projection : Observation :

100

300 500 µcmp0 (MB/s)

0.5 0.0

700

100

300 500 µcmp0 (MB/s)

700

(b) Memtable and L0 Stall with flush throughput (µflush )

Fig. 2: Model predictions and actual observations of write stalls under different flush and compaction throughputs.

(1)

by Amdahl’s law, throughput is capped at cmp0 1−p . While Sub-Compaction lowers L0 stall frequency and duration, it also increases downstream injection rate k µcmp0 , thereby rais(Pend) unless deeper-level coming pending-stall frequency λv paction scales proportionally. Moreover, if compaction threads contend for shared IO/CPU, the effective µflush may drop, raising Memtable-stall frequency. Hence, Sub-Compaction improves one stage at the cost of others. ADOC. ADOC [5] adaptively tunes Memtable size M and compaction threads c = c0 + cd : • Increasing M reduces Memtable stall by lowering flush frequency, but yields larger SSST , damping µcmp0 and increasing L0 stall. • Increasing c0 accelerates L0 compaction, reducing L0 stalls but increasing pending stalls via higher k µcmp0 and, under contention, Memtable stalls via lower effective µflush . • increasing cd mitigates pending stalls, but under a fixed resource budget can reduce µflush or µcmp0 , raising Memtable or L0 stalls. Thus, ADOC’s decoupled heuristics induce a balloon effect: mitigating one stall type often exacerbates another. It lacks a unified mechanism to eliminate stalls altogether. Preliminary Modeling Results and Analysis. The proposed write stall model enables us to understand how the interaction between flush and compaction produces stalls. Figure 2 presents the model’s predictions and the results obtained from RocksDB using the db bench’s FillRandom 8 KB workload(same as § IV) under different flush and compaction throughputs. The lines indicate the predicted values of our TABLE I: Validation of the Model. Stall (stalls/s)

64MT, 1Sub

512MT, 1Sub

512MT, 2Sub

512MT, 8Sub

MT Stall

Obs. Pred.

0.094 0.11

0.12 0.11

0.24 0.24

0.63 0.63

L0 Stall

Obs. Pred.

0.81 0.83

0.75 0.83

0.58 0.45

0 0

write stall model, while the circles represent actual measurements under varying system parameters. To clearly observe the interaction between the two dominant types of write stalls—Memtable stalls and L0 stalls—we conducted experiments under conditions where pending stalls do not occur. In all graphs, the y-axis reports the average ratio of stall duration to total execution time, expressed as stalls per second (stalls/s). Figure 2(a) shows stall trends when µcmp0 is fixed and µflush increases. Here, increasing µflush along the x-axis corresponds to changes in Memtable size under ADOC. As the three observed points suggest, lighter circles indicate reduced Memtable stalls but increased L0 stalls. In other words, while the degree of Memtable and L0 stalls varies with system parameters, the overall stalls never disappear—a balloon effect is observed. The measurements lie close to the model’s predictions for the three values of µcmp0 . Figure 2(b) depicts stall behavior when µflush is fixed and µcmp0 increases, as the number of Sub-Compaction threads grows. Here, the trend reverses: L0 stalls decrease while Memtable stalls increase, revealing the balloon effect. All measurements closely match the model’s predictions for the two values of µflush . This balloon effect reveals a fundamental limitation: optimizations such as ADOC or Sub-Compaction only shift the stall bottleneck between levels, but can never eliminate stalls entirely. Model Validation. The accuracy of the proposed model is validated in the contexts of Sub-Compaction and ADOC. Validation is based on the experimental and observed values presented in Figure 2. Table I compares predicted and observed write stall rates. The model achieves a mean absolute error (MAE) of 0.03 stalls/s in predicting both Memtable and L0 stall rates, while consistently capturing the balloon effect between the two stall types. C. Opportunity: LSM Sharding The preceding analysis shows that in a monolithic LSM pipeline, stalls cannot be eliminated regardless of parameter tuning, since the arrival rate λ eventually exceeds the internal throughput (µflush , µcmp0 , µcmpd ). A structural alternative is to partition the LSM tree into L independent shards, reducing the per-shard arrival rate to λ/L. This slows Memtable filling, staggers flushes, and lowers utilization to ρ/L. If a shard stalls with probability α, then the probability of all L shards stalling simultaneously is αL , which decreases exponentially. The expected stall time after sharding is thus approximated by: E[B]L ≃

λ αL V̄ . 1 − ρ/L

(9)

Unlike Sub-Compaction or ADOC, which only shift stall types, sharding reduces stall probability exponentially and provides a structural path toward near-stall-free operation. Figure 3 shows model-based theoretical changes in stalls as a function of the number of shards under preliminary results (512MT, 1 Sub-Compaction, 8KB FillRandom). As the number of shards increases, stalls decrease sharply and

approach nearly zero at eight shards. This behavior is validated by the evaluation results (§IV-B). Stall (stalls/s)

L0 Stall

Memtable Stall

1.0 0.5 0.0

4 Shard (#)

Fig. 3: Changes in stall according to the number of shards based on the model in the preliminary results (512MT, 1 Sub-Compaction, 8KB FillRandom). I/O

• Objective #2: Maintain Read I/O Performance. Because D IA LSM consists of several small physical LSM trees, redirected KV pairs must be efficiently located. This requires an indexing mechanism—similar to a lightweight directory service—whose lookup cost remains minimal. • Objective #3: Support Global Ordering of KV Pairs. Keys distributed across different shards lack a global order. Since range queries rely on ordering, D IA LSM preserves global order semantics as in a monolithic LSM tree. • Objective #4: Provide Consistency. When KV pairs are written to fallback shards during stalls, crashes may occur anytime. It is critical to reliably track such redirections, ensuring recovery without data loss or inconsistency.

Idx = Hash(Key) Logical LSM tree

Idx=1 Shard 1

Idx=2 Shard 2

Idx=3 Shard 3

Idx=N

…

Shard N

Fig. 4: A high-level concept of D IA LSM. III. D ESIGN OF D IA LSM D IA LSM adopts a shard-based LSM architecture that departs from the traditional monolithic design by assembling multiple smaller and independent LSM shards. Each shard manages part of the global key space and executes its own compaction processes in isolation, effectively distributing write traffic and alleviating compaction-induced stalls. At a higher level, the full LSM tree can be regarded as a logical aggregation of these shards, as shown in Figure 4. To support this architecture, D IA LSM incorporates directory services to track the placement of key-value pairs across shards, ensures global key ordering, and maintains the same level of failure consistency as a conventional non-sharded LSM tree. Model-based Intuition for Number of Shards. The modeling results provide important intuition on how the number of shards affects write stall mitigation (§II-C). Based on observable parameters in the LSM pipeline, including the write (λ), flush (µflush ), and compaction rate (µcmp0 , µcmpd ), the model quantitatively estimates how stall probability decreases as the number of shards increases. This helps approximate the necessary range of shards required to effectively mitigate write stalls in a given environment, but it cannot guarantee identical results when applied to an actual system. Accordingly, the design of D IA LSM does not attempt to automatically tune or determine the optimal number of shards; instead, it focuses on experimentally demonstrating that D IA LSM can practically mitigate write stalls across diverse shard configurations and system conditions (§IV). A more detailed discussion of shard-count trade-offs is deferred to the Discussion (§VI). A. Design Goals • Objective #1: Practical Reduction of Write Stalls. D I A LSM introduces a primary LSM shard and one or more fallback LSM shards for each key-value pair, effectively mitigating write stalls by bypassing writes even when the internal throughput of LSM shards is insufficient.

B. Dynamic Rerouting with Primary-Fallback Figure 5(a) illustrates how primary and fallback shards are determined. D IA LSM adopts hash-based placement: the primary shard index for a key is obtained by hash(key), mod(num shards). Each shard maintains its own Memtable, flushes it when full, and performs leveled compactions (including L0-to-L1) in the same manner as a monolithic LSM tree. For example, if ⟨K1⟩ maps to shard 1, then shard 1 serves as the primary shard, while all other shards act as fallbacks, as shown in Figure 5(a). This mapping is per-key: a shard may be primary for some keys and fallback for others. 1) Write Procedure: Figure 5(b) shows the write path for the ⟨K2⟩ example, divided into Primary and Fallback: 1) Primary path. If the primary shard of ⟨K2⟩ is not stalled, the write is inserted directly into it. 2) Fallback path. If the primary shard is stalled, the write redirected to a non-stalled fallback shard (e.g., shard 1). 3) CE and TKV. In the fallback case, an indexing entry is inserted in the primary shard to record the redirection. This indexing entry is referred as Clue-Entry (CE), while the original KV pair for ⟨K2⟩ is called the True-KV. The CE entry in primary shard points to the fallback shard → − containing the TKV, e.g., ⟨K2, 1 ⟩. This approach leads to versioning and obsolescence issues which covered in detail in Section III-C. 4) Reserved Space for CE. Since the primary shard is stalled, regular TKV entries cannot be inserted. However, CEs are only a few bytes. To guarantee CE insertions, D IA LSM reserves 2 MB of Memtable space in each shard, excluded from stall threshold calculations. Thus, CEs can always be inserted even during stalls. With 20-byte entries (16-byte key, 4-byte pointer), this space holds up to 100,000 CEs. Note that the reserved space size is user-defined. Fallback Shard Selection Policy. Since fallback shards can also experience stalls, their selection must be handled carefully. In a system with N shards, candidates are chosen from the N −1 non-stalled shards. Selection follows a strict priority order: (1) smallest L0 size; (2) lowest Memtable usage; (3) smallest pending backlog; and (4) smallest total data size. This approach balances load across shards and reduces the risk of cascading stalls. Redirecting I/O to a fallback shard and inserting the corresponding CE incur extra reads and writes,

TKV

Ex) Idx=1 Hash(K1)=1

Primary Fallback

Reserved Space

N K2

Hash(K2)=2

OKV

N OCE

shard 2

…

Primary Fallback

Fallback Ex) Idx=2

Hash(K2)=2

shard 1

shard 2

Fallback Primary

…

Flush

shard 1

shard 2 Read

Primary Fallback

Level 0

Different index CEs for the same key(K2)

OCE GC

1 3

shard N Fallback

(a)

shard 1

shard 2

Move to L1

(b)

Fallback

OKV GC

Caching 1

Index pointing

shard N

CE-Cache

Memory

shard 1

CE-Set

Write

shard 1

shard 2

shard 3

(d) CE-Set

Capping K2

shard 2

(c)

1 2 Read SelfCE Chk If the same key TKV is inserted into the primary LSM 6 5 Delete Delete TKV CE

3 Read TKV

4 Write TKV

(e)

Fig. 5: Architecture and operations of D IA LSM. (a) Examples of the primary LSM and fallback LSM for each key, (b) write and read

paths, (c) internal operations of LSM shard: CE Capping, CE Caching, CE/TKV Garbage Collection, (d) A scenario where obsolete data occurs, (e) Flow of performing a rollback.

which can increase read, write, and space amplification. These impacts are evaluated in detail in Section IV-E. 2) Read Procedure: The read path in Figure 5(b) is also divided into two cases: 1) Primary path. If the primary shard holds the TKV, it is returned immediately. 2) Fallback path. If the primary shard returns a CE, the pointer is followed to the fallback shard to retrieve TKV. This requires two reads across shards, doubling worst-case latency. To mitigate this, D IA LSM employs CE capping and CE caching in Section III-C.

OCE garbage collection occurs naturally during L0 compaction, which keeps only the most recent CE per key. For OKV pairs, since they are stored in different shards, D IA LSM sends a delete request to the relevant shard whenever its corresponding OCE is removed. This ensures obsolete KV pairs are properly cleaned up. Because GC is integrated into existing compaction, its overhead is typically minimal. Only in rare workloads, with extremely frequent updates to the same key might the GC load become significant enough to impact performance – scenarios that are uncommon in practice.

C. Managing Clue Entries

D. Managing Rollbacks

Figure 5(c) shows an LSM shard’s internal structure and operation. Each shard behaves like a standalone LSM tree, following traditional LSM principles. To enable efficient interaction between TKVs and CEs, D IA LSM introduces additional components: a reserved space and a CE-cache in memory, and a CE-Set at L0. These structures ensure that CEs are tracked and accessed efficiently during both writes and reads. When a flush occurs, the CE from the reserved space and the TKV from the Memtable are written together into an L0 SSTable. During L0 compaction, they are split, TKVs are compacted into L1, while CEs are retained in L0 via a process called CE L0 Capping, which ensures CEs never move beyond L0. To further reduce lookup latency, the CE-Set is mirrored in memory via CE Caching. Both the CE-Set and CE-cache are updated after every L0 compaction. The system performs lookups in the following order: (1) Memtable, (2) CE-cache, (3) L0 SSTables, and (4) CE-Set. Garbage Collection. When multiple CEs exist for the same key, older versions become obsolete. For example, in Fig→ − → − ure 5(d), if ⟨K2, 2 ⟩ is inserted and later replaced by ⟨K2, 3 ⟩, the former becomes an obsolete CE (OCE). The KV pair it points to — stored in another LSM shard — becomes an obsolete KV (OKV) pair. Without cleanup, these outdated entries would remain in the system indefinitely, consuming unnecessary storage. To address this, garbage collection (GC) is build into the L0 compaction process (Figure 5(c)), where both OCE and OKV pair cleanup are performed.

D IA LSM temporarily redirects KV pairs to fallback shards when a primary shard enters a write stall. To maintain consistency across the LSM tree, these redirected KV pairs must eventually be written back to their original shard through a rollback process. Rollbacks are performed by dedicated background threads, triggered independently in each shard based on specific policies. Figure 5(e) shows the rollback process as follows. Step 1 → − Read a CE (e.g., ⟨K2, 2 ⟩) from the CE-cache of the primary shard. Step 2 Perform a self-check to see if the corresponding TKV has already been inserted into primary shard. Step 3 If not found, retrieve the TKV from the fallback shard (e.g., shard 2). Step 4 Write the TKV back to the primary shard. Step 5 – 6 Delete the CE from the primary shard and the TKV from the fallback shard. However, this rollback flow assumes a static system state. In practice, new writes may occur concurrently with rollback, introducing the risk of inconsistencies — most notably, a version inversion problem. Handling Version Inversion Issues. During rollback, foreground I/O thread may continue working to the primary LSM shard. This can cause a version inversion issue, where a newly written TKV is overwritten by an outdated version from rollback. For instance if a new TKV for key K2 is inserted into the primary shard between Step 1 and Step 3 , and the rollback process proceeds without recognizing this update, it may overwrite the new TKV. To prevent this, D IA LSM checks for key conflicts. If a new TKV for the same key is detected,

the rollback skips re-insertion and proceeds directly to cleanup (Steps 5 – 6 ), ensuring data correctness. Policy of Rollback Triggering. Rollback introduces additional write/read load to both primary and fallback shards. To avoid degrading performance, rollback is only triggered under controlled conditions. D IA LSM uses two trigger policies. The stabilization-state trigger runs rollback only when all shards are stable — i.e., no active compactions and a small L0 — indicating low write activity. If a new write burst disrupts this state, rollback is aborted. The CE threshold trigger activates rollback when the number of CEs exceeds a predefined limit (default: 1 million). This prevents excessive CE build up from impacting reads. When this trigger fires, rollback proceeds regardless of shard state, and no further CEs are accepted, even at the cost of potential write stall. E. Range Query Processing in D IA LSM In a shard-based LSM architecture, there is no global ordering across shards. A naive approach to range queries would involve comparing the current key of every shard during each call to Next(). However, this method introduces significant overhead, as it requires serial comparisons across all shards. As the number of shards increases, this overhead grows linearly, degrading range query performance to below that of a monolithic LSM tree. To address this, DIALSM implements a parallel range query mechanism that considers the start key (K) and the scan length (L) as scan bounds and exploits the parallelism of the sharded structure. Instead of scanning serially, all shard perform Seek(K) concurrently. Each shard then independently invokes Next() until it reaches the end of its local portion of the query range (K + L). Because data is hash-partitioned across shards, each shard holds only a subset of keys. As the number of shards increases, the key span handled by each shard shrinks, resulting in improved range query throughput. Algorithm 1 outlines this process. Given a user-specified start key Kstart and scan length L, the system first computes the upper bound key Kend (lines 1–3). Then, each shard concurrently executes Seek(Kstart ). If the key is not present in a shard, its iterator advances to the nearest key greater than or equal to Kstart (line 4–5). From there, each shard continues scanning by repeatedly invoking Next() until it reaches Kend (line 6–8). This entire process runs in parallel, with each shard operating independently. Once all shards complete local scans, the range query is complete (line 9). While parallel range queries may increase CPU usage due to concurrent shard execution, this is offset by a significant reduction in overall processing time. As a result, D IA LSM achieves efficient and scalable range query performance. F. Handling Failures and Recovery System crashes can lead to consistency issues in D IA LSM. A full cross-validation of all LSM shards would ensure correctness, but this approach is prohibitively expensive due to the large number of reads required. Instead, D IA LSM employs a fast recovery method that avoid global cross-validation and

Algorithm 1: Parallel Range Scan in D IA LSM Function RangeScan(Kstart , L): Kend ← Kstart + L 3 Output ← [ ] 4 foreach s ∈ Shards in parallel do 5 Shard iters .Seek(Kstart ) 6 while Shard iters .V alid() and Shard iters .GetKey() < Kend do 7 Output ← Shard iters .GetKey(), Shard iters .GetV alue() 8 Shard iters .N ext()

return Output

enables efficient recover after a crash. In the recovery phase, user I/O is not accepted. Failures in Writing. During normal operation, a failure may occur while inserting a KV pair into the fallback LSM shard, typically triggered by a write stall in the primary shard. We define this as Failure Case-1 (FC-1): • FC-1: The TKV is successfully inserted into the fallback shard, but a crash occurs before the corresponding CE is written to the primary shard. In FC-1, the fallback shard contains a TKV that is effectively invisible due to the missing CE entry in primary shard. To recover, D IA LSM reads the most recent TKV in each shard, hashes the key to determine its rightful primary shard, and checks for a matching CE entry. If no CE is found in the primary shard, the system assumes an incomplete write and rolls the TKV back to the primary shard — without creating a CE — thereby restoring consistency. At this point, consecutive TKVs with missing CEs may have been inserted into the fallback shard. Therefore, this process is repeated until no TKVs with missing CEs remain. Failures in the Process of Rollback. Failures may occur during the rollback process. We consider two such cases: • FC-2: A crash occurs after inserting the TKV into the primary shard (Step 4 ) but before removing the CE from the CE-Set (Step 5 ). • FC-3: A crash occurs after removing the CE (Step 5 ) but before deleting the TKV from the fallback shard (Step 6 ). In FC-2, both TKV and CE exist in the system, which can cause unnecessary reads and increased latency. To resolve this, D IA LSM checks if a shard contains both a recently inserted TKV and a matching CE. If so, the rollback is resumed and completed that point. For FC-3, the same KV pair exists in both primary and fallback shards, but the CE has already been deleted — making it unclear which shard the fallback was. In recovery, each shard scans for its most recent TKVs and checks all other shards for duplicates. The shard that still holds the redundant KV (identified via key hashing) is treated as the fallback, and its KV is removed to finalize rollback. IV. E VALUATION A. Experimental Setup Implementation. We implemented D IA LSM on top of RocksDB v8.3.2, a widely adopted LSM tree based key-value store. To enable this, we introduced the db master class,

which ensures that each LSM shard in D IA LSM operates as an independent RocksDB instance. The db master class exposes APIs for operations, including Open(), Close(), Put(), Get(), and Seek(), and supports the following functionality. To avoid write stalls and select the optimal fallback LSM shard, the system periodically monitors shard states, including Memtable usage, L0 size, and the compaction backlog. In our experiments, the monitoring interval is set to 0.1 seconds. The source code for D IA LSM is publicly available at https: //github.com/DISCOS-LAB/DiaLSM. Platform. Our experiments were conducted on a server equipped with two AMD EPYC 7352 24-Core CPUs, 256 GB DDR4 DRAM, and a PCIe Gen3x4 3.84 TB Samsung MZSLR3T8HBLS-00A07 NVMe SSD. The system ran CentOS 7 with the ext4 file system. Comparison Systems. We compare ADOC [5], RocksDB [3], with Sub-Compaction enabled, and D IA LSM. Configurations of ADOC, RocksDB and D IA LSM are as follows. • ADOC: We have enabled the Sub-Compaction in ADOC under RocksDB v8.3.2. Note that ADOC dynamically expands Memtables up to 512 MB. ADOC(m) refers to an ADOC with m Sub-Compactions enabled. • D IA LSM: Each shard has two Memtables and two flush threads. D IA LSM(n) refers to a D IA LSM that utilizes n LSM shards. • RocksDB: RocksDB v8.3.2 with Sub-Compaction enabled. RocksDB(m) notation follow the same as ADOC. Comparison Fairness. As shown in Table II, all systems use the same resources, and fairness is as follows. • Memtable and Flush Parallelism: As the number of shards increases, D IA LSM(n) increases Memtable(2n) and Flush(2n) parallelism; RocksDB(m) is configured accordingly to match this behavior. In contrast, ADOC dynamically adjusts Memtable sizes, making equivalent configuration infeasible. • Number and Size of L0 SSTables: The L0 SSTable size depends on the Memtable size. As Memtable sizes decrease, D IA LSM and RocksDB can accommodate more SSTables in L0. However, all systems use the same L0 capacity (RocksDB default: up to 36 SSTables in L0, totaling 36 × 512). • Number of Compaction Threads: All systems are configured with a total of 32 compaction threads. In D IA LSM(n), each shard is allocated ⌈32/n⌉ compaction threads, so that the sum of compaction threads across all shards is 32. TABLE II: Configuration details of evaluation candidates. Each Memtable Size (MB) Memtable Count (#) Total Memtable Size (MB) Flush Thread (#) Compaction Thread (#) Max L0 SST (#) Total L0 Size (MB) Li Size (i ≥ 1) (MB)

D IA LSM(n)

ADOC(m)

RocksDB(m)

512/n 2n 1024 2n n · ⌈32/n⌉ 36 · n 512 × 36 (256 × 10i /n) · n

64 - 512 2 1024 2 32 36 512 × 36 256 × 10i

512/m 2m 1024 2m 32 36 · m 512 × 36 256 × 10i

• LSM Size: With more shards, D IA LSM(n) reduces perlevel(i) sizes (256 × 10i /n) so that each shard becomes proportionally smaller, while the total LSM size remains the same as in the other systems. The L1 size (256MB) and level ratio (10) are RocksDB defaults. Common RocksDB Parameter Configurations. RocksDB provides I/O rate throttling thresholds that throttle the I/O when the number of SSTs in L0 reaches the Write Stall Threshold (WST) during the high write I/O phase. To accurately assess performance degradation caused by write stalls, we disable the throttling threshold in all experiments. We also disabled commit logging to accurately identify only the cause of write stalls in IO. RocksDB also provides a block cache, D IA LSM with multiple LSM shards uses more cache than RocksDB and this can impact performance. We disable block cache for all systems for a fair evaluation. Workloads. To evaluate the efficacy of D IA LSM in a variety of workloads, we consider various workloads from db bench [28], YCSB benchmark [29], and Sysbench [30]. • FillRandom: 100% write workloads are evaluated in db bench. To emulate different arrival rates, three value sizes—128B, 1KB, and 8KB—are considered, representing very small, medium, and very large values based on prior analyses of real-world key-value workloads [5], [7], [21], [31]–[35]. For each I/O thread inserts 10 million entries. • RRWR: The ReadRandomWriteRandom workload supports execution under different read/write ratios. The database is first populated with 100 million (10M × 10) entries of 1KB values using FillRandom, after which each I/O thread performs read and write operations on an additional 10 million 1KB entries. • YCSB: The YCSB benchmark, a widely adopted workload for evaluating real-world scenarios, is used in the evaluation. The experiments are conducted with a value size of 1KB, and the details of each workload are presented in Table III. • OLTP: To evaluate effectiveness in RocksDB-based RDBMSs, the OLTP workloads of Sysbench [30] are used. Detailed workload descriptions are provided in Table V. All db bench and YCSB workloads use 16-byte keys and operate with 10 I/O threads, except for the YCSB-E workload. In YCSB-E, a single I/O thread was used to avoid the parallel processing overhead of D IA LSM, meaning that a single I/O thread performs range scans. B. Write-Only Performance Figure 6 analyzes throughput and stall behavior across different value sizes. With small values (128B), stalls are negligible in all systems, but D IA LSM still benefits from sharding, showing throughput gains even without stall pressure. For medium values (1KB), stalls begin to appear; here, D IA LSM maintains its advantage, while ADOC and RocksDB remain constrained by L0 bottlenecks. With large values (8KB), stalls become dominant: ADOC and RocksDB demonstrate up to 17.6× higher stall rates than

1 2 4 8 12 16 1 2 4 8 12 16

RocksDB

Stall Rate

1.0

0.5

0.5 0

1 2 4 8 12 16 1 2 4 8 12 16

0.3

1.0

Stall Rate

0.2

1.0 0.5

0.1 0

0.0

Throughput

1 2 4 8 12 16 1 2 4 8 12 16

(stalls/s)

0.5

ADOC

Throughput

(stalls/s)

0.5

(stalls/s)

1.0

1.5

1.0

IOPS (×106 )

1.5

Stall Rate

IOPS (×106 )

D IA LSM

Throughput

0.0

Shard (#) or Sub Comp. Thread (#)

(a) 128B (Small) (b) 1KB (Medium) (c) 8KB (Large) Fig. 6: Comparison of throughput and stall for different value sizes on the FillRandom workload. On the x-axis, D IA LSM refers to the number of LSM shards, and all other systems refer to the number of Sub-Compaction threads. 100.000

99.960

50 0

99.995

99.930

103 107 Latency (us)

(a) p0–p100

99.900

D IA LSM

RocksDB(16)

103 105 Latency (us)

(b) p99.9–p99.99

99.990 5 10

106 107 Latency (us)

C. Mixed Read/Write Workloads Earlier, we demonstrated that D IA LSM outperforms existing solutions under write-only workloads, where write stalls can be most severe. However, real-world environments typically mix reads and writes, so it is crucial that D IA LSM also delivers competitive performance when reads dominate. To

(a) R90/W10

1 2 4 8 12 16

5 4 3 2 1 0

1 2 4 8 12 16

(b) R50/W50 Read/Write Ratio

Fig. 8: Throughput comparison for different Read/Write ratios on the ReadRandomWriteRandom workload.

evaluate this, we varied the read/write ratio using the RRWR workload, while keeping the experimental setup identical to the previous section. Figure 8(a) shows results for R90/W10. While ADOC remains nearly flat and RocksDB degrades sharply, D IA LSM experiences only a modest decline. This difference stems from Memtable dynamics: with more shards (in D IA LSM) or more Sub-Compaction threads (in RocksDB), the effective Memtable size per pipeline decreases, leading to faster flush cycles and fewer Memtable hits on reads. Although both systems use the same Memtable size overall, D IA LSM maintains higher throughput than RocksDB because sharding prevents excessively frequent flushes per shard. A deeper explanation of this effect is given in Figure 9. At R50/W50 (Figure 8(b)), ADOC shows slight improvement, as the higher write ratio lets it to benefit from expanded Memtable capacity when more Sub-Compaction threads are enabled. Finally, at R10/W90 (Figure 8(c)), the behavior Memtable D IA LSM Lat. Read Hit (%)

D IA LSM (94.3% lower), limiting their throughput, whereas D IA LSM achieves up to 2.4× higher throughput than ADOC by both parallelizing the pipeline and avoiding stalls. Notably, D IA LSM’s throughput scales with the number of shards only up to 8, after which the bottleneck shifts from stalls to software overhead, indicating that the system reaches a saturation point beyond which additional shards bring no further gains. In addition, ADOC sustains throughput improvements as more Sub-Compaction threads are added, while RocksDB suffers a throughput decline beyond 8 threads due to diminishing Sub-Compaction efficiency. This drop arises because smaller Memtables generate smaller SSTables in L0, reducing the benefit of partitioning. In contrast, D IA LSM nearly eliminates stalls altogether, highlighting its structural advantage over both ADOC and RocksDB. Figure 7 illustrates the latency distribution for 8KB values. D IA LSM(16) consistently lowers average and median latency by about 50% over ADOC(16) and RocksDB(16), demonstrating the benefit of sharding in reducing stall-induced delays. At high percentiles (p99.9–p99.99), D IA LSM incurs extra latency from fallback redirection and CE insertion, but this overhead remains bounded. Most importantly, at the extreme tail (p99.99+), ADOC(16) and RocksDB(16) suffer severe latency spikes due to write stalls, whereas D IA LSM sustains stable performance and reduced tail-latency.

1 2 4 8 12 16

RocksDB

Shard (#) or Sub Comp. Thread (#)

Fig. 7: Cumulative distribution function (CDF) of latency for D I -

A LSM(16), ADOC(16), and RocksDB(16) under the FillRandom workload with 8KB values. In (c), the legend’s colored lines mark latency at the p99.9999.

ADOC

Level 0 ADOC Lat.

100

400 100

200

0 0 1 2 4 8 12 16 Sub-Comp. Thread (#)

(a) RocksDB

50 0

1 2 4 8 12 16 Shard (#)

Level 1–N RocksDB Lat.

400 100

400

200

0 0 1 2 4 8 12 16 Sub-Comp. Thread (#)

(b) D IA LSM

Avg. Latency (us)

CDF (%)

ADOC(16) 99.990

IOPS (×105 )

D IA LSM(16)

100

Fig. 9: Access ratio per level (Memtable, L0, L1+) and average read latency for each system.

D IA LSM

YCSB-Load

IOPS (×105 )

1 2 4 8 12 16

YCSB-B

2 0

YCSB-A

1 2 4 8 12 16

ADOC

RocksDB

YCSB-C

1 2 4 8 12 16

YCSB-D

0.02

1 0

1 2 4 8 12 16

YCSB-E

0.04

1 2 4 8 12 16

YCSB-F

1.0 0.5

1 2 4 8 12 16

Shard (#) or Sub Comp. Thread (#)

Fig. 10: Comparison of throughput in the YCSB benchmark workload.

IOPS (×103 )

0.2

0.5 1 2 4 8 12 16

RocksDB

Get-CE

0.4

1.0

1 0

ADOC

1.5

CDF (%)

D IA LSM

1 2 4 8 12 16

Shard (#) or Sub Comp. Thread (#)

Get-Total

100

0 0 10

103 Latency (us)

(a) CE Capping On

0 0 10

Cap

IOPS

On Off

6.58K 6.35K

103 Latency (us)

(b) CE Capping Off

(a) Length=1,024 (b) Length=4,096 (c) Length=16,384 Fig. 11: Comparison of throughput under different scan lengths in the YCSB-E workload.

Fig. 12: Latency and throughput comparison under configurations

closely resembles the write-only case in Figure 6(b), where stalls dominate and D IA LSM outperforms the baselines. Figure 9 shows the average read latency and level-wise access ratios under the RRWR R50/W50 workload. In RocksDB (Figure 9(a)), increasing the number of Sub-Compaction threads leads to higher latency. This occurs because a larger number of threads reduces the Memtable size, accelerating flush cycles and lowering the probability of Memtable hits. A similar trend is observed in D IA LSM (Figure 9(b)), where Memtable hits decrease as the shard count grows. However, unlike RocksDB, sharding reduces the write load per shard, preventing flush cycles from becoming excessively frequent even with smaller Memtables. As a result, D IA LSM sustains a higher Memtable hit ratio and effectively suppresses read-latency degradation. ADOC (Figure 9(c)) exhibits the opposite trend. As the number of Sub-Compaction threads increases, read latency decreases. This is because faster L0 compaction reduces accesses to unsorted L0 SSTables, shifting queries toward more efficient hits in deeper, sorted levels.

D IA LSM consistently achieves higher throughput than ADOC and RocksDB, regardless of the degree of parallelism. One notable case is YCSB-E, which involves range queries. While ADOC and RocksDB remain largely unaffected by increasing parallelism, D IA LSM shows throughput gains up to 4 shards, reaching about 1.7× higher performance than both baselines. Beyond this point, throughput declines as the shard count grows, since the relatively short scan length (128) amplifies the overhead of parallel range query execution. Another observation is from YCSB-C, the read-only workload, where throughput remains unchanged across all systems. In this case, D IA LSM, ADOC, and RocksDB all deliver comparable performance, as no write stalls are present to differentiate them. 1) Iterator Efficiency: Figure 11(a)–(c) presents throughput results for the YCSB-E with scan lengths of 1K, 4K, and 16K. As the scan length increases, the benefit of parallelizing range queries outweighs the parallelization overhead introduced by larger shard counts, resulting in overall throughput improvements. Notably, D IA LSM achieves 3.3×, 5.7×, and 8.9× higher throughput than ADOC and RocksDB at scan lengths of 1K, 4K, and 16K, respectively.

D. YCSB Benchmark Evaluation Figure 10 presents throughput comparisons across YCSB workloads, with workload details given in Table III. Overall, TABLE III: Description of YCSB workload characteristics. Type

Description

Distribution

A B C D E F

50% Updates, 50% Reads 95% Reads, 5% Updates 100% Reads 95% Reads, 5% Inserts 95% Seeks, 5% Inserts; Scan length:128 50% Read-Modify-Write, 50% Reads

Zipfian Zipfian Zipfian Latest Uniform Zipfian

with and without CE Capping. Get-CE is the time to read a CE, and Get-Total is the overall time to process a Get.

E. Impact of D IA LSM Features 1) CE L0 Capping Efficiency: Although the preceding experiments were performed with CE Capping enabled, Figures 12(a)–(b) present a comparison of read latency in D I A LSM (16) with and without CE Capping, under the db bench ReadRandom (100% read) workload following FillRandom with 8KB values. When CE Capping was disabled, the CE access time was almost the same as the overall read latency. However, when Capping was enabled, the CE read time decreased by 95.5%, resulting in a noticeable improvement in latency. Figure 12(c) shows that throughput improvement

Rollback and Compaction

200

400 Time

600

800

600k 400k 200k 100k 50k 0 1.5M 1M 500k 0 0

Read

Write

Read

Just Compaction

200

400 Time

600

1 2 4 8 12 16

ADOC

10 8 6 4 2 0

1 2 4 8 12 16

(b) 1KB

Fig. 14: Write amplification comparison for each system. depends on how many CE reads occur. In this workload, CE reads were only about 15%, so the gain was small. If the ratio is higher, the reduced latency leads to larger throughput gains, making CE Capping more effective. 2) Rollback Overhead and Throughput Benefits: Figures 13(a)–(b) present throughput and CE counts in D IA LSM (16) while alternately running 8KB FillRandom and ReadRandom workloads for 200 seconds each, comparing rollback enabled and disabled. In the initial write phase, approximately 850,000 CEs are generated. During the subsequent read phase, the system performs compaction prior to serving requests, and enabling rollback incurs about 60 seconds of additional delay. Despite this overhead, enabling rollback delivers throughput improvement over the disabled case, demonstrating that rollback effectively enhances read performance. As described in Section III-C, rollback is a user-defined policy that benefits read-heavy workloads. It is not just overhead but can improve throughput. Since workload-aware decision making has been well studied, we leave adaptive rollback policies for future work. Note that all experiments except for this evaluation were conducted with rollback disabled to maintain consistency. 3) Write and Space Amplification: Figure 14 presents the comparison of Write Amplification (WA) across value sizes under the FillRandom workload. D IA LSM exhibited more stable WA than other systems, indicating that CE insertion has little impact on WA. In contrast, ADOC and RocksDB show increasing WA as the number of Sub-Compaction threads grows, since SSTable fragmentation increases. In particular, for RocksDB, as Memtable size decreases and the number of Memtables increases, the number of L0 SSTable files grows sharply, causing WA to deteriorate significantly. Space Amplification. Table IV presents the number of CEs

1 2 4 8 12 16

(b) Memory

D IA LSM (1 SSD)

D IA LSM (2 SSDs)

1.5 1.0 0.5

4.0 2.0 0

1 2 4 8 12 16

Shard (#) or Sub Comp. Thread (#)

(a) 128B

Shard (#) or Sub Comp. Thread (#)

(a) 128B

(a) CPU

1 2 4 8 12 16

Fig. 15: Resource usage comparison for each system.

RocksDB

10 8 6 4 2 0

RocksDB

Shard (#) or Sub Comp. Thread (#)

IOPS (×106 )

Write Amplification

D IA LSM

ADOC

800

(a) Rollback On (b) Rollback Off Fig. 13: Overhead and throughput comparison under rollback execution. 10 8 6 4 2 0

D IA LSM

100

Memory Usage (GB)

Write

IOPS

Read

IOPS (×105 )

0 1.5M 1M 500k 0 0

Write

CPU Utilization (%)

Read

CE (#)

IOPS

Write

600k 400k 200k 100k 50k

(b) 8KB

Fig. 16: Evaluation of D IA LSM utilizing multiple devices. and the Space Amplification (SA) of D IA LSM in the FillRandom 8KB workload(Figure 6(c)) across different shard counts. As the number of shards increases up to 8, the likelihood of avoiding write stalls rises, resulting in more CEs and higher SA. Beyond 12 shards, however, the sharding effect becomes more pronounced, reducing per-shard write stalls and thereby lowering both CE occurrences and SA. These results indicate that increasing the shard count enhances not only throughput but also space efficiency. 4) Resource Utilization: Figures 15(a)–(b) show CPU and memory consumption under the FillRandom 8KB. D IA LSM uses more CPU to accelerate parallel compaction, reducing total processing time. Its CE caching adds some memory overhead, but modestly. In contrast, RocksDB’s memory usage rises sharply as immutable Memtables accumulate, showing that D IA LSM achieves higher memory efficiency even with smaller, more frequent Memtables. F. Multi-SSD Performance Evaluation In large-scale services (e.g., ByteDance [36]), multiple SSDs are commonly deployed to meet throughput and parallelism demands, with RocksDB serving as the backend storage engine. While a single SSD often suffers from controller bottlenecks, scaling out with multiple SSDs alleviates these limitations and delivers substantial performance gains. Similarly, D IA LSM mitigates LSM pipeline bottlenecks inherent to monolithic LSM tree designs through sharding, but devicelevel bottlenecks still remain. To address this, distributing LSM shards across multiple SSDs offers a practical solution. TABLE IV: Space amplification in D IA LSM. LSM shards (#)

Space Amplification CE (#)

1 -

1.28 3.5M

1.35 3.4M

1.5 5.3M

1.21 2M

1.14 1.5M

D IA LSM

ADOC

2 1 2 4 8 12 16

TPS (×102 )

3 TPS (×104 )

TPS (×104 )

RocksDB

2 1 0

5 0

1 2 4 8 12 16

Shard (#) or Sub Comp. Thread (#)

(a) oltp insert

(b) oltp write only

Fig. 17: Sysbench evaluation of MariaDB with MyRocks. We experimentally validate this by comparing single-SSD and dual-SSD setups, placing LSM shards evenly across the two devices and running FillRandom workloads. As shown in Figure 16, performance remains comparable for 128B values, but with 8KB workloads, a single SSD exhibits clear bottlenecks once the shard count exceeds eight. Beyond this point, distributing LSM shards across dual SSDs achieves performance scaling proportional to the available bandwidth. These results highlight the importance of intelligent shard placement in multi-SSD arrays, suggesting that in multi-tenant cloud environments, effective load balancing of LSM shards across SSD controllers is a critical challenge. G. OLTP Evaluation on RDBMS We evaluate effectiveness in RDBMS environments using Sysbench OLTP workloads on MariaDB based on RocksDB, known as MyRocks [22]. Detailed characteristics of the OLTP workloads are presented in Table V, and the workloads are executed with 10 I/O threads for 1800 seconds. Figure 17(a) shows the results for oltp insert, which consists of 100% INSERT operations. Starting from two shards, write stalls are alleviated, achieving up to 2.3× higher throughput than ADOC, after which performance saturates. In contrast, RocksDB exhibits degraded performance due to reduced Memtable sizes, similar to the behavior observed from eight shards in Figure 6(c). Figure 17(b) shows the results for oltp write only, which includes DELETE and UPDATE operations in addition to INSERT. RocksDB and ADOC show limited benefits from Sub-Compaction, whereas D IA LSM fully exploits sharding effects and achieves up to 9.9× higher throughput. Figure 17(c) shows the results for oltp read write. While D IA LSM achieves 2.2× higher throughput due to sharding effects, the other systems exhibit little change or a slight decrease in performance. These results indicate that D IA LSM’s design can be effectively applied beyond key-value stores to RDBMSs. TABLE V: Description of OLTP workload characteristics. Workload Type

Operations per Transaction (Execution Order)

oltp insert oltp write only oltp read write

1 INSERT 2 UPDATE, 1 DELETE, 1 INSERT 10 SELECT, 2 UPDATE, 1 INSERT, 1 DELETE

V. R ELATED W ORK Optimizing the Monolithic Pipeline. Extensive work accelerates compaction and improves read/write amplification

trade-offs in a single LSM-tree. Software approaches improve compaction scheduling [7], [11], [37]–[41], tune system parameters [5], [42]–[45], modify compaction strategies [46]– [49] (e.g., leveled and tiered), redesign data layouts [35], [50]–[60], reduce syscall overhead [61], or separate keys from values [62]–[66]. Hardware-assisted methods offload compaction to FPGAs [67]–[69], DPUs [70]–[72], GPUs [73]–[78], KVSSDs [79], or distributed and cloud backends [80]–[84], and exploit in-storage processing [85], [86] or non-volatile memory [6], [8], [87], [88] such as 3D XPoint [89]; others systematically analyze compaction designs and future directions [90], [91]. Beyond compaction-focused optimizations, a wide range of studies have actively explored optimizing the overall structure and operation of LSM-trees [92]–[98]. Partitioning and Multi-Tree Approaches. Decomposing a monolithic index into smaller, independently maintained units is well established, from partitioned and multi-version Btrees [99]–[102] to fragmented or range-partitioned LSMtrees such as PebblesDB [58] and WipDB [59]; the latter compact fragments independently but can trap hot ranges in continuous merges, while Column Families [103] separate trees only logically and require explicit user management. We therefore do not claim the decomposition principle itself as novel: D IA LSM’s contribution is the LSM-internal stall mitigation built on hash sharding—dynamic fallback rerouting, CE indirection, and rollback/recovery integration—which sustains writes under stalls and lowers stall probability with shard count, achieving near-stall-free operation in software. VI. D ISCUSSION Why Internal Sharding is Necessary. System-level sharding, as in ZippyDB [17] or Kvrocks [16], improves scalability but does not eliminate stalls within each embedded store. In contrast, internal sharding allows finer-grained control, better use of device-level parallelism (e.g., NVMe SSDs), and avoids the overhead of inter-node communication. While it introduces modest CPU Utilization, the gains in latency and stability far outweigh these costs (§IV). Number of Shards. Determining an appropriate shard count is inherently challenging: CPU, memory, I/O bandwidth, workload skew, and the deployment environment jointly determine how sharding affects write stalls, so no single setting is universally optimal. Dynamic adjustment is feasible but incurs nontrivial migration and rebalancing overhead; we therefore treat shard count as a deployment-layer concern (as in systems such as HDFS) rather than an internal LSM optimization. VII. C ONCLUSIONS We showed that write stalls in monolithic LSM trees are a structural limitation of the tightly coupled write–flush–compaction pipeline and cannot be eliminated by parameter tuning alone. Based on a vacation-based queuing analysis, we proposed D IA LSM, an internally shard-based LSM architecture that substantially reduces write stalls and achieves up to 2.4× higher throughput with lower latency than state-of-the-art approaches.

R EFERENCES [1] P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil, “The Log-Structured Merge-Tree (LSM-tree),” Acta Informatica, vol. 33, no. 4, pp. 351–385, 1996. [2] Google, “LevelDB.” https://github.com/google/leveldb, 2017. [3] “RocksDB.” http://rocksdb.org, 2012. [4] “Cassandra.” https://cassandra.apache.org, 2008. [5] J. Yu, S. H. Noh, Y.-r. Choi, and C. J. Xue, “Adoc: Automatically harmonizing dataflow between components in log-structured key-value stores for improved performance,” in 21st USENIX Conference on File and Storage Technologies (FAST 23), pp. 65–80, 2023. [6] T. Yao, Y. Zhang, J. Wan, Q. Cui, L. Tang, H. Jiang, C. Xie, and X. He, “Matrixkv: Reducing write stalls and write amplification in lsmtree based kv stores with matrix container in nvm,” in 2020 USENIX Annual Technical Conference (USENIX ATC 20), pp. 17–31, 2020. [7] O. Balmau, F. Dinu, W. Zwaenepoel, K. Gupta, R. Chandhiramoorthi, and D. Didona, “Silk: Preventing latency spikes in log-structured merge key-value stores,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 753–766, 2019. [8] C. Ding, T. Yao, H. Jiang, Q. Cui, L. Tang, Y. Zhang, J. Wan, and Z. Tan, “Trianglekv: Reducing write stalls and write amplification in lsm-tree based kv stores with triangle container in nvm,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 12, pp. 4339–4352, 2022. [9] K. He, Y. An, Y. Luo, X. Liu, and G. Wang, “Flatlsm: Write-optimized lsm-tree for pm-based kv stores,” ACM Transactions on Storage, vol. 19, no. 2, pp. 1–26, 2023. [10] C. Luo and M. J. Carey, “On performance stability in lsm-based storage systems (extended version),” arXiv preprint arXiv:1906.09667, 2019. [11] J. Liang and Y. Chai, “Cruisedb: An lsm-tree key-value store with both better tail throughput and tail latency,” in 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1032–1043, IEEE, 2021. [12] Facebook, “Subcompaction.” https://github.com/facebook/rocksdb/wi ki/Subcompaction, 2023. [13] S. W. Fuhrmann and R. B. Cooper, “Stochastic decompositions in the m/g/1 queue with generalized vacations,” Operations research, vol. 33, no. 5, pp. 1117–1129, 1985. [14] B. M. Abdelhafiz and M. Elhadef, “Sharding database for fault tolerance and scalability of data,” in 2021 2nd International Conference on Computation, Automation and Knowledge Management (ICCAKM), pp. 17–24, IEEE, 2021. [15] L. Xiao, K. Ren, Q. Zheng, and G. A. Gibson, “Shardfs vs. indexfs: Replication vs. caching strategies for distributed metadata management in cloud storage systems,” in Proceedings of the Sixth ACM Symposium on Cloud Computing, pp. 236–249, 2015. [16] Apache, “Kvrocks.” https://kvrocks.apache.org/, 2019. [17] ZippyDB, “How we built a general purpose key value store for Facebook with ZippyDB.” https://engineering.fb.com/2021/08/06/ core-data/zippydb/, 2021. [18] B. T. Doshi, “Queueing systems with vacations—a survey,” Queueing systems, vol. 1, pp. 29–66, 1986. [19] Y. Levy and U. Yechiali, “Utilization of idle time in an m/g/1 queueing system,” Management Science, vol. 22, no. 2, pp. 202–211, 1975. [20] Facebook, “Write Stalls.” https://github.com/facebook/rocksdb/wiki/W rite-Stalls, 2021. [21] Z. Cao, S. Dong, S. Vemuri, and D. H. Du, “Characterizing, modeling, and benchmarking rocksdb key-value workloads at facebook,” in 18th USENIX Conference on File and Storage Technologies (FAST 20), pp. 209–223, 2020. [22] Y. Matsunobu, S. Dong, and H. Lee, “Myrocks: Lsm-tree database storage engine serving facebook’s social graph,” Proceedings of the VLDB Endowment, vol. 13, no. 12, pp. 3217–3230, 2020. [23] S. Dong, A. Kryczka, Y. Jin, and M. Stumm, “Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications,” ACM Transactions on Storage (TOS), vol. 17, no. 4, pp. 1–32, 2021. [24] E. Parzen, Stochastic processes. SIAM, 1999. [25] L. Kleinrock, Theory, Volume 1, Queueing Systems. USA: WileyInterscience, 1975. [26] R. W. Wolff, “Poisson arrivals see time averages,” Operations research, vol. 30, no. 2, pp. 223–231, 1982. [27] J. W. Cohen, The single server queue. Elsevier, 2012.

[28] Facebook, “DB Bench.” https://github.com/facebook/rocksdb/wiki/B enchmarking-tools, 2017. [29] R. Mohan, “Benchmarking cloud serving systems with ycsb,” in Proceedings of ACM Symposium on Cloud Computing, Indianapolis, IN, USA, 2010. [30] A. Kopytov, “sysbench.” https://github.com/akopytov/sysbench, 2020. [31] Z. Wang and S. Yin, “Rbc: A bandwidth controller to reduce write-stalls and tail latency,” in Proceedings of the 52nd International Conference on Parallel Processing, pp. 213–222, 2023. [32] B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang, and M. Paleczny, “Workload analysis of a large-scale key-value store,” in Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pp. 53–64, 2012. [33] C. Lai, S. Jiang, L. Yang, S. Lin, G. Sun, Z. Hou, C. Cui, and J. Cong, “Atlas: Baidu’s key-value storage system for cloud data,” in 2015 31st Symposium on Mass Storage Systems and Technologies (MSST), pp. 1– 14, 2015. [34] J. Yang, Y. Yue, and K. Rashmi, “A large-scale analysis of hundreds of in-memory key-value cache clusters at twitter,” ACM Transactions on Storage (TOS), vol. 17, no. 3, pp. 1–35, 2021. [35] H. Sun, G. Chen, Y. Yue, and X. Qin, “Improving lsm-tree based keyvalue stores with fine-grained compaction mechanism,” IEEE Transactions on Cloud Computing, 2023. [36] ByteDance, “Bytedance official website.” https://www.bytedance.com/. Accessed: 2025-09-17. [37] Z. Zhang, Y. Yue, B. He, J. Xiong, M. Chen, L. Zhang, and N. Sun, “Pipelined compaction for the lsm-tree,” in 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pp. 777–786, 2014. [38] O. Balmau, F. Dinu, W. Zwaenepoel, K. Gupta, R. Chandhiramoorthi, and D. Didona, “Silk+ preventing latency spikes in log-structured merge key-value stores running heterogeneous workloads,” ACM Transactions on Computer Systems (TOCS), vol. 36, no. 4, pp. 1–27, 2020. [39] Y. Hu, L. Zhu, L. Jia, and C. Wang, “Aislsm: Revolutionizing the compaction with asynchronous i/os for lsm-tree,” arXiv preprint arXiv:2307.16693, 2023. [40] F.-F. Pan, Y.-L. Yue, and J. Xiong, “dcompaction: Speeding up compaction of the lsm-tree via delayed compaction,” Journal of Computer Science and Technology, vol. 32, pp. 41–54, 2017. [41] H. Byun, H. Yoo, and S. Park, “Revisiting multi-threaded compaction in lsm-trees: Enabling compaction pipelining,” in Proceedings of the 54th International Conference on Parallel Processing, pp. 794–803, 2025. [42] A. Huynh, H. A. Chaudhari, E. Terzi, and M. Athanassoulis, “Endure: a robust tuning paradigm for lsm trees under workload uncertainty,” arXiv preprint arXiv:2110.13801, 2021. [43] H. Wang, J. Qiu, F. Yuan, and H. Zhang, “Rethinking the compaction policies in lsm-trees,” Proceedings of the ACM on Management of Data, vol. 3, no. 3, pp. 1–26, 2025. [44] V. Thakkar, M. Sukumar, J. Dai, K. Singh, and Z. Cao, “Can modern llms tune and configure lsm-based key-value stores?,” in Proceedings of the 16th ACM Workshop on Hot Topics in Storage and File Systems, HotStorage ’24, (New York, NY, USA), p. 116–123, Association for Computing Machinery, 2024. [45] V. Thakkar, Q. Lin, K. Prasetyo, H. Wisjnunandono, J. Wang, A. I. Kistijantoro, R. F. Rachmadi, and Z. Cao, “Tellytune: Exploring the limits of llm-assisted tuning for lsm-based key-value stores,” in Proceedings of the 19th ACM International Systems and Storage Conference, pp. 81–96, 2026. [46] N. Dayan, T. Weiss, S. Dashevsky, M. Pan, E. Bortnikov, and M. Twitto, “Spooky: granulating lsm-tree compactions correctly,” Proceedings of the VLDB Endowment, vol. 15, no. 11, pp. 3071–3084, 2022. [47] X. Wang, P. Jin, B. Hua, H. Long, and W. Huang, “Reducing write amplification of lsm-tree with block-grained compaction,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE), pp. 3119–3131, IEEE, 2022. [48] N. Dayan, M. Athanassoulis, and S. Idreos, “Monkey: Optimal navigable key-value store,” in Proceedings of the 2017 ACM International Conference on Management of Data, pp. 79–94, 2017. [49] N. Dayan and S. Idreos, “Dostoevsky: Better space-time trade-offs for lsm-tree based key-value stores via adaptive removal of superfluous merging,” in Proceedings of the 2018 International Conference on Management of Data, pp. 505–520, 2018.

[50] D. Teng, L. Guo, R. Lee, F. Chen, S. Ma, Y. Zhang, and X. Zhang, “Lsbm-tree: Re-enabling buffer caching in data management for mixed reads and writes,” in 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), pp. 68–79, IEEE, 2017. [51] B. Lepers, O. Balmau, K. Gupta, and W. Zwaenepoel, “KVell: the design and implementation of a fast persistent key-value store,” in Proceedings of the 27th ACM Symposium on Operating Systems Principles, pp. 447–461, 2019. [52] H. Chen, C. Ruan, C. Li, X. Ma, and Y. Xu, “Spandb: A fast,costeffective lsm-tree based kv store on hybrid storage,” in 19th USENIX Conference on File and Storage Technologies (FAST 21), pp. 17–32, 2021. [53] A. Raina, J. Lu, A. Cidon, and M. J. Freedman, “Efficient compactions between storage tiers with prismdb,” in Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, pp. 179–193, 2023. [54] G. Xanthakis, A. Katsarakis, G. Saloustros, and A. Bilas, “vlsm: Low tail latency and i/o amplification in lsm-based kv stores,” arXiv preprint arXiv:2407.15581, 2024. [55] X. Wu, Y. Xu, Z. Shao, and S. Jiang, “Lsm-trie: An lsm-tree-based ultra-large key-value store for small data items,” in 2015 USENIX Annual Technical Conference (USENIX ATC 15), pp. 71–82, 2015. [56] O. Balmau, D. Didona, R. Guerraoui, W. Zwaenepoel, H. Yuan, A. Arora, K. Gupta, and P. Konka, “TRIAD: Creating synergies between memory, disk and log in log structured key-value stores,” in 2017 USENIX Annual Technical Conference (USENIX ATC 17), pp. 363–375, 2017. [57] K. Ren, Q. Zheng, J. Arulraj, and G. Gibson, “SlimDB: A spaceefficient key-value storage engine for semi-sorted data,” Proceedings of the VLDB Endowment, vol. 10, no. 13, pp. 2037–2048, 2017. [58] P. Raju, R. Kadekodi, V. Chidambaram, and I. Abraham, “Pebblesdb: Building key-value stores using fragmented log-structured merge trees,” in Proceedings of the 26th Symposium on Operating Systems Principles, pp. 497–514, 2017. [59] X. Zhao, S. Jiang, and X. Wu, “Wipdb: A write-in-place key-value store that mimics bucket sort,” in 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1404–1415, IEEE, 2021. [60] T. Yao, J. Wan, P. Huang, Y. Zhang, Z. Liu, C. Xie, and X. He, “GearDB: A GC-free Key-Value store on HM-SMR drives with gear compaction,” in 17th USENIX Conference on File and Storage Technologies (FAST 19), (Boston, MA), pp. 159–171, USENIX Association, Feb. 2019. [61] H. Byun, S. Lee, H. Yoo, M. Kim, and S. Park, “Resystance: Unleashing hidden performance of compaction in lsm-trees via ebpf,” in 2026 IEEE 42nd International Conference on Data Engineering (ICDE), pp. 3124–3137, 2026. [62] L. Lu, T. S. Pillai, H. Gopalakrishnan, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau, “Wisckey: Separating keys from values in ssdconscious storage,” ACM Transactions On Storage (TOS), vol. 13, no. 1, pp. 1–28, 2017. [63] “BlobDB.” https://github.com/facebook/rocksdb/wiki/BlobDB, 2018. [64] L. Tamasi, “Integrated blobdb.” https://rocksdb.org/blog/2021/05/26/in tegrated-blob-db.html. [65] Y. Li, Z. Liu, P. P. Lee, J. Wu, Y. Xu, Y. Wu, L. Tang, Q. Liu, and Q. Cui, “Differentiated key-value storage management for balanced i/o performance,” in 2021 USENIX Annual Technical Conference (USENIX ATC 21), pp. 673–687, 2021. [66] S. Jamil, A. Khan, X. He, and Y. Kim, “Dedupkv: A space-efficient and high-performance key-value store via fine-grained deduplication,” in Proceedings of the 39th ACM International Conference on Supercomputing, pp. 580–595, 2025. [67] T. Zhang, J. Wang, X. Cheng, H. Xu, N. Yu, G. Huang, T. Zhang, D. He, F. Li, W. Cao, et al., “Fpga-accelerated compactions for lsmbased key-value store,” in 18th USENIX Conference on File and Storage Technologies (FAST 20), pp. 225–237, 2020. [68] X. Sun, J. Yu, Z. Zhou, and C. J. Xue, “Fpga-based compaction engine for accelerating lsm-tree key-value stores,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 1261–1272, IEEE, 2020. [69] D. Tang, W. Wang, Y. Mao, J. Yu, T.-W. Kuo, and C. J. Xue, “Stem: Streaming-based fpga acceleration for large-scale compactions in lsm kv,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 3893–3905, IEEE, 2024.

[70] C. Ding, J. Zhou, J. Wan, Y. Xiong, S. Li, S. Chen, H. Liu, L. Tang, L. Zhan, K. Lu, et al., “Dcomp: Efficient offload of lsm-tree compaction with data processing units,” in Proceedings of the 52nd International Conference on Parallel Processing, pp. 233–243, 2023. [71] C. Ding, J. Zhou, K. Lu, S. Li, Y. Xiong, J. Wan, and L. Zhan, “D2comp: Efficient offload of lsm-tree compaction with data processing units on disaggregated storage,” ACM Transactions on Architecture and Code Optimization, vol. 21, no. 3, pp. 1–22, 2024. [72] J. Chen, S. Wang, Z. Zhang, S. Wu, and B. Mao, “iknowfirst: An efficient dpu-assisted compaction for lsm-tree-based key-value stores,” in 2023 IEEE 34th International Conference on Application-specific Systems, Architectures and Processors (ASAP), pp. 53–60, IEEE, 2023. [73] H. Sun, X. Jiang, X. Qin, S. Jiang, and E. Wang, “gparakv: A gpgpu-accelerated key-value separation-based kv store with optimized compaction and garbage collection,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1284–1298, 2025. [74] H. Sun, J. Xu, X. Jiang, G. Chen, Y. Yue, and X. Qin, “glsm: Using gpgpu to accelerate compactions in lsm-tree-based key-value stores,” ACM Transactions on Storage, vol. 20, no. 1, pp. 1–41, 2024. [75] H. Sun, X. Jiang, Y. Yue, and X. Qin, “Rgkv: A gpgpu-empowered compaction framework for lsm-tree-based kv stores with optimized data transfer and parallel processing,” IEEE Transactions on Computers, 2025. [76] H. Zhou, Y. Chen, L. Cui, G. Wang, and X. Liu, “A gpu-accelerated compaction strategy for lsm-based key-value store system,” in The 38th International Conference on Massive Storage Systems and Technology, pp. 1–11, 2024. [77] H. Zhou, Y. Chen, W. Zeng, L. Cui, G. Wang, and X. Liu, “Gpcomp: Using gpu and ssd-gpu peer to peer dma to accelerate lsm-tree compaction for key-value store,” IEEE Transactions on Parallel and Distributed Systems, 2025. [78] P. Xu, J. Wan, P. Huang, X. Yang, C. Tang, F. Wu, and C. Xie, “Luda: Boost lsm key value store compactions with gpus,” arXiv preprint arXiv:2004.03054, 2020. [79] K. Kim, H. Chung, S. Ahn, J. Park, S. Jamil, H. Byun, M. Lee, J. Choi, and Y. Kim, “Kvaccel: A novel write accelerator for lsm-tree-based kv stores with host-ssd collaboration,” in 2025 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 666–677, IEEE, 2025. [80] Z. Wang and Z. Shao, “Mirrorkv: An efficient key-value store on hybrid cloud storage with balanced performance of compaction and querying,” Proceedings of the ACM on Management of Data, vol. 1, no. 4, pp. 1– 27, 2023. [81] Q. Yu, C. Guo, J. Zhuang, V. Thakkar, J. Wang, and Z. Cao, “Caaslsm: compaction-as-a-service for lsm-based key-value stores in storage disaggregated infrastructure,” Proceedings of the ACM on Management of Data, vol. 2, no. 3, pp. 1–28, 2024. [82] J. Kim, H. Yoo, S. Lee, H. Byun, and S. Park, “Coordinating compaction between lsm-tree based key-value stores for edge federation,” in 2024 IEEE 17th International Conference on Cloud Computing (CLOUD), pp. 419–429, IEEE, 2024. [83] J. Kim, H. Byun, S. Lee, M. Kim, Y. Kim, Z. Xie, and S. Park, “Eco-kvs: Energy-aware compaction offloading mechanism for lsmtree based key-value stores in edge federation,” in 2025 IEEE 25th International Symposium on Cluster, Cloud and Internet Computing (CCGrid), pp. 570–579, IEEE, 2025. [84] Q. Lin, G. Huang, T. Guo, C. Guo, V. Thakkar, Z. Zhu, J. Wang, and Z. Cao, “O3-lsm: Maximizing disaggregated lsm write performance via three-layer offloading,” Proceedings of the ACM on Management of Data, vol. 4, no. 3 (SIGMOD, pp. 1–27, 2026. [85] H. Sun, B. Chen, J. Huang, Q. Wang, X. Liu, Y. Zhou, Y. Yue, and X. Qin, “A+ store: An asynchronous parallel compaction for multi-ndpenabled key-value store,” Journal of Systems Architecture, p. 103549, 2025. [86] H. Sun, W. Liu, J. Huang, and W. Shi, “Collaborative compaction optimization system using near-data processing for lsm-tree-based keyvalue stores,” Journal of Parallel and Distributed Computing, vol. 131, pp. 29–43, 2019. [87] B. Zhang and D. H. Du, “Nvlsm: A persistent memory key-value store using log-structured merge tree with accumulative compaction,” ACM Transactions on Storage (TOS), vol. 17, no. 3, pp. 1–26, 2021. [88] L. Chen, R. Chen, C. Yang, Y. Han, R. Zhang, X. Zhou, P. Jin, and W. Qian, “Workload-aware log-structured merge key-value store for

nvm-ssd hybrid storage,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE), pp. 2207–2219, IEEE, 2023. [89] F. T. Hady, A. Foong, B. Veal, and D. Williams, “Platform storage performance with 3d xpoint technology,” Proceedings of the IEEE, vol. 105, no. 9, pp. 1822–1833, 2017. [90] S. Sarkar, D. Staratzis, Z. Zhu, and M. Athanassoulis, “Constructing and analyzing the lsm compaction design space (updated version),” arXiv preprint arXiv:2202.04522, 2022. [91] S. Sarkar, K. Chen, Z. Zhu, and M. Athanassoulis, “Compactionary: A dictionary for lsm compactions,” in Proceedings of the 2022 International Conference on Management of Data, pp. 2429–2432, 2022. [92] Z. Zhu, Y. Wei, J. H. Mun, and M. Athanassoulis, “Mnemosyne: Dynamic workload-aware bf tuning via accurate statistics in lsm trees,” Proceedings of the ACM on Management of Data, vol. 3, no. 3, pp. 1– 28, 2025. [93] D. Mo, F. Chen, S. Luo, and C. Shan, “Learning to optimize lsm-trees: Towards a reinforcement learning based key-value store for dynamic workloads,” Proceedings of the ACM on Management of Data, vol. 1, no. 3, pp. 1–25, 2023. [94] S. Sarkar, T. I. Papon, D. Staratzis, and M. Athanassoulis, “Lethe: A tunable delete-aware lsm engine,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 893– 908, 2020. [95] S. Sarkar and M. Athanassoulis, “Dissecting, designing, and optimizing lsm-based data stores,” in Proceedings of the 2022 International Conference on Management of Data, pp. 2489–2497, 2022. [96] C. Luo and M. J. Carey, “Efficient data ingestion and query processing for lsm-based storage systems,” arXiv preprint arXiv:1808.08896, 2018. [97] W. Zhong, C. Chen, X. Wu, and J. Eriksson, “Disco: A compact index for lsm-trees,” Proceedings of the ACM on Management of Data, vol. 3, no. 1, pp. 1–27, 2025. [98] S. Lee, C.-G. Lee, D. Min, I. Park, W. Chung, A. Sivasubramaniam, and Y. Kim, “Iterator Interface Extended LSM-tree-based KVSSD for Range Queries,” in Proceedings of the 16th ACM International Conference on Systems and Storage, pp. 60–70, 2023. [99] G. Graefe, “Sorting and indexing with partitioned b-trees.,” in CIDR, vol. 3, pp. 5–8, 2003. [100] G. Graefe, F. Halim, S. Idreos, H. Kuno, and S. Manegold, “Concurrency control for adaptive indexing,” arXiv preprint arXiv:1203.6405, 2012. [101] C. Riegger, T. Vinçon, and I. Petrov, “Write-optimized indexing with partitioned b-trees,” in Proceedings of the 19th International Conference on Information Integration and Web-based Applications & Services, pp. 296–300, 2017. [102] C. Riegger, T. Vinçon, R. Gottstein, and I. Petrov, “Mv-pbt: Multiversion indexing for large datasets and htap workloads,” in International Conference on Extending Database Technology, 2020. [103] Facebook, “Column Families.” https://github.com/facebook/rocksdb/ wiki/Column-Families, 2021.

DiaLSM: Towards Write-Stall-Free Performance via Shard-based LSM-tree

Analyze & explore related research in Conceptio

Related documents