References

Books

  • Sippu, S., & Soisalon-Soininen, E. (2015). Transaction Processing: Management of the Logical Database and its Underlying Physical Structure. Springer. Chapter 6 ("Logical Database Updates") gives the cleanest treatment of the no-op-update / no-op-delete rule that governs txid allocation here.
  • Bernstein, P. A., Hadzilacos, V., & Goodman, N. (1987). Concurrency Control and Recovery in Database Systems. Addison-Wesley. Chapter 5 on multiversion concurrency control is the source of the "tombstone with deleted-at txid" representation we use.
  • Hellerstein, J. M., Stonebraker, M., & Hamilton, J. (2007). Architecture of a Database System. Foundations and Trends in Databases, 1(2). Provides the layering vocabulary (storage manager, access methods, query processor) we slice through here.

Papers

  • Reed, D. P. (1978). Naming and Synchronization in a Decentralized Computer System. MIT/LCS/TR-205. The original MVCC paper.
  • Bernstein, P. A., & Goodman, N. (1981). Concurrency Control in Distributed Database Systems. ACM Computing Surveys 13(2). Lays out the timestamp-ordering protocols that motivate our monotonic txid.

Source documentation

Cross-language byte-identity practice

  • Google's protobuf canonical encoding spec — https://protobuf.dev/programming-guides/encoding/. The discipline of sorting map entries before serialisation comes from there.
  • CBOR deterministic encoding (RFC 8949 §4.2). Same idea applied to a different format. Useful background for why we sort the secondary index lexicographically rather than by insertion order.

Earlier labs in this workspace