...

...

This list is a compilation of readings which are valuable to a general understanding of the operation of Cockroach. This list is extensive (but not exhaustive), don't feel you need to read everything here, it's provided as a way to drill down into topics you find interesting, if you so choose. The entries in each section are roughly organized in recommended order of consumption, but this is not a strict ordering in any sense.

...

Introduction

• Architecture docs: https://www.cockroachlabs.com/docs/stable/architecture/overview.html

• Life of a Query: https://github.com/cockroachdb/cockroach/blob/master/docs/tech-notes/life_of_a_query.md

• The hows and whys of a distributed SQL database by Alex: https://www.youtube.com/watch?v=6OFeuNy39Qg

• Designing Data-Intensive Applications: https://dataintensive.net

• CMU Intro to Database Systems: https://www.youtube.com/playlist?list=PLSE8ODhjZXjbohkNBWQs_otTrBTrjyohi

General

• https://github.com/cockroachlabs/slack-convos

  • There's been various productive conversations that have taken place in the #transactions channel in slack.

• What’s Really New With NewSQL: https://db.cs.cmu.edu/papers/2016/pavlo-newsql-sigmodrec2016.pdf

• A 30k overview of distributed databases: ACID, CAP, NewSQL.pdf

• Aphyr's distributed systems course: https://github.com/aphyr/distsys-class

• CMU Advanced Database Systems: https://www.youtube.com/playlist?list=PLSE8ODhjZXjasmrEd2_Yi1deeE360zv5O

• CMU Quarantine 2020 Database Talks: https://www.youtube.com/playlist?list=PLSE8ODhjZXjagqlf1NxuBQwaMkrHXi-iz

• CMU Vaccination 2021 Database Talks: https://www.youtube.com/playlist?list=PLSE8ODhjZXjbeqnfuvp30VrI7VXiFuOXS

• Database Internals: https://www.oreilly.com/library/view/database-internals/9781492040330/

Storage

• Kleppmann - Designing Data Intensive Applications: Chapter 3

• A Brief History of Log Structured Merge Trees: https://ristret.com/s/gnd4yr/brief_history_log_structured_merge_trees

Admission Control

• Value-cognizant Admission Control for RTDB Systems

• BBR: Congestion-Based Congestion Control

• Enlightening the I/O Path: A Holistic Approach for Application Performance

• Real-Time Database and Information Systems

• Admission control and scheduling of remote processes in loosely-coupled distributed systems

• Regulating I/O Performance of Shared Storage with a Control Theoretic Approach

• The creation of the io.latency block I/O controller

• Constructing and Analyzing the LSM Compaction Design Space

• Online Bigtable merge compaction

• IOCost: Block IO Control for Containers in Datacenters

• Overload Control for Scaling WeChat Microservices

• Controlling Queue Delay

• Fail at Scale

Transactions

• A History of Transaction Histories: https://ristret.com/s/f643zk/history_transaction_histories

• ANSI Critique: https://arxiv.org/pdf/cs/0701157.pdf

• Yabandeh: https://drive.google.com/file/d/0B9GCVTp_FHJIMjJ2U2t6aGpHLTFUVHFnMTRUbnBwc2pLa1RN/edit

  • An extremely well-written explanation of optimistic serializable transactions. I think this is one of the best resources for gaining intuition about transactions.

• How CockroachDB Does Distributed, Atomic Transactions: https://www.cockroachlabs.com/blog/how-cockroachdb-distributes-atomic-transactions/

• Serializable, Lockless, Distributed: Isolation in CockroachDB: https://www.cockroachlabs.com/blog/serializable-lockless-distributed-isolation-cockroachdb/

• Understanding Weak Isolation: http://www.bailis.org/blog/understanding-weak-isolation-is-a-serious-problem/

• Read-Only Transaction Anomaly: https://www.cs.umb.edu/~poneil/ROAnom.pdf

  • Explanation of a surprising and unintuitive anomaly that can occur in Snapshot Isolation

• What Does Write Skew Look Like: http://justinjaffray.com/what-does-write-skew-look-like/

  • A (hopefully) simplified explanation of Fekete 2005.

• Fekete 2005: https://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2009/Papers/p492-fekete.pdf

• Empirical Evaluation: http://www.cs.cmu.edu/~pavlo/papers/p781-wu.pdf

  • Mostly relevant to in-memory databases (which CockroachDB is not), but a good overview of the main components of an MVCC system.

• Adya Thesis: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.1760&rep=rep1&type=pdf

  • Very dense, formal treatment of isolation levels. Not really recommended unless you're trying to win an argument.

• Hermitage: https://github.com/ept/hermitage

  • Martin Kleppmann's testing of different databases' isolation levels (mapping SQL standard levels like REPEATABLE READ to the richer categorization of Adya)

Linearizability

• Strong consistency models: https://aphyr.com/posts/313-strong-consistency-models

• Linearizability vs. Serializability: http://www.bailis.org/blog/linearizability-versus-serializability/

  • While I think this is a good post, keep in mind when reading it that linearizability and serializability are mostly orthogonal concepts and I think conflating them in this way is confusing.

• A Mild Generalization of Linearizability: http://justinjaffray.com/a-mild-generalization-of-linearizability/

• Living Without Atomic Clocks: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

  • Written by Spencer comparing Cockroach's use of synchronized clocks with Spanner's.

• Herlihy+Wing: https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

  • The formal genesis of linearizability. I think reading this is confusing because it's actually slightly different and much more formal from how people talk about linearizability in the real world, but I still think it's valuable. It goes off the rails in section 4, though.

Consensus

• Why Consensus: http://justinjaffray.com/why-consensus/

  • I feel quite strongly that people should start here. I don't think the problem that consensus solves is adequately motivated in most discussions, which is what I tried to rectify with this.

• Paxos Made Live: http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf

  • Describes the process of building a production system on Paxos. Illuminated for me the purpose of consensus in a lot of ways.

• Paxos Made Simple: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

• Paxos Made Moderately Complex: http://paxos.systems

• In Search of an Understandable Consensus Algorithm: https://raft.github.io/raft.pdf

  • Animation: The Secret Lives of Data: http://thesecretlivesofdata.com/raft/

• Scaling Raft: https://www.cockroachlabs.com/blog/scaling-raft/

• Flexible Paxos: Quorum Intersection Revisited: https://arxiv.org/pdf/1608.06696.pdf

SQL Execution

• Volcano: https://paperhub.s3.amazonaws.com/dace52a42c07f7f8348b08dc2b186061.pdf

  • The introduction of the general execution model that the planNode and DistSQL engines in Cockroach use. Start here if you know nothing about how SQL statements are executed.

• MonetDB (MIL Primitives for querying a fragmented world) (1999) (Boncz, Kersten): https://ir.cwi.nl/pub/11183/11183B.pdf

  • This paper discusses MonetDB, a database system that uses column-at-a-time processing. Entire columns are processed at once, with no batching. 

• MonetDB/X100: Hyper-Pipelining Query Execution (2005) (Boncz, Zukowski, Nes) : http://cidrdb.org/cidr2005/papers/P19.pdf

  • This paper is the primary source of the idea to use batched, templated, column-at-a-time execution to avoid the interpretation and type-lookup overhead inherent in the Volcano model. CockroachDB's nascent vectorized execution engine follows the ideas in this paper closely.

  • This paper is really important! Read it if you're interested in CockroachDB's exec package and vectorized execution.

  • It's also written by Marcin Zukowski, cofounder of Snowflake

• Everything you always wanted to know about compiled and vectorized queries but were afraid to ask (2018) (Kersten, Leis, Kemper, Neumann, Pavlo, Boncz): http://www.vldb.org/pvldb/vol11/p2209-kersten.pdf

  • Really good intro to what's the deal with vectorized and how does it compare with JIT (compiled) systems like HyPER or MemSQL. Andy Pavlo co-author.

• Balancing vectorized query execution with bandwidth-optimized storage (2009) (Zukowski): https://dare.uva.nl/search?identifier=5ccbb60a-38b8-4eeb-858a-e7735dd37487

  • This is the paper about the VectorWise database system that came out of MonetDB/X100 from Zukowski, his PhD thesis.

  • Especially chapter s4, 5, 6 are really relevant to CockroachDB.

• The Design and Implementation of Modern Column-Oriented Database Systems (2012) (Abadi, Boncz, ...) : http://db.csail.mit.edu/pubs/abadi-column-stores.pdf

  • Massive survey paper. Good but a lot of info in there.

• Rethinking SIMD Vectorization for In-Memory Databases (2015) (Polychroniou, Raghavan, Ross) http://www.cs.columbia.edu/~orestis/sigmod15.pdf

  • Interesting stuff about how to actually utilize SIMD for vectorized execution.

• DSM vs. NSM: CPU performance tradeoffs in block-oriented query processing (2008) (Zukowski, Nes, Boncz) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.1243

SQL Optimization/Query Planning

• Basics of SQL indexing, independent of database: https://use-the-index-luke.com/

• Index Selection in CockroachDB: https://www.cockroachlabs.com/blog/index-selection-cockroachdb-2/

  • Not especially specific to Cockroach - great as an introduction to index selection

• SQL Query Planning: https://github.com/cockroachdb/cockroach/blob/master/docs/RFCS/20171213_sql_query_planning.md

• Andy K on Optimizer: The Story So Far (April 2018): https://www.youtube.com/watch?v=wAfAVv9SFIc

• Andy Pavlo optimizer lectures

  • Part 1: https://www.youtube.com/watch?v=qbfPpWnAP-4

  • Part 2: https://www.youtube.com/watch?v=m7GxSvdV4NU

• The Cascades Framework for Query Optimization

...

• • This is what our optimizer is based on

...

• • .

• Fundamental Techniques for Order Optimization by Simmen et. al

  • Explains how to manipulate orders, not aware of a publicly available PDF

• pkg/sql/opt/doc.go: https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/doc.go

• Optimization of Analytic Window Functions: http://vldb.org/pvldb/vol5/p1244_yucao_vldb2012.pdf

Systems

This section is randomly important because people at Cockroach talks about things in terms of the Google system which introduced them

• BigTable: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf

• Spanner: https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf

• F1: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41344.pdf

• Colossus/GFS: http://pages.cs.wisc.edu/%7Eremzi/Classes/736/Spring2000/Papers/gfs-sosp2003.pdf

• Online, Asynchronous Schema Change in F1: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41376.pdf

  • Lovely discussion of how the schema changes in F1/Spanner (and Cockroach) work

• PostgreSQL back-end flowchart: https://www.postgresql.org/developer/backend/

• The internals of PostgreSQL: http://www.interdb.jp/pg/index.html

Other

• The Promise, and Limitations, of Gossip Protocols: http://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/2007PromiseAndLimitations.pdf