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.

Original Author: The content of this macro can only be viewed by users who have logged in.

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

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

Database Background