English
A distributed system is a collection of independent machines that coordinate to appear as a coherent service. The machines fail independently, communicate over an unreliable network, and have no shared memory or global clock. Every assumption that makes single-machine programming tractable — that memory is uniformly fast, that operations on shared state are atomic, that when something fails, it fails completely — evaporates. What remains is harder and stranger than most programmers expect: a setting where a machine cannot tell whether a peer has crashed or is merely slow, where two correct processes can observe the same sequence of events in different orders, and where some coordination problems are mathematically impossible to solve correctly under all circumstances.
The reward for this difficulty is that distributed systems can do things no single machine can: they can scale beyond the limits of any one piece of hardware, they can remain available when individual components fail, and they can serve users from geographically distributed locations with low latency. But these capabilities are not free — they require trading away properties that single-machine systems provide automatically. The central intellectual activity of distributed systems is understanding those tradeoffs precisely: what must be given up, what can be retained, and what the fundamental limits are.
The subject is organized around three layers. The system model establishes the formal setting: what assumptions can be made about message delivery, machine behavior, and failure modes? Results that hold in synchronous models (where messages have bounded delivery time) may fail in asynchronous models; impossibility results for asynchronous systems may not apply to partially synchronous ones. The foundational problems — consensus, replication, distributed transactions, leader election, global snapshots — are the canonical problems whose solutions form the intellectual core. The systems layer is where these solutions are composed into real infrastructure: distributed databases, coordination services, stream processors, distributed file systems.
Prerequisites: Operating systems (§4.2) — processes, concurrency primitives, and the single-machine resources that distributed systems extend. Computer networks (§4.3) — the unreliable communication layer on which distributed systems are built. Databases (§4.4) — transactions, consistency models, and durability, all of which generalize to the distributed setting.
From Logical Clocks to Globally Distributed Transactions
The theoretical foundations of distributed systems arrived before the practical systems that would need them.
Leslie Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System” established the conceptual vocabulary the field would use for decades. Lamport’s key insight was that in a distributed system, physical clocks cannot be trusted to establish the ordering of events — clocks drift, and synchronizing them perfectly across machines is impossible. What can be established is a logical ordering based on causality: if event A caused event B (by sending a message that B received), then A happened before B in the only sense that matters for reasoning about distributed systems. Lamport’s logical clocks assigned integers to events such that causally related events received increasing numbers, enabling reasoning about happens-before relationships without physical time. Vector clocks, developed by Fidge and Mattern in 1988, extended this to capture concurrency: events that have no causal relationship can proceed simultaneously without conflict. Both abstractions remain the standard tools for reasoning about event ordering in distributed systems.
The Byzantine generals problem, posed by Lamport, Shostak, and Pease in 1982, asked: if some fraction of machines in a distributed system may behave arbitrarily — sending contradictory messages, lying about their state, or failing in any way whatsoever — can the remaining machines still reach agreement? The answer was yes, subject to constraints: if more than one-third of machines are Byzantine, agreement is impossible regardless of the protocol. The Byzantine fault model was initially motivated by hardware failures that corrupt computation rather than stopping it, but it later became the foundation for blockchain consensus, where the Byzantine actors are assumed to be strategic adversaries rather than hardware malfunctions.
Fischer, Lynch, and Paterson’s 1985 paper “Impossibility of Distributed Consensus with One Faulty Process” — the FLP impossibility result — established one of the deepest constraints in the field. In an asynchronous distributed system where even a single process might fail (by stopping, without other processes being able to detect the failure), no protocol can guarantee that the remaining processes will reach consensus in finite time. The proof proceeds by constructing a sequence of executions in which the protocol is always in a “bivalent” state — undecided between two possible outcomes — and showing that the faulty process can always delay the decision indefinitely. The result does not say consensus is impossible; it says that any protocol must either sacrifice safety (risk choosing wrong values) or liveness (risk never choosing at all). All practical consensus protocols choose to sacrifice liveness: they guarantee correct agreement if reached, but they may not terminate if the system is sufficiently adversarial or asynchronous.
Practical consensus arrived with Paxos, described by Leslie Lamport in a 1989 paper “The Part-Time Parliament” that was sufficiently unconventionally presented — written as a fictional account of voting procedures on a Greek island — that it was rejected by reviewers as insufficiently serious and not published until 1998. Lamport’s “Paxos Made Simple” (2001) provided the more accessible treatment. Paxos works in two phases: a proposer first establishes that it has authority to propose a value (by getting promises from a majority of acceptors not to accept values from earlier proposals), then proposes the value and gets the majority to accept it. The majority requirement ensures that any two majorities overlap, so any committed decision is visible to any subsequent decision, preventing contradictions. Paxos is correct and has been the foundation of distributed coordination for twenty years, but it is notoriously difficult to understand, and extending it to practical multi-decree Paxos (for a sequence of decisions rather than a single decision) requires significant additional design work.
The practical realization of distributed systems at scale came through a series of papers from Google describing their internal infrastructure. “The Google File System” (Ghemawat, Gobioff, Leung, 2003) described a distributed file system that sacrificed POSIX compliance for the access patterns of large sequential reads and append-only writes, achieving high throughput on the commodity hardware that made large clusters economically feasible. “Bigtable: A Distributed Storage System for Structured Data” (Chang et al., 2006) described a sparse distributed table serving Google’s web index and many other products, using a sorted string table format that became the basis for the LSM-tree designs (§4.4). “Spanner: Google’s Globally-Distributed Database” (Corbett et al., 2012) demonstrated that strong consistency could be provided across globally distributed data centers using TrueTime — a timekeeping API backed by GPS and atomic clocks that provided bounded uncertainty on wall-clock time — to implement external consistency: a property stronger than linearizability, where transactions appear to execute at a point in time consistent with physical wall-clock time. Spanner contradicted the widespread engineering assumption that strong consistency was incompatible with geographic distribution at scale.
Amazon’s Dynamo paper (DeCandia et al., 2007) represented the opposite point in the design space. Dynamo, which underlies services including Amazon’s shopping cart and session state, chose high availability over strong consistency: during network partitions, Dynamo continued accepting writes on all replicas, resolving conflicts after the partition healed using application-specific reconciliation logic. The paper introduced vector clocks for conflict detection, sloppy quorums for availability during failures, and consistent hashing for partition assignment. Dynamo became the template for “eventually consistent” key-value stores and influenced the subsequent wave of NoSQL systems (Cassandra, Riak, Voldemort).
Eric Brewer’s conjecture, stated in a keynote address in 2000 and proved by Gilbert and Lynch in 2002, captured the tension between Spanner and Dynamo as a mathematical result: the CAP theorem. Under network partitions, a distributed system cannot simultaneously provide both consistency (all nodes see the same data) and availability (every request receives a response). Since network partitions cannot be prevented in any real system, designers must choose which property to sacrifice during partitions. The CAP theorem framed a decade of design decisions, though subsequent analysis — particularly Brewer’s own 2012 revisitation and the PACELC theorem (Abadi, 2012) — clarified that the original framing was too binary: the real tradeoff during partitions is between consistency and availability, and during normal operation is between latency and consistency, and different systems make different choices along both dimensions.
The state of consensus changed with Diego Ongaro’s PhD thesis work, published as “In Search of an Understandable Consensus Algorithm” with John Ousterhout in 2014 as the Raft paper. Raft was designed explicitly to be more understandable than Paxos, achieving this through a different decomposition: it separates leader election, log replication, and safety into distinct concerns, and it restricts which servers can become leader (only servers with up-to-date logs). Raft became the basis of production consensus in etcd (the Kubernetes configuration store), CockroachDB, TiKV, and many other systems. Its understandability made it practical for a broader community of engineers than Paxos had reached.
The contemporary landscape of distributed systems is shaped by the maturation of cloud platforms, which have abstracted much of the infrastructure that engineers previously built directly. Kubernetes (2014), Google’s container orchestration system open-sourced after internal development, manages the deployment, scaling, and health of containers across clusters, handling service discovery, load balancing, and failure recovery automatically. Service meshes (Istio, Linkerd) handle inter-service communication, providing TLS, traffic management, and observability. These platforms have raised the floor of what engineers can build without deep distributed systems expertise — but they have also introduced new failure modes that require exactly that expertise to diagnose.
The discipline of testing distributed systems for correctness violations — rather than only for performance — gained prominence through Kyle Kingsbury’s Jepsen analyses, which began in 2013. Kingsbury’s methodology involves running a distributed system under network partition conditions while injecting concurrent operations, then verifying that the history of operations satisfies the system’s claimed consistency properties. The analyses have repeatedly found that production systems violate their documented consistency guarantees under realistic failure conditions. The Jepsen findings have motivated the broader community to take correctness testing more seriously and have influenced how systems document and verify their consistency properties.
Consensus, Consistency, and the Limits of Distributed Agreement
The System Model and What It Determines
Every distributed systems result is stated relative to a system model: what failures are possible, how processes communicate, and what timing guarantees (if any) the network provides. These choices are not academic — they determine which algorithms are applicable and which impossibility results apply.
In the asynchronous model, messages may be delayed arbitrarily (but not lost, in the classic formulation) and processes may fail by stopping. This is the most adversarial model and the setting in which FLP applies: consensus is impossible with even one crash failure. In the synchronous model, messages are delivered within a known bound and processes that fail do so within detectable time limits. Synchronous models admit cleaner algorithms but are unrealistic for wide-area networks. The partially synchronous model, introduced by Dwork, Lynch, and Stockmeyer in 1988, captures realistic systems: the network behaves asynchronously in general but periods of synchrony occur (often “eventually” — after some unknown stabilization time). Practical consensus protocols, including Paxos and Raft, are designed for partially synchronous systems: they are always safe but guarantee liveness only during periods of synchrony.
Failure modes matter equally. Crash-stop failures (processes stop and never restart) are the simplest to handle. Crash-recovery failures (processes may restart after crashing, possibly with stale state) require protocols that maintain correctness across recovery. Byzantine failures (processes may behave arbitrarily, including sending contradictory messages) require Byzantine fault-tolerant (BFT) protocols that tolerate up to f failures with 3f + 1 total processes, at substantially higher communication cost than crash-tolerant protocols.
Consensus: The Central Problem
Consensus requires a set of processes to agree on a single value, given that each process may propose a different value and some processes may fail. The requirements are validity (the agreed value must be one that some process proposed), agreement (all correct processes agree on the same value), and termination (all correct processes eventually decide). FLP proves that termination cannot be guaranteed in asynchronous models with even one crash failure. Practical protocols relax termination to “decide eventually when the system is sufficiently stable.”
Paxos achieves safety unconditionally: if any two processes decide, they decide the same value. It achieves liveness during periods of synchrony with a stable leader. Multi-Paxos extends single-decree Paxos to a log of decisions (the sequence of state-machine commands), where a stable leader amortizes the Phase 1 cost across many decisions. Raft makes the same tradeoffs with different decomposition, restricting leader election to candidates whose logs are at least as up-to-date as any majority, simplifying correctness reasoning.
The performance characteristics of Paxos-family consensus are well understood: a decision requires at least one round trip from the leader to a majority of followers (two message delays in the best case), and the system makes progress whenever a majority is reachable and the leader is stable. The failure recovery path is more complex: a new leader must first determine the current state of all in-progress decisions before proposing new ones, requiring an additional round trip. These costs determine where Paxos-style consensus is practical: for coordination services where decisions are infrequent (configuration, leader election, distributed locks), the overhead is acceptable; for every-operation use in a high-throughput database, it is not without careful implementation.
Replication and Consistency Models
Replication — maintaining multiple copies of data across machines — provides both fault tolerance (the system survives the loss of any single copy) and performance (reads can be served from nearby replicas). The challenge is maintaining consistency across replicas.
Strong consistency (specifically linearizability) requires that the replicated system behave as if there is a single copy of the data. Every read sees the most recent write, and operations appear to take effect at a single point in time. Linearizability is implementable: single-master replication with synchronous writes to a quorum achieves it. The cost is latency (writes must wait for quorum acknowledgment) and availability under partition (writes cannot proceed if the leader cannot reach a quorum).
Eventual consistency relaxes the guarantee: if no new writes are made, replicas will eventually converge to the same state, but at any given time, different replicas may have different values. Eventual consistency enables high availability (writes can proceed on any replica) and low latency (no quorum required) at the cost of application complexity: the application must handle the possibility of reading stale data or seeing conflicts between concurrent writes.
Between these extremes are many intermediate consistency models. Causal consistency guarantees that causally related operations are seen in causal order by all processes, while causally independent operations may be seen in different orders. Session consistency guarantees that a client always reads its own writes and observes monotonically increasing versions. These models provide stronger guarantees than eventual consistency while avoiding the availability and latency costs of linearizability.
Conflict-free replicated data types (CRDTs) are data structures designed for eventual consistency: their operations are commutative and idempotent, so concurrent writes can be merged in any order without conflicts. Sets with add-only semantics, counters that support increment and decrement, last-write-wins registers, and grow-only sets are the standard CRDT examples. CRDTs resolve the conflict resolution problem that makes most eventual consistency implementations application-specific: a CRDT’s merge function is defined by the data type, not the application.
Distributed Transactions and the Coordination Cost
Distributed transactions — atomically committing or aborting a set of operations spanning multiple machines — require coordination that single-machine transactions avoid. Two-phase commit (2PC) is the classical protocol: in Phase 1, a coordinator asks all participants to vote commit or abort; in Phase 2, if all voted commit, the coordinator sends commit; otherwise it sends abort. 2PC is blocking: if the coordinator fails after Phase 1 but before Phase 2, participants that voted commit are blocked until the coordinator recovers, unable to commit or abort the transaction. Three-phase commit (3PC) adds a phase to reduce blocking but cannot handle network partitions.
Modern distributed databases avoid 2PC for the common case by using single-leader replication with Paxos-based log replication (CockroachDB, TiDB), or by using optimistic concurrency control with deterministic commit (Calvin, TAPIR). These designs show that distributed transactions can be efficient when the coordination is carefully designed — the cost is not inherent to transactions but to the naive 2PC design.
The CRDT and eventual consistency approaches avoid distributed transactions entirely, requiring applications to express their operations in a form that allows concurrent execution without global coordination. The CALM theorem (Hellerstein and Alvaro) formalizes when this is possible: a program’s results are eventually consistent and coordination-free if and only if it is monotone — the set of possible outputs only grows as input is added, never shrinks. Non-monotone computations (those that can retract previous results, such as “the maximum value seen so far has decreased”) require coordination. The CALM theorem characterizes which distributed computations inherently require consensus.
What Studying This Changes
Distributed systems changes how practitioners design any system where multiple processes share state.
The first change is the recognition of distributed-systems problems. A microservice that shares a database with another service is not “sharing a database”; it is participating in a distributed system with all the coordination and consistency challenges that implies. Two services that each read from and write to a shared queue are not “using a queue”; they are implementing a distributed coordination protocol whose correctness depends on the queue’s consistency guarantees. Practitioners who have studied distributed systems recognize these patterns immediately and know what questions to ask. Practitioners who have not often implement the same patterns without recognizing the problems they embed.
The second change is fluency with the impossibility results. FLP, CAP, and the various lower bounds on consensus and coordination are not academic curiosities but practical constraints. An engineer who attempts to build a system providing strong consistency, perfect availability, and partition tolerance has not understood CAP. An engineer who designs a consensus protocol that guarantees termination in an asynchronous system with failures has not understood FLP. These misunderstandings lead to designs that appear correct but fail under specific conditions that were not considered. Knowing the impossibility results prevents these designs from being built in the first place.
The third change is failure analysis as a design discipline. The trained practitioner routinely asks: what happens when this machine crashes? what happens when this network link fails? what happens if these two failures coincide? what happens if a failure persists for a week? The analysis shapes the design from the beginning rather than being deferred to post-incident review. Systems designed with failure analysis as a first-class concern fail predictably; systems designed without it fail chaotically.
The fourth change is operational awareness: distributed systems produce emergent behaviors under load and failure that are not visible in testing. The discipline of observability — instrumenting systems to understand their behavior in production, structuring logs and metrics to make failure modes diagnosable — is an integral part of distributed-systems work, not a separate operational concern. Engineers who design distributed systems without considering how they will be observed in production design systems they cannot operate effectively.
Resources
Books and Texts
Kleppmann’s Designing Data-Intensive Applications (O’Reilly, 2017) is the most valuable single book for a working engineer entering distributed systems. Its coverage of replication, partitioning, distributed transactions, consistency models, and stream processing is organized around engineering decisions rather than academic taxonomy. It is technically rigorous without requiring mathematical background, and it engages seriously with the research literature while remaining accessible to practitioners. Engineers who have read it have a significantly better conceptual framework for distributed systems work than those who have not.
Tanenbaum and van Steen’s Distributed Systems (4th ed., free at distributed-systems.net) covers the subject comprehensively — naming, synchronization, replication, fault tolerance, distributed file systems — with a more academic orientation than Kleppmann. Where Kleppmann organizes around engineering decisions, Tanenbaum organizes around conceptual categories, making it better as a reference for specific topics and less compelling as a narrative. The free availability and the comprehensiveness make it an important complement.
Lynch’s Distributed Algorithms (Morgan Kaufmann, 1996) provides the mathematical treatment: the I/O automaton formalism for specifying distributed systems, proofs of the foundational algorithms, and the impossibility results with their proofs. It is demanding but provides the kind of understanding that holds up when you need to reason carefully about a new protocol. Engineers planning to design or analyze distributed protocols should read it. For most practitioners, reading the relevant chapters alongside Kleppmann provides the right depth without requiring the full mathematical treatment.
The MIT 6.5840 Distributed Systems course (formerly 6.824, free at pdos.csail.mit.edu/6.5840) is the gold standard course. The reading list — Raft, Zookeeper, Spanner, MapReduce, Dynamo, and other papers — provides the canonical paper diet. The labs — implementing a distributed key-value store using Raft — are the most valuable distributed systems implementation exercise available. Completing the Raft lab requires implementing leader election, log replication, and log compaction, and getting the implementation to pass the test suite under simulated network partition and server crash conditions. No other publicly available exercise covers this ground as effectively.
| Book | Role | Type |
|---|---|---|
| Kleppmann, Designing Data-Intensive Applications | Contemporary engineering-oriented entry | Entry |
| Tanenbaum & van Steen, Distributed Systems (4th ed., free) | Comprehensive academic reference | Entry |
| Lynch, Distributed Algorithms | Mathematical treatment of distributed algorithms | Depth |
| Cachin, Guerraoui & Rodrigues, Introduction to Reliable and Secure Distributed Programming | Rigorous algorithmic foundations | Depth |
Courses and Lectures
MIT 6.5840 (Distributed Systems, free at pdos.csail.mit.edu/6.5840) is the canonical course. The lab sequence — implementing MapReduce, implementing Raft, implementing a fault-tolerant key-value store using Raft, implementing a sharded key-value store — provides a complete path from “I understand Raft conceptually” to “I have implemented Raft and debugged it under failure injection.” The lecture videos and paper reading list are valuable independently of the labs, but the labs are where the understanding is built.
Martin Kleppmann’s Cambridge lecture series on distributed systems (free on YouTube) covers the foundational material — system models, logical clocks, broadcast protocols, replication, consistency — at a level appropriate for the book’s audience. The lectures are more theoretically complete than the book in some areas and are worth watching alongside it.
| Course | Platform | Type |
|---|---|---|
| MIT 6.5840 Distributed Systems (free) | MIT / YouTube | Entry |
| Kleppmann Cambridge distributed systems lectures (free) | YouTube | Entry |
Papers and Current Sources
The research papers are a primary resource in distributed systems in a way that is unusual even within CS. The field’s canonical results are described most clearly and most authoritatively in the papers themselves, and reading them is qualitatively different from reading textbook summaries.
Essential papers: Lamport’s “Time, Clocks, and the Ordering of Events” (1978); Fischer, Lynch, Paterson “Impossibility of Distributed Consensus” (1985); Lamport “Paxos Made Simple” (2001); Ongaro and Ousterhout “In Search of an Understandable Consensus Algorithm” (Raft, 2014); DeCandia et al. “Dynamo: Amazon’s Highly Available Key-Value Store” (2007); Corbett et al. “Spanner: Google’s Globally-Distributed Database” (2012); Gilbert and Lynch “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services” (CAP proof, 2002).
These papers are all freely available and between 10 and 30 pages each. Reading each paper after studying the topic in Kleppmann or Tanenbaum — to see how the original authors framed the problem and what they considered important — develops a kind of understanding that textbook study does not produce.
| Paper | Role | Type |
|---|---|---|
| Lamport, “Time, Clocks, and the Ordering of Events” (1978, free) | Logical clocks; foundational paper | Depth |
| Fischer, Lynch, Paterson, FLP impossibility (1985, free) | The central impossibility result | Depth |
| Lamport, “Paxos Made Simple” (2001, free) | Consensus; essential paper | Depth |
| Ongaro & Ousterhout, Raft paper (2014, free) | Understandable consensus | Depth |
| DeCandia et al., Dynamo (2007, free) | Eventual consistency at scale | Depth |
| Corbett et al., Spanner (2012, free) | Global strong consistency | Depth |
| Gilbert & Lynch, CAP proof (2002, free) | The CAP theorem formally | Depth |
Practice, Tools, and Current Sources
The MIT 6.5840 Raft lab is the primary implementation exercise. Instructions are provided in the course materials; the lab requires implementing leader election, log replication, persistence, and log compaction, with a test suite that injects network partitions and server crashes.
TLA+ (§3.6) is the right tool for specifying and model-checking distributed protocols before implementing them. The TLA+ specification for Raft (by Ongaro, freely available) can be checked with the TLC model checker to verify that the protocol satisfies its safety properties on small model instances. Writing a TLA+ specification for a protocol before implementing it reveals logical errors that would otherwise appear only under specific failure conditions in testing.
Jepsen analyses (jepsen.io) document what happens when production distributed systems are tested under network partition conditions. Reading the analyses for systems you use — Kafka, Cassandra, MongoDB, Redis — reveals the gap between documented guarantees and actual behavior under failure and motivates careful consistency model selection.
Kyle Kingsbury’s talks on distributed systems testing (available on YouTube) explain the methodology behind Jepsen and provide a framework for thinking about how to test distributed systems correctness rather than only performance.
| Resource | Platform | Type |
|---|---|---|
| MIT 6.5840 Raft lab | pdos.csail.mit.edu/6.5840 | Practice |
| TLA+ with Raft specification | lamport.azurewebsites.net + GitHub | Practice |
| Jepsen analyses (free) | jepsen.io | Reference |
| Jepsen consistency models (free) | jepsen.io/consistency | Reference |
| Gossip Glomers distributed systems challenges (free) | fly.io/dist-sys | Practice |
| Kingsbury distributed systems testing talks (free) | YouTube | Depth |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| The eight fallacies of distributed computing | Engineers without distributed systems training implicitly assume that the network is reliable, latency is negligible, bandwidth is unlimited, the network is secure, topology does not change, and there is one administrator. These assumptions are false for any real distributed system. Code written under these assumptions works in local testing and fails under realistic conditions. | Review Peter Deutsch’s eight fallacies explicitly before designing any distributed system. For each assumption in a design, ask: what happens if this assumption is violated? Systems designed with realistic assumptions about network behavior fail predictably rather than chaotically. |
| The CAP theorem misunderstanding | CAP is widely cited but often misunderstood. It does not say that distributed systems must always sacrifice either consistency or availability — it says that under network partition, a system must choose which to sacrifice. In normal operation (no partition), a system can provide both. The PACELC theorem adds the normal-operation tradeoff: latency versus consistency. Many engineers make the wrong consistency/availability choice because they are applying CAP as a general constraint rather than as a partition-specific one. | Read the CAP theorem formally (Gilbert and Lynch 2002) and Brewer’s 2012 revisitation. Then read the PACELC paper. The precise statements are important; the folk versions that circulate in engineering culture misrepresent what the theorems say. |
| Implementing consensus without fully understanding it | Paxos and Raft are subtle protocols where small deviations from the specification break correctness in ways that only appear under specific failure conditions. Engineers who implement consensus from a high-level description, without reading the protocol specification carefully and implementing the test suite, produce implementations that pass basic tests and fail in production. | Implement Raft using the MIT 6.5840 lab as a guide. Read the Raft paper’s Figure 2 (the complete protocol specification) as the authoritative reference. Run the test suite with failure injection enabled. An implementation that passes the test suite has been subjected to failure conditions that informal implementations never encounter. |
| Ignoring failure modes in design | Distributed systems fail in ways that single-machine systems do not: network partitions, split-brain conditions, clock skew, Byzantine failures from bit-flipping hardware. Designs that have not been analyzed for these failure modes contain latent bugs that emerge only under conditions that are difficult to reproduce. The most dangerous bugs are those that cause data corruption rather than crashes — corruption can persist undetected for days before its effects become apparent. | For every distributed system design, perform a systematic failure analysis before implementation. Ask: what happens if the leader crashes here? what happens if this write is acknowledged but the acknowledgment is lost? what happens if two nodes both believe they are the leader? These questions have answers, and the answers determine whether the design is correct. |
| Treating eventual consistency as “good enough” without understanding what it gives up | Eventual consistency is appropriate for some applications and inappropriate for others. A distributed counter for page views can tolerate eventual consistency. A shopping cart that reflects a user’s current selections probably cannot — if the cart shows stale data, the user may purchase something they already deleted. Many engineers adopt eventually consistent systems because they are simpler to scale, without carefully analyzing whether the application’s correctness depends on consistency guarantees the system does not provide. | For any application that uses an eventually consistent data store, explicitly identify which operations require reading up-to-date data and which can tolerate stale reads. If operations that require up-to-date data are served by eventually consistent reads, the application is subtly incorrect. Weaker consistency models are appropriate when the application genuinely tolerates the weaker guarantees — not as a default choice motivated by simplicity. |
| Skipping the implementation labs | Distributed systems is one of the subjects where the gap between understanding the concepts and being able to implement a correct system is largest. Reading about Raft and understanding Raft well enough to implement it correctly under failure injection are different things. The implementation process reveals subtleties in the specification that reading does not: what exactly should happen when a leader receives a message from a higher-term leader while it has pending uncommitted entries? The specification answers this; intuition often answers incorrectly. | Complete the MIT 6.5840 Raft lab or equivalent. The test suite for the lab is specifically designed to expose common implementation errors by injecting the exact failure conditions under which they manifest. An implementation that passes is not necessarily correct, but one that fails is definitely incorrect, and the failures are informative. |
中文
分布式系统是一组独立机器，它们通过协调，对外表现为一个连贯服务。这些机器会独立失败，通过不可靠网络通信，并且没有共享内存，也没有全局时钟。所有让单机编程变得可处理的假设——内存速度均匀、共享状态上的操作是原子的、某物失败时会完全失败——都会消失。剩下的东西比多数程序员预期的更困难，也更陌生：在这里，一台机器无法判断 peer 是已经崩溃，还是只是变慢；两个正确进程可能以不同顺序观察到同一组事件；而某些协调问题在数学上不可能在所有情况下都被正确解决。
这种困难的回报是，分布式系统能做到单台机器做不到的事情：它们可以扩展到任何单个硬件能力之外，可以在个别组件失败时仍保持可用，也可以从地理分布位置以低延迟服务用户。但这些能力不是免费的——它们要求放弃单机系统自动提供的一些性质。分布式系统的中心智识活动，就是精确理解这些权衡：必须放弃什么，可以保留什么，根本限制在哪里。
这门学科围绕三个层次组织。系统模型建立形式化设定：可以对消息投递、机器行为和失败模式做出什么假设？在同步模型中成立的结果（消息投递时间有界），可能在异步模型中失败；异步系统中的不可能性结果，也未必适用于部分同步系统。基础问题——consensus、replication、distributed transactions、leader election、global snapshots——是规范问题，它们的解构成智识核心。系统层则是把这些解组合进真实基础设施的地方：分布式数据库、协调服务、流处理器、分布式文件系统。
前置知识：操作系统（§4.2）——进程、并发原语，以及分布式系统所扩展的单机资源。计算机网络（§4.3）——分布式系统建立其上的不可靠通信层。数据库（§4.4）——事务、一致性模型和持久性，这些都会推广到分布式设定中。
从逻辑时钟到全球分布式事务
分布式系统的理论基础，早于真正需要它们的实践系统到来。
Leslie Lamport 1978 年的论文 “Time, Clocks, and the Ordering of Events in a Distributed System”，确立了这个领域此后几十年会使用的概念词汇。Lamport 的关键洞见是，在分布式系统中，不能信任物理时钟来确定事件顺序——时钟会漂移，而在机器之间完美同步时钟是不可能的。能够建立的是一种基于因果性的逻辑顺序：如果事件 A 导致了事件 B（通过发送一条被 B 接收的消息），那么 A happened before B，而这正是推理分布式系统时唯一重要的意义。Lamport 的 logical clocks 为事件分配整数，使具有因果关系的事件获得递增编号，从而能在不使用物理时间的情况下推理 happens-before relationships。Fidge 和 Mattern 于 1988 年发展的 vector clocks 扩展了这一思想，用来捕捉并发性：没有因果关系的事件可以同时进行而不冲突。这两种抽象至今仍是推理分布式系统中事件顺序的标准工具。
Byzantine generals problem 由 Lamport、Shostak 和 Pease 于 1982 年提出，它问的是：如果分布式系统中某一部分机器可能任意行为——发送互相矛盾的消息、谎报状态，或以任何方式失败——剩下的机器还能达成一致吗？答案是可以，但有约束：如果超过三分之一的机器是 Byzantine，那么无论使用什么协议，一致都不可能。Byzantine fault model 最初动机来自会破坏计算而不是停止计算的硬件失败，但后来成为 blockchain consensus 的基础；在这里，Byzantine actors 被假定为战略性对手，而不是硬件故障。
Fischer、Lynch 和 Paterson 1985 年的论文 “Impossibility of Distributed Consensus with One Faulty Process”——也就是 FLP impossibility result——确立了这个领域最深的限制之一。在一个异步分布式系统中，只要有一个进程可能失败（停止运行，而其他进程无法检测到这个失败），就没有任何协议能保证剩余进程在有限时间内达成 consensus。证明通过构造一系列执行过程，使协议始终处在 “bivalent” 状态——在两个可能结果之间尚未决定——并展示故障进程总能无限推迟决定。这个结果不是说 consensus 不可能；它说任何协议都必须牺牲 safety（冒着选择错误值的风险）或 liveness（冒着永远不选择的风险）。所有实践 consensus protocols 都选择牺牲 liveness：如果达成一致，它们保证一致是正确的，但如果系统足够对抗性或足够异步，它们可能不会终止。
实践性 consensus 随 Paxos 到来。Leslie Lamport 在 1989 年论文 “The Part-Time Parliament” 中描述了 Paxos，但其呈现方式非常非传统——它被写成一个希腊岛屿投票程序的虚构记录——以至于审稿人认为它不够严肃，并拒绝发表；直到 1998 年才正式发表。Lamport 的 “Paxos Made Simple”（2001）提供了更易理解的处理。Paxos 分两阶段工作：proposer 首先确立自己有权提出某个值（通过获得 acceptors 中多数人的 promises，承诺不再接受更早 proposal 的值），然后提出该值，并获得多数接受。多数要求保证任意两个多数集合都会相交，因此任何已提交决定都会被任何后续决定看到，从而防止矛盾。Paxos 是正确的，并且二十年来一直是分布式协调的基础，但它以难以理解著称；把它扩展到实践性的 multi-decree Paxos（面向一系列决定，而不是单个决定）还需要大量额外设计工作。
大规模分布式系统的实践实现，来自 Google 描述其内部基础设施的一系列论文。“The Google File System”（Ghemawat、Gobioff、Leung，2003）描述了一个分布式文件系统，它为了适配大规模顺序读取和 append-only writes 的访问模式，牺牲了 POSIX compliance，并在让大规模集群经济可行的 commodity hardware 上实现了高吞吐量。“Bigtable: A Distributed Storage System for Structured Data”（Chang 等，2006）描述了一个稀疏分布式表，服务 Google 的 Web index 和许多其他产品，使用 sorted string table 格式，而这种格式后来成为 LSM-tree designs（§4.4）的基础。“Spanner: Google’s Globally-Distributed Database”（Corbett 等，2012）证明，可以使用 TrueTime——一个由 GPS 和原子钟支持、能提供 wall-clock time 有界不确定性的时间 API——在全球分布的数据中心之间提供 strong consistency，并实现 external consistency：一种强于 linearizability 的性质，使事务看起来是在与物理墙钟时间一致的某个时间点执行。Spanner 反驳了当时广泛存在的工程假设：strong consistency 与大规模地理分布不兼容。
Amazon 的 Dynamo 论文（DeCandia 等，2007）代表了设计空间中的相反点。Dynamo 是 Amazon shopping cart 和 session state 等服务的底层系统，它选择高可用性而不是 strong consistency：在 network partitions 期间，Dynamo 继续接受所有 replicas 上的 writes，并在分区恢复后使用应用特定 reconciliation logic 解决冲突。该论文引入了用于 conflict detection 的 vector clocks、用于失败期间保持可用性的 sloppy quorums，以及用于 partition assignment 的 consistent hashing。Dynamo 成为 “eventually consistent” key-value stores 的模板，并影响了后来的 NoSQL 系统浪潮（Cassandra、Riak、Voldemort）。
Eric Brewer 在 2000 年一次 keynote address 中提出的猜想，以及 Gilbert 和 Lynch 于 2002 年的证明，把 Spanner 与 Dynamo 之间的张力表达成一个数学结果：CAP theorem。在 network partitions 下，一个分布式系统不能同时提供 consistency（所有节点看到同一数据）和 availability（每个请求都收到响应）。由于任何真实系统都无法防止 network partitions，设计者必须选择在分区期间牺牲哪种性质。CAP theorem 框定了十年的设计决策，尽管后续分析——尤其是 Brewer 自己 2012 年的 revisitation，以及 PACELC theorem（Abadi，2012）——澄清了原始框架过于二元：分区期间的真实权衡是在 consistency 与 availability 之间；正常运行期间的权衡是在 latency 与 consistency 之间；不同系统会在这两个维度上做出不同选择。
随着 Diego Ongaro 博士论文工作的发展，consensus 的状态发生了变化。他与 John Ousterhout 于 2014 年发表 “In Search of an Understandable Consensus Algorithm”，也就是 Raft 论文。Raft 被明确设计为比 Paxos 更容易理解，它通过不同分解实现这一点：把 leader election、log replication 和 safety 分离为不同关切，并限制哪些 servers 可以成为 leader（只有 logs 足够新的 servers 才可以）。Raft 成为 etcd（Kubernetes configuration store）、CockroachDB、TiKV 以及许多其他系统中的生产 consensus 基础。它的可理解性，使 Paxos 未能触达的更广泛工程师群体也能实际使用 consensus。
当代分布式系统图景由云平台的成熟塑造，这些平台抽象掉了许多过去工程师必须直接构建的基础设施。Kubernetes（2014）是 Google 的 container orchestration system，在内部发展后开源；它管理 clusters 中 containers 的部署、扩展和健康状态，自动处理 service discovery、load balancing 和 failure recovery。Service meshes（Istio、Linkerd）处理服务间通信，提供 TLS、traffic management 和 observability。这些平台提高了工程师在没有深厚分布式系统专业知识情况下可以构建内容的下限——但它们也引入了新的失败模式，而诊断这些失败模式恰恰需要这种专业知识。
通过 Kyle Kingsbury 的 Jepsen analyses，测试分布式系统 correctness violations——而不只是测试性能——的纪律开始受到重视。Jepsen 分析始于 2013 年。Kingsbury 的方法是在 network partition 条件下运行一个分布式系统，同时注入并发操作，然后验证操作历史是否满足该系统声称的一致性性质。这些分析反复发现，生产系统会在现实失败条件下违反其文档化的一致性保证。Jepsen 的发现推动了更广泛共同体更严肃地对待正确性测试，并影响了系统如何记录和验证其一致性性质。
Consensus、一致性与分布式一致的限制
系统模型及其决定的内容
每一个分布式系统结果，都是相对于某个系统模型陈述的：可能发生哪些失败，进程如何通信，网络提供哪些 timing guarantees（如果有的话）。这些选择不是学术细节——它们决定哪些算法适用，以及哪些不可能性结果适用。
在异步模型中，消息可以被任意延迟（但在经典表述中不会丢失），进程可能因停止而失败。这是最具对抗性的模型，也是 FLP 适用的设定：即使只有一个 crash failure，consensus 也不可能。在同步模型中，消息会在已知边界内投递，而进程失败也会在可检测时间限制内发生。同步模型允许更干净的算法，但对广域网络来说不现实。部分同步模型由 Dwork、Lynch 和 Stockmeyer 于 1988 年引入，捕捉了现实系统：网络一般按异步方式表现，但会出现同步时期（通常是 “eventually”——在某个未知稳定时间之后）。实践 consensus protocols，包括 Paxos 和 Raft，都为部分同步系统设计：它们始终安全，但只在同步时期保证 liveness。
失败模式同样重要。Crash-stop failures（进程停止并且永不重启）最容易处理。Crash-recovery failures（进程崩溃后可能重启，且可能带着过时状态）要求协议在恢复过程中仍保持正确性。Byzantine failures（进程可以任意行为，包括发送矛盾消息）要求 Byzantine fault-tolerant（BFT）protocols，这类协议在总数 3f + 1 个进程中可容忍最多 f 个失败，通信成本显著高于 crash-tolerant protocols。
Consensus：中心问题
Consensus 要求一组进程就一个单一值达成一致，前提是每个进程可能提出不同值，且某些进程可能失败。其要求包括 validity（达成一致的值必须是某个进程提出过的值）、agreement（所有正确进程同意同一个值）和 termination（所有正确进程最终做出决定）。FLP 证明，在有哪怕一个 crash failure 的异步模型中，termination 无法得到保证。实践协议会把 termination 放宽为“当系统足够稳定时最终决定”。
Paxos 无条件实现 safety：如果任意两个进程做出决定，那么它们决定的是同一个值。它在具有稳定 leader 的同步时期实现 liveness。Multi-Paxos 把 single-decree Paxos 扩展到一个 decision log（也就是 state-machine commands 的序列），其中稳定 leader 会把 Phase 1 成本摊销到许多 decisions 上。Raft 以不同分解做出同样权衡，把 leader election 限制为只有 logs 至少与任意多数一样新的 candidates 才能获选，从而简化正确性推理。
Paxos-family consensus 的性能特征已经相当清楚：一次决定至少需要 leader 到多数 followers 的一次 round trip（最佳情况下两个 message delays），只要多数可达且 leader 稳定，系统就能前进。Failure recovery path 更复杂：新的 leader 必须先确定所有进行中 decisions 的当前状态，然后才能提出新 decisions，这需要额外一次 round trip。这些成本决定了 Paxos-style consensus 在哪里实用：对于 decisions 不频繁的协调服务（configuration、leader election、distributed locks），开销可接受；但如果在高吞吐数据库中对每次操作都使用它，若没有谨慎实现，就不现实。
Replication 与 Consistency Models
Replication——在多台机器上维护多份数据副本——同时提供 fault tolerance（系统可以承受任一副本丢失）和性能（reads 可以由附近 replicas 服务）。挑战在于维持 replicas 之间的一致性。
Strong consistency（具体来说是 linearizability）要求复制系统表现得像只有一份数据。每次 read 都看到最近的 write，而 operations 看起来都在某个单一时间点生效。Linearizability 是可以实现的：single-master replication 配合同步写入 quorum 就能实现。代价是 latency（writes 必须等待 quorum acknowledgment）和分区下的 availability（如果 leader 无法到达 quorum，writes 就无法继续）。
Eventual consistency 放松保证：如果没有新的 writes，replicas 最终会收敛到同一状态，但在任一给定时刻，不同 replicas 可能有不同值。Eventual consistency 允许高可用性（writes 可以在任意 replica 上继续）和低延迟（不需要 quorum），代价是应用复杂性：应用必须处理读取 stale data 或看到 concurrent writes 冲突的可能性。
在这两个极端之间，还有许多中间 consistency models。Causal consistency 保证所有进程都会按因果顺序看到有因果关系的 operations，而因果上独立的 operations 可以以不同顺序被看到。Session consistency 保证一个 client 总能 read its own writes，并观察到单调递增的 versions。这些模型提供了强于 eventual consistency 的保证，同时避免 linearizability 的可用性和延迟成本。
Conflict-free replicated data types（CRDTs）是为 eventual consistency 设计的数据结构：它们的 operations 是 commutative 和 idempotent 的，因此 concurrent writes 可以按任意顺序合并而不产生冲突。只支持 add 的 sets、支持 increment 和 decrement 的 counters、last-write-wins registers，以及 grow-only sets，是标准 CRDT examples。CRDTs 解决了多数 eventual consistency 实现中需要应用特定处理的 conflict resolution 问题：CRDT 的 merge function 由数据类型定义，而不是由应用定义。
分布式事务与协调成本
分布式事务——在多台机器上原子 commit 或 abort 一组操作——需要单机事务所不需要的协调。Two-phase commit（2PC）是经典协议：Phase 1 中，coordinator 要求所有 participants vote commit or abort；Phase 2 中，如果所有人都 vote commit，coordinator 发送 commit；否则发送 abort。2PC 是 blocking 的：如果 coordinator 在 Phase 1 之后、Phase 2 之前失败，已经 vote commit 的 participants 会被阻塞，直到 coordinator 恢复，无法 commit 也无法 abort transaction。Three-phase commit（3PC）增加一个阶段以减少 blocking，但无法处理 network partitions。
现代分布式数据库会通过使用带 Paxos-based log replication 的 single-leader replication（CockroachDB、TiDB），或使用 optimistic concurrency control with deterministic commit（Calvin、TAPIR），避免在常见情况下使用 2PC。这些设计表明，只要协调设计得足够谨慎，分布式事务可以高效；成本并不是事务本身固有的，而是 naive 2PC 设计的成本。
CRDT 和 eventual consistency 路线完全避免分布式事务，要求应用把操作表达成不需要全局协调也能并发执行的形式。CALM theorem（Hellerstein 和 Alvaro）形式化了什么时候这可行：一个程序的结果 eventual consistent 且 coordination-free，当且仅当它是 monotone 的——也就是随着输入增加，可能输出集合只会增长，永不缩小。Non-monotone computations（那些会撤回先前结果的计算，例如“目前见到的最大值下降了”）需要协调。CALM theorem 刻画了哪些分布式计算天然需要 consensus。
学习这一部分会改变什么
分布式系统会改变实践者设计任何多个进程共享状态系统的方式。
第一个变化，是识别分布式系统问题的能力。一个 microservice 与另一个 service 共享数据库，并不是“共享一个数据库”；它是在参与一个分布式系统，并承担这所暗含的全部协调与一致性挑战。两个 services 分别从同一个 queue 中读取和写入，并不是“使用一个 queue”；它们是在实现一个分布式协调协议，而其正确性取决于该 queue 的一致性保证。学习过分布式系统的实践者会立刻识别这些模式，并知道该问哪些问题。没有学过的人，经常在不认识问题的情况下实现同样模式。
第二个变化，是熟悉不可能性结果。FLP、CAP 以及各种 consensus 和协调 lower bounds 不是学术奇观，而是实践约束。一个试图构建同时提供 strong consistency、perfect availability 和 partition tolerance 的系统的工程师，没有理解 CAP。一个设计出能在存在失败的异步系统中保证 termination 的 consensus protocol 的工程师，没有理解 FLP。这些误解会带来看似正确、但在特定未考虑条件下失败的设计。知道不可能性结果，可以从一开始就阻止这些设计被建造出来。
第三个变化，是把 failure analysis 当成设计纪律。受过训练的实践者会例行询问：这台机器崩溃会怎样？这条网络链路失败会怎样？如果这两个失败同时发生会怎样？如果一个失败持续一周会怎样？分析从一开始就塑造设计，而不是被推迟到事故复盘。把 failure analysis 当成一等关切设计出的系统，会以可预测方式失败；没有它的系统，会以混乱方式失败。
第四个变化，是运维意识：分布式系统在负载和失败下会产生测试中看不见的 emergent behaviors。Observability 这门纪律——为系统加 instrumentation 以理解生产行为，组织 logs 和 metrics 以使失败模式可诊断——是分布式系统工作的一部分，而不是单独的运维问题。设计分布式系统却不考虑如何在生产中观察它们的工程师，会设计出自己无法有效运维的系统。
资源
书籍与文本
Kleppmann 的 Designing Data-Intensive Applications（O’Reilly，2017）是工作工程师进入分布式系统最有价值的单本书。它对 replication、partitioning、distributed transactions、consistency models 和 stream processing 的覆盖，是围绕工程决策而不是学术分类组织的。它技术上严谨，但不要求数学背景；它认真接触研究文献，同时对实践者保持可读性。读过这本书的工程师，在分布式系统工作上会比没有读过的人拥有明显更好的概念框架。
Tanenbaum 和 van Steen 的 Distributed Systems（第 4 版，可在 distributed-systems.net 免费获取）全面覆盖这门学科——命名、同步、replication、fault tolerance、分布式文件系统——学术导向比 Kleppmann 更强。Kleppmann 围绕工程决策组织，Tanenbaum 则围绕概念类别组织，因此更适合作为特定主题参考，叙事吸引力较弱。免费可得和综合性，使它成为重要补充。
Lynch 的 Distributed Algorithms（Morgan Kaufmann，1996）提供数学处理：用于规定分布式系统的 I/O automaton formalism，基础算法证明，以及不可能性结果及其证明。它要求很高，但提供一种当你需要仔细推理新协议时仍然稳固的理解。计划设计或分析分布式协议的工程师应当阅读它。对多数实践者来说，把相关章节与 Kleppmann 搭配阅读，可以在不要求完整数学处理的情况下获得合适深度。
MIT 6.5840 Distributed Systems 课程（原 6.824，可在 pdos.csail.mit.edu/6.5840 免费获取）是黄金标准课程。阅读列表——Raft、Zookeeper、Spanner、MapReduce、Dynamo 以及其他论文——提供了标准论文饮食。实验——使用 Raft 实现一个分布式 key-value store——是目前最有价值的分布式系统实现练习。完成 Raft lab 要求实现 leader election、log replication 和 log compaction，并让实现通过在模拟 network partition 和 server crash 条件下运行的测试套件。没有其他公开可用练习能如此有效地覆盖这块内容。
| 书籍 | 作用 | 类型 |
|---|---|---|
| Kleppmann, Designing Data-Intensive Applications | 当代工程导向入口 | 入门 |
| Tanenbaum & van Steen, Distributed Systems（第 4 版，免费） | 综合学术参考 | 入门 |
| Lynch, Distributed Algorithms | 分布式算法的数学处理 | 深入 |
| Cachin, Guerraoui & Rodrigues, Introduction to Reliable and Secure Distributed Programming | 严格算法基础 | 深入 |
课程与讲座
MIT 6.5840（Distributed Systems，pdos.csail.mit.edu/6.5840 免费）是经典课程。实验序列——实现 MapReduce、实现 Raft、用 Raft 实现 fault-tolerant key-value store、实现 sharded key-value store——提供了一条完整路径，从“我在概念上理解 Raft”，到“我已经实现 Raft，并在 failure injection 下调试过它”。讲座视频和论文阅读列表即使不做实验也有价值，但真正建立理解的是实验。
Martin Kleppmann 的 Cambridge distributed systems lecture series（YouTube 免费）覆盖基础材料——system models、logical clocks、broadcast protocols、replication、consistency——难度适合其书籍读者。在某些区域，讲座比书更理论完整，值得与书一起观看。
| 课程 | 平台 | 类型 |
|---|---|---|
| MIT 6.5840 Distributed Systems（免费） | MIT / YouTube | 入门 |
| Kleppmann Cambridge distributed systems lectures（免费） | YouTube | 入门 |
论文与当前资料
在分布式系统中，研究论文作为一手资源的重要性甚至超过 CS 中许多其他领域。这个领域的经典结果，往往在论文中被最清楚、最权威地描述；阅读论文与阅读教材摘要，在性质上不同。
必要论文包括：Lamport 的 “Time, Clocks, and the Ordering of Events”（1978）；Fischer、Lynch、Paterson 的 “Impossibility of Distributed Consensus”（1985）；Lamport 的 “Paxos Made Simple”（2001）；Ongaro 和 Ousterhout 的 “In Search of an Understandable Consensus Algorithm”（Raft，2014）；DeCandia 等的 “Dynamo: Amazon’s Highly Available Key-Value Store”（2007）；Corbett 等的 “Spanner: Google’s Globally-Distributed Database”（2012）；Gilbert 和 Lynch 的 “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services”（CAP proof，2002）。
这些论文都可免费获取，每篇大约 10 到 30 页。每学完 Kleppmann 或 Tanenbaum 中的相关主题后阅读对应论文——看原作者如何框定问题，以及他们认为哪些内容重要——会发展出教材学习无法产生的理解。
| 论文 | 作用 | 类型 |
|---|---|---|
| Lamport, “Time, Clocks, and the Ordering of Events”（1978，免费） | Logical clocks；奠基论文 | 深入 |
| Fischer, Lynch, Paterson, FLP impossibility（1985，免费） | 中心不可能性结果 | 深入 |
| Lamport, “Paxos Made Simple”（2001，免费） | Consensus；必要论文 | 深入 |
| Ongaro & Ousterhout, Raft paper（2014，免费） | 可理解的 consensus | 深入 |
| DeCandia et al., Dynamo（2007，免费） | 大规模 eventual consistency | 深入 |
| Corbett et al., Spanner（2012，免费） | 全球 strong consistency | 深入 |
| Gilbert & Lynch, CAP proof（2002，免费） | CAP theorem 的形式证明 | 深入 |
实践、工具与当前资料
MIT 6.5840 Raft lab 是主要实现练习。课程材料提供说明；该实验要求实现 leader election、log replication、persistence 和 log compaction，并配有注入 network partitions 和 server crashes 的测试套件。
TLA+（§3.6）是在实现分布式协议之前进行 specification 和 model-checking 的正确工具。Ongaro 的 Raft TLA+ specification 可免费获取，并可用 TLC model checker 检查，以验证协议在小型模型实例上满足其 safety properties。在实现协议之前为其写 TLA+ specification，会暴露一些逻辑错误，否则这些错误只会在测试中特定失败条件下出现。
Jepsen analyses（jepsen.io）记录了生产分布式系统在 network partition 条件下被测试时会发生什么。阅读你使用的系统——Kafka、Cassandra、MongoDB、Redis——对应的分析，可以揭示文档化保证与真实失败行为之间的差距，并促使人谨慎选择 consistency model。
Kyle Kingsbury 关于 distributed systems testing 的演讲（YouTube 可得）解释了 Jepsen 背后的方法论，并提供一个框架，用于思考如何测试 distributed systems correctness，而不只是性能。
| 资源 | 平台 | 类型 |
|---|---|---|
| MIT 6.5840 Raft lab | pdos.csail.mit.edu/6.5840 | 实践 |
| TLA+ with Raft specification | lamport.azurewebsites.net + GitHub | 实践 |
| Jepsen analyses（免费） | jepsen.io | 参考 |
| Jepsen consistency models（免费） | jepsen.io/consistency | 参考 |
| Gossip Glomers distributed systems challenges（免费） | fly.io/dist-sys | 实践 |
| Kingsbury distributed systems testing talks（免费） | YouTube | 深入 |
陷阱
| 陷阱 | 为什么会误导 | 更好的回应 |
|---|---|---|
| 分布式计算的八个谬误 | 没有分布式系统训练的工程师会隐含假设网络是可靠的、延迟可忽略、带宽无限、网络安全、拓扑不会变化、只有一个管理员。这些假设对任何真实分布式系统都是假的。建立在这些假设上的代码在本地测试中能工作，在真实条件下会失败。 | 在设计任何分布式系统之前，明确复习 Peter Deutsch 的 eight fallacies。对设计中的每个假设都问：如果这个假设被违反会怎样？以现实网络行为假设设计的系统，会以可预测方式失败，而不是混乱失败。 |
| 误解 CAP theorem | CAP 被广泛引用，但经常被误解。它不是说分布式系统总是必须牺牲 consistency 或 availability；它说的是在 network partition 下，系统必须选择牺牲哪一个。在正常运行时（没有 partition），系统可以同时提供二者。PACELC theorem 增加了正常运行中的权衡：latency versus consistency。许多工程师会做出错误的一致性/可用性选择，因为他们把 CAP 当作一般性约束，而不是 partition-specific 约束。 | 阅读 CAP theorem 的形式化表述（Gilbert 和 Lynch，2002）以及 Brewer 2012 年的 revisitation。然后阅读 PACELC 论文。精确陈述很重要；工程文化中流传的民间版本会误表这些定理真正说了什么。 |
| 没有充分理解就实现 consensus | Paxos 和 Raft 都是微妙协议，对 specification 的小偏离会以只在特定失败条件下出现的方式破坏正确性。工程师如果只根据高层描述实现 consensus，而不仔细阅读 protocol specification 和实现 test suite，会得到能通过基础测试、却在生产中失败的实现。 | 以 MIT 6.5840 lab 为指导实现 Raft。把 Raft 论文中的 Figure 2（完整 protocol specification）作为权威参考。开启 failure injection 运行测试套件。一个通过测试套件的实现，已经经历了非正式实现很少遭遇的失败条件。 |
| 设计中忽视失败模式 | 分布式系统会以单机系统不会出现的方式失败：network partitions、split-brain conditions、clock skew、bit-flipping hardware 导致的 Byzantine failures。没有分析这些失败模式的设计，包含 latent bugs，而这些 bug 只会在难以复现的条件下出现。最危险的 bug 是导致数据损坏而不是崩溃的 bug——损坏可能持续数天不被发现，直到其影响变得明显。 | 对每个分布式系统设计，在实现前进行系统性 failure analysis。问：如果 leader 在这里崩溃会怎样？如果这个 write 已被 acknowledged，但 acknowledgment 丢失会怎样？如果两个节点都认为自己是 leader 会怎样？这些问题有答案，而答案决定设计是否正确。 |
| 不理解放弃了什么，就把 eventual consistency 当作“够用” | Eventual consistency 适合某些应用，不适合另一些应用。用于 page views 的分布式 counter 可以容忍 eventual consistency。反映用户当前选择的 shopping cart 可能不能——如果 cart 显示 stale data，用户可能购买自己已经删除的东西。许多工程师采用 eventually consistent systems，是因为它们更容易扩展，却没有仔细分析应用正确性是否依赖系统并未提供的一致性保证。 | 对任何使用 eventually consistent data store 的应用，明确识别哪些 operations 需要读取 up-to-date data，哪些可以容忍 stale reads。如果需要 up-to-date data 的 operations 由 eventually consistent reads 服务，那么应用就存在细微错误。弱一致性模型只有在应用确实能容忍弱保证时才合适，而不应因为简单而成为默认选择。 |
| 跳过实现实验 | 分布式系统是概念理解与能够实现正确系统之间差距最大的学科之一。阅读 Raft 并在概念上理解 Raft，与在 failure injection 下正确实现 Raft，是两回事。实现过程会揭示阅读无法显现的 specification 细节：当 leader 有 pending uncommitted entries 时，收到来自 higher-term leader 的消息到底应该怎样？Specification 会回答这个问题；直觉经常回答错。 | 完成 MIT 6.5840 Raft lab 或等价实验。这个 lab 的测试套件专门通过注入那些会暴露常见实现错误的失败条件来测试实现。通过测试的实现不一定正确，但失败的实现一定不正确，而这些失败本身很有信息量。 |