MIT6.824分布式系统笔记

前段时间在线看完了MIT 6.824的分布式系统课程，Robert Morris教授在课程里列举了大量的工业界实现，理论结合实践，水平是真的高。学习过程中也消除了之前的很多疑惑，比如线性一致性的定义、多数投票的动机等等，有很多恍然大悟、原来如此的时刻。总之，对于能学习到这么一门课程，是由衷的感激。

本文主要针对课程中的自认为重要的点记录下来，以进一步吸收巩固所学知识。

相关资源:

1. Youtube课程
2. 国内搬运课程
3. schedule

下面是笔记正文，针对课程记录。

简介（Introduction）

分布式系统的驱动力

• parallelism, 并行计算以达到高性能
• fault tolerance，容错性
• physical，一些天然的原因导致系统是物理分布的，比如银行间转账
• security/isolated，代码隔离，限制出错域，保证安全性

分布式系统的挑战

• 并发编程，复杂交互
• 部分失败
• 性能，并不是加更多的机器就一定可以达到更多的性能

分布式系统的三个抽象

• 存储
• 计算
• 通信

分布式系统的话题

• scalability，关注的是性能performance，可以通过增加机器来提高系统性能
• fault tolerance，关注的是错误，系统可以容忍错误的发生
  • availablity。可用性
    • 非易失性存储
    • replicator，副本机制
  • recoverability，自愈性
• consistency，关注的是数据一致性
  • 强一致，代价高昂
  • 弱一致，牺牲一致性以提高性能

GFS

分布式存储的设计难点

设计难点循环：performance -> sharding -> fault -> tolrance -> relication -> inconsistency -> consistency -> performance

多副本设计的一个bad design

• 评价标准只能从产生的结果来判断系统的输出是一致性还是非一致。
• 客户端双写模型是最糟糕的设计，服务器无法保证写入顺序。

GFS设计目标

• 大容量、快速的文件系统
• 全局的，应用共享
• 文件分割
• 自动恢复
• 单数据中心
• 内部使用，不对外开放
• 大型文件顺序读写，关注吞吐量

GFS架构

• 单master节点和多个chunk server节点，master节点保存了文件名和存储位置的对应关系，chunk server存储具体数据，每一个数据会在多台chunk server上备份
• master数据
  • 文件名到chunk handler数组的映射（需要持久化），每个大文件拆分多个为64MB大小的块,可以保存在不同的chunk节点中
  • chunk handler包含：
    • chunk server列表
    • 当前的版本号（需要持久化）
    • primary chunk server，写入操作都在primary上顺序处理，保证写入顺序
    • primary租约过期时间
  • 操作日志以及检查点（需要持久化）

GFS读过程

1. 客户端发送文件名和偏移量到master
2. master返回对应的chunk Handle和服务器列表
3. 客户端选择一个网络上最近的服务器读取数据，可能会读到旧数据

GFS写过程

• 客户端请求master节点
• master确定primary
  1. 找到持有最新版本的副本
  2. 挑选一个作为primary, 其余作为secondary
  3. 增加版本号
  4. 告知副本节点版本号，并通过租约机制告知primary租约期内会是primary节点，避免租约内有两个primary
  5. 持久化版本号
  6. 返回所有副本节点给客户端
• 客户端将数据写入到所有副本的临时位置，得到响应通知primary
• primary顺序执行文件追加，并通知secondary可以追加到文件中，如果全部成功返回给客户端成功，否则返回失败。

GFS一致性

• 多个副本不保证一致，客户端可以从任意一个副本读，会读到不一致的数据

GFS缺陷

• master存在单点问题，随着规模变大，数据量和请求也越来越多
• 副本不一致导致应用程序很难处理
• master没有自动恢复机制，需要人工干预

主从复制（Primary-Backup Replication）

复制（repliaction）

• 可以解决fail-stop错误。fail-stop是一种故障类型，指如果某些东西出了故障，那么会单纯的停止运行。
• 不能处理软件中的bug和硬件设计中的缺陷
• 多个副本之间并不是完全独立，很可能相关，比如
  • 采购同一批有缺陷的计算机
  • 在同一个数据中心
• 并不能提升性能，只能用来容错fault-tolerance，这是一个经济问题。

复制方式

• 状态转移（State Transfer)，是指Primary将自己的完整状态，拷贝并发送给其他backup

• 复制状态机（State Machine Replication），客户端将操作发送给Primary，Primary依次将操作发送到其他backup，所有副本都有同样的起始状态、执行操作、操作顺序，而且是确定性的。

  • 复制状态机基于这个事实：我们想复制的大部分的服务都有一些确定的内部操作，而不确定的部分是外部的输入。通常来说，人们倾向于使用复制状态机的原因是外部操作或者事件比服务的状态要小。
  • 随机操作在复制状态机会怎么处理？比如获取系统当前时间或者机器ID，一般Primary会将随机操作的结果复制到backup。
  • 实现复制状态机需要考虑的一些问题：
    • 什么状态需要复制？
      • 应用程序的状态，比如数据库表，效率高，需要应用程序参与
      • 机器级别的状态，比如寄存器和内存，效率低但更通用
    • 复制过程中，primary必须等待backup吗？
      • 几乎每一个复制系统都会面临这个问题：在某个时间点，Primary必须要停下来等待Backup。
    • 什么时候需要切换到backup？
      • primary故障的时候
    • 切换过程中异常对外可见吗？
      • 客户端必然会察觉到异常，需要对异常进行处理和恢复
    • 如何添加一个新的副本并尽快提供服务？
      • 通过状态转移，比如检查点和快照

VMware FT

• VMware FT是对虚拟机的复制，其独特之处在于，是从机器级别实现复制，复制底层的寄存器和内存，可以不关心在机器上运行什么样的软件。
• 非确定性事件
  • 怪异指令，primary会拦截这些指令并将结果复制给backup，比如：
    • 随机数生成器
    • 获取系统事件
    • 获取mac地址
  • 多核CPU,VMware FT不考虑多核场景，这种状态也没法复制
• VMware FT论文中将Primary到Backup之间同步的数据流的通道称之为Log Channel，所有的事件都需要通过Log Channel，从Primary同步到Backup
• 重复输出
  • 对于任何有主从切换的复制系统，基本上不可能将系统设计成不产生重复输出。当出现主从切换时，切换的两边都有可能生成重复的输出，这意味着复制系统的客户端需要一种重复检测机制。VMware FT可以通过TCP来完成重复检测，因为主从的TCP序列号都是一致的。否则，可能需要使用应用程序级别的序列号。
• Test-and-Set服务
  • 避免脑裂
  • Test-and-Set是个单点故障。

Raft

脑裂（Split Brain）

• GFS、VMvareFT等多副本系统，存在一个共性：它们需要一个单节点来决定在多个副本中谁是Primary。
• 使用单节点的好处是，它不可能否认自己。因为只有一个节点，它的决策就是整体的决策。缺点是，它本身又是一个单点故障。
• 使用单点的原因是可以避免脑裂（Split-Brain）。当网络出现故障，将网络分割成两半，网络的两边独自运行，且不能访问对方，这通常被称为网络分区(Network Partition)。
• 问题的关键是服务器不能识别宕机和网络分区，因为他们的症状表现都是一样的。

多数投票（Majority Vote）

• 多数投票可以用来解决网络分区的问题
• 服务器的数量需要是奇数，而不是偶数
• 必须凑够过半的服务器来批准相应的操作。这里的过半总是相对于服务器的总数来说，而不是当前在线服务器数量的一半。这背后的逻辑是，如果网络存在分区，那么必然不可能有超过一个分区拥有过半数量的服务器。
• 隐含的特性是对于一系列需要多数投票的操作来说，任意两组投票的服务器必然会有重叠。比如raft的两次leader选举，第二次必然知道第一次的选举信息，日志提交也类似。
• 如果系统有2 * F + 1 个服务器，那么系统最多可以接受F个服务器出现故障，仍然可以正常工作。
• 通常也被称为法定投票系统（Quorum）

接口设计

• Raft以库的形式存在于服务中。基于Raft的多副本服务由两部分组成：应用程序代码和Raft库。应用程序代码接收客户端请求，不同节点的Raft库之间相互协作完成多副本的任务。
• Raft设计主要包括两大部分：
  1. leader选举，requestVote接口
  2. 日志同步，appendEntries接口

leader选举

• 为什么需要一个leader？
  • 保证所有的副本以相同的顺序执行相同的操作。实际上也可以不用，比如paxos，只要多数投票即可。
  • 通常情况下，如果服务器不出现故障，有一个leader的存在，会使得整个系统更加高效。
• 为什么leader需要任期号(term)？
  • 确保一个任期至多有一个leader，节点只选举最新任期的leader而不是旧任期的leader，没有任期号的话区分不了新旧leader。
  • 只有当前任期的leader才可以发出appendEntries消息。
• 选举约束
  • 投票给拥有更高任期号记录的候选人。背后的意思是这个候选人接收到了任期高的旧leader的记录。
  • 如果候选人都拥有最高的任期号，那么投票给拥有更多记录的候选人。背后的意思是候选人接收到了更多的旧leader的记录。
  • 为什么不采用拥有最长日志的候选人作为leader？
    • 实现不了，节点不知道谁拥有最长的日志。除非询问所有节点，但这种方案在网络分区的情况下要么全部不可用，要么会出现多个leader。
    • 多数投票可以让节点知道需要的最新的信息，并往前递进。
• 选举定时器（election timer）
  • 每个节点都有一个选举定时器，如果定时器时间耗尽之前，节点没有收到任何当前leader的消息，这个节点会认为leader已经下线，并自增当前任期号开始新一轮选举
    • 虽然会造成无意义的选举，但是保证了安全性。
    • 开始新一轮的投票并不意味着旧leader已经宕机。
  • 随机选举超时（randomized election timeouts）
    • Raft不能完全避免分割选票（Split Vote），但是可以通过随机选举超时机制大大降低出现的概率。
    • 选举定时器的超时时间下限要大于若干次leader的心跳间隔, 随机选取的区间既要能大于完成一次选举的时间，也要尽量小可以快速恢复避免长时间停机。
• 节点如何意识到leader已经产生？
  • leader收到多数节点投票
  • 其他节点收到leader的带有更高任期号的新消息（appendEntries或者heartbeat）

Raft日志

• 日志提交流程
  • 一条日志记录在多数节点写入完成后通知leader，再由leader返回给客户端，这是第一阶段提交。
  • 第二阶段提交可以在下次客户端请求顺带进行commit，优化写入流程。如果客户端请求不是很频繁，也可以通过心跳进行commit。
  • 如果第二段提交前leader宕机也没有关系，因为返回给客户端成功的记录一定是写入到过半节点上的，在发起新一轮leader选举时，新的leader会知道最新的commit记录是哪一条。所以raft论文中commitIndex不必要持久化，因为一轮投票就可以知道当前的commitIndex
• Log是leader用来对操作排序的一种手段。这对于复制状态机而言至关重要，所有副本不仅要执行相同的操作，还需要用相同的顺序执行这些操作。实际上，Log是一些按照数字编号的槽位，槽位的数字表示了leader选择的顺序。
• Log可以让leader对某些日志记录进行重传，如果follower因为网络原因或者其他原因短时间离线了导致丢了一些消息，leader需要向follower重传丢失的日志记录。
• Log是follower存储临时操作的地方，follower不确定这些操作是否被commit了，这些操作可能会被丢弃。
• Log可以帮助服务器在重启时恢复状态。
• 流控机制，follower写入的速度可能跟不上leader，需要额外的机制进行流控。这点raft论文没有提及。

日志恢复

• 在日志复制过程中，可能出现任何异常，导致follower的日志和leader的日志不一致
• Leader使用了一种备份机制来探测Followers的Log中，第一个与Leader的Log相同的位置。在获得位置之后，Leader会给Follower发送从这个位置开始的，剩余的全部Log。经过这个过程，所有节点的Log都可以和Leader保持一致。
• 为什么Raft系统可以安全的删除这条记录？毕竟这条记录是真实的客户端请求，删除之后意味这某个相关的客户端请求也随之被丢弃了。
  • 首先，如果leader已经得到了多数follower的回应，并返回给客户端写入成功，这个时候就算leader宕机，写入的日志是不会被删除的，原因是选举约束，新一轮的leader必然保留了之前写入的日志。
  • follower上与leader不一致的日志，必然是可以被安全删除的，因为与leader不一致的日志，一定是leader之前没有得到过半响应的，也就不会返回给客户端成功。
  • 另外，多数follower写入的日志一定会被保留的吗？不一定，例子可以参见raft论文figure8，多数follower写入的日志的日志也可能被删除，但这个删除是安全的，因为raft不可能回复过客户端成功，这个状态只是一个中间状态。
• 快速恢复
  • 日志恢复机制中，如果Log有冲突，leader每次会回退一条Log条目。如果不一致的日志太多，通过多轮RPC回退，会有性能问题。
  • 为了能够更快的恢复日志，可以让follower返回足够的信息给leader，这样leader可以以任期为单位来回退，而不用每次只回退一条Log条目。

日志压缩和快照（Log compaction and snapshots）

• 对于一个长期运行的系统，Log会持续增长，浪费存储。另外如果一个服务器重启了，应用如果需要从头开始执行海量Log来重建自己的状态会很浪费时间。
• Raft通过快照来解决这个问题。快照背后的思想是，要求应用程序将其状态的拷贝作为一种特殊的Log条目存储下来。
• 对于大多数的应用程序来说，应用程序的状态远小于Log的大小。
• 当Raft认为它的Log将会过于庞大，例如大于1MB，10MB或者任意的限制，Raft会要求应用程序在Log的特定位置，对其状态做一个快照。
• leader做快照时可能会丢弃follower在日志恢复过程中需要的Log。解决方法是通过InstallSnapshot告知follower之前的快照。

持久化

• 为了节点宕机之后可以快速恢复自己的状态，某些状态是需要持久化的，有且仅有三个数据是需要持久化存储的：
  • Log
    • 唯一记录了应用程序状态的地方，而且新的leader需要知道哪些日志被提交了。
  • currentTerm
    • 保证任期是单调递增的，保证一个任期最多只有一个leader。
  • votedFor
    • votedFor保存当前任期投票给了谁，节点任期内只能投票一次，否则可能会导致两个leader的出现。
• 同步持久化操作的代价很高
  • 一方面可以用性能更高的存储
  • 另一方面可以使用批量更新
• 为什么服务器重启时，commitIndex、lastApplied、nextIndex、matchIndex，可以被丢弃？
  • 综合考虑了Raft的简单性和安全性。
  • 之所以这些数据是非持久化存储的，是因为leader可以通过检查自己的Log和发送给follower的AppendEntries的结果，来发现哪些内容已经commit了。

线性一致性（Linearizable consistency）

• 对于正确性的判断方法
  • 首先，看待一致性要从客户端响应结果上来看，如果请求的区间有重合，那么系统可以在区间的任何时间点执行请求，所以系统可能以任何的顺序执行这些请求。
  • 正确的定义就是线性一致（Linearizability）或者说强一致（Strong consistency）。一个服务是线性一致的，那么它表现的就像只有一个服务器，并且服务器没有故障，这个服务器每次执行一个客户端请求。
• 线性一致的解释
  • 线性一致是观察系统的执行历史。通过观察执行历史，可以构建一个序列，满足：
    • 序列中的请求的顺序与实际时间匹配(请求没有重合的操作)
    • 每个读请求看到的都是序列中前一个写请求写入的值，对于读请求不允许返回旧的数据，只能返回最新的数据
  • 我们要么需要构造一个序列来证明线性一致，要么需要构造一个带环的图来证明非线性一致
  • 线性一致的另外一个条件是，对于整个请求历史记录，只存在一个序列，不允许不同的客户端看见不同的序列。这里只能有一个序列，所有的客户端必须看到相同的序列。
  • 线性一致的定义是有关历史记录的定义，而不是系统的定义。所以我们不能说一个系统设计是线性一致的，我们只能说请求的历史记录是线性一致的。
  • 客户端的某个读请求时间跨度可能非常长，期间如果有其他写请求，读请求是可能读到旧数据，但这个一样满足线性一致的定义，因为这个时候客户端的请求是并发的有重合的。

Zookeeper

• 定位
  • 与Raft库定位不同，zookeeper可以被认为是一个通用的协调服务，帮助人们构建分布式系统。
  • 可扩展，通过增加服务器来提升读性能
• 一致性
  • 写请求是线性一致的
  • FIFO客户端序列。任何一个客户端的请求，都会按照客户端指定的顺序来执行。
    • 读请求不保证读到最新的数据，读请求的线性一致只对单个客户端有效。实现方式是通过zxid，副本会返回zxid之后的数据。
  • 为什么zookeeper可以这样弱化一致性？
    • 写是线性一致的
    • 读针对单个客户端是一致的
    • 最重要的一点是sync操作可以重新让读也变成线性一致
• sync同步
  • 本质上是一个写请求，可以让客户端读到最新的数据。符合了FIFO客户端请求序列，因为读请求必须至少要看到同一个客户端前一个写请求对应的状态。
• mini-transaction
  • zookeeper的setdata接口可以指定version版本，通过CAS操作原子更新数据
• 节点类型
  • Regular znodes。永久性节点，除非被删除。
  • Ephemeral znodes。临时性节点，如果Zookeeper认为创建它的客户端挂了，会主动删除这种类型的znodes。
  • Sequential znodes。顺序性节点。当有多个客户端同时创建Sequential文件时，Zookeeper会确保这里的数字不重合，同时也会确保这里的数字总是递增的。
• 为什么要用zookeeper实现锁？
  • 通过Zookeeper实现的锁就不太一样。如果持有锁的客户端挂了，它会释放锁，另一个客户端可以接着获得锁，所以它并不确保原子性。
  • 应用考虑清理残留数据
  • 保护一些不重要的数据
  • 选举master

参考文献

1. Youtube课程
2. 国内搬运课程
3. schedule
4. GFS
5. faults and fault tolerance
6. State Transfer
7. State Machine Replication
8. VMware FT
9. Single point of failure
10. Split-Brain
11. Network Partition
12. Raft
13. Quorum
14. zookeeper

• 上一篇 使用Reactor进行反应式编程
• 下一篇 反应式网络库Reactor Netty的回压设计