Data versioning

Content addressing and Merkle structures#

A content-addressed store keys objects by $h(\text{contents})$ for a collision-resistant hash $h$. Properties that follow directly: deduplication is automatic, integrity is verifiable without a trusted index, and equality is decidable in $O(1)$ after hashing.

For large datasets, hashing the whole object on every check is $O(n)$ per verification. Merkle trees (Merkle, 1987) reduce this. Chunk the data, hash each chunk as a leaf, and hash concatenated pairs upward to a root:

$$ h_{\text{node}} = h\big(h_{\text{left}} \,|\, h_{\text{right}}\big) $$

Verifying one chunk against a known root costs $O(\log n)$ hashes. Diffing two versions costs $O(k \log n)$ for $k$ changed chunks, rather than $O(n)$. This is the structure underneath Git, IPFS, ZFS and Delta Lake's file-level manifests.

Chunk boundaries matter. Fixed-size chunking suffers the boundary shift problem: an insertion of one byte at offset 0 changes every subsequent chunk. Content-defined chunking (Rabin fingerprinting) places boundaries where a rolling hash meets a condition, so an insertion affects only the local chunk. Expected chunk size is tuned by the number of low bits required to be zero.

Collision probability#

With a $b$-bit digest and $k$ stored objects, the birthday bound gives:

$$ P(\text{collision}) \;\approx\; 1 - e^{-k^2 / 2^{b+1}} \;\approx\; \frac{k^2}{2^{b+1}} $$

For the truncated 48-bit fingerprint in the developer section and $k = 10^4$ dataset versions, this is around $1.8 \times 10^{-7}$. Acceptable for a human-facing label. For a content-addressed store where a collision means silent data loss, use the full digest.

Note that SHA-1 is no longer collision-resistant (Stevens et al., 2017, SHAttered), which is why Git has been migrating to SHA-256. Use SHA-256 for anything new.

Table formats and snapshot isolation#

Delta Lake (Armbrust et al., 2020, VLDB) implements ACID transactions over object storage by writing an ordered log of JSON actions plus periodic Parquet checkpoints. A table version is a log offset. Readers resolve a snapshot by replaying the log to a version, giving serialisable snapshot isolation without a coordinating server, using atomic put-if-absent on the log file as the concurrency primitive.

Iceberg takes a different route: a metadata tree of manifest lists and manifest files, with an atomic pointer swap on the current metadata location. It handles very high partition counts better, since a scan plan reads manifests rather than listing directories.

Both give time travel — reading a table as of a version or timestamp — which is precisely the reproducibility primitive that ad-hoc CSV workflows lack.

Point-in-time correctness#

Reproducibility of the inputs is necessary but not sufficient. For any model consuming time-varying features, the correct training row for an event at time $t$ uses feature values as known at $t$, not as known now.

Formally, given an event log $E$ and a feature computation $\phi$, the training feature must be $\phi\big({e \in E : e.\text{ts} \le t}\big)$. Computing $\phi$ over the whole table at training time is a temporal leak, and it is invisible to every fingerprint scheme, because the bytes are correct and the join is wrong.

This requires bitemporal modelling: distinguish valid time (when the fact was true in the world) from transaction time (when the system learned it). Snodgrass's work on temporal databases is the reference treatment; Kleppmann's Designing Data-Intensive Applications, chapter 11, gives the practical version. See feature stores for the machinery.

What a run record should contain#

Minimum viable provenance, per training run:

1. Dataset fingerprint, plus fingerprints of each upstream source.
2. Manifest statistics: row and column counts, null rates per column, label distribution, and per-column min/max/mean for numerics.
3. Code commit SHA, and the resolved dependency set — a lockfile hash, not a requirements range.
4. All random seeds, including any framework-level global seed.
5. Hardware and library versions where numerics matter, since floating-point reduction order varies with thread count and device.
6. The transformation lineage: which function produced this table from which inputs.

Items 1 to 3 are cheap and almost always omitted. Item 6 is what W3C PROV formalises, and what lineage tools such as OpenLineage and Marquez collect automatically.

Reproducibility is a spectrum#

Worth naming precisely, because teams claim the strongest form and deliver the weakest:

• Repeatable — same team, same setup, same result.
• Reproducible — different team, same artefacts, same result.
• Replicable — different team, independently collected data, same conclusion.

Data versioning is necessary for the second and irrelevant to the third. Confusing them produces a great deal of misplaced confidence.

Reading#

• Armbrust et al., Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores, VLDB 2020.
• Merkle, A Digital Signature Based on a Conventional Encryption Function, CRYPTO 1987.
• Kleppmann, Designing Data-Intensive Applications, O'Reilly 2017 — chapters 3 and 11.
• Stevens et al., The First Collision for Full SHA-1, CRYPTO 2017.
• Sculley et al., Hidden Technical Debt in Machine Learning Systems, NeurIPS 2015 — on data dependencies as the costliest debt.

What to learn next#

• Feature stores — versioning the features, and getting the time joins right.
• Experiment tracking — the other half of the run record.
• MLflow — a tool that stores both together.