分布式系统-MIT6.824

本文为作者跟随肖宏辉老师学习MIT公开课6.824分布式系统时做的笔记

另外还有电子书

github仓库

1-介绍

驱动力

• 人们需要获得更高的计算性能
• 提供容错（tolerate faults）
• 一些问题天然在空间上是分布的
• 限制出错域

挑战

• 并发编程和各种复杂交互带来的问题，以及时间依赖的问题
• 局部错误
• 如何提高分布式系统的性能

四次编程实验

• 实现MapReduce
• 实现Raft算法，通过复制复制和出现故障时自动切换来让系统容错
• 使用Raft实现可以容错的KV服务
• 分片式KV服务，将数据在多个服务器上做了分区，来实现并行的加速

基础架构的类型主要是存储，通信（网络）和计算

构建分布式系统的工具

• RPC（Remote Procedure Call）。
• 线程
• 并发控制，如锁

可扩展性（Scalability）

可扩展性（Scalability）：通过增加机器的方式来实现扩展，即提升性能或吞吐量。通常可扩展性不是无限的，当一个系统的某一部分扩展到一定程度，瓶颈会转移到其他部分，比如web服务器扩展到一定程度后瓶颈转移到数据库

可用性（Availability）

可用性（Availability）：对应用开发人员屏蔽和掩盖错误，在特定的故障范围内，系统仍然能够提供服务

自我可恢复性（recoverability）：出现问题，服务停止工作，在修复之后系统仍然可以正常运行。这是一个比可用性更弱的需求

为了实现这些特性，有很多工具。其中最重要的有两个：

• 非易失存储（non-volatile storage，类似于硬盘）
• 复制（replication）

一致性（Consistency）

强一致（Strong Consistency）：get请求可以得到最近一次完成的put请求写入的值

弱一致（Weak Consistency）：不保证get请求可以得到最近一次完成的put请求写入的值

强一致代价很高，需要大量的通信才能得到一个数据，所以，常常使用弱一致系统，只需要更新最近的数据副本，并且只需要从最近的副本获取数据

MapReduce基本工作方式

MapReduce是由Google设计，开发和使用的一个系统，相关的论文在2004年发表

MapReduce的思想是：只需要写简单的Map函数和Reduce函数，不需要知道任何有关分布式的事情，MapReduce框架会处理剩下的事情

1. 假设有一些输入，这些输入被分割成大量的不同的文件或者数据块
2. 启动时，查找Map函数，为每个输入文件并行运行Map函数，Map函数的输出是一个key-value对的列表（中间输出）。一个最简单的MapReduce Job：单词计数器，key为单词，value为数量
3. 搜集所有的key-value对，并运行Reduce函数

一些术语

• Job。整个MapReduce计算称为Job
• Task。每一次MapReduce调用称为Task，map task和reduce task

可以将Reduce函数的输出再传递给Map函数

3-GFS

分布式存储系统的难点

将数据分割放到大量的服务器上，并行的从多台服务器读取数据，这种方式称之为分片（Sharding）

服务器越多越容易出错，我们需要一个自动的容错（fault tolerance）系统

实现容错最有用的一种方法是使用复制（replication），只需要维护2-3个数据的副本，当其中一个故障了，可以使用另一个

复制导致不一致的问题（inconsistency）

一种分布式存储错误的设计

写操作在每个服务器上都执行，读操作只在一个服务器执行

由于网络延迟可能会出现不一致

GFS的设计目标

Google的目标是构建一个大型的，快速的文件系统，是全局有效的，各种不同的应用程序都可以从中读取数据

为了获得大容量和高速的特性，每个包含了数据的文件会被GFS自动的分割并存放在多个服务器

希望有自动的故障修复

一些非目标特征：

• 没有将副本保存在世界各地，因为实现起来难，GFS局限在一个数据中心
• GFS并不面向普通的用户
• GFS在各个方面对大型的顺序文件读写做了定制

4-VMware FT

6,7-raft1

脑裂（Split Brain）

MapReduce，GFS和VMware FT都有一个共性：它们需要一个主节点（Primary），存在单点故障（Single Point of Failure）

使用单点的原因是，我们需要避免脑裂（Split-Brain）

脑裂（Split-Brain）：在分布式系统中，由于网络分区或通信故障等原因，导致系统中的节点无法相互通信，从而形成了多个独立的子系统，每个子系统都认为自己是唯一有效的系统

过半票决（Majority Vote）

当网络出现故障，将网络分割成两半，网络的两边独自运行，且不能访问对方，这通常被称为网络分区

可以正确的实现能够自动完成故障切换的系统，关键点在于过半票决（Majority Vote）

过半票决系统的第一步在于，服务器的数量要是奇数，在任何时候为了完成任何操作

你必须凑够过半的服务器来批准相应的操作，因为如果网络存在分区，必然不可能有超过一个分区拥有过半数量的服务器

过半是指所有服务器数量的一半，而不是当前开机服务器数量的一半

如果系统有 2 * F + 1 个服务器，那么系统最多可以接受F个服务器出现故障，仍正常工作

通常这也被称为多数投票（quorum）系统

Raft 初探

Raft会以库（Library）的形式存在于服务中

每个服务的副本由两部分组成：应用程序代码kv数据库（上层）和Raft库（下层）

应用程序代码接收RPC或者其他客户端请求；不同节点的Raft库之间相互合作，来维护多副本之间的操作同步

Key-Value数据库需要对Raft层进行函数调用，来传递自己的状态和Raft反馈的信息

Raft本身也会保持状态，其中，最重要的状态就是Raft会记录操作的日志

客户端是一些外部程序代码，它们使用服务，且不知道，也没有必要知道，交互的是一个多副本服务

客户端会将请求发送给当前Raft集群中的Leader节点对应的应用程序，这里的请求就是应用程序级别的请求，例如一个访问Key-Value数据库的请求，可能是Put也可能是Get。Put请求带了一个Key和一个Value，更新Key-Value数据库中，Key对应的Value；而Get向当前服务请求某个Key对应的Value

Log 同步时序

对于put请求：客户端将请求发送给Raft的Leader节点，Leader应用程序将来自客户端的请求对应的操作向下发送到Leader的Raft层，把这个操作提交到多副本的日志（Log）中，Leader的Raft层和其他节点的Raft层交互，直到过半的Raft节点（包括自己）报告已经将操作加入到自己的日志中，Leader的Raft层才会通知Leader的应用程序可以真正的执行这个操作了。Leader的应用程序执行完操作后，Leader的Raft层通知每个副本节点的Raft层，执行这个操作

对于Get请求：直接返回value即可

日志（Raft Log）

• Log是Leader用来对操作排序的一种手段
• Log是副本节点用来存放临时操作的地方
• Leader通过Log确定需要重传的操作
• Log用来持久化存储操作，重启的服务器可以依赖这些操作来恢复状态

Raft没有同步Leader和其他节点操作执行速度的机制，所以需要一些通信来同步操作执行速度，类似于TCP的滑动窗口，告诉Leader，副本执行到哪一步了

应用层接口

• 应用程序调用Start函数：参数是客户端请求，Raft层存储Log并与其他副本的Raft层交互（AppendEntries）
• applyCh：Raft层通知应用程序其他副本已经添加了Log，以go channel种的消息（操作）来实现
• ApplyMsg：commit之后，发送给副本消息来执行操作，包含请求（command）和对应的Log位置（index），所有的副本都会收到这个ApplyMsg消息

Raft会最终强制不同副本的Log保持一致。或许会有短暂的不一致，但是长期来看，所有副本的Log会被Leader修改，直到Leader确认它们都是一致的。

Leader选举（Leader Election）

Raft生命周期中可能会有不同的Leader，它使用任期号（term number）来区分不同的Leader

Followers（非Leader副本节点）不需要知道Leader的ID，它们只需要知道当前的任期号

每一个任期最多有一个Leader

每个Raft节点都有一个选举定时器（Election Timer），每次收到Leader的消息会重置定时器，当前服务器定时器结束时认为Leader已经下线并开始新的选举。

选举的流程

• 当前服务器增加任期号（term number）
• 当前服务器发出请求投票（RequestVote）RPC给所有Raft节点，自己一定会投给自己，相当于只发送了N-1个节点
• 当自己得票超过半数则向其他服务器发送心跳通知其他服务器我赢得了选举

Leader没有故障也可能会有新的选举，比如网络很慢，丢了几个心跳。这种时候会发生网络分区，分两种情况：

1. 旧Leader所在分区有过半数服务器，旧Leader不受影响。其他分区无法完成Leader选举因为没有过半数服务器
2. 旧Leader所在分区没有过半数服务器，旧Leader无法完成AppendEntries将Log写入超过半数服务器，所以无法commit操作。其他网络分区如果有超过半数的服务器则选出新的Leader并正常运行，否则一直卡住，但不会出现错误操作

选举定时器（Election Timer）

任何一条Leader发出的消息都会重置所有Raft节点的选举定时器（心跳或者其他的AppendEntries消息）

如果一次选举选出了0个Leader，这次选举就失败了，这时什么事也不会发生。比如候选人们几乎同时参加竞选，并分割了选票（Split Vote），接下来它们的选举定时器会重新计时，这个过程可能持续

Raft不能完全避免分割选票（Split Vote），但是可以通过为选举定时器随机的选择超时时间来使得这个场景出现的概率大大降低

选举定时器的超时时间：下限需要至少大于Leader的心跳间隔，最好是心跳间隔的几倍。上限只决定恢复需要多久，在故障频率较小的时候影响不大

不同选举定时器的超时时间的差至少需要大于RPC所需的RTT

可能的异常情况

只要Followers还能处理，它们就会全盘接收Leader在AppendEntries中发送给它们的内容，并加到本地的Log中，之后再收到来自Leader的commit消息，在本地执行请求

举例是，每一列为Log的一个槽位，即一条Log，值为该Log的任期值

新Leader执行的操作：

• 本地未提交Log的可以直接丢弃（这里老师举的例子没有丢弃）
• 本地已提交Log必须保留
• 保证其他副本Log一致（见日志恢复）

日志恢复（Log Backup）

1. 新Leader收到客户端请求时发送AppendEntries消息给其他服务器，包含前一个槽位的位置prevLogIndex和前一个槽位的任期号PrevLogTerm两个字段。当这两个值不匹配副本最新的已提交槽位时返回false给Leader。
2. 新Leader会记录每个副本的nextIndex，且在刚成为Leader时将每个副本的nextIndex初始化为和自己一样，比如自己成为Leader时最新的槽位为12，那么就会把其他副本和自己的nextIndex设置为13。当收到false时将副本的nextIndex减1，然后再发送AppendEntries消息给回自己false的副本，prevLogIndex为该副本nextIndex-1，且该消息带有从nextIndex到最新的槽位的所有Log。
3. 副本接收到会再次匹配prevLogIndex和PrevLogTerm，如果匹配则将其拷贝到自己的Log里面，否则返回false重复2，3

如果客户端发送请求之后一段时间没有收到回复，它应该重新发送请求

选举约束（Election Restriction）

节点只能向满足下面条件之一的候选人投出赞成票：

• 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号
• 候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

快速恢复（Fast Backup）

让Follower返回足够的信息给Leader，这样Leader可以以任期（Term）为单位来回退，而不用每次只回退一条Log条目，携带3个额外的信息

• XTerm：Follower中与Leader冲突时，preLogTerm对应槽位的任期号，没有Log则为-1
• XIndex：Follower中，XTerm不为-1时，任期号为XTerm的第一条Log条目的槽位号
• XLen：Follower中，XTerm为-1时，XLen表示空白的Log槽位数

Leader收到回复后：

• XTerm不为-1时，将副本对应的nextIndex更新为Max(XIndex,自己的XTerm任期的最新Log的槽位+1)
• XTerm为-1时，将副本对应的nextIndex更新为旧nextIndex-XLen

持久化（Persistence）