elonnzhang@home:~$
#

Archive

About

RSS

raft

分布式系统下的一致性问题

分布式系统有多个服务节点，给定一系列操作，在约定协议的保障下，使得它们对处理结果达成某种程度的协同。

分布式系统中的节点通信存在两种模型：

  • 共享内存（Shared memory）
  • 消息传递（Messages passing）。 基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会响应慢、被杀死或者重启，消息可能会延迟、丢失、重复；发生上面任意一种异常都会对分布式系统中各个节点对某一个值达成一致性产生问题。

一致性

  • 强一致性
  • 弱一致性
  • 最终一致性

共识算法 共识算法（Consensus Algorithm）是分布式系统中用于在多个节点之间就某个值达成一致的算法，即使在存在节点故障、网络分区的情况下，也能确保系统状态的一致性。

共识算法解决的问题

共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。提案泛指多个事件发生的顺序、某个键对应的值…对于分布式系而言，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，State-Machine Replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。

这里共识算法需要解决两个基本问题：

  1. 如何提出一个待共识的提案（令牌传递、随机选取…）
  2. 如何让多个节点对提案达成共识（投票、规则验证…）

现实网络环境中存在各种各样的问题，在分布式环境下，共识算法还需要解决如通信问题（网络中断、分区）、节点故障、消息伪造…

CAP定理 CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer’s theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点，只能满足三项中的两项：

  • C（一致性）：任何事务都应该是原子的，所有副本上的状态都是事务成功提交后的结果，并保持强一致性。
  • A（可用性）：系统正常节点能在有限时间内完成对操作请求的应答。
  • P（分区容错性）：系统中的网络可能发生分区故障（成为多个子网、节点上线和下线），节点之间的通信无法保障，而网络故障不应该影响到系统正常服务。
  • 结论：在分布式系统中 P 必须要保证，只能在 C 和 A 之间权衡：
  • 保 C（强一致性）→ 可能牺牲可用性（如 Zookeeper）
  • 保 A（高可用）→ 只能是最终一致性（如 Dynamo、Cassandra）

三类系统模型

  • CA（一致性+可用性）：包括完全严格的仲裁协议，例如2PC（两阶段提交）。
  • CP（一致性+分区容错性）： 包括多数仲裁协议，其中少数分区不可用，例如Paxos。
  • AP（可用性+分区容错性）： 包括执行最终一致性的协议，例如Gossip。

ACID ACID 即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）四种特性的缩写，一般出现在分布式数据库等基于事务过程的系统中；ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

  • Atomicity: 每次事务是原子的，事务包含的所有操作要么全部成功，要么全部不执行。一旦有操作失败，则需要回退状态到执行事务之前；
  • Consistency: 数据库的状态在事务执行前后的状态是一致的和完整的，无中间状态。即只能处于成功事务提交后的状态；
  • Isolation: 各种事务可以并发执行，但彼此之间互相不影响。按照标准 SQL 规范，从弱到强可以分为未授权读取、授权读取、可重复读取和串行化四种隔离等级；
  • Durability: 状态的改变是持久的，不会失效。一旦某个事务提交，则它造成的状态变更就是永久性的。

BASE原则 BASE即 Basic Availability（基本可用），Soft-state（弱状态），Eventual Consistency（最终一致性），为 eBay 技术专家 Dan Pritchett 提出的与ACID相对的一个原则，主要面向大型高可用分布式系统，主张牺牲掉对强一致性的追求，而实现最终一致性，来换取一定的可用性。

  • Basic Availability：系统在出现不可预知的故障时候，允许损失部分可用性，保证核心服务可用。
  • Soft-state：允许系统在不同节点的数据副本之间进行数据同步的过程中存在延时（允许系统中的数据存在中间状态，不会影响系统的整体可用性）。
  • Eventual Consistency：系统中所有的数据副本，在进过一段时间的同步后，最终能够达到一个一致的状态。

同步复制：知道数据真的安全复制到全部机器上 异步复制：master将更新存储在本地后立即向客户端发回响应，master在之后才进行异步复制到全部的机器上。 半同步复制：要求master在应答客户端之前必须把数据复制到足够多的机器上, 而非全部机器. 这样副本数够多可以提供比较高的可靠性; 1台机器宕机也不会让整个系统停止写入; 但系统中还是会存在数据不一致的情况。

两阶段提交 一、 准备（投票）阶段 协调人向所有参与者发送更新信息。每个参与者处理更新，并投票决定是提交还是放弃。当投票决定提交时，参与者将更新存储到一个临时区域（Write-Ahead Log）预写日志。 二、 提交阶段 协调程序决定结果并通知每个参与者。如果所有参与者投票提交，那么更新将从临时区域获得并永久化。

Quorum机制 （法定人数机制、多数派机制） 在分布式系统中，Quorum常用于副本的读写控制，容忍最多 (N-1)/2 个节点损坏。

Paxos

Paxos可以协同让多个机器成为一个整体的系统，这个系统中的每个机器都必须让系统中的状态达成一致，如果在三副本集群中的一台机器上上传了一个文件，其他两台机器也必须复制这个文件，达到系统的一致性。

角色

  • Proposer: 提出提案(Proposal),Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • Acceptor: 参与决策，可以理解为存储节点，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数派Acceptors的接受，则称该Proposal被批准。
  • Learners: 用于学习被批准的提案

Paxos算法中的角色允许身兼数职，也有了如下的基本约束：

  1. 决策（value）只有在被 proposers 提出后才能被批准（未经批准的称为提案）；
  2. 在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
  3. Learners 只能获得被批准（chosen）的 value。

加强约束 P1：一个Acceptor必须接受第一次收到的提案 P2：如果某个value为v的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 Acceptor 再次接受（accept）的提案必须具有 value v P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 Proposer 提出的提案必须具有 value v。 P2c：如果一个编号为 n 的提案具有 value v，该提案被提出，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

Basic Paxos

  • Basic Paxos 通过二阶段方式来达成共识，即准备阶段和接受阶段
  • Basic Paxos 除了达成共识功能，还实现了容错，在少于一半节点出现故障时，集群也能工作
  • 提案编号大小代表优先级。对于提案编号，接受者提供三个承诺：
    • 如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者承诺不响应这个准备请求
    • 如果接受请求中的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者承诺不通过这个提案
    • 如果按受者已通过提案，那些接受者承诺会在准备请求的响应中，包含已经通过的最大编号的提案信息

Multi Paxos

Basic Paxos 算法只能对单个值达成共识，对于多个值的情形，Basic Paxos 算法就不管用了。因此，Basic Paxos 算法几乎只是用来理论研究，并不直接应用在实际工作中。

Multi Paxos 算法则是一个统称，是指基于 Multi Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（例如 Raft 算法等）。

如果直接通过多次执行 Basic Paxos 实例方式，来实现一系列值的共识，存在以下问题：

  • 如果集群中多个提议者同时在准备阶段提交提案，可能会出现没有提议者接收到大多数准备响应，导致需要重新提交准备请求。例如，在一个 5 个节点的集群中，有 3 个节点同时作为提议者同时提交提案，那就会出现没有一个提议者获取大多数的准备响应，而需要重新提交
  • 为了达成一个值的共识，需要进行 2 轮 RPC 通讯，分别是准备阶段和接受阶段，性能低下

为了解决以上问题，Multi Paxos 引入了领导者（Leader）和优化了 Basic Paxos 的执行过程。

Leader 作为唯一的提案人，解决了冲突问题 引入Leader后，准备阶段就没意义了，减少了RPC次数

https://youtu.be/d7nAGI_NZPk?si=g1jTd84nDbf1yEm1

Raft

易于理解的共识算法

节点类型

  • Leader
  • Follower
  • Candidate

Follower->Candidate->Leader 所有节点都从 Follower 开始，没有收到Leader的信息，把自己变为Candidate，发起投票，获获得多数的选票成为Leader 类似主席->人大代表->群众

将时间划分为term(任期)

Raft 任期具有如下特点：

  • 跟随者在等待领导者心跳消息超时后，推举自己为候选人时，会增加自己的任期编号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1
  • 如果一个节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如，节点 B 的任期编号为 0，当收到来自节点 A 的请求投票 RPC 消息，消息中包含节点的任期编号为 1，那么节点 B 将把自己的任期编号更新为 1
  • 如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态（可以参考上面的节点状态转换示意图）。比如网络分区错误，导致出现两个领导者，当分区错误恢复后，任期编号为 3 的领导者 B 接收到领导者 A 任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟随着状态，接受节点 A 为领导者
  • 如果一个节点接收到一个包含较小任期编号值的请求，那么它会直接拒绝这个请求。例如，节点 C 的任期编号为 4，接收到任期编号为 3 的 RPC 消息，那么节点 C 将拒绝这个消息

两个超时时间

  • 心跳超时：leader - 周期性发送心跳（AppendEntries RPC）给所有 Follower，防止它们发起选举
  • 选举超时：选举超时是指_followers_跟随者成为_candidates_候选者之前所等待的时间。- 控制 Follower 转为 Candidate 发起选举的时间，选举超时时间为随机值 150 ~ 300 ms

日志复制 日志由日志项（log entry）构成。日志项包含日志项索引、任期编号以及指令： 日志复制

  1. 客户端发送请求，领导者接收到客户端请求，根据请求中的指令，创建一个新的日志项，并附加（append）到领导者日志中
  2. 领导者通过日志复制 RPC（AppendEntries RPC），将新的日志项复制至其他节点
  3. 当领导者将日志项成功复制至集群大多数节点的时候，日志项处于 committed 状态，领导者可将这个日志项应用（apply）到自己的状态机中
  4. 领导者将客户端请求结果返回给客户端
  5. 当其他节点，即跟随者，接收到领导者的心跳消息，或新的日志复制消息（该消息均会附上领导者最大已提交日志项索引），如果跟随者发现领导者已提交某日志项，而自己还没将该日志项应用至状态机，那么，跟随者就将该日志项应用至自己的状态机中

https://raft.github.io/ https://github.com/hashicorp/raft?tab=readme-ov-file https://github.com/otoolep/hraftd/tree/master/http

ZAB

TODO: need to update