05.分布式一致性算法

分布式一致性：

定义：

• 分布式一致性是指在分布式系统中，确保所有节点对数据的视图是一致的，即所有节点在某个时间点上看到的数据状态是一致的。
• 分布式系统的核心目标：确保所有节点的数据和状态一致

强一致性：

• 所有读操作都能看到最新的写操作结果
• 强一致性模型：
  • 线性一致性
  • 顺序一致性

弱一致性：

• 读操作可能不会立即看到最新的写操作结果
• 弱一致性模型：
  • 最终一致性
  • 会话一致性

分布式一致性算法：

• 它们主要关注的是数据的一致性，即所有节点在任何时刻看到的数据都是一致的

Gossip 协议：（一种去中心化的通信协议）

具体应用场景：

• Amazon Dynamo、zookeeper、Consul、Kafka-KRaft

核心：

• 像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致

直接邮寄（Direct Mail）

• 实现：直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传
• 优点：
  • 数据变更时，同步及时
• 难点：
  • 失败需要缓存数据，进而会丢数据

反熵（Anti-entropy）

• 核心：通过异步修复实现最终一致性的方法。
• 实现：集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异实现反熵
• 数据交换方式：
  • 推：将自己的所有副本数据推给对方，修复对方数据
  • 拉：拉取对方的所有副本数据，修复自己数据
  • 推拉：即推自己数据、也拉对方数据，同时修复自己数据和对方数据
• 缺点：
  • 通信成本极高，因为要传输完整副本数据
• 局限性：
  • 相关的节点需要互相已知
  • 节点不能频繁动态变化
  • 节点过多的分布式环境
• 数据修复的具体实现：
  • 按照一定顺序来修复节点的数据差异，实现闭环（顺时针或逆时针）
  • 先随机选择一个节点，然后循环修复，每个节点生成自己节点有、下一个节点没有的差异数据，发送给下一个节点，进行修复
  • A修复B，B修复C，C修复A，A再次修复B
  • 通过闭环方式，这样可以在某个时间范围内达到最终一致；如果采用节点随机修复，则只是理论最终一致，所需时间变成随机

谣言传播

• 核心：当一个节点收到新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据(A->B;B->C,B->D,...)
• 适用：谣言传播非常具有传染性，它适合动态变化的分布式系统

Quorum NWR 算法：（灵活地制定一致性的级别的算法）

具体应用场景：

• 通过多数优先，灵活地制定一致性的级别
• 能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度

核心思想：

• 通过 Quorum NWR，你可以自定义一致性级别。通过临时调整写入或者查询的方式，当 W + R > N 时，就可以实现强一致性。

Quorum NWR 的三要素：

• N，表示副本数，集群中同一份数据有多少个副本。又叫做复制因子（Replication Factor）。
  • 副本数可以不等于节点数，不同的数据可以有不同的副本数
• W，又称写一致性级别（Write Consistency Level），表示成功完成W个副本更新，才算成功完成写操作
• R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读R个副本。（读取指定数据时，要读R副本，然后返回R个副本中最新的那份数据）

NWR的组合：

• 当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。
• 当 W + R <= N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。

举例：

• W(2) + R(2) > N(3)
• 数据有3个副本，每次写入2个副本才成功，每次读都需要读任意两个副本的最新数据。此时读到的数据一定是最新的数据。

副本和节点的关系：

• 副本数一般不能超过节点数据
• 解释：多副本的意义在于冗余备份。如果副本数超过节点数，则一个节点上会存在多个相同副本。对于这个节点的冗余来说，这个就没意义。

分布式容错算法：

定义：

• 分布式容错算法是用于确保分布式系统在部分节点发生故障时，仍能保持数据的一致性和服务的可用性的方法
• 分布式容错算法是分布式系统实现高可用性和可靠性的基础
• 分布式协调服务和共识算法通常会结合容错算法来处理节点故障和网络分区等问题

常用算法：

复制/副本/从库：

• 将数据复制到多个节点，以便在某个节点故障时仍能访问数据

数据分片：

• 将数据分布到多个节点上，减少单点故障的影响

分布式共识算法：

• 它们主要关注的是在存在部分节点故障或网络分区的情况下，确保系统对某个值或者决策能够达成一致的决策

定义：

• 分布式共识算法是用于在分布式系统中多个节点对某个值或决策达成一致的算法，从而保证数据的一致性

常用算法：

Paxos：

• 基于多轮投票机制，确保分布式系统中的数据一致性。主要关注理论上的一致性保证，设计较为复杂。
• 实际应用中通常使用其变种（如Multi-Paxos）来简化实现
• Paxos和Raft都依赖于多数派原则，即在多数节点达成一致的情况下，整个系统认为达成了一致

Raft：

• 通过领导者选举和日志复制，提供简化和易于理解的一致性保证。
• Paxos和Raft都依赖于多数派原则，即在多数节点达成一致的情况下，整个系统认为达成了一致

ZAB（ZooKeeper Atomic Broadcast）：

• 专为ZooKeeper设计的原子广播协议，确保分布式协调服务中的数据一致性
• 通过领导者选举和事务广播机制，专门为ZooKeeper设计

应用场景：

• 分布式数据库的主备同步
• 分布式文件系统的元数据管理
• 分布式协调服务（如ZooKeeper、etcd）