分布式 共识算法

浅谈分布式系统的一致性

Post on

分布式系统的由来

分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。

简单来说，就是通过分治法，将一个任务拆成多个子任务分给不同计算机节点处理

以下是一个常见的互联网架构图，也是一个基本的分布式系统，Nginx层负责代理，WebServer层负责中台组装数据，service层由很多的微服务（无状态、有状态都存在）组成，还有专门的DB。

img

分片与副本

分片

以DB举例：

img

对于数据级别到数百上千万的DB，最终都会走向分库分表的，而这种分库分表其实就是分片的其中一个表征。

这样做的好处是：

  1. 提升性能和并发，操作被分发到不同的分片，相互独立
  2. 提升系统的可用性，即使部分分片不能用，其他分片不会受到影响

但它并不能高可用，因为在分布式系统下，随着节点的增多，下面的问题出现的概率将会指数级增加

  1. 进程挂掉、断电、磁盘损害
  2. 断网、高延迟

为了解决以上的问题，副本出现了。

副本

img

通过副本（多活或者是主备策略），在原DB或网络延迟、或宕机发生时，能够柔性替换，保证业务的连续性。

由上面的说明，我们可以看出，一个分布式系统，内部必然会出现分片、副本等功能至少一种。

那么多副本怎么保证数据的一致性？

img

  1. 网络要足够保障业务连续性
  2. 多节点之间对数据的一致性操作有共识（排除拜占庭将军问题）

一致性

分类

根据使用和学术研究的角度，或者说根据系统内外的角度来看，可以分为用户的角度、数据的角度。

在用户的角度上看：

  1. 强一致性： 向系统写入一个值后，后续任意时刻的读取一定成功。
  2. 弱一致性： 向系统写入一个值后，后续的读操作可能读出来，也可能读不出来。
  3. 最终一致性（弱一致性特定场景）：向系统写入一个值后，后续立刻的读操作可能读不出来，但是在某个时间段后，读取一定成功。 例如，读写分离的关系型数据库。

数据角度上的一致性？

CAP

img

一致性 在分布式环境中,一致性是指数据在多个副本之间是否能够保持一致的特性（强一致性）。

可用性 可用性是指系统提供的服务必须一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。

分区容错性 分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

选 择 说 明
CA 放弃分区容错性，加强一致性和可用性，其实就是传统的单机数据库的选择
AP 放弃一致性（这里说的一致性是强一致性），追求分区容错性和可用性，这是很多分布式系统设计时的选择，例如很多NoSQL系统就是如此；如：Cassandra
CP 放弃可用性，追求一致性和分区容错性，基本不会选择，网络问题会直接让整个系统不可用；如：Etcd

在网络分区发生的情况下，分布式系统不能同时保证一致性和可用性。 除非是单节点系统， 否则无法同时保证 CA。

为什么C和A只能选一个？

img

P1 P2就是两个节点的意思，正常情况下，当写入a=1后，P1同步到P2后，在任意节点读取时a都是等于1。

img

但因为网络问题或宕机等情况发生，P1同步不到P2，这个时候网络分区就出现了。

img

  1. 我们选择可用性时，意味P2节点也要对外提供服务，那么在a=1同步失败后，P1、P2对外提供的数据是不一致的。
  2. 我们选择一致性时，在a=1同步失败后，为了保证一致性，P2不能对外提供服务，则意味着P2是不可用的。

我们可以得出结论：在网络发生分区的情况下，我们必须在可用性和一致性之间做出选择。

那么如果以同个节点对外提供服务，那么是否可以CA都拥有？

读写同一节点，可以避开分区影响吗?

img

由上图可见，也是无法避开的。

如果作为master的P1在将a=1的数据同步给P2之前挂了

  1. 为了保证可用性，那么P2将转为master，但因为P2没有同步P1的数据，那么此刻提供出来的数据是不一致的。
  2. 为了保证一致性，P2也不能对外提供服务，那么就意味着整个系统是不可用的。

数据同步的两种方式

我们有说 “节点间必然有数据同步的机制， 不然无法读取到跨节点的写更新”。

数据同步的方式可以分为：

  1. 同步： 所有 节点写入完成后，返回写入成功。
  2. 异步： 先返回写入成功，再同步到其他节点。

下面是两种数据同步方式的示例，紫色长条表示数据备份：

img

当然，同步和异步的方式并不是绝对的， 我们可以设计出先同步写 N 个节点，回复客户端，再异步写入其他节点的方式（典型例子：etcd）。

不过，我们稍加分析即可以发现， 网络分区发生的时候，无论同步还是异步的方式，如果不放弃可用性，都不能保证一致性。

img

保证一致性的理论

Raft理论

状态机复制

img

img

技术来源于生活，像地铁闸口，就是一个典型的状态机状态，每一次的状态都是覆盖迭代，不存在什么随便修改的问题。

img

像上图，在共识算法写入log并同步到其他节点后，就会将新的字段状态同步到内存中的stat machine。

在Raft协议中，有一个强Leader，由它全权负责接受客户端的请求，并将命令作为日志复制给其它服务器，在确认安全后，将日志提交执行。当Leader故障时，则会选举产生一个新的Leader。在Leader的帮助下，Raft协议将一致性问题简化，分解为了以下三个子问题：

1）领导选举（Leader Election）：当现有的Leader故障时，必须重新选出一个新的Leader。

2）日志复制（Log Replication）：Leader接收来自客户端的命令，记录为日志，并复制给集群中的其它服务器，且强制其它服务器的日志与Leader保持一致。

3）安全措施（Safety）：通过一些措施保证系统安全，例如确保所有服务器均按照相同顺序执行相同命令的措施。

日志复制过程

img

img

客户端提交每一条命令都会被按顺序记录到Leader的日志中，每一条命令都包含Term编号和顺序索引，然后向其他节点并行发送AppendEntries RPC用以复制命令，当大多数节点成功复制后，Leader就会提交命令，即执行该命令并且将执行结果返回客户端，Raft保证已经提交的命令最终也会被其他节点成功执行。Leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的，而且之前的命令也是相同的。当发送AppendEntries RPC时，会包含Leader上一条刚处理过的命令，接收节点如果发现上一条命令不匹配，就会拒绝执行。

日志不一致的情况？

在现实情况下，主从节点的日志可能不一致（例如在消息到达从节点前主节点挂了，而从节点被选为了新的主节点，此时主从节点的日志不一致）。Raft 算法中，主节点需要处理不一致的情况，它要求所有的从节点复制自己的所有日志。

要复制所有日志，就要先找到日志开始不一致的位置，如何做到呢？Raft 当主节点接收到新的 command 时，会发送 AppendEntries 让从节点复制日志，不一致的情况也会在这时被处理（AppendEntries 消息同时还兼职作为心跳信息）。日志不一样的情况如下：

img

主节点需要为每个从节点记录一个 nextIndex，作为该从节点下一条要发送的日志的编号。当一个节点刚被选为主节点时，为所有从节点的 nextIndex 初始化自己最大日志编号加 1（如上图示例则为 11）。接着主节点发送 AppendEntries 给从节点，此时从节点会进行一致性检查（Consistency Check）。

所谓一致性检查，指的是当主节点发送 AppendEntries 消息通知从节点添加条目时，需要将新条目 A 之前的那个条目 B 的 log index 和 term，这样，当从节点收到消息时，就可以判断自己第log index 条日志的 term 是否与 B 的 term 相同，如果不相同则拒绝该消息，如果相同则添加条目 A。

主节点的消息被某个从节点拒绝后，主节点会将该从节点的 nextIndex 减一再重新发送AppendEntries 消息。不断重试，最终就能找主从节点日志一致的 log index，并用主节点的新日志覆盖从节点的旧日志。当然，如果从节点接收 AppendEntries 消息后，主节点会将 nextIndex 增加一，且如果当前的最新 log index 大于 nextIndex 则会继续发送消息。

img

保证：

  • 如果两个日志条目有相同的 log index 和 term，则它们的内容一定相同。

  • 如果两个节点中的两个条目有相同的 log index 和 term，则它们之前的所有日志一定相同。

选主？安全性保证？可以留着各位自行查资料。

未提及的如 gossip、paxos。

以上是偏存储相关的共识算法的一致性保障，那么不同服务之间为保证业务连续性的一致性怎么做？

2PC/3PC

img

1.1的操作事实上就是让参与者直接执行。

问题：

  1. 阻塞
  2. 协调者单点问题

三阶段提交（Three-phase commit）主要做的事情：

  1. 引入超时机制。同时在协调者和参与者中都引入超时机制。

  2. 并且把两阶段提交协议的第一个阶段（协调者）拆分成了两步：询问，然后再锁资源，最后真正提交。

img

一旦出现网络或宕机问题，数据不一致性必然存在！！！

分布式事务最好的解决方案是尽量避免出现分布式事务！

市面上常用的分布式事务框架：seata

基于BASE的一致性保证

BASE理论

基本可用（Basically Available）

基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。

电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。(削峰填谷，延迟响应，服务降级)

软状态（ Soft State）

软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。mysql replication 的异步复制也是一种体现。

最终一致性（ Eventual Consistency）

最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。(写时修复，读时修复)

核心思想：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性

img

img

抢红包服务只是数字的展现，抢到的金额通过kafka，交由发放服务去进行金额发放。而这种模式是市面上的很多分布式系统会做的事情。

引用：

https://www.cnblogs.com/xybaby/p/7787034.html

https://writings.sh/post/cap-and-consistency-models

https://blog.csdn.net/lihao21/article/details/114879304

https://lotabout.me/2019/Raft-Consensus-Algorithm/



X