分布式技术

发表于 更新于 分类于 阅读次数： 本文字数： 18k 阅读时长 ≈ 16 分钟
引言：分布式技术——不要浪费时间去试图为异步分布式系统设计面向任意场景的共识算法

本文相关Link：

分布式基本概念

一致性问题

分布式最核心的问题——一致性问题

一致性

一致性Consistency：很多台服务器（分布式集群）对外表现就像是单机环境一样，一直呈现稳定一致的状态

（注意：一致性强调的是系统对外体现一致的状态，并不考虑结果是否正确）

一致性要求三方面：（这三个概念无需刻意去记，知道一致性要求：有限时间、结果需要共识且合理即可）

  • 可终止性 Termination：有限时间内给出一致的结果（保证能够在一定的时间内提供服务）
  • 约同性 Agreement：不同节点最终完成决策的结果相同（系统要么不给出结果，要么给出的结果必须是达成共识的）
  • 合法性 Validity：决策的结果必须是某个结点提出的提案（即A节点认为结果是a，B节点认为结果是b，那么最终结果必须是a或b，不能是c）

举个例子：比如售票案例有A、B两个售票口售卖去往北京的机票，还剩最后一张，分别售卖给a与b，而ab几乎同时下单，那么此时该把这张票给谁呢？

分布式系统解决问题的核心秘诀：把不同时空发生的多个事件进行全局唯一排序，而且这个顺序是共识的。

最简单的方法就是，a与b分别有时间戳，我们比较时间戳就可以得到最终谁更快一点（之后我们还会用到比较时间戳的思想）

但是A如果与B相隔很远，时钟计时可能不准确（即使是Google的分布式数据库Spanner，面对不同的数据库，也有10ms的延迟）因此我们应该对事件排序，而不是一味的追求绝对的时间戳

这个例子里：在一定时间内返回给a、b谁拿到了票，就是可终止；不同节点在排序后，得到a事件早于b事件的共识，这就是约同性；系统最终将票给了a、b其中之一就是合法性

一致性的分类

一致性根据更新值后是否可以立即读取到分为：

  • 强一致性：写操作后可以立即读到最新数据

    • 顺序一致性（因果一致性）：约束力较强

      要求：

      • 所有进程看到的全局执行顺序（total order）一致（否则数据副本就不一致了）；

      • 并且每个进程看自身操作的顺序（local order）跟实际发生顺序一致。

      比如一个进程执行A、B；另一个进程执行C、D；那么所有进程都应该看到A先于B、C先于D（即所有进程都应该看到ABCD、ACDB、CDAB、CADB、CABD、ACDB中的一个 total order）进程内部应该是串行的，进程之间可以并行

    • 线性一致性（原子一致性）：约束力最强，在顺序一致性前提下增加了进程间的操作顺序要求（更新后立即可以读取到最新的值）

  • 弱一致性：写操作后不能保证立即读到最新数据

    • 最终一致性：即允许出现临时的不一致，但要在一定时间内达到一致

（PS：对于一致性分类的说法很多版本不一样啊，无非就是把强或弱里面的一种单拿出来，个人认为这里的分类比较好）

注意

一致性的概念有区别

  • 在ACID中的C，指的是状态的一致性，通过二阶段提交来解决
  • 在CAP中的C，指的是线性一致性，比如Paxos、Raft

所以下文中提到一致性，注意区别指的是哪一个

共识

共识 Consensus：特指在分布式系统中多个节点之间对某个提案Proposal达成一致看法的过程

提案：提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是主节点……等等。可以认为任何可以达成一致的信息都是一个提案。

达成共识需要解决的两个问题：

  • 如何提出提案？
  • 如何让多个节点达成共识？

注意：一致性和共识一样吗？

不一样！很多人把Paxos和Raft看做一致性算法，这是错误的，他们俩是共识算法

  • 共识 Consensus：一致的意见
  • 一致性 Consistency：根据是否可以立即读到最新数据分为强弱一致性

FLP不可能原理

Fischer、Lynch 和 Patterson （FLP）三位科学家于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位计算机科学家）奖

FLP 不可能原理：在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法

不要浪费时间去试图为异步分布式系统设计面向任意场景的共识算法。

在分布式系统的同步与异步：

  • 同步：a节点执行完成等待b节点一定时间（分布式系统的时钟误差存在上限）同步情况下，如果b节点超时，那么就能进一步判断其宕机还是网络出现故障
  • 异步：a节点执行完成后通知b节点（这个时间没有上限）这就造成无法判断某个消息迟迟没有被响应是哪里出了问题

FLP不可能原理实际上说明：对于允许节点失效情况下，纯粹异步系统无法确保共识在有限时间内完成

CAP原理

CAP 原理：分布式系统无法同时确保一致性（Consistency）、可用性（Availability）和分区容忍性（Partition），设计中往往需要弱化对某个特性的需求

在现实情况中，我们往往在C与A之间取舍

  • C 一致性：线性一致性（可以看第一节），要么读到同一份数据，要么都失败
  • A 可用性：系统能在有限时间内完成对操作请求的应答；
  • P 分区容忍性：系统中的网络可能发生分区故障（成为多个子网，甚至出现节点上线和下线），即节点之间的通信无法保障。网络故障不应该影响到系统正常服务。

CAP原理认为分布式系统最多只能保证满足其中两种特性：其中AP与CP使用比较多

  • AP：适合于结果一致性不敏感的应用，允许一段时间后再保持同步。
    • 网站静态页面、CDN、实时性较弱的查询类数据库
    • 简单分布式同步协议：Gossip、CouchDB、Cassandra
    • 设计时，我们对于普通的数据就可以处理为AP
  • CP：适合于结果一致性敏感的应用
    • MongoDB、Redis、MapReduce
    • Paxos、Raft等共识算法
    • 设计时，我们对于元数据就应该保证CP
  • AC：网络分区出现概率较小，但很难完全避免，舍弃P意味着放弃分布式系统
    • 两阶段提交
    • Zookeeper

OLTP与OLAP

ACID与BASE是对不同场景对CAP三者的不同的取舍的结果：

  • 对于OLTP（Online transaction processing）联机事务处理：比如传统的关系型数据库，相关操作主要是CRUD增删查改

  • 对于OLAP（Online analytical processing）联机分析处理：注重数据的分析

因为不同的要求，所以OLTP就要求实时性、小数据量、处理事务和查询；而OLAP就要求实时性要求不高，数据量大。

ACID 酸

关系型数据库的事务处理基本满足ACID原则。

  • Atomic 原子性：事务要么成功要么失败
  • Consistency 一致性：事务执行前后，对数据库的完整性没有破坏（实体完整性、域完整性、参照完整性）
    • 实体完整性：主键须唯一
    • 域完整性：限制字段满足预设类型的值（比如需要是日期或是字符串或是数值）
    • 参照完整性：父记录存在，子记录才能存在（外键）
  • Isolation 隔离性：不同事物之间互不影响
  • Durability 持久性：数据存储后永久存在，除非进行删除操作

BASE 碱

BASE是AP的延伸

分布式数据库的要求，其实是分布式系统实现ACID成本过高，退而求其次得到BASE要求。

BASE是AP的延伸拓展，可以理解为BASE放弃了C（最终一致性）

  • Basic Availability 基本可用：系统内部可能有部分宕机，但是依然可以提供服务
  • Soft-state 软状态：系统不要求保持强一致状态
  • Eventual consistency 最终一致性：系统需要在一段时间后保证数据一致。

软状态只是描述系统的一个特点，对于基本可用与最终一致性我们来讨论一下具体实现：

如何保证BA

如何保证BA基本可用？一套组合拳

  • 削峰填谷：（削峰）分不同时间段售卖，比如8点抢深圳的票、9点抢北京的票；（填谷）比如在QPS较少的时间段开放此类高并发服务
  • 延迟响应：自己提交的请求会排队等待处理，可能推迟几分钟
  • 体验降级：
    • 比如用较为模糊的图片替代高清图片
    • 保证核心功能可以使用，停止提供非核心功能
  • 过载保护：请求限流，消息队列满载之后，拒绝之后的请求或是清空一部分请求

这部分和Redis防止缓存雪崩、缓存击穿、缓存穿透异曲同工

如何保证E

一般有三种方法保证最终一致

  • 读时修复：在读取数据的时候检测数据是否一致
  • 写时修复：在写入数据的时候，监测数据是否一致，写失败就缓存数据，定时重传（对系统的消耗最小，不需要额外的判断）
  • 异步修复：最常用的方式，定时对账，保证数据副本一致

多阶段提交

在mysql介绍过两阶段提交，当时记录了mysql先写redo log后写bin log，这个思想来源于分布式事务的多阶段提交方法。

这一部分的相关资料：

二阶段提交

既然在分布式场景下，直接提交事务可能出现各种故障和冲突，那么可将其分解为预提交和正式提交两个阶段，规避风险。

二阶段提交协议（Two-phase Commit Protocol，简称 2PC）是分布式事务的核心协议：

定义了一个事务管理器 TM（Transaction Manager）与一个资源管理器RM（Resource Manager），所有RM向TM汇报自身活动状态，由TM根据各RM汇报的状态（完成准备或准备失败）来决定各RM是“提交”事务还是进行“回滚”操作。

协议分成了两个阶段：（TM与RM也有称为协调者与参与者）

  • phase1：预提交（也有称投票阶段）：
    1. TM通知各RM执行事务
    2. 各RM执行事务，但是不提交
    3. RM将执行情况汇报给TM
    4. RM阻塞等待TM的指令
  • phase2：正式提交：
    • 如果所有RM均执行完成：通知所有的RM进行提交
    • 如果有一个RM执行失败：通知所有的RM进行回滚

两阶段提交存在的问题：

  • 同步阻塞：各RM执行事务后会阻塞，等待TM指示
  • 单点故障：非常依赖TM这一个点，如果TM宕机，其他RM会一直等待
  • 数据可能不一致：比如在第二阶段，TM告知RM可以提交后，有RM没有收到或是宕机

三阶段提交

为了弥补二阶段存在的问题，三阶段提交将二阶段的第一个阶段拆为了两个部分，变成了三阶段：

  • phase1：询问提交（注意这个阶段不执行事务，因此这个阶段不会阻塞）
    1. TM询问RM是否可以进行提交操作
    2. RM根据自身状况回复一个预估值：是或否
  • phase2：预提交（如果事务开始执行，那么执行完成后他们会阻塞）
    1. TM检查所有收到的答复，根据不同情况返回不同请求
      • 全部为是：TM对RM发起执行事务的请求
      • 一个或多个返回否或等待超时：TM对RM发送abort请求，RM收到后中断事务
  • phase3：正式提交
    • 如果所有RM均执行事务成功：
      1. TM向所有RM发送commit请求
      2. 所有RM进行提交操作，释放相关资源
      3. RM返回给TM其提交结果
    • 如果一个或多个失败或等待超时：
      1. TM向所有RM发送回滚指令
      2. RM执行回滚
      3. 返回回滚操作

如果phase3中，RM迟迟接收不到TM的commit或rollback请求，将在等待超时后继续commit（二阶段中如果出现这种情况会一直阻塞）

三阶段提交存在的问题：

三阶段提交解决了阻塞问题和单点故障问题，但是还是会有数据不一致的情况（比如TM发送rollback请求，但是有的RM没有收到这个消息，在等待超时后，他们依然会commit）

两阶段提交协议中所存在的长时间阻塞状态发生的几率还是非常低的，所以虽然三阶段提交协议相对于两阶段提交协议对于数据强一致性更有保障，但是因为效率问题，两阶段提交协议在实际系统中反而更加受宠。

XA协议

2PC的传统方案是在数据库层面实现的，如Oracle、MySQL都支持2PC协议

为了统一标准减少行业内不必要的对接成本，需要制定标准化的处理模型及接口标准，国际开放标准组织Open Group定义分布式事务处理模型DTP（Distributed Transaction Processing Reference Model）

DTP模型定义TM和RM之间通讯的接口规范叫XA，简单理解为数据库提供的2PC接口协议，基于数据库的XA协议来实现2PC又称为XA方案。

一句话就是：XA接口方案实现了2PC（比如Mysql XA）

TCC

Try-Confirm-Cancel 预留-确认-撤销：

可以将TCC理解为是业务层的二阶段提交，而二阶段提交是处理数据库层的事务的

  • Try：对应二阶段提交phase1，对业务系统做检测及资源预留
  • Comfirm：对应二阶段提交的phase2的commit，一般Try成功都能Confirm成功
  • Cancel：对应二阶段提交的phase2的rollback，业务执行出错，那么就进行回滚

在需要分布式事务能力时，优先考虑现成的事务型数据库（比如 MySQL XA），当现有的事务型数据库不能满足业务的需求时，再考虑基于 TCC 实现分布式事务。

拜占庭将军问题

拜占庭是古代东罗马帝国的首都，现土耳其君士坦丁堡（后改名为伊斯坦布尔）

所谓的拜占庭将军问题就是：一组拜占庭将军分别各率领一支军队共同围困一座城市，他们商量进攻还是撤退，而且将军中可能出现叛徒

二忠一叛难题：

假设现有A、B、C三个将军商量进攻，要求必须至少有两个将军一起进攻才能胜利：

此时假如C是间谍，那么如果A告诉B、C进攻，B告诉A、C撤退，此时进攻撤退比为1:1，而间谍C给A发送进攻，给B发送撤退。

那么A看到2:1，会进攻，最后全军覆没；B看到1:2会撤退

那么如果你是指挥，你会如何破局呢？

Leslie Lamport莱斯利·兰伯特（Paxos算法创始人、LaTeX的La、图灵奖得主，大佬）提出了两个解决这个问题的办法：

  • 口信消息型：多轮交互

  • 签名消息型：给消息加密

口信消息型

前提：n个将军，最多容忍m = (n-1)/3位叛徒，最多需要m+1次交互

（推到过程参考大佬的论文，我们只需要记住结论）

比如上面的二忠一叛问题，就需要再加一个将军D（4个人，个叛徒）就可以防止叛徒捣乱。

我们规定首先发出指令的为指挥官，其余的为副官，当忠诚将军首先发出指令时：

  1. A向B、C、D发送进攻的指示（如果没有收到信息默认是撤退）
  2. 副官B、C、D之间互相发送作战信息
  3. B、D之间互相发送进攻的消息；B与C、D与C发送进攻，此时叛徒C无论给B与D发送撤退，影响不了局面（进攻与撤退比：D收到2:1、B收到2:1）

当叛徒首先发出指令时：

  1. C告诉A进攻，告诉B、D撤退
  2. A、B、D之间相互交流，发现撤退2大于进攻1，于是都不会进攻

签名消息型

使用签名保证，最多需要m+1次交互

  • 忠诚将军签名无法伪造
  • 任何人都能验证消息真伪

这样就可以不增加人数而达到共识

比如还是A、B、C：

  1. A通知B、C：A要进攻
  2. B通知C：A、B要进攻
  3. C是叛徒，通知B：A、C撤退

此时B就能判断出C叛变了，从而忽略他的消息，参与进攻

（如果叛徒C先发出消息也将这样）

签名消息就是带有数字签名的消息，假设现在bob要给alice发送消息“我爱你”，为了防止被人篡改，我们使用非对称加密算法比如（RSA）

bob发送时：

  1. 将消息“我爱你”先进行数字摘要（比如MD5），生成一个摘要Digest
  2. 然后使用私钥对Digest加密，生成签名Signature1
  3. 发送时发送：消息+Signature（两个都要发送）

Alice接收时：

  1. Alice接收到的消息是“我不爱你”，对这个消息也进行摘要，生成Signature2
  2. Alice使用公钥对Signature进行解密，得到Signature1
  3. 对比Signature1与Signature2，Alice就知道消息被篡改了

共识算法

拜占庭错误 Byzantine Fault：指存在故意伪造恶意信息的节点引发的错误

非拜占庭错误Non-Byzantine Fault：指断电、网络拥塞等等故障（Crash或Fail-Stop）引发的错误

针对解决不同的错误场景有不同的共识算法：

  • 解决非拜占庭错误——CFT（Crash Fault Tolerance）
    • Poxos（1990年）
    • Raft及其变种（2014年）
  • 解决拜占庭错误——BFT（Byzantine Fault Tolerance）
    • 确定性系列算法：一旦达成共识就不可逆转，即共识是最终结果
      • PBFT（Practical Byzantine Fault Tolerance，1999）
    • 概率算法：指共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，最终成为事实上结果（比如比特币出现两个链时，会由下一个区块决定哪一个是最长链）
      • PoW（Proof of Work，1997）

近几年还有其他的算法：

  • XFT（Cross Fault Tolerance，2015 年）：提供类似 CFT 的处理响应速度，并能在大多数节点正常工作时提供 BFT 保障
  • Algorand（2017年）：基于 PBFT 进行改进，通过引入可验证随机函数解决了提案选择的问题，理论上可以在容忍拜占庭错误的前提下实现更好的性能

可靠性指标

可靠性（Availability），或者说可用性，是描述系统可以提供服务能力的重要指标

几个9指标

几个9表示：每年允许服务出现不可用时间的参考值。

  • 单点的服务器系统至少应能满足两个 9（99%，每年允许87.6h不可用）；
  • 普通企业信息系统应能满足三个 9（99.9%，每年允许8.76h不可用）；
  • 少数领先企业（如亚马逊、甲骨文）产品能实现四个9甚至更多（99.99%，每年允许52min不可用）。
  • 大型金融和电信系统指标是五个9（99.999%，每年允许5min不可用）。
  • 五个 9 以上的系统十分罕见，要实现往往意味着极高的成本。

MTBF与MTTR

描述系统出现故障的可能性和故障出现后的恢复能力

  • MTBF：Mean Time Between Failures 平均故障间隔时间，即系统可以无故障运行的预期时间（越大越好）
  • MTTR：Mean Time To Repair，平均修复时间，即发生故障后，系统可以恢复到正常运行的预期时间（越小越好）

分布式算法

Paxos

Paxos

无论将数据分为几个阶段进行提交，都避免不了出现数据不一致的问题，直到出现第一个共识算法

Paxos：第一个共识算法，解决非拜占庭问题

论文中为了描述问题编造了一个虚构故事：在古代爱琴海的Paxos岛，议会如何通过表决来达成共识。议员们通过信使传递消息来对议案进行表决。但议员可能离开，信使可能走丢，甚至重复传递消息。

兰伯特的Paxos包括两部分：

  • Basic Paxos：多节点如何就一个值达成共识
  • Multi-Paxos：多节点如何对一系列值达成共识

三种角色

算法提到了三种角色：

  • 提案者Proposer：提出一个提案，等待大家批准chosen为决议value；
    • client承担这个角色（但其实，接收到client请求的节点才是提案者）
    • 负责接入与协调：接入client的请求，协调发起二阶段提交
  • 接受者Acceptor：对提案进行投票
    • server承担这个角色
    • 负责协商和存储数据：参与二阶段提交，存储最终达成共识的数据
  • 学习者Learner：获取共识结果，不参与投票过程
    • 可以是client也可以是server
    • 学习者一般是为了备份数据，被动接受数据，不参与共识过程
    • 负责存储数据：接收达成共识的值

Paxos算法基本过程很类似于二阶段提交

Basic-Paxos

现在假设我们实现了一个分布式集群，提供只读KV存储服务，有两个客户端，一个要修改x为3，另一个要修改为7：

Phase1：如图所示，我们用[n, v]来表示一个提案，n表示提案的id，v表示提案的值；图中有两个提案者，proposer1的提案为x=3，proposer2的提案为x=7；图中有三个接收者，他们之前均没有共识过任何提案

Paxos phase1

  1. proposer1发出提案[1, ]（注意：第一个阶段并不需要指定提议的值）；
  2. Acceptor1接收到请求[1, ]，承诺之后将拒绝所有小于1的请求；Acceptor2同理
  3. proposer2发出提案[5, ]
  4. Acceptor1接收到请求[5, ]，承诺之后将拒绝所有小于5的请求，由于之前没有共识过任何提案，所以返回给提案者一个空值[,]；Acceptor2、Acceptor3同理（如果之前共识过，那么应该返回提案者曾经共识的提案的id）
  5. Acceptor3接收到请求[1, ]，由于1<5，因此拒绝响应这个请求
  6. proposer1接收到来自于Acceptor1、Acceptor2的响应，开始进入第二阶段（注意：接受者有3个，只需要接收到>2个的响应，就可以进入第二阶段）
  7. proposer2接收到来自于Acceptor1、Acceptor2的响应，开始进入第二阶段

Paxos phase2

Phase2：

  1. proposer1决定设置x为3，发出请求[1, 3]
  2. proposer2决定设置x为7，发出请求[5, 7]
  3. 由于1<5，Acceptor1、Acceptor2、Acceptor3均拒绝响应
  4. proposer2的请求，得到了共识，于是设置x的值为7

假设，如果Acceptor3第二阶段收到信息延迟了，而新的提案者Proposer3提议要把x改为6，如图所示

Paxos 其他情况

  1. proposer3发出提议[9, ]
  2. Acceptor1、Acceptor2将更新接收到的最大编号为9，返回曾经共识过的提案信息[5, 7]
  3. Acceptor3将更新接收到的最大编号为9，因为曾经没有共识过，所以返回空值[,]
  4. proposer3收到两个值，但是提示说这个值已经共识过了，所以会把自己的请求由[9, 6]改为[9, 7]
  5. Acceptor1、Acceptor2、Acceptor3接收到并更新自己的值为7（其实没有发生变化）

下面对Paxos的两阶段提交做一个总结：

阶段1Prepare阶段：

  • 提案者向接受者发送计划提交的提案编号n的Request，不需要指定设定的值，只需要发送提案编号
  • 接受者收到n，检查回复过的提案的最大编号M
    • 如果n > M：发送ACCEPT的Response，并且携带上上一个共识的编号P，且更新M_i的值为n，不再接受小于n的提案
    • 如果n < M：拒绝响应

阶段二Commit阶段：

  • 某个提案者如果收到大多数接受者的回复（表示大部分人收到了 n），则准备发出带有n与值v的提交消息
  • 还是比较n与M
    • 如果n >= M则更新值（注意这里包括=这个选择）
    • n < m则忽略

1、如果只有Acceptor1共识了值，Acceptor2、3都没有的话，出现proposer3要设置为6的情况，那么结果会是7还是6呢？

有可能是6，也有可能是7，取决于谁先共识（由于网络的不稳定，无法判断是哪一个值）

2、题目设计的是一个只读的KV服务器，如果是一个可读写的KV服务器，是不是就能改变值了？

不能。Basic Paxos是一个共识算法：通过提案的值就不会改变了！！

Basic Paxos只能就单值达成共识，属于一个基础算法；Multi-Paxos，才能在实际场景中落地。

3、怎么保证提案号不会重复呢？

提案号可以利用时间戳+分区的办法，比如给Acceptor1分配1-5，Acceptor2分配6-10等等，再加上时间戳标记，就可以保证既是递增，也不会冲突

Multi Paxos

Basic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用了

兰伯特提到的 Multi-Paxos 是一种思想，不是算法：Multi-Paxos 算法是一个统称，通过多个 Basic Paxos 实例实现一系列值的共识的算法

Multi-Paxos的想法就是多次执行Basic-Paxos实例，但是这么做存在几个问题：

  1. 可能因为提案者的编号冲突，导致没有一个提案能得到大多数准备响应，协商失败需要重新协商。（比如五个接受者，同时出现三个提案，得票为1:2:2）
  2. 2轮RPC通讯（二阶段）往返消息多，耗费性能。

如何解决这两个问题？有两个方案：引入领导者Leader和优化Basic Paxos（个人理解优化Basic Paxos是引入领导者后才有的优化，因此方案可以理解为引入领导者一个）

引入Leader后：

  1. 将提案者缩减为一个，这样就不存在出现同时提案导致协商失败的情况。（Multi-Paxos没有说明如何选取领导者，不同的算法有自己的实现）
  2. 可以省略掉阶段一，直接进行阶段二，提升了效率

但是同样的，引入了Leader也带来了几个问题：

  • 增加了选举Leader的复杂度
  • 只有Leader可以写，分布式系统中容易出现性能瓶颈
  • 存在单点故障问题

Chubby的Multi-Paxos的实现简单了解

Chubby是谷歌提供的经典的分布式锁服务，提供了粗粒度的分布式锁、对于小数据的可靠存储、关注可靠性一致性扩展性而不是性能

Chubby实现了单提案者，它的选举机制是：通过执行Basic Paxos算法投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。

​ 比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。

Chubby是谷歌基于Multi-Paxos的落地实现

Raft共识算法

Raft 算法属于 Multi-Paxos 算法，是Multi-Paxos的落地实现。

Raft算法：通过一切以领导者为准的方式，实现一系列的共识和各节点日志的一致

Raft的角色身份

角色身份即服务器的节点状态，Raft有三种状态：

  • 领导者（Leader）：负责三个任务，处理写请求、管理日志复制、不断发送HeartBeat信息
  • 跟随者（Follower）：接收处理Leader的信息，如果Leader心跳超时，就会变成Candidate
  • 候选人（Candidate）：向其他节点发送请求投票的RPC消息，赢得多数选票的就晋升为Leader

Leader的选举机制

Raft给每一个Follower都随机了一个超时时间，时间到期就会变为Candidate，然后给其他的节点发送请求投票的消息，获得多票者晋升为Leader

每个Follower初始化时都有两个值：

  • 任期编号：一个自增的值
  • 超时时间：（这个值是随机的）

假设现在有A(0, 150ms)、B(0, 200ms)、C(0, 300ms)三个Follower，要选出一个Leader，这里用X(a,b,c)分别代表任期编号、超时时间、选票数

  1. 系统中没有Leader，因此没有任何的HeartBeat信息
  2. 由于随机到的A的超时时间最短，到期后，A就变为了Candidate
  3. A给B、C发送请求投票 RPC 消息，请它们选举自己为领导者，然后A的任期编号加1，自己再给自己投一票，变为A(1, 150ms, 1)
  4. B、C收到A的请求后，投票给A节点，而且发现自己的任期编号0<1，更新一下任期编号：B(1, 200ms)、C(1, 300ms)
  5. A收到B、C的投票，变为A(1, 150ms, 3)
  6. A获得了大部分的选票，A变为了Leader，向B、C发送心跳机制（告诉他们已有Leader，不要篡权）

注意下面几个问题：

1、节点之间如何通讯？

节点之间联络通过RPC：选举过程有两类RPC

  • RequestVote 请求投票RPC：请求投票。Candidate发起投票，晋升Leader。
  • AppendEntries 日志复制RPC：只能Leader发起。用来复制日志，提供心跳信息。（注意：心跳信息包含在此一起发送）

2、什么是任期？

Leader是有任期的，任期到期，需要重新选举Leader，在选举过程中，主要会有以下几个事件变化任期：

  • 心跳超时：Follower在HeartBeat信息超时后，变为Candidate，增加自己的任期编号
  • 交流后发现自己编号小：节点发现自己的任期编号比其他节点的小，就会更新自己的任期编号为较大的编号值

这个任期编号有什么用？

  • Candidate或Leader发现自己的编号小于其他节点的编号，会变为Follower
  • 节点接收到小于自己编号的请求，会直接拒绝

3、选举有哪些规则？

对于Leader来说：

  • Leader会周期性的给Follower发送心跳信息（即不带日志的AppendEntries）
  • 一个任期有多久？直到Leader出现故障，否则Leader一直是Leader

对于Follower与Candidate：

  • Follower超时时间内没有得到心跳信息，就会变为Candidate，发起选举
  • 获得大多数选票的Candidate晋升为Leader
  • 一个Follower只能投一次票，先来的先投；之后的将无票可投
  • 节点接收到小于自己编号的请求，会直接拒绝
  • 日志完整度高的Follower拒绝投票给日志完整性低的Candidate（因为日志完整度高代表：最后一条日志项对应的任期编号值更大）

4、随机超时时间是什么？

Raft设计超时时间，避免同时的出现很多个Candidate，造成网络堵塞

在Raft随机超时时间有两个：

  1. Follower等待成为Candidate的超时时间
  2. Candidate在一个随机时间内没有获得半数以上的票，那么此选举无效

Raft的日志复制

日志是什么？**日志(Log)由日志项(Log entries)**组成

一个日志项由三部分组成：也就是指令（Command）、索引值（Log index）、任期编号（Term）

比如log entries1：(1, 3, x<-3)就是一个日志项，前后分别代表索引值、任期编号、指令

如图所示（图片来自极客时间，分布式协议与算法实战）：

Raft Log

图中可以看到，Leader的日志是最新的，而且注意到，索引值是连续的

具体的日志复制的流程是这样的：

日志复制流程

  1. 客户端请求，比如将x设置为3
  2. Leader接收到之后，创建一个新的日志项(index+1, 9, x<-3)，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上（二阶段优化为了一个阶段）
    • 如果大多数节点返回成功，那么就提交日志，并且返回给客户端成功
    • 如果没有收到大多数节点返回的成功，那么就返回错误
  3. Follower接收到RPC消息，如果Leader已经提交，那么他们也会提交

理想情况下是这样的，如果出现了宕机崩溃，那么Leader会强制让Follower复制自己的日志项：

​ Leader通过AppendEntries的一致性检查，找到Follower与自己相同的最后的索引值（说明之后的都不一致）

举个例子：

Raft 日志一致性

如图所示，Follower的日志与领导者发生了区别（7号索引位置），图中还引入了两个值：

  • PrevLogEntry：上一个entry的索引值，图中为7
  • PrevLogItem：上一个entry的任期编号，图中为4
  1. Leader通过AppendEntries，发送最新日志给Follower（发送的内容包括：心跳、新的日志项、PrevLogEntry、PrevLogItem）
  2. Follower发现找不到PrevLogEntry=7&&PrevLogItem=4的记录，说明与Leader不一致，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者
  3. Leader会递减要复制的日志项的索引值，并发送新的日志项到跟随者（PrevLogEntry=6, PrevLogTerm=3）
  4. Follower找到了此条日志，那么返回成功，这样Leader就知道Follower在什么位置之后与自己发生了分歧
  5. 领导者通过AppendEntries，复制并更新覆盖该索引值之后的日志项，实现了集群各节点日志的一致

Raft成员变更

在分布式系统中，经常会有节点的加入和退出，有可能会引发脑裂问题（出现了新旧两个配置的Leader）

脑裂问题：Raft集群分裂，出现了两个Leader。

配置 configuration：即集群是哪些节点组成的，比如ABC组成的集群，那么集群的配置就是[A, B, C]的集合

比如现在有配置[A, B, C]要加入D、E两个节点，如果在加入的时候，AB与C发生了分区，导致[A, B]推举了A为Leader，[C, D, E]推举C为Leader，集群中就出现了两个Leader

如何解决脑裂问题？

  • 联合共识 Joint Consensus：但这个方法实现起来很难
  • 单节点变更 single-server changes：即每次都只添加一个节点进入集群

还是刚才那个问题，[A, B, C]要加入D、E两个节点，第一次只加入D这个节点，

  1. Leader A向新节点D同步数据
  2. Leader A将新配置[A, B, C, D]作为一个新的日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项应用（Apply）到本地状态机，完成单节点变更。
  3. 重复1-2步骤，添加节点E

PBFT

Paxos和Raft都是解决非拜占庭问题CFT的，如果遇到故意使坏的节点，那么他们将不能发挥作用，因此本节介绍最出名的BFT算法，PBFT（Practical Byzantine Fault Tolerance）

口信消息型与签名消息型

在上一章介绍解决拜占庭问题的两种办法：口信消息与签名消息

实际中，口信消息无法落地，其需要进行叛军数量f+1轮循环，如果有n个将军的话，那么就会系统中就会有O(n^(f+1))条消息，指数级别爆炸；而签名消息型也存在这个消息指数爆炸的问题

所以实际中这两个办法都是理论化的办法，无法落地

PBFT共识

如图所示，以该图为例串一下PBFT的过程：

这里例子里面有一个客户端Client以及四个node节点，假设node1是Master，而其中node4是叛徒节点

PBFT的实现需要保证 N >= 3*F + 1

  • F代表叛徒节点
  • N代表节点总数

所以实现PBFT至少需要4个节点（1个为叛徒）

PBFT共识过程

  1. 系统先通过轮换或随机算法选出某个节点为主节点Master，此后只要主节点不切换，则称为一个视图（View），如图node1就被选中了作为Master
  2. Client请求发送给Master（如果发送给了从节点Slave，那么Slave会发送到Master）请求的内容是<REQUEST,op,timestamp,client>
    • op表示具体的操作，timestamp代表当前时间戳，client表示客户端
  3. Master接收到Client的消息，将消息发送给所有的Slave（开启一个三阶段提交过程）
    1. Phase1 Pre-Prepare：Master发送<<PRE-PREPARE,view,n,digest>,msg>给Slave（View代表视图，n代表Master给此请求分配的序号，digest是摘要，msg表示客户端的消息）
      • 注意：这里有摘要信息，表示其他节点不能伪造该节点的信息
    2. Phase2 Prepare：收到消息的Slave，发送<PREPARE,view,n,digest,id>给其他的节点
      • 此处的digest是对应节点自己的摘要，id代表自己
      • 发送的对象是除自己以外的节点（包括Master）
      • node4节点是叛徒，因此他不准备回应任何消息
    3. Phase3 Commit：如果节点收到了至少2F+1个消息（本例中即为3）则认为验证通过
      • 注意：这个2F+1需要包含自己，如图中node1准备reply，因为收到了node2和node3的消息，再加上自己的，正好3票，因此可以回应Client
      • node4节点是叛徒，虽然他收到了3票（不算自己），他依然不会去回复Client
  4. 如果节点收到了至少2F+1个消息，就可以回复Client；Client如果收到了至少f+1个不同节点的相同结果，就达成共识，作为最后的结果

1、叛徒节点为什么不伪造其他人的信息？

信息中有签名，如果node4要发送完全不一样的消息给node1，那么node1在受到来自Master和node4的消息后，验证签名发现不一致，就发现了node4是叛徒

2、如果Master节点是叛徒怎么办？

图中我们举的例子是Slave为叛徒节点，那么如果Master是叛徒，Slave会发现其为叛徒，并且会以“轮流上岗”方式，推举新的主节点。

轮流上岗：(v + 1)mod|R|，其中v为当前视图的值，|R|为节点数

3、PBFT对签名型消息的优化：

PBFT将消息复杂度从 O(n^(f+1)) 降低为 O(n^2)

4、一个动态集群怎么确定f的值？

最坏打算f=(n-1)/3

5、为什么Client为什么需要f+1个回复而不是2f+1？

假设f个全是叛徒发的错误讯息，那么多一个讯息就能让Client确认有问题

Master是叛徒

如何切换主节点？

视图变更，使用轮流上岗的形式：(v + 1)mod|R|，其中v为当前视图的值，|R|为节点数

如果Master是坏蛋怎么办？

如果Master是叛徒，那么他的作恶手段无非三种：

  • 接收到Client请求，不作任何处理
    • 这种情况下：Client在一段时间得不到回应后，会给所有的节点发送消息，各节点然后给Master发消息，如果Master没音讯，那么就发起视图变更
  • 接收到Client请求，给不同的预准备请求分配不同的序号
    • 达不成共识，最后触发视图变更
  • 接收到Client请求，主节点只给部分节点发送预准备消息
    • 达不成共识，最后触发视图变更

PBFT存在的问题

  • 消息量还是很多，适合用在中小型分布式系统中（比如联盟链）

虽然PBFT能在实际场景中落地，但是消息还是比较多的

比如n=13, f=4的情况下：(f=(n-1)/3)

  • 请求消息：1
  • 预准备消息：n-1 = 3*f =12（Master给其他节点发消息）
  • 准备消息：(n-1-f)*(n-1)= (3*f - f)*3f = 8*12 = 96（除Master与叛徒节点外，节点给其他节点发消息）
  • 提交消息：(n-1)*(n-f) = 3f*(2f+1) = 108
  • 回复消息：n - f = 2f + 1 = 9

Gossip

Gossip是一个较为底层的协议，他并不是共识算法

本质是一个异步的图广度优先算法

这句话的意思是：

  • 对于Paxos、Raft算法，如果我们把它看做黑盒，那么我们每次输入得到的最后输出是一致的

  • 但是对于Gossip来说，前一个时刻的输入和后一个时刻的输入得到的输出可能会不同

这两种协议内部都可能存在很多种结果（不同的节点认为的可能不同），但是对于Paxos、Raft他们会得到共识后输出，但是Gossip不会

Gossip的使用场景

是一种：用于分布式数据库在多节点间复制同步数据的算法

比如在区块链网络中：Gossip用它来在各个分布式节点中互相同步区块头和区块体的信息，这是整个网络能够正常交换信息的基础（但并不能称作共识）

Gossip协议的目的也很简单就是保证高鲁棒性下（即使只剩一个节点依然能正常工作）传递消息

Gossip的三个核心要义

Gossip三个核心要义：

  • 直接邮寄 Direct Mail
  • 反熵 Anti-entropy
  • 谣传 Rumor mongering

DirectMail

Gossip的基本机制：

如果有一个节点想要传输数据（源节点）

  1. 源节点每过一个定时的周期，传输到与他相连接的K个节点上
  2. 节点收到消息后，如果该消息是其未收到过的消息，那么就传播给除源节点外的节点

有点像流行病毒传播，而最初它是被称作“流行病算法”（Epidemic Algorithm）

Gossip 传播示意图

（图片来源）

这种机制下我们可以看到Gossip的优点与缺点十分明显：

优点：

  • 极高的鲁棒性：对网络节点的连通性和稳定性几乎没有任何要求，网络中可以随意新增节点或是删除节点

缺点：

  • 达到最终一致（指网络中的所有数据变为相同的状态）的时间不确定
  • 冗余消息量大（每个节点可能会重复收到好几次消息）

而这两个缺点，是相互对立的

达到一致性耗费的时间与网络传播中消息冗余量这两个缺点存在一定对立，如果要改善其中一个，就会恶化另外一个

因此Gossip还涉及了反熵和谣传两种模式来供选择

反熵

熵是指事物的混乱程度

反熵也就是反混乱，降低混乱程度，尽量达成同步

反熵下：集群中的节点每隔一段时间就会随机选择某个节点与其交换数据

交换方式有三种：

  • 推：将本节点消息推给另一个节点，修复对方的熵
  • 拉：同理，修复自己的熵
  • 推拉：修复双方的熵

反熵的效果：缩减达到一致性耗费时间，增加了冗余消息量

谣传

谣传：当节点有了新数据，此节点变为活跃状态，周期性的联系给其他节点发送新的数据，直到所有的节点都包含此新数据

注意：谣传只发送新数据，因此冗余数据量少

比如A向B、C发送新数据，B与C得到新数据后变为活跃节点，给其他没有新数据的节点（即不是活跃状态的节点）发送新数据

反熵与谣传的对比

模式 特点 适用于
反熵 更快的一致性，但是冗余数据量大 节点已知，基本固定不变
谣传 一致较慢，但是冗余量少 节点动态变化的分布式系统

Gossip总结

优点：

  • 扩展性强：允许节点任意增加减少
  • 高容错：网络中节点宕机重启不会影响Gossip消息传播
  • 去中心化：节点之间相互平等，不存在任何中心节点
  • 一致性收敛：整个网络会很快的收敛一致，消息传播速度达到了 logN。

缺点：

  • 冗余消息多
  • 消息延迟，不适合要求实时性的场景

雪花算法

雪花算法，分布式环境下生成64bit的有序ID

雪花算法ID结构

  • 0：第一bit固定不使用
  • 41bit：表示时间戳，可以表示69年的时间
  • 10bit：机器ID，还可以细分，前5bit为机房，后5bit为机器号
  • 12bit：自增序列，最多表示4096

这意味着，雪花算法可以在一毫秒一台机器上生成4096个有序的不重复ID，并且由于机器ID号很多，同一毫秒可以生成机器数*4096个ID号。

具体的生成算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 生成唯一ID
public synchronized long nextId() {
    long timestamp = System.currentTimeMillis();

    // 如果当前时间小于上次生成ID的时间戳，说明系统时钟倒退过，抛出异常
    if (timestamp < lastTimestamp) {
        throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
    }

    // 如果是同一时间生成的，则进行毫秒内序列
    if (lastTimestamp == timestamp) {
        sequence = (sequence + 1) & sequenceMask;
        if (sequence == 0) // 如果超过4096个，则阻塞到下一毫秒, 获取新的时间戳
            timestamp = tilNextMillis(lastTimestamp);
    } else {
        sequence = 0L;
    }

    lastTimestamp = timestamp;

    // 移位并通过或运算拼到一起组成64位的ID
    return ((timestamp - twepoch) << timestampLeftShift) |
        (datacenterId << datacenterIdShift) |
        (workerId << workerIdShift) |
        sequence;
}

// 阻塞到下一个毫秒，直到获得新的时间戳
protected long tilNextMillis(long lastTimestamp) {
    long timestamp = System.currentTimeMillis();
    while (timestamp <= lastTimestamp) {
        timestamp = System.currentTimeMillis();
    }
    return timestamp;
}