一致性算法原理

2022-07-10 11:59:47

一致性算法原理

一致性算法的出现是为了解决一致性问题，一致性问题是指对于一组服务器(集群)，给定一组操作，需要使用一种协议使得他们的结果最终达成一致，看起来好像是一台服务器一样。

弱一致性 (DNS)

DNS 就是典型的弱一致性，访问不同的 DNS 服务器可能在一开始不一致，但是等待一段时间后会一致。

强一致性 (主从同步)

  1. Master 接受写请求
  2. Master 复制日志至 slave
  3. Master 等待，直到所有从库范围

问题：
一个节点失败，Master 阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低。

强一致性 (多数派)

在并发环境下，无法保证系统正确性，顺序非常重要。

强一致性 - Paxos

Paxos 算法是莱斯利·兰伯特 于 1990 年提出的一种基于消息传递的一致性算法且具有高度容错的一致性算法。这个算法被认为是类似算法中最有效的。

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

Paxos 算法有三种版本。下面我们一个一个来介绍。

  • Paxos
    • Basic Paxos
    • Multi Paxos
    • Fast Paxos

Basic Paxos

在 Paxos 主要有3种角色 Proposer(提案者)、Acceptor(提议投票和接受者)、Learners(提议接受者)。外部角色 Client(请求发起者)。在具体实现种，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。还有一个很重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。

  • 角色介绍
    • Client
      • 请求发起者，系统外部角色
    • Proposer
      • 接收 client 请求，向集群提出提议。起到冲突调节的作用。
    • Acceptor
      • 提议投票和接受者，只有在形成法定人数（Quorum）时，提议才会最终被接受。
    • Learners
      • 提议接受者，备份，对集群一致性没有影响(不参与投票)
  • 步骤和阶段
    • Prepare
      • Proposer 提出一个议案，编号为N，此N大于这个 Proposer 之前提出的提案编号。请求 acceptors 的 quorum 接收。
    • Promise
      • 如果N大于此 acceptor 之前接收的任何提案编号则接受，否则拒绝。
    • Accept
      • 如果达到了多数派，Proposer 会发出 accept 请求。此请求包含提案编号N，以及内容。
    • Accepted
      • 如果此 acceptor 在此期间没有收到任何大于 N 的提案，则接收此提案内容，否则忽略。

时序图如下:（成功的情况）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IRRhLObG-1624337364102)(一致性算法原理详解.assets/image-20210621142354500.png)]

只要 Accepted 达到多数派，则表示成功。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xnaJrSK6-1624337364104)(一致性算法原理详解.assets/image-20210621143952422.png)]

当第一次失败，或者第二次在第一次还未成功之前发送了有一次 prepare2 。那么会执行编号大的一次 prepare2 请求。比如在 Accept 期间，新的 proposer 发起 prepare2 请求。那么之前 prepare1 提案则将被拒绝。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KteERIDe-1624337364105)(一致性算法原理详解.assets/image-20210621144849870.png)]

这种情况成为活锁情况，当 prepare1 的提案还未被通过，然后出现 prepare2 提案，当 prepare2 提案未通过又出现 prepare3 .如此循环导致不断出现提案并且所有提案都未通过。举个例子，你和你女朋友去吃饭，她先提议说“吃火锅吧”。还没等她说完然后你说"我觉得烤鱼好一些"，然后她又说"昨天新开的一家海鲜排档还不错"。最后无尽的推翻前一次的提议。最后无法得到结论最后吃啥，导致产生活锁。

Multi-Paxos

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos思想，通过多个 Basic Paxos实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft算法等）。

通过多次执行 Basic Paxos 实例，来实现一系列值的共识，会存在一下问题：

  • 如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。
  • 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。分布式系统的运行是建立在 RPC 通讯的基础之上的，因此，延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。

解决方案

引入领导者(Leader)解决问题

可以通过引入领导者节点，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。但是在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法，进行投票选举产生的。

减少交互次数

采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化Basic Paxos 执行。也就是说，领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段。

和重复执行 Basic Paxos 相比，Multi-Paxos 引入领导者节点之后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。

Chubby 的 Multi-Paxos 实现

  1. 通过引入主节点，实现了兰伯特提到的领导者（Leader）节点的特性。主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了；
  2. 在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。
  3. 在 Chubby 中实现了兰伯特提到的，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制；
  4. 在 Chubby 中，实现了成员变更（Group membership），以此保证节点变更的时候集群的平稳运行。

在 Chubby 中，为了实现了强一致性，读操作也只能在主节点上执行。 也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。

  • 选举阶段

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EU26gQfr-1624337364111)(一致性算法原理详解.assets/image-20210621151635489.png)]

  • 提案阶段

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vU1ZzHu1-1624337364111)(一致性算法原理详解.assets/image-20210621151907660.png)]

Raft 算法

raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication），raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。

Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected.

上面的引文对raft协议的工作原理进行了高度的概括：raft会先选举出leader，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followes会重新选举出新的leader。

下面分别介绍 raft 算法中 leader election(领导选举)、log replication(日志复制)、safety(安全性)、corner case (极端情况) 进行介绍。

  • leader election(领导选举)

    raft协议中，一个节点任一时刻处于以下三个状态之一：

    • leader(领导)
    • follower(跟随)
    • candidate(候选)

    follower(跟随) 只能响应其他服务的请求，并且在一开始时所有的节点都是 follower(跟随) 状态；在一段时间内(每个节点的时间可能是随机的)，follower(跟随) 没有接收到其他服务发来的请求。 follower(跟随) 的状态将变成 candidate(候选) 状态；candidate(候选) 节点如果得到集群中所有节点的多数派投票。那么将变成 leader(领导) 节点；领导角色将会一旦产生，其他candidate(候选) 节点 将变成follower(跟随)节点。直到 leader(领导) 出错(宕机、或者网络问题失去连接)。那么将重复上述 follower(跟随) 状态 -> candidate(候选) 状态 -> leader(领导) 的过程。

    注意：当出现多个候选节点的票相同的情况下，raft 算法会进行第二轮选举。并且 follower(跟随) 状态 -> candidate(候选) 状态的时间是随机的来避免再次平票的情况。

  • log replication(日志复制)

    在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。

    当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：

    • leader append log entry 领导节点添加日志记录
    • leader issue AppendEntries RPC in parallel 领导节点使用 RPC 并行发送这些记录到 follower(跟随)节点
    • leader wait for majority response 等待多数派的响应
    • leader apply entry to state machine 领导节点应用当前记录到状态机(领导节点应用当值的记录)
    • leader reply to client 领导节点回复客户端
    • leader notify follower apply log 领导节点通知follower(跟随) 节点应用当前的日志

    logs由顺序编号的log entry组成 ，每个log entry除了包含command，还包含产生该log entry时的leader term。raft算法为了保证高可用，并不是强一致性，而是最终一致性，leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。

    leader只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。这里有两个词：commit（committed），apply(applied)，前者是指日志被复制到了大多数节点后日志的状态；而后者则是节点将日志应用到状态机，真正影响到节点状态。

  • safety(安全性)

    在上面提到只要日志被复制到大多数节点，就能保证不会被回滚，即使在各种异常情况下，这根leader election提到的选举约束有关。在这一部分，主要讨论raft协议在各种各样的异常情况下如何工作的。

    衡量一个分布式算法，有许多属性，如

    • safety：nothing bad happens.
    • liveness： something good eventually happens.

    在任何系统模型下，都需要满足safety属性，即在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。比如，raft保证被复制到大多数节点的日志不会被回滚，那么就是safety属性。而raft最终会让所有节点状态一致，这属于liveness属性。

    1. Election safety: 选举安全性，即任一任期内最多一个leader被选出。

    2. log matching: log匹配特性， 就是说如果两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的

    3. leader completeness vs elcetion restriction: 如果一个log entry在某个任期被提交（committed），那么这条日志一定会出现在所有更高term的leader的日志里面。这个跟leader election、log replication都有关。

      • 一个志被复制到majority节点才算committed
      • 一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。

      raft与其他协议（Viewstamped Replication、mongodb）不同，raft始终保证leade包含最新的已提交的日志，因此leader不会从follower catchup日志，这也大大简化了系统的复杂度。

  • corner case (极端情况)

    • stale leader(旧领导)

    raft保证Election safety，即一个任期内最多只有一个leader，但在网络分割（network partition）的情况下，可能会出现两个leader，但两个leader所处的任期是不同的。

    在这样的情况下，我们来考虑读写。

    首先，如果客户端将请求发送到了stale leader(旧的领导)，stale leader(旧的领导)无法将log entry 复制到majority(多数派)节点，因此不会告诉客户端写入成功，这就不会有问题。

    对于读请求，stale leader(旧的领导)可能返回stale data(旧数据)，比如在read-after-write的一致性要求下，客户端写入到了term2任期的leader(新的领导)，但读请求发送到了stale leader(旧的领导)。如果要保证不返回stale data(旧数据)，leader需要check自己是否过时了，办法就是与大多数节点通信一次，这个可能会出现效率问题。另一种方式是使用lease，但这就会依赖物理时钟。

    从raft的论文中可以看到，leader转换成follower的条件是收到来自更高term的消息，如果网络分割一直持续，那么stale leader就会一直存在。而在raft的一些实现或者raft-like协议中，leader如果收不到majority节点的消息，那么可以自己step down，自行转换到follower状态。

    • State Machine Safety(状态机的安全)

    Sate Machine Safety: If a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.

    如果节点将某一位置的log entry应用到了状态机，那么其他节点在同一位置不能应用不同的日志。简单点来说，所有节点在同一位置（index in log entries）应该应用同样的日志。但是似乎有某些情况会违背这个原则：

    Raft never commits log entries from previous terms by counting replicas.

    Only log entries from the leader’s current term are committed by counting replicas; one an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

    也就是说，某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了，具体怎么实现了，在log matching部分有详细介绍。那么问题来了，如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log

    Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term.

    • leader crash

    follower的crash处理方式相对简单，leader只要不停的给follower发消息即可。

    一致性算法原理

ZAB 算法

ZAB 协议介绍

  1. ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。

  2. Zookeeper 是一个为分布式应用提供高效且可靠的分布式协调服务。在解决分布式一致性方面，Zookeeper 并没有使用 Paxos ，而是采用了 ZAB 协议。

  3. ZAB 协议定义：ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。下面我们会重点讲这两个东西。

  4. 基于该协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。具体如下图所示：

    一致性算法原理

    上图显示了 Zookeeper 如何处理集群中的数据。所有客户端写入数据都是写入到 主进程（称为 Leader）中，然后，由 Leader 复制到备份进程（称为 Follower）中。从而保证数据一致性。从设计上看，和 Raft 类似。

    1. 那么复制过程又是如何的呢？复制过程类似 2PC，ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交，大大减小了同步阻塞。也提高了可用性。

简单介绍完，开始重点介绍 消息广播 和 崩溃恢复。整个 Zookeeper 就是在这两个模式之间切换。 简而言之，当 Leader 服务可以正常使用，就进入消息广播模式，当 Leader 不可用时，则进入崩溃恢复模式。

消息广播

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似一个 二阶段提交过程。对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数成功响应，则执行 commit 操作（先提交自己，再发送 commit 给所有 Follwer）。

基本上，整个广播流程分为 3 步骤：

1.将数据都复制到 Follwer 中

一致性算法原理

  1. 等待 Follwer 回应 Ack，最低超过半数即成功一致性算法原理
  2. 当超过半数成功回应，则执行 commit ，同时提交自己一致性算法原理

通过以上 3 个步骤，就能够保持集群之间数据的一致性。实际上，在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，避免同步，实现异步解耦。

还有一些细节：

  1. Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务ID（ZXID），ZAB 兮协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。
  2. 在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。
  3. zookeeper集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。
  4. 实际上，这是一种简化版本的 2PC，不能解决单点问题。等会我们会讲述 ZAB 如何解决单点问题（即 Leader 崩溃问题）。

崩溃恢复

刚刚我们说消息广播过程中，Leader 崩溃怎么办？还能保证数据一致吗？如果 Leader 先本地提交了，然后 commit 请求没有发送出去，怎么办？

实际上，当 Leader 崩溃，即进入我们开头所说的崩溃恢复模式（崩溃即：Leader 失去与过半 Follwer 的联系）。下面来详细讲述。

假设1：Leader 在复制数据给所有 Follwer 之后崩溃，怎么办？

假设2：Leader 在收到 Ack 并提交了自己，同时发送了部分 commit 出去之后崩溃怎么办？

针对这些问题，ZAB 定义了 2 个原则：

  1. ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
  2. ZAB 协议确保丢弃那些只在 Leader 提出/复制，但没有提交的事务

所以，ZAB 设计了下面这样一个选举算法：

能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。

针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。

而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

这样，我们刚刚假设的两个问题便能够解决。假设 1 最终会丢弃调用没有提交的数据，假设 2 最终会同步所有服务器的数据。这个时候，就引出了一个问题，如何同步？

数据同步

当崩溃恢复之后，需要在正式工作之前（接收客户端请求），Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了，即是否完成了数据同步。目的是为了保持数据一致。

当所有的 Follwer 服务器都成功同步之后，Leader 会将这些服务器加入到可用服务器列表中。

实际上，Leader 服务器处理或丢弃事务都是依赖着 ZXID 的，那么这个 ZXID 如何生成呢？

答：在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。

而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 epoch 值，然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。

基于这样的策略：当 Follower 链接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

引用

https://www.bilibili.com/video/BV1p4411v7ns
https://www.cnblogs.com/xybaby/p/10124083.html
https://www.cnblogs.com/stateis0/p/9062133.html

上一篇：Chocolatey如何使用


下一篇：MacOS从零开始搭建hexo博客