大数据之分布式理论_分布式原理 大數據

1. 分布式理论基础

1.1. 2PC和3PC(解决一致性)

1.1.1. 一致性是什么

一致性问题就是相互独立的节点之间如何达成一项决议的问题。分布式系统中，进行数据库事务提交(commit transaction)、Leader选举、序列号生成等都会遇到一致性问题。

1. 系统满足一致性的条件：

• 全认同：所有N个节点都认同一个结果
• 值合法(validity): 该结果必须由N个节点中的节点提出
• 可结束(termination): 决议过程在一定时间内结束，不会无休止地进行下去

2. 实现一致性面临的问题

• 消息传递异步无序(asynchronous): 现实网络不是一个可靠的信道，存在消息延时、丢失，节点间消息传递做不到同步有序(synchronous)
• 节点宕机(fail-stop): 节点持续宕机，不会恢复
• 节点宕机恢复(fail-recover): 节点宕机一段时间后恢复，在分布式系统中最常见
• 网络分化(network partition): 网络链路出现问题，将N个节点隔离成多个部分
• 拜占庭将军问题(byzantine failure): 节点或宕机或逻辑失败，甚至不按套路出牌抛出干扰决议的信息

1.1.2. 一致性的两个属性及一致性简单解决

• 强一致性：所有节点状态一直、同进退
• 可用性 ：分布式系统无间断堆外提供服务

工程实践上根据具体的业务场景，或保证强一致(safety)，或在节点宕机、网络分化的时候保证可用(liveness)。2PC、3PC是相对简单的解决一致性问题的协议，下面我们就来了解2PC和3PC。

（1） 3PC(三阶段提交)

它分成两个阶段（提议+提交/回滚）

• 第一阶段，先由coordinator进行提议(propose)并收集其他节点的反馈
• 第二阶段，根据反馈决定提交(commit)或中止(abort)事务。我们将提议的节点称为协调者(coordinator)，其他参与决议节点称为参与者
• 若coordinator提议后宕机会使节点阻塞，所以有一个协调者(coordinator watchdog)备份coordinator，当coordinator宕机时watchdog接替其工作，通过询问各节点的状态决定阶段二是否提交。

（2） 3PC(三阶段提交)

3PC可解决异步网络+节点宕机恢复的系统一致性，它分成三个阶段（提议+准备提交+提交/回滚）:

• 第一阶段，先由coordinator进行提议(propose)并收集其他节点的反馈
• 第二阶段，coordinator给各节点发送准备提交的指令，各节点接到指令后在保证可回滚的前提下可以锁定资源
• 第三阶段，coordinator收到各节点的ack应答后决定是否提交。
• 3PC同样需要watchdog备份coordinator

由于有了阶段二的准备提交阶段，各节点不会阻塞等待提交；并且当有节点宕机时coordinator通过ack获知哪个节点宕机，可以直接commit，当宕机节点恢复后再询问已提交的节点实现同步保证一致性。

1.2. CAP定理

1.2.1. CAP描述

• C(consistency):数据一致性，表示服务节点宕机则立刻取消该服务，即所有请求都必须得到该服务的正确响应，对调用者而言数据具有强一致性(原子性)
• A(availability):服务可用性，表示允许服务节点宕机恢复，宕机时保留服务可用性，所有请求在一定时间内可能无法得到正确响应，但可以终止请求。
• P(partition-toleranc):分区容错性，表示在网络分区 ( 部分服务失败导致完整系统被割断；丢包 ) 的情况下仍能对外提供服务（分布式系统必须满足）

1.2.2. CAP分析

1. P(分区容错)，现实情况下我们面对的是一个不可靠的网络(丢包)、有一定概率宕机的设备(系统被割断)，这两个因素都会导致Partition，因而分布式系统实现中 P 是一个必须项。
2. CA中的A表示强一致性(必须得到服务的正确响应)，强一致性要求多节点组成的被调要能像单节点一样运作、操作具备原子性，数据在时间、时序上都有要求。除了强一致性，还有：

• 顺序一致性(sequential consistency)：保证同一个进程的指令顺序不变，不同进程的指令可以相互交叉（顺序一致性描述链接）
• 最终一致性(eventual consistency)：放宽对时间的要求，在被调完成操作响应后的某个时间点，被调多个节点的数据最终达成一致
• 工程实践中，较常见的做法是通过异步拷贝副本(asynchronous replication)、quorum/NRW，实现在调用端看来数据强一致、被调端最终一致，在调用端看来服务可用、被调端允许部分节点不可用(或被网络分隔)的效果。

3. 跳出CAP
   延时(latency)，它是衡量系统可用性、与用户体验直接相关的一项重要指标。CAP理论中的可用性要求操作能终止、不无休止地进行，除此之外，我们还关心到底需要多长时间能结束操作，这就是延时，它值得我们设计、实现分布式系统时单列出来考虑。
   要实现强一致性，多个副本数据一致，必然要增加延时。所以可以考虑增加延时，将强一致性改变为最终一致性。

1.2.3. 总结

CAP在工程中的实际意义是：
(1)调用端保证可用性A；
(2)被调用端保证最终一致性(EC);
(3)允许出现网络分区，并保证服务可用(P);

1.3.逻辑时钟

现实生活中物理时间有统一的标准，而分布式系统中每个节点记录的时间并不一样，即使设置了 NTP 时间同步节点间也存在毫秒级别的偏差。因而分布式系统需要有另外的方法记录事件顺序关系，这就是逻辑时钟(logical clock),主要有一下三种：

1.3.1 Lamport timestamp

分布式系统中按是否存在节点交互可分为三类事件，一类发生于节点内部，二是发送事件，三是接收事件。Lamport时间戳原理如下：

• 每个事件对应一个Lamport时间戳，初始值为0
• 如果事件在节点内发生，时间戳加1
• 如果事件属于发送事件，时间戳加1并在消息中带上该时间戳
• 如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1
  图中A、B、C代表三个节点，各节点上的时间从0开始顺序进行，事件时间在方格中表示。

1.3.2 Vector timestamp

Vector clock是在Lamport时间戳基础上演进的另一种逻辑时钟方法，它通过vector结构不但记录本节点的Lamport时间戳，同时也记录了其他节点的Lamport时间戳。Vector clock的原理与Lamport时间戳类似，使用图例如下：

节点B上的第4个事件p (A:2，B:4，C:1) 与节点C上的第2个事件 q(B:3，C:2) 没有因果关系， Tq[B] > Tp[B] 且 Tq[C] < Tp[C]，则认为p、q同时发生属于同时发生事件。

1.3.3 Version timestamp

分布式系统中数据一般存在多个副本(replication)，多个副本可能被同时更新，这会引起副本间数据不一致，Version vector的实现与Vector clock非常类似[8]，目的用于发现数据冲突。下面通过一个例子说明Version vector的用法：
- client端写入数据，该请求被Sx处理并创建相应的vector ([Sx, 1])，记为数据D1

• 第2次请求也被Sx处理，数据修改为D2，vector修改为([Sx, 2])
• 第3、第4次请求分别被Sy、Sz处理，client端先读取到D2，然后D3、D4被写入Sy、Sz
• 第5次更新时client端读取到D2、D3和D4 3个数据版本，通过类似Vector clock判断同时发生关系的方法可判断D3、D4存在数据冲突(可能只接受一个数据)，最终通过一定方法解决数据冲突并写入D5

2. 分布式理论进阶

2.1. Paxos协议

---

引用自简书：理解分布式一致性:Paxos协议之Multi-Paxos

---

Paxos协议在节点宕机恢复、消息无序或丢失、网络分化的场景下能保证决议的一致性，是被讨论最广泛的一致性协议。

2.1.1. Basic Paxos

Paxos中的节点存在5中角色：client, acceptor, proposer, learner, 和 leader，实际实现中，一个服务可以扮演多个角色。

• Client：是请求的发起端，Client发送请求给分布式系统并等待回复；
• Acceptor：是消息请求的存储器，请求消息发送给Acceptor后，只有大多数Acceptor确认接收此消息时该消息才会被存储。
• Proposer：可看做Client的代理，将请求发送给Acceptor并等待Acceptor确认，当发生消息冲突时会尝试解决。
• Leaner：learner依附于acceptor，备份已经接受的请求消息，用于习得已确定的决议。如果部分acceptor因宕机等原因未知晓已确定决议，宕机恢复后可经learner采用pull的方式从其他acceptor已确认的消息习得。
• Leader： Paxos需要一个Leader来确保分布式系统可以按步骤进行下去。这里的Leader其实就是一个Proposer, Paxos协议会确保只有一个Proposer会被当做Leader。

Basic Paxos可分为以下两个阶段：

1. Prepare阶段：

• 一个Proposer会创建一个Prepare消息，每个Prepare消息都有唯一的提议id=n； n必须比该Proposer之前用过的所有编号都大，一般来说我们可以以数字递增的方式来实现这个编号， Proposer把[n,v]发送给Acceptor（v表示提议的值）
• Acceptor回应提议ID为n的proposer自己曾接受过ID最大的提议，同时保证(promise)不再接受ID小于n的提议

2. Accept阶段：

• Proposer收到多个Acceptors返回过来的消息之后，会从中选择编号最大的一个消息所对应的值z，并把他作为Accept请求的值 （n,z） 发给Acceptor。
• 当Acceptor接收到了Proposer的确认消息请求（n,z），如果该Acceptor在Prepare阶段的时候没有promise只接收>n的消息，那么该（n,z）消息就必须被Acceptor确认(即记录曾接受的ID最大的提议，因proposer需要问询该信息以决定提议值)。 当（n,z）消息被Acceptor确认时，Acceptor会发送一个Accepted（n,z）消息给Proposer 和所有的Learner。当然在大部分情况下Proposer和Learner这两个角色可以合并。

2.1.2. Multi Paxos

如果Leader足够稳定的话，Phase 1 里面的Prepare完全可以省略掉，从而使用同一个Leader去发送Accept消息。当然我们还要对请求消息做一些改造，这里我们在请求里面加入了轮数I，每过一轮，I+1 。

1. 下图我们展示一个基本的Multi-Paxos一次执行交互流程，系统有1个Client，1个Proposer， 3个Acceptor， 1个Learner。
   
2. 上面我们讲到在Multi-Paxos中，如果Leader足够稳定的话，在接下来的执行中，phase 1 的请求其实是可以被省略的，那么接下来我们看一下被省略的整个流程。
   这里round number需要+1,表示已经进入下一轮了。
   
3. 在Basic-Paxos中我们区分了很多角色，有Clients，Proposers, Acceptors and Learners。实际上Proposers, Acceptors and Learners可以合并成一个，我们把它统称为Server。下面是合并之后的序列图。
   
4. 同样的，当Leader很稳定的时候，我们可以在接下来的执行中忽略Phase 1. 如下图所示：
   

2.2.常见一致性协议Raft和Zab

2.2.1. Raft

Raft论文翻译地址

Paxos偏向于理论，在生产环境中基于Paxos实现一个正确的分布式系统非常难，Raft的更利于理解、更易于实行。

(1)为达到更容易理解和实行的目的，Raft将问题分解和具体化：

Raft结构相关重点：
1

• 唯一Leader统一处理变更操作请求，简化了实现方法。，
• 一致性模块相互通信保证节点间操作日志副本(log replication)一致(保证指令追加的顺序和内容一致)，节点运行相同状态机(state machine)运行相同顺序和内容的指令得到一致结果。，
• 以(leader任期)term作为逻辑时钟(logical clock)保证时序，log中index保存追加位置；log条目会记录两者，一致性则体现在log中的term和index都相同，

保证日志一致性相关重点：
1

• 所有服务维护nextIndex(指令id)保证指令完整一致，leader追加指令时nextIndex初始化为log的index+1，follower同步log会从和leader最初不一致的地方追加覆盖，实现日志同步及恢复
• leader必须存储了所有已提交的指令日志；只有 leader 当前任期(term)内的日志条目才通过计算副本数目达到半数的方式来提交，之前的所有日志条目会随当前term提交而被间接地提交

leader选举相关重点：
1

• 随机设置candidate选举超时时间，使各candidate任期号很快就各不相同，防止多个follow同时成为candidate且同时超时后再将term+1还以相同term选举导致的分票无法选出leader

(2)Candidate：

1. follower选举时将自己视为candidate并将自己之前的term+1参与选举，同时向其他candidate发送自己当前的任期号。
2. 其他candidate若发现接收的term不小于自己的term时则放弃选举变回follower；若小于则保持candidate等待超时或选举成功，超时则再将term+1重新发起选举。

(3)Raft的具体过程如下：

1. Client发起请求，每一条请求包含操作指令
2. 请求交由Leader处理，Leader将操作指令(entry)追加(append)至操作日志(使用index记录日志追加位置)，紧接着对Follower发AppendEntries请求，尝试让操作日志副本在Follower落地
3. 如果Follower多数派(quorum)同意AppendEntries请求，Leader进行commit操作、把指令交由本机的状态机处理(如果我们能按顺序将指令作用于状态机，它就可以产生相同的状态和相同的输出)
4. 状态机处理前要保证follower已经同步了交给状态机处理的指令日志条目，状态机处理完成(即对follower执行相同顺序的相同指令)后将结果返回给Client
5. 一致性算法的工作就是保证复制日志的一致性。 每台服务器上的一致性模块接收来自客户端的命令，并将它们添加到其日志中。 它与其他服务器上的一致性模块通信，以确保每个日志最终以相同的顺序包含相同的命令，即使有一些服务器失败。 一旦命令被正确复制，每个服务器上的状态机按日志顺序处理它们，并将输出返回给客户端。 这样就形成了高可用的复制状态机。

(4)raft遵循几条性质：

• 每次任期内只能有一个Leader
• leader只追加日志条目，不能重写或者删除日志条目
• 如果两个日志条目的index和term都相同，则在两个日志中的当前追加条目及它们之前的日志条目也完全相同
• 如果一条日志被commited过，那么大于该日志条目index的日志都应该包含这个点(可以理解为高水位)
• 如果一个server将某个特定index的日志条目交由状态机处理了，那么对于其他server，交由状态及处理的log中相同index的日志条目应该相同

(5)nextIndex：

宕机、网络分化等情况可引起Leader重新选举(每次选举产生新Leader的同时，产生新的term)、Leader/Follower间状态不一致。Raft中Leader为自己和所有Follower各维护一个nextIndex值，其表示Leader紧接下来要处理的指令id以及将要发给Follower的指令id， leader 将所有 nextIndex 的值都初始化为自己最后一个日志条目的 index 加1，LnextIndex不等于FnextIndex时代表Leader操作日志和Follower操作日志存在不一致，这时将从Follower操作日志中最初不一致的地方开始，由Leader操作日志覆盖Follower，直到LnextIndex、FnextIndex相等。

2.2.2. Zab

引用了博客园：《从 Paxos 到> Zookeeper——分布式一致性原理和实践》
引用了简书：《Zookeeper——一致性协议:Zab协议》

(1)Zab协议描述：

• Zab：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议），是Zookeeper内部用到的一致性协议。相比Paxos，Zab最大的特点是保证强一致性(strong consistency，或叫线性一致性linearizable consistency)。

(2)Zab协议重点：

Zab结构重点：Zab就是崩溃恢复和消息广播两种模式循环切换的过程
1

• 消息广播：类似于2PC，加入了队列实现异步解耦防止同步阻塞，提高性能
  

• 崩溃恢复：一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式 。崩溃恢复包括Leader选举和数据恢复。
leader中不能包含未提交的Proposal，且leader中包含最大的zxid的事务

• Zab为每一个事务配置了一个唯一的64位zxid，高32位代表Leader唯一epoch(年代)，低32位随新事务出现而递增
  

保证数据一致性相关重点
1

• 同步：Leader维护了一个保持同步Follower的列表，故障恢复即 Follower 将所有尚未同步的已提交事务 都从 Leader 服务器上同步过来并且应用到内存数据中以后，Leader 才会把该 Follower 加入到同步Follower 列表中

• 抛弃：flowers只听从epoch(zxid高32位)大的Leader的指令，每重新选举都会将epoch+1。如果flower中有上一个Leader未提交的Proposal则当前Leader会发出让其回滚的指令

Leader选举相关重点
1

• leader中不能包含未提交的Proposal，且leader中包含最大的zxid(即epoch大且事务id大)的事务

(3)Zab协议过程：

当整个集群启动过程中，或者当 Leader 服务器出现网络中弄断、崩溃退出或重启等异常时，Zab协议就会 进入崩溃恢复模式，选举产生新的Leader。

当选举产生了新的 Leader，同时集群中有过半的机器与该 Leader 服务器完成了状态同步（即数据同步）之后，Zab协议就会退出崩溃恢复模式，进入消息广播模式。

这时，如果有一台遵守Zab协议的服务器加入集群，因为此时集群中已经存在一个Leader服务器在广播消息，那么该新加入的服务器自动进入恢复模式：找到Leader服务器，并且完成数据同步。同步完成后，作为新的Follower一起参与到消息广播流程中。

2.2.3. Zab和Raft的对比总结

相同点：

• 唯一Leader：Zab 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有唯一一个 Leader负责发送请求到follower，用来保证一致性（Paxos 并没有使用唯一 Leader 机制保证一致性）。
• 半数成功机制：采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。
• 逻辑时钟都包含Leader信息：Zab的逻辑时钟是epoch(Leader世代)+事务id组成的zxid；Raft的逻辑时钟就是term(Leader任期)，但由于两者实现一致性的方式不同，Raft通过nextindex标记指令序号。

不同点

• 一致性实现方式不同：Zab为广播数据，Raft为发送指令、保存指令日志、状态机执行指令
  （Zab为每个事务分配一个全局递增编号zxid，Raft为每个指令分配一个初始化为lnextIndex=index+1）
• 同步机制不同：Zab的Follower通过Learner实现同步，Raft通过状态机执行指令实现同步。
• 数据发送路径不同：Zab数据发往每个Follower的FIFO队列实现异步解耦广播，Raft指令发往每个Follower的同步模块实现解耦并保证各Follower接收的指令顺序和内容相同(各同步模块相互通信)。
• Leader选举细节不同：Zab是Leader必须包含全部提交的Proposal且zxid最大，若zxid相同则选择Zookeeper集群中myid最大的为Leader；Raft的Leader必须包含全部已经提交的指令且term最大，采取随机超时选举时间保证term值不同则确保选出Leader。

3.分布式锁的获取