ᓫ (°⌑°) ǃ
归档 标签 分类 关于
ᓫ (°⌑°) ǃ

Contents

分布式

 included in 面试
   31461 words   63 minutes    views  
Contents

[toc]

一些比较好的文档：

常见面试题

RAFT 算法

  • 主节点选举过程？
  • 怎么保证个节点的一致性？G

一、分布式理论和一致性模型

==CAP==

  • Consistency（一致性）：所有节点访问同一份最新的数据副本；
  • Availability（可用性）：非故障的节点在合理的时间内返回合理的响应（不是错误或者超时的响应）；
  • Partition Tolerance（分区容错性）：分布式系统出现网络分区的时候，仍然能够对外提供服务。
img

**注：**什么是网络分区？

分布式系统中，多个节点之前的网络本来是连通的，但是因为某些故障（比如部分节点网络出了问题）某些节点之间不连通了，整个网络就分成了几块区域，这就叫 网络分区。

问：所谓的 “3选2” ？

其实不是任意的 “3选2”。

当发生网络分区的时候，如果我们要继续服务，那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提，决定了 P 之后才有 C 和 A 的选择。也就是说分区容错性（Partition tolerance）我们是必须要实现的。

==简而言之就是：==CAP 理论中分区容错性 P 是一定要满足的，在此基础上，只能满足可用性 A 或者一致性 C。

因此，分布式系统理论上不可能选择 CA 架构，==只能选择 CP 或者 AP 架构==。

问：为啥不可能同时满足 CAP 呢？

  • 首先，分布式系统要保障整体的服务，就必须拥有分区容错性 P。

  • 然后，可以举个例子。若系统发生“分区”，分为A、B：

    • 有写请求进来，修改了 A 中某数据，正常情况下要同步给 B，但分区状态，发生同步失败；

    • 此时，B 来了读请求，要么保证一致性，阻塞请求，等待分区状态结束再继续服务；要么保证可用性，返回给旧的数据。

==BASE==

BASE：Basically Available（基本可用）、**Soft-state（软状态）**和 Eventually Consistent（最终一致性）。

  • **基本可用：**指分布式系统在出现不可预知故障的时候，允许损失部分可用性。损失部分可用性，例如响应时间变长，系统提供的功能变少等；
  • **软状态：**允许系统存在短暂的数据不一致；
  • 最终一致性：系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。

AP 方案只是在系统发生分区的时候放弃一致性，而不是永远放弃一致性。在分区故障恢复后，系统应该达到最终一致性。

==一致性模型==

分布式系统按照对一致性要求的不同，主要分为强一致性，弱一致性这两大类，前者是基于 safety 的概念，后者是基于 liveness 的概念。

强一致性

顺序一致性：如果一个并发执行过程所包含的所有读写操作能够重排成一个全局线性有序的序列，并且这个序列满足以下两个条件，那么这个并发执行过程就是满足顺序一致性的：

  • 重排后的序列中每一个读操作返回的值，必须等于前面对同一个数据对象的最近一次写操作所写入的值；
  • 原来每个进程中各个操作的执行先后顺序，在这个重排后的序列中必须保持一致。

**线性一致性：**和顺序一致性很相似，除了满足上面两个条件外，还需要满足：

  • 不同进程的操作，如果在时间上不重叠，那么它们的执行先后顺序，在这个重排后的序列中必须保持一致。

区别：

  • 线性一致性考虑了时间先后顺序，而顺序一致性没有。
  • 满足线性一致性的执行过程，肯定都满足顺序一致性；反之不一定。
  • 线性一致性总是能读到最新的数据，顺序一致性有可能读到旧版本的数据。
弱一致性

弱一致性是指系统在数据成功写入之后，不承诺立即可以读到最新写入的值，也不会具体承诺多久读到，但是会尽可能保证在某个时间级别之后，可以让数据达到一致性状态。其中包括了最终一致性。

问：那共识和一致性有什么区别？

  • 一致性指的是分布式系统中多个副本对外呈现的数据状态，比如顺序一致性、线性一致性等。
  • 共识则指的是分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程，比如Paxos、Raft等算法。

因此，一致性描述的是结果状态，共识则是达成一致性的一种手段。

错误类型与错误容忍(Fault Tolerance)

在分布式系统当中可能出现的错误主要有两种：

  • CF (Crash Fault)：宕机故障，系统中的某些节点可能出现宕机故障，不会响应请求，但是不会恶意响应；
  • BF (Byzantine Fault): 拜占庭故障，系统中的某些节点可能出现拜占庭故障，可能会不响应请求，也可能错误响应请求。

出现拜占庭故障的节点我们称为拜占庭节点。

  • 能够容忍宕机故障的系统我们称为 CFT（Crash Fault Tolerance）系统；
  • 能够容忍拜占庭故障的系统我们称为 BFT（Byzantine Fault Tolerance）系统。

二、Paxos 算法

概述

主要包括两部分：

  • Basic Paxos 算法：描述的是多节点之间如何就某个值(提案 Value)达成共识。

  • Multi-Paxos 思想：描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。Multi-Paxos 说白了就是执行多次 Basic Paxos ，核心还是 Basic Paxos 。

Basic Paxos 中存在 3 个重要的角色：

提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。

接受者（Acceptor）：也可以叫做投票员（voter），负责对提议者的提案进行投票，同时需要记住自己的投票历史；

学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

image-20230309204849800

Multi-Paxos 思想：

思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识。

也就是说：Basic Paxos 是 Multi-Paxos 思想的核心，Multi-Paxos 就是多执行几次 Basic Paxos。

两阶段

prepare 阶段
  • Proposer提案者：负责提出 proposal。在提出提案时都会首先获取到一个 具有全局唯一性的、递增的提案编号 N，然后将该编号关联其要提出的提案，在第一阶段是只将提案编号发送给所有的表决者；
  • Acceptor表决者：每个表决者在 accept 某提案编号后，会将该提案编号N记录在本地，这样每个表决者中保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案，在批准提案时表决者会将以前接受过的最大编号的提案作为响应反馈给 Proposer 。
accept 阶段
  • 当Proposer收到超过半数的Accepter的响应后，就会发送提案的内容与编号；
  • 当Accepter收到提案内容与编号后，若提案编号是自己批准过的最大编号，那就Accept该提案。

三、RAFT 算法

动态演示

RAFT 只有三种类型的节点：

  • **Leader：**负责发起心跳，响应客户端，创建日志，同步日志。

  • Candidate：Leader 选举过程中的临时角色，由Follower转化而来，发起投票参与竞选。

  • **Follower：**接受Leader的心跳和日志同步数据，投票给 Candidate。

任期(Term)

img

RAFT 算法划分任意时间长度的任期(Term)，任期用连续的数字表示，看作当前 term 号。

问：Term 号的作用？

每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号。

  • 如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值；
  • 如果一个**Candidate或者Leader**发现自己的 term 过期了，他会立即退回成 Follower；
  • 如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求。

日志(Log)

entry：每一个事件成为 entry，只有 Leader 可以创建 entry。entry 的内容为<term, index, cmd>，其中 cmd 是可以应用到状态机的操作。

log：由 entry 构成的数组，每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机中。

RAFT 强化了 Leader 的地位，日志算法只能由 Leader 复制给其他成员，这意味着日志复制是单向的，Leader 从不会覆盖本地日志，即所有的日志均以 Leader 为基准。

==Leader 选举==

RAFT 使用心跳机制来触发Leader的选举。

如果一台服务器能够收到来自Leader或者Candidate的有效信息，那么它会一直保持为Follower状态，并且刷新自己的 election计时器，重新计时。

image-20230308205046274

问：选主过程？

每个Follower节点都保持一个election计时器，如果一个Follower在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为此时没有可用的 Leader，并且开始进行一次选举以选出一个新的 Leader：

  • Follower 会自增自己的term号并且转换状态为 Candidate(候选者)；

  • 然后他会向所有节点发起**RequestVoteRPC(投票请求)：自身的任期 term、memberId、最新日志(即最后一个Entry)的任期 term 和 index。每个节点只有一票(保证每个Term至多只有一个Leader，避免split brain)，如果发现 候选者的任期 >= 自身任期 并且 候选者的最新日志 >= 自身的最新日志，则回复同意；这样可以保证新 leader 节点一定包含最新提交的日志**。

  • Candidate的状态会持续到以下情况发生：

    • 赢得选举：收到了来自集群内的多数选票(N/2+1)；
    • 其他节点赢得选举；
    • 一轮选举结束，无人胜出。
    image-20230308205007474

在Candidate等待选票的时候，它可能收到其他节点声明自己是Leader的心跳，此时有两种情况：

  • 该Leader的term号>=自己的term号，说明对方已经成为 Leader，则自己回退为 Follower。
  • 该Leader的term号<自己的term号，那么会拒绝该请求并让该节点更新 term。

问：会出现选不出主的情况吗？如何解决？

会。同一时刻出现多个 Candidate，导致没有Candidate获得大多数选票，如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。

RAFT 通过随机的election时间来缓解这一问题：每一个Candidate在发起选举后，都会随机化一个新的选举超时时间，一旦超时后还没完成选举，则自增自己的Term，然后发起新一轮的选举(Term 较大的有更大的概率压倒其他节点)。这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；它会在其他服务器超时之前赢得选举。

==日志复制==

问：日志复制的过程是什么样的？

  • 一旦选出Leader，它就负责所有的客户端请求。每一个客户端请求都包含一条需要被复制状态机（Replicated State Mechine）执行的命令；

  • Leader 收到客户端请求后，会生成一个 entry，包含<index, term, cmd>，再将这个entry添加到自己的日志末尾后( Append Entries)；

  • 然后 Leader 会生成日志复制请求，包含本次待复制的日志列表(新的entry)、上一条日志(已提交的最后一个entry)等信息，并行地向所有从节点广播该请求；

  • Follower收到日志复制请求后：

    • 如果发现 leader 的任期 >= 自身任期 并且 日志一致性检查 通过，就接受待复制的日志列表，同时返回给Leader同意；
    • 否则，返回拒绝。

  • 如果Leader收到了多数的成功响应，Leader 会将这个entry应用到自己的状态机中，之后可以认为这个entry是 committed 的，并且向客户端返回执行结果。

==RAFT 保证以下两个性质：==

  • 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd。
  • 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同

第一条通过**只有Leader才能生成entry来保证；第二条通过一致性检查**来保证。

问：一致性检查的过程是怎样的？/如何保证节点一致性？⭐⭐

  • leader 在通过AppendEntriesRPC和follower通讯时，会携带**上一个entry **的信息；
  • follower在收到后会对比自己的日志：如果发现这个entry的信息(index、term)和自己日志内的不匹配，则会拒绝该请求；
  • 一旦leader发现有follower拒绝了请求，则会与该follower不断进行一致性检查，直到找到双方最大的共识点，然后用leader的entries记录覆盖follower在最大共识点之后的所有数据。

这样，主从节点就一致了。

问：一致性检查失效的情况？如何解决呢？

在出现网络分区时，不同分区A、B就会出现不同的Leader，然后两个分区就有可能出现日志不一致(因为没办法同步了呀)，例如：

image-20230308220014209

如果分区状态结束，重新合并为一个区，Term号小的节点就会找到和**Term大的节点**的日志中最后一个相同的entry，并回滚该位置之后的所有entry，然后复制Term大的节点的日志Append到后面，此时所有节点的日志就一致了。

问：参加选举的节点有没有什么限制？

**Leader 需要保证自己存储全部已经提交的日志条目。**这样才可以使日志条目只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的日志条目。

**每个 Candidate 发送 RequestVoteRPC 时，都会带上最后一个 entry 的信息。**所有节点收到投票信息时，会对该 entry 进行比较，如果发现自己的更新，则拒绝投票给该 Candidate。

**判断日志新旧的方式：**如果两个日志的 term 不同，term 大的最新；如果 term 相同，index 大的最新。

问：节点崩溃会发生什么？

  • Leader节点崩溃：集群中的节点在electionTimeout时间内没有收到Leader的心跳信息就会触发新一轮的选主，在选主期间整个集群对外是不可用的；
  • Follower、Candidate节点崩溃：那么发送给它的 RequestVoteRPC 和 AppendEntriesRPC 会失败，但由于 raft 的所有请求都是幂等的，所以失败的话会无限的重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。

问：RAFT 中的各种时间设置？

1

broadcastTime << electionTimeout << MTBF
  • broadcastTime：向其他节点并发发送消息的平均响应时间；
  • electionTimeout：选举超时时间；
  • MTBF(mean time between failures)：单台机器的平均健康时间；

broadcastTime应该比electionTimeout小一个数量级，为的是使Leader能够持续发送心跳信息（heartbeat）来阻止Follower开始选举；

electionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。当Leader崩溃时，大约会在整个electionTimeout的时间内不可用。我们希望这种情况仅占全部时间的很小一部分。

由于broadcastTime和MTBF是由系统决定的属性，因此需要决定electionTimeout的时间。

一般来说，broadcastTime 一般为 0.5～20ms，electionTimeout 可以设置为 150～300ms，MTBF 一般为一两个月。

日志压缩

同其他系统一样，日志总不能无限制的增长，这样不仅会导致日志文件很大，还会导致恢复数据时执行日志的时间很长。因此，需要定时的快照(snapshot)。snapshot 会包括：

  • 状态机当前的状态；
  • 状态机最后一条应用的 entry 对应的 index 和 term；
  • 集群最新配置信息；
  • 为了保证 exactly-once 线性化语义的去重表。

各个节点自行完成自己的 snapshot，当 Leader 发现需要发给某个 Follower 的 nextIndex 已经被做成了 snapshot，则可以直接把这个 snapshot 发送给 Follower，Follower 收到 snapshot 后，检查是否过期，不过期的话，直接用这个 snapshot 覆盖本地的所有状态即可。

问：啥时候进行 snapshot 呢？

定时或者定大小，达到阈值就 snapshot。

问：做 snapshot 时是否还可继续提供写请求？

一般情况下，做 snapshot 期间需要保证状态机不发生变化，也就是需要保证 snapshot 期间状态机不处理写请求。

但其实，还可以去向其他节点同步，就是不能 Commit，也就是不能改变状态机的状态。

预投票

问：预投票机制是为了解决啥？是咋实现的？

**主要是为了避免：**一个暂时脱离集群网络的节点，在重新加入集群后会干扰到集群的运行。

**场景是这样的：**一个离群节点，收不到 Leader 的心跳包，就会导致它的 ElectionTimeout 超时，然后他就会自增自己的 Term 并发起选举，但他收不到其他节点的投票，再次超时后，就会继续自增自己的 Term，持续自增就会导致该节点的 Term 显著高于集群其他节点的 Term，当他突然又恢复了和集群的联系，他的高 Term 就会导致 Leader 退位，但实际上这是不合理的。

**引入 Pre-Vote 机制后：**一个 candidate 必须在获得了多数赞同的情形下，才会增加自己的 Term。一个节点在满足下述条件时，才会投票给一个 candidate：

  • 该 candidate 的日志足够新；
  • 当前节点的 ElectionTimeout 已经超时。

这样的话，离群节点只会不断的发起 Pre-Vote，而不会更新自己的 Term。

四、PBFT 算法

参考文章：

简介

PBFT 是 Practical Byzantine Fault Tolerance 的缩写，意为实用拜占庭容错算法。

该算法首次将拜占庭容错算法复杂度从指数级降低到了多项式级，其可以在恶意节点不高于总数 1/3 的情况下同时保证安全性（Safety）和活性（Liveness）。

约定变量

  • 集群数量定义为 N，其数量定义为 ∣N∣=n
  • 拜占庭或者是宕机节点集合为定义为 F，其数量定义为 ∣F∣=f
  • quorum 法定成员集合Q，即每次访问的节点数量∣Q∣

术语

  • Primary: 主节点

  • Replica: 副本节点

  • Client: 客户端，用于向共识集群发送消息，请求共识

  • View: 视图，Primary 和 Replica 共同达成的一个状态视图，所有节点都基于某个视图进行共识

  • Sequence Number：序列号，由主节点生成的序列号，用于标识共识轮次

  • Check Point: 检查点，如果某个序列号被确认，则成为检查点

  • Stable checkpoint: 稳定检查点，该检查点通常会被持久化

N > 3f + 1

这里先提出一个问题：在分布式系统中需要读写多少台节点才可以满足正确性要求，即 quorum 的值为多少比较合适？

先给出结论：

  • 在 CFT 系统中，只需要达到2f + 1就可以了；
  • 在 BFT 系统中，就需要达到3f + 1才行，因为是允许同时存在故障节点和拜占庭节点的。

给出分析：

节点总数是n，其中作恶节点有f，那么剩下的正确节点为n - f，意味着只要收到n - f个消息就能做出决定，但是这n - f个消息有可能有f个是由作恶节点冒充的，那么正确的消息就是n - f - f个，为了多数一致，正确消息必须占多数，也就是 n - f - f > f，但是节点必须是整数个，所以 n 最少是 3f + 1 个。

算法流程

约定符号

  • i：节点ID(replica id)，应该是在 [0, N−1] 范围内的值；
  • v#：视图编号(view number)，初始为零，用 v# 表示；
  • Primary：主节点，通常采用模运算取得: Primary = v# mod N；
  • m：即本轮共识的具体操作，可以是数据库操作，也可以是区块写入操作；
  • d(m)：是m的摘要信息(digest)；
  • seq# 为 sequence number；
  • log：操作日志，通常记录了当前收到的消息，形式为 <v#, seq#, status, d>
    • status 为 pre-prepared 、prepared或者是committed；

消息结构

image-20230422213246397

这里列出了三阶段协议相关的消息结构，其中只有 PRE-PREPARE 消息包含新生成的区块，其他消息则主要包含一些 id、sequence number、区块摘要和签名等信息。

核心过程

image-20230422210933188

  • STEP 1: 客户端发送请求给主节点(或者发给所有节点)，之后主节点将会触发三阶段协议。这里可以有一个优化，节点可以先把请求缓存起来，等到攒够一堆请求之后再一起发送，这样可以降低网络开销和系统负载。

  • STEP 2: 主节点收到客户端发送来的消息后，构造pre-prepare消息结构体 <<PRE-PREPARE, v#, seq#, d, sig>, m> (p)，其中 (p) 表示由主节点发出，d是当前消息摘要，m为原始消息，sig 为d的数字签名

    1. PRE-PREPARE标识当前消息所处的协议阶段；
    2. v#标识当前视图编号；
    3. seq#为主节点广播消息的一个唯一递增序号；
    4. d为m的消息摘要；
    5. sig 为d的数字签名；
    6. m为客户端发来的消息。

  • STEP 3: 从节点检查主节点发送的 pre-prepare 消息，检查通过会存储在本节点日志。检查通过会进入PREPARE状态，广播消息<PREPARE, v#, seq#, d, i,> (i)，其中 (i) 标识从i节点发出。消息的有效性检查过程如下：

    1. 检查收到的消息体中摘要d，是否和自己对m生成的摘要一致，确保消息的完整性。
    2. 检查v#是否和当前视图v#一致。
    3. 检查序号seq#是否在水线h和H之间，避免快速消耗可用序号。
    4. 检查之前是否接收过相同序号seq#和v#，但是摘要d不同的消息。

  • STEP 4: 所有节点收到PREPARE消息后，同样也会对消息进行有效性检查，检查的内容也是 STEP3 中的1, 2, 3, 4。

    • 当收到2f(包括自己)个检查通过且一致的PREPARE消息后，会进入COMMIT阶段，并且广播消息<COMMIT, v#, seq#, d, i> (i)
      • 2f-1 个从其他节点收到的prepare消息(不包括自己的)。这里是因为主节点不会再发送prepare消息，因此收到2f-1个prepare，加上主节点的pre-prepare，以及自己的prepare，就是2f+1个了；

  • STEP 5: 所有节点收到COMMIT消息后，同样也会对消息进行有效性检查，检查的内容也是 STEP3 中的1, 2, 3, 4。

    • 当收到2f+1(包括自己)个检查通过且一致的COMMIT消息后，进入committed-local状态，按照m中的请求顺序执行操作。
    • 执行完成之后，所有节点将发送结果给到客户端。

  • STEP 6: 客户端收到超过2f+1的一致消息则确认当前结果成功

整个过程不需要要求所有的消息是有序到达的，因为seq#会保证顺序，只需要对应的pre-prepare，prepare和commit消息都是完整的即可。

一种优化流程

以下是基于公开资料收集的 Hyperchain 优化之后的 RBFT 算法

image-20230422213644093

主要优化点：

  • 客户端可以发送请求到任意节点，如果这个节点不是主节点的话，将会进行一次广播；(类似读写分离)
  • 主节点收到交易之后会先进行验证，并把验证结果放在pre-prepare中，并且pre-prepare是以区块为单位处理的，这样的 pre-prepare 消息中既包含了排好序的交易信息也包含了区块验证结果；
  • 从节点收到pre-prepare后，也是先验证消息的合法性，然后广播prepare。不同的是，在收到2f个prepare后会对区块内容进行验证，并与pre-prepare中的验证结果对比，若一致，则广播 commit 表明本节点同意主节点的验证结果；若不一致，直接发起 view-change 表明本节点认为主节点存在异常行为，需要切换主节点。

RBFT 具体流程：

  • **交易转发阶段：**客户端将交易发送到区块链中的任意节点（包括共识节点与记账节点），其中记账节点在收到交易后会主动转发给与其相连的共识节点；而共识节点在收到客户端的交易后将其广播给其他共识节点，这样所有共识节点的交易池中都会维护一份完整的交易列表；

共识节点就是参与RBFT共识过程的节点，记账节点是不参与共识，只接受结果并写入区块的节点

  • PrePrepare 阶段：主节点按照如下策略进行打包：用户可以根据需求自定义打包的超时时间（batch timeout）与打包的最大区块大小（batch size），主节点在超时时间内收集到了足够多（超过最大区块大小个数）的交易或者超时时间到达后仍未收集到足够多的交易都会触发主节点的打包事件。主节点将交易按照接收的时间顺序打包成块，并进行验证，计算执行结果，最后将定好序的交易信息连同验证结果等写入 pre-prepare 消息中，广播给所有共识节点，开始三阶段处理流程；
  • Prepare 阶段： 从节点在收到主节点的 pre-prepare 消息后，首先进行消息合法性检查，检查当前的视图与序列号号等信息，检查通过后向共识节点广播 prepare 消息；
  • **Commit 阶段：**从节点在收到quorum-1 即(2f) 个prepare 消息以及相应的 pre-prepare 消息后进行验证，并将验证结果与主节点写入pre-prepare 消息中的验证结果进行比对，比对结果一致则广播 commit 表明本节点同意主节点的验证结果，否则直接发起 view-change 表明本节点认为主节点存在异常行为，需要切换主节点；
  • **写入账本：**所有共识节点在收到 quorum 个 commit 消息后将执行结果写入本地账本。

日志压缩

PBFT的每个阶段都写入了日志，长时间运行内存总会不够用，需要一种日志压缩机制。PBFT通过检查点实现日志压缩，其本质和RAFT算法采用快照的形式清理日志是一样的，只是实现的方式不同。

为每一次操作创建一个集群中稳定检查点，代价是非常昂贵的。因此，PBFT为常数k个操作创建一次稳定检查点，比如每100个操作创建一次检查点checkpoint，当这个checkpoint得到集群中多数节点认可以后，就变成了稳定检查点stable checkpoint。

总之，稳定检查点是一个确定性的系统状态快照，可以用来恢复系统状态，类比于**RDB快照**；而水位线[h, H]间的消息就相当于**AOF文件**。

稳定检查点

生成过程：

  • 当 replica i 生成了一个 checkpoint，将广播消息 <CHECKPOINT, seq#, d(state), i>，其中，seq#是最后一次执行的消息序号，d是seq执行后的状态机状态的摘要；
  • 当所有节点收到了2f+1个拥有相同的 seq# 和 d(state) 的检查点消息(包括自己)后，将会生成stable checkpoint。

作用：

  • 当stable checkpoint生成之后，将会删除stable checkpoint之前(seq#之前)的 pre-prepare、prepare、commit消息，日志就被压缩了，并且稳定检查点是一个确定性的系统状态快照，可以用来恢复系统状态。

  • 同时checkpoint还有一个**提高水线(water mark)**的作用，当一个stable checkpoint被创建的时候，水线h被修改为stable checkpoint的seq#，水线H为h + k而k就是之前用到创建checkpoint的那个常数。

水位线

水位线机制用于限制消息序号的有效范围，包括：

  • 低水位线(low-water mark) h；
  • 高水位线(high water mark) H = h + k。

设置规则：

通常来讲，低水位线是最近的一个稳定检查点的seq#，而高水位线需要在低水位线上加上一个常量k。

  • k要足够大，避免需要频繁创建稳定检查点；
  • 但**k又不能太大**，避免出现故障或错误，进行状态恢复时需要重放大量的请求数量。

作用：

  • 在共识进行的过程中，由于节点之间的性能差距，可能会出现节点间运行速率差异过大的情况。部分节点执行的序号可能会领先于其他节点，导致于领先节点的共识数据长时间得不到清理，造成内存占用过大的问题，而高低水位的作用就是对集群整体的运行速率进行限制，从而限制了节点的共识数据大小。在执行到最高水位 H 时，如果低水位 h 没有被更新，节点会暂停执行序号更大的请求，等待其他节点的执行，待低水位 h 更新后重新开始执行更大序号的请求。

视图切换

视图切换(view-change)是为了保证系统的高可用性，主要发生在：

  • 主节点超时；
  • 从节点认为主节点是拜占庭节点。

view-change通过定时器来进行切换，避免从节点长时间等待请求。

原文中是这样做的：在通常情况下，主节点将会发送 pre-prepare 来正常进行共识，从节点也可以通过该消息确认主节点是否存活，因此如果超过一段时间没有收到 pre-prepare 的话就会认为该主节点有问题；

工程上：在实际运行当中，长时间没有pre-prepare是常见的，因此一般会通过心跳+定时器来进行探测保活。

View-Change 过程

image-20230423150450984

当从节点收到请求时，如果有定时器在运行就重置(reset)定时器，否则开启一个定时器。但是主节点宕机的时候，从节点i就会在当前视图v#中超时，这个时候该从节点i就会触发view-change：

  • 从节点i会将视图切换为v#+1，停止接收除了checkpoint，view-change和new view-change以外的请求，同时广播消息<VIEW-CHANGE, v#+1, seq#(stable_checkpoint), C-set, P-set, i> (i)到集群：

    1. seq#是节点i知道的最后一个stable checkpoint的消息序号；
    2. C-set是节点i保存的 2f+1 个能够证明seq#(stable_checkpoint)是正确检查点的的消息集合；
    3. P-set是一个保存了seq#之后所有已经达到prepared状态消息的集合，通过P-set可以把原来的在稳定检查点之后确定的交易进行重新共识。

  • 当视图(v#+1)中的**新主节点p1**接收到2f个有效的视图切换消息以后，p1就会广播消息<NEW-VIEW, v#+1, V-set, Q-set> (p)：

    1. V-set是p1收到的，包括自己发送的view-change的消息集合；
    2. Q-set是PRE-PREPARE状态的消息集合，是从P-set转换过来的：
      • 主节点根据最新stable_checkpoint的seq# s 和P-set的最大seq# t，将[s, t]间的所有seq#创建pre-prepare消息成为Q-set；

  • 从节点接收到NEW-VIEW消息后，校验签名，V和Q中的消息是否合法，如验证通过，将执行Q-set中的请求，然后主节点和从节点都进入视图v#+1。

C、P、Q

当p1接收到2f个VIEW-CHANGE消息以后，可以确定**stable checkpoint之前的消息在视图切换的过程中不会丢**。

但是**[当前检查点，下一个检查点]间已经通过PREPARE阶段的消息**可能会被丢弃，所以在视图切换到v+1后，PBFT会把旧视图中已经PREPARE的消息变为PRE-PREPARE，组成Q然后广播。

  • 如果集合P为空，创建<PRE-PREPARE, v#+1, seq#, null>，接收节点就什么也不做；
  • 如果集合P不为空，创建<PRE-PREPARE, v#+1, seq#, d>。

总结一下，在view-change中最重要的就是C，P，Q三个消息的集合：

  • C确保了视图变更的时候，stable checkpoint之前的状态安全；
  • P确保了视图变更前，已经PREPARE的消息的安全；
  • Q确保了视图变更后，P-set中的消息安全。

回想一下pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图(view)中的顺序是一致的，而在视图切换过程中的C，P，Q三个集合就是解决这个问题的。

Leader 选举

在介绍 view-change 时，并没有说明在新的视图中，新主节点是如何选出来的，其实不同的系统做法不同：

FISCO BCOS系统中，leader索引的计算公式如下：

1

leader_idx = (view + block_number) % node_num

主动恢复

区块链网络在运行过程中由于网络抖动、突然断电、磁盘故障等原因，可能会导致部分节点的执行速度落后于大多数节点。在这种场景下，节点需要能够做到自动恢复才能继续参与后续的共识流程。

传统的PBFT并没有实现主动恢复的功能，但**RBFT提供了一种动态数据自动恢复的机制(recovery)，recovery 通过主动索取现有共识网络中所有节点的视图、最新区块高度等信息，更新自身的存储状态，最终同步至整个系统的最新状态**。

在节点启动、节点重启或者节点落后的时候，节点将会自动进入 recovery，同步至整个系统的最新状态。

比如，一个节点落后太多，这个时候它收到主节点发来的消息时，对消息进行水位检查会失败，当计时器超时，就会发送view-change的消息，但是由于只有自己发起view-change达不到2f+1个节点的数量，本来正常运行的节点就退化为一个拜占庭节点。

视图协商

image-20230423220147320
  • 新增/落后节点Replica 4发起NegotiateView消息给其他节点；
  • 其余节点收到消息以后，返回NegotiateViewResponse消息，包含自己的视图信息，节点ID，节点总数N；
  • Replica 4收到2f+1个NegotiateViewResponse消息后，则更新本节点的视图信息；
  • Replica 4同步完视图后，广播RecoveryInit消息到其余节点，通知其他节点本节点需要进行自动恢复，请求其余节点的检查点信息和最新区块信息；
  • 其余节点收到RecoveryInit后将自身最新的检查点信息和区块信息返回给Replica 4;
  • Replica 4收到quorum个RecoveryResponse消息后，更新自己的检查点到最新；
  • 更新完成后，还要向正常节点索要P-set、Q-set和C-set的信息，同步至全网最新状态。

增删节点(随便看看而已)

传统的PBFT算法不支持节点的动态增删，RBFT 为了能够更加方便地控制联盟成员的准入和准出，添加了保持集群非停机的情况下动态增删节点的功能。

增加节点

img

Replica 5新节点加入的流程：

  • 新增节点Replica 5主动向现有的所有节点发起连接，确认所有节点连接成功后更新自身的路由表，并发起recovery；
  • 现有节点接收到Replica 5的连接请求后向全网广播AddNode消息，表明自己同意该新节点加入整个共识网络；
  • 当现有节点收到N条（N为现有区块链共识网络中节点总数）AddNode消息后，更新自身的路由表，随后开始回应新增节点的共识消息请求（在此之前，新增节点的所有共识消息是不予处理的）；
  • Replica 5完成recovery之后，向全网现有节点广播ReadyForN请求；
  • 现有节点在收到ReadyForN请求后，重新计算新增节点加入之后的N，view等信息，随后将其与PQC消息封装到AgreeUpdateN消息中，进行全网广播；
  • Replica 5加入后的共识网络会产生一个新的主节点，该主节点在收到N-f个AgreeUpdateN消息后，以新的主节点的身份发送UpdateN消息；
  • 全网所有节点在收到UpdateN消息之后确认消息的正确性，进行VCReset；
  • 每个节点完成VCReset后，全网广播FinishUpdate消息；
  • 节点在收到N-f个FinishUpdate消息后，处理后续请求，完成新增节点流程。

五、分布式ID⭐

参考文章

问：什么是分布式ID？

例如，多机 MySQL 中，也就是分库了，数据库的自增主键已经没办法满足生成的主键是唯一的了。如何在不同节点生成全局唯一的主键？

这个时候就需要 分布式ID 。

问：分布式ID 需要满足啥条件？

其实最主要的就是 全局唯一。

  • ==全局唯一==：ID 的全局唯一性肯定是首先要满足的！
  • 高性能：分布式 ID 的生成速度要快，对本地资源消耗要小。
  • 高可用：生成分布式 ID 的服务要保证可用性无限接近于 100%。

除了这些之外，一个比较好的分布式 ID 还应保证：

  • 安全：ID 中不暴露系统和业务的信息。
  • 有序递增：如果要把 ID 存放在数据库的话，ID 的有序性可以提升数据库写入速度。并且，很多时候，我们还很有可能会直接通过 ID 来进行排序。
  • 有具体的业务含义：生成的 ID 如果能有具体的业务含义，可以让定位问题以及开发更透明化（通过 ID 就能确定是哪个业务）。
  • 独立部署：也就是分布式系统单独有一个发号器服务，专门用来生成分布式 ID。这样就生成 ID 的服务可以和业务相关的服务解耦。不过，这样同样带来了网络调用消耗增加的问题。总的来说，如果需要用到分布式 ID 的场景比较多的话，独立部署的发号器服务还是很有必要的。

⭐问：分布式ID 常见的解决方案？

  1. **==数据库主键自增==**⭐

数据库自增 ID 是最常见的一种生成 ID 方式。优势是使用简单，满足基本业务需求，天然有序；缺点是强依赖 DB，会由于数据库部署的一些特性而存在单点故障、数据一致性等问题。

以 MySQL 举例，我们通过下面的方式即可。

  • 创建一个数据库表。
1
2
3
4
5
6

CREATE TABLE `sequence_id` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `stub` char(10) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

stub 字段无意义，只是为了占位，便于我们插入或者修改数据。并且给 stub 字段创建了唯一索引，保证其唯一性。

  • 通过 replace into 来插入数据。
1
2
3
4

BEGIN;
REPLACE INTO sequence_id (stub) VALUES ('stub');
SELECT LAST_INSERT_ID();
COMMIT;

插入数据这里，我们没有使用 insert into 而是使用 replace into 来插入数据，具体步骤是这样的：

  • 第一步：尝试把数据插入到表中。

  • 第二步：如果主键或唯一索引字段出现重复数据错误而插入失败时，先从表中删除含有重复关键字值的冲突行，然后再次尝试把数据插入到表中。

**优点：**实现起来比较简单、ID 有序递增、存储消耗空间小

**缺点：**支持的并发量不大、每次获取 ID 都要访问一次数据库

  1. **==数据库号段模式==**⭐⭐

数据库主键自增模式的话，某个节点每次获取 ID 都要访问一次数据库，这肯定不太好。因此，数据库号段模式就批量获取一批 ID，存在该节点的内存中，这样就可以每次用的时候就从内存中慢慢获取了，不够用了就再申请一批，美滋滋~~

以 MySQL 举例，我们通过下面的方式即可。

  • 创建一个数据库表。
1
2
3
4
5
6
7
8

CREATE TABLE `sequence_id_generator` (
  `id` int(10) NOT NULL,
  `current_max_id` bigint(20) NOT NULL COMMENT '当前最大id',
  `step` int(10) NOT NULL COMMENT '号段的长度',
  `version` int(20) NOT NULL COMMENT '版本号',
  `biz_type`    int(20) NOT NULL COMMENT '业务类型',
   PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

current_max_id 字段和step字段主要用于获取批量 ID，获取的批量 ID 为： current_max_id ~ current_max_id+step。

  1. ==Redis 自增==

优势是不依赖于数据库，使用灵活，性能也优于数据库；而缺点则是可能要引入新的组件 Redis，如果 Redis 出现单点故障问题，则会影响序号服务的可用性。

通过 Redis 的 incr 命令即可实现对 id 原子顺序递增。

1
2
3
4
5
6

127.0.0.1:6379> set sequence_id_biz_type 1
OK
127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2
127.0.0.1:6379> get sequence_id_biz_type
"2"
  1. **==UUID==**⭐

UUID 由32位的16进制数组成，可以保证唯一性，有如下生成规则：

  • 基于时间的 UUID：主要依赖当前的时间戳和机器 mac 地址。优势是能基本保证全球唯一性，缺点是由于使用了 mac 地址，会暴露 mac 地址和生成时间；
  • 基于随机数的 UUID：基于随机数或伪随机数生成。优势是实现简单，缺点是重复几率可计算；
  • 基于名字空间的 UUID(MD5 版)：基于指定的名字空间/名字生成 MD5 散列值得到，优势是不同名字空间/名字下的 UUID 是唯一的，缺点是 MD5 碰撞问题；

因为其生成规则包括 MAC 地址、时间戳、名字空间、随机或伪随机数、时序等元素，计算机基于这些规则生成的 UUID 是肯定不会重复的。

很少使用 UUID。

**优点：**生成速度快，简单易用；

**缺点：**存储消耗空间太大(128位)、无序(非常影响MySQL的性能)、没有具体业务含义、有可能出现重复 ID、不安全(基于 MAC 地址生成的话，有可能会泄露 MAC地址)

  1. **==雪花算法(Snowflake)==**⭐⭐⭐

Snowflake 由 64 bit 的二进制数字组成，这 64bit 的二进制被分成了几部分，每一部分存储的数据都有特定的含义：

image-20230420112206866

  • 第 0 位：符号位(标识正负)，始终为 0，没有用，不用管。

  • 第 1~41 位：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑 2 ^41 毫秒(约 69 年)

  • 第 42~51 位：一共 10 位，机器编码，一般来说，前 5 位表示机房 ID，后 5 位表示机器 ID(实际项目中可以根据实际情况调整)。这样就可以区分不同集群/机房的节点。

  • 第 52~63 位：一共 12 位，用来表示序列号。序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096)，也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID。

**优点：**单机生成的 ID 有序递增、生成速度比较快、比较灵活(可根据业务需求调整bit位)；

缺点：重复 ID 问题(强依赖时间，当机器时间回拨的情况下，可能导致会产生重复 ID)、ID 可能不是全局递增，虽然 ID 在单机上是递增的，但是由于涉及到分布式环境下的每个机器节点上的时钟，可能会出现不是全局递增的场景。

  1. ==利用Zookeeper==

zookeeper 是通过 树形结构 来存储数据节点的，那也就是说，对于每个节点的 全路径，它必定是唯一的，我们可以使用节点的全路径作为命名方式了。

六、分布式锁⭐

概述

分布式锁示意图：

分布式锁

一个最基本的分布式锁需要满足：

  • 多进程可见⭐：你总得让人知道有锁的存在吧？
  • 互斥⭐：任意一个时刻，锁只能被一个线程持有；
  • 高可用：锁服务是高可用的。并且，即使客户端的释放锁的代码逻辑出现问题，锁最终一定还是会被释放，不会影响其他线程对共享资源的访问。
  • 可重入：一个节点获取了锁之后，还可以再次获取锁。

分布式锁的实现，目前常用的方案有以下三类：

  1. 数据库乐观锁；
  2. 基于分布式缓存实现的锁服务，典型代表有 Redis 和基于 Redis 的 RedLock；
  3. 基于分布式一致性服务实现的锁服务，典型代表有 ZooKeeper 和 ETCD。

通常情况下，采用ZooKeeper或者Redis获得分布式锁，Redis用的多一些。

基于 Mysql 实现分布式锁

利用MySQL本身的互斥锁机制，主要是基于主键和唯一索引。比如说两个线程去同一个数据库表进行操作，利用主键冲突来保证。

基于 Redis 实现分布式锁

加解锁流程
  1. 加锁
1

SET lock_name my_random_value NX PX 30000	# SETNX 获得锁
  • lock_name：锁名(key)，在分布式环境中，对于某一确定的公共资源，所有争用方（客户端）都应该知道对应锁的名字，全局可知；
  • my_random_value：随机字符串(value)，作为持有者的唯一标识，避免误删；
  • NX：只有当lock_name不存在的时候才能 SET 成功，从而保证只有一个客户端能获得锁，而其它客户端在锁被释放之前都无法获得锁，保证互斥；
  • PX 30000：表示这个锁节点有一个 30 秒的自动过期时间，避免死锁。
  1. 释放锁

首先，向 Redis 节点发送命令，获取锁对应的 Value

1

GET lock_name

如果查询回来的 value 和客户端自身的 my_random_value 一致，则可确认自己是锁的持有者，可以发起解锁操作，即主动删除对应的 Key，发送命令：

1

DEL lock_name
安全性分析
死锁避免

典型的死锁场景：获得锁的客户端，在释放锁之前崩溃了，导致锁一直无法被释放，进而导致死锁。

为了解决该问题，对锁设置了过期时间，当锁到期后，Redis 会自动删除该锁对应的 key-value，也就释放了锁。

但存在隐患，比如这个场景：

  1. 客户端 A 获取锁成功；
  2. 客户端 A 在某个操作上阻塞了很长时间；
  3. 过期时间到，锁自动释放；
  4. 客户端 B 获取到了对应同一个资源的锁；
  5. 客户端 A 从阻塞中恢复过来，认为自己依旧持有锁，继续操作同一个资源，导致互斥性失效。

为了解决该问题，有如下方案：

  • 有隐患的方案，但网上很多都是这样做的。第 5 步中，客户端 A 恢复后，可以比较下目前已经持有锁的时间，如果发现已经过期，则放弃对共享资源的操作，即可避免互斥性失效的问题。但分布式中，各节点的时钟不一定是强一致的，导致了一定的隐患。其实，任何依赖两个节点时间比较结果的互斥性算法，都存在隐患；
  • 可取的方案。可以比较 my_random_value，即客户端 A 恢复后，在操作共享资源前应比较目前自身所持有锁的 my_random_value 与 Redis 中存储的 my_random_value 是否一致，如果不相同，说明已经不再持有锁，则放弃对共享资源的操作以避免互斥性失效的问题。
解锁操作的原子性

为了保证解锁的正确性，引入了my_random_value。具体的解锁过程就分成了两步：

  • 先查询(GET)锁对应的 Value，与自己加锁时设置的 my_random_value 进行对比；
  • 如果相同，则可确认这把锁是自己加的，然后再发起解锁(DEL)。

但是，GET 和 DEL 是两个操作如果是非原子性的，那么解锁本身也会存在破坏互斥性的可能。

比如在查询完，释放前，又阻塞了很长时间。下面是典型场景：

  1. 客户端 A 获取锁成功；
  2. 客户端 A 访问共享资源；
  3. 客户端 A 为了释放锁，先执行 GET 操作获取锁对应的随机字符串的值；
  4. 客户端 A 判断随机字符串的值，与预期的值相等；
  5. 客户端 A 由于某个原因阻塞了很长时间；
  6. 过期时间到了，锁自动释放了；
  7. 客户端 B 获取到了对应同一个资源的锁；
  8. 客户端 A 从阻塞中恢复过来，执行 DEL 操纵，释放掉了客户端 B 持有的锁。

为了解决该问题，有如下方案：

  • Redis 支持 Lua 脚本并保证其原子性，使用 Lua 脚本实现锁校验与释放，并使用 Redis 的 eval 函数执行 Lua 脚本。
1
2
3
4
5

// Lua脚本，用于校验并释放锁     
String script = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end";
// 执行Lua脚本，校验并释放锁
jedis.eval(script, Collections.singletonList("lock_name"),
        Collections.singletonList("my_random_value"));
主备切换的一致性

当主从切换时，由于 Redis 的主从复制是异步的，就可能导致切换过程中丧失锁的安全性。

典型场景：

  1. 客户端 A 从 Master 获取了锁；
  2. Master 宕机了，存储锁的 Key 还没有来得及同步到 Slave 上；
  3. Slave 升级为 Master；
  4. 客户端 B 从新的 Master 获取到了对应同一个资源的锁；
  5. 客户端 A 和客户端 B 同时持有了同一个资源的锁，锁的安全性被打破。

可以通过 RedLock 来解决。

运行 Redlock 算法的客户端依次执行以下步骤，来进行加锁的操作：

  • 获取当前系统时间（毫秒数）；

  • 按顺序依次向 N 个 Redis 节点执行获取锁的操作。这个获取操作跟前面基于单 Redis 节点获取锁的过程相同，包含随机字符串 my_random_value，也包含过期时间（比如 PX 30000，即锁的有效时间）。为了保证在某个 Redis 节点不可用的时候算法能够继续运行，这个获取锁的操作还有一个超时时间（Time Out），它要远小于锁的有效时间（几十毫秒量级）。客户端在向某个 Redis 节点获取锁失败以后，应该立即尝试下一个 Redis 节点。这里的失败，应该包含任何类型的失败，比如该 Redis 节点不可用；

  • 计算获取锁的整个过程总共消耗了多长时间，计算方法是用当前时间减去第 1 步记录的时间。如果客户端从大多数 Redis 节点（>=N/2+1）成功获取到了锁，并且获取锁总共消耗的时间没有超过锁的有效时间（Lock Validity Time），那么这时客户端才认为最终获取锁成功；否则，认为最终获取锁失败；

    • 如果最终获取锁成功了，就要重新计算这个锁的有效时间，等于最初的锁的有效时间减去第 3 步计算出来的获取锁消耗的时间；
    • 如果最终获取锁失败了（可能由于获取到锁的 Redis 节点个数少于 N/2+1，或者整个获取锁的过程消耗的时间超过了锁的最初有效时间），那么客户端应该立即向所有 Redis 节点发起释放锁的操作。

释放锁的过程比较简单：即客户端向所有 Redis 节点发起释放锁的操作，不管这些节点在获取锁的时候成功与否。

但 RedLock也有缺陷(如下场景)，一般不建议用这种方式，真要用的话，真不如用Zookeeper来做。

如下场景，假设一共有 5 个 Redis 节点：A、B、C、D、E。

  1. 客户端 1 成功锁住了 A、B、C，获取锁成功（但 D 和 E 没有锁住）。
  2. 节点 C 时间异常，导致 C 上的锁数据提前到期，而被释放。
  3. 客户端 2 此时尝试获取同一把锁：锁住了C、D、E，获取锁成功。
可重入

问：如何实现可重入锁？⭐

可重入锁指的是在一个线程中可以多次获取同一把锁，比如一个线程在执行一个带锁的方法，该方法中又调用了另一个需要相同锁的方法，则该线程可以直接执行调用的方法即可重入，而无需重新获得锁。

可重入分布式锁的实现核心思路是线程在获取锁的时候判断是否为自己的锁，如果是的话，就不用再重新获取了。

实现思路：可以为每个锁关联一个可重入计数器和一个占有它的线程。若可重入计数器大于 0，则表示锁被占有，需要判断占有该锁的线程和请求获取锁的线程是否为同一个。每次获取锁时，计数器+1，每次释放锁时，计数器-1。

问：如果对资源的操作还未结束，锁就到期了咋办？⭐

这就涉及到如何给锁优雅的续期了。有非常成熟的解决方案：Java-Redisson、Go-Redsync等。。。

**原理简单来说就是：**提供了一个专门用来监控和续期锁的 Watch Dog（ 看门狗），如果操作共享资源的线程还未执行完成的话，Watch Dog 会不断地延长锁的过期时间，进而保证锁不会因为超时而被释放。

基于 Zookeeper 实现分布式锁

主要是利用临时顺序节点。

问：怎么利用 Zookeeper 实现分布式锁呢？能实现共享锁和独占锁嘛？

主要是利用创建节点的有序性。

可以让多个客户端在指定节点(通常是持久节点)下创建临时顺序节点，判断自己创建的是否是有序节点中序号最小的那个，若是就获得锁；若不是，就通过Watcher进行监听，若自己前边的序号都失效了，就说明锁释放了，就可以通过回调函数尝试得到该锁。

https://chuyu-typora.oss-cn-hangzhou.aliyuncs.com/image/e0edfab2ec426b3ea45765d931b10a8b.png

同时实现共享锁和独占锁：

  • 读请求：如果 没有比自己更小的节点，或比自己小的节点都是读请求，则可以获取读锁；
  • 写请求：如果 没有比自己更小的节点，则可以获得写锁。

为避免羊群效应，可以让 读请求监听比自己小的最后一个写请求节点，写请求只监听比自己小的最后一个节点。

给一个帮助理解的示例：

获取锁：

  1. 首先我们要有一个持久节点/locks，客户端获取锁就是在locks下创建临时顺序节点。
  2. 假设客户端 1 创建了/locks/lock1节点，创建成功之后，会判断 lock1是否是 /locks 下最小的子节点。
  3. 如果lock1是最小的子节点，则获取锁成功。否则，获取锁失败。
  4. 如果获取锁失败，则说明有其他的客户端已经成功获取锁。客户端 1 并不会不停地循环去尝试加锁，而是在前一个节点比如/locks/lock0上注册一个事件监听器。这个监听器的作用是当前一个节点释放锁之后通知客户端 1（避免无效自旋），这样客户端 1 就加锁成功了。

释放锁：

  1. 成功获取锁的客户端在执行完业务流程之后，会将对应的子节点删除。
  2. 成功获取锁的客户端在出现故障之后，对应的子节点由于是临时顺序节点，也会被自动删除，避免了锁无法被释放。
  3. 我们前面说的事件监听器其实监听的就是这个子节点删除事件，子节点删除就意味着锁被释放。
img

问：为啥要使用临时节点来实现分布式锁？

这样的话，就算获得锁的节点宕机了，临时节点也会自动删除，避免死锁。

问：如何实现可重入锁？

线程获得锁的时候，会创建临时顺序节点，将该线程与该临时节点绑定，每当要获得锁的时候，就判断当前线程是否和锁绑定的线程相等，若相等就对锁计数器+1，否则就创建个新的节点在后边等待。

基于 ETCD 实现分布式锁

主要机制
  • Lease 机制：即租约机制（TTL，Time To Live），Etcd 可以为存储的 Key-Value 对设置租约，当租约到期，Key-Value 将失效删除；同时也支持续约，通过客户端可以在租约到期之前续约，以避免 Key-Value 对过期失效。
    • Lease 机制可以保证分布式锁的安全性，为锁对应的 Key 配置租约，即使锁的持有者因故障而不能主动释放锁，锁也会因租约到期而自动释放。
  • Revision 机制：每个 Key 带有一个 Revision 号，每进行一次事务便加一，因此它是全局唯一的，如初始值为 0，进行一次 put(key, value)，Key 的 Revision 变为 1，同样的操作，再进行一次，Revision 变为 2；换成 key1 进行 put(key1, value) 操作，Revision 将变为 3。
    • 这种机制有一个作用：通过 Revision 的大小就可以知道写操作的顺序。在实现分布式锁时，多个客户端同时抢锁，根据 Revision 号大小依次获得锁，可以避免 “羊群效应” （也称“惊群效应”），实现公平锁。
  • Prefix 机制：即前缀机制，也称目录机制。
    • 例如，一个名为 /mylock 的锁，两个争抢它的客户端进行写操作，实际写入的 Key 分别为：key1="/mylock/UUID1",key2="/mylock/UUID2"，其中，UUID 表示全局唯一的 ID，确保两个 Key 的唯一性。很显然，写操作都会成功，但返回的 Revision 不一样，那么，如何判断谁获得了锁呢？通过前缀“/mylock” 查询，返回包含两个 Key-Value 对的 Key-Value 列表，同时也包含它们的 Revision，通过 Revision 大小，客户端可以判断自己是否获得锁，如果抢锁失败，则等待锁释放（对应的 Key 被删除或者租约过期），然后再判断自己是否可以获得锁。
  • Watch 机制：即监听机制，Watch 机制支持监听某个固定的 Key，也支持监听一个范围（前缀机制），当被监听的 Key 或范围发生变化，客户端将收到通知。
    • 在实现分布式锁时，如果抢锁失败，可通过 Prefix 机制返回的 Key-Value 列表获得 Revision 比自己小且相差最小的 Key（称为 Pre-Key），对 Pre-Key 进行监听，因为只有它释放锁，自己才能获得锁，如果监听到 Pre-Key 的 DELETE 事件，则说明 Pre-Key 已经释放，自己已经持有锁。
实现流程

假设对某个共享资源设置的锁名为：/lock/mylock

image-20230503221359359

步骤1：准备

客户端连接 Etcd，以 /lock/mylock 为前缀创建全局唯一的 Key，假设第一个客户端对应的 Key="/lock/mylock/UUID1"，第二个为 Key="/lock/mylock/UUID2"；客户端分别为自己的 Key 创建租约 Lease，租约的长度根据业务耗时确定，假设为 15s。

步骤2：创建定时任务作为租约的“心跳”

在一个客户端持有锁期间，其它客户端只能等待，为了避免等待期间租约失效，客户端需创建一个定时任务作为“心跳”进行续约。此外；如果持有锁期间客户端崩溃，心跳停止，Key 将因租约到期而被删除，从而锁释放，避免死锁。

步骤3：客户端将自己全局唯一的 Key 写入 Etcd

进行 Put 操作，将步骤 1 中创建的 Key 绑定租约写入 Etcd，根据 Etcd 的 Revision 机制，假设两个客户端 Put 操作返回的 Revision 分别为1、2，客户端需记录 Revision 用以接下来判断自己是否获得锁。

步骤4：客户端判断是否获得锁

客户端以前缀 /lock/mylock 读取 Key-Value 列表（Key-Value 中带有 Key 对应的 Revision），判断自己 Key 的 Revision 是否为当前列表中最小的，如果是则认为获得锁；否则监听列表中前一个 Revision 比自己小的 Key 的删除事件，一旦监听到删除事件或者因租约失效而删除的事件，则自己获得锁。

步骤5：执行业务

获得锁后，操作共享资源，执行业务代码。

步骤6：释放锁

完成业务流程后，删除对应的 Key 释放锁。

参考文章：

七、分布式事务

分布式事务指事务的参与者、支持事务的服务器、资源服务器、事务管理器分别位于不同的分布式系统的不同节点上，分布式事务要保证这些操作要么全部成功要么全部失败。**本质上：**就是为了保证不同数据库的一致性。

八、Zookeeper

Zookeeper 基础理论

问：Zookeeper 是什么？

Zookeeper 是一个分布式一致性解决方案集，保证了 CP，可用来实现诸如数据发布/订阅、负载均衡、命名服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能。

ZooKeeper 将数据保存在内存中。

问：Zookeeper 具有哪些特性？⭐

  • 顺序一致性⭐：从一个客户端发起的事务请求，最终都会严格按照其发起顺序被应用到 ZooKeeper 中。实现原理：原子广播。
  • **原子性⭐：**所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的，即整个集群要么都成功应用了某个事务，要么都没有应用。实现原理：事务。
  • 单一视图⭐：无论客户端连接的是哪个 Zookeeper 服务器，其看到的服务端数据模型都是一致的。
  • **高可用⭐：**基于副本机制实现，此外 ZooKeeper 支持故障恢复。实现原理：选举 Leader。
  • **高性能：**ZooKeeper 将数据全量存储在内存中，所以其性能很高。

问：Zookeeper 有哪些数据类型？⭐

zookeeper 数据模型采用树形结构，使用了 znode 作为数据节点。

znode 是 zookeeper 中的最小数据单元，每个 znode 上都可以保存数据，同时还可以挂载子节点，形成一个树形化命名空间。

  • 持久节点：一旦创建就一直存在(即使 ZooKeeper 集群宕机)，直到主动将其删除；
  • **临时节点：**临 客户端会话（session）结束则节点消失 。并且，临时节点只能做叶子节点，不能创建子节点；
  • 持久顺序节点：除了具有持久节点的特性外，节点ID还具有顺序性，如/node1/app0000000001、/node1/app0000000002
  • **临时顺序节点：**除了具有临时节点特性外，节点ID还具有顺序性。
zk数据模型

每个 znode 由 2 部分组成:

  • stat：状态信息；
  • data：节点存放的数据的具体内容。

问：Zookeeper 集群中有哪些角色？⭐

共有 Leader、Follower 和 Observer 三种角色：

  • Leader：
    • 负责发起并维护与各 Follower 及 Observer 间的心跳；
    • 所有的写操作必须要通过 Leader 完成再由 Leader 将写操作广播给其它服务器；
    • 一个 Zookeeper 集群同一时间只会有一个实际工作的 Leader。
  • Follower：
    • 响应 Leader 的心跳；
    • Follower 可直接处理并返回客户端的读请求，同时会将写请求转发给 Leader 处理，并且负责在 Leader 处理写请求时对请求进行投票；
    • 一个 Zookeeper 集群可能同时存在多个 Follower。
  • Observer：角色与 Follower 类似，但是无投票权。

Zookeeper 工作原理

读操作

Leader/Follower/Observer 都可直接处理读请求，从本地内存中读取数据并返回给客户端即可。

由于处理读请求不需要服务器之间的交互，Follower/Observer 越多，整体系统的读请求吞吐量越大，也即读性能越好。

写操作

所有的写请求实际上都要交给 Leader 处理。Leader 将写请求以事务形式发给所有 Follower 并等待 ACK，一旦收到半数以上 Follower 的 ACK，即认为写操作成功。Follower/Observer 均可接受写请求，但不能直接处理，而需要将写请求转发给 Leader 处理。

问：Watcher(事件监听器) 有啥用？⭐

客户端注册监听它关心的 znode，当 znode 状态发生变化(数据变化、子节点增减变化)时，ZooKeeper 服务会推送给客户端。

Watcher 可以实现分布式锁、发布订阅等功能。

问：会话机制？(Zookeeper 是咋推送给客户端的呢？)

客户端通过TCP 长连接与 ZooKeeper 服务集群建立会话(Session)，之后通过心跳检测机制来保持有效的会话状态。通过这个连接，客户端可以发送请求并接收响应，同时也可以接收到 Watch 事件的通知。

每个会话都会有一个超时时间，客户端通过心跳方式(ping)来保持会话不过期，若服务器在超时时间内没有收到任何请求或心跳，则相应会话被视为过期。

ZAB 协议

ZAB 协议主要定义了两个可以无限循环的流程：

  • 崩溃恢复：用于故障恢复。当主节点出现故障时，选举 Leader，从而保证高可用。
  • 原子广播：用于主从同步，从而保证数据一致性。

在 ZAB 中很重要的字段：

  • **zxid：**是一个 64 位长度的 Long 类型。其中高 32 位表示 epoch，低 32 表示 xid；

$$ zxid = (epoch, xid) $$

  • epoch：每个 Leader 都会具有一个不同的 epoch，用于区分不同的时期（可以理解为朝代的年号）；

  • xid：事务 id，是一个流水号。每次朝代更替，即 leader 更换时，会重新从 0 开始递增；

每当选举产生一个新的 Leader ，就会从这个 Leader 服务器上取出本地事务日志中最大编号 Proposal 的 zxid，并从 zxid 中解析得到对应的 epoch 编号，然后再对其加 1，之后该编号就作为新的 epoch 值，并将低 32 位数字归零，由 0 开始重新生成 zxid。

  • **myid：**节点id。

问：Zookeeper 如何实现高可用？崩溃恢复/选举过程是啥样的？⭐⭐

Zookeeper 通过副本机制，副本机制通过原子广播实现，当 Leader 出现故障时，会进行崩溃恢复来保证高可用。

关键点：保证选举出的新 Leader 拥有集群中所有节点中最大编号(zxid)的事务！！

崩溃恢复的过程大致是这样的：

  1. **自增选举轮次：**每个服务器在开始新一轮投票时，会先对自己维护的 logicClock 进行自增操作；

  2. 初始投票：每个服务器最开始都通过广播把票投给自己，投票内容为所投票服务器的 myid 和 zxid；

  3. 接收外部投票：每个服务器都会接收其它服务器的投票，并记入自己的投票箱内；

  4. **判断选举轮次：**收到外部投票后，首先会根据投票信息中的 logicClock 进行判断：

    • 若外部投票的 logicClock 大于自己的，说明自己落后，会立即清空并更新自己的投票箱；
    • 若外部投票的 logicClock 小于自己的，直接忽略该选票；
    • 若等于，就将该选票存入投票箱，之后进行投票 PK；

  5. **投票 PK：**每个节点都只有一票，这步就是确定最终投给谁。**优先选择 zxid 大的，然后选择 myid 大的。**然后将最终投票广播出去；

  6. **统计选票：**若某个 Server 的投票数大于半数以上，则该 Server 就成为了 Leader；

  7. **同步状态：**利用 leader 前一阶段获得的最新提议，同步集群中所有的副本。同步完成之后，就可以对外提供服务了。

问：Zookeeper 如何实现分布式数据一致性？⭐⭐

Zookeeper 主要依赖 ZAB 协议来实现分布式数据一致性，ZAB协议是顺序一致性的。主要是通过原子广播来保证。

详细过程：

ZooKeeper 中所有的写请求都由 Leader 节点来处理：

  1. 客户端的写请求进来之后，Leader 会将写请求包装成 Proposal 事务，并添加一个递增事务 ID，也就是 Zxid。Zxid 是单调递增的，以保证每个消息的先后顺序；
  2. 广播这个 Proposal 事务。Leader 会为每一个 Follower 服务器分配一个单独的 FIFO 队列，然后把 Proposal 放到队列中；
  3. Follower 节点收到对应的 Proposal 之后会把它持久到磁盘上，当完全写入之后，发一个 ACK 给 Leader；
  4. 当 Leader 收到超过半数 Follower 的 ACK 之后，会提交本地机器上的事务，同时开始广播 commit；
  5. Follower 收到 commit 之后，完成各自的事务提交。

问：Zookeeper 如何保证事务(Proposal)发送的顺序性？⭐⭐

如果Follower收到事务的顺序不同，那么会造成数据不一致的。

主要是靠**Zxid和队列**：

  • Leader会为每个事务分配一个全局递增的事务ID(Zxid)，生成事务后，按照该 ID 进行排序，以保证顺序；

  • Leader会为每一个Follower分配一个单独的队列，然后将事务 Proposal 依次放入队列中，并根据 FIFO(先进先出) 的策略进行消息发送。

问：为啥集群中的机器最好是奇数台？

Zookeeper集群中，存活主机数目 > 宕机数目 时，才能继续提供服务。

也就是说，2n 和 2n-1 的容忍度是一样的，都是 n-1。既然多出一台也一样，那何必呢？

问：Zookeeper 集群如何防止脑裂现象？⭐

==采用过半机制。==在收到大于一半的选票才能成为 Leader。

ZooKeeper 的过半机制导致不可能产生 2 个 leader，因为少于等于一半是不可能产生 leader 的，这就使得不论机房的机器如何分配都不可能发生脑裂。

Zookeeper 应用

参考链接

因为Zookeeper的强一致性，可以保证在高并发情况下创建全局唯一的节点。

分布式ID

在分布式系统中，通常需要一个全局唯一的名字，如生成全局唯一的订单号等，ZooKeeper 可以通过顺序节点的特性来生成全局唯一 ID，从而可以对分布式系统提供命名服务。

img
分布式锁⭐

示例过程：

可以让多个客户端在指定节点(通常是持久节点)下创建临时顺序节点，判断自己创建的是否是有序节点中序号最小的那个，若是就获得锁；若不是，就通过Watcher进行监听，若自己前边的序号都失效了，就说明锁释放了，就可以通过回调函数得到该锁。

https://chuyu-typora.oss-cn-hangzhou.aliyuncs.com/image/e0edfab2ec426b3ea45765d931b10a8b.png

改进：

比如当一个锁得到释放它会通知所有等待的客户端从而造成 羊群效应 ，此时可以通过让等待的节点只监听他们前面的节点。

集群管理和注册中心⭐

对于集群管理，如果我们想知道有多少机器在工作，可以为每个机器创建一个临时节点，并监控其父节点，当父节点的状态改变，就能知道机器变动状态。

集群管理

对于注册中心，可以：

  • 让服务提供者在Zookeeper中创建一个临时节点，并将自己的ip、port、调用方式 写入节点；

  • 当服务消费者需要进行调用的时候会 通过注册中心找到相应服务的地址列表(IP端口什么的)。之后可以缓存到本地(方便以后调用)，当消费者再次调用服务时，不会再去请求注册中心，而是直接通过负载均衡算法从地址列表中取一个服务提供者的服务器调用服务。

当服务提供者的某台服务器宕机或下线时，相应的地址会从服务提供者地址列表中移除。同时，注册中心会将新的服务地址列表发送给服务消费者的机器并缓存在消费者本机（当然你可以让消费者进行节点监听，我记得 Eureka 会先试错，然后再更新）。

注册中心
选主

示例过程：

可以让多个客户端同时创建一个指定的临时顺序节点，成为主节点。若该主节点挂了，就相当于会话结束，可以通过**Watcher来监听这个节点的状态**，发现挂了就触发回调函数重新选举。

选主

九、Etcd

主要参考：

Etcd 是一个基于 Raft 共识算法实现的分布式键值存储服务，是 K8s 的核心存储。在项目结构上采用了模块化设计，其中最主要的三个部分是实现分布式共识的 Raft 模块、实现数据持久化的 WAL 模块和实现状态机存储的 MVCC 模块。

/posts/database/etcd/etcd-Architecture@2x.png

更详细的架构图如下：

  • api 接口支持 http 协议和 grpc 协议；
  • node 主要负责 raft 算法的实现；
  • storage 主要负责 raft 日志以及 snap 快照文件的存储；
  • transport 主要负责集群节点间的通信；
  • kvstore 分为 v2 和 v3 两个版本数据库，主要负责业务数据的存储，其中 v3 版本数据库的实现采用 lboltdb 和 keyIndex，支持 mvcc 机制。
image-20230404151032958

RAFT 模块

==日志复制==

在分布式环境中，如果我们要让一个服务具有容错能力，最常用的方法就是让一个服务的多个副本同时运行在多个节点上。为了保证多个副本在运行时的状态都是同步的，即客户端无论将请求发送到哪一个节点中，最后都能得到相同的结果，通常采用状态机复制（State Machine Replication）方法。

Etcd使用日志复制实现。Etcd 将日志实例化为 Entry 日志，每个节点会存储一系列 Entry 日志，每个节点的 Entry 日志都相同并且顺序也一致，状态机按顺序执行 Entry 中的命令，因此每个状态机处理相同的命令序列，这样就能得到相同的数据状态和输出序列。

RAFT 就是用来保证复制日志的一致性。服务器节点上的Consensus模块接收来自客户端的写请求，将它们添加到 WAL (Write Ahead Log，预写日志）中。随后该服务器与其他服务器上的Consensus模块通信，以确保每个服务器上具有相同的日志序列。每个服务器上的状态机按顺序执行命令，并将执行结果返回给客户端，这样就形成了高可用的复制状态机。

/posts/database/etcd/State-Machine-Replication@2x.png
数据通道

为了网络层能够高效地处理不同数据量的消息，etcd 采取分类处理的方式，它抽象出 2 种类型的消息传输通道：

  • **Stream 通道：**用于处理数据量较少、发送比较频繁的消息，例如心跳消息、追加日志消息等，节点与节点之间只维护 1 个 HTTP 长连接，交替向连接中写入数据；
  • **Pipeline 通道：**用于处理数据量大的消息，比如传输快照消息。这种类型的消息需要与心跳消息等分开处理，否则会阻塞心跳包的传输，进而影响集群的稳定性。Pipeline 通道只通过短连接传输数据，用完即关闭。

这两种消息传输通道都使用 gRPC 传输数据。

/posts/database/etcd/etcd-Data-Channel@2x.png
==Leader 选举==

Raft 通过『leader 选举机制』选举出一个 Leader，由它全权管理日志复制来实现一致性。

Raft 算法论文规定了三种节点身份：Leader、Follower 和 Candidate，Etcd 的实现中又添加了 PreCandidate 和 Learner 这两种身份。

/posts/database/etcd/Node-State-Change@2x.png

  • 集群启动时所有节点初始状态均为 Follower，随后会有一个节点选举成功成为 Leader，在绝大多数时间里集群内的节点会处于这两种身份之一；

  • 当一个 Follower 节点的选举计时器超时后，会切换为 PreCandidate 身份，进行**preVote**，不自增任期号仅发起预投票，也就是询问集群中其他节点是否愿意参与选举：

    • 如果集群中的其它节点能够正常收到 Leader 的心跳消息，那么会拒绝参与选举；
    • 如果有超过法定人数的节点响应并表示参与新一轮选举，该节点会从 PreCandidate 身份切换到 Candidate，自增任期号并投票给自己，并向其他节点广播竞选投票信息；

  • 当节点收到其他节点的竞选消息后，首先判断竞选节点的任期号大于本节点，则可以投票给竞选节点，否则拒绝投票。

  • 当一个节点成为 Leader 后会立即提交一条空日志，将自身携带的所有日志都设置为提交状态，包括由其它 Leader 创建但还没有提交的日志条目，然后向集群内的其它节点同步。这样就可以保证集群数据的一致性，防止 Leader 节点切换过程中发生数据丢失。

  • 当一个新节点刚进入集群，此时就是 Learner 身份，主要是因为需要花费很长时间来同步日志，这可能导致集群无法处理新的请求，为了避免这种间隔，所以 Learner 不具有投票权，接收 Leader 发来的快照以快速赶上日志，当和Leader日志一致后会转变身份为 Follower。

Entry

Raft 模块维护的**所有数据（键值对）**都被实例化为 Entry 日志表示。

Raft 算法中所有写请求都是由 Leader 节点处理的，如果收到提案的节点是 Follower，它会转发给 Leader。

Leader 收到提案后，需要对客户端发送的数据封装为 Entry 日志：

  • Data字段是客户端发送的键值对；
  • Term字段是当前集群的任期；
  • Index字段是该 Entry 日志的索引，相当于全局唯一标识 ID。

封装完数据后会将这些 Entry 日志追加到 Raft Log 中。

写请求流程
  1. client 通过负载均衡算法选择一个 Etcd 节点，发起 gRPC 调用，发送 K-V 请求；
  2. 经过检验之后，传递提案给上层，RAFT 模块收到提案后，若当前节点是 Follower，就会转发给 Leader，只有 Leader 才能处理写请求；
  3. Leader 收到提案后，通过 RAFT 模块生成 Entry，并保存到 unstable中；
  4. Leader 获得 Entry 后，会将其写入 WAL 文件，同时将其广播给集群中的其他节点；
  5. 然后 Leader 的 RAFT 模块会把该 Entry 移到 MemoryStorage；
  6. 待该 Entry 日志被复制到集群半数以上的节点时，该 Entry 日志会被 Leader 节点确认为己提交，Leader 会回复客户端写请求操作成功；
  7. 然后 Leader 将该 Entry 应用到状态机。
/posts/database/etcd/etcd-Write-Request@2x.png
线性一致读

ETCD 中，所有的写请求都只由Leader处理，再通过日志复制的方法同步给其他Follower。

但所有的节点(Leader+Follower)都可以处理读请求。由于以下原因，从不同的节点读数据可能会出现不一致:

  • Etcd 应用日志的过程是异步的，Follower的状态总的落后于Leader，且Follower之间的状态也可能存在差异；
  • 若出现网络分区，进而出现脑裂，新旧Leader的状态也会不一致。

也就是说，各个节点并非是 实时 一致，所以读取数据很有可能读取到不一致的旧数据。

问：怎么解决线性一致读问题？⭐

Etcd 采用 ReadIndex 机制实现线性一致读，基本原理：

  • Leader首先通过某种机制确认自己依然是Leader；
  • Leader需要给客户端返回最近已应用的数据：即最新被应用到状态机的数据。

流程如下：

  • 当 Follower 节点收到一个线性读请求时，它首先会向 Leader 请求获取集群最新的、已提交的日志索引，记为ReadIndex；
  • Leader 收到 ReadIndex 请求时，会向 Follower 发送心跳消息，如果超过法定人数的节点响应了心跳消息，就说明自己是合法的 Leader，然后才能将读时已提交的索引返回给请求节点；
  • Follower 拿到后，等待状态机『至少』应用到ReadIndex，即 AppliedIndex >= ReadIndex，然后执行读请求，将结果返回给 Client。

日志存储

RAFT 共有两类数据需要持久化存储：

  • **RAFT 日志：**已提交的日志是不能丢失的；
  • 节点的状态：包括当前的任期 term、当前的投票目标 vote、已提交的最后一条日志索引。前两个字段是 leader 选举流程中的承诺，第三个字段是节点在重启恢复时用来控制日志回放到哪一条日志。
WAL

问：什么是 WAL ？

ETCD 使用 WAL(Write Ahead Log，预写日志) 保存上面两种数据。

  • 所有数据在提交之前都要先写入 WAL 中；

  • 然后定期对数据进行快照备份，快照文件存储了某一时刻 ETCD 的所有数据，数据已经存储在快照中的 WAL 文件就可以删除。

问：WAL 如何工作？

WAL 的工作过程非常像区块链：

  • 首个 WAL 文件的文件开头 crc32 初始值为 0，之后每个记录(raft 日志或者节点状态)的 crc32值 = calc(pre_crc32, 本记录的二进制值)；
  • 对于第二个及以后的 WAL 文件，文件开头的初始 crc32 值 = 上一个 wal 文件最后一条记录的 crc32 值。

这样的话，所有 WAL 文件，其所有记录的 crc32 值可以形成一个可进行强校验的链表。这样在重启恢复的时候，ETCD 就可以对 WAL 文件的内容进行精细化的校验。

image-20230404153256659
日志压缩

WAL 是一种 Append Only 的日志文件，只会在文件结尾不断地添加新日志。当数据量越来越大，WAL 文件就会越来越大，会占用大量空间，并且，通过这么大的 WAL 文件进行数据恢复时，也会耗费很长时间。因此，同 Redis 一样，会定期创建快照，将整个节点的状态进行序列化，然后写入稳定的快照文件中，在该快照文件之前的日志记录就可以全部丢弃掉。

在 RATF 日志中，首先定义几个概念：

  1. **log_index：**最新的日志位置索引。
  2. **commit_index：**已达成多数派一致，可提交的最大日志位置索引。
  3. apply_index：已应用到业务状态机的最大日志位置索引。
  4. **compact_index：**RAFT 日志清理的临界位置索引，在该索引之前的所有 RAFT 日志，都可以清掉。
  5. **last_snap_index：**上一个 snap 快照文件的日志索引，代表 snap 快照文件生成时刻的 apply_index。
image-20230404154816559

共分为两种快照：

  • 数据快照：用来日志压缩。当 apply_index - last_snap_index > Cfg.SnapshotCount(默认值为 10w)时，会触发 snap 快照文件的生成，即判断 已应用日志的索引与上次快照保存的最后一条日志的索引值之间的差距 是否大于设定值，若超过了，就快照一下；此时 apply_index 之前的所有 raft 日志都可以清掉了；
  • RPC快照：用来快速恢复。Leader 会为每一个 Follower 维护一个 Next值，表示该 Follower 节点下一个待复制的 Entry 记录的索引值。为了让落后的节点尽快地追赶上集群，Leader 会将从Next开始的日志打包成快照，发送给 Follower。
日志读写性能的优化

问：ECTD 怎么提高日志存储效率？

每一个写请求都会生成一条 RAFT 日志，而 RAFT 日志是需要刷盘的。如果每生成一条 RAFT 日志就刷盘一次，那 ETCD 的写入性能必然很低，因此 ETCD 采用异步批量刷盘的方式来优化写入性能，如下图所示。

  1. 外部的写请求先由 go routine 1 写入到 propc 通道；
  2. go routine 2 消费 propc 通道中的请求，将其转化为 unstable_log (保存在内存中，表示尚未达成多数一致的 RAFT 日志)，也会在待发送消息的缓冲区中生成日志复制请求；
  3. go routine 3 会将 unstable_log、待发送的日志复制请求打包成一个 ready 结构，写入道 readyc 通道；
  4. go routine 4 消费 readyc 中的数据，将 RAFT 日志刷盘到 WAL 文件以及追加到 stable_log (保存在内存中，可理解为 WAL 文件中的 RAFT 日志在内存中的副本)，同时将日志复制请求发送给 Follower 节点；
  5. 对于已达成多数一致的那些日志，unstable_log 缓冲区就可以清理掉了。
image-20230404155824344

好处就是：

  • 将多次写请求合并为一次刷盘优化了写入性能；

  • 而且通过在 stable_log 内存缓冲区中额外维护一份 WAL 文件中日志的副本，从而优化了 RAFT 日志的读取性能。

MVCC 机制

问：了解 MVCC 吗？什么是 MVCC 机制？

多版本并发控制（Multi-Version Concurrency Control , MVCC）是一种无锁事务机制，能最大化地实现高效地读写并发，尤其是高效地读，非常适合读多写少的场景。

MVCC 的每一个写操作都会创建一个新版本的数据，读操作会从有限多个版本的数据中挑选一个最合适(要么是最新版本，要么是指定版本)的结果直接返回。通过这种方式，我们就不需要关注读写操作之间的数据冲突。

因此，如何管理和高效地选取数据的版本就成了 MVCC 需要解决的主要问题。

/posts/database/etcd/MVCC-Read@2x.png

问：ETCD 如何存储数据以支持 MVCC 机制？

ETCD 使用 B-Tree 维护 key 与 reversion 之间的映射关系。B-Tree 的键存储了原始的 key，值存储了一个 keyIndex 实例。

image-20230404161616775

问：ETCD 如何维护 key 的版本号数据？

一个 keyIndex 实例维护了该 key 全部的历史版本信息。

keyIndex 用代generation表示同一个 Key 在某一个生命周期内的数据变化情况：

  • 每代中可以存储**多个修订版本(version)**的信息；
  • 当遇到删除操作时，会加入墓碑，并创建一个新的 generation。
/posts/database/etcd/KeyIndex-Format@2x.png

这样设计的好处就是：

  • 存储的时候不用区分修改的版本号与删除的版本号。在判断 key 是否存在时，我们只需要判断 keyIndex 是否存在或者其最后一代 generation 是否为空；
  • 在查找 key 的指定版本号数据时，可以先查找 generation，然后再在 generation 中查找具体的 version，相当于将一个大数组的查找划分为两个小数组的查找，加快了查找速度。==不是很理解这个说法==
image-20230405174016265

问：如何利用该结构，查找到给定 key 的某个历史版本信息？

客户端在查找指定键值对时，会先通过内存中维护的 B 树查找到对应的 keyIndex 实例，然后通过 keyIndex 查找到对应的 revision 信息，最后通过 revision 从 BoltDB 中查找真正的键值对数据。

问：ETCD 如何存储每个版本号的数据？

etcd 底层默认采用 boltdb 来存储每个版本号对应的 value，boltdb 是采用 B+ 树来存储数据的，每个 key-value 键值对必须存储在 bucket 桶中，每一个 bucket 桶的数据都由一个独立的 B+ 树来维护。

==// TODO: 没理解清楚，先这样吧。。。==

image-20230405195714649

Watch 机制

ETCD 允许客户端监听某个 key 或者某段 key 范围区间的变化。如果监听范围内的某个 key，其数据发生变化，则 watch 的客户端会立刻收到通知。

客户端发出 watch 请求后，服务端首先创建一个 serverWatchStream，该 serverWatchStream 包含一个 recv loop 协程和 send loop 协程：

  • recv loop 协程：负责监听客户端对具体 key 的 watch 请求，一旦收到 watch 请求就创建一个 watcher；
  • send loop 协程：负责将相关事件发送给客户端。
image-20230405201633881

Lease 租约

可以简单理解为 key 的有效期。

问：Key 如何关联一个 Lease?

大致分为两步：

  • 1）创建 Lease
  • 2）将 key 与 lease 关联
续期

在正常情况下，节点存活时，需要定期发送 KeepAlive 请求给 etcd 续期健康状态的 Lease，否则你的 Lease 和关联的数据就会被删除。

问：如何高效的淘汰过期的 Lease？

Etcd 基于最小堆来管理 Lease，会定时轮询堆顶的元素，若已过期则加入到待淘汰列表，直到堆顶的 Lease 过期时间大于当前，则结束本轮轮询。然后执行删除 Lease 和其关联的 key 列表数据的任务。

问：怎么通知其他 Follower 淘汰它们呢？

  • Lessor 模块会将已确认过期的 LeaseID，保存在一个 channel 中，Etcd 会定期从 channel 中获取 LeaseID 并传递给 Follower 节点。

  • 各个节点收到请求后，获取关联到此 Lease 上的 key 列表，执行删除操作即可。

应用场景

服务注册与发现

服务启动后向注册中心(Etcd)登记自己的IP与端口信息，服务的消费方通过查看登记信息，可以直接找到对应的服务，并发起请求。并且可以通过设置Lease，定时发送keepLive来达到健康监控的效果。

消息发布与订阅

配置一个消息共享中心，生产者在这个中心发布消息，而消费者则订阅他们关心的主题，一旦有关主题有消息发布，就会实时通知订阅者。比如：

  • 应用中用到的一些配置信息存放在etcd上进行集中管理。这类场景的使用方式通常是这样的：应用在启动的时候主动从etcd获取一次配置信息，同时，在etcd节点上注册一个Watcher并等待，以后每次配置有更新的时候，etcd都会实时通知订阅者，以此达到获取最新配置信息的目的。
  • **分布式日志收集系统。**核心工作是收集分布在不同机器上的日志。收集器通常按照应用（或主题）来分配收集任务单元，因此可以在etcd上创建一个以应用（或主题）命名的目录P，并将这个应用（或主题）相关的所有机器ip，以子目录的形式存储在目录P下。
负载均衡

利用etcd维护一个负载均衡节点表。etcd可以监控一个集群中多个节点的状态，当有一个请求发过来后，可以轮询式地把请求转发给存活着的多个节点。

分布式锁

Etcd提供**分布式锁原子操作CAS（ComparaAndSwap）**的API，可以保证在多个节点同时创建某个目录时，只有一个成功，操作成功即可认为是获得了锁。

分布式队列

所有试图获得锁的进程都会进入等待队列，获得锁的顺序全局唯一，进而保证了队列的执行顺序。

==关键总结==

问：为什么 etcd v3 版本的 KeyIndex 使用 B-tree 而不使用哈希表、平衡二叉树？

答：从功能特性上分析， 因 etcd 需要支持范围查询，因此保存索引的数据结构也必须支持范围查询才行。所以哈希表不适合，而 B-tree 支持范围查询。从性能上分析，平横二叉树每个节点只能容纳一个数据、导致树的高度较高，而 B-tree 每个节点可以容纳多个数据，树的高度更低，更扁平，涉及的查找次数更少，具有优越的增、删、改、查性能。

问：etcd v3 版本数据是采用 boltdb 存储的，boltdb 对于每一个写事务都会进行一次刷盘，那 etcd 为了优化写入性能，做了什么样的处理？

答：采用批量提交的，也就是用底层 boltdb 的单个写事务来处理上层业务 api 接口的多次写入请求。

问：采用批量提交，在尚未达到提交条件而系统宕机，会不会导致 v3 版本的部分数据丢失呢？

答：不会，因为宕机后重启恢复的时候，可以通过回放 raft 日志来恢复数据，而 v3 版本的存储数据是支持 raft 日志可重入回放的，在将 raft 日志应用到 v3 版本数据的时候，会更新 consistentIndex，而这个 consistentIndex 在批量提交的时候也会 commit 到 boltdb 中。在系统宕机时，consistentIndex 的值也没有刷盘，boltdb 底层保存的还是旧的 consistentIndex，这样宕机后就可以通过重启后的日志回放来恢复数据。

问：ETCD 如何实现线性一致读？⭐

问：Zookeeper 和 ETCD 有哪些不同？

  • zookeeper 使用 ZAB 协议，保证顺序一致性；etcd 使用 Raft 协议，保证线性一致性。顺序一致性是可能返回旧数据的。

  • zookeeper从逻辑上来看是一种目录结构，而etcd从逻辑上来看就是一个k-v结构。

  • 在实现服务发现时，我们一般都会用到zookeeper的临时节点。当客户端掉线一段时间，对应的zookeeper session会过期，那么对应的临时节点就会被自动删除；在etcd中对应的是lease租约机制，通过该机制实现了key的自动删除。

  • zookeeper 官方只提供了java和C两种语言的接口；etcd 使用HTTP作为接口，适用性更广泛。

Updated on 2023-04-23
Read Markdown
 计算机基础
Back | Home