CS Paper Radar

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

Andreas Andreakis

cs.DB cs.DCcs.LO ·submitted 2026-09-08 02:44 UTC · v4
theory

Abstract

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

Comment
40 pages, 6 figures. Formal verification artifacts: https://doi.org/10.5281/zenodo.22643866

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DB cs.DCcs.LO ·2026-11-07 ·Andreas Andreakis
similarity 0.80
Abstract · 15 pages, 4 figures, 2 tables. Isabelle/HOL, Lean 4 and TLA+ development: https://doi.org/10.5281/zenodo.24035424

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.

0.19

Adaptive Snapshots Require Visible Reads

cs.DC ·2026-08-13 ·Niv Sulimany, Tomer Cory, Erez Petrank
published similarity 0.58
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

Transactional Data Change for Real-Time Analytics in Lakehouses

cs.DB cs.AIcs.DCcs.PF ·2026-11-09 ·Dongyang Geng, Haoqiong Bian, Zinuo Li, Haoyue Li
top venuecode/data similarity 0.56
Abstract · Accepted by VLDB 2026 and to be published on PVLDB Vol.19 No.13, 14 pages, 16 figures

Real-time data analytics has become a key demand for lakehouses. It requires propagating data changes from the data source to the lakehouse in real time, while ensuring ACID guarantees and minimizing resource consumption and impact on analytical query performance. This is highly challenging for a data system according to the RUM conjecture, especially given the read-optimized immutable file storage layer in lakehouses. Existing lakehouses offer only git-style catalog version control on a single table, and they trade data freshness, query performance, and/or resource efficiency to achieve a barely acceptable data-change throughput. In this paper, we propose a novel data synchronization framework, Retina, that enables real-time, cost-efficient, query-performant, and fully transactional data changes in lakehouses. We implement and open-source Retina. Evaluations show that Retina delivers 10-millisecond-level data freshness and over 3.2 million row/s linear-scalable data-change throughput with low resource consumption and query-performance overhead, significantly outperforming state-of-the-art lakehouse systems and lake-compatible HTAP databases.

0.49

IBLTs Measure Before They Decode: Self-Sizing Set Reconciliation for Database Consistency Verification

cs.DB cs.DC ·2026-08-27 ·Min Wu, Ji Qi, Zhengsheng Ye, Chengdui Luo, Shudong Lu +1 more
theorycode/data similarity 0.55
Abstract · Code and archived artifact: https://github.com/whitewum/self-sizing

Cross-system data replication pipelines cannot confirm end-to-end consistency from the local guarantees of each hop, so the two endpoints must be compared directly on a periodic basis. Once the rows of a fixed snapshot are normalized into fingerprints, the task reduces to finding the symmetric difference of the two sets. An Invertible Bloom Lookup Table (IBLT) reconciles the sets with communication that grows only with the difference cardinality $d$, independent of table size, but its capacity must be fixed while $d$ is still unknown. Across 41,603 production reconciliations over 90 days, nonzero $d$ spans about seven orders of magnitude, and no reliable empirical constant exists. We show that the count array of an IBLT has already measured $d$ before decoding. The measurement is in-band: it is carried by the recovery sketch itself and adds no bytes dedicated to estimation. A mapping-aware theorem extends the construction to Irregular, Rateless, and MET IBLTs. The protocol reads the estimate only after a decoding failure; we prove that the failure-conditioned lower quantile bounds the risk of underestimation, which gives the second-round capacity a configurable success-probability guarantee. The resulting self-sizing protocol attempts recovery with a small first-round sketch and stops on success; on failure it reads $d$, sizes the second round, and completes reconciliation in at most two rounds. Against a controlled oracle, communication is 1.29-1.47 times that of a scheme given $d$ in advance. Production workload characterization, relational-database replay, and a cross-city KV deployment confirm the end-to-end mechanism. In production on an Oracle-MySQL link, all completed runs succeeded within two rounds, over 90% on the 1-RTT fast path with a single 16 KB sketch.

0.38

Causal Resolution of Undefined Answers in Datalog with Negation

cs.DB ·2026-11-09 ·Ratan Bahadur Thapa
similarity 0.55
Abstract

Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality.

0.28

Harbormaster: Evidence-Gated, Replay-Safe Maritime Anomaly Detection on AWS

cs.CR ·2026-09-30 ·Arun Sharma
similarity 0.55
Abstract

Ships broadcast their positions through the Automatic Identification System (AIS), and those reports can be false or missing. An operator who acts on an anomaly alert needs that alert to be attributable, reviewable, and recoverable after a failure. This paper describes Harbormaster, a production-shaped system on AWS that follows three rules. Physics checks run on every report before any learned model runs. The DynamoDB read store is an idempotent projection of PostgreSQL, and a guard on the log sequence number (LSN) of each change protects every write to it. A candidate model must pass a holdout gate and a shadow comparison before a canary gives it traffic, and a burn-rate check guards each canary step. The paper proves that replaying any prefix or suffix of the change log leaves each projected key at the value of its highest applied LSN. It also notes effects this result does not cover, such as repeated cache invalidations and repeated audit rows. In a bounded AWS window, a one-hour soak returned 35,999 HTTP 200 responses to 36,000 requests, with a 95th-percentile (p95) client latency of 142.751 ms. In a separate bounded AWS run of 900 s, the stream path received a burst of 400 records/s, and its consumer lag later drained to zero. Every number in the paper carries a label that says where it was measured, and the paper lists the parts of the design that were never built.

0.29

Ingest-Time Fact Compilation for Cost-Efficient and Reliable Question Answering over Revised Corpora

cs.AI cs.DBcs.IR ·2026-08-29 ·Kyle Wild, Yusuke Takahashi, Asako Uraki
publishedcode/data similarity 0.54
Abstract · 6 pages, 5 tables, 1 figure. Accepted for presentation at the 2026 International Conference on Applied Science and Technology - Engineering …

Most agentic question answering (QA) systems do an important part of their semantic work at the worst possible time: every time someone asks a question. When a corpus contains revisions, drafts, revocations, deletions, and sources with different levels of authority, the model must reconstruct the governed current state on every read - then throw that work away and repeat it on the next query. This is a bit like a database that rebuilds a materialized view every time someone reads from it. We present ingest-time fact compilation, an architecture that performs this work when corpus data is ingested or changed. Raw passages are rephrased into self-contained facts; rules governing revisions, deletions, effective dates, and source trust are resolved once; and the resulting state is stored as typed records carrying source and revision provenance. At query time, an inexpensive model reads the compiled record instead of reconstructing it from noisy candidates. In a controlled synthetic experiment across five seeds, the same low-cost model produced the correct value, source, and revision in only one of 30 trials under query-time reconstruction, but in all 30 trials from the compiled substrate, at 12.89 times lower mean read cost per question. On simpler revision questions both architectures were exact, but the compiled path used 21.6 times fewer tokens. A separate test found that fact rephrasing roughly halved verbose Federal Reserve dialogue while preserving high source entailment, but left concise Wikipedia prose essentially unchanged. These results support a narrow but practical claim: resolving a corpus state once can make subsequent QA cheaper and more reliable for inexpensive models. We release the open source, MIT-licensed implementation and experimental artifacts.

0.40

TRAIL: Towards Effective Log Parsing for Rare Logs through Template-Preserving Augmentation

cs.SE ·2026-09-21 ·Sepideh Hodaeian, Zhenhao Li, An Ran Chen
benchmark similarity 0.54
Abstract

Log parsing is essential for system log analysis because it supports tasks such as debugging, monitoring, and anomaly detection by transforming unstructured log messages into structured log templates. However, real-world log datasets exhibit highly imbalanced, long-tailed distributions, where a small number of frequent templates dominate while many rare templates appear only a few times. This imbalance causes evaluation results to be overly optimistic by allowing frequent templates to dominate benchmark metrics, while poor performance on rare yet operationally important events remains largely hidden. In this paper, we investigate the prevalence and impact of rare log groups, defined as log groups with fewer than five instances. Our empirical study on the widely used Loghub-2.0 benchmark shows that rare log groups account for nearly 20% of all templates but less than 0.01% of log messages. Because they contain only a handful of instances, all evaluated parsers experience substantial performance degradation on these groups. To address this challenge, we propose TAILOR, a log parsing framework that improves template inference for rare log groups through template-preserving augmentation. TAILOR enriches rare log groups with template- consistent log messages before template inference. The additional structural evidence helps distinguish static tokens from dynamic variables. Our experimental results show that TAILOR improves parsing accuracy on rare log groups by 19% over the strongest baseline while maintaining competitive performance on complete datasets. We further show that the proposed augmentation strategy generalizes across different LLM backbones and consistently improves existing LLM-based parsers without modifying their core architectures.

0.13