分布式系统模型

拜占庭将军问题

拜占庭将军主要用于解决共识问题，三个将军决定攻打拜占庭，只有三个人一同进行攻打才能够成功，否则则会失败，因此需要三者之间通过信使来进行通信，以求达成共识，整个系统是处于不信任状态的，即将军可能会是叛徒，向其他的将军传递错误的信息，信使也是不可靠的，可能会被俘虏或者数据为假。

将军即对应分布式系统当中的节点，节点不仅会发生故障或者宕机，其中会有一些节点为叛徒，可能恶意篡改和传播错误信息，信使即对应着网络通信，在此条件下网络通信也为不可靠的。 image.png

系统模型分类

网络链路模型

  • 可靠链路 ：可靠传递，没有重复，不会无中生有，但是对于消息可能会出现排序
  • 公平损失链路：
    • 公平损失：如果发送方和接收方都正常运行，发送方不断进行尝试，消息最终会送达
    • 有限重复：消息只会重复发送有限次
    • 不会无中生有
  • 任意链路：最弱的网络模型，允许任意的网络链路执行任何的操作，可能会有软件恶意篡改数据包

节点故障模型

  • 崩溃-停止(fail-stop) ：一个节点停止工作后就永远不会恢复
  • 崩溃-恢复(fail-recover):允许节点重启后继续执行剩余的步骤，一般通过持久化存储的方式
  • 拜占庭故障：故障节点不止会当机，还有可能以任意方式偏离算法，甚至恶意破坏系统

时间划分

可以分为同步和异步：

  • 同步指一个消息的响应时间在有限且已知的一个时间范围内
  • 异步的消息的响应时间为无限的，不知道具体的消息到达时间

分布式系统数据基础

水平分区算法

范围分区

根据指定的关键字拆分成若干连续范围，问题是无法对于分区关键字以外的关键字进行范围查询，数据本身分布不均时容易造成某些节点负载较高

哈希分区

对指定关键字使用哈希函数进行分区，传统的哈希函数的问题如果添加新的分区则需要对原本所有的数据进行全部rehash，对于hashtable来说，可以使用可扩展哈希表的方式降低扩展的负载。但是此处只是使用了哈希函数，因此需要对哈希函数进行改进采用一致性哈希

一致性哈希

将整个哈希值抽象成一个圆环，而节点分布在圆环上，数据存储在按照顺时针方向遇到的第一个节点上，此时如果添加或者移除一个节点，只会有相邻的另外一个节点收到影响，避免的全局rehash 一致性哈希同样存在数据倾斜的问题，即如果一个节点下线，其存储的数据会全部转移到相邻节点，导致该节点的负载过高，解决方法即为采用虚拟节点的方式，一个物理节点对应多个虚拟节点，使数据分布更加均匀。 image.png

复制

单主复制

数据首先写入到主节点上，之后再由主节点复制到从节点上，这个过程可以为同步的，也可以为异步的，同步可以保证从节点一定能够读取到最新的消息，但是对客户端的响应速度就减慢，即影响写请求的性能，异步则以牺牲数据一致性和持久性来换取响应速度。

此外还有半同步的方式，即对于一个节点采用同步的方式，其他的节点为异步的方式，这样可以一定程度上保证响应速度，并且在主节点当机之后一定有一个和主节点完全一致的从节点能够直接顶替主节点。

单主复制的性能瓶颈为只有一个主节点来响应写请求。

多主复制

通过多个主节点来接受写入请求以提升写性能，显而易见会带来冲突问题，主要解决方式有：

  • 客户端解决，产生冲突时，将所有的冲突数据返回给客户端，由客户端选择合适的数据
  • 最后写入胜利，通过每条请求上携带的时间戳或者自增ID
  • 因果关系跟踪：happen - before image.png

无主复制

平等的对待每个节点，每次写入尝试向所有的节点进行写入，读取也对所有的节点进行读取。基于大多数原理，即对于N个节点的情况，如果$W + R > N$ 则可以保证读与写之间存在一个交集，从而保证新写入的数据一定能够被读取到。

在该配置下，如果一次写入有W个节点给予响应即认定写入成功，读取也发送给多个节点，由于存在冲突问题，客户端根据读取到的版本号来解决冲突，采用版本号最新的数据作为结果

除了$W + R > N$之外，还需要$W > N/2$ ,来保证数据的串行化修改，即两个不同的写请求不能够同时成功修改同一份数据。每次写入要求写入大多数即可保证两次写入之间存在一个交集，从而发现冲突。但是即便$W < N/2$的话，那么就意味着$R > N/2$，那么在一次检索过程当中就一定能够发现冲突的数据，此时可以根据时间戳来进行修复，保留最新的数据

CAP定理

在一个异步的网络环境中，对于一个分布式读写存储系统，只能满足一下三个特性之二

  • 一致性(Consistency)
  • 可用性(Availability)
  • 分区容错性(Partition Tolerance) 一致性为客户端进行一次读取，总能给获取到最新的数据（与数据库一致性进行区分）可用性为每次请求都能获得一个非错误的响应，但不保证获取的数据为最新的。分区容错性为节点由于网络分区而导致消息丢失的情况下，系统仍能正常运行。

CAP三角通常指的是三者无法得兼，只能选其中之二，但是对于实际的应用，所期待的是其能够抵抗网络分区，因此CAP又可以表述为在出现网络分区时保证分区容错性情况下，是要求一致性还是要求可用性。

反之则为如果不出现网络分区，则可以同时保证一致性和可用性

一致性模型

一致性模型首先需要与数据库的一致性约束进行区分。其次，一致性的概念也不是分布式系统当中独有的，（内存一致性）具体来说指的是：在并发编程中，系统和开发者之间的一种约定，如果在开发这遵循约定，则执行读操作或斜操作的结果是可预测的。

线性一致性

最强的一致性级别，通常可以使用Linearizability表述，线性一致性的直观理解或者说非严格定义可以表述为所有操作看起来为原子的，整个系统看起来只有一个节点。

线性一致性的严格定义为：给定一个执行理事，执行历史根据并发操作可以扩展为多个顺序历史，只要从当中找到一个合法的顺序历史，那么该执行理事就是线性一致性的。

在执行历史当中又可以分为顺序的和并发的，顺序则为时间A的结束时间早于时间B的开始时间，而并发则是两个时间当中存在重叠的部分。在生成顺序历史时，顺序关系必须由先发生的指向后发生的，而并发的则可以进行编排，最后如果能够获取到一个读写请求都合法的顺序历史，则称其为线性一致性的。

线性一致性最困难的就是需要一个全局时钟，从而来确定时间发生的时间顺序

顺序一致性

只要求一个客户端的操作在排序后保持顺序不变，不同客户端之间的先后顺序可以任意改变。通过改变顺序之后，可以得到一个合乎逻辑的顺序历史。

由于各个客户端之间的顺序可以改变，因此没有全局时钟的限制。

在一个社交网络应用当中，通常不关心看到的所有朋友的帖子的顺序，但是对于某个具体的朋友，以正确的顺序去显示更加符合逻辑性。

因果一致性

要求必须以相同的顺序看到因果相关的操作，没有因果关系的并发操作可以被不同的进程以不同的顺序观察到。如先发帖才能有该帖子的评论体现了发生于…..之前(Happens-Before)关系。

最终一致性

在某个阶段，系统个节点处理客户端的操作顺序可以不同，读操作也不需要返回最新的写操作的结果。

只要在最终的状态下，即不再执行写操作，读操作将返回相同的，最新的结果。

以客户端为中心的一致性模型

即不关注多个客户端操作的并发结果，只站在单一客户端的角度上进行分析，可以分为：

  • 单调读：如果客户端读到关键字x的值v，那么之后的读取只能够读取到比v更新的值
  • 单调写：同一个客户端的写操作在不同的副本上必须以同样的顺序执行
  • 读你所写(Read Your Write):写操作完成后，同一副本或者其他副本上的读操作必须能够读取到写入的值
  • PRAM(Pipelined RAM):也称为FIFO一致性，同一个客户端的多个写操作，将被所有的副本按照同样的执行顺序观察到
  • 读后写(Write Follow Read)：如果先读到了写操作w1的结果v，那么一周的写操作w2保证给予v或比v更新的值

分布式共识

状态机

状态机包含一组状态、一组输入，一组输出，一个转换函数和一个输出函数，和一个独特的初始状态。状态机从初始状态开始，每个输入都被传入转换函数和输出函数，产生一个新的状态和输出，在收到新的输入前，状态机的状态保持不变。

对于共识，就是在一个可能出现任意故障的分布式系统中的多个节点对某个值达成共识。由于状态机的特性，这个问题可以很好的使用状态进行解决：

采用日志作为输入，从相同的位置以相同的顺序读取日志内容并执行，则会产生相同的输出，结束在相同的状态上，备份到不同的节点上并输入给状态机，从而即可使从节点达到和主节点一样的状态。

Paxos

基本概念

每个节点通过提案(proposal)的方式来推进状态的改变，因此每个提案需要提案编号(proposal number)和提案值(proposal value)

paxos通过轮次+服务器id的形式来组成一个唯一的提案值，即<n,server_id>，paxos解决冲突的方法即为根据提议号的大小，对同一个值只接受第一次的提议

算法角色：

  • 客户端：客户端向分布式系统发起一个请求，并等待回应
  • 提议者(Proposer)：提议者收到客户端的请求，提出相关的提案，试图让接收者去接受提案
  • 接收者(Accepter)：也叫投票者(Voters)，投票接受或者拒绝提议者的提案，如果超过半数接受着接受，则提案批准
  • 学习者：不参与决议提案，只学习提案值并执行

算法流程

这里讨论Basic Paxos，只针对一个值达成共识，而不是像raft那样进行完整的日志复制，即指对一个日志的entry进行共识，如果想要实现如raft的效果，需要使用multi paxos，但是multi paxos与raft还存在着一点差别。

第一阶段

第一阶段提议者发送RPC称为phase 1a，也叫做prepare阶段，在这个阶段只发送提议号，而不设计具体内容

1

send Prepare(++n)

响应的过程称为phase 1b，称为promise阶段，在这个过程当中，主要根据提议号来判断是否存在冲突：

  • 如果prepare当中的n大于之前接受的所有提案编号，那么返回promise进行响应，并且承诺之后不再接受任何小于n的提议，如果对于该值接受了某个提案，那么就返回前一次的提案号与提案值
  • 否则忽略该请求，恢复一个拒绝响应
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

if (n > max_n) {
	max_n = n
	if (proposal_accepted == true) {
		respond: PROMISE(n,accepted_N,accepted_VALUE)
	} else {
	respond:PROMISE(n)
	}
} else {
	respond with fail message
}

第二阶段

第二阶段发送 rpc 时称为 phase 2a，Accept 阶段，如果提议者能够收到半数以上的 phase 1b 的正确回应，则进行 phase 2a 阶段，如果 phase 1b 的响应当中存在提议值，那么就使用该提议值，否则提议者可以自由决定提议值

1
2
3
4
5
6
7
8

if (success > n/2) {
	if (contains_acc_val()) {
		val = accepted_VALUE
	} else {
		val = VALUE
	}
	send Accept(ID,val)
}

第二阶段的响应被称为phase 2b，如果在此之前没有接受过比n大的提案，那么久接受n，保存提案

1
2
3
4
5
6
7
8
9

if (n > max_n) {
	proposal_accepted = true
	max_n = n
	accepted_N = n
	accepted_VALUE = VALUE
	respond:Accepted(N,VALUE) to proposer and all learners
} else {
	respond with fail message
}

对于basic paxos，其过程和两阶段提交比较相像，即均存在一个prepare的过程，先去询问从节点是否能够执行命令或者进行写入，当收到肯定的答复之后，进行第二轮去真正执行命令。只不过二者的目的略有不同，分布式事务的两阶段提交意在所有节点共同参与，因此需要所有的节点均给予应答，因此存在阻塞的问题，而paxos意在形成共识，因此只需要有超过1/2的节点能够正确响应即可。

活锁

系统中可能存在两个提议者不断交叉进行提议，A在proposal之后从节点又收到了B的proposal，从而A的accept请求被拒绝，之后A再进行proposal，产生了有个更大的proposal number，从而B的Accept请求也会被拒绝，因此系统产生一种活锁的状态，解决方法和raft一样，引入随机的超时时间来避免互相竞争导致的活锁问题。

Multi Paxos

paxos只是用于完成一次共识，而对于分布式存储的多条日志，则需要对于每条日志均运行一次paxos，从而让从节点能够拿到所有的日志，称为multi paxos。 后续有空再进行补充

Raft

raft已经比较熟悉了，这里就进行简单的补充

安全性与活性

选举过程中需要保证安全性与活性：

  • 安全性只在一个任期当中，只有一个leader能够被选举出来，相关保证为：
    • 一个节点在一个任期当中只能够进行一次投票，并且投票信息需要进行持久化存储
    • 只有获得超过半数的选票之后才能够称为leader，从而保证不会同时有两个leader当选
  • 活性指的是要确保系统最终能够选举出一个leader，因此需要在选不出leader时有的节点会超时触发新的一轮选举，并且为了防止陷入活锁问题，raft同样需要设置一个随机的超时时间(150ms-300ms)

延迟提交

考虑以下这种情况，上一任期的leader为s1，并且s1已经提交了index = 3的日志，此时s1宕机，重新进行leader election，S5当选为leader，之后S5进行日志复制时，就会覆盖掉S2 S3当中index = 3的日志，但是该日志已经在s1为leader时进行了提交，从而导致已经提交的日志丢失。 image.png 针对这种情况，需要进行额外的限制：

  1. 日志必须存储在超过半数的节点以上
  2. Leader 必须看到超过半数的节点上还存储着至少一条自己任期内的日志

这就是所谓的延迟提交，换句话说，leader不能够提交不属于自己任期的日志，对于之前的日志，leader只能在提交当前任期日志时，顺带进行提交。即只有以下的情况时，leader S1才能够对index = 3的日志提交 image.png no-op空日志

通过延迟提交的方式，可以解决掉已提交日志被覆盖的问题，但是存在的问题是leader需要等待客户端发来一条请求才能够生成对应的日志，否则index = 3的日志则会迟迟得不到提交，导致对应的请求阻塞，无法收到响应。

解决方式即为当leader上线之后，立马向自身写入一条没有内容的空日志，并进行复制与提交，通过提交空日志来顺带提交之前的日志，从而推动整个系统

处理旧的领导者

在不存在网络分区的情况下，对于旧的领导者处理很简单，只需要进行一次rpc通信，即可通过比较携带的term来完成。而对于网络分区的情况，由于raft在CAP当中选择了CP，因此处于较少分区的leader无法形成大多数的共识，因此无法提交日志和响应客户端，但是身份依旧为leader，客户端就会继续和他进行通信，因此最好让该leader及时退位。

相关优化即为check quorum，如果leader发现与自己能保持通信的follower<= n/2，则主动退位

实现线性一致性

线性一致性的实现方案主要有三种，最简单的为将读请求也写入到日志当中，之后即可按照日志的顺序来严格执行，从而保证顺序。但是会产生写日志和复制日志的额外开销。 相关优化有两种，分别为read index和lease read：

ReadIndex

  1. 将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。
  2. 向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。
  3. Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。
  4. Leader 执行 read 请求，将结果返回给 client。

在这个过程当中同样需要no-op来保证当前leader的commitIndex为集群当中最新。

只有commit了日志才能够视为顺序关系，而对于那些在commitIndex之后写请求，将其视为与当前的读请求为并发关系，因此可以不读取到其中的内容，虽然与Log Read获取到了不一样的结果，但是依旧是满足线性一致性的。

在使用ReadIndex时，可以采用在follower出进行读取的方式来提高吞吐量，即follower向leader去索取一个ReadIndex，后续等待自身的appliedIndex == ReadIndex时仅可进行读取，对于local read，还有其他的实现方案，留在etcd当中进行分析

LeaseRead

Leader使用正常的心跳机制来位于一个lease，心跳开始的时间标记为start,如果leader的心跳被多数派确认，那么在start+electionTimeout/clockDriftBound的时间内，Leader均为有效的leader，不会因为其他节点进行选举而退位，因此可以安全的处理只读查询，结果全部满足线性一致性。

性能优化

raft涉及到的主要性能优化即为批处理和流水线，这两个都在etcd当中进行了实现，这里就不额外进行分析了

分布式事务

分布式事务可以理解为单机事务的变体，主要分为两种类型，一种是同一份数据需要在多个副本上更新，一个事务需要更新所有的副本，而另外一种为事务所需要的数据存储在不同的节点上，一次事务操作需要跨越多个事务，保证在分布式情况下，同样能够令事务遵循ACID，其中持久性可以通过WAL的形式来解决，一致性通常不在讨论范围内，主要需要克服的就是原子性与隔离性，需要通过原子提交和并发控制来进行解决

原子提交

  • 协定性：所有进程决定出同一个值，即要么所有进程全部提交，要么所有进程一同中止事务
  • 有效性：只要有一个事务决定中止事务，系统最终将中止事务
  • 终止性：可以分为弱中止条件和强中止条件
    • 弱中止条件：如果没有故障发生，所有进程最终都会做出决议
    • 强中止条件没有发生故障的进程最终会做出决议

两阶段提交

角色上分为协调者(Coordinator)和参与者(Participants),协调者负责进行协调算法的各个阶段，参与者参与到事务执行的各个部分

阶段：

第一阶段称为准备阶段：

  1. 协调者向所有参与者发起信息，询问是否可以提交事务，等待参与者响应

  2. 参与者检查执行所需的条件，如果发现自身事务执行的都成功，则回应yes，反之no 第二阶段称为提交阶段：

  3. 如果所有的参与者第一阶段都回应了yes，协调者向所有的参与者发送信息，请求提交事务

  4. 参与者收到信息后进行事务的提交，并响应协调者

  5. 协调者如果收到了全部的正确响应，确认事务成功提交

  6. 如果其中第一阶段有一个参与者响应了no，则协调者指示参与者中止事务

  7. 参与者利用第一阶段执行时保存的信息进行回滚

  8. 中止完成后响应给协调者，收到所有参与者的信息后，确认事务的中止 相关故障

  • 第一阶段参与者回复协调者时超时，会导致协调者一直等待，解决方法为引入一个超时时间，超时则认为该参与者投了反对票（可解决）
  • 协调者在向参与者发送消息后立刻发生了故障，除非协调者恢复，否则会一直阻塞下去
  • 在第二阶段发生了网络分区，协调者只向一部分的参与者发送了提交信息，此时进行读取则会产生不一致性
  • 在第二阶段，如果协调者发送信息之后宕机，该信息之发送给了一个参与者，而该参与者收到信息并执行后也宕机，此时则会完全不知道系统的状态，如果盲目提交或中止，宕机的参与者如果恢复过来并且状态不一样则会引发数据不一致问题

基本的2PC的根本问题是无法解决单点故障问题，一旦有某个节点宕机就会引发如阻塞或者数据不一致的问题，解决方法为通过raft等方式将原本的单个节点转换为集群的形式，避免单点故障

三阶段提交

三阶段提交的提出用于解决两阶段提交的阻塞问题，在原本两个阶段的中间添加了一个预提交阶段(Pre-Commit)，在预提交阶段，将第一阶段的结果发送给所有的参与者，这样在协调者宕机之后，依旧可以获取集群的状态，判断应该中止还是提交。

流程

准备阶段：

  1. 协调者向参与者发送信息询问是否能够执行提交事务
  2. 参与者判断自身是否能够执行事务，但是并不真正执行事务，只是判断基本条件，给予响应 预提交阶段
  3. 协调者发送预提交信息
  4. 参与者如果满足条件则执行事务，并记录日志，响应协调者 提交阶段
  5. 协调者发送提交信息
  6. 参与者提交事务并给予相应

通过额外的预提交，在提交阶段时，如果协调者发生宕机，则可以根据之前的信息重新选举出一个新的协调者，来避免协调者称为单点故障阻塞系统，而如果在预提交阶段发生宕机，则可以随意选出一个协调者，由于没有执行，从而不存在数据一致性的问题。

但是三阶段提交无法解决所有问题，会收到网络分区的影响：在两个分区内会各存在一个协调者，从而导致数据不一致。 2afd4adccd587a9582fe139c94eb00ed.jpeg

paxos提交

paxos提交主要用于解决原本三阶段提交在发生网络分区时，随意选举协调者的问题，通过共识算法来选举leader，从而避免数据一致性问题。此处仅是对一个值或者结果来形成共识，因此采用的为basic paxos

主要分为三个角色：

  • 资源管理者：相当于2PC 3PC当中的参与者，负责事务的一部分执行与提交，而在paxos当中，充当提议者(非leader)
  • 领导者：协调paxos算法的执行，可以视为paxos和资源管理者之间的桥梁，领导者同时也是接受者
  • 接受者：与资源管理者组成paxos集群，存储结果，通过paxos来避免网络分区 67654767e435f73934b09ea3eec7ec0b.jpeg
  1. paxos算法开始于某个资源管理者，资源管理者决定提交事务，向leader发送一个BeginCommit
  2. leader收到BeginCommit之后，响应一个prepare消息给所有的资源管理者
  3. 之后所有的资源管理者根据条件去判断自身是否提交事务，如果能够提交事务，则发起一个commit的提案，否则为abort的提案
  4. Leader 根据提案的结果，判断此次事务是否能够提交，之后将消息发送给资源管理者，资源管理者根据 leader 的结果进行提交或者回滚

相比raft，basic paxos的结构更为松散一些，raft所追求的就是follower完全复制leader的日志，从而在状态机上达成共识。而basic paxos只是对于某个值达成共识，提案者的概念并不等同于leader，提案者仅仅是进行提案而已，本身可以不参与数据的决策。

paxos提交的结构更像是在事务的执行者外接了一个paxos,paxos只是用来存储结果，和防止网络分区的问题，实际上并不参与事务的执行或者判断的过程。

Saga事务

实现分布式事务的代价较高，并且可能存在一些长事务，其中甚至可能会涉及到手动输入等人工介入等问题。使用常见方式处理，通常性能较低。而对于一些不需要完全进行隔离的事务，可以采用Saga事务。

Saga事务通过一些列的子事务组成，子事务按照原本的方式进行执行，保证ACID，Saga事务整体通过补偿事务的方式来保证整个事务的原子性。即如果由T1,T2组成，T1提交之后，T2需要回滚，则运行一个T1的补偿事务，来撤销掉T1做出的操作。

Saga事务最大的问题是无法保证隔离性。