分布式概念与协议

分布式协议

分布式理论概念

1. 分布式数据一致性

分布式数据一致性，指的是数据在多个副本中存储时，各副本中的数据是一致的。

在分布式系统中，数据往往有多个副本。多个副本就需要保证数据的一致性。这就带来了同步的问题，因为网络延迟等因素，我们几乎没有办法保证可以同时更新所有机器中的所有数据，一定会有一刻会出现数据不一致。

那么实际应用中，我们如何既保证数据一致性，同时又不影响系统运行的性能呢？于是一致性级别的概念由此诞生。

2. 一致性级别

1. 强一致性

它要求系统写入什么，读出来的也会是什么，用户体验好，但是实现起来对系统的性能影响比较大
2. 弱一致性

这种级别，不承诺立即可以读到写入的值，也不承诺多久之后数据能够达到一致，但会尽可能的保证到某个时间节点后，数据能够达到一致状态。
3. 最终一致性

最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问能看到最新数据，而是需要一个时间，这个时间之后可以保证一致。

如微信的2小时到账：

3. CAP理论

CAP定理，它指出一个分布式系统不可能同时满足以下三点：

• 一致性 （Consistency）所有节点访问时都是同一份最新的数据副本
• 可用性（Availability）每次请求都能获取到非异常的响应，但不保证数据最新
• 分区容错性（Partition tolerance）分布式系统遇到任何网络分区故障的时候，仍然能够对外提供服务，除非整个网络环境都发生了故障

4. BASE理论

BASE全称是：Basically Available（基本可用），Soft state（软状态）和Eventually consistent（最终一致性）三个短语的缩写。

Base理论的核心思想是：既然无法做强一致性，那么每个应用可以根据自身业务特定，采用适当的方式使系统达到最终一致性。

• 基本可用：出现了不可预知的故障，但还是能用。只是相对正常系统来说可能响应变慢，部分功能缺失。

• 软状态：指系统的数据存在中间状态，并认为该状态不会影响系统的整体可用性。即允许不同副本的数据存在延迟

• 最终一致性：上面说的软状态，不能一直是软状态，必须要有时间期限。在期限过后，应当保证所有副本数据一致

分布式一致性协议

1. 两阶段提交

两阶段提交协议，简称2PC（2 Prepare Commit）,是比较常用的解决分布式事务问题的方式，要么所有参与进程提交事务，要么都取消事务。

阶段一：事务询问。协调者向所有资源发送事务的内容，参与者执行事务并响应结果给协调者。

阶段二：协调者根据上一阶段的结果，向所有参与者发送提交或回滚请求

优缺点

优点：原理简单

缺点：

• 同步阻塞：在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态。
• 单点问题：当协调者出现问题，那么整个二阶段提交都无法运转
• 数据不一致：在阶段二中，执行事务提交时，如果因为局部网络问题导致尚未向所有的参与者发送完Commit请求就宕机的话，就会导致出现数据不一致的现象。

2. 三阶段提交

三阶段提交是二阶段提交的改进版，将2PC的”提交事务请求“过程一分为二，共形成了由CanCommit，PreCommit和doCommit三个阶段组成的事务处理协议。

第一阶段（CanCommit阶段）：类似于2PC的准备（第一）阶段。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

第二阶段（PreCommit阶段)：协调者根据参与者的反应情况来决定是否可以执行事务的PreCommit操作。

• 如果是YES，向参与者发送预提交请求，通知参与者执行事务操作。
• 如果是NO，向参与者发送abort请求

第三阶段（doCommit阶段）：根据上一阶段的结果进行真正的事务提交或中断。

如果第三阶段中，协调者挂掉或者协调者和参与者出现网络问题：参与者都会在等待超时之后，继续进行事务提交

2PC和3PC的对比：

1. 3PC对于协调者和参与者都设置了超时机制（在2PC中，只有协调者拥有超时机制，即如果在一定时间内没有收到参与者的消息则默认失败）,主要是避免了参与者在长时间无法与协调者节点通讯（协调者挂掉了）的情况下，无法释放资源的问题，因为参与者自身拥有超时机制会在超时后，自动进行本地commit从而进行释放资源。而这种机制也侧面降低了整个事务的阻塞时间和范围。
2. 通过CanCommit、PreCommit、DoCommit三个阶段的设计，相较于2PC而言，多设置了一个缓冲阶段保证了在最后提交阶段之前各参与节点的状态是一致的 。
3. PreCommit是一个缓冲，保证了在最后提交阶段之前各参与节点的状态是一致的。

3. NWR协议

NWR是一种在分布式存储系统中控制一致性级别的一种策略。

• N：在分布式存储系统中，有多少份备份数据
• W：代表一次成功的更新操作要求至少有W份数据写入成功
• R：代表一次成功的读数据操作要求至少有R份数据成功读取

NWR值的不同组合会产生不同的一致性效果，当W+R>N时，整个系统对于客户端来讲能保证强一致性。而W+R<N时无法保证。

举例：W=2 R=2 N=3

上述例子W+R>N，这种情况下，Read和Writer肯定会在某个或多个节点有交集，重合就表示强一致性。

4. Gossip 协议

Gossip协议也叫Epidemic协议（流行病协议）。原本用于分布式数据库中节点同步数据使用，后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。

gossip 协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题

Gossip原理

Gossip 协议的消息传播方式有两种：反熵传播 和 谣言传播

• 反熵传播

是以固定的概率传播所有的数据。所有参与节点只有两种状态：Suspective(病原)、Infective(感染)

• 谣言传播

是以固定的概率仅传播新到达的数据。所有参与节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。过程是消息只包含最新update，谣言消息在某个时间点之后会被标记为 removed，并且不再被传播

三种通信方式：推送模式、拉取模式、推/拉模式

优缺点：

综上所述，我们可以得出Gossip是一种去中心化的分布式协议，数据通过节点像病毒一样逐个传播。因为是指数级传播，整体传播速度非常快。

1. 优点

• 扩展性：允许节点的任意增加和减少，新增节点的状态最终会与其他节点一致
• 容错：任意节点的宕机和重启都不会影响Gossip消息的传播，具有天然的分布式系统容错特性
• 去中心化：无需中心节点，所有节点都是对等的，任意节点无需知道整个网络状况，只要网络连通，任意节点可把消息散播到全网
• 最终一致性：Gossip协议实现信息指数级的快速传播，因此在有新信息需要传播时，消息可以快速地发送到全局节点，在有限的时间内能够做到所有节点都拥有最新的数据。

2. 缺点

• 消息延迟:节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网；不可避免的造成消息延迟。
• 消息冗余:节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤；不可避免的引起同一节点消息多次接收，增加消息处理压力

5. Paxos协议

Paxos协议其实说的就是Paxos算法。Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

自Paxos问世以来就持续垄断了分布式一致性算法。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。然而，Paxos的最大特点就是难，不仅难以理解，更难以实现.

Paxos解决了什么问题？

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性

Paxos的版本有Basic Paxos，Multi Paxos，Fast-Paxos，具体落地有Raft和zk的ZAB协议。

Basic Paxos

角色概念：

• Client：客户端
• Proposer：提案发起者。提案者提倡客户端请求，试图说服Accptor对此达成一致
• Acceptor：决策者，可以批准提案
• Learner：最终决策的学习者，学习者充当该协议的复制因素（不参与投票）

Basic Paxos流程图

1. 客户端发起一个请求，它的值为1
2. Proposer发起一个提案，编号为1
3. Acceptor收到的提案编号比本地的大，就通过
4. Proposer就将客户端的值和提案一起再发给Acceptor
5. Acceptor接收后复制给Learners

异常情况下：

1. 如果Acceptor中有一个发生了故障，但是只要大多数是正常的，Basic Paxos协议仍然成功
2. Proposer传递给Acceptor的时候故障了的话，这时需要选出新的Proposer
3. 如果多个提议者发生冲突了，那么也是重新提议。

6. Raft协议

Paxos协议的出现为分布式强一致性提供了很好的理论基础。但是实现比较复杂。然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议Raft。Java，C++，Go 等都有其对应的实现。

Raft协议，引入主节点，通过竞选确认主节点。节点类型有Follower、Candidate、Leader。

Raft相关概念：

1. 节点状态：

• Leader（主节点） ：接受client更新请求，写入本地后，同步给其他副本
• Follower（从节点）：从Leader中接受更新请求，然后写入本地日志文件。对客户端提供读请求
• Candidate（候选节点）：如果follower在一段时间内未收到leader心跳，则判断leader可能故障，发起选主提议。节点状态就会从follower变成Candidate状态，直到选主结束

2. termId：任期号，时间被划分为一个个任期，每次选举后会产生一个新的termId
3. RequestVote：请求投票，candidate在选举过程中发起，收到多数派响应后，成为leader。

Leader 会周期性的发送心跳包给Follower。每个Follower都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成Candidate，进入竞选阶段,通过竞选阶段的投票多的人成为Leader

竞选阶段流程

这个是Raft完整版http://thesecretlivesofdata.com/raft/动画演示

github也提供一个https://raft.github.io/动画演示地址 .

1. 初始阶段下所有节点都是follower节点，每个follower节点都会等待一个随机的竞选超时时间，如果超时时间后，没收到Leader发来的心跳包，就会进入竞选阶段
2. 如果节点A的随机超时时间最短，那么它先进入竞选阶段。节点A会发送投票请求给其他所有节点
3. 其他节点会对投票请求进行回复，如果超一半的节点回复了，那么该Candidate就会变成Leader
4. 之后Leader会周期性的发送心跳给Follower，Follower收到心跳后，会重新开始计时

如果多个Follower成为Candidate并且票数相同，那么就需要重新开始投票。当重新开始投票时，由于每个节点的随机竞选超时时间不同，因此能下一次再次出现多个Candidate并获得相同票数的概率很低。

日志复制

1. 来自客户端的修改会被传入Leader，但修改还未提交，只是写入日志
2. Leader会把修改复制到所有follower
3. Leader会等待大多数的Follower也进行了修改，然后才将修改提交
4. 此时Leader会通知所有的Follower让它们提交修改，此时所有节点的值达成一致

网络分区

面对网络分区，Raft也可以保持一致。

举例说明：

当发生分区后，肯定会因为接受不到Leader的心跳而重新发生选举，就会出现两个Leader。这样就分成了2部分。

• Leader B节点+Follower A
• Leader E+Follower C+Flollwer D

原来的节点总数是5，大多数等于3.那么客户端往LeaderB上发的消息都是未提交的。只有发给E才能被提交。

等网络恢复后E节点Termid较大成为Leader节点，并同步节点数据。Leader B降为Follower节点

---

如果是NodeB、NodeA、NodeC在一边，NodeD和NodeE在另一边，这种分区情况是怎么样的呢？

NodeD和NodeE发现没有Leader了，但是他们只有2个节点，没法达到大多数原则，选不了主。所以消息只能发往Leader B节点。还是保证了一致性。

7. Lease机制

Lease机制，翻译过来是租约机制，是维护分布式系统数据一致性的一种常用工具。

Lease机制有如下几个特点：

• Lease是颁发者对一段时间内数据一致性的承诺
• 颁发者发出Lease后，不管是否被接受，只要Lease不过期，颁发者都会被按照协议遵守承诺
• Lease的持有者只能在Lease的有效期内使用承诺，一旦Lease超时，持有者需要放弃执行，重新申请Lease

Lease机制能解决什么问题呢？

分布式系统中，如何确认一个节点是否正常工作。考虑如下场景

Node1是主节点，剩下4个副本，如果Node1发生网络抖动（Node1本身是正常的，没有宕机），导致从节点无法接收到心跳。他们就会再选出一个主节点。

这种场景解决思路有4种：

• 设计能容忍双主的协议
• Raft协议：通过TermId大的通过给低的
• Lease机制
• 去中心化-Gossip协议

Lease如何处理这种情况呢？

1. 引入了一个中心节点，负责下发有时效性的Lease给主节点（这个有效期内不管你出啥问题，我就认你）
2. 如果网络出现问题了，重新选了主节点。
3. Lease未过期，新的主节点去申请会被拒绝
4. 网络恢复了，原来的主节点可以继续续期
5. 如果是原来的主节点是真的宕机了，那么它的有效期过后，新的主节点就能申请成功了。

Lease时间长短一般取1-10秒。太短网络压力太大，太长则收回承诺的时间也长，影响可用性

Lease的容错

1. 主节点宕机 Lease的机制天生可容忍网络、Lease接收方的出错，时间即Lease剩余过期时长
2. 中心节点异常 中心节点异常会使得所有节点没有Lease，解决办法是使用小集群作为颁发者
3. 时差问题 中心节点和主节点之间可能存在时差问题，需要校对

应用：

1. GFS(Google 文件系统)中，Master通过lease机制决定哪个是主副本，lease在给各节点的心跳响应消息中携带。收不到心跳时，则等待lease过期，再颁发给其他节点。
2. chubby中，paxos选主后，从节点会给主颁发lease，在期限内不选其他节点为主。另一方面，主
   节点给每个client节点发送lease，用于判断client死活。