← Back
Home › Systems › Data processing and pipelines

data-versioning

versioned datasets and data lakes

lakeFS, DVC

SystemTechniques · 3Primitives · 13 data-versioning Three-way mergedistributed · medium: Merge two descendants against their common ancestor: take whichever side changed, report a conflict only where both changed the same spot differently.›Table snapshot manifestsstorage · medium: Table state as an immutable tree of snapshot -> manifest lists -> data files, committed by pointer swapMyers diffsearch-sort · medium: Greedy O(ND) shortest edit script between two sequences, the default of git and GNU diff; fast when the inputs are similar.›Object storagecloud · low: S3-compatible blob storage at cents per GB-month with 11 nines durability; pick by egress price, request price and latency, not by storage price alone.›Conditional writesdistributed · low: Put-if-absent / if-match compare-and-swap on objects or keys as a commit primitiveContent defined chunkingcompression · low: Rolling-hash chunk boundaries (Rabin, FastCDC) for deduplication that survives insertionsMerkle dagdata-structures · low: Content-addressed DAG of hashed nodes (git trees/commits) for dedupe and verifiable historyCryptographic hashes (SHA-2, BLAKE3)security · low: Collision-resistant fingerprints of data; SHA-256 for interoperability, BLAKE3 for speed, HMAC/HKDF for keyed uses.›Copy on write snapshotsstorage · low: Point-in-time snapshots by sharing pages/extents and copying only on writeOptimistic concurrency controlstorage · low: Run transactions without locks, record what they read, and validate at commit that nothing changed; fastest when conflicts are rare.›Sstablestorage · low: Sorted string table: data blocks with restart points, index, filter and footerLowest common ancestorgraphs · low: LCA/merge-base computation in trees and DAGsColumnar file formatstorage · low: Row groups, column chunks, pages, encodings and footer stats (Parquet/ORC style) (listed in Moved to the wiki)Zone mapsstorage · low: Per-block min/max (and sparse primary) indexes to skip data during scansRolling hashdata-structures · low: Rabin-Karp polynomial rolling hashes and winnowing for substring fingerprints and document matchingEdit distancesearch-sort · low: Levenshtein/Damerau distance by DP, bit-parallel Myers variant

Similar systems

Share the most building blocks with this one.

lakehouse 22 %backup-dr 19 %cold-archive 17 %