MIT6.824部分学习

MIT6.824部分学习
W3nYui整体阅读这份笔记,简单了解分布式以及一些架构,关于论文阅读部分没有整理,只作为架构知识点去看。
关于论文的总结、阅读可以看这篇博客
Lecture 1
为什么需要 分布式系统
- 利用分布式,获得更高的计算性能(并行运算、CPU、内存、磁盘)
- 提供容错,如果一台出现问题,可以切换到另一台服务器接手项目。
- 一些问题天然在空间上是分布的。例如银行转账,我们假设银行A在纽约有一台服务器,银行B在伦敦有一台服务器,这就需要一种两者之间协调的方法。
- 构建分布式系统来达成一些安全的目标。比如有一些代码并不被信任,但是又需要和它进行交互,因此可以通过一些特定的网络协议通信,从而限制了出错域。
分布式系统的挑战
- 并发问题:整体系统内存在多个部分,这些部分有在并发执行,因此会遇到并发编程和各种交互带来的复杂问题,以及时间依赖问题(同步、异步)。
- 局部错误:分布式系统有多个组成部分,再加上计算机网络,你会遇到一些意想不到的故障。如果你只有一台计算机,那么它通常要么是工作,要么是故障或者没电,总的来说,要么是在工作,要么是没有工作。而由多台计算机组成的分布式系统,可能会有一部分组件在工作,而另一部分组件停止运行,或者这些计算机都在正常运行,但是网络中断了或者不稳定。所以,局部错误也是分布式系统很难的原因。
- 性能组合:人们设计分布式系统的根本原因通常是为了获得更高的性能,比如说一千台计算机或者一千个磁盘臂达到的性能。但是实际上一千台机器到底有多少性能是一个棘手的问题,这里有很多难点。
分布式的抽象
基础架构的类型主要是存储,通信(网络)和计算。对于存储和计算,我们的目标是为了能够设计一些简单接口,让第三方应用能够使用这些分布式的存储和计算,这样才能简单的在这些基础架构之上,构建第三方应用程序。它看起来就像一个非分布式存储和计算系统一样,但是实际上又是一个有极高的性能和容错性的分布式系统。
在构建分布系统时,使用了很多的工具,例如:
- RPC(Remote Procedure Call)。RPC的目标就是掩盖我们正在不可靠网络上通信的事实。
- 线程。这是一种编程技术,使得我们可以利用多核心计算机。对于本课程而言,更重要的是,线程提供了一种结构化的并发操作方式,这样,从程序员角度来说可以简化并发操作。
- 锁。因为我们会经常用到线程,我们需要在实现的层面上,花费一定的时间来考虑并发控制,比如锁。
性能问题
可拓展性(Scalability)
通常来说,构建分布式系统的目的是为了获取人们常常提到的可扩展的加速。所以,我们这里追求的是可扩展性(Scalability)。
这里说的可扩展或者可扩展性指的是,如果我用一台计算机解决了一些问题,当我买了第二台计算机,我只需要一半的时间就可以解决这些问题,或者说每分钟可以解决两倍数量的问题。两台计算机构成的系统如果有两倍性能或者吞吐,就是我说的可扩展性。
很少有可以通过无限增加计算机来获取完整的可扩展性的场景。因为在某个临界点,你在系统中添加计算机的位置将不再是瓶颈了。这时,你几乎是必然要做一些重构工作。但是只有一个数据库时,很难重构它。而虽然可以将一个数据库拆分成多个数据库(进而提升性能),但是这需要大量的工作。
可用性(Availability)
大型分布式系统中有一个大问题,那就是一些很罕见的问题会被放大。例如在我们的1000台计算机的集群中,总是有故障,要么是机器故障,要么是运行出错,要么是运行缓慢,要么是执行错误的任务。一个更常见的问题是网络,在一个有1000台计算机的网络中,会有大量的网络电缆和网络交换机,所以总是会有人踩着网线导致网线从接口掉出,或者交换机风扇故障导致交换机过热而不工作。在一个大规模分布式系统中,各个地方总是有一些小问题出现。所以大规模系统会将一些几乎不可能并且你不需要考虑的问题,变成一个持续不断的问题。
因为错误总会发生,必须要在设计时就考虑,系统能够屏蔽错误,或者说能够在出错时继续运行。同时,因为我们需要为第三方应用开发人员提供方便的抽象接口,我们的确也需要构建这样一种基础架构,它能够尽可能多的对应用开发人员屏蔽和掩盖错误。这样,应用开发人员就不需要处理各种各样的可能发生的错误。
这些表述中,有一个共同的思想就是可用性(Availability)。某些系统经过精心的设计,这样在特定的错误类型下,系统仍然能够正常运行,仍然可以像没有出现错误一样,为你提供完整的服务。
比如,你构建了一个有两个拷贝的多副本系统,其中一个故障了,另一个还能运行。当然如果两个副本都故障了,你的系统就不再有可用性。所以,可用系统通常是指,在特定的故障范围内,系统仍然能够提供服务,系统仍然是可用的。如果出现了更多的故障,系统将不再可用。
除了可用性之外,另一种容错特性是自我可恢复性(recoverability)。这里的意思是,如果出现了问题,服务会停止工作,不再响应请求,之后有人来修复,并且在修复之后系统仍然可以正常运行,就像没有出现过问题一样。
为了实现这些特性,有很多工具。其中最重要的有两个:
- 一个是非易失存储(non-volatile storage,类似于硬盘)。这样当出现类似电源故障,甚至整个机房的电源都故障时,我们可以使用非易失存储,比如硬盘,闪存,SSD之类的。我们可以存放一些checkpoint或者系统状态的log在这些存储中,这样当备用电源恢复或者某人修好了电力供给,我们还是可以从硬盘中读出系统最新的状态,并从那个状态继续运行。所以,这里的一个工具是非易失存储。因为更新非易失存储是代价很高的操作,所以相应的出现了很多非易失存储的管理工具。同时构建一个高性能,容错的系统,聪明的做法是避免频繁的写入非易失存储。在过去,甚至对于今天的一个3GHZ的处理器,写入一个非易失存储意味着移动磁盘臂并等待磁碟旋转,这两个过程都非常缓慢。有了闪存会好很多,但是为了获取好的性能,仍然需要许多思考。
- 对于容错的另一个重要工具是复制(replication),不过,管理复制的多副本系统会有些棘手。任何一个多副本系统中,都会有一个关键的问题,比如说,我们有两台服务器,它们本来应该是有着相同的系统状态,现在的关键问题在于,这两个副本总是会意外的偏离同步的状态,而不再互为副本。对于任何一种使用复制实现容错的系统,我们都面临这个问题。
一致性(Consistency)
一致性就是用来定义操作行为的概念。之所以一致性是分布式系统中一个有趣的话题,是因为,从性能和容错的角度来说,我们通常会有多个副本。在一个非分布式系统中,你通常只有一个服务器,一个表单。虽然不是绝对,但是通常来说对于put/get的行为不会有歧义。直观上来说,put就是更新这个表单,get就是从表单中获取当前表单中存储的数据。但是在一个分布式系统中,由于复制或者缓存,数据可能存在于多个副本当中,于是就有了多个不同版本的key-value对。因此就可能会出现版本不一致的现象。
实际上,对于一致性有很多不同的定义。有一些非常直观,比如说get请求可以得到最近一次完成的put请求写入的值。这种一般也被称为强一致(Strong Consistency)。但是,事实上,构建一个弱一致的系统也是非常有用的。弱一致是指,不保证get请求可以得到最近一次完成的put请求写入的值。尽管有很多细节的工作要处理,强一致可以保证get得到的是put写入的最新的数据;而很多的弱一致系统不会做出类似的保证。所以在一个弱一致系统中,某人通过put请求写入了一个数据,但是你通过get看到的可能仍然是一个旧数据,而这个旧数据可能是很久之前写入的。
几乎可以确定的是,分布式系统的各个组件需要做大量的通信,才能实现强一致性。如果你有多个副本,那么不管get还是put都需要询问每一个副本。在之前的例子中,客户端在更新的过程中故障了,导致一个副本更新了,而另一个副本没有更新。如果我们要实现强一致,简单的方法就是同时读两个副本,如果有多个副本就读取所有的副本,并使用最近一次写入的数据。但是这样的代价很高,因为需要大量的通信才能得到一个数据。所以,为了尽可能的避免通信,尤其当副本相隔的很远的时候,人们会构建弱一致系统,并允许读取出旧的数据。当然,为了让弱一致更有实际意义,人们还会定义更多的规则。
为了避免强一致性导致的延迟、系统处理速度缓慢问题,人们常常会使用弱一致系统,你只需要更新最近的数据副本,并且只需要从最近的副本获取数据。在学术界和现实世界(工业界),有大量关于构建弱一致性保证的研究。
Lecture 3
分布式存储的难点
存储是一种关键的抽象。你可以想象,在分布式系统中,可能有各种各样重要的抽象可以应用在分布式系统中,但是实际上,简单的存储接口往往非常有用且极其通用。所以,构建分布式系统大多都是关于如何设计存储系统,或是设计其它基于大型分布式存储的系统。
人们设计大型分布式系统或大型存储系统出发点通常是,他们想获取巨大的性能加成,进而利用数百台计算机的资源来同时完成大量工作。因此,性能问题就成为了最初的诉求。 之后,很自然的想法就是将数据分割放到大量的服务器上,这样就可以并行的从多台服务器读取数据。我们将这种方式称之为分片(Sharding)。
如果你有数千台服务器,那么总是会有一台服务器宕机,每天甚至每个小时都可能会发生错误。所以,我们需要自动化的方法而不是人工介入来修复错误。我们需要一个自动的容错(fault tolerance)系统。
实现容错最有用的一种方法是使用复制,只需要维护2-3个数据的副本,当其中一个故障了,你就可以使用另一个。所以,如果想要容错能力,就得有复制(replication)。
针对复制出现的副本,自然而然就会有不一致(inconsistency)问题,只有保证完全一致,两者才能严格称为副本。但为了一致性,需要服务器之间通过额外的网络交互,这就会导致性能降低,反而与原先的设计背道而驰。
现实中,如果你想要好的一致性,你就要付出相应的代价。如果你不想付出代价,那就要忍受一些不确定的行为。我们之后会在很多系统中看到这里介绍的循环。通常,人们很少会乐意为好的一致性付出相应的性能代价。
错误的分布式设计(Bad Design)
对于具备强一致或者好的一致性的系统,从应用程序或者客户端看起来就像是和一台服务器在通信。尽管我们会通过数百台计算机构建一个系统,但是对于一个理想的强一致模型,你看到的就像是只有一台服务器,一份数据,并且系统一次只做一件事情。这是一种直观的理解强一致的方式。你可以认为只有一台服务器,甚至这个服务器只运行单线程,它同一时间只处理来自客户端的一个请求。
为了让这里的简单服务有可预期的行为,需要定义一条规则:一个时间只执行一条请求。这样每个请求都可以看到之前所有请求按照顺序执行生成的数据。所以,如果有一些写请求,并且服务器以某种顺序一次一个的处理了它们,当你从服务器读数据时,你可以看到期望的数据。即使在一个非常简单的系统中,仍然会出现一些模糊的场景使得你不知道系统的执行过程以及输出结果。你能做的只是从产生的结果来判断系统的输出是一致性还是非一致性。
(简单理解了上一段的内容,教授基本想表达的应该和SQL的MVCC版本链控制差不多,利用版本链控制进行事务管理,这样每一次操作看到的内容是基于当前事务发生时间ts而言的,而不是现实并发时间。 而所谓的从结果检查,基本和CMU15445写的后验检查差不多,检查是否有别的事务在事务运行期间对事务快照内容进行了修改,从而实现乐观锁/串行化验证。)
而GFS内有一个糟糕的分布式系统设计:
有两台服务器,每个服务器都有数据的一份完整拷贝。它们在磁盘上都存储了一个key-value表单。直观上希望这两个表单是完全一致的,这样一台服务器故障了,可以切换到另一台服务器去做读写。
两个表单完全一致意味着,每一个写请求都必须在两台服务器上执行,而读请求只需要在一台服务器上执行,否则就没有容错性了。
现在问题来了,假设客户端C1和C2都想执行写请求,其中一个要写X为1,另一个写X为2。C1会将写X为1的请求发送个两个服务器,因为我们想要更新两台服务器上的数据。C2也会将写X为2的请求发送给两个服务器。
由于没有保障两台服务器以相同的顺序处理这2个请求,如果服务器1(S1)先处理C1的请求,那么在它的表单里面,X先是1,之后S1看到了来自C2的请求,会将自己表单中的X覆盖成2。但是,如果S2恰好以不同的顺序收到客户端请求,那么S2会先执行C2的请求,将X设置为2,之后收到C1的请求,将X设置为1。(简单来说,由于网络问题,S1内是2,S2内是1,与原先写入的C1、C2完全相反,且不一致)
假设我们尝试修复上面的问题,我们让客户端在S1还在线的时候,只从S1读取数据,S1不在线了再从S2读取数据。这样最开始所有的客户端读X都能得到2。但是突然,如果S1故障了,尽管没有写请求将X改成1,客户端读X得到的数据将会从2变成1。因为S1故障之后,所有的客户端都会切换到S2去读数据。当然,这里的问题是可以修复的,修复需要服务器之间更多的通信,并且复杂度也会提升。由于获取强一致会带来不可避免的复杂性的提升,有大量的方法可以在好的一致性和一些小瑕疵行为之间追求一个平衡。
GFS的架构
1 | 元数据请求 |
GFS 主要由三种角色组成。
1. Master
一个 GFS 集群只有一个逻辑上的 Master,负责管理:
- 文件和目录的命名空间
- 文件被切分成了哪些 Chunk
- 每个 Chunk 保存在哪些 ChunkServer
- Chunk 副本的创建、迁移和恢复
- 写入租约(Lease)
- ChunkServer 的故障检测
Master 主要管理元数据,通常不传输文件内容。因此客户端的数据流量不会全部经过 Master,避免它过早成为数据传输瓶颈。
Master 将关键变更记录在操作日志中,并把日志复制到其他机器,以便故障恢复。
2. ChunkServer
文件被切分成固定大小的 Chunk,论文中的默认大小是 64 MB。
每个 Chunk:
- 拥有唯一的 Chunk Handle
- 存储在普通 Linux 文件系统中
- 默认保存 3 个副本
- 分散在不同机器,甚至不同机架
ChunkServer 定期向 Master 发送心跳,报告自己的状态和持有的 Chunk。
3. Client
Client 是应用程序使用的 GFS 客户端库。
读取文件时:
- Client 根据文件名和偏移量计算 Chunk 编号。
- 向 Master 查询 Chunk Handle 和副本位置。
- 缓存查询结果。
- 直接从某个 ChunkServer 读取数据。
因此,Master 负责“告诉客户端数据在哪里”,ChunkServer 才负责真正传输数据。
写入流程
一个 Chunk 通常有多个副本。为了保证副本按照相同顺序执行写操作:
- Master 为一个副本授予 Lease,使其成为 Primary。
- 其他副本成为 Secondary。
- Client 将数据发送给所有副本。
- Client 通知 Primary 执行写入。
- Primary 决定写操作的顺序。
- Secondary 按照该顺序执行写入。
- 所有副本完成后向 Client 返回结果。
这里的 Primary 是某个 Chunk 的写入主副本,不是整个 GFS 的 Master。不同 Chunk 可以拥有不同的 Primary,因此写入可以分散到不同服务器。
关于每个Chuck的 Chuck Version,可以理解为:某个 Chunk 当前副本所属的“版本代号”或“任期号”。
Version 的主要作用:
- 识别过期副本
- 防止旧副本重新参与服务
- 防止旧 Primary 继续写入
GFS如何解决分布式C问题
对正常完成的写入提供较好的副本一致性;对故障、并发和重试场景放宽语义,换取高吞吐和较简单的实
现。
GFS 提供的是一种针对特定工作负载的弱一致性模型,不是数据库式的强一致性。
基本可以如下表所示:
| 情况 | 结果 |
|---|---|
| 单次写入成功,且没有并发写 | 副本一致,内容明确 |
| 多个写入并发成功 | 副本通常一致,但最终排列可能未定义 |
| 写入失败 | 可能留下局部、不连续或不一致的数据 |
| Record Append | 原子追加,但重试可能出现重复记录 |
GFS 并不是通过全局事务解决一致性,而是把问题拆成几个局部机制。
1. 单个 Chunk 只有一个 Primary
同一时刻,一个 Chunk 的写入由一个 Primary 负责排序,避免多个副本各自决定顺序。
2. Primary 给写操作排序
所有副本按照 Primary 确定的顺序执行同一批 mutation,从而尽量保证副本内容一致。
3. Lease 防止多个 Primary 长期共存
Primary 只能在 Lease 有效期间处理写操作。Lease 过期后,旧 Primary 不能无限期继续工作。
4. Chunk Version 识别旧副本
版本号用于判断副本是否来自旧的 Lease,避免过期副本被误认为最新副本。
5. Checksum 检测静默损坏
即使磁盘没有明显报错,数据块也可能损坏。GFS 使用 checksum 检测这种损坏,并从其他副本读取或恢复。
GFS缺陷
最严重的局限可能在于,它只有一个Master节点,会带来以下问题:
Master节点必须为每个文件,每个Chunk维护表单,随着GFS的应用越来越多,这意味着涉及的文件也越来越多,最终Master会耗尽内存来存储文件表单。你可以增加内存,但是单台计算机的内存也是有上限的。所以,这是人们遇到的最早的问题。
除此之外,单个Master节点要承载数千个客户端的请求,而Master节点的CPU每秒只能处理数百个请求,尤其Master还需要将部分数据写入磁盘,很快,客户端数量超过了单个Master的能力。
另一个问题是,应用程序发现很难处理GFS奇怪的语义(GFS的副本数据的同步,或者可以说不同步)。
最后一个问题是,从我们读到的GFS论文中,Master节点的故障切换不是自动的。GFS需要人工干预来处理已经永久故障的Master节点,并更换新的服务器,这可能需要几十分钟甚至更长的而时间来处理。对于某些应用程序来说,这个时间太长了。
Lecture 4
在分布式系统中,如何维护一致性是很重要的课题。本节探讨关于容错(Fault-Tolerance)和复制(Replication)的问题。
复制(Replication)
容错本身是为了提供高可用性。例如,当你想构建一个服务时,尽管计算机硬件总是有可能故障,但是我们还是希望能稳定的提供服务,甚至,即使出现了网络问题我们还是想能够提供服务。我们所使用到的工具就是复制,至少在本课程的这一部分是这样。所以,一个很有意思的问题是:复制能处理什么样的故障呢?因为复制也不可能是万能的工具(可以用来解决所有的问题)。
复制的核心作用是:用多台机器保存或运行同一份服务,使单台机器失效时系统仍能继续工作。
能解决:Fail-stop 故障 (出错即终止)
即机器停止工作或从网络中消失,例如断电、宕机、网线被拔、风扇损坏导致 CPU 过热关机。外界无法再与该机器通信时,也可按 fail-stop 处理;此时由其他副本接管即可。不能解决:相同原因导致的所有副本频繁出错
若所有副本运行相同的有 bug 软件,它们可能一致地产生错误结果;复制只复制了错误。
同样,若硬件设计缺陷会让机器产生错误计算,使用同型号、同设计的副本也可能一起出错。
状态转移和复制状态机(State Transfer and Replicated State Machine)
在VMware FT论文中,介绍了两种复制方法:
- 状态转移(State Transfer)
- 复制状态机(Replicated State Machine)
这两者都为了一个目的:如果我们有一个服务器的两个副本,我们需要让它们保持同步,在实际上互为副本,这样一旦Primary出现故障,因为Backup有所有的信息,就可以接管服务。
唯一的区别就是:状态转移传输的是可能是内存,而复制状态机会将来自客户端的操作或者其他外部事件,从Primary传输到Backup。
状态转移
状态转移背后的思想是,Primary将自己完整状态,比如说内存中的内容,拷贝并发送给Backup。Backup会保存收到的最近一次状态,所以Backup会有所有的数据。当Primary故障了,Backup就可以从它所保存的最新状态开始运行。所以,状态转移就是发送Primary的状态。这种情况下,每过一会,Primary就会对自身的内存做一大份拷贝,并通过网络将其发送到Backup。
当然也可以有一些优化,比如只传送相比上次变化的数据等等,但总之这种方法所需带宽非常大,延迟较高,因此在工业界中应用不多。
复制状态机
由于一个机器不确定的状态只有外部输入,只有当外部事件干预时,才会发生一些预期外的事。因此复制状态机不会在不同的副本之间发送状态,相应的,它只会从Primary将这些外部事件,例如外部的输入,发送给Backup。通常来说,如果有两台计算机,如果它们从相同的状态开始,并且它们以相同的顺序,在相同的时间,看到了相同的输入,那么它们会一直互为副本,并且一直保持一致。
如何选择
人们倾向于使用复制状态机的原因是,通常来说,外部操作或者事件比服务的状态要小。
如果是一个数据库的话,它的状态可能是整个数据库,可能到达GB这个级别,而操作只是一些客户端发起的请求,例如读key27的数据。所以操作通常来说比较小,而状态通常比较大。所以复制状态机通常来说更吸引人一些。复制状态机的缺点是,它会更复杂一些,并且对于计算机的运行做了更多的假设。而状态转移就比较简单粗暴,我就是将我整个状态发送给你,你不需要再考虑别的东西。
针对随机性问题,或许是获取当前的时间,因为执行时间的略微不同,会产生不同的结果。又或者是获取当前CPU的唯一ID和序列号,也会产生不同的结果。对于这一类问题的统一答案是,Primary会执行这些指令,并将结果发送给Backup。Backup不会执行这些指令,而是在应该执行指令的地方,等着Primary告诉它,正确的答案是什么,并将监听到的答案返回给软件。
非确定指令下的复制
非确定性事件可以分成几类。
- 客户端输入。假设有一个来自于客户端的输入,这个输入随时可能会送达,所以它是不可预期的。客户端请求何时送达,会有什么样的内容,并不取决于服务当前的状态。一个网络数据包对于我们来说有两部分,一个是数据包中的数据,另一个是提示数据包送达了的中断。当网络数据包送达时,通常网卡的DMA(Direct Memory Access)会将网络数据包的内容拷贝到内存,之后触发一个中断。操作系统会在处理指令的过程中消费这个中断。对于Primary和Backup来说,这里的步骤必须看起来是一样的(接受+拷贝+触发终端 是一体的),否则它们在执行指令的时候就会出现不一致。所以,这里的问题是,中断在什么时候,具体在指令流中的哪个位置触发?对于Primary和Backup,最好要在相同的时间,相同的位置触发,否则执行过程就是不一样的,进而会导致它们的状态产生偏差。所以,我们不仅关心网络数据包的内容,还关心中断的时间。
- 有一些指令在不同的计算机上的行为是不一样的,这一类指令称为怪异指令,比如说:
- 随机数生成器
- 获取当前时间的指令,在不同时间调用会得到不同的结果
- 获取计算机的唯一ID
- 另外一个常见的非确定事件,就是多CPU的并发。我们现在讨论的都是一个单进程系统,没有多CPU多核这种事情。之所以多核会导致非确定性事件,是因为当服务运行在多CPU上时,指令在不同的CPU上会交织在一起运行,进而产生的指令顺序是不可预期的。假设两个核同时向同一份数据请求锁,在Primary上,核1得到了锁;在Backup上,由于细微的时间差别核2得到了锁,那么执行结果极有可能完全不一样,这里其实说的就是(在两个副本上)不同的线程获得了锁。
Lecture 6 + 7 Raft
详细的Raft算法、一致性问题见分布式系统的相关学习中的实现强一致的复制状态机 – Raft
这里只总结教授课上提出的问题。
同时,具体的讲解可以看这个视频专栏
脑裂问题
假设我们有一个网络,这个网络里面有两个服务器(S1,S2),这两个服务器都是我们Test-and-Set服务的拷贝。这个网络里面还有两个客户端(C1,C2),它们需要通过Test-and-Set服务确定主节点是谁。在这个例子中,这两个客户端本身就是VMware FT中的Primary和Backup虚拟机。
当一个客户端可以与其中一个服务器通信,但是不能与另一个通信时,有可能出现脑裂的问题。我们假设,客户端发送请求时,它会将请求同时发送给两个服务器。这样,我们就需要考虑,当某个服务器不响应时,客户端该怎么做?或者说,某个服务器不响应时,整个系统该如何响应?更具体点,我们假设C1可以访问S1但是不能访问S2,系统该如何响应?
一种情况是,我们必然不想让C1只与S1通信。因为,如果我们只将C1的请求设置给S1,而不设置给S2,会导致S2的数据不一致。所以,我们或许应该规定,对于任何操作,客户端必须总是与两个服务器交互,而不是只与其中一个服务器交互。但是这是一个错误的想法,为什么呢?因为这里根本就没有容错。这里甚至比只使用一个服务器更糟。因为当两个服务器中的一个故障了或者失联了,我们的系统就不能工作了。对于一个单点的服务,我们只依赖一个服务器。现在我们有两个服务器,并且两个服务器都必须一致在线,这里的难度比单个服务器更大。如果这种方式不是容错的,我们需要一种行之有效的方法。
另一个明显的答案是,如果客户端不能同时与两个服务器交互,那它就与它能连通的那个服务器交互,同时认为另一个服务器已经关机了。为什么这也是一个错误的答案呢?因为,我们的故障场景是,另一个服务器其实还开机着。我们假设我们经历的实际问题并不是这个服务器关机了,因为如果关机了对我们来说其实更好。实际情况可能更糟糕,实际可能是网络线路出现了故障,从而导致C1可以与S1交互,但是不能与S2交互。同时,C2可以与S2交互,但是不能与S1交互。现在我们规定,如果一个客户端连接了两个服务器,为了达到一定的容错性,客户端只与其中一个服务器交互也应该可以正常工作。但是这样就不可避免的出现了这种情况:假设这根线缆中断了,将网络分为两个部分(分区容错)。
所以,在这种有两个拷贝副本的配置中,看起来我们只有两种选择:要么等待两个服务器响应,那么这个时候就没有容错能力;要么只等待一个服务器响应,那么就会进入错误的场景,而这种错误的场景,通常被称为脑裂。
当时的人们在构建多副本系统时,需要排除脑裂的可能。这里有两种技术:
第一种是构建一个不可能出现故障的网络。实际上,不可能出现故障的网络一直在我们的身边。你们电脑中,连接了CPU和内存的线路就是不可能出现故障的网络。所以,带着合理的假设和大量的资金,同时小心的控制物理环境,比如不要将一根网线拖在地上,让谁都可能踩上去。如果网络不会出现故障,这样就排除了脑裂的可能。这里做了一些假设,但是如果有足够的资金,人们可以足够接近这个假设。当网络不出现故障时,那就意味着,如果客户端不能与一个服务器交互,那么这个服务器肯定是关机了。
另一种就是人工解决问题,不要引入任何自动完成的操作。默认情况下,客户端总是要等待两个服务器响应,如果只有一个服务器响应,永远不要执行任何操作。相应的,给运维人员打电话,让运维人员去机房检查两个服务器。要么将一台服务器直接关机,要么确认一下其中一台服务器真的关机了,而另一个台还在工作。所以本质上,这里把人作为了一个决策器。而如果把人看成一台电脑的话,那么这个人他也是个单点。
过半票决(Majority Vote)
随着技术的发展,人们发现哪怕网络可能出现故障,可能出现分区,实际上是可以正确的实现能够自动完成故障切换的系统。当网络出现故障,将网络分割成两半,网络的两边独自运行,且不能访问对方,这通常被称为网络分区。
在构建能自动恢复,同时又避免脑裂的多副本系统时,人们发现,关键点在于过半票决(Majority Vote)。这是Raft论文中出现的,用来构建Raft的一个基本概念。过半票决系统的第一步在于,服务器的数量要是奇数,而不是偶数。例如在上图中(只有两个服务器),中间出现故障,那两边就太过对称了。这里被网络故障分隔的两边,它们看起来完全是一样的,它们运行了同样的软件,所以它们也会做相同的事情,这样不太好(会导致脑裂)。
但是,如果服务器的数量是奇数的,那么当出现一个网络分割时,两个网络分区将不再对称。假设出现了一个网络分割,那么一个分区会有两个服务器,另一个分区只会有一个服务器,这样就不再是对称的了。这是过半票决吸引人的地方。所以,首先你要有奇数个服务器。然后为了完成任何操作,例如Raft的Leader选举,例如提交一个Log条目,在任何时候为了完成任何操作,你必须凑够过半的服务器来批准相应的操作。这里的过半是指超过服务器总数的一半。直观来看,如果有3个服务器,那么需要2个服务器批准才能完成任何的操作。
有关过半票决系统的一个特性就是,最多只有一个网络分区会有过半的服务器,所以我们不可能有两个分区可以同时完成操作。这里背后更微妙的点在于,如果你总是需要过半的服务器才能完成任何操作,同时你有一系列的操作需要完成,其中的每一个操作都需要过半的服务器来批准,例如选举Raft的Leader,那么每一个操作对应的过半服务器,必然至少包含一个服务器存在于上一个操作的过半服务器中。也就是说,任意两组过半服务器,至少有一个服务器是重叠的。实际上,相比其他特性,Raft更依赖这个特性来避免脑裂。例如,当一个Raft Leader竞选成功,那么这个Leader必然凑够了过半服务器的选票,而这组过半服务器中,必然与旧Leader的过半服务器有重叠。所以,新的Leader必然知道旧Leader使用的任期号(term number),因为新Leader的过半服务器必然与旧Leader的过半服务器有重叠,而旧Leader的过半服务器中的每一个必然都知道旧Leader的任期号。类似的,任何旧Leader提交的操作,必然存在于过半的Raft服务器中,而任何新Leader的过半服务器中,必然有至少一个服务器包含了旧Leader的所有操作。这是Raft能正确运行的一个重要因素。
应用层接口
这一部分简单介绍一下应用层和Raft层之间的接口。你或许已经通过实验了解了一些,但是我们这里大概来看一下。假设我们的应用程序是一个key-value数据库,下面一层是Raft层。
在Raft集群中,每一个副本上,这两层之间主要有两个接口。
第一个接口是key-value层用来转发客户端请求的接口。如果客户端发送一个请求给key-value层,key-value层会将这个请求转发给Raft层,并说:请将这个请求存放在Log中的某处。这个接口实际上是个函数调用,称之为Start函数。这个函数只接收一个参数,就是客户端请求。key-value层说:我接到了这个请求,请把它存在Log中,并在committed之后告诉我。
另一个接口是,随着时间的推移,Raft层会通知key-value层:哈,你刚刚在Start函数中传给我的请求已经commit了。Raft层通知的,不一定是最近一次Start函数传入的请求。例如在任何请求commit之前,可能会再有超过100个请求通过Start函数传给Raft层。
这个向上的接口以go channel中的一条消息的形式存在。Raft层会发出这个消息,key-value层要读取这个消息。所以这里有个叫做applyCh的channel,通过它你可以发送ApplyMsg消息。
当然,key-value层需要知道从applyCh中读取的消息,对应之前调用的哪个Start函数,所以Start函数的返回需要有足够的信息给key-value层,这样才能完成对应。Start函数的返回值包括,这个请求将会存放在Log中的位置(index)。这个请求不一定能commit成功,但是如果commit成功的话,会存放在这个Log位置。同时,它还会返回当前的任期号(term number)和一些其它我们现在还不太关心的内容。
所有的副本都会收到这个ApplyMsg消息,它们都知道自己应该执行这个请求,弄清楚这个请求的具体含义,并将它应用在本地的状态中。所有的副本节点还会拿到Log的位置信息(index),但是这个位置信息只在Leader有用,因为Leader需要知道ApplyMsg中的请求究竟对应哪个客户端请求(进而响应客户端请求)。
日志恢复
1. 核心思想
Raft 的日志恢复本质上是:
Leader 通过递减 follower 的
nextIndex,找到 Leader 与 follower 日志中最后一个一致的位置,然后用 Leader 的日志覆盖 follower 后面的冲突内容。
恢复过程中,Leader 不会盲目追加日志,而是先通过 prevLogIndex 和 prevLogTerm 检查双方日志前缀是否一致。
2. AppendEntries 的关键字段
Leader 向 follower 发送 AppendEntries RPC 时,主要包含:
| 字段 | 含义 |
|---|---|
prevLogIndex |
新日志条目前一个日志槽位的下标 |
prevLogTerm |
prevLogIndex 对应日志条目的任期 |
entries |
本次需要复制给 follower 的日志条目 |
nextIndex |
Leader 认为 follower 下一条需要接收的日志位置 |
Follower 只有在满足下面条件时,才会接受日志:
1 | 本地存在 prevLogIndex |
如果检查失败,Follower 返回 False,Leader 将对应的 nextIndex 减一后重试。
3. 具体恢复过程
假设:
- 当前新任期为
6 S3在任期6成为 Leader- Leader 的新日志位于槽位
13 S3的槽位12日志属于任期5S2的槽位12日志属于任期4S1的槽位12为空
第一次发送
Leader 刚当选时,通常将每个 follower 的 nextIndex 初始化为:
1 | Leader 最后一条日志的位置 + 1 |
本例中:
1 | nextIndex = 13 |
结果:
S2拒绝:本地槽位12的任期是4,与 Leader 的任期5不一致。S1拒绝:本地没有槽位12。
Follower 不会因为收到了槽位 13 的日志,就直接把它追加到本地。否则会导致日志中间出现不一致。
第二次发送
Leader 收到拒绝后,将 follower 的 nextIndex 减一:
1 | nextIndex = 12 |
结果:
S2接受:它的槽位11与 Leader 的槽位11一致。S2删除本地冲突的槽位12,再写入 Leader 发来的槽位12和13。S1仍然拒绝:因为S1的槽位11为空,无法匹配prevLogIndex = 11。
此时,S2 的日志已经与 Leader 一致。
第三次发送给 S1
Leader 将 S1 的 nextIndex 再减一:
1 | nextIndex = 11 |
这次 S1 能够匹配槽位 10,因此接受整个日志片段。
最终:
1 | S1、S2、S3 的日志完全一致 |
nextIndex = 14 表示 follower 当前已经拥有槽位 13,下一条需要复制的是槽位 14。
4. 恢复流程概括
整个过程可以概括为:
1 | 1. Leader 从 nextIndex 开始发送 AppendEntries |
5. 为什么不能直接追加日志?
假设 follower 在槽位 12 已经有任期 4 的日志,而 Leader 发送槽位 13 的日志。
如果 follower 不检查槽位 12,直接写入槽位 13,就会形成:
1 | 槽位 12:旧日志 |
这样虽然日志长度看起来一致,但日志内容实际上来自不同的历史分支,破坏了 Raft 的日志一致性。
因此,Follower 必须先确认前一个日志条目一致,才能接受后续日志。
6. 为什么删除 follower 的旧日志是安全的?
本例中,S2 被删除的槽位 12 日志只存在于少数服务器上,没有复制到大多数节点,因此它不可能已经提交。
Raft 的安全性依赖以下规则:
- 日志只有复制到多数服务器后才能提交。
- 只有提交后的日志才会被应用到状态机。
- Leader 只有在日志提交后,才会向客户端返回成功。
- 如果客户端长时间没有收到回复,它会重新发送请求。
因此,被覆盖的旧日志:
1 | 没有提交 |
删除它不会造成已经确认的客户端操作丢失。
更一般地说,Raft 不会覆盖已经提交的日志;被覆盖的只能是未提交的冲突日志。
7. 为什么看起来总是在删除日志尾部?
Leader 和 follower 一致的部分构成一个共同前缀。冲突通常出现在这个共同前缀之后,因此恢复时表现为:
1 | 保留一致前缀 |
这并不是因为 Leader 只能删除尾部。Leader 拥有完整日志,即使从第一条日志开始发送整个日志,也可以恢复 follower。
从尾部逐步回退只是更高效的做法,因为它可以尽快找到双方日志的共同前缀。
8. 一句话总结
Raft 日志恢复通过 prevLogIndex 和 prevLogTerm 找到 Leader 与 follower 的共同日志前缀;匹配失败就递减 nextIndex 重试,匹配成功后删除 follower 的冲突后缀,并用 Leader 的日志替换它,从而最终让所有节点的日志保持线性一致。
任期约束
在Raft论文的5.4.1,Raft有一个稍微复杂的选举限制(Election Restriction)。这个限制要求,在处理别节点发来的RequestVote RPC时,需要做一些检查才能投出赞成票。这里的限制是,节点只能向满足下面条件之一的候选人投出赞成票:
- 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号;
- 或者,候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号,且候选人的Log记录长度大于等于本地Log记录的长度
快速恢复
在 7.1 介绍的日志恢复机制中,当 Leader 与 Follower 的日志存在冲突时,Leader 每次只回退一条 Log 条目。这在某些现实场景中效率极低:
- 场景举例:一个 Follower 关机了很长时间,错过了大量的 AppendEntries 消息(例如 1000 条)。Leader 重启后,会将所有 Follower 的
nextIndex设置为本地 Log 的下一个槽位,然后逐条回退,需要 1000 次 RPC 才能完成恢复。 - 更极端的场景:5 台服务器中,1 个 Leader 和 1 个 Follower 被困在一个网络分区中。旧 Leader 不知道自身已不是 Leader,持续向唯一的 Follower 发送 AppendEntries(但因不过半,无法 commit)。另一个分区选出新 Leader 继续运行。当旧分区重新加入集群时,旧 Leader 和 Follower 上可能积累了大量未 commit 的旧任期日志,需要被删除覆盖。
因此快速恢复就是为了:让 Follower 在拒绝 AppendEntries 时,返回足够的信息给 Leader,使 Leader 能够以 任期(Term)为单位 进行回退,而不是逐条回退。
为简化说明,以一个 Leader(S2)和一个 Follower(S1)为例,S2 将发送任期号为 6 的 AppendEntries 给 S1。
| 场景 | 描述 | 处理方式 |
|---|---|---|
| 场景 1 | S1 没有任期 6 的任何 Log,需要回退一整个任期 | Leader 回退到 Follower 中该任期的起始位置 |
| 场景 2 | S1 收到了旧 Leader 的多条任期 4 的 Log,但新 Leader S2 只有一条任期 4 的 Log | Leader 用自身日志覆盖 Follower 中多余的旧日志 |
| 场景 3 | S1 与 S2 的 Log 不冲突,但 S1 缺失了部分 S2 中的 Log | Leader 从 Follower 日志末尾开始发送 |
如果失败,则需要额外返回信息:
当 Follower 因日志不匹配而拒绝 Leader 的 AppendEntries 时,回复中携带:
| 字段 | 含义 |
|---|---|
| XTerm | Follower 中与 Leader 冲突的 Log 对应的任期号。若 Follower 在对应位置没有 Log,则返回 -1 |
| XIndex | Follower 中,任期号为 XTerm 的第一条 Log 条目的槽位号 |
| XLen | 当 XTerm = -1 时,表示 Follower 中空白 Log 槽位的数量(即日志长度) |
场景 1:Leader 没有 XTerm 对应的日志
- Follower 返回:
XTerm=5, XIndex=2 - Leader 发现自己没有任期 5 的日志
- 操作:将
nextIndex设置为XIndex(即 Follower 中任期 5 的第一条 Log 位置) - 效果:下一条 AppendEntries 可一次覆盖 Follower 中所有任期 5 的 Log
场景 2:Leader 有 XTerm 对应的日志
- Follower 返回:
XTerm=4, XIndex=1 - Leader 发现自己有任期 4 的日志
- 操作:将
nextIndex设置为 Leader 本地 XTerm 位置 Log 条目的下一个槽位(即槽位 2) - 效果:下一条 AppendEntries 可一次覆盖 Follower 中多余的旧日志
场景 3:Follower 日志太短(XTerm = -1)
- Follower 返回:
XTerm=-1, XLen=2 - 表示 Follower 在冲突位置没有 Log 条目
- 操作:将
nextIndex设置为XLen(即 Follower 最后一条 Log 的下一个位置,槽位 2) - 效果:Leader 从该位置开始发送 AppendEntries
持久化(Persistence)
持久化的核心概念
- 定义:持久化是指将数据写入磁盘或电池供电的RAM等非易失性存储中。其目的是确保服务器在故障重启后,能够恢复之前的状态并继续运行。
- 适用场景:
- 单机故障:虽然可以用新服务器替换,但无法从损坏的磁盘中恢复数据。
- 集群级断电:这是持久化最关键的场景。当整个集群同时断电时,必须依赖持久化状态在供电恢复后重建服务,而不能仅靠替换新硬件解决。
- 区分原则:Raft 论文图2明确区分了“持久化(Persistent)”和“非持久化(Volatile)”数据。只有对重启后恢复必不可少的数据才进行持久化,以平衡安全性与性能。
必须持久化的三个关键数据
根据 Raft 论文,仅有以下三项数据必须持久化:
| 数据项 | 持久化原因 |
|---|---|
| Log (日志) | 是记录应用程序状态的唯一来源。Raft 不要求持久化应用状态本身,重启后需通过重放 Log 来重建应用状态。 |
| votedFor | 防止同一任期内出现双 Leader。若未持久化,服务器重启后可能在同一任期重复投票给不同候选人,导致该任期产生两个 Leader,破坏安全性。 |
| currentTerm | 确保任期号的单调递增和唯一性。若未持久化,重启后的节点可能使用旧的任期号发起选举或追加日志,导致与现有集群状态冲突(如产生重复的任期号)。 |
可以安全丢弃的非持久化数据
以下数据在重启后可以被安全重置,无需持久化:
- commitIndex & lastApplied:Leader 可以通过向 Follower 发送
AppendEntriesRPC 并收集响应,重新计算出哪些日志已被提交。 - nextIndex & matchIndex:这些是 Leader 用于管理 Follower 同步状态的临时变量,重启后可通过通信重新探测和建立。
- 应用程序状态:基于 Raft 的简单性设计,假设应用状态随重启消失,完全依赖重放持久化的 Log 从头构建。(注:这种方式虽优雅但较慢,后续可通过 Log Compaction/Snapshot 优化)。
性能挑战与优化策略
持久化操作(尤其是机械硬盘的同步写入)代价高昂,可能成为系统瓶颈。
- 性能瓶颈:机械硬盘同步写入耗时约 10ms,限制了系统吞吐量上限约为 100 ops/s。
- 编程注意事项:
- 在 UNIX/Linux/Mac 系统中,
write()返回并不代表数据已落盘。 - 必须调用
fsync()才能确保数据安全写入介质。fsync开销大,应谨慎使用。
- 在 UNIX/Linux/Mac 系统中,
- 优化方案:
- 批量处理 (Batching):累积多个客户端请求后,一次性持久化多条 Log 再发送 RPC,减少
fsync调用次数。 - 硬件升级:使用 SSD/闪存(写入耗时降至 ~0.1ms)或电池供电的 DRAM(百万级 IOPS),从根本上消除磁盘 IO 瓶颈。
- 最小化持久化范围:仅持久化必要的三个字段,避免全量状态持久化带来的额外开销。
- 批量处理 (Batching):累积多个客户端请求后,一次性持久化多条 Log 再发送 RPC,减少
日志快照
保持线性一致性
Lecture 8 Zab
同样的,总结教授上课提出的问题,详细的Zab见分布式系统的相关学习中的ZooKeeper 的强一致复制协议 —— ZAB




