▷LESSON VIDEOOverview: CoordinationVideo coming soon. Start with the reading below.COMING SOON
- 03.01Overview: Coordination▷LESSON VIDEOOverview: CoordinationVideo coming soon. Start with the reading below.COMING SOON
- 03.02System models▷LESSON VIDEOSystem modelsVideo coming soon. Start with the reading below.COMING SOON
- 03.03Failure detection▷LESSON VIDEOFailure detectionVideo coming soon. Start with the reading below.COMING SOON
- 03.04Time▷LESSON VIDEOTimeVideo coming soon. Start with the reading below.COMING SOON
- 03.05Leader election▷LESSON VIDEOLeader electionVideo coming soon. Start with the reading below.COMING SOON
- 03.06Replication▷LESSON VIDEOReplicationVideo coming soon. Start with the reading below.COMING SOON
- 03.07Coordination avoidance▷LESSON VIDEOCoordination avoidanceVideo coming soon. Start with the reading below.COMING SOON
- 03.08Transactions▷LESSON VIDEOTransactionsVideo coming soon. Start with the reading below.COMING SOON
- 03.09Asynchronous transactions▷LESSON VIDEOAsynchronous transactionsVideo coming soon. Start with the reading below.COMING SOON
References
System models
- “The Byzantine Generals Problem,” https://lamport.azurewebsites.net/pubs/byz.pdf
- “Unreliable Failure Detectors for Reliable Distributed Systems,” https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf
- “Introduction to Reliable and Secure Distributed Programming,” https://www.distributedprogramming.net/
- “All models are wrong,” https://en.wikipedia.org/wiki/All_models_are_wrong
Time
- “Atomic clock,” https://en.wikipedia.org/wiki/Atomic_clock
- “RFC 5905: Network Time Protocol Version 4: Protocol and Algorithms Specification,” https://datatracker.ietf.org/doc/html/rfc5905
- “Time, Clocks, and the Ordering of Events in a Distributed System,” http://lamport.azurewebsites.net/pubs/time-clocks.pdf
- “Timestamps in Message-Passing Systems That Preserve the Partial Ordering,” https://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf
- In actual implementations, a dictionary is used rather than an array.
- In a total order, every pair of elements is comparable. Instead, in partial order, some pairs are not comparable
- “Why Logical Clocks are Easy,” https://queue.acm.org/detail.cfm?id=2917756 6
Leader election
- “In Search of an Understandable Consensus Algorithm,” https://raft.github.io/raft.pdf
- The same happens if the leader receives a heartbeat with a greater term.
- We will encounter one such case when discussing replication in Replication (lesson 03.06).
- We will define what linearizability means exactly later in Strong consistency in Replication.
- “Compare-and-swap,” https://en.wikipedia.org/wiki/Compare-and-swap
- “Building Distributed Locks with the DynamoDB Lock Client,” https://aws.amazon.com/blogs/database/building-distributed-locks-with-the-dynamodb-lock-client/
Replication
- “In Search of an Understandable Consensus Algorithm,” https://raft.github.io/raft.pdf
- “Paxos Made Simple,” https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
- “Finite-state machine,” https://en.wikipedia.org/wiki/Finite-state_machine
- In practice, there are ways to reduce the number of messages required for this step.
- “Consensus,” https://en.wikipedia.org/wiki/Consensus_(computer_science)
- “Paxos made Abstract,” https://maheshba.bitbucket.io/blog/2021/11/15/Paxos.html
- We will define what linearizability means in the next section. 8nor want to, since it’s very challenging to get right; see “Paxos Made Live - An Engineering Perspective,” https://static.googleusercontent.com/media/research.google.com/en//archive/paxos_made_live.pdf
- “etcd: A distributed, reliable key-value store for the most critical data of a distributed system,” https://etcd.io/
- “Apache ZooKeeper: An open-source server which enables highly reliable distributed coordination,” https://zookeeper.apache.org/
- “Consistency Models,” https://jepsen.io/consistency
- “Linearizability,” https://jepsen.io/consistency/models/linearizable
- For example, this is the guarantee you would expect from a coordination service that manages leases.
- “Sequential Consistency,” https://jepsen.io/consistency/models/sequential
- “Perspectives on the CAP Theorem,” https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
- “A Critique of the CAP Theorem,” https://www.cl.cam.ac.uk/research/dtg/www/files/publications/public/mk428/cap-critique.pdf
- “CAP Theorem: You don’t need CP, you don’t want AP, and you can’t have CA,” https://www.youtube.com/watch?v=hUd_9FENShA
- “Consistency Tradeoffs in Modern Distributed Database System Design,” https://en.wikipedia.org/wiki/PACELC_theorem
- “Consistency levels in Azure Cosmos DB,” https://docs.microsoft.com/en-us/azure/cosmos-db/consistency-levels
- “Apache Cassandra: How is the consistency level configured?,” https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/dml/dmlConfigConsistency.html
- “Chain Replication for Supporting High Throughput and Availability,” https://www.cs.cornell.edu/home/rvr/papers/OSDI04.pdf
- This is slightly different from the original chain replication paper since it’s based on CRAQ, an extension of the original protocol; see “Object Storage on CRAQ,” https://www.usenix.org/legacy/event/usenix09/tech/full_papers/terrace/terrace.pdf .
- required for state machine replication
Coordination avoidance
- Total order broadcast is equivalent to consensus, see “Unreliable Failure Detectors for Reliable Distributed Systems,” https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf
- “Perspectives on the CAP Theorem,” https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
- Consensus is harder to solve than implementing a linearizable read/write register, which is what the CAP theorem uses to define consistency.
- “Gossip protocol,” https://en.wikipedia.org/wiki/Gossip_protocol
- “Strong Eventual Consistency and Conflict-free Replicated Data Types,” https://www.microsoft.com/en-us/research/video/strong-eventual-consistency-and-conflict-free-replicated-data-types/
- “Conflict-free Replicated Data Types,” https://hal.inria.fr/inria-00609399v1/document
- In practice, version vectors are used to compare the state of different replicas that only keep track of events that change the state of replicas, see “Detection of Mutual Inconsistency in Distributed Systems,” https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2017/Papers/parker83detection.pdf .
- “Dynamo: Amazon’s Highly Available Key-value Store,” https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
- “Cassandra: Open Source NoSQL Database,” https://cassandra.apache.org/
- “Riak KV: A distributed NoSQL key-value database,” https://riak.com/products/riak-kv/
- “Merkle tree,” https://en.wikipedia.org/wiki/Merkle_tree
- “Keeping CALM: When Distributed Consistency is Easy,” https://arxiv.org/pdf/1901.01930.pdf
- Consistency can have different meanings depending on the context; make sure you know precisely what it refers to when you encounter it.
- “Building on Quicksand,” https://dsf.berkeley.edu/cs286/papers/quicksand-cidr2009.pdf
- “Causal Consistency,” https://jepsen.io/consistency/models/causal
- “Consistency, Availability, and Convergence,” https://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2036.pdf
- “Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS,” https://www.cs.princeton.edu/~mfreed/docs/cops-sosp11.pdf
- COPS can track causal relationships between partitions (and therefore nodes), unlike simpler approaches using version vectors, which limit causality tracking to the set of keys that a single node can store (see “Session Guarantees for Weakly Consistent Replicated Data,” https://www.cs.utexas.edu/users/dahlin/Classes/GradOS/papers/SessionGuaranteesPDIS.pdf ).
- “Azure Cosmos DB: Pushing the frontier of globally distributed databases,” https://azure.microsoft.com/en-gb/blog/azure-cosmos-db-pushing-the-frontier-of-globally-distributed-databases/
Transactions
- “Transaction processing,” https://en.wikipedia.org/wiki/Transaction_processing
- “When is”ACID” ACID? Rarely.” http://www.bailis.org/blog/when-is-acid-acid-rarely/
- see Replication (lesson 03.06)
- “PostgreSQL Transaction Isolation,” https://www.postgresql.org/docs/12/transaction-iso.html
- “Consistency Models,” https://jepsen.io/consistency
- “Jepsen Analyses,” https://jepsen.io/analyses
- “Two-phase locking,” https://en.wikipedia.org/wiki/Two-phase_locking
- “On Optimistic Methods for Concurrency Control,” https://www.eecs.harvard.edu/~htk/publication/1981-tods-kung-robinson.pdf
- “Multi-version concurrency control,” https://en.wikipedia.org/wiki/Multiversion_concurrency_control
- “CMU 15-445/645: Database Systems,” https://15445.courses.cs.cmu.edu/fall2019/
- We have already seen an example of this when discussing leases in Practical considerations in Leader election.
- The details of how this recovery mechanism works are outside the scope of this module, but you can learn more about it from any database textbook.
- “Two-phase commit protocol,” https://en.wikipedia.org/wiki/Two-phase_commit_protocol
- “It’s Time to Move on from Two Phase Commit,” http://dbmsmusings.blogspot.com/2019/01/its-time-to-move-on-from-two-phase.html
- “Uniform consensus is harder than consensus,” https://infoscience.epfl.ch/record/88273/files/CBS04.pdf?version=1
- “Spanner: Google’s Globally-Distributed Database,” https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf
- The clock uncertainty is generally less than 10ms.
- “CockroachDB,” https://www.cockroachlabs.com/
- “Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases,” https://cse.buffalo.edu/tech-reports/2014-04.pdf
Asynchronous transactions
- “Online Event Processing: Achieving consistency where distributed transactions have failed,” https://queue.acm.org/detail.cfm?id=3321612
- “Elasticsearch: A distributed, RESTful search and analytics engine,” https://www.elastic.co/elasticsearch/
- “Distributed Transaction Processing: The XA Specification,” https://pubs.opengroup.org/onlinepubs/009680699/toc.pdf
- “Pattern: Transactional outbox,” https://microservices.io/patterns/data/transactional-outbox.html
- For example, Debezium is an open source relay service that does this, see https://debezium.io/ .
- “Apache Kafka: An open-source distributed event streaming platform,” https://kafka.apache.org
- “Azure Event Hubs: A fully managed, real-time data ingestion service,” https://azure.microsoft.com/en-gb/services/event-hubs/
- “Sagas,” https://www.cs.cornell.edu/andru/cs711/2002fa/reading/sagas.pdf
- ”Building on Quicksand,” https://dsf.berkeley.edu/cs286/papers/quicksand-cidr2009.pdf
- “Clarifying the Saga pattern,” http://web.archive.org/web/20161205130022/http://kellabyte.com:80/2012/05/30/clarifying-the-saga-pattern
- “AWS Step Functions,” https://aws.amazon.com/step-functions/
- “Azure Durable Functions documentation ,” https://docs.microsoft.com/en-us/azure/azure-functions/durable/
- “Semantic ACID properties in multidatabases using remote procedure calls and update propagations,” https://dl.acm.org/doi/10.5555/284472.284478