CS Paper Radar

Ditto: Generalized Reconfigurable Linearizable Reads

Aleksey Panas

cs.DC cs.DB ·submitted 2026-09-30 20:49 UTC · v1

Abstract

Linearizability gives developers the illusion that operations on a distributed datastore execute sequentially on a single machine. Providing it is expensive, so numerous specialized reads algo- rithms have been proposed to make reads significantly faster without sacrificing linearizability, which matters because most workloads are read-dominant by orders of magnitude. Yet, none of these algorithms is the best choice for every deployment. We show why with a framework that classifies these algorithms into a generalized space together with a mathematical analysis of their latencies as a function of this generalization. The analysis exposes two fundamental tradeoffs, one between read and write latency and one between read and write tolerance to network variance, which together leave the best algorithm dependent on network and workload conditions that vary over time. It also exposes a gap: there is a way to minimize the delay a read incurs when it overlaps a concurrent write, at no cost to writes, yet exist- ing algorithms can apply it only for a subset of the tradeoff space, forcing any deployment that needs the full space to settle for a strictly worse solution. We close this gap with a new algorithm, Pairwise Quorums, and build a second, Ditto, that reconfigures across the space at runtime as conditions change. Together they subsume every existing algorithm under our model: against each, the combination is either strictly better, or reconfigures to match it where a genuine tradeoff applies.

Closest papers

Nearest neighbours by meaning across the whole index.

Revisiting Index Performance under High Cache-Miss Penalties

cs.DB ·2026-11-16 ·Mathew M. Kim, Beomseok Nam
similarity 0.68
Abstract

Modern data-intensive applications often query very large datasets, making index performance critical. Recent index structures exploit the fine-grained access capabilities of emerging storage devices such as DCPMM and CXL. However, existing benchmarks typically evaluate indexes in isolation using saturated, closed-loop workloads that emphasize maximum throughput. Such workloads favor highly concurrent designs while overlooking the application work that follows an index lookup and competes for cache, memory bandwidth, and CPU resources. We present AuxBench - a microbenchmark that evaluates indexes as auxiliary access paths within larger application workloads. Using AuxBench, we evaluate four byte-addressable indexes under controlled post-lookup memory activity, concurrency, and request arrival patterns. Our experiments show that post-lookup memory activity can change the relative performance of competing indexes, that concurrency-oriented designs may lose their advantages when substantial application work is introduced, and that time-varying request arrivals can produce severe tail latency near saturation. These findings demonstrate why index-only benchmarks may not adequately predict performance in larger application workloads

0.21

KVStream: Adaptive Parallel Storage Management for KV Caching in Large-Scale LLM Serving

cs.DC ·2026-10-22 ·Avinash Maurya, Jaiaid Mobin, Jie Ye, M. Mustafa Rafique, Franck Cappello +1 more
similarity 0.65
Abstract

Long-context LLM serving for agentic, coding, and document workloads reuses prefixes whose key-value (KV) cache outgrows GPU and host memory, putting storage I/O on the critical path of the inference step for retrieving prefixes. A single node-local NVMe absorbs all retrievals, while the parallel file system or cloud file store that nodes already mount carries almost no inference traffic. We cast prefix retrieval as aggregate-bandwidth scheduling across these tiers and present KVStream, a KV cache engine that batches a step's reads, defers writes behind the forward pass, replicates each chunk on every tier, and lets each tier adaptively claim the next unread chunks once it is free. Our performance model shows this routing attains the aggregate-bandwidth bound without prediction or tuning, whereas any static split misses it by a margin that grows as per-tier bandwidths drift or fluctuate. It also predicts that the time-to-first-token (TTFT) gain grows with load, as faster retrieval drains the queue, and disappears when host memory or arrival order keeps reuse in cache. Plugged into LMCache and evaluated on four models, six datasets, and up to 128 GPUs, KVStream retrieves within 5% of the bound, delivers up to 1.49$\times$ higher offline throughput than LMCache, and lowers mean TTFT by up to 6.1$\times$ under bursty arrivals.

0.06

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

cs.OS ·2026-10-07 ·Yang Shen, Wenzhe Zhang, Yong Dong, Min Xie, Wei Zhang +2 more
similarity 0.64
Abstract · 30 pages, 15 figures, 3 tables

A simple read interface provides uniform semantics but unpredictable performance. Using synchronous large-buffer Linux reads, we decompose the buffered-read path into work volume, processing time, and critical-path exposure. Reducing local cost or accelerating request submission need not shorten a complete read. Linux uses large folios to reduce metadata work and I/O-copy overlap to hide most cold-read copying; an experimental kernel prototype shows that more aggressive overlap and parallelism can shorten the host path when these mechanisms fail. Device waiting dominates SSD cold reads. We abstract first-completion wait F and subsequent completion capacity B_CQ from request-batch timelines. Real-SSD experiments characterize their variation with request and batch size, while MQSim traces explain their internal origins. A wait chain along the folio-bio-request mapping connects device completion to upper-layer waiting. Under strict batching, the median absolute cross-layer prediction error is at most 7.43%. Finally, we apply the completion model and wait chain to request supply, Linux readahead, data layout, and waiting policies. Cases cover gains, no gains, and reversals, comparing predictions with interventions to close the loop from observation and modeling to understanding and control and provide a measurable basis for layered I/O decisions.

0.22

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

cs.OS ·2026-10-26 ·James McMahon, Amit Samanta, Seung-seob Lee, Ryan Stutsman, Anurag Khandelwal
similarity 0.63
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.

0.11

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

cs.DB ·2026-09-13 ·Hongsu Byun, Safdar Jamil, Honghyeon Yoo, Sungyong Park, Myungcheol Lee +3 more
top venue similarity 0.62
Abstract · Accepted to the 43rd IEEE International Conference on Data Engineering (ICDE 2027)

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 DiaLSM, an internally shard-based LSM architecture. Instead of forcing all writes through one pipeline, DiaLSM 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, DiaLSM achieves up to 2.4x 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.

0.40

FlatCake: A Flat KVCache Storage Architecture for LLM Serving

cs.DC cs.OS ·2026-10-28 ·Xin Huang, Teng Ma, Zhuoran Li, Yibo Zhao, Zhaoshi Li +5 more
similarity 0.62
Abstract · 10 figures

KV cache reuse accelerates LLM serving, but existing systems manage host DRAM and NVMe SSD as a tiered hierarchy where DRAM acts as an intermediate cache. Production LLM workloads break both premises of this hierarchy. First, bimodal reuse defeats DRAM temporal filtering, since workloads are dominated either by one-shot blocks with long reuse distances or by multi-gigabyte agentic sessions that exceed DRAM capacity, putting SSD on the critical read path. Second, DRAM staging and eviction-ordered layout bottleneck SSD restoration. Holding host staging buffers for in-flight prefixes causes contention under load that aborts prefetches, while incremental eviction scatters a session's blocks across the SSD and prevents large sequential reads. We present FlatCake, a flat KV storage architecture that exposes host DRAM and NVMe SSD as peer media in a unified 64-bit address space. Exploiting the fact that KV blocks are write-once, immutable, and reused at session scope, FlatCake places each block directly onto its target medium in session-contiguous, layer-major order at creation time and never migrates it. FlatCake streams coalesced SSD reads directly into a bounded GPU window via GPUDirect Storage and decouples DRAM and SSD request queues to prevent head-of-line blocking. On a production Claude Code trace with DeepSeek-V4-Flash, FlatCake sustains a 94% cache hit rate as load increases (versus 64% for Mooncake), eliminates Mooncake's $6.5\times$--$6.7\times$ SSD read amplification, and reduces peak-load mean TTFT by $1.6\times$ while improving total token throughput by $1.6\times$. Across 8K--128K contexts on Llama-3.1-70B, FlatCake further reduces mean TTFT by up to $2.4\times$ over Mooncake and $1.8\times$ over Mooncake-GDS.

0.13

Synchronized Rebuilds:The Hidden Cost of Concurrent Inserts in Learned Indexes

cs.DB ·2026-10-24 ·Emmilly Immaculate Namuganga, Laurent Bindschaedler
benchmark similarity 0.62
Abstract · 15 pages, 4 figures, 4 tables

Nine years after learned indexes were proposed, their advantage on read-mostly data is well established, and a standard benchmark rates their best concurrent version as almost ready for use. Across more than 4000 runs of 13 indexes, we find that each design pays for concurrent inserts in a different way. Gapped-array indexes rebuild their nodes in synchronized bursts, at positions that follow from three constants in the source. Model-placement indexes use three to four times the memory, buffered indexes take two to three times as long. Three of five concurrent learned indexes lost keys or stopped making progress. Standard benchmarks miss both the bursts and the lost keys. The bursts cost far more than in B-trees because each rebuild copies a node a thousand times larger than a page and, under concurrency, blocks every operation that reaches the node. The typical B-tree fix of randomizing node density only spreads the bursts out, while smaller nodes trade them for longer run times at scale. Two standard systems techniques remove them: a buffer that exists only while a node is rebuilt, and background rebuilds. We show that on 400M real keys, these techniques reduce the number of inserts whose latency exceeds 100$μ$s by two orders of magnitude at one thread, and by one at sixteen when spare cores run the background threads, at a third to half the run time of the buffered designs.

0.32

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

cs.OS ·2026-10-15 ·Ying He, Dingsen Shi, Yanbo Dai, Donger Chen, Harry Fu +3 more
published similarity 0.62
Abstract · 6 pages, 3 figures, 3 tables

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.

0.18