Metraipolis › archive › dc_28fd187faeb6

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

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.26537
License (as archived): CC0-1.0
Archived: 2026-10-17T15:28:28.595Z
SHA-256 of the archived text: 31167ccd67b18a90cac473b2aebb802d4dbf008666a2c5a60a5374cbf06cd835
Stable URL of this page: https://metraipolis.com/documento/dc_28fd187faeb6

How to cite

IBLTs Measure Before They Decode: Self-Sizing Set Reconciliation for Database Consistency Verification — arXiv:2608.26537 — arXiv (en), https://arxiv.org/abs/2608.26537 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_28fd187faeb6 (Metraipolis archive dc_28fd187faeb6, sha256 31167ccd67b18a90cac473b2aebb802d4dbf008666a2c5a60a5374cbf06cd835)

BibTeX

@misc{dc28fd187faeb6,
  title = {IBLTs Measure Before They Decode: Self-Sizing Set Reconciliation for Database Consistency Verification — arXiv:2608.26537},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.26537},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_28fd187faeb6; sha256 31167ccd67b18a90cac473b2aebb802d4dbf008666a2c5a60a5374cbf06cd835},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26537. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DC).
Categorie arXiv: Databases (cs.DB) ; Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2608.26537 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T15:17:44.904Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).