Papers for

storage system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Sail improves learned index query speed with hybrid node structures

SAIL: Self-Adaptive Index Learning with Hybrid Models (Extended Version)

Abstract: Learned index structures have demonstrated a significant improvement in query performance over traditional index structures. The majority of learned indexes use a uniform node structure throughout their index structures. A few studies show that combining multiple types of node structures can lead to indexes that better adapt to local key-set distributions, hence yielding query efficiency gains. Following this line of work, we propose a learned index structure named SAIL that supports a wide range of different candidate node structures for both leaf and inner nodes, selected via cost models based on data driven approximations. We design an efficient construction algorithm that recursively partitions the key-set to be fitted by the candidate node types. Experiments demonstrate that SAIL achieves 2x improvement over existing learned indexes in query time, with similar memory consumption and index build times.

Tue 10 NovDatabases
The gist
Indexes help computers find data quickly, but traditional ones can be slow or bulky. The authors created SAIL, a new kind of index that uses different types of parts inside, chosen based on what fits the data best. This makes searching much faster without needing much more memory or time to build the index. Their tests show it can be twice as fast as older learned indexes.
Open → 2611.13856v1

Data deduplication achieves strong compression with small edits allowed

Asymptotic Analysis of Data Deduplication Under a Constant Edit Model

Abstract: Data deduplication has become increasingly important in large-scale storage systems, driven by the rapid growth of digital data. By identifying and removing repeats in the data stream, deduplication saves storage space more efficiently than traditional compression methods. In this paper, we study the performance of variable-length deduplication and multi-chunk deduplication algorithms from an information-theoretic perspective, focusing on data streams where repeats are approximate rather than exact. We consider two probabilistic source models in which source strings consist of repeated blocks that are modified by either a constant number of substitution edits or burst-insertion edits per block, the latter capturing the localized edit patterns commonly observed in real-world data. For both models, we show that variable-length deduplication achieves asymptotically arbitrarily large compression ratios, and that multi-chunk deduplication achieves compression within a constant factor of the source entropy under mild conditions.

Fri 6 NovInformation Theory
The gist
Data deduplication is a way to save storage space by detecting and removing repeated parts of information. This study looks at how well deduplication works when parts of the data are similar but not exactly the same because of small changes. The authors find that some deduplication methods can still compress data very efficiently even if there are a few edits in repeated blocks. Their results apply to realistic situations where errors or changes happen in bursts within data.
Open → 2611.09842v1

Lossless coding matches symbol frequencies exactly for new applications

Lossless Source Coding with Marginal Distribution Constraint

Abstract: We consider lossless source coding with a marginal distribution constraint on the encoding symbols (SC-MDC). Unlike distribution matching, signal shaping and homophonic coding which require the symbols to be (approximately) i.i.d. following a target distribution, SC-MDC requires each symbol to have a marginal distribution that exactly matches the target distribution, which can be regarded as a perfect perceptual quality constraint on the symbols, and may have applications to wear leveling, source coding with cost and steganography. We give nonasymptotic lower and upper bounds on the optimal encoding length, and exactly characterize the coding rate (or the first-order term of the length) when the source distribution or the target distribution is uniform, or when the source is an i.i.d. sequence.

Wed 4 NovInformation Theory
The gist
This paper studies a way to compress data without losing any information, but with a twist: the frequency of each symbol after encoding must match a given pattern exactly. This requirement is stricter than previous methods which only aimed for similar or approximate distributions. The authors provide mathematical formulas that describe the best possible compression lengths when this exact-frequency condition holds, especially in some special cases like uniform sources or uniform target distributions. Their work could help in areas where the exact distribution of encoded symbols matters a lot, such as device wear leveling or hiding information.
Open → 2611.07156v1

Adaptive data placement cuts ssd write overhead on shared servers

eBPF-Driven Adaptive Lifetime-Aware Data Placement for Shared FDP SSDs

Abstract: NVMe Flexible Data Placement (FDP) reduces SSD write amplification by separating data with different lifetimes to minimize garbage collection (GC) copying. However, on shared servers, multiple tenants generate more lifetime classes than the available placement handles. Existing approaches rely on static mappings or application-specific knowledge, failing to capture runtime lifetimes and adapt to changing workloads. The challenge is to identify which data die together and determine which classes should be separated to maximize GC savings under a limited handle budget. We present eFDP, an eBPF-based system that automatically learns data lifetimes and manages FDP placement for unmodified applications on a stock Linux kernel. By tracking writes and invalidations, eFDP identifies lifetime classes and estimates the GC copying saved by separating them. It first assigns each tenant a handle, then allocates the remaining handles to the separations offering the greatest savings. It also re-plans placement when active tenants change. With four database tenants on an emulated FDP SSD, eFDP eliminates twice as much excess write amplification as tenant-level isolation and improves every writing tenant's throughput by 19-23%. On an enterprise FDP SSD, given RocksDB's levels, it matches a manually optimized placement using three handles instead of five. After a tenant switch, eFDP re-plans within seven minutes and maintains 25% lower write amplification than the original layout even after an hour.

Wed 4 NovOperating Systems
The gist
SSDs slow down and wear out faster when they repeatedly rewrite data in the same places. To help, Flexible Data Placement (FDP) separates data by how long it will be kept, reducing unnecessary work. The authors of this paper created eFDP, a system that automatically and continuously learns how long different data lives and adapts where data is stored on SSDs used by many tenants at once. eFDP improves performance and reduces extra writing, even as tenants change over time.
Open → 2611.06461v1

Callosal improves cluster memory caching with strong consistency

Callosal: Rethinking the Kernel Page Cache for Disaggregated Storage and Memory

Abstract: Classic distributed filesystems like NFS centralize filesystem operations on a server and use custom, filesystem-specific approaches for managing cache consistency across client nodes. This limits scalability, and it leads to weak consistency, ruling out applications that concurrently access and mutate shared files. Our key insight is that these legacy designs are now too storage-centric; with today's large memories, OS page caches do most of the "heavy lifting" in accessing data, not the filesystem and block storage layers. In response to this, we present Callosal, a page cache for a cluster of machines that is centered on shared disaggregated memory. Rather than serializing operations through a filesystem server and using ad hoc caching like NFS, Callosal is built around the existing Linux page cache paths and is accelerated by RDMA and programmable switches. Callosal delivers the strong consistency that programs expect with local filesystems (like in ext4 and tmpfs) while avoiding the additional network access delays and bottlenecks that host-based solutions incur. We compare Callosal against NFS, CephFS, and local filesystems; often Callosal can provide caching performance similar to local filesystems while also scaling across nodes. For mixed read/write workloads, on average Callosal has 4.6x higher throughput than NFS when contention is not extreme, and it offers strong consistency guarantees like CephFS, while outperforming it. For a file-backed key-value store with 1% writes and uniform access, Callosal scales 1.7x across 4 nodes, while CephFS collapses across nodes.

Mon 26 OctOperating Systems
The gist
Traditional network file systems make one server handle all file operations, which causes slowdowns and weak guarantees when multiple computers try to change the same files. The authors argue that memory caches are now more important than storage devices for fast data access. They created Callosal, a new system that shares memory caches across computers using specialized networking hardware, allowing programs to get strong consistency similar to local files while avoiding network delays. Tests show Callosal is faster and scales better than existing network file systems for mixed reading and writing tasks.
Open → 2610.36347v1

Reed Solomon codes exact repair extension degrees identified

Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound

Abstract: We study the minimum extension degree required for a Reed--Solomon code to admit exact $\mathbb{F}_q$-linear repair at the cut-set bound from every prescribed set of $d$ helpers. Let $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. For every prime power $q$ and all $3\le k<d<n\le2d-2$, we prove that the minimum degree over $\mathbb{F}_q$ is exactly $sQ_s(n)$. When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with $n>2d-2$, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an $\mathbb{F}_p$-linear repair scheme on the same code, where $p$ is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

Sun 25 OctInformation Theory
The gist
Reed Solomon codes are a way to protect data by spreading it over many parts. Fixing or repairing these codes efficiently needs extra data parts, called extension degrees. The authors figured out the exact smallest number of these parts needed to perfectly fix the data under certain conditions. They also showed that even if the repair method isn’t simple (nonlinear), the smallest number of parts needed doesn’t get any smaller than in linear methods. This helps understand the limits of how efficiently data can be repaired.
Open → 2610.34377v1

Logarithmic gap found between LZ77 and grammar compression methods

Logarithmic Separation between LZ77 and LZ-End and Grammar Compression

Abstract: We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.

Fri 23 OctInformation TheoryData Structures and Algorithms
The gist
The paper finds that one popular data compression method, called LZ77, can compress some data much more efficiently than two other methods called LZ-End and grammar compression. Specifically, the difference in how compact the results are can grow like the logarithm of the input size, meaning the gap can be significantly large as data gets bigger. The authors establish this by proving a theoretical limit, showing these methods are not equally powerful for all inputs.
Open → 2610.32818v1

Fast on-ssd index speeds key-value cache recovery and matching

SARP: An On-SSD Index for KVCache with Fast Prefix Matching and Recovery

Abstract: Distributed LLM serving relies on a global index to locate reusable key-value cache (KVCache) blocks through prefix matching. Losing the index after a crash or restart forces affected requests to recompute existing KVCache on GPUs. Persisting the index restores access after a failure. Existing persistent indexes face a tension between prefix-matching performance and recovery time. A snapshot-backed in-memory index supports fast prefix matching, but rebuilding the full index delays recovery. An on-SSD index avoids this rebuild, but adds storage accesses to prefix matching. Our core insight is that extending a matched prefix over a short span typically requires distinguishing only a few token sequences, suggesting that sparse in-memory routing state may suffice. Prefix matching also accesses block metadata in sequence order, allowing metadata for consecutive blocks to be retrieved together. We present SARP (Sparse Adaptive Routing and Packing), an on-SSD KVCache index for fast recovery and prefix matching. SARP groups consecutive block IDs and metadata into segments to amortize storage accesses across multiple blocks. A compact in-memory routing directory identifies candidate segments using entries at selected block positions. SARP limits segment retrievals and uses compact filters to prioritize candidates with longer potential matches. After retrieval, SARP verifies block IDs against the query and reuses only KVCache blocks covered by the verified prefix. After a restart, SARP restores the sparse routing directory from a snapshot. Across four multi-turn chat and agentic workloads, SARP recovers 8.0x to 77.5x faster than the in-memory index baselines and delivers 1.15x to 66.6x the request throughput of the on-SSD index baselines, while reusing only 0.0030% to 0.029% fewer tokens than exact prefix matching.

Mon 19 OctDatabases
The gist
Large language models use many small cache blocks to answer questions faster by reusing past information. When the system crashes, recovering these cache blocks is slow and costly. The authors have created SARP, a new way to store an index on solid-state drives that speeds up finding cache blocks and recovering after crashes. SARP uses a clever mix of a small in-memory guide and grouped data on SSD to balance speed and recovery time better than past methods.
Open → 2610.26849v1

Kv-cache offloading in llm serving trades predictability for latency

Characterizing Predictability-Latency Trade-offs of KV-Cache SSD Offloading in LMCache for LLM Serving Systems

Abstract: KV-cache offload is widely used to stretch GPU memory for LLM serving, but its storage behavior has not been characterized at the block-device level. In this paper, we study LMCache through realworld multi-session workloads that span same/different context x same/different prompt, using over 100 stateless requests per workload. Our comparison is observational rather than factorial: it contrasts two realizable deployment snapshots -- LMCache 0.3.0 with buffered I/O and the kernel page cache, and LMCache 0.3.16 with prefix-aware deduplication and O_DIRECT. Key findings define the paper. First, the legacy stack appears almost read-free at the SSD layer in all four workloads, but a flush_ram experiment shows that this is conditional on page-cache warmth: once the cache is evicted, the same path issues about 1 GB of sequential reads in 683 ms. Second, deduplication delivers a dramatic write reduction only for the exact-repeat workload: one set collapses from 1.62 GB to 11.75 MB of writes, while the other three sets remain in the 2-5 GB range. Third, O_DIRECT converts a hidden and bimodal read cost into an explicit and stable one: on one set, warm TTFT rises from 27 ms to 93 ms because each of the 99 warm requests re-reads the same ~12 MB partial chunk from SSD. The main conclusion is therefore not "newer is better," but a system trade-off: predictability versus average-case latency.

Thu 15 OctOperating Systems
The gist
LLM serving systems often save GPU memory by storing large key-value cache data on SSDs, but the way these SSDs behave has not been well understood. The authors study two versions of LMCache software with different storage techniques to see how they influence read/write behavior and speed. They find that newer techniques trade stable and predictable response times for sometimes slower average performance. This helps system builders choose between consistent speeds or faster responses depending on their needs.
Open → 2610.21249v1

Codes protect data and related function values against errors in lee metric

On Function-Correcting Lee Metric Codes with Data Protection

Abstract: Function-correcting codes are designed to protect the function values of a prescribed function against errors. Every error-correcting code that provides data protection inherently offers some degree of protection for functions defined on the data. In this work, we introduce a class of codes over $\mathbb{Z}_m$, termed function-correcting Lee metric codes with data protection (FCLMCs with data protection), which simultaneously provide error protection for both the data and the corresponding function values under the Lee metric. We consider codes that provide protection against a prescribed level of error for the function values that exceeds the level of protection guaranteed for the underlying data. We present a general construction of these codes and derive lower and upper bounds on the optimal redundancy, including a Plotkin-type lower bound. Furthermore, we derive explicit upper bounds on the redundancy of FCLMCs with data protection for several important classes of functions, including locally binary Lee functions, the Lee weight function, and the modular sum function. Finally, since the Lee metric coincides with the Hamming metric over $\mathbb{Z}_2$, all of our results remain valid over $\mathbb{Z}_2$ with respect to the Hamming metric.

Thu 8 OctInformation Theory
The gist
Protecting information from errors can also protect the answers to questions asked about that information. The authors focus on special codes that not only fix errors in the raw data but also better protect the results of specific functions applied to that data. They create a new type of code that works over numbers with a certain error measure called the Lee metric, ensuring stronger protection for function results than the data itself. Their work includes ways to build these codes and mathematical limits on how efficient they can be. This also applies to the simpler case of binary data and the common Hamming error measure.
Open → 2610.12217v1

Linux large reads reveal wait time causes and enable performance tuning

Behind a Simple Read: Understanding Work and Waiting in the Linux I/O Stack

Abstract: A simple read interface provides uniform functional semantics, but not equally simple or predictable performance behavior. We use synchronous large-buffer reads in Linux as an observation window and decompose the buffered-read path end to end, distinguishing work volume, processing time, and critical-path exposure. We find that Linux reduces metadata work through large folios and overlaps most cold-read copying with device waiting, but these mechanisms depend on access advice, folio granularity, cache state, and backend execution. Using an experimental kernel prototype, we validate additional opportunities from out-of-order early copying and opportunistic parallelism, while showing that faster request submission does not improve end-to-end performance when SSD supply is already sufficient. To explain device waiting, we abstract first-completion wait $F$ and subsequent completion capacity $B_{CQ}$ from finite request-batch completion timelines. Measurements on a real SSD characterize how they vary with request size and batch size, while MQSim experiments connect them to internal device mechanisms and distinguish finite-batch completion from sustained throughput. We then construct a cross-layer wait chain along the actual folio--bio--request mapping. Independently calibrated device parameters predict waiting at the block layer and at read_pages with errors no greater than approximately 6.9% and 3.2%, respectively. Finally, four use cases apply the model and wait chain to parallel submission, Linux readahead, dependent-read layout, and polling versus sleeping. Their gains, no gains, and gain reversals form a closed loop from observation and modeling to explanation and control, providing a measurable basis for performance decisions in layered I/O stacks.

Wed 7 OctOperating Systems
The gist
Reading data in Linux may seem like a simple operation, but its speed depends on many hidden steps and waiting times. The authors studied how big read requests are handled, showing how the system overlaps data copying with device waiting to save time, but these benefits rely on things like memory layout and cache state. They built a model to predict waiting times accurately and used it to understand when speeding up parts of the system helps or not. Their work helps explain why read performance varies and guides better design and tuning of Linux I/O.
Open → 2610.10137v1

Custom data compression algorithms improve speed and size by two times

The Case for Synthesized Data Compression

Abstract: Compression is a fundamental tool in data management. Today's compression schemes are generally designed by hand to apply to many different types of data (e.g., run length encoding or arithmetic encoding), leading to a zoo of general-purpose algorithms which work well for many datasets, but may not be optimal for any specific dataset. Inspired by recent advancements in agentic coding, we propose synthesizing custom-tailored data compression algorithms on a per-dataset basis. Unlike prior work using agents to synthesize database components, a data-specific compression algorithm can be fully verified at construction time, alleviating most correctness concerns. Modern file formats, like AnyBlox and F3, allow including the synthesized code alongside the data itself. Experimentally, we show that our synthesis agent can expand the compression-factor/decompression-speed Pareto front, outperforming general-purpose methods by nearly $2\times$ in compression factor.

Wed 7 OctDatabases
The gist
Compressing data helps save space but common methods are made to work well on all kinds of data, not perfect for any one type. The authors suggest creating special compression programs designed just for each specific dataset. These custom programs can be fully checked for accuracy before use. They also showed their new approach can store data in about half the space or decompress it twice as fast as general methods.
Open → 2610.09913v1

Function-correcting codes improve symbol-pair error handling in psks

Function-Correcting Lee-distance Codes for Symbol-Pair Read Channels

Abstract: Function-correcting codes (FCCs) protect specified function evaluations of messages against errors while reducing the redundancy required for reliable communication. We study FCCs for symbol-pair read channels, motivated by high-density storage systems that read overlapping symbol pairs. Phase-shift keying (PSK) modulation is well-suited to such systems due to its bandwidth efficiency and noise robustness. While FCCs for symbol-pair read channels have been studied under the Hamming metric, the Lee metric is a more appropriate error model for $q$-ary PSK and, hence for $q$-ary symbol-pair read channels. We generalize the symbol-pair Lee distance, previously defined only over $\mathbb{Z}_4$, to $\mathbb{Z}_q$, $q\ge2$, and introduce function-correcting symbol-pair Lee-distance codes (FCSPLCs) over $\mathbb{Z}_q$, specializing to $q=2^m$, $m\ge1$, for $2^m$-ary PSK constellations. We investigate their redundancy requirements by introducing irregular-pair Lee-distance codes and relating the optimal redundancy of FCSPLCs to the shortest length of such codes. We derive Plotkin-type and Gilbert--Varshamov-type bounds on the optimal redundancy through lower and upper bounds on the shortest length of irregular-pair Lee-distance codes. For bijective functions, we obtain corresponding Plotkin-type and Gilbert--Varshamov-type bounds for classical Lee metric codes for symbol-pair read channels over $\mathbb{Z}_q$, which, to the best of our knowledge, are the first such bounds for the Lee metric symbol-pair setting. We then specialize the FCSPLC framework to pair-locally bounded functions, the Pair-Lee weight function, and the Pair-Lee weight distribution function, giving explicit constructions and corresponding bounds on the optimal redundancy. Finally, for linear functions, we derive a Plotkin-type lower bound on the optimal redundancy.

Wed 7 OctInformation Theory
The gist
Modern storage systems read data in overlapping pairs of symbols, which can cause unique errors. The authors study special codes that protect certain computations on messages, rather than the entire message, for these symbol-pair errors. They extend previous math models to better fit common signal types used in communication, called phase-shift keying (PSK). Their work provides new methods and limits on how efficiently such codes can be designed for error correction in these settings.
Open → 2610.09491v1

Scan-resistant cache gadgets improve storage performance and reliability

SR-Gadgets: Make Scan-Resistant Caching Practical

Abstract: Block caches commonly serve scan-heavy I/O workloads, motivating extensive studies on scan-resistant eviction algorithms. Many of these algorithms adopt a multi-queue structure. However, they focus primarily on one-time scans and do not handle repeated scans well. Two important challenges from repeated scans are miss-ratio cliffs, where a small increase in cache size sharply reduces the miss ratio, and Belady's anomalies, where increasing the cache size increases the miss ratio. In this paper, we first develop two quantitative metrics to measure these behaviors. With these metrics, we find that LIRS is the only multi-queue algorithm that is scan-resistant (almost cliff- and anomaly-free). Contrary to conventional wisdom, we show that stack distance is not the secret sauce that makes LIRS scan-resistant. Instead, regulating the queues are the key to its scan resistance. Based on these insights, we design the \gadgetprefix Gadgets, easy-to-integrate augmentations that make existing algorithms scan-resistant without changing their eviction heuristics or queue structures. We implement the \gadgetprefix Gadgets in five algorithms: S3-FIFO, SIEVE, ARC, 2Q, and TinyLFU, and make them scan-resistant. Evaluated on 5,538 production traces, all augmented algorithms outperform their base versions, reducing miss ratios by up to 23.1% while consistently reducing cliffs and Belady's anomalies across the production traces.

Thu 24 SeptPerformance
The gist
Cache systems store data temporarily to speed up computers, but data 'scans' can cause sudden drops or unexpected increases in cache misses, hurting performance. The authors studied these problems and found that a popular algorithm called LIRS avoids them well—not because of earlier assumed reasons, but because it manages its data queues smartly. Using this insight, they created small add-ons called Gadgets that make other cache algorithms handle scans better without changing their core methods. Testing these Gadgets on thousands of real data traces showed they reduce missed data fetches and avoid weird caching problems.
Open → 2609.30468v1

Amortized relaxed codes enable efficient data recovery with low probes

Amortized Relaxed Locally Decodable Codes

Abstract: Locally decodable codes (LDCs) enable recovery of any message symbol by probing only a small number of positions in a possibly corrupted codeword. The central parameters of an LDC are its rate, locality, and error tolerance. Ideally, one would like all three parameters to be constant. However, classical lower bounds show that such codes cannot exist. A recent line of work introduced amortized locally decodable codes (aLDCs), in which the decoder is tasked with recovering an entire block of consecutive message symbols rather than a single symbol. While prior work obtained ideal aLDCs with constant rate, constant error tolerance, and constant amortized locality, those constructions relied on either shared randomness hidden from the channel or computational assumptions restricting the channel. Another well-studied relaxation is the notion of a relaxed locally decodable code (RLDC), in which the decoder may output a special failure symbol $\bot$ rather than risk decoding incorrectly. In this work, we introduce the notion of an amortized relaxed locally decodable code (aRLDC), combining amortized decoding with the relaxed decoding paradigm. Unlike prior ideal aLDC constructions, our model is fully information-theoretic and makes no assumptions about shared randomness or computational limitations of the adversarial channel. We construct the first aRLDC with constant rate, constant error tolerance, and constant amortized locality. Moreover, for any block of length $Ω(\mathrm{polylog}(k))$, our decoder achieves amortized locality $1+δ^{1 - o(1)}$, where $δ$ is the error tolerance parameter. Thus, asymptotically, recovering a long block requires essentially less than two codeword probe per message symbol recovered. By contrast, without amortization no RLDC can simultaneously achieve constant rate, constant error tolerance, and constant locality.

Mon 14 SeptInformation TheoryDiscrete Mathematics
The gist
Locally decodable codes let you recover parts of a message by checking only a few spots in the coded data, even if some parts got messed up, but making them work well for many parameters at once is hard. The authors worked on a new kind of code that combines two relaxations—decoding multiple message parts at once and allowing the decoder to say "I don’t know" sometimes instead of making mistakes. They built such codes that achieve good rates, tolerate errors, and require very few probes per symbol on average, without relying on assumptions about the communication channel or secret randomness. This advances the theoretical possibilities for error-correcting codes in noisy environments.
Open → 2609.16332v1