References — db-21

The lab is intentionally self-contained, but the ideas are not original.

Range Tombstones

  • RocksDB wiki, "DeleteRange: A New Native RocksDB Operation" https://rocksdb.org/blog/2018/11/21/delete-range.html
  • CockroachDB blog: "DeleteRange and the importance of tombstones in a distributed SQL database."
  • "Bringing Modern Hierarchical Memory Systems Into Main-Memory Databases" (Bortnikov et al.) — discusses interval-deletion structures.

Compaction Policies

  • "The Log-Structured Merge-Tree (LSM-Tree)", O'Neil et al., 1996. The canonical paper; introduces the size-tiered idea.
  • RocksDB wiki, "Universal Compaction Style" https://github.com/facebook/rocksdb/wiki/Universal-Compaction
  • RocksDB wiki, "Leveled Compaction" https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
  • ScyllaDB docs, "Size-tiered compaction strategy (STCS)" — the Cassandra heritage of size-tiered.

SplitMix64

  • Steele, Lea, Flood, "Fast Splittable Pseudorandom Number Generators", OOPSLA 2014. The mixing constants 0x9E37..., 0xBF58..., 0x94D0... come straight from this paper.

FNV-1a

  • Glenn Fowler, Landon Curt Noll, Phong Vo, "FNV non-cryptographic hash." The 64-bit offset 0xCBF29CE484222325 and prime 0x100000001B3 are the standard FNV-1a parameters.

Cross-Language Byte Equivalence as a Methodology

  • TigerBeetle's "Tigerstyle" notes on deterministic simulation.
  • FoundationDB's flow-based testing — the closest commercial analogue to "spec-by-hash-of-canonical-dump".