ZooKeeper 入门教程之四

发表于 阅读次数： 评论数： 本文字数： 5.8k 阅读时长 ≈ 5 分钟

大纲

前言

学习资源

拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem）是计算机科学和分布式系统中的一个经典问题，用于描述在分布式系统中如何在存在不可靠参与者（即恶意节点或故障节点）的情况下，达成一致的决策。

故事背景

拜占庭将军问题来源于一个虚构的故事：拜占庭帝国的将军们围攻一个城市，他们需要通过协调一致的行动（例如共同进攻或共同撤退）来成功。但由于将军之间的通信可能会被拦截、篡改或完全失败，以及可能存在叛徒故意传递错误的信息，将军们需要设计一个机制确保忠诚的将军们能够在恶劣的条件下达成一致。

核心问题

  • 拜占庭将军问题的核心是：
    • (1) 达成共识：所有忠诚的将军必须就一个共同的行动（如进攻或撤退）达成一致。
    • (2) 容错性：即使某些将军是叛徒或发送错误信息，忠诚的将军仍需正确决策。

主要挑战

  • 拜占庭将军问题中涉及的主要挑战是：
    • (1) 不可靠的通信：消息可能被篡改、丢失或延迟。
    • (2) 恶意参与者：部分节点可能尝试通过发送矛盾或虚假的信息来破坏系统的一致性。

解决方案

  • 拜占庭容错问题的研究结果表明：
    • 在一个由 n 个节点组成的系统中，若系统中存在最多 f 个恶意节点，必须满足 n ≥ 3f + 1 的条件，才能通过某种算法实现一致性。
    • 拜占庭容错算法（Byzantine Fault Tolerance，BFT）是应对这一问题的具体解决方案，如：
      • 实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）
      • 使用 Raft 和 Paxos 等分布式一致性算法（尽管这些算法并非专门针对拜占庭问题而设计）
      • 使用区块链技术中的共识算法（如 PoW、PoS 等）

应用场景

  • 拜占庭将军问题的解决方案广泛应用于以下领域：
    • 分布式系统：如分布式数据库和分布式存储。
    • 区块链：确保交易一致性和防篡改。
    • 航空航天和军事通信：保证关键系统的可靠性。

通过研究拜占庭将军问题，工程师们能够设计更加可靠、容错的分布式系统，为实际应用提供理论和技术支持。

Paxos 算法

Paxos 算法的概念

  • 什么是 Paxos 算法

    • 一种基于消息传递且具有高度容错特性的一致性算法。

  • Paxos 算法解决的问题

    • 如何快速正确地在一个分布式系统中对某个数据值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

Paxos 算法的描述

在一个 Paxos 系统中，首先将所有节点划分为 Proposer（提议者）、Acceptor（接受者）和 Learner（学习者）。特别注意，每个节点都可以身兼数职。

一个完整的 Paxos 算法流程分为三个阶段:

  • (1) 准备阶段（Prepare）

    • Proposer 向多个 Acceptor 发出 Propose（提议）请求 Promise（承诺）
    • Acceptor 针对收到的 Propose（提议）请求进行 Promise（承诺）

  • (2) 接受阶段（Accept）

    • Proposer 收到多数 Acceptor 承诺的 Promise 后，向 Acceptor 发出 Propose 请求
    • Acceptor 针对收到的 Propose 请求进行 Accept 处理

  • (3) 学习阶段（Learn）

    • Proposer 将形成的决议发送给所有 Learners

Paxos 算法的流程

工作流程

  • (1) Prepare

    • Proposer 生成全局唯一且递增的 Proposal ID，向所有 Acceptor 发送 Propose 请求，这里无需携带提案内容，只携带 Proposal ID 即可。

  • (2) Promise

    • Acceptor 收到 Propose 请求后，做出 “两个承诺，一个应答”。
      • 不再接受 Proposal ID 小于等于（注意：这里是 <=）当前请求的 Propose 请求。
      • 不再接受 Proposal ID 小于（注意：这里是 <）当前请求的 Accept 请求。
      • 不违背以前做出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。

  • (3) Propose

    • Proposer 收到多数 Acceptor 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value 作为本次要发起的提案。
    • 如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value；然后携带当前 Proposal ID，向所有 Acceptor 发送 Propose 请求。

  • (4) Accept

    • Acceptor 收到 Propose 请求后，在不违背自己之前做出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。

  • (5) Learn

    • Proposer 收到多数 Acceptor 的 Accept 后，决议形成，将形成的决议发送给所有 Learner。

推演举例

下面针对上述 Paxos 算法的工作流程做三种情况的推演举例，为了简化流程，这里不设置 Learner。

推演情况一

  • 有 A1、A2、A3、A4、A5 这 5 位议员，就税率问题进行决议
  • A1 发起 1 号 Proposal（提案）的 Propose（提议），等待 Promise（承诺）
  • A2 ~ A5 回应 Promise
  • A1 在收到两份回复时，就会发起税率 10% 的 Proposal
  • A2 ~ A5 回应 Accept
  • 通过 Proposal，决定税率定为 10%
推演情况二

  • 现在假设在 A1 提出提案的同时，A5 决定将税率定为 20%
  • A1、A5 同时发起 Propose（序号分别为 1、2）
  • A2 承诺 A1，A4 承诺 A5，A3 的承诺行为成为关键
  • 情况一：A3 先收到 A1 消息，承诺 A1
  • A1 发起 Proposal（1，10%），A2、A3 接受
  • 之后 A3 又收到 A5 消息，回复 A1（1，10%），并承诺 A5
  • A5 发起 Proposal（2，20%），A3、A4 接受，之后 A1、A5 同时广播决议
推演情况三

  • 现假设在 A1 提出提案的同时，A5 决定将税率定为 20%
  • A1、A5 同时发起 Propose（序号分别为 1、2）
  • A2 承诺 A1，A4 承诺 A5，A3 的承诺行为成为关键
  • 情况二：A3 先收到 A1 消息，承诺 A1；之后立刻收到 A5 消息，承诺 A5
  • A1 发起 Proposal（1，10%），无足够响应，A1 重新发起 Propose（序号 3），A3 再次承诺 A1
  • A5 发起 Proposal（2，20%），无足够响应，A5 重新发起 Propose (序号 4)，A3 再次承诺 A5
  • ……（循环往复）

造成上述循环往复情况的原因是系统中有一个以上的 Proposer（提议者），多个 Proposers（提案人）相互争夺 Acceptor，造成迟迟无法达成一致的情况。针对这种情况，一种改进的 Paxos 算法被提出：从系统中选出一个节点作为 Leader，只有 Leader 能够发起提案。这样就可以保证，一次 Paxos 流程中只有一个 Proposer，不会出现活锁的情况，此时只会出现例子中第一种情况。

Paxos 算法的缺陷

在网络复杂的情况下，一个使用 Paxos 算法的分布式系统，可能很久无法收敛，甚至陷入活锁的情况。

ZAB 协议

ZAB 协议的概念

ZAB 借鉴了 Paxos 算法，是特别为 Zookeeper 设计的支持崩溃恢复的原子广播协议。基于 ZAB 协议，Zookeeper 被设计为只有一个节点（Leader）负责处理外部的写事务请求，然后 Leader 节点将数据同步到其他 Follower 节点。即 Zookeeper 只有一个 Leader 节点可以发起提案。

ZAB 协议的内容

ZAB 协议包括两种基本模式：消息广播、崩溃恢复。

消息广播

  • (1) 客户端发起一个写操作请求
  • (2) Leader 节点将客户端的请求转化为事务 Proposal（提案），同时为每个 Proposal 分配一个全局的 ID（即 zxid）。
  • (3) Leader 节点为每个 Follower 节点分配一个单独的队列，然后将需要广播的 Proposal 依次放到队列中去，并且根据 FIFO 策略进行消息发送。
  • (4) Follower 接收到 Proposal 后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向 Leader 反馈一个 ACK 响应消息。
  • (5) Leader 接收到超过半数以上 Follower 的 ACK 响应消息后，即认为消息发送成功，可以发送 Commit 消息了。
  • (6) Leader 向所有 Follower 广播 Commit 消息，同时自身也会完成事务提交。Follower 接收到 Commit 消息后，会将上一条事务提交。
  • (7) Zookeeper 采用 ZAB 协议的核心，就是只要有一台节点提交了 Proposal，就要确保所有的节点最终都能正确提交 Proposal。

崩溃恢复

一旦 Leader 节点出现崩溃或者由于网络原因，导致 Leader 节点失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式。崩溃恢复主要包括两部分：Leader 选举和数据恢复。

  • 假设有以下两种服务器异常情况：

    • (1) 假设一个事务在 Leader 提出之后，Leader 宕机了。
    • (2) 一个事务在 Leader 上提交了，并且过半的 Follower 都响应 ACK 了，但是 Leader 在 Commit 消息发出之前宕机了。

  • ZAB 协议崩溃恢复要求满足以下两个要求：

    • (1) 确保已经被 Leader 提交的提案 Proposal，必须最终被所有的 Follower 节点提交（已经产生的提案，Follower 必须执行）。
    • (2) 确保丢弃已经被 Leader 提出的，但是没有被提交的 Proposal（丢弃胎死腹中的提案）。
Leader 选举

根据上述要求，ZAB 协议需要保证选举出来的新 Leader 满足以下条件：

  • (1) 新选举出来的 Leader 不能包含未提交的 Proposal，即新 Leader 必须都是已经提交了 Proposal 的 Follower 节点。
  • (2) 新选举的 Leader 节点中必须含有最大的 zxid，这样做的好处是可以避免 Leader 节点检查 Proposal 的提交和丢弃工作。
数据恢复

ZAB 是如何执行数据同步的：

  • (1) Leader 选举完成后，在正式开始工作之前（接收事务请求，然后提出新的 Proposal），Leader 节点会首先确认事务日志中的所有的 Proposal 是否已经被集群中过半的服务器 Commit。

  • (2) Leader 节点需要确保所有的 Follower 节点能够接收到每一条事务的 Proposal，并且能将所有已经提交的事务 Proposal 应用到内存数据中。等到 Follower 将所有尚未同步的事务 Proposal 都从 Leader 节点上同步过来，并且应用到内存数据中以后，Leader 才会把该 Follower 加入到真正可用的 Follower 列表中。

CAP 理论

CAP 理论的概念

CAP 理论是指一个分布式系统不可能同时满足以下三个条件：

  • 一致性（Consistency）

    • 在分布式环境中，一致性是指数据在多个副本之间是否能够保持数据一致的特性。
    • 在一致性的需求下，当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据仍然处于一致的状态。

  • 可用性（Available）

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

  • 分区容错性（Partition Tolerance）

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

这三个基本条件，最多只能同时满足其中的两个，因为分区容错性是必须要满足的，因此往往选择就在 CP 或者 AP 之间。值得一提的是，ZooKeeper 保证的是 CP。

  • (1) ZooKeeper 不能保证每次服务请求的可用性。在极端环境下，ZooKeeper 可能会丢弃一些请求，客户端需要重新发送请求才能获得结果。所以说，ZooKeeper 不能保证服务可用性。
  • (2) ZooKeeper 集群进行 Leader 选举时，整个集群都是不可用，往往需要几十秒甚至一两分钟才能恢复过来。

特别注意

  • Eureka 保证的是 AP。
  • ZooKeeper 保证的是 CP。
  • Nacos 保证的是 AP 或者 CP（可以通过配置来选择），默认是保证 AP。在 Nacos 中，AP 是基于 Distro 协议实现，CP 是基于 Raft 协议实现。

Base 理论

BASE 理论的概念

eBay 的架构师 Dan Pritchett 源于对大规模分布式系统的实践总结，在 ACM 上发表文章提出 BASE 理论。BASE 理论是对 CAP 理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP 的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consitency）。BASE 是以下三个原则的缩写：

  • Basically Available（基本可用）

    • 系统保证基本可用性，即系统在大部分时间内是可用的，但不一定保证在所有情况下都能正常处理所有请求。例如，在部分系统节点发生故障时，系统仍然能够提供服务，但可能会有部分功能受限或性能下降。

  • Soft State（软状态）

    • 软状态也称为弱状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

  • Eventually Consistent（最终一致性）

    • 系统保证在没有新的更新操作后，经过一段时间后，所有数据副本最终会达到一致状态。这与 ACID 中的强一致性（即在事务完成后，所有数据立即一致）不同，最终一致性允许在短期内存在不一致，但最终会达到一致。

总结

BASE 理论常用于 NoSQL 数据库和大规模分布式系统中，如 Cassandra、Amazon DynamoDB 等。这些系统通过放松一致性要求，以换取更高的可用性和分区容忍度，适应大规模、分布式环境中的高并发和高性能需求。总的来说，BASE 理论在分布式系统中强调的是可用性和扩展性，通过接受短期的不一致性来实现系统的高可用性和高性能。

CAP 与 BASE 的关系

BASE 是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于 CAP 定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），更具体地说，是对 CAP 中 AP 方案的一个补充。其基本思路就是：通过业务，牺牲强一致性而获得可用性，并允许数据在一段时间内是不一致的，但是最终达到一致性状态。