mit6824

mapreduceMapReduce (2004)

介绍及例子

用户需要指定map以及reduce函数，map函数负责建立中间键值的映射关系，reduce将所有的值合并到相同的键上。（如wordcount程序）

reduce  (k2,list(v2))   → list(v2)
map     (k1,v1)         → list(k2,v2)

输入键和值是从与输出键和值不同的域中绘制的。此外，中间键和值与输出键和值来自相同的域。

分布式Grep

map ：在匹配到一行时发射一行

reduce：将中间数据复制到输出

url访问频率统计

map：输出 <URL, 1>

reduce: 对来自相同url的相加然后发送<URL, TOTAL count>

实现

Map调用通过将输入数据自动分割为 M 段 分布在多个机器上。

Map函数执行完之后，会通过分区函数将中间键划分为R个互不重叠的分区。（默认分区函数可以是hash函数，这样可以将相同的键放到同一个分区，即将该类键都分到某一个具体的分区中，由某一个任务执行）

任务粒度

当用户提供的map以及reduce操作都是确定性的（相同输入必定产生相同输出），那么mapreduce的分布式执行结果也会类似于单机顺序执行的结果。

M和R的数量可以尽可能比worker数量大，可以实现负载均衡，出错时可以可以快速failback。

还是有些具体限制的，比如master主机必须做出O(M+R)调度决策，以及在内存保存O(M*R)中状态

备份执行

多台worker之间存在掉队者现象，由于一些原因导致该worker虽然能正常运行，但是执行速度相当慢，这会导致整个MapReduce的时间非常长。解决办法是，在MapReduce将要完成时，将还在执行的任务备份到另一个worker进行执行，这两个worker任意一个执行完成都会导致该任务执行完成。

拓展功能

分区函数

数据在Map之后会被分区，默认分区函数时hash函数，当有特殊需求时，可以提供特殊的分区函数。

顺序保证

每个分区中，中间键值对会按照键递增顺序处理，这可以使得每个分区生成有序的生成文件。

组合函数

组合函数与Reduce函数的功能相同，但是组合函数是在执行Map任务的机器上执行的。（先组合再进行网络传输，可以少传输一点数据）

输入输出格式

可以将输入数据按照多种格式读入。

• 文本格式将每一行是为一个键值对，唔讲的偏移是键，而该行作为值。

读取器不一定从文件读取数据，额可以定义读取器从数据库读取。

副作用

跳过坏记录

通过信号处理器函数捕获异常，多次发现错误时，master 指示跳过。

本地执行

便于调试。

状态信息

主节点提供http页面供观察

计数器

Lecture01

使用分布式系统的两个原因：性能与容错。

该课程依赖的基础架构：存储，通信，计算。

能否提供些抽象的接口，将分布式特性隐藏在整个系统内。

构建分布系统时，使用了很多的工具：

• RPC, 目标就是掩盖我们正在不可靠网络上通信的事实。
• 线程，
• 并发控制，比如锁

可拓展性

一个系统跑在多个计算机上就会有多倍的性能。（系统拓展了，性能也会对应的拓展，这种可拓展性在一段范围内是生效的，当达到系统瓶颈时，将失去可拓展性，这需要我们再次优化架构设计)

可用性

单台计算机大概率是可靠的，但是如果一个服务器集群，很可能会出现错误。

• 容错：发生某些错误时，系统仍然能够正常运行，像没有错误一样。

• 可用（Availability）系统是指，在特定的故障范围内，系统仍然能够提供服务。（比如一个有两个拷贝的系统，一台有故障，那么系统仍然是可用的）

• 可恢复性（Recoverablity），一个更弱的容错特性，指的是发生会导致服务中止的错误时，系统会停止工作，不在响应请求，等待修复完成后，系统可以正常运行。（比如系统需要通过日志将数据/状态写入硬盘，这样发生错误——断电时，系统停止工作，重启后，会从磁盘读取数据正常运行）

一个好的可用的系统，也应该是可恢复的。为了实现这些特性，需要很多工具，比如：

• 硬盘，为了实现容错需要频繁写入，为了性能应该减少写入
• 复制，如果管理多系统中的副本是个问题，他们可能轻易的偏离同步的状态，而不再是副本。

一致性

很多问题，比如分布式kv数据库，有两台主机，向一台主机put了数据，这台主机可能无法及时同步到另一台主机上，造成不一致。

• 强一致，get请求会返回最近一次完成的put请求写入的值，
• 弱一致，不会做上面的保证，所有弱一致系统的get可能返回一个旧数据。

虽然强一致很完美，但是弱一致也让人感兴趣。因为强一致的代价太大，用户需要向所有的主机get数据，使用最新的数据作为get返回的数据，带来了很大的资源开销。当服务器相隔很远时，人们会构建弱一致系统，当然，为了让弱一致更有意义，还会定义很多的规则。

Map & Reduce

以wordcount为例：

Map函数使用一个key以及value作为参数，key通常是输入文件的名字（或者索引），通常被忽略，值包含了要统计的文本。Map函数对于每一个单词，通过emit函数传到MarReduce库，比如emit('w', 1)。

Reduce函数

Reduce函数的入参是某一个key的所有实例，比如参数为，(w, [1, 1, 1, 1,1])。该函数也可以使用emit函数，该函数需要一个参数value，这个value会作为传入参数key的最终输出。

编码过程中，遇到了问题，是cpu跑满了，但是执行速度仍然十分慢，io速度也很慢：

filename := fmt.Sprintf("mr-%v-%v", reply.MIndex, ihash(kvs[first].Key)%reply.RNum)
file, err := os.Create(filename)
if err != nil {
 fmt.Println("Cannot create file: ", err)
 return nil, false
}
//利用缓冲区，避免每次调用encode都会触发系统调用write
wfile := bufio.NewWriterSize(file, 64*1024)
enc := json.NewEncoder(wfile)
for _, kv := range kvs[first:i] {
 err := enc.Encode(&kv)
 if err != nil {
     fmt.Println("Encode to json failed: ", err)
     return nil, false
 }
}

一开始猜测是缓冲区太小，导致每次通过encode时，都会触发io，速度很慢，

实际上，操作系统本来就具有缓冲区，写入量达到一定程度时才会写入磁盘。这里可能是因为每次使用encode都触发了write系统调用，虽然write只是将数据写到内存上的磁盘缓冲区中，但毕竟是系统调用，十分耗时间，导致这里十分慢。

这里可使用这两种内存缓冲区，bufio.Writer 内部维护一个内存缓冲区（大小可指定，比如 64KB）。

每次写入先写到缓冲区（无需系统调用），只有缓冲区满或者调用 Flush()才会写到磁盘缓冲区中，进而写入磁盘。

发现速度也很慢，后面查看火焰图，是json的encode方法占用了大量的cpu，可以从这里优化，

• 就是使用更快的json库：github.com/goccy/go-json，
• 每次写入读取keyvalue的切片，而非单个keyvalue

极其隐蔽的bug：

Go 的 net/rpc 包使用 反射机制 来序列化和反序列化结构体字段。
只有大写字母开头的字段（即导出字段）才会被反射访问到，小写字母开头的字段是未导出的，无法被外部RPC包访问，因此：小写字段会被忽略，不会参与编码传输。

容错虚拟机Fault-Tolerant Virtual Machines (2010)

默认使用共享磁盘，主虚拟机与备份虚拟机访问相同的虚拟磁盘。

两种备份方式：

• 全量状态复制，将主虚拟机的全部状态传输至备份端：cpu状态，内存数据，io设备的操作状态。
• 状态机复制，保证输入一致，然后同步所有输入请求（数据包，用户操作指令），以及一些其他的非确定性操作信息，比如中断时机。

对多核处理器上较难实现，因为涉及到共享内存，多个进程均可对一块内存区域进行访问。（那感觉没啥实际意义啊）

基本设计

为了检测 主、备份虚拟机是否有故障，使用了两种机制，

• 一是在服务器之间建立心跳连接，
• 二是对日志通道上的流量进行监控。

确定性重放

FT 协议

主虚拟机的输出信息也需要通过特殊的日志传输给备份虚拟机，备份虚拟机确认后再由主虚拟机发送。

但是备份虚拟机接管时，仍然不知道主虚拟机是否执行了最后的输出，

• 幸运的是网络基础设施，操作系统（TCP）等通过设计能处理数据包丢失以及重复的情况。（重复以及丢失感觉都行，最主要的是避免服务器状态的不一致，比如主服务器收到自增数据包，再备用服务器未确认LOG前就给客户端回发了包，如果LOG和主服务器同时崩了，那么备用服务器的内部状态就和主服务器不一致；只要主服务器没有输出，感觉不管丢失多少LOG日志都没有问题，只要外部客户端能重发消息就行了）
• 也可以是使用两阶段提交（以一种分布式一致性协议），保证多个参与者要么全部成功，要么全部失败。

检测以及响应错误

具有一致性语义的键值服务器

不管有多少服务器副本，有多少客户端在操作，看起来就像是所有人都在访问 同一份全局的单机 key/value 存储。

用 KV（键值存储）实现锁

键值存储只提供了两个方法：

func (kvtest.IKVClerk) Put(string, string, rpc.Tversion) rpc.Err
func (kvtest.IKVClerk) Get(string) (string, rpc.Tversion, rpc.Err)

实现如下：

func (lk *Lock) Acquire() {
	// Your code here
	quit := false
	for !quit {
		err := lk.ck.Put(lk.l, "on", (lk.ver))
		switch err {
		case rpc.OK:
			quit = true
			lk.ver = lk.ver + 1
		case rpc.ErrNoKey:
			fmt.Println("why, this should't happend.")
		case rpc.ErrMaybe:
			//不确定，重试吧
		case rpc.ErrVersion:
			stat, newver, _ := lk.ck.Get(lk.l)
			if stat == "on" {
				//服务器有用户，抢下一个版本号
				lk.ver = newver + 1
			} else {
				//服务器无用户，抢这个版本号
				lk.ver = newver
			}
		}
	}
}

func (lk *Lock) Release() {
	// Your code here
	quit := false
	for !quit {
		err := lk.ck.Put(lk.l, "off", (lk.ver))
		switch err {
		case rpc.OK:
			quit = true
			lk.ver = lk.ver + 1 //方便下次上锁
		case rpc.ErrNoKey:
			fmt.Println("why, this should't happend.")
		case rpc.ErrMaybe:
			//不确定，重试吧,暂不支持maybe
			quit = true
		case rpc.ErrVersion:
			fmt.Println("Lock has been stoled by others.")
			//_, newver, _ := lk.ck.Get(lk.l)
			//lk.ver = newver + 1
			quit = true
		}
	}
}

主要思路是lk.ver存储了当前线程最可能获取到锁的version，初始为0，

• 获取成功则标记value，让其他线程知道锁被占用。
• 失败则获取最新的version，将其作为 lk.version,然后判断当前锁是否被占用再执行对应的操作

貌似下面的方法更简单：

func (lk *Lock) Acquire() {
	for {
		id, version, err := lk.ck.Get(lk.lockStr)
		if id == lk.id {
			return
		}
		if err == rpc.ErrNoKey || id == "" {
			err := lk.ck.Put(lk.lockStr, lk.id, version)
			if err == rpc.OK {
				return
			}
		}
		time.Sleep(10 * time.Millisecond)
	}
}
func (lk *Lock) Release() {
	id, version, err := lk.ck.Get(lk.lockStr)
	if err == rpc.OK && id == lk.id {
		lk.ck.Put(lk.lockStr, "", version)
	}
}

分布式系统的线性化

需要保证线性一致性，线性化是一种强一致性模型，因此在线性化系统之上构建其他系统相对容易。比如如下的操作是符合线性一致性的，我们能够找到每一个操作的线性化点，这样系统仍然具有线性的：

如果从客户端的角度来定义线性一致，那么如下的情况：

客户端 C2在发送读请求时，服务器收到了请求，记录请求id，发送回复3（假如这个回复丢包了），执行了 写入 X 等于 4。这时收到了客户端发送的重复 读请求，服务器这时发现自己已经收到过这个请求，那么现在其实发送之前的回复，还是发送新的值 4 都是满足线性一致性的。

Raft共识算法

Raft和Paxos等价，但更好理解。

介绍

共识算法能够让一组机器协同工作，形成一个统一的整体，即便部分机器出现故障，该整体仍能正常运行。（要满足基本目标一致性）

Raft算法分为三个部分：领导者选举、日志复制和安全性

Raft有很多新特性：

• 强领导者机制：日志条目只会从领导者流向其他服务器。
• 领导者选举：再选举领导者时，使用随机计时器。
• 集群成员变更

复制状态机

一致性算法来源自复制状态机。复制状态机通常通过复制日志来实现，每台服务器都会存储一个包含一系列命令的日志，其状态机会按顺序执行这些命令。所有日志都包含相同的命令，且命令顺序一致，因此每个状态机处理的命令序列完全相同。所以关键问题就是如何保证复制LOG的一致性。

服务器上的共识模块会接收客户端发送的命令并将其添加到本地日志中，同时与其他服务器的共识模块通信，以确保即便部分服务器发生故障，所有日志最终仍会包含相同的请求，且请求顺序完全一致。一旦命令完成正确复制，每台服务器的状态机就会按日志顺序执行这些命令，并将执行结果返回给客户端。最终，这些服务器对外呈现为一个单一且高可靠的状态机。

拜占庭故障：节点可能恶意撒谎、发送错误信息、或者不一致的消息。（感觉节点可能被人入侵了，有叛徒）

一致性算法通常有如下特性：

• 非拜占庭故障场景下，都能保证安全性（比如延迟，丢包，重复以及乱序，分区故障即整个网络分为了若干个互相无法联系的分区）
• 只要集群中任意多数派服务器处于正常运行状态，且能彼此通信并与客户端交互，共识算法就能保持完全可用（即具备可用性）
• 不依赖节点的本地时钟，来保证日志的一致性，坏消息/慢消息最多只会导致卡顿，但不会威胁到一致性（不管机器的物理时钟漂移有多严重，Raft 依旧能确保所有副本的日志保持一致。）
• 在常见场景下，只要集群中多数派服务器对一轮远程过程调用（RPC）做出响应，一条命令就能完成执行；少数响应缓慢的服务器不会影响系统的整体性能。

Paxos算法的优势与不足

提升算法可理解性的通用方法

• 问题拆分
• 减少需要考虑的状态数量，

Raft共识算法

Raft就是管理复制日志的算法。

Raft首先选举一个特定的领导者，这个领导者独占管理复制日志的权限。领导者从客户端接收日志条目，将其复制到其他服务器上，并且靠苏服务器什么时候可以安全的将日志应用到状态机（执行的意思吧）。

基于领导者机制，Raft可分为三个独立的子问题：

• 领导者选举
• 复制日志，领导者接收客户端的日志，并且将日志复制到集群，强制其他服务器的日志与自身一致
• 安全，状态机安全。若任一服务器已将某条特定日志条目应用到其状态机中，则其他所有服务器绝不能将不同的命令应用到相同的日志索引位置。（否则一致性就没了）

Raft基础

服务器包括三种状态：领导者，追随者，候选人。

追随者是被动的，只会被动的接收领导者以及候选人的RPC请求并回应，他们不会制动发送请求。

Raft将时间分为任意长度的任期。任期用连续的整数编号，任期以选举开始，若一个候选人获得多数票，则在该任期的剩下时间担任领导者。如果没有候选人获得多数票，则该任期以无领导者状态结束，随后开启一个新任期。

在 Raft 中，任期充当着 “逻辑时钟” 的角色，使服务器能够检测到过期信息。每台服务器内部会存储一个单调递增的任期号码。服务器之间交换信息时，也会交换任期号：

• 若某个候选人（candidate）或领导者（leader）发现自身的任期已过期，会立即退回到追随者（follower）状态
• 若某台服务器收到带有过期任期号的请求，则会拒绝该请求

Raft服务器使用RPC通信，基础共识算法仅需两种类型的RPC：

• 请求投票RPC，由候选人发出
• 追加条目RPC，由领导者发出

为实现最佳性能，服务器会以并行方式发起 RPC。

领导者选举

所有服务器初始状态均为追随者，服务器只要能定时收到领导者或者候选人的消息就会一直保持追随者状态。领导者会向所有追随者定期发送心跳信息（即不携带日志条目的追加条目 RPC）。若某一追随者在一段被称为 “选举超时（election timeout）” 的时间内未收到任何通信，则会认为当前不存在可用的领导者，并发起选举以选出新的领导者。

要发起选举时，追随者会先递增自身的当前任期号，并转换为候选人状态。随后它会给自己投票，并向集群中的其他每台服务器并行发送 “请求投票 RPC”。正常情况下，候选人保持候选状态直到发生下面几种情况：（非正常状态就比如发现自己的任期比别人小）

• 获得选举
• 另一服务器已经确立领导人地位
• 一段时间过去但未产生获胜者

每个任期内，每个服务器只能给一个候选人投票。

在等待投票期间，候选人可能会收到来自另一台声称是领导者的服务器发来的追加条目 RPC。会根据任期号判断：

• 如果该领导者的任期号大于或等于候选人当前的任期号，那么候选人会退回到追随者状态
• 否则，拒绝该RPC，保持候选人状态

上面的第三种情况，如果候选人太多，就会导致不会产生领导者，中止当前任期，进入下一任期投票，这样的无限循环。可以通过随机化选举超时时间的方式来解决这个问题。

日志复制

领导者从客户端请求获取一条需由复制状态机执行的命令，领导者会将该命令作为新条目追加到自身日志中，随后向集群内其他所有服务器并行发送 “追加条目 RPC”，以复制该日志条目。当该条目被安全复制后（具体机制见下文），领导者会将其应用到自身的状态机中，并将执行结果返回给客户端。（若追随者发生崩溃、运行缓慢，或网络数据包丢失，领导者会无限次重试发送 AppendEntries RPC（即便已向客户端返回结果），直至所有追随者最终都存储了所有日志条目）

领导者会决定将日志条目应用到状态机（执行）的时机，这类条目称为已提交条目。Raft保证，已提交的条目具有持久性，最终会被所有的状态机执行。当该条目被复制到集群中多数服务器上时，这些日志挑拨会被标记为已提交。（如下图的条目7，这一操作同时也会提交领导者日志中所有位于该条目之前的条目，包括由前任领导者创建的条目。详见第四小结）

领导者会记录它所知的 “已提交条目” 的最高索引，并将该索引包含在后续的 “追加条目 RPC”中（包括心跳信息），以便其他服务器最终知晓该索引。一旦追随者得知某条日志条目已提交，就会按照日志顺序将该条目应用到自身的本地状态机中。

Raft日志在不同服务器是高度一致的：（下面两点是任何时候都成立的）

• 若不同日志中存在两条索引（index）和任期号（term）均相同的条目，则这两条条目存储的命令完全一致。
• 若不同日志中存在两条索引（index）和任期号（term）均相同的条目，则这两条条目之前的所有日志条目也完全一致。

针对第一个特性：对于某一个特定的任期（即某一个特定的领导者,每个追随者每个任期只能投一次票，所以每个任期只能选出一个领导者）只会在一个特定的索引上创建唯一一个日志条目。（任期号相同意味着领导者能够给这两个服务器append内容，意味着该日志条目前面的内容均与领导者相同）

针对第二个特性：会执行一致性检查。领导者发送 AppendEntries RPC 时，会在请求中包含 “待追加新条目之前的那条日志条目” 的索引和任期号。若追随者在自身日志中未找到索引与任期号均匹配的该条目，则会拒绝接收这些新条目。（这像是一个不断递增的检查，如果中间任意的一个索引出错，都会在下次收到复制日志时检查到问题）

领导者会通过强制追随者复制自己的日志来处理日志不一致问题。追随者日志中与领导者日志冲突的条目，会被领导者日志中的条目覆盖。领导者为每一个追随者维护一个nextIndex，表示下一次发给该追随者的日志条目的位置，追随者如果发现位置不匹配，会拒绝，领导者将nextIndex-1之后再次通过AppendEntries发送，直到该nextIndex与追随者的日志位置一致，（为什么不能直接在reply中返回呢），这时会执行一致性检查，删除冲突的条目，追加领导者的条目。（一旦 AppendEntries RPC 成功，追随者的日志便与领导者日志保持一致，并且在当前任期剩余时间内会一直维持这种一致性。）

安全性

之前的领导者选举以及复制日志还不足以确保每个状态机以相同的顺序执行命令。比如，某个追随者在领导者提交日志期间在关机状态，启动之后又处于领导者状态，则会将自己的条目覆盖已提交的条目。

这里限制了哪些服务器可以被选举为领导者：对于任意给定任期，其领导者（leader）都包含所有在之前任期内已提交的条目。

选举限制

领导者最终都必须存储所有已提交的日志条目。

候选人为了赢得选举，必须联系网络中的多数服务器，（这意味着最新的已提交条目比如存在于这多数服务器中的某一台上，因为要提交日志，也需要用到多数服务器），若候选者的日志至少与该多数服务器中的任意日志 “同样新”，则其候选者日志中必然包含所有已提交条目。

请求投票 RPC 实现了这一限制：该 RPC 会包含候选者日志的相关信息，若投票者自身的日志比候选者的日志 “更新”，则会拒绝为该候选者投票。（注意这里判断的不是已提交日志，而是最新的日志，这可以确定领导者必定拥有所有已提交日志，有几率拥有最新但未提交的日志，从而快速复制到其他服务器上，尽快提交。）

任期号必定是独一无二的，不可能存在两个领导人存在相同的任期号，

如何判断哪个日志最新：

• 任期不同，更大的任期号更新
• 任期相同，更大的索引号更新

提交之前任期的日志

当前任期的领导者发现之前任期的日志已经被提交到多数服务器上时，领导者也不能直接判定其已提交。比如下面的例子：

加粗框代表当前的领导者，在图c中，S1重新当选领导者，这时他即使发现之前任期的日志 2 被复制到了多数服务器上，仍然不能直接判断其已经提交。如果后续正常运行会进入图 e。如果 S1 再次crash，可能会导致 日志 2 被覆盖。（框中的号码并不代表当前机器当前的任期，而是代表该日志是在该任期被发送的）

所以Raft从不通过计数副本的方式来提交之前任期的日志条目，只有领导者当前任期的日志条目才会通过计数副本的方式被提交。（假如当前任期5 提交 任期2 的日志，那么处于这两者之间的任期的服务器 比如 3，4，一旦重新当选，就可能覆盖任期2 的日志）而是通过如下的方式提交：一旦当前任期的某个条目以这种方式被提交，那么由于日志匹配特性的存在，所有之前的条目都会被间接提交。（因为有当前任期的放到最后，所以，3，4任期的服务器不可能再次当选）

安全论证

问：某个追随者的日志数量有没有可能从领导者漏了一条日志A，又不知道从哪里获得了一条日志B

GPT：不会。Follower 永远不可能凭空得到一条日志条目。原因如下：日志的唯一来源
Raft 的日志条目只能来自 Leader 的 AppendEntries RPC。Follower 自己不会生成日志。

问：领导者有没有可能给某一个追随者发送额外的日志，由于某些错误，比如重复发送

GPT：日志是按 index 和 term 定位的，如果该条目已经在 Follower 那里存在（相同 index、相同 term），Follower 会直接忽略这次重复 Append。

这就保证了出现日志不一致（漏日志）就一定能够通过索引和任期号检测到。（也可以为日志匹配特性提供一点支撑）

现在可以论证领导者完整性特性是成立的。反证略。任何任期更大的领导者，必然包含低任期时期提交的条目。（注意不是append是提交）

追随者和候选人崩溃

重试就行了。如果执行后发送通知前崩溃，下次收到相同索引/任期的RPC请求时，忽略就行了。

时序以及可用性

Raft算法的要求是不能依赖时序性——不能因为某些事件发生的时间快慢就让系统产生错误结果。

为了让系统能够正常运行，通常要满足如下条件：

broadcastTime << electionTimeout << MTBF(平均无故障时间)

选举超时通常为 10ms-500ms之间，MTBF通常为几个月或更多。

超时时间，不应该小于故障间隔；不同追随者的超时时间之差应该大于发送一条RPC的往返时间。

日志压缩

Raft的日志会随着客户端请求的增加而不断增长，会占用更多的空间以及时间，如果不丢弃累积的日志，会导致可用性问题。

可以使用快照来实现日志压缩，系统的状态被写入到磁盘中的快照中，如下。

当读取状态到磁盘文件中时，需要保证没有其他进程往状态中写入值，理论上需要锁。但这可能导致服务程序卡顿，另一种做法是，通过fork 复制当前的内存——写时复制，这样：

• 假如，没有其他进程写入，那么我们的快照正常生成
• 假如有其他进程写入，那么操作系统为什么创建新页面，不会通过锁影响其他进程，代价更小。

客户端交互

客户端首次启动时，会连接到一台随机选择的服务器。若客户端首次选择的服务器并非领导者，该服务器会拒绝客户端的请求，并提供其最近已知的领导者相关信息。

就目前的内容而言，Raft仍然无法实现线性化语义。比如客户端连接服务器发送请求后，服务器提交了日志，但给客户端回应前崩溃了。客户端会重发请求消息导致命令被重复执行。解决办法是：让客户端为每条命令分配唯一的序列号，状态机会检查该序列号的命令是否被执行。

如果是只读操作，按理说可以直接返回一个消息即可。但是如果没有额外措施，可能导致服务器返回过期的消息。

比如，任期 1， 领导者提交了日志4，将结果返回给客户端；但是还没有给每个追随者发送 commit就崩溃了。任期 2，另一个服务器当选，这时领导者没有提交日志 4，导致结果是旧的消息。这时需要提交这些旧的日志，安全提交旧任期日志的方法前面提到过，就是在本任期提交一个空日志。

为此，有两个要求：

• 在其任期（term）开始时，可能并不清楚具体哪些条目已提交。为明确这一点，领导者需要提交一条属于其自身任期的日志条目。
• 领导者在处理只读请求前，必须检查自身是否已被罢免。

实现以及评估

7.4 持久化（Persistence） | MIT6.824

需要持久化保持LOG，currentTerm，votedfor，后两者可以避免同一任期出现多个领导者。

Raft1

发送RPC请求时绝对不应该处于加锁状态：

• 假设服务器 A 给服务器 B 发送了请求，那么在服务器 B 的函数中，会涉及到修改状态，也就会加锁，这就意味着：服务器A要同时获取服务器A以及服务器B的两把锁，这时如果服务器B真想要获取服务器B以及服务器A的锁的时候就极有可能出现死锁。一旦涉及到两把锁就很有可能面临死锁的问题。（最好的办法就是将一部分内容移除临界区）
• 浪费时间

关于领导者选举的速度太慢：

• 可能是领导者的心跳以及追随者的超时时间设计不平衡，导致追随者太容易超时，（通过在领导者选举成功后立刻发送心跳能缓解一点问题）
• 后面发现是因为领导者在发送心跳的时候并没有并发发送，导致每发送一次心跳都要花费 2 - 3 秒，这明显超过领导者的心跳间隔，会导致很多追随者竞争领导者。

ZooKeeper

ZooKeeper 的 ZAB 协议 和 Raft 协议 都是 分布式一致性协议，ZAB (ZooKeeper Atomic Broadcast) 用于 广播状态更新（state update），Raft 用于 达成日志共识（log replication）。

ZooKeeper不为 读请求提供线性一致性，这使得它在读的时候可能返回过时的数据，但是这可以换得一点性能的提升。

一致性保证

两个保证：

• 写请求是线性一致的。假设 写请求 A的 结束时间早于 写请求 B 的开始时间——那么 写请求 A 一定 先于 写请求 B 执行。
• 任何一个客户端的请求，都会按照客户端指定的顺序来执行（单个客户端的读写请求是线性一致的）。同一个客户端发送的读写请求顺序在服务器中也是同样的顺序（虽然可能有间隔）（可能在客户端发送请求时需要加上一个序号）

读请求会满足一个条件，假设有两个读请求，读请求1 先执行，完成后执行读请求2，那么读请求 2 观察到的状态一定要不早于读请求 1 观察到的状态。

如果一个客户端正在与一个副本交互，客户端发送了一些读请求给这个副本，之后这个副本故障了，客户端需要将读请求发送给另一个副本。这时，尽管客户端切换到了一个新的副本，FIFO客户端序列仍然有效。

具体原理是：每个Log条目都会被Leader打上zxid的标签，这些标签就是Log对应的条目号。任何时候一个副本回复一个客户端的读请求，回复里面会带上zxid，客户端会记住最高的zxid，当客户端发出一个请求到一个相同或者不同的副本时，它会在它的请求中带上这个最高的zxid。如果副本发现自己没有该Log，则不能响应请求。（这虽然不能保证读请求是最新的，但能够保证读请求是有序的）

ZooKeeper，针对所有服务器来说不是线性一致的，但是，针对某个具体的服务器来说，是线性一致的。假如某个客户端发送一个写请求，成功了，并且获得了一个zxid，那么这个客户端后续发送给副本发送读请求时会附带上zxid，这个副本必须等到自己看到对应zxid的写请求再执行读请求。这保证了单个客户端的线性一致性。（其他服务器没有最新的zxid，读的线性一致性无法保证）

• Zookeeper基于（类似于）Raft框架，所以我们可以认为它是，当然它的确是容错的，它在发生网络分区的时候，也能有正确的行为。
• 当我们在分析各种Zookeeper的应用时，我们也需要记住Zookeeper有一些性能增强，使得读请求可以在任何副本被处理，因此，可能会返回旧数据。
• 另一方面，Zookeeper可以确保一次只处理一个写请求，并且所有的副本都能看到一致的写请求顺序。这样，所有副本的状态才能保证是一致的（写请求会改变状态，一致的写请求顺序可以保证状态一致）。
• 由一个客户端发出的所有读写请求会按照客户端发出的顺序执行。
• 一个特定客户端的连续请求，后来的请求总是能看到相比较于前一个请求相同或者更晚的状态（详见8.5 FIFO客户端序列）。

Zookeeper中包含了3种类型的znode

1. 第一种Regular znodes。这种znode一旦创建，就永久存在，除非你删除了它。
2. 第二种是Ephemeral znodes。如果Zookeeper认为创建它的客户端挂了，它会删除这种类型的znodes。这种类型的znodes与客户端会话绑定在一起，所以客户端需要时不时的发送心跳给Zookeeper，告诉Zookeeper自己还活着，这样Zookeeper才不会删除客户端对应的ephemeral znodes。
3. 最后一种类型是Sequential znodes。它的意思是，当你想要以特定的名字创建一个文件，Zookeeper实际上创建的文件名是你指定的文件名再加上一个数字。当有多个客户端同时创建Sequential文件时，Zookeeper会确保这里的数字不重合，同时也会确保这里的数字总是递增的。

链复制

CRAQ采用的方式与Zookeeper非常相似，它通过将读请求分发到任意副本去执行。它在任意副本上执行读请求的前提下，还可以保证线性一致性。

设计方式：将服务器排列为一种链状，写请求总是发送给 HEAD，读请求总是发送给TAIL。客户端向HEAD 服务器发送信息时，信息会沿着链状的服务器传递一周，然后由TAIL服务器将回复发送回客户端。

虽然很简单高效，但这种方式不能抵御网络分区，也不能抵御脑裂，这意味着他不能单独使用。（总是会有一个外部的权威（External Authority）来决定谁是活的，谁挂了）

Configuration Manager通告给所有参与者整个链的信息，所以所有的客户端都知道HEAD在哪，TAIL在哪，所有的服务器也知道自己在链中的前一个节点和后一个节点是什么。这种架构极其常见，这是正确使用Chain Replication和CRAQ的方式。在这种架构下，像Chain Replication一样的系统不用担心网络分区和脑裂，进而可以使用类似于Chain Replication的方案来构建非常高速且有效的复制系统。

故障恢复：

HEAD如果故障了，就由HEAD的下一个节点来接手并成为新的HEAD。

Aurora

有状态的服务依赖于 web 服务器以及数据库运行，web 服务器主机 宕机了，重启一个就行了，如果是数据库的主机宕机了，那么会导致数据无法访问。就算使用了快照，两次快照之间的数据也会丢失。

为了给用户提供容错的并且支持持久化存储的系统，EBS。EBS类似一个硬盘，它底层基于两个互为副本的存储服务器，使用链复制进行复制。写请求发送给第一个EBS服务器，然后从第二个EBS服务器读取数据。即使一个EBS服务器出现故障，也可以快速启动另外一个EBS服务器加入。

缺点：

• 假如EBS 上层运行一个数据库，那么网络负载会相当大。
• EBS的容错性不够好，两个EBS如果位于相同的数据中心，如果整个数据中心挂了，那么也会丢失容错性。

事务：在整个事务的过程中，都对X，Y加了锁。并且只有当事务结束、提交并且持久化存储之后，锁才会被释放。

RDS（Relational Database Service）

Aurora

将 EBS 变为了专用存储系统。（可以直接收发Log，而不是收发整个的页面，这可以降低网络负载）

仲裁复制机制

最小需要满足：R + W >= N + 1（Aurora的Quorum系统中，N=6，W=4，R=3）

Frangipani

分布式的文件系统，可以存放每一个研究员的home目录也可存放共享的项目目录。

工作站不允许持有缓存的数据，除非同时也持有了与数据相关的锁。

如果你在释放锁之前，修改了锁保护的数据，那你必须将修改了的数据写回到Petal。

缓存一致性

获取数据前加锁，将缓存写入patel提供的磁盘接口，解锁。

故障恢复——预写日志

故障，比如说某个服务器需要写很多数据到patel服务器，在写了一半时，发生故障，

分布式事务

分布式事务主要有两部分组成。第一个是并发控制（Concurrency Control）第二个是原子提交（Atomic Commit）。

事务的正确性：（ACID）

• A，原子性
• C，一致性，执行事务操作前后，必须从一个一致（有效）状态转移为另一个一致状态。（一致——满足所有的约束条件）
• I，隔离性，多个事务不能相互干扰——序列化
• D，持久性，事务提交后，修改是持久的。

并发控制——可序列化的主要工具

原子提交——提供故障恢复的能力

并发控制

主要策略包括：

• 悲观并发控制
• 乐观并发控制