一门分布式系统课
简介
这里的内容主要来我给某大学上的分布式系统课程大纲。 出于课时和难度的考虑，没有讲太多的概念和内容，只选择了一些基本概念来介绍。 其中，中心的是共识协议，围绕着共识协议的工作模型，介绍分布式系统的概念，围绕着测试共识协议，介绍系统质量保障技术。 以尽量少的内容，让学生对分布式系统有直观的了解和接触，结合理论与实践，为以后的深入学习打下基础。
具体分成三个部分。 第一部分介绍分布式系统概念和模型，然后介绍go语言，学习用go语言实现系统； 第二部分着重介绍共识协议，这一部分主要是同学们自己读论文，照着论文实现共识，最后构建一个基于共识的高可用键值存储； 第三部分介绍一些前沿的系统质量保障手段，要求学生把这些技术应用起来，测试和验证自己实现的系统。
分布式系统概念和模型
1. 分布式系统简介
内容：
- 分布式系统概念
- 为什么需要它
- 它的问题、挑战
阅读
书
- Distributed Systems, Concepts and Design(Chapter1)
- Distributed Systems An Algorithmic Approach(Chapter1)
2. 系统模型
内容：
- 基于消息： 同步 异步
- 基于共享 同步 异步
- 抽象系统模型： 状态机 + 图
- 物理系统模型： 线程，进程，事件，网络通信，客户端/服务器，消息/RPC
- go编程
- A tour of the Go programming language
- The Go Programming Language and Environment
- Patterns and Hints for Concurrency in Go
阅读
报告
- Event VS Thread: Why Threads Are A Bad Idea(for most purposes)
理解基于事件的处理，并发=/=多线程（进程）
论文
- Message Passing VS RPC: A Note on Distributed Computing
关注二者优缺点，设计系统时做出你的选择
- I/O automata model: An Introduction to Input/Output Automata
I/O automata概念，了解如何用它描述算法、系统
书
- Notes on Theory of Distributed Systems(Chapter2, Chapter16, APPENDIX J)
- Distributed Systems, Concepts and Design(Chapter2-7)
- Distributed Systems An Algorithmic Approach (Chapter2~5)
- Distributed Algorithms(Chapter2, Chapter8)
- Unix Network Programming
3. 实践 1
内容：
构建基于消息(RPC)的分布式系统
- 使用go，或你熟悉的其它语言
- 用go的理由，它足够简单，非常适合写分布式系统 n个节点（N1, N2, N3，… ，Nn) 复制系统
- N1节点不断地从标准输入接收数据，N1持久化接收到的输入数据
- N1节点不断地发送它的持久化数据到其它节点（ N2，N3 ， … ， Nn）
- N2，N3 ， … ， Nn节点在收到数据后，如果没有这项数据，将其持久化到本地
- 持久化的数据不能丢失
- 最终，所有节点的数据将都和N1一致
模型
- 任意两个节点间的消息可能丢失，乱序，重复，延迟（异步模型）
- 任意节点可能崩溃后重启（崩溃、恢复模型）
高可用系统
4. 复制和共识
内容：
- 复制状态机
- 容错
- 共识
- CAP theorem （CP VS AP）
阅读：
论文
理解状态机（重要），关于时间和时钟的部分如果看不懂可略过
扩展阅读
复制状态机
理解CAP，“三选二”，“二选一”是什么
书
- Distributed Systems, Concepts and Design(Chapter18)
- Distributed Systems An Algorithmic Approach (Chapter12~13)
5. 共识算法 Raft
阅读：
论文
-
In Search of an Understandable Consensus Algorithm 理解Raft，复制+选举
-
Raft Thesis， 可选， Consensus: Bridging Theory and Practice 更多的Raft细节
-
Analysis of Raft Consensus 理解Raft正确性
Raft资料
案例：
ETCD
6.实践2
内容
-
构建一个高可用key value存储，可以基于实践1部分codebase
-
n个节点（N1, N2, N3，… ，Nn， n固定) 复制系统，每个节点都是一个key value存储 客户端通过连接到节点读写数据； 当半数节点（n/2）停止服务时，系统仍能提供服务（fairness），并且保持数据的一致； 选用一种共识算法实现，实现复制和选主，不需要节点管理（不需要考虑增减节点），不需要实现linearizability（不需要考虑读旧值和写入重复命令的问题）
-
注意： 客户端需要容忍失败； key value需要持久化； 允许参考开源程序，但要表明对应哪一部分是自己的工作，以及为什么你觉得可以用它而不担心它的问题，用一些办法测试和验证它的正确（测试和验证部分，实践 2 cont，使用开源对这一部分的要求会相应地增高）
目标
熟悉高可用系统和共识协议开发
7. 共识算法 Paxos
阅读 ：
论文
单Value Paxos
要点: 多Value Paxos
理解Paxos和Raft差异
书
- Notes on Theory of Distributed Systems(Chapter12, Chapter13, Chapter14)
案例：
- Tencent PaxosStore
系统质量保障
8. 系统测试和验证方法
内容
- 确定性模拟
- 随机化方法
- 形式化方法
阅读：
论文
-
Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems Testing, 测试的重要关注点
-
FoundationDB: A Distributed Key Value Store Deterministic Simulation, 着重理解模拟，确定性
-
Why is random testing effective for partition tolerance bugs?
了解随机化方法
- Verdi: A Framework for Implementing and Formally Verifying Distributed Systems
- How formal methods helped AWS to design amazing services
- eXtreme Modelling in Practice
- Model Checking Guided Testing for Distributed Systems
了解形式化方法，模型检验
其它资料：
- Specifying Systems（Chapter1~8）
- Testing a Single-Node, Single Threaded, Distributed System Written in 1985 By Will Wilson Colin Scott, Fuzzing Raft for Fun and Publication
- jepsen “Simulation Testing” by Michael Nygard
- Golang Fuzz https://go.dev/doc/security/fuzz/
- Leslie Lamport’s The TLA+ Video Course
- Raft TLA+ Specification
9. 实践 2（cont）
内容
为高可用key value store找deep bug
- 说明发现了什么deep bugs，画出它们的事件状态转换图
- 说明是用什么方法发现它们的（参考第8部分）
目标
掌握一定的测试/验证系统/协议正确技术 deep bug？
要经历多个特定的连续异步事件（消息重复/丢失/乱序，崩溃/重启）才能发生的bug
参考书
- Distributed Algorithms