CS Paper Radar

Extending DBLog-Based Incremental Snapshots to Handle Orphan Rows in CDC Pipelines

Andreas Andreakis

cs.DB cs.DCcs.LO ·submitted 2026-11-07 15:43 UTC · v1

Abstract

Applications use heterogeneous datastores where a source feeds sinks such as search indexes or data warehouses via change data capture (CDC). As transaction logs have limited retention, CDC alone cannot bootstrap sinks, and traditional approaches either stall source writes or hold back log events. DBLog-based incremental snapshots, adopted by Debezium and Flink CDC, read tables in chunks interleaved with the log without blocking writes or long log stalls and resume where they stopped. After the initial bootstrap, a sink can drift when losing change events or receiving unintended writes. Even a repeated bootstrap can leave orphan rows that exist in the sink and not at the source. A common remedy is to populate a new empty sink, but repairing an existing sink avoids parallel pipelines, a switch and serving traffic from a drifted sink until the new sink is ready. In DBLog's original design, each chunk only emits the latest state of the rows the table still contains, so it does not handle orphan rows. We extend DBLog to delete them using what a chunk read already knows, namely the keys that the range select did not return, emitting a new kind of event that sinks apply as deletes. We also add a repair request that an external process calls with orphan candidates, which the connector checks with its own read, emitting these events for keys confirmed absent. This enables three modes. In the fully integrated mode, every chunk pass removes the orphans it finds during full or periodic repairs. In the second mode, an external drift process hands suspected orphans to the connector. The third mode combines both and is what we recommend. Together, they turn DBLog into a complete data synchronization engine whether a sink catches up on live changes or missing rows, holds wrong column values, or contains orphan rows. Their safety and convergence are formally verified in Isabelle/HOL and Lean 4.

Comment
15 pages, 4 figures, 2 tables. Isabelle/HOL, Lean 4 and TLA+ development: https://doi.org/10.5281/zenodo.24035424

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized DBLog: A Verified Contract for Interleaving Copied Rows with a Change Log

cs.DB cs.DCcs.LO ·2026-09-08 ·Andreas Andreakis
theory similarity 0.80
Abstract · 40 pages, 6 figures. Formal verification artifacts: https://doi.org/10.5281/zenodo.22643866

Change-data capture (CDC) feeds downstream systems like caches, search indexes, and data warehouses from a database's log of committed row changes. When bootstrapping, adding a table, or repairing downstream data, a pipeline must also copy existing rows. Merging this copy with the active log introduces the copy-to-log handoff problem. Changes must not fall through a gap, and older copied state must not overwrite a newer logged update or resurrect a deleted row. DBLog, developed at Netflix, addressed this problem by reading tables in chunks and interleaving those reads with the live log. Watermarks identify the changes that overlap each read, and the log wins when a copied row is stale. Debezium and Flink CDC have since adapted this design. Earlier work proved that applying the original algorithm's copied rows and logged changes in their emitted order reconstructs the source's rows, including the effect of every logged insert, update, and delete processed. Generalized DBLog asks when the same result holds for variants of that design. We state the conditions the source and capture implementation must satisfy. Once copying and reconciliation are complete, we prove that the result holds across all selected tables and key ranges even when their rows were read at different times. A single database snapshot is not required for the copy. Further logged changes advance the reconstructed state one event at a time. We establish these guarantees for classic watermarking, Debezium's signal-table and read-only modes, Flink CDC's parallel chunks, reads and dumps tied to exact log positions, and engine-consistent backups whose log position lies within known bounds. The complete theory is machine-checked in Isabelle/HOL, its core independently verified in Lean 4, and the protocols are also examined by bounded model checking in TLA+.

0.57

RetainZ: Reclaim-Time-Aware Placement for AI Checkpoints on Zoned SSDs

cs.OS cs.AR ·2026-10-04 ·Minxing Chu, Ruoxi Yang
code/data similarity 0.54
Abstract · 5 pages, 4 figures. Code and reproducibility artifacts: https://github.com/DonaldLucy/RetainZ

Solid State Drives (SSDs) are becoming the dominant medium for performance-critical storage. Zoned Namespace (ZNS) SSDs are getting more and more attractive because sequential writes and explicit zone resets reduce address-mapping, over-provisioning, and internal garbage-collection costs. However, reclaiming space requires resetting an entire zone, so deleting one file does not free its space while other files there must be kept. This erase-before-write constraint becomes a bottleneck for write-intensive workloads, particularly AI checkpointing during model training, where frequent saves of model and optimizer state compete for space with long-retained checkpoints. We observe that retention policies inherently encode when data can be retired, avoiding the need for a learned lifetime predictor. We present RetainZ, a storage backend that translates these policies into explicit reclaim epochs. Its allocator isolates long-retained data and groups objects with nearby reclaim epochs, balancing delayed space reclamation against unused space at zone ends. Evaluated on FEMU with multi-tenant streams and checkpoint manifests up to Pythia-1B, RetainZ reduces space occupied by deleted data and unused zone tails by 41.7% and mean per-input checkpoint p99 latency by 47.5% at 84% target load compared with the allocator of ZenFS, an established lifetime-aware ZNS backend, and lowers host write amplification from 1.165 to 1.003.

0.26

Adaptive Snapshots Require Visible Reads

cs.DC ·2026-08-13 ·Niv Sulimany, Tomer Cory, Erez Petrank
published similarity 0.53
Abstract · Accepted to the 40th International Symposium on Distributed Computing (DISC), 2026

Snapshots are widely used to record the state of a running execution. Snapshots have been extensively studied in the literature, with the goal of improving performance and extending functionality. In this work, we consider $adaptive$ snapshots over a set of $m$ components. Adaptive snapshots provide a Click() operation that logically creates a new snapshot and an Observe$(i)$ operation that returns the state of component $i$ at the most recent Click(). Several constructions of adaptive snapshots have recently been proposed; interestingly, none of them employs invisible reads, even though invisible reads can improve performance, sometimes significantly. In this paper, we ask whether it is possible to build an adaptive snapshot with invisible reads. We show that, even when restricting the snapshot algorithm to the single-writer, single-scanner setting, under reasonable assumptions satisfied by all existing adaptive snapshot implementations, adaptive snapshots with invisible reads are not linearizable.

0.27

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.52
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

Checkpoint Reload Explains Most of the Measured State Gap in Two State Discovery Reproductions

cs.LG ·2026-10-26 ·Weijia Han, Lisha Qu
published similarity 0.50
Abstract · Equal contribution, 11 pages, 3 figures, 7 tables. Accepted at the NeurIPS 2026 Workshop on Foundation Models for Temporal Systems (FMTS 202…

Temporal models that maintain per-sequence latent states during training must reconstruct those states when the stored table is unavailable at inference. This creates a basic consistency question: do the reconstructed states agree with those formed during training? We study this question for State Discovery in World Machine, which updates stored states in parallel each epoch but performs inference by sequential rollout from an all-zero start. On Toy1D, we analyze two paired-checkpoint runs whose decoded-state MSE is 27 to 36 percent above the published value. We compare the stored table with rollouts under the best-validation checkpoint reloaded after training and the last-epoch weights that wrote the table. Matching the rollout to the table-writing weights removes 90 to 91 percent of the mean per-dimension Wasserstein-1 distance. Causal distillation and frozen SD updates do not satisfy their pre-specified criteria under either checkpoint. Overall, checkpoint reload accounts for most of the measured gap in these runs.

0.32

A Log-Timescale Perturbation Bound for Selective State Space Models at Every Sequence Length

cs.LG ·2026-11-16 ·Jack Humphries, Daniel Midgley
theorycode/data similarity 0.50
Abstract · 22 pages, 3 figures, 1 table. Code and recorded runs: https://github.com/jackdoesjava/mamba-v-lob

Mamba models deployed on streaming data, such as limit order book updates, run far past the sequence lengths they were trained on. A guarantee on how much a small change of input can move the hidden state therefore has to hold at every length. The closest existing bound we know of measures the change of the timescale additively, and it grows linearly with the sequence length unless the timescale is bounded away from zero. In this paper, we measure the change on a log scale instead. The key observation is that the decay factor of each step then moves by at most a fixed fraction of that step's input weight, so the per-step errors cannot pile up. Using this, we prove that two runs of a selective-scan cell from a common start stay within a bound that holds at every length, shrinks to zero with the size of the change and needs no lower bound on the timescale. We give a construction showing that, for small changes, this bound is within a factor of about 2 of the best possible, and we extend it to the update used in Mamba's released code when the timescale is bounded above. We then evaluate block-level bounds built from the theorem on two small models trained on one day of order book data. With a bounded timescale, a bound built on the existing analysis is tighter than ours for at most the first 8 steps. With Mamba's softplus timescale, whose certified lower bound is as small as $10^{-21}$, it is looser at every length. Our bounds hold for every input to a block, but they remain more than five orders of magnitude above the changes that gradient attacks find.

0.51

Nemo: Efficient Caching with Index Pushdown for Disaggregated OLTP Databases

cs.DB cs.DC ·2026-10-23 ·Wenjie Hu, Xinjing Zhou, Zhihan Guo, Xiangpeng Hao, Xiangyao Yu
published similarity 0.49
Abstract

Storage-disaggregated databases decouple compute from storage, improving elasticity but suffering from network bottlenecks. Most cloud databases use page-based B+trees and buffer pools. Under disaggregation, each index traversal incurs serial network round-trips. Page-granularity transfers and caching also amplify network traffic and lower cache efficiency. Pushing down the full index to storage and caching only hot records at compute is appealing, but an efficient design must (1) provide a holistic record cache that accelerates both point and range queries, (2) mitigate the negative search penalty of confirming non-existence via remote probes, and (3) enforce phantom protection despite the index being encapsulated by the storage service. We introduce Nemo, a holistic index-and-buffer design optimized for storage-disaggregated OLTP with index pushdown. Nemo employs a tree-structured record buffer that unifies caching and buffering and accelerates both point and range queries. It further reduces the negative search penalty by caching negative search results. Nemo provides phantom protection that requires no knowledge of the storage-side data layout and is robust against large key domains, varying data skew, and partition schemes. Experiments show that Nemo outperforms page-based B+Tree and the state-of-the-art 2-Tree by up to 11.42x and 2.97x on positive point queries, and achieves up to 4.76x speedup on negative searches over a hash-indexed record cache. For phantom protection, Nemo outperforms PCL by up to 1.55x even under a dense key domain. Moreover, Nemo maintains stable performance while PCL degrades sharply as the key domain grows large and sparse.

0.39

Returning to Development States: When Full Sandbox Snapshots Help Coding Agents

cs.LG cs.SE ·2026-10-09 ·Daniel Thi Graviet, Tanmay Shah
similarity 0.49
Abstract · 7 pages, 6 figures. Preprint. Not peer reviewed

Coding agents often make useful progress before they fail, but retry-from-scratch discards the machine state created along the way. This makes failure recovery an interesting search problem: if intermediate environment states preserve meaningful progress, restoring and branching from them could outperform repeatedly restarting from the initial state. We implement Go-Explore-style search over full Daytona snapshots and find that higher and more efficient solve rates depend mainly on progress that sits outside the repository, such as databases, services, and other runtime state. Our results suggest that full-snapshot search is most effective when long-horizon coding work spans multiple services whose state cannot be reconstructed from a single diff.

0.39