← Back
Home › Systems › CI/CD and developer tooling

monorepo-vcs

monorepo-scale version control

Piper, Sapling

SystemTechniques · 6Primitives · 31 monorepo-vcs Multi-Paxosdistributed · medium: Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.›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.›Transitive closure indexgraphs · medium: Segment/interval labelling of DAGs (commit graphs) for fast reachability queriesMyers 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.›Incremental computationsystems · medium: Dependency graph of derived values recomputed only when inputs change (reactive cells, spreadsheets)State-machine snapshotsdistributed · medium: Periodically save the state a log has produced at index i so the log prefix can be deleted; recovery and catch-up become load snapshot plus replay suffix.›Lowest common ancestorgraphs · low: LCA/merge-base computation in trees and DAGsDictionary compressioncompression · low: Prime the compressor with shared, pre-trained content so small messages can reference it; often 2-5x better ratio on sub-KB records.›Zstandard (zstd)compression · low: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.›Bloom filterdata-structures · low: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.›Merkle treedata-structures · low: Hash tree for verifying and diffing large datasets with logarithmic proofsConsistent hashingdistributed · low: Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.›File system watchinghardware-os · low: Treat OS change notices as hints, debounce them, and rescan and diff a snapshot whenever notices overflow or may be lost.›Fuse userspace filesystemhardware-os · low: FUSE protocol: kernel forwards VFS requests to a userspace daemon; caching and spliceContent-addressed storagestorage · low: Store each blob under the hash of its bytes: immutable, deduplicated by construction, self-verifying on every read, and composable into Merkle trees.›LRU and CLOCKsystems · low: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.›Leasesdistributed · low: A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.›Write-ahead logstorage · low: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.›Interval treedata-structures · low: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Topological sortgraphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Rolling hashdata-structures · low: Rabin-Karp polynomial rolling hashes and winnowing for substring fingerprints and document matching+ 15 more primitives

Similar systems

Share the most building blocks with this one.

version-control 32 %remote-build-execution 25 %code-hosting 17 %image-snapshotter 17 %build-system 16 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

PiperAlphabet