深入剖析共识性算法 Raft

发表于 2020-02-01 分类于分布式

深入剖析共识性算法 Raft

📦 本文已归档到：「blog」

一、Raft 简介
二、Raft 基础
三、选举 Leader
四、日志复制
五、安全性
- 选举限制
- 提交旧任期的日志条目
六、日志压缩
参考资料

一、Raft 简介

Raft _是一种为了管理日志复制的分布式一致性算法*。

Raft 出现之前，Paxos 一直是分布式一致性算法的标准。Paxos 难以理解，更难以实现。Raft 的设计目标是简化 Paxos，使得算法既容易理解，也容易实现。

Paxos 和 Raft 都是分布式一致性算法，这个过程如同投票选举领袖（Leader），参选者（Candidate）需要说服大多数投票者（Follower）投票给他，一旦选举出领袖，就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。

Raft 可以解决分布式 CAP 理论中的 CP，即 一致性（C：Consistency） 和 _分区容忍性（P：Partition Tolerance）_，并不能解决 可用性（A：Availability） 的问题。

分布式一致性

分布式一致性 (distributed consensus) 是分布式系统中最基本的问题，用来保证一个分布式系统的可靠性以及容错能力。简单来说，分布式一致性是指多个服务器的保持状态一致。

在分布式系统中，可能出现各种意外（断电、网络拥塞、CPU/内存耗尽等等），使得服务器宕机或无法访问，最终导致无法和其他服务器保持状态一致。为了应对这种情况，就需要有一种一致性协议来进行容错，使得分布式系统中即使有部分服务器宕机或无法访问，整体依然可以对外提供服务。

以容错方式达成一致，自然不能要求所有服务器都达成一致状态，只要超过半数以上的服务器达成一致就可以了。假设有 N 台服务器，大于等于 $\frac{N}{2}+1$ 台服务器就算是半数以上了。

复制状态机

复制状态机（Replicated State Machines） 是指一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。

复制状态机通常都是基于复制日志实现的，如上图。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

保证复制日志相同就是一致性算法的工作了。在一台服务器上，一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，尽管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。

实际系统中使用的一致性算法通常含有以下特性：

安全性保证（绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。
通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

RAFT 应用

RAFT 可以做什么？

通过 RAFT 提供的复制状态机，可以解决分布式系统的复制、修复、节点管理等问题。Raft 极大的简化当前分布式系统的设计与实现，让开发者只关注于业务逻辑，将其抽象实现成对应的状态机即可。基于这套框架，可以构建很多分布式应用：

分布式锁服务，比如 Zookeeper
分布式存储系统，比如分布式消息队列、分布式块系统、分布式文件系统、分布式表格系统等
高可靠元信息管理，比如各类 Master 模块的 HA

二、Raft 基础

Raft 将一致性问题分解成了三个子问题：

选举 Leader
日志复制
安全性

在后续章节，会详细讲解这个子问题。现在，先了解一下 Raft 的一些核心概念。

服务器角色

在 Raft 中，任何时刻，每个服务器都处于这三个角色之一：

Leader - 领导者，通常一个系统中是一主（Leader）多从（Follower）。Leader 负责处理所有的客户端请求。
Follower - 跟随者，不会发送任何请求，只是简单的 响应来自 Leader 或者 Candidate 的请求。
Candidate - 参选者，选举新 Leader 时的临时角色。

:bulb: 图示说明：

Follower 只响应来自其他服务器的请求。在一定时限内，如果 Follower 接收不到消息，就会转变成 Candidate，并发起选举。

Candidate 向 Follower 发起投票请求，如果获得集群中半数以上的选票，就会转变为 Leader。

在一个 Term 内，Leader 始终保持不变，直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息，以阻止 Follower 转变为 Candidate。

任期

Raft 把时间分割成任意长度的 *任期（Term），任期用连续的整数标记。每一段任期从一次选举*开始。Raft 保证了在一个给定的任期内，最多只有一个领导者**。

如果选举成功，Leader 会管理整个集群直到任期结束。
如果选举失败，那么这个任期就会因为没有 Leader 而结束。

不同服务器节点观察到的任期转换状态可能不一样：

服务器节点可能观察到多次的任期转换。
服务器节点也可能观察不到任何一次任期转换。

任期在 Raft 算法中充当逻辑时钟的作用，使得服务器节点可以查明一些过期的信息（比如过期的 Leader）。每个服务器节点都会存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。

如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。
如果一个 Candidate 或者 Leader 发现自己的任期号过期了，那么他会立即恢复成跟随者状态。
如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。

RPC

Raft 算法中服务器节点之间的通信使用 ***远程过程调用（RPC）***。

基本的一致性算法只需要两种 RPC：

RequestVote RPC - 请求投票 RPC，由 Candidate 在选举期间发起。
AppendEntries RPC - 附加条目 RPC，由 Leader 发起，用来复制日志和提供一种心跳机制。

三、选举 Leader

选举规则

Raft 使用一种心跳机制来触发 Leader 选举。

Leader 需要周期性的向所有 Follower 发送心跳消息，以此维持自己的权威并阻止新 Leader 的产生。

每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms ~ 300ms，如果在竞选超时时间内没有收到 Leader 的心跳消息，就会认为当前 Term 没有可用的 Leader，并发起选举来选出新的 Leader。开始一次选举过程，Follower 先要增加自己的当前 Term 号，并转换为 Candidate。

Candidate 会并行的向集群中的所有服务器节点发送投票请求（RequestVote RPC），它会保持当前状态直到以下三件事情之一发生：

自己成为 Leader
其他的服务器成为 Leader
没有任何服务器成为 Leader

自己成为 Leader

当一个 Candidate 从整个集群半数以上的服务器节点获得了针对同一个 Term 的选票，那么它就赢得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票，按照先来先服务（FIFO）的原则。_要求半数以上选票的规则确保了最多只会有一个 Candidate 赢得此次选举_。
一旦 Candidate 赢得选举，就立即成为 Leader。然后它会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。

其他的服务器成为 Leader

等待投票期间，Candidate 可能会从其他的服务器接收到声明它是 Leader 的 AppendEntries RPC。

如果这个 Leader 的 Term 号（包含在此次的 RPC 中）不小于 Candidate 当前的 Term，那么 Candidate 会承认 Leader 合法并回到 Follower 状态。
如果此次 RPC 中的 Term 号比自己小，那么 Candidate 就会拒绝这个消息并继续保持 Candidate 状态。

没有任何服务器成为 Leader

如果有多个 Follower 同时成为 Candidate，那么选票可能会被瓜分以至于没有 Candidate 可以赢得半数以上的投票。当这种情况发生的时候，每一个 Candidate 都会竞选超时，然后通过增加当前 Term 号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。

Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，竞选超时时间是一个随机的时间，在一个固定的区间（例如 150-300 毫秒）随机选择，这样可以把选举都分散开。

以至于在大多数情况下，只有一个服务器会超时，然后它赢得选举，成为 Leader，并在其他服务器超时之前发送心跳包。
同样的机制也被用在选票瓜分的情况下：每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。

理解了上面的选举规则后，我们通过动图来加深认识。

单 Candidate 选举

（1）下图表示一个分布式系统的最初阶段，此时只有 Follower，没有 Leader。Follower A 等待一个随机的选举超时时间之后，没收到 Leader 发来的心跳消息。因此，将 Term 由 0 增加为 1，转换为 Candidate，进入选举状态。

（2）此时，A 向所有其他节点发送投票请求。

（3）其它节点会对投票请求进行回复，如果超过半数以上的节点投票了，那么该 Candidate 就会立即变成 Term 为 1 的 Leader。

（4）Leader 会周期性地发送心跳消息给所有 Follower，Follower 接收到心跳包，会重新开始计时。

多 Candidate 选举

（1）如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票。例如下图中 Candidate B 和 Candidate D 都发起 Term 为 4 的选举，且都获得两票，因此需要重新开始投票。

（2）当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。

四、日志复制

日志格式

日志由含日志索引（log index）的日志条目（log entry）组成。每个日志条目包含它被创建时的 Term 号（下图中方框中的数字），和一个复制状态机需要执行的指令。如果一个日志条目被复制到半数以上的服务器上，就被认为可以提交（Commit）了。

日志条目中的 Term 号被用来检查是否出现不一致的情况。
日志条目中的日志索引（一个整数值）用来表明它在日志中的位置。

Raft 日志同步保证如下两点：

如果不同日志中的两个日志条目有着相同的日志索引和 Term，则它们所存储的命令是相同的。
- 这个特性基于这条原则：Leader 最多在一个 Term 内、在指定的一个日志索引上创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。
如果不同日志中的两个日志条目有着相同的日志索引和 Term，则它们之前的所有条目都是完全一样的。
- 这个特性由 AppendEntries RPC 的一个简单的一致性检查所保证。在发送 AppendEntries RPC 时，Leader 会把新日志条目之前的日志条目的日志索引和 Term 号一起发送。如果 Follower 在它的日志中找不到包含相同日志索引和 Term 号的日志条目，它就会拒绝接收新的日志条目。

日志复制流程

Leader 负责处理所有客户端的请求。
Leader 把请求作为日志条目加入到它的日志中，然后并行的向其他服务器发送 AppendEntries RPC 请求，要求 Follower 复制日志条目。
Follower 复制成功后，返回确认消息。
当这个日志条目被半数以上的服务器复制后，Leader 提交这个日志条目到它的复制状态机，并向客户端返回执行结果。

注意：如果 Follower 崩溃或者运行缓慢，再或者网络丢包，Leader 会不断的重复尝试发送 AppendEntries RPC 请求（尽管已经回复了客户端），直到所有的跟随者都最终复制了所有的日志条目。

下面，通过一组动图来加深认识：

（1）来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。

（2）Leader 会把修改复制到所有 Follower。

（3）Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交。

（4）此时 Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。

日志一致性

一般情况下，Leader 和 Followers 的日志保持一致，因此日志条目一致性检查通常不会失败。然而，Leader 崩溃可能会导致日志不一致：旧的 Leader 可能没有完全复制完日志中的所有条目。

Leader 和 Follower 日志不一致的可能

Leader 和 Follower 可能存在多种日志不一致的可能。

:bulb: 图示说明：

上图阐述了 Leader 和 Follower 可能存在多种日志不一致的可能，每一个方框表示一个日志条目，里面的数字表示任期号。

当一个 Leader 成功当选时，Follower 可能出现以下情况（a-f）：

存在未更新日志条目，如（a、b）。

存在未提交日志条目，如（c、d）。

或两种情况都存在，如（e、f）。

_例如，场景 f 可能会这样发生，某服务器在 Term2 的时候是 Leader，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在 Term3 重新被选为 Leader，并且又增加了一些日志条目到自己的日志中；在 Term 2 和 Term 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态_。

Leader 和 Follower 日志一致的保证

Leader 通过强制 Followers 复制它的日志来处理日志的不一致，Followers 上的不一致的日志会被 Leader 的日志覆盖。

Leader 为了使 Followers 的日志同自己的一致，Leader 需要找到 Followers 同它的日志一致的地方，然后覆盖 Followers 在该位置之后的条目。
Leader 会从后往前试，每次日志条目失败后尝试前一个日志条目，直到成功找到每个 Follower 的日志一致位点，然后向后逐条覆盖 Followers 在该位置之后的条目。

五、安全性

前面描述了 Raft 算法是如何选举 Leader 和复制日志的。

Raft 还增加了一些限制来完善 Raft 算法，以保证安全性：保证了任意 Leader 对于给定的 Term，都拥有了之前 Term 的所有被提交的日志条目。

选举限制

拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。

Raft 使用投票的方式来阻止一个 Candidate 赢得选举除非这个 Candidate 包含了所有已经提交的日志条目。 Candidate 为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么他一定持有了所有已经提交的日志条目。

RequestVote RPC 实现了这样的限制：RequestVote RPC 中包含了 Candidate 的日志信息， Follower 会拒绝掉那些日志没有自己新的投票请求。

如何判断哪个日志条目比较新？

Raft 通过比较两份日志中最后一条日志条目的日志索引和 Term 来判断哪个日志比较新。

先判断 Term，哪个数值大即代表哪个日志比较新。
如果 Term 相同，再比较日志索引，哪个数值大即代表哪个日志比较新。

提交旧任期的日志条目

一个当前 Term 的日志条目被复制到了半数以上的服务器上，Leader 就认为它是可以被提交的。如果这个 Leader 在提交日志条目前就下线了，后续的 Leader 可能会覆盖掉这个日志条目。

💡 图示说明：

上图解释了为什么 Leader 无法对旧 Term 的日志条目进行提交。

阶段 (a) ，S1 是 Leader，且 S1 写入日志条目为 (Term 2，日志索引 2），只有 S2 复制了这个日志条目。

阶段 (b)，S1 下线，S5 被选举为 Term3 的 Leader。S5 写入日志条目为 (Term 3，日志索引 2）。

阶段 (c)，S5 下线，S1 重新上线，并被选举为 Term4 的 Leader。此时，Term 2 的那条日志条目已经被复制到了集群中的大多数节点上，但是还没有被提交。

阶段 (d)，S1 再次下线，S5 重新上线，并被重新选举为 Term3 的 Leader。然后 S5 覆盖了日志索引 2 处的日志。

阶段 (e)，如果阶段 (d) 还未发生，即 S1 再次下线之前，S1 把自己主导的日志条目复制到了大多数节点上，那么在后续 Term 里面这些新日志条目就会被提交。这样在同一时刻就同时保证了，之前的所有旧日志条目就会被提交。

Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目。只有 Leader 当前 Term 里的日志条目通过计算副本数目可以被提交；一旦当前 Term 的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。

当 Leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的 Term，这在提交规则上产生了额外的复杂性。在其他的一致性算法中，如果一个新的领导人要重新复制之前的任期里的日志时，它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外，和其他的算法相比，Raft 中的新领导人只需要发送更少日志条目（其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号）。

六、日志压缩

在实际的系统中，不能让日志无限膨胀，否则系统重启时需要花很长的时间进行恢复，从而影响可用性。Raft 采用对整个系统进行快照来解决，快照之前的日志都可以丢弃。

每个副本独立的对自己的系统状态生成快照，并且只能对已经提交的日志条目生成快照。

快照包含以下内容：

日志元数据。最后一条已提交的日志条目的日志索引和 Term。这两个值在快照之后的第一条日志条目的 AppendEntries RPC 的完整性检查的时候会被用上。
系统当前状态。

当 Leader 要发送某个日志条目，落后太多的 Follower 的日志条目会被丢弃，Leader 会将快照发给 Follower。或者新上线一台机器时，也会发送快照给它。

生成快照的频率要适中，频率过高会消耗大量 I/O 带宽；频率过低，一旦需要执行恢复操作，会丢失大量数据，影响可用性。推荐当日志达到某个固定的大小时生成快照。

生成一次快照可能耗时过长，影响正常日志同步。可以通过使用 copy-on-write 技术避免快照过程影响正常日志同步。

说明：本文仅阐述 Raft 算法的核心内容，不包括算法论证、评估等

参考资料

Raft 一致性算法论文原文
Raft 一致性算法论文译文
Raft 作者讲解视频
Raft 作者讲解视频对应的 PPT
分布式系统的 Raft 算法
Raft 算法详解
Raft: Understandable Distributed Consensus - 一个动画教程
sofa-jraft - 蚂蚁金服的 Raft 算法实现库（Java 版）

Markdown Cheat Sheet

发表于 2020-01-27 分类于效率提升，规范

Markdown Cheat Sheet

:package: 本文已归档到：「blog」

标题

Markdown 支持六个级别的标题。

语法：
# 一级标题
## 二级标题
### 三级标题
#### 四级标题
##### 五级标题
###### 六级标题

文本样式

:bulb: 粗体、斜体、删除线可以混合使用。

在 Markdown 中，粗体文本、斜体文本可以使用 * 或 _ 符号标记。建议统一风格，始终只用一种符号。

语法	效果
普通文本	普通文本
`斜体文本` `_斜体文本_`	斜体文本斜体文本
`粗体文本` `__粗体文本__`	粗体文本粗体文本
`~~删除文本~~`	~~删除文本~~
`*粗斜体文本*` `___粗斜体文本___`	粗斜体文本粗斜体文本

列表

无序列表

RED
YELLOW
BLUE

有序列表

第一步
第二步
第三步

任务列表

完成任务
计划任务

多级列表

数据结构
- 线性表
  - 顺序表
  - 链表
    - 单链表
    - 双链表
- 树
  - 二叉树
    - 二叉平衡树

分割线

***、---、___ 都可以作为分割线。

链接

普通链接

语法：

1	[我的博客](https://dunwu.github.io/blog/)

[] 中标记链接名。类似 HTML 中 <a> 元素的 title 属性。
() 中标记链接的 url，也支持相对路径（前提是资源可以访问）。类似 HTML 中 <a> 元素的 href 属性。

效果：

我的博客

图片

Markdown 引用图片的语法：

1	![alt](url title)

alt 和 title 即对应 HTML 中 img 元素的 alt 和 title 属性（都可省略）：

alt - 表示图片显示失败时的替换文本。
title - 表示鼠标悬停在图片时的显示文本（注意这里要加引号）
url - 即图片的 url 地址

图片链接

可以将图片和链接混合使用。

锚点

其实呢，每一个标题都是一个锚点，和 HTML 的锚点（#）类似，比如：回到顶部

引用

普通引用：

:question: 什么是 Markdown

Markdown是一种轻量级标记语言，创始人为约翰·格鲁伯（英语：John Gruber）。它允许人们“使用易读易写的纯文本格式编写文档，然后转换成有效的XHTML（或者HTML）文档”。[4]这种语言吸收了很多在电子邮件中已有的纯文本标记的特性。 —— 摘自 Wiki

嵌套引用：

数据结构

树

二叉树

平衡二叉树

满二叉树

代码高亮

代码块

语法一：在文本前后都使用三个反引号进行标记。【✔️ 推荐】

1
2
3

这是一个文本块。
这是一个文本块。
这是一个文本块。

语法二：在连续几行的文本开头加入 1 个 Tab 或者 4 个空格。【❌ 不推荐】

这是一个文本块。
这是一个文本块。
这是一个文本块。

语法

在三个反引号后面加上编程语言的名字，另起一行开始写代码，最后一行再加上三个反引号。

1	public static void main(String[]args){} //Java

1	int main(int argc, char *argv[]) //C

1	echo "hello GitHub" #Bash

1	document.getElementById('myH1').innerHTML = 'Welcome to my Homepage' //javascipt

1	string &operator+(const string& A,const string& B) //cpp

表格

一般表格：

表头 1	表头 2
表格单元	表格单元
表格单元	表格单元

表格可以指定对齐方式：

序号	商品	价格
1	电脑	6000.0
2	鼠标	100.0
3	键盘	200.0

Emoji 表情

:bulb: 注意：部分 Markdown 引擎支持 Emoji。

合理使用 Emoji 表情，往往可以使得文章内容更加丰富生动。例如：:heavy_check_mark: :x: :bulb: :bell: :heavy_exclamation_mark: :question:

更多 Emoji 表情请参考：

http://emojihomepage.com/

http://www.emoji-cheat-sheet.com

注脚

:bulb: 注意：部分 Markdown 引擎支持注脚。

一个具有注脚的文本。^1

数学公式

:bulb: 注意：部分 Markdown 引擎支持 Latex。

很多文档中，需要引入一些数学符号、特殊符号，其排版问题比较头疼。这种问题，可以用 Latex 来解决，大部分 Markdown 引擎都支持 Latex。

Latex 可以使用 $ 符号来标记 Latex 表达式，下面是一个数学公式示例：

$$
\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt,.
$$

列举一些常用数学符号：

符号	语法	描述
$\leq$	$\leq$	小于等于
$\geq$	$\geq$	大于等于
$\neq$	$\neq$	不等于
$\approx$	$\approx$	约等于
$\infty$	$\infty$	无穷
$\prod_{x}^{y}$	$\prod_{x}^{y}$	累乘
$\sum_{i=0}^n$	$\sum_{i=0}^n$	求和
$\int$	$\int$	积分
$\iint$	$\iint$	双重积分
$\log_x{y}$	$\log_x{y}$	对数
$x^{y+1}$	$x^{y+1}$	上标
$x_{y+1}$	$x_{y+1}$	下标
$\frac{x}{y}$	$\frac{x}{y}$	分数
$\sqrt[y]{x}$	$\sqrt[y]{x}$	开方
$\sin$	$\sin$	正弦
$\cos$	$\cos$	余弦
$\tan$	$\tan$	正切

更多数学符号支持请参考：

Begin-Latex-in-minutes

Markdown 数学符号&公式

Diff

:bulb: 注意：部分 Markdown 引擎支持 Diff。

版本控制的系统中都少不了 diff 的功能，即展示一个文件内容的增加与删除。
GFM 中可以显示的展示 diff 效果。可以用 + 开头表示新增，- 开头表示删除。

1 2	+ 新增内容 - 删除内容

UML 图

💡 注意：部分 Markdown 引擎支持 mermaid。

mermaid 提供了多种 UML 图。详情请参考：mermaid 文档

流程图

graph LR
    A[Hard edge] -->|Link text| B(Round edge)
    B --> C{Decision}
    C -->|One| D[Result one]
    C -->|Two| E[Result two]

时序图

sequenceDiagram
    Alice->>Bob: Hello Bob, how are you?
    alt is sick
        Bob->>Alice: Not so good :(
    else is well
        Bob->>Alice: Feeling fresh like a daisy
    end
    opt Extra response
        Bob->>Alice: Thanks for asking
    end

甘特图

gantt
       dateFormat  YYYY-MM-DD
       title Adding GANTT diagram functionality to mermaid

       section A section
       Completed task            :done,    des1, 2014-01-06,2014-01-08
       Active task               :active,  des2, 2014-01-09, 3d
       Future task               :         des3, after des2, 5d
       Future task2              :         des4, after des3, 5d

       section Critical tasks
       Completed task in the critical line :crit, done, 2014-01-06,24h
       Implement parser and jison          :crit, done, after des1, 2d
       Create tests for parser             :crit, active, 3d
       Future task in critical line        :crit, 5d
       Create tests for renderer           :2d
       Add to mermaid                      :1d

       section Documentation
       Describe gantt syntax               :active, a1, after des1, 3d
       Add gantt diagram to demo page      :after a1  , 20h
       Add another diagram to demo page    :doc1, after a1  , 48h

       section Last section
       Describe gantt syntax               :after doc1, 3d
       Add gantt diagram to demo page      :20h
       Add another diagram to demo page    :48h

HTML

有些 Markdown 引擎支持在文档中嵌入的 html 元素。

有些 Markdown 语法所不支持的特性，可以使用 html 元素来支持。

折叠

折叠内容一

展开才能看到的内容

折叠内容二

展开才能看到的内容

居中

居中显示的文本

图片尺寸

编辑器

参考资料

限流基本原理

发表于 2020-01-20 分类于分布式

限流基本原理

📦 本文已归档到：「blog」

限流方法
参考资料

限流可以认为是服务降级的一种。限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

限流方法

计数器

控制单位时间的请求数量。使用 AtomicInteger 进行统计。

public class Counter {
    /**
     * 最大访问数量
     */
    private final int limit = 10;
    /**
     * 访问时间差
     */
    private final long timeout = 1000;
    /**
     * 请求时间
     */
    private long time;
    /**
     * 当前计数器
     */
    private AtomicInteger reqCount = new AtomicInteger(0);

    public boolean limit() {
        long now = System.currentTimeMillis();
        if (now < time + timeout) {
            // 单位时间内
            reqCount.addAndGet(1);
            return reqCount.get() <= limit;
        } else {
            // 超出单位时间
            time = now;
            reqCount = new AtomicInteger(0);
            return true;
        }
    }
}

滑动窗口

滑动窗口是对计数器方式的改进，增加一个时间粒度的度量单位。

import java.util.Iterator;
import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.stream.IntStream;

public class TimeWindow {
    private ConcurrentLinkedQueue<Long> queue = new ConcurrentLinkedQueue<Long>();

    /**
     * 间隔秒数
     */
    private int seconds;

    /**
     * 最大限流
     */
    private int max;

    public TimeWindow(int max, int seconds) {
        this.seconds = seconds;
        this.max = max;

        /**
         * 永续线程执行清理queue 任务
         */
        new Thread(() -> {
            while (true) {
                try {
                    // 等待 间隔秒数-1 执行清理操作
                    Thread.sleep((seconds - 1) * 1000L);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                clean();
            }
        }).start();

    }

    public static void main(String[] args) throws Exception {

        final TimeWindow timeWindow = new TimeWindow(10, 1);

        // 测试3个线程
        IntStream.range(0, 3).forEach((i) -> {
            new Thread(() -> {

                while (true) {

                    try {
                        Thread.sleep(new Random().nextInt(20) * 100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    timeWindow.take();
                }

            }).start();

        });

    }

    /**
     * 获取令牌，并且添加时间
     */
    public void take() {


        long start = System.currentTimeMillis();
        try {


            int size = sizeOfValid();
            if (size > max) {
                System.err.println("超限");

            }
            synchronized (queue) {
                if (sizeOfValid() > max) {
                    System.err.println("超限");
                    System.err.println("queue中有 " + queue.size() + " 最大数量 " + max);
                }
                this.queue.offer(System.currentTimeMillis());
            }
            System.out.println("queue中有 " + queue.size() + " 最大数量 " + max);

        }

    }


    public int sizeOfValid() {
        Iterator<Long> it = queue.iterator();
        Long ms = System.currentTimeMillis() - seconds * 1000;
        int count = 0;
        while (it.hasNext()) {
            long t = it.next();
            if (t > ms) {
                // 在当前的统计时间范围内
                count++;
            }
        }

        return count;
    }


    /**
     * 清理过期的时间
     */
    public void clean() {
        Long c = System.currentTimeMillis() - seconds * 1000;

        Long tl = null;
        while ((tl = queue.peek()) != null && tl < c) {
            System.out.println("清理数据");
            queue.poll();
        }
    }

}

令牌桶（Token Bucket）

规定固定容量的桶,token 以固定速度往桶内填充,当桶满时 token 不会被继续放入,每过来一个请求把 token 从桶中移除,如果桶中没有 token 不能请求。

public class TokenBucket {
    /**
     * 时间
     */
    private long time;
    /**
     * 总量
     */
    private Double total;
    /**
     * token 放入速度
     */
    private Double rate;
    /**
     * 当前总量
     */
    private Double nowSize;


    public boolean limit() {
        long now = System.currentTimeMillis();
        nowSize = Math.min(total, nowSize + (now - time) * rate);
        time = now;
        if (nowSize < 1) {
            // 桶里没有token
            return false;
        } else {
            // 存在token
            nowSize -= 1;
            return true;
        }
    }
}

漏桶

规定固定容量的桶，有水进入，有水流出。对于流进的水我们无法估计进来的数量、速度，对于流出的水我们可以控制速度。

public class LeakBucket {
    /**
     * 时间
     */
    private long time;
    /**
     * 总量
     */
    private Double total;
    /**
     * 水流出去的速度
     */
    private Double rate;
    /**
     * 当前总量
     */
    private Double nowSize;


    public boolean limit() {
        long now = System.currentTimeMillis();
        nowSize = Math.max(0, (nowSize - (now - time) * rate));
        time = now;
        if ((nowSize + 1) < total) {
            nowSize++;
            return true;
        } else {
            return false;
        }

    }
}

参考资料

系统测试架构

发表于 2019-12-10 分类于设计，架构

系统测试架构

软件测试描述一种用来促进鉴定软件的正确性、完整性、安全性和质量的过程。软件测试的经典定义是：在规定的条件下对程序进行操作，以发现程序错误，衡量软件质量，并对其是否能满足设计要求进行评估的过程。

现代软件开发项目中，分工明确，基本上都会有研发、测试、QA 等角色。不同角色由于关注的视角不同，测试目标和测试方法也不完全相同。本文主要从研发、测试的视角去考量软件测试技术。

注意：

为了方便，只有测试人员需要关注的测试点用【测试】标注；

而只有研发人员需要关注的测试点用【研发】标注；

都需要关注的测试点则不作标注。

测试方法分类

从测试设计方法分类

黑盒测试【测试】 - 把软件系统当作一个“黑箱”，无法了解或使用系统的内部结构及知识。从软件的行为，而不是内部结构出发来设计测试。
白盒测试【研发】 - 设计者可以看到软件系统的内部结构，并且使用软件的内部知识来指导测试数据及方法的选择。
灰盒测试 - 介于黑盒和白盒之间。

小结：

黑河测试通常针对的是软件的行为或功能，一般是测试人员主要关注的。

白盒测试通常则需要对软件有一定程度的了解，一般是开发人员所关注的。

灰盒测试通常是为了测试软件在特定的场景下的表现，而非主场景。

从测试的目的分类

功能测试

单元测试（Unit Test） - 在最低粒度的功能/参数上验证程序的准确性，比如测试一个函数的正确性。【研发】
- 常用技术：junit4
功能测试（Functional Test） - 验证模块的功能。【测试】
集成测试（Integration Test） - 验证几个互相有依赖关系的模块的功能。【测试】
场景测试（Scenario Test）- 验证几个模块是否能完成一个用户场景。【测试】
系统测试（System Test） - 对于整个系统功能的测试。【测试】
Alpha 测试 - 软件测试人员在真实用户环境中对软件进行全面的测试。【测试】
Beta 测试 - 也叫公测，是真实的用户在真实的环境中进行的测试。

非功能测试

压力测试（Stress test） - 验证软件在超过负载设计的情况下仍能返回正确的结果，没有崩溃
负载测试（Load test） - 测试软件在负载情况下能否正常工作
性能测试（Performance test） - 测试软件的效能，是否提供满意的服务质量。
- 常用技术：JMeter、JMH。
软件辅助功能测试（Accessibility test） - 测试软件是否向残疾用户提供足够的辅助功能
本地化/全球化测试（Localization/Globalization）
兼容性测试（Compatibility Test）
配置测试（Configuration Test） - 测试软件在各种配置下能否正常工作
可用性测试（Usability Test） – 测试软件是否好用
安全性测试（Security Test）

参考资料

分库分表基本原理

发表于 2019-10-16 分类于分布式

分库分表基本原理

📦 本文已归档到：「blog」

分片（Sharding）的基本思想就要把一个数据库切分成多个部分，存储在不同的数据库(server)上，从而缓解单一数据库的性能问题。

1. 数据分片

数据分片指按照某个维度将存放在单一数据库中的数据分散地存放至多个数据库或表中以达到提升性能瓶颈以及可用性的效果。数据分片的有效手段是对关系型数据库进行分库和分表。分库和分表均可以有效的避免由数据量超过可承受阈值而产生的查询瓶颈。除此之外，分库还能够用于有效的分散对数据库单点的访问量；分表虽然无法缓解数据库压力，但却能够提供尽量将分布式事务转化为本地事务的可能，一旦涉及到跨库的更新操作，分布式事务往往会使问题变得复杂。使用多主多从的分片方式，可以有效的避免数据单点，从而提升数据架构的可用性。

通过分库和分表进行数据的拆分来使得各个表的数据量保持在阈值以下，以及对流量进行疏导应对高访问量，是应对高并发和海量数据系统的有效手段。数据分片的拆分方式又分为垂直分片和水平分片。

1.1. 垂直分片

按照业务拆分的方式称为垂直分片，又称为纵向拆分，它的核心理念是专库专用。

在拆分之前，一个数据库由多个数据表构成，每个表对应着不同的业务。而拆分之后，则是按照业务将表进行归类，分布到不同的数据库中，从而将压力分散至不同的数据库。下图展示了根据业务需要，将用户表和订单表垂直分片到不同的数据库的方案。

垂直分片往往需要对架构和设计进行调整。通常来讲，是来不及应对互联网业务需求快速变化的；而且，它也并无法真正的解决单点瓶颈。垂直拆分可以缓解数据量和访问量带来的问题，但无法根治。如果垂直拆分之后，表中的数据量依然超过单节点所能承载的阈值，则需要水平分片来进一步处理。

1.2. 水平分片

水平分片又称为横向拆分。相对于垂直分片，水平分片不再将数据根据业务逻辑分类，而是通过某个字段（或某几个字段），根据某种规则将数据分散至多个库或表中，每个分片仅包含数据的一部分。例如：根据主键分片，偶数主键的记录放入 0 库（或表），奇数主键的记录放入 1 库（或表），如下图所示。

水平分片从理论上突破了单机数据量处理的瓶颈，并且扩展相对自由，是分库分表的标准解决方案。

2. 分库分表的问题

2.1. 事务问题

解决事务问题目前有两种可行的方案：分布式事务和通过应用程序与数据库共同控制实现事务下面对两套方案进行一个简单的对比。

方案一：使用分布式事务
- 优点：交由数据库管理，简单有效
- 缺点：性能代价高，特别是 sharding 越来越多时
方案二：由应用程序和数据库共同控制
- 原理：将一个跨多个数据库的分布式事务分拆成多个仅处于单个数据库上面的小事务，并通过应用程序来总控各个小事务。
- 优点：性能上有优势
- 缺点：需要应用程序在事务控制上做灵活设计。如果使用了spring的事务管理，改动起来会面临一定的困难。

跨库事务也是分布式的数据库集群要面对的棘手事情。合理采用分表，可以在降低单表数据量的情况下，尽量使用本地事务，善于使用同库不同表可有效避免分布式事务带来的麻烦。在不能避免跨库事务的场景，有些业务仍然需要保持事务的一致性。而基于 XA 的分布式事务由于在并发度高的场景中性能无法满足需要，并未被互联网巨头大规模使用，他们大多采用最终一致性的柔性事务代替强一致事务。

2.2. 跨节点 Join 的问题

只要是进行切分，跨节点 Join 的问题是不可避免的。但是良好的设计和切分却可以减少此类情况的发生。解决这一问题的普遍做法是分两次查询实现。在第一次查询的结果集中找出关联数据的 id，根据这些 id 发起第二次请求得到关联数据。

2.3. 跨节点的 count,order by,group by 以及聚合函数问题

这些是一类问题，因为它们都需要基于全部数据集合进行计算。多数的代理都不会自动处理合并工作。解决方案：与解决跨节点 join 问题的类似，分别在各个节点上得到结果后在应用程序端进行合并。和 join 不同的是每个结点的查询可以并行执行，因此很多时候它的速度要比单一大表快很多。但如果结果集很大，对应用程序内存的消耗是一个问题。

2.4. 数据迁移，容量规划，扩容等问题

来自淘宝综合业务平台团队，它利用对 2 的倍数取余具有向前兼容的特性（如对 4 取余得 1 的数对 2 取余也是 1）来分配数据，避免了行级别的数据迁移，但是依然需要进行表级别的迁移，同时对扩容规模和分表数量都有限制。总得来说，这些方案都不是十分的理想，多多少少都存在一些缺点，这也从一个侧面反映出了 Sharding 扩容的难度。

2.5. ID 问题

一旦数据库被切分到多个物理结点上，我们将不能再依赖数据库自身的主键生成机制。一方面，某个分区数据库自生成的 ID 无法保证在全局上是唯一的；另一方面，应用程序在插入数据之前需要先获得 ID,以便进行 SQL 路由. 一些常见的主键生成策略

2.5.1. UUID

使用 UUID 作主键是最简单的方案，但是缺点也是非常明显的。由于 UUID 非常的长，除占用大量存储空间外，最主要的问题是在索引上，在建立索引和基于索引进行查询时都存在性能问题。

2.5.2. 结合数据库维护一个 Sequence 表

此方案的思路也很简单，在数据库中建立一个 Sequence 表，表的结构类似于：

CREATE TABLE `SEQUENCE` (
    `table_name` varchar(18) NOT NULL,
    `nextid` bigint(20) NOT NULL,
    PRIMARY KEY (`table_name`)
) ENGINE=InnoDB

每当需要为某个表的新纪录生成 ID 时就从 Sequence 表中取出对应表的 nextid,并将 nextid 的值加 1 后更新到数据库中以备下次使用。此方案也较简单，但缺点同样明显：由于所有插入任何都需要访问该表，该表很容易成为系统性能瓶颈，同时它也存在单点问题，一旦该表数据库失效，整个应用程序将无法工作。有人提出使用 Master-Slave 进行主从同步，但这也只能解决单点问题，并不能解决读写比为 1:1 的访问压力问题。

2.5.3. Twitter 的分布式自增 ID 算法 Snowflake

在分布式系统中，需要生成全局 UID 的场合还是比较多的，twitter 的 snowflake 解决了这种需求，实现也还是很简单的，除去配置信息，核心代码就是毫秒级时间 41 位机器 ID 10 位毫秒内序列 12 位。

10—0000000000 0000000000 0000000000 0000000000 0 — 00000 —00000 —000000000000 在上面的字符串中，第一位为未使用（实际上也可作为 long 的符号位），接下来的 41 位为毫秒级时间，然后 5 位 datacenter 标识位，5 位机器 ID（并不算标识符，实际是为线程标识），然后 12 位该毫秒内的当前毫秒内的计数，加起来刚好 64 位，为一个 Long 型。

这样的好处是，整体上按照时间自增排序，并且整个分布式系统内不会产生 ID 碰撞（由 datacenter 和机器 ID 作区分），并且效率较高，经测试，snowflake 每秒能够产生 26 万 ID 左右，完全满足需要。

2.6. 跨分片的排序分页

一般来讲，分页时需要按照指定字段进行排序。当排序字段就是分片字段的时候，我们通过分片规则可以比较容易定位到指定的分片，而当排序字段非分片字段的时候，情况就会变得比较复杂了。为了最终结果的准确性，我们需要在不同的分片节点中将数据进行排序并返回，并将不同分片返回的结果集进行汇总和再次排序，最后再返回给用户。如下图所示：

上面图中所描述的只是最简单的一种情况（取第一页数据），看起来对性能的影响并不大。但是，如果想取出第 10 页数据，情况又将变得复杂很多，如下图所示：

有些读者可能并不太理解，为什么不能像获取第一页数据那样简单处理（排序取出前 10 条再合并、排序）。其实并不难理解，因为各分片节点中的数据可能是随机的，为了排序的准确性，必须把所有分片节点的前 N 页数据都排序好后做合并，最后再进行整体的排序。很显然，这样的操作是比较消耗资源的，用户越往后翻页，系统性能将会越差。

那如何解决分库情况下的分页问题呢？有以下几种办法：

如果是在前台应用提供分页，则限定用户只能看前面 n 页，这个限制在业务上也是合理的，一般看后面的分页意义不大（如果一定要看，可以要求用户缩小范围重新查询）。

如果是后台批处理任务要求分批获取数据，则可以加大 page size，比如每次获取 5000 条记录，有效减少分页数（当然离线访问一般走备库，避免冲击主库）。

分库设计时，一般还有配套大数据平台汇总所有分库的记录，有些分页查询可以考虑走大数据平台。

2.7. 分库策略

根据数值范围，比如用户 Id 为 1-9999 的记录分到第一个库，10000-20000 的分到第二个库，以此类推。
根据数值取模，比如用户 Id mod n，余数为 0 的记录放到第一个库，余数为 1 的放到第二个库，以此类推。

优劣比较：评价指标按照范围分库按照 Mod 分库库数量前期数目比较小，可以随用户/业务按需增长前期即根据 mode 因子确定库数量，数目一般比较大访问性能前期库数量小，全库查询消耗资源少，单库查询性能略差前期库数量大，全库查询消耗资源多，单库查询性能略好调整库数量比较容易，一般只需为新用户增加库，老库拆分也只影响单个库困难，改变 mod 因子导致数据在所有库之间迁移数据热点新旧用户购物频率有差异，有数据热点问题新旧用户均匀到分布到各个库，无热点实践中，为了处理简单，选择 mod 分库的比较多。同时二次分库时，为了数据迁移方便，一般是按倍数增加，比如初始 4 个库，二次分裂为 8 个，再 16 个。这样对于某个库的数据，一半数据移到新库，剩余不动，对比每次只增加一个库，所有数据都要大规模变动。补充下，mod 分库一般每个库记录数比较均匀，但也有些数据库，存在超级 Id，这些 Id 的记录远远超过其他 Id，比如在广告场景下，某个大广告主的广告数可能占总体很大比例。如果按照广告主 Id 取模分库，某些库的记录数会特别多，对于这些超级 Id，需要提供单独库来存储记录。

2.8. 分库数量

分库数量首先和单库能处理的记录数有关，一般来说，Mysql 单库超过 5000 万条记录，Oracle 单库超过 1 亿条记录，DB 压力就很大(当然处理能力和字段数量/访问模式/记录长度有进一步关系)。

在满足上述前提下，如果分库数量少，达不到分散存储和减轻 DB 性能压力的目的；如果分库的数量多，好处是每个库记录少，单库访问性能好，但对于跨多个库的访问，应用程序需要访问多个库，如果是并发模式，要消耗宝贵的线程资源；如果是串行模式，执行时间会急剧增加。

最后分库数量还直接影响硬件的投入，一般每个分库跑在单独物理机上，多一个库意味多一台设备。所以具体分多少个库，要综合评估，一般初次分库建议分 4-8 个库。

3. 读写分离

面对日益增加的系统访问量，数据库的吞吐量面临着巨大瓶颈。对于同一时刻有大量并发读操作和较少写操作类型的应用系统来说，将数据库拆分为主库和从库，主库负责处理事务性的增删改操作，从库负责处理查询操作，能够有效的避免由数据更新导致的行锁，使得整个系统的查询性能得到极大的改善。

通过一主多从的配置方式，可以将查询请求均匀的分散到多个数据副本，能够进一步的提升系统的处理能力。使用多主多从的方式，不但能够提升系统的吞吐量，还能够提升系统的可用性，可以达到在任何一个数据库宕机，甚至磁盘物理损坏的情况下仍然不影响系统的正常运行。

与将数据根据分片键打散至各个数据节点的水平分片不同，读写分离则是根据 SQL 语义的分析，将读操作和写操作分别路由至主库与从库。

读写分离的数据节点中的数据内容是一致的，而水平分片的每个数据节点的数据内容却并不相同。将水平分片和读写分离联合使用，能够更加有效的提升系统性能。

3.1. 挑战

读写分离虽然可以提升系统的吞吐量和可用性，但同时也带来了数据不一致的问题。这包括多个主库之间的数据一致性，以及主库与从库之间的数据一致性的问题。并且，读写分离也带来了与数据分片同样的问题，它同样会使得应用开发和运维人员对数据库的操作和运维变得更加复杂。下图展现了将分库分表与读写分离一同使用时，应用程序与数据库集群之间的复杂拓扑关系。

4. 参考资料

Redis 双端链表

发表于 2019-09-19

总结 Redis 双端链表的实现。

阅读全文 »

Redis 字符串：SDS

发表于 2019-09-19

总结 Redis 封装 C 字符串为 SDS 的实现。

阅读全文 »

Redis 内存管理：zmalloc

发表于 2019-09-17

总结 Redis 内存分配工具 zmalloc 的实现。

阅读全文 »

分布式存储基本原理

发表于 2019-08-21 分类于分布式

分布式存储基本原理

📦 本文已归档到：「blog」

1. 分区规则

分布式数据库 首先要解决把 整个数据集 按照 分区规则 映射到 多个节点 的问题，即把 数据集 划分到 多个节点 上，每个节点负责 整体数据 的一个子集。

数据分布通常有 哈希分区 和 顺序分区 两种方式，对比如下：

分区方式	特点	相关产品
哈希分区	离散程度好，数据分布与业务无关，无法顺序访问	Redis Cluster，Cassandra，Dynamo
顺序分区	离散程度易倾斜，数据分布与业务相关，可以顺序访问	BigTable，HBase，Hypertable

由于 Redis Cluster 采用 哈希分区规则，这里重点讨论 哈希分区。常见的 哈希分区 规则有几种，下面分别介绍：

1.1. 节点取余分区

使用特定的数据，如 Redis 的键或用户 ID，再根据 节点数量 N 使用公式：hash（key）% N 计算出 哈希值，用来决定数据映射到哪一个节点上。

优点

这种方式的突出优点是 简单性，常用于 数据库 的 分库分表规则。一般采用 预分区 的方式，提前根据 数据量 规划好 分区数，比如划分为 512 或 1024 张表，保证可支撑未来一段时间的 数据容量，再根据 负载情况 将表迁移到其他 数据库 中。扩容时通常采用 翻倍扩容，避免 数据映射 全部被打乱，导致 全量迁移 的情况。

缺点

当 节点数量 变化时，如扩容或收缩节点，数据节点 映射关系 需要重新计算，会导致数据的 重新迁移。

1.2. 一致性哈希分区

一致性哈希 可以很好的解决 稳定性问题，可以将所有的 存储节点 排列在 首尾相接 的 Hash 环上，每个 key 在计算 Hash 后会 顺时针 找到临接的 存储节点 存放。而当有节点加入或退出时，仅影响该节点在 Hash 环上 顺时针相邻 的 后续节点。

优点

加入和删除节点只影响 哈希环 中 顺时针方向 的 相邻的节点，对其他节点无影响。

缺点

加减节点 会造成 哈希环 中部分数据 无法命中。当使用 少量节点 时，节点变化 将大范围影响 哈希环 中 数据映射，不适合 少量数据节点 的分布式方案。普通的 一致性哈希分区 在增减节点时需要 增加一倍 或 减去一半 节点才能保证数据和 负载的均衡。

注意：因为 一致性哈希分区 的这些缺点，一些分布式系统采用 虚拟槽 对 一致性哈希 进行改进，比如 Dynamo 系统。

1.3. 虚拟槽分区

虚拟槽分区 巧妙地使用了 哈希空间，使用 分散度良好 的 哈希函数 把所有数据映射到一个 固定范围 的 整数集合 中，整数定义为槽（slot）。这个范围一般 远远大于 节点数，比如 Redis Cluster 槽范围是 0 ~ 16383。槽是集群内 数据管理 和迁移的 基本单位。采用 大范围槽 的主要目的是为了方便 数据拆分 和 集群扩展。每个节点会负责 一定数量的槽，如图所示：

当前集群有 `3` 个节点，每个节点平均大约负责 `5460` 个 **槽**。由于采用 **高质量** 的 **哈希算法**，每个槽所映射的数据通常比较 **均匀**，将数据平均划分到 `3` 个节点进行 **数据分区**。`Redis Cluster` 就是采用 **虚拟槽分区**。

集群中的每个节点负责一部分哈希槽，比如集群中有３个节点，则：

节点Ａ存储的哈希槽范围是：0 – 5460
节点Ｂ存储的哈希槽范围是：5461 – 10922
节点Ｃ存储的哈希槽范围是：10923 – 16383

这种结构很容易添加或者删除节点。如果增加一个节点 4，就需要从节点 1 ~ 3 获得部分槽分配到节点 4 上。如果想移除节点 1，需要将节点 1 中的槽移到节点 2 ~ 3 上，然后将 没有任何槽 的节点 1 从集群中移除即可。

由于从一个节点将 哈希槽 移动到另一个节点并不会 停止服务，所以无论 添加删除 或者改变某个节点的 哈希槽的数量 都不会造成 集群不可用 的状态.

2. 参考资料

深入剖析 Redis 系列(三) - Redis 集群模式搭建与原理详解

分布式 ID 基本原理

发表于 2019-07-24 分类于分布式

分布式 ID 基本原理

📦 本文已归档到：「blog」

传统数据库软件开发中，主键自动生成技术是基本需求。而各个数据库对于该需求也提供了相应的支持，比如 MySQL 的自增键，Oracle 的自增序列等。

数据分片后，不同数据节点生成全局唯一主键是非常棘手的问题。同一个逻辑表内的不同实际表之间的自增键由于无法互相感知而产生重复主键。虽然可通过约束自增主键初始值和步长的方式避免碰撞，但需引入额外的运维规则，使解决方案缺乏完整性和可扩展性。

为此，需要使用分布式 ID 来解决此问题。本文总结业界常用的分布式 ID 解决方案。

1. 简介
2. UUID
3. 数据库自增键
4. 利用 Redis 生成键
5. 雪花算法（Snowflake）
6. Leaf
7. 参考资料

1. 简介

首先，分布式 ID 应该具备哪些特性呢？

全局唯一性 - 不能出现重复的 ID 号，既然是唯一标识，这是最基本的要求。
趋势递增 - 在 MySQL InnoDB 引擎中使用的是聚集索引，由于多数 RDBMS 使用 B-tree 的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
单调递增 - 保证下一个 ID 一定大于上一个 ID，例如事务版本号、IM 增量消息、排序等特殊需求。
信息安全 - 如果 ID 是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定 URL 即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要 ID 无规则、不规则。

2. UUID

UUID 是通用唯一识别码（Universally Unique Identifier)的缩写，开放软件基金会(OSF)规范定义了包括网卡 MAC 地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素。利用这些元素来生成 UUID。

UUID 是由 128 位二进制组成，一般转换成十六进制，然后用 String 表示。在 java 中有个 UUID 类,在他的注释中我们看见这里有 4 种不同的 UUID 的生成策略:

random - 基于随机数生成 UUID，由于 Java 中的随机数是伪随机数，其重复的概率是可以被计算出来的。这个一般我们用下面的代码获取基于随机数的 UUID:

1	String id = UUID.randomUUID().toString();

time-based - 基于时间的 UUID,这个一般是通过当前时间，随机数，和本地 Mac 地址来计算出来，自带的 JDK 包并没有这个算法的我们在一些 UUIDUtil 中，比如我们的 log4j.core.util，会重新定义 UUID 的高位和低位。

public static UUID getTimeBasedUuid() {
    long time = System.currentTimeMillis() * 10000L + 122192928000000000L + (long)(COUNT.incrementAndGet() % 10000);
    long timeLow = (time & 4294967295L) << 32;
    long timeMid = (time & 281470681743360L) >> 16;
    long timeHi = (time & 1152640029630136320L) >> 48;
    long most = timeLow | timeMid | 4096L | timeHi;
    return new UUID(most, LEAST);
}

DCE security - DCE 安全的 UUID。
name-based - 基于名字的 UUID，通过计算名字和名字空间的 MD5 来计算 UUID。

2.1. UUID 的优点

通过本地生成，没有经过网络 I/O，性能较快

2.2. UUID 的缺点

长度过长 - UUID 太长，16 字节 128 位，通常以 36 长度的字符串表示，很多场景不适用。例如：Mysql 官方明确建议主键越短越好，36 个字符长度的 UUID 不符合要求。
信息不安全 - 基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露，这个漏洞曾被用于寻找梅丽莎病毒的制作者位置。
无序性 - 不能生成递增有序的数字。这对于一些特定场景不利。例如：如果作为数据库主键，在 InnoDB 引擎下，UUID 的无序性可能会引起数据位置频繁变动，严重影响性能。

2.3. 适用场景

UUID 的适用场景可以为不需要担心过多的空间占用，以及不需要生成有递增趋势的数字。在 Log4j 里 UuidPatternConverter 中加入了 UUID 来标识每一条日志。

3. 数据库自增键

提到自增键，最先想到的肯定是直接使用数据库自增键。_各数据库对于该需求也提供了相应的支持，比如 MySQL 的自增键，Oracle 的自增序列等_。

3.1. 优点

非常简单，利用现有数据库的功能实现，成本小，有 DBA 专业维护
有序递增
方便排序和分页

3.2. 缺点

强依赖数据库，当数据库异常时整个系统不可用。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
生成 ID 性能瓶颈限制在单台 MySQL 的读写性能。
简单递增容易被其他人分析利用
- 比如根据用户 ID 来分析注册人数，猜测出服务的一个大概状况。

3.3. 适用场景

数据量不大，并发不高的场景。

3.4. 改进

对于 MySQL 性能问题，可用如下方案解决：在分布式系统中我们可以多部署几台机器，每台机器设置不同的初始值，且步长和机器数相等。比如有两台机器。设置步长 step 为 2，TicketServer1 的初始值为 1（1，3，5，7，9，11…）、TicketServer2 的初始值为 2（2，4，6，8，10…）。这是 Flickr 团队在 2010 年撰文介绍的一种主键生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。如下所示，为了实现上述方案分别设置两台机器对应的参数，TicketServer1 从 1 开始发号，TicketServer2 从 2 开始发号，两台机器每次发号之后都递增 2。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

这种架构存在以下缺点：

系统水平扩展比较困难，比如定义好了步长和机器台数之后，如果要添加机器该怎么做？假设现在只有一台机器发号是 1,2,3,4,5（步长是 1），这个时候需要扩容机器一台。可以这样做：把第二台机器的初始值设置得比第一台超过很多，比如 14（假设在扩容时间之内第一台不可能发到 14），同时设置步长为 2，那么这台机器下发的号码都是 14 以后的偶数。然后摘掉第一台，把 ID 值保留为奇数，比如 7，然后修改第一台的步长为 2。让它符合我们定义的号段标准，对于这个例子来说就是让第一台以后只能产生奇数。扩容方案看起来复杂吗？貌似还好，现在想象一下如果我们线上有 100 台机器，这个时候要扩容该怎么做？简直是噩梦。所以系统水平扩展方案复杂难以实现。
ID 没有了单调递增的特性，只能趋势递增，这个缺点对于一般业务需求不是很重要，可以容忍。
数据库压力还是很大，每次获取 ID 都得读写一次数据库，只能靠堆机器来提高性能。

4. 利用 Redis 生成键

Redis 中有两个命令 Incr，IncrBy。

因为 Redis 是单线程的，所以能保证原子性。

4.1. 优点

性能比数据库好
能满足有序递增

4.2. 缺点

由于 Redis 是内存数据库，即使支持持久化（AOF 和 RDB），但是依然可能丢失数据，造成 ID 重复。
依赖于 Redis 生成键，如果 Redis 服务不稳定，会影响 ID 生成。

4.3. 适用场景

Redis 性能比数据库好，但是有可能会出现 ID 重复和不稳定。如果可以接受，那么就可以使用这种方案。

5. 雪花算法（Snowflake）

雪花算法（Snowflake）是由 Twitter 公布的分布式主键生成算法，它会生成一个 64 bit 的整数，可以保证不同进程主键的不重复性，以及相同进程主键的有序性。

在同一个进程中，它首先是通过时间位保证不重复，如果时间相同则是通过序列位保证。同时由于时间位是单调递增的，且各个服务器如果大体做了时间同步，那么生成的主键在分布式环境可以认为是总体有序的，这就保证了对索引字段的插入的高效性。

5.1. 基本原理

键的组成

使用雪花算法生成的主键，二进制表示形式包含 4 部分，从高位到低位分表为：1bit 符号位、41bit 时间戳位、10bit 工作进程位以及 12bit 序列号位。

符号位(1bit)

预留的符号位，恒为零。

时间戳位(41bit)

41 位的时间戳可以容纳的毫秒数是 2 的 41 次幂，一年所使用的毫秒数是：365 * 24 * 60 * 60 * 1000。通过计算可知：

1	Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);

结果约等于 69.73 年。ShardingSphere 的雪花算法的时间纪元从 2016 年 11 月 1 日零点开始，可以使用到 2086 年，相信能满足绝大部分系统的要求。

工作进程位(10bit)

该标志在 Java 进程内是唯一的，如果是分布式应用部署应保证每个工作进程的 id 是不同的。该值默认为 0，可通过属性设置。

序列号位(12bit)

该序列是用来在同一个毫秒内生成不同的 ID。如果在这个毫秒内生成的数量超过 4096(2 的 12 次幂)，那么生成器会等待到下个毫秒继续生成。

雪花算法主键的详细结构见下图：

时钟回拨

服务器时钟回拨会导致产生重复序列，因此默认分布式主键生成器提供了一个最大容忍的时钟回拨毫秒数。如果时钟回拨的时间超过最大容忍的毫秒数阈值，则程序报错；如果在可容忍的范围内，默认分布式主键生成器会等待时钟同步到最后一次主键生成的时间后再继续工作。最大容忍的时钟回拨毫秒数的默认值为 0，可通过属性设置。

灵活定制

上面只是一个将 64bit 划分的标准，当然也不一定这么做，可以根据不同业务的具体场景来划分，比如下面给出一个业务场景：

服务目前 QPS10 万，预计几年之内会发展到百万。
当前机器三地部署，上海，北京，深圳都有。
当前机器 10 台左右，预计未来会增加至百台。

这个时候我们根据上面的场景可以再次合理的划分 62bit，QPS 几年之内会发展到百万，那么每毫秒就是千级的请求，目前 10 台机器那么每台机器承担百级的请求，为了保证扩展，后面的循环位可以限制到 1024，也就是 2^10，那么循环位 10 位就足够了。

机器三地部署我们可以用 3bit 总共 8 来表示机房位置，当前的机器 10 台，为了保证扩展到百台那么可以用 7bit 128 来表示，时间位依然是 41bit，那么还剩下 64-10-3-7-41-1 = 2bit，还剩下 2bit 可以用来进行扩展。

5.2. 优点

生成的 ID 都是趋势递增的。
不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成 ID 的性能也是非常高的。
可以根据自身业务特性分配 bit 位，非常灵活。

5.3. 缺点

强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

5.4. 适用场景

当我们需要无序不能被猜测的 ID，并且需要一定高性能，且需要 long 型，那么就可以使用我们雪花算法。比如常见的订单 ID，用雪花算法别人就无法猜测你每天的订单量是多少。

5.5. 防止时钟回拨

雪花算法是强依赖于时间的，而如果机器时间发生回拨，有可能会生成重复的 ID。

我们可以针对算法做一些优化，来防止时钟回拨生成重复 ID。

用当前时间和上一次的时间进行判断，如果当前时间小于上一次的时间那么肯定是发生了回拨。普通的算法会直接抛出异常，这里我们可以对其进行优化，一般分为两个情况:

如果时间回拨时间较短，比如配置 5ms 以内，那么可以直接等待一定的时间，让机器的时间追上来。
如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:
- 直接拒绝，抛出异常。打日志，通知 RD 时钟回滚。
- 利用扩展位。上面我们讨论过，不同业务场景位数可能用不到那么多比特位，那么我们可以把扩展位数利用起来。比如：当这个时间回拨比较长的时候，我们可以不需要等待，直接在扩展位加 1。两位的扩展位允许我们有三次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。

6. Leaf

美团提供了一种分布式 ID 解决方案 Leaf，其本质可以视为数据库分段+服务缓存 ID。

详情可以参考 Leaf——美团点评分布式 ID 生成系统

6.1. 基本原理

使用数据库生成 ID，但是做了如下改进：

原方案每次获取 ID 都得读写一次数据库，造成数据库压力大。改为利用 proxy server 批量获取，每次获取一个 segment(step 决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。 - 各个业务不同的发号需求用 biz_tag 字段来区分，每个 biz-tag 的 ID 获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对 biz_tag 分库分表就行。

数据库表设计如下：

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

重要字段说明：

biz_tag 用来区分业务
max_id 表示该 biz_tag 目前所被分配的 ID 号段的最大值
step 表示每次分配的号段长度。原来获取 ID 每次都需要写数据库，现在只需要把 step 设置得足够大，比如 1000。那么只有当 1000 个号被消耗完了之后才会去重新读写一次数据库。读写数据库的频率从 1 减小到了 1/step。

大致架构如下图所示：

test_tag 在第一台 Leaf 机器上是 1~1000 的号段，当这个号段用完时，会去加载另一个长度为 step=1000 的号段，假设另外两台号段都没有更新，这个时候第一台机器新加载的号段就应该是 3001~4000。同时数据库对应的 biz_tag 这条数据的 max_id 会从 3000 被更新成 4000，更新号段的 SQL 语句如下：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

6.2. 优点

比数据库自增键性能高
能保证键趋势递增。
如果数据库宕机，由于 proxServer 有缓存，依然可以坚持一段时间。

6.3. 缺点

和主键递增一样，容易被人猜测。
数据库宕机后，虽然能支撑一段时间，但是仍然会造成系统不可用。

6.4. 适用场景

需要趋势递增，并且 ID 大小可控制的，可以使用这套方案。

当然这个方案也可以通过一些手段避免被人猜测，把 ID 变成是无序的，比如把我们生成的数据是一个递增的 long 型，把这个 Long 分成几个部分，比如可以分成几组三位数，几组四位数，然后在建立一个映射表，将我们的数据变成无序。

深入剖析共识性算法 Raft

一、Raft 简介

分布式一致性

复制状态机

RAFT 应用

二、Raft 基础

服务器角色

任期

RPC

三、选举 Leader

选举规则

自己成为 Leader

其他的服务器成为 Leader

没有任何服务器成为 Leader

单 Candidate 选举

多 Candidate 选举

四、日志复制

日志格式

日志复制流程

日志一致性

Leader 和 Follower 日志不一致的可能

Leader 和 Follower 日志一致的保证

五、安全性

选举限制

提交旧任期的日志条目

六、日志压缩

参考资料

Markdown Cheat Sheet

目录

标题

文本样式

列表

无序列表

有序列表

任务列表

多级列表

分割线

链接

普通链接

图片

图片链接

锚点

引用

代码高亮

标签

代码块

语法

表格

Emoji 表情

注脚

数学公式

Diff

UML 图

流程图

时序图

甘特图

HTML

折叠

居中

图片尺寸

编辑器

参考资料

限流基本原理

限流方法

计数器

滑动窗口

令牌桶（Token Bucket）

漏桶

参考资料

系统测试架构

测试方法分类

从测试设计方法分类

从测试的目的分类

功能测试

非功能测试

参考资料

分库分表基本原理

1. 数据分片

1.1. 垂直分片

1.2. 水平分片