分布式相关算法总结

2022-01-13 分布式分布式 0 评论字数统计: 17839字阅读时长: 36分

分布式相关算法总结

一、拜占庭将军问题

拜占庭将军问题是一个共识问题。这个概念最早由Leslie Lamport于1980年发表的“Reaching agreement in the presence of faults"论文中提出。

拜占庭是位于如今土耳其的伊斯坦布尔，是东罗马帝国的首都。由于拜占庭罗马帝国国土辽阔，出于防御的原因，每个军队之间的距离相隔较远，所以将军之间只能通过信件来传递信息。当发生战争的时候，拜占庭军队的所有将军必须达成共识，决定是否攻击敌人。但是，军队内可能存在间谍或者叛徒扰乱将军们的决定，在进行达成共识交流时，最后的结果可能不能代表大多数将军的意见。这时，在已知存在成员不可靠的情况下，其余忠诚的将军如何派除叛徒或者间谍的影响达成一致的决定，就是著名的拜占庭将军问题。

拜占庭将军问题对现实世界的模拟。由于硬件错误、网络拥塞、连接失败等原因，计算机和网络可能会出现预想不到的行为。拜占庭错误在计算机科学领域特指的是分布式系统中的某些恶意节点扰乱系统的正常运行，包括选择性不传递消息，选择性伪造消息等。

二、CAP、BASE、ACID理论

2.1 CAP原理

学习分布式经典的理论莫过于CAP理论。

CPA定理 指的是在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）。CAP 原则上，这三个要素最多只能同时实现两点，不可能三者兼顾。

元素	含义
一致性（Consistency）	所有节点访问同一份最新的数据副本
可用性（Availability）	每次访问都能保证得到一个非报错的响应，但不保证数据是最新的
分区容错性（Partition tolerance）	当分布式系统遇到网络分区故障的时候，仍然可以对外界提供一致性、可用性的服务

2.1.1 一致性（Consistency）

这里的一致性指的是强一致性而不是最终一致性。一致性严谨的表述是原子读写，即所有的读写都应该看起来是“原子”的，或者“串行”的。也就是说，在一致性系统中，一旦客户端向系统内其中一个节点写入一份数据，那么之后client从其他节点读取到的都是刚刚写入的数据。

上面的系统模拟一致性模型。

客户端向分布式系统其中一个节点写入val1
由于val1是新写入的值，其他节点（B、C）都没有设置该值，所以需要从A节点同步该数据
待全部节点都同步完成之后，A节点再向客户端返回一个成功写入的响应。
之后，另一个客户端向B节点请求该数据的时候，B节点可以直接该值返回给该客户端

2.1.2 可用性（Availability）

分布式系统中的非故障节点在收到请求时，都必须返回响应。

在可用系统中，如果我们的客户端向服务器发送请求，并且服务器未崩溃，则服务器必须最终响应客户端，不允许服务器忽略客户的请求。

2.1.3 分区容错性（Partition tolerance）

允许网络丢失从一个节点发送到另一个节点的任意多条消息，即不同步也就是说，节点A和节点B发送给对方的任何消息都是可以放弃的，也就是说节点A和节点B可能因为各种意外情况，导致无法成功进行同步，分布式系统要能容忍这种情况。

2.1.4 三者不可同时兼顾

假设三者能同时兼顾

首先我们对系统进行分区，由于满足分区容错性，节点A与节点B之间不能够进行正常通信，初始值都为val0
这时，客户端向节点A写入val1，但是因为分区容错性，该val1没有同步到节点B。此时，节点A是val1，节点B是val0。
由于需要满足可用性，节点A必须向client1返回数据。
这时，client2向节点B访问数据，节点B只能返回val0

显然，节点A与节点B出现了数据不一致的现象，不能满足一致性。

2.1.5 三者权衡

CA (Consistency + Availability)：关注一致性和可用性，它需要非常严格的全体一致的协议，比如“两阶段提交”（2PC）。CA 系统不能容忍网络错误或节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了，还是只是网络问题。唯一安全的做法就是把自己变成只读的。
CP (consistency + partition tolerance)：关注一致性和分区容忍性。它关注的是系统里大多数人的一致性协议，比如：Paxos 算法 (Quorum 类的算法)。这样的系统只需要保证大多数结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。
AP (availability + partition tolerance)：这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。

2.2 BASE理论

BASE理论是Basically Available(基本可用)，Soft State（软状态）和Eventually Consistent（最终一致性）三个短语的缩写

核心思想：

即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。

2.2.1 基本可用（Basically Available）

基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。

相较于正常的系统而言：

**响应时间上的损失：**正常情况下的搜索引擎0.5秒即返回用户结果，而基本可用的搜索引擎可以在2秒作用返回结果。
**功能上的损失：**在一个电商网站上，正常情况下，用户可以顺利完成每一笔订单

2.2.2 软状态（Soft State）

软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现

2.2.3 最终一致性（Eventual Consistency）

最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

2.3 ACID

ACID是传统数据库常用的设计理念，追求强一致性模型。

关系数据库的ACID模型拥有高一致性 + 可用性很难进行分区：

原子性（Atomicity）：一个事务中所有操作都必须全部完成，要么全部不完成。
一致性（Consistency）：在事务开始或结束时，数据库应该在一致状态。
隔离性（Isolation）：事务的隔离性是多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作数据所干扰，多个并发事务之间要相互隔离。
持久性（Durability）：持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响

三、分布式协议和算法

3.1 Raft 算法

3.1.1 背景

在Raft算法诞生之前，Paoxs几乎成为了一致性协议的代名词。1990年，Leslie Lamport教授向ACM Transactions on Computer Systems提交了关于Paxos算法的论文。然而，对大多数人来说，理解Paxos太困难了，而且难以实现。而一致性协议对大规模分布式系统又非常重要。因此，斯坦福大学的Diego Ongaro 和 John Ousterhout 决定设计一种比Paxos更容易理解的一致性算法—-Raft

3.1.2 概念

Raft是实现分布式共识的一种算法，主要用来管理日志复制的一致性。它和Paxos的功能是一样，但是相比于Paxos，Raft算法更容易理解、也更容易应用到实际的系统当中。

Raft的三个角色（状态）

在一个由Raft协议组织的集群中，一共包含如下3类角色：

Leader（领导人）：负责日志的同步管理，处理来自客户端的请求，与Follower保持heartBeat的联系。同一时刻最多只有一个Leader存在。
Candidate（候选人）：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发起选举，选举胜出（获得超过半数节点的投票）后，从Candidate转为Leader状态。
Follower（群众）：响应 Leader 的日志同步请求，响应Candidate的邀票请求，以及把客户端请求到Follower的事务转发（重定向）给Leader。所有节点开始的时候都是Follower状态。

复制状态机

在一个分布式数据库中，如果每个节点的状态一致，每个节点都执行相同的命令序列，那么最终他们会得到一个一致的状态。也就是和说，为了保证整个分布式系统的一致性，我们需要保证每个节点执行相同的命令序列，也就是说每个节点的日志要保持一样。所以说，保证日志复制一致就是Raft等一致性算法的工作了。

这里就涉及Replicated State Machine（复制状态机）。它的基本思想是一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中。如上图所示。在一个节点上，一致性模块（Consensus Module，也就是分布式共识算法）接收到了来自客户端的命令。然后把接收到的命令写入到日志中，该节点和其他节点通过一致性模块进行通信确保每个日志最终包含相同的命令序列。一旦这些日志的命令被正确复制，每个节点的状态机（State Machine）都会按照相同的序列去执行他们，从而最终得到一致的状态。然后将达成共识的结果返回给客户端。

任期（Term）

在分布式系统中，“时间同步”是一个很大的难题，因为每个机器可能由于所处的地理位置、机器环境等因素会不同程度造成时钟不一致，但是为了识别“过期信息”，时间信息必不可少。

Raft算法中就采用任期（Term）的概念，将时间切分为一个个的Term（同时每个节点自身也会本地维护currentTerm），可以认为是逻辑上的时间。

每一任期的开始都是一次领导人选举，一个或多个候选人（Candidate）会尝试成为领导（Leader）。如果一个人赢得选举，就会在该任期（Term）内剩余的时间担任领导人。在某些情况下，选票可能会被评分，有可能没有选出领导人（如t3），那么，将会开始另一任期，并且理科开始下一次选举。Raft 算法保证在给定的一个任期最少要有一个领导人。

心跳（heartbeats）和超时机制（timeout）

在Raft算法中，有两个timeout机制来控制领导人选举：

一个是选举定时器（election timeout）：即Follower等待成为Candidate状态的等待时间，这个时间被随机设定为150ms~300ms之间。

另一个是heartbeat timeout：在某个节点成为Leader以后，它会发送Append Entries消息给其他节点，这些消息就是通过heartbeat timeout来传送，Follower接收到Leader的心跳包的同时也重新设置选举定时器。

3.1.3 工作机制

Raft将一致性问题分解成了三个相对独立的子问题：

**选举（Leader Election）：**当Leader宕机或者集群初始化时，一个新的Leader需要被选举出来；
**日志复制（Log Replication）：**Leader接收来自客户端的请求并将其以日志条目的形式复制到集群中的其他节点，并且强制要求其他节点的日志与自己保持一致；
**安全性（Safety）：**如果任何服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。

领导人选举（Leader Election）

（1）一开始，所有节点都是以Follower角色启动，所有节点的状态都是 Follower，初始 Term（任期）为 0。同时启动选举定时器（时间随机，降低冲突概率），超时时间在100~500 毫秒之间且并不一致。

（2）如果一个节点发现在超过选举定时器的时间后一直没有收到Leader发送的心跳请求，则该节点就会成为候选人（Candidate），并且一直处于该状态，直到下列三种情况发生：

该节点（Candidate）在选举中获胜
其他节点赢得了选举
一段时间后没有任何一台服务器赢得选举（这时候，就会进入下一轮Term的选举，并随机设置选举定时器的时间）

（3）然后这个候选人（Candidate）就会向其他节点发送投票请求（Request Vote），如果得到半数以上节点的同意，就成为Leader（Leader）。如果选举超时，还没有Leader选出，则进入下一任期（Term），重新选举。

（4）完成Leader选举后，Leader就会定时给其他节点发送心跳包（Heartbeat），告诉其他节点Leader还在运行，同时重置这些节点的选举定时器。

日志复制（Log Replication）

在一个Raft集群中，只有Leader节点可以处理客户端的请求（如果客户端的请求发送到了Follower，Follower将请求重定向到Leader），客户端的每个请求都包含一条被复制状态机执行的指令。Leader将这条指令作为一条新的日志条目（Entry）附加到日志中去，然后并行地将附加条目发送给Follower，让它们复制这条日志条目。

（1）客户端向Leader提交指令，Leader收到命令后，将命令追加到本地日志中。此时，这个命令处于“uncomitted”状态，复制状态机不会执行该命令。

（2）Leader 与 Followers 之间保持着心跳联系，随心跳 Leader 将追加的 Entry（AppendEntries）并行地发送给其它的 Follower，并让它们复制这条日志条目，这一过程称为复制（Replicate）。注意：

Leader 向 Followers 发送的不仅仅是追加的 Entry（AppendEntries）。

在发送追加日志条目的时候，Leader会将新的日志条目紧接着之前条目的索引位置（preLogIndex），Leader 任期号（Term）也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么它就会拒绝接收新的日志条目，因为出现这种情况说明 Follower 和 Leader 不一致。
如何解决 Leader 与 Follower 不一致的问题？

Leader和Follower一系列崩溃的青葵会使它们的日志处于不一致状态。Follower可能会丢失一些在新的Leader中有的日志条目，它可能会拥有一些Leader没有的日志条目，又或者两个都有可能发送。

要使两者回复一致，Leader需要找到两者最后达到一致的地方（LogIndex），实际上是个回溯的过程，然后删除从那个点之后的全部日志条目，发送自己的日志给 Follower。所有的这些操作都在进行附加日志的一致性检查时完成。

Leader为每个Follower都维护一个nextIndex，它表示下一个需要发送给Follower的日志条目的索引。当一个节点刚转为Leader时，它会初始化所有的nextIndex值，为自己的最后一个日志的index+1。如果一个Follower的日志和Leader不一致，那么在下一次AppendEntry的时候就会失败。在被 Follower 拒绝之后，Leader 就会减小该 Follower 对应的 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得 Leader 和 Follower 的日志达成一致。当这种情况发生，附加日志就会成功，这时就会把 Follower 冲突的日志条目全部删除并且加上 Leader 的日志。一旦附加日志成功，那么 Follower 的日志就会和 Leader 保持一致，并且在接下来的任期继续保持一致。

（3）Leader等待Follower回应。 Followers接收到Leader发送过来的复制请求后，有两种可能的回应

写入本地日志中，返回Success
一致性检查失败，拒绝写入，返回False

当 Leader 收到大多数 Followers 的回应后，会将写入的 Entry 标记为提交状态（Committed），并把这条日志条目应用到它的状态机中。

（4）前面完成后，Leader会向客户端回应。

（5）Leader节点在提交命令后，下一次的心跳包中就带有通知其他节点提交命令的消息，其他节点收到Leader的消息后，就将命令应用到状态机中（State Machine），最终每个节点的日志都保持了一致性。

安全性（Safety）

不能保证每个状态机能按照相同的顺序执行同样的指令。例如，当领导人提交了若干日志条目的同时一个追随者可能宕机了，之后它又被选为了领导人然后用新的日志条目覆盖掉了旧的那些，最后，不同的状态机可能执行不同的命令序列。

因此，Raft算法通过在领导人选举阶段增加一个限制来完善了Raft算法。该限制可以保证，Leader对于固定的任期号（Term），都拥有之前任期的所有被提交的日志条目。

选举限制

在所有基于 Leader 机制的一致性算法中，Leader 都必须存储所有已经提交的日志条目。一个Candidate节点要成为赢得选举，就需要跟网络中大部分节点进行通信，这就意味着每一条已经提交的日志条目最少在其中一台服务器上出现。Raft 使用了一种简单而有效的方法，以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的 Leader 中。换言之，日志条目的传送是单向的，只从 Leader 传给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目。RequestVote RPC 实现了这个限制：这个 RPC包括候选人的日志信息，如果它自己的日志比候选人的日志要新，那么它会拒绝候选人的投票请求。

3.2 一致性算法

3.2.1 前言

在互联网中，一致性哈希算法(Consistent Hashing)在分布式系统的应用还是十分广泛的。一致性哈希算法最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中提出。具体思路就是一致性哈希将整个哈希输出空间设置为一个环形区域。

3.2.2 分布式缓存

随着业务的发展，流量的剧增，单体项目逐渐划分为分布式系统。对于经常访问的数据，我们可以使用缓存机制来存储，减少数据库的压力。

一般会使用Redis作为缓存，为了保证Redis的高可用，我们一般会对Redis做主从复制，组成Master-Slave的形式，进行数据的读写分离。

优化的最简单的策略是随机分配请求。每次Redis请求会随机发送到其中一个集群中，这种策略会存在下面的两个问题：

同一份数据可能在多个Redis集群中存在，造成数据冗余。
某一份数据在其中一台Redis数据库已存在，但是再次访问Redis数据库，并没有命中数据已存在的库。无法保证对相同的key的所有访问都发送到相同的Redis中。

为了解决上述的问题，我们可以使用hash算法，将key 进行hash取模，将数据保存到特定的Redis数据库中。例如，我们有6台服务器，存储图片的时候，可以将图片的名称作为key，计算key 的hash值再%6，得到0-5 中其中一个值，这个值对应的是服务器的编号，也就是该图片保存到的服务器的编号。

但是，使用上述的hash算法进行缓存的时候，会出现一些缺陷，试想一下，如果6台服务已经无法满足我们的需求的时候，我们需要增加服务器的数量，例如数量由6变成8，此时，如果再用这种方法存储一张图片的话，那么这张图片所在的服务器编号必定与原来6台服务器时所在的服务器编号不同，除数由6变8，余数肯定不同了。这种情况带来的结果就是当服务器数量变动时，所有缓存的位置都要发生改变，换句话说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据，同理，假设3台缓存中突然有一台缓存服务器出现了故障，无法进行缓存，那么我们则需要将故障机器移除，但是如果移除了一台缓存服务器，那么缓存服务器数量从6台变为4台，如果想要访问一张图片，这张图片的缓存位置必定会发生改变，以前缓存的图片也会失去缓存的作用与意义，由于大量缓存在同一时间失效，造成了缓存的雪崩，此时前端缓存已经无法起到承担部分压力的作用，后端服务器将会承受巨大的压力，整个系统很有可能被压垮，所以，我们应该想办法不让这种情况发生，但是由于上述HASH算法本身的缘故，使用取模法进行缓存时，这种情况是无法避免的，为了解决这些问题，一致性哈希算法诞生了。

3.2.3 一致性哈希算法

上述方法存在的问题：

当缓存服务器数量发生变化的时候，会引起缓存雪崩，可能会造成整体系统压力过大而崩溃（大量缓存同时失效）
当缓存服务器数量发生变换的时候，几乎所有缓存的位置都发生了变化

其实，一致性哈希算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性哈希算法是对2^32取模

一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n 个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

一致性hash算法将整个hash空间组织成一个虚拟的圆环，Hash函数的值空间为0 ~ 2^32 - 1(一个32位无符号整型)

整个空间按顺时针方向组织，我们将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台服务器就确定在了哈希环的一个位置上。

hash（服务器A的IP地址） % 2^32

通过上述公式算出的结果一定是一个0到2^32-1之间的一个整数，我们就用算出的这个整数，代表服务器A，既然这个整数肯定处于0到2^32-1之间，那么，上图中的hash环上必定有一个点与这个整数对应，而我们刚才已经说明，使用这个整数代表服务器A，那么，服务器A就可以映射到这个环上，其他的服务器也依次类推，最后如下图示意

假设，我们需要使用缓存服务器缓存图片，而且我们仍然使用图片的名称作为找到图片的key，那么我们使用如下公式可以将图片映射到上图中的hash环上。从此位置沿顺时针滚动，遇到的第一台服务器就是其应该定位到的服务器。

hash（图片名称） % 2^32

映射后的示意图如下，下图中的橘黄色圆形表示图片。

一致性哈希算法就是通过这种方法，判断一个对象应该被缓存到哪台服务器上的，将缓存服务器与被缓存对象都映射到hash环上以后，从被缓存对象的位置出发，沿顺时针方向遇到的第一个服务器，就是当前对象将要缓存于的服务器，由于被缓存对象与服务器hash后的值是固定的，所以，在服务器不变的情况下，一张图片必定会被缓存到固定的服务器上，那么，当下次想要访问这张图片时，只要再次使用相同的算法进行计算，即可算出这个图片被缓存在哪个服务器上，直接去对应的服务器查找对应的图片即可。

优点

容错性

假如服务器B宕机了，那么，原本存储到服务器B的数据B保存到服务器C中。因此，其中一台宕机后，干扰的只有前面的数据（原数据被保存到顺时针的下一个服务器），而不会干扰到其他的数据。

拓展性

假如在服务器B与服务器C之间添加服务器D，数据C就会保存到服务器D，受影响的只有服务器C，其他数据不会有影响。

缺点

前面部分都是讲述到服务器节点较多和节点分布较为均衡的情况，如果节点较少就会出现节点分布不均衡造成数据倾斜问题。

如果服务器被映射成上图中的模样，那么被缓存的对象很有可能大部分集中缓存在某一台服务器上。如果出现上图中的情况，A、B、C三台服务器并没有被合理的平均的充分利用，缓存分布的极度不均匀，而且，如果此时服务器A出现故障，那么失效缓存的数量也将达到最大值，在极端情况下，仍然有可能引起系统的崩溃，上图中的情况则被称之为hash环的偏斜，那么，我们应该怎样防止hash环的偏斜呢？一致性hash算法中使用”虚拟节点”解决了这个问题。

3.2.4 虚拟节点

为了解决这种数据存储不平衡的问题，一致性哈希算法引入了虚拟节点机制，即对每个节点计算多个哈希值，每个计算结果位置都放置在对应节点中，这些节点称为虚拟节点。

从上图可以看出，A、B、C三台服务器分别虚拟出了一个虚拟节点，当然，如果你需要，也可以虚拟出更多的虚拟节点。引入虚拟节点的概念后，缓存的分布就均衡多了，上图中，1号、3号图片被缓存在服务器A中，5号、4号图片被缓存在服务器B中，6号、2号图片被缓存在服务器C中，如果你还不放心，可以虚拟出更多的虚拟节点，以便减小hash环偏斜所带来的影响，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大。

3.3 Gossip 协议

Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。对你来说，掌握这个协议不仅能很好地理解这种最常用的，实现最终一致性的算法，也能在后续工作中得心应手地实现数据的最终一致性。

3.3.1 Gossip 三板斧

Gossip 的三板斧分别是：直接邮寄（Direct Mail）、**反熵（Anti-entropy）**和 谣言传播（Rumor mongering）。

3.3.2 直接邮寄（Direct Mail）

直接邮寄：就是直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。从图中你可以看到，节点 A 直接将更新数据发送给了节点 B、C。

但是直接邮寄有个不足之处就是当缓存队列满了的时候，会造成数据丢失，所以只采用直接邮寄是无法实现最终一致性的。

3.3.3 反熵（Anti-entropy）

反熵：指的是集群中的节点，每隔一段时间就随机选择某个其他节点，然后通过相互交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性：

实现反熵的时候，主要有推、拉和推拉三种方式

推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵：

拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵：

推拉的方式就是同时修复自己的副本和对方副本的熵：

注意：反熵需要节点两两交换和对比自己所有的数据，执行反熵时通讯成本会很高，所以在实际场景中避免频繁执行反熵，并且可以通过引入校验和等机制，减少需要对比的数据量和通讯信息等。

虽然反熵比较实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境，这时候反熵就不适用了。当面对这种场景的时候就得通过“谣言传播”来实现最终一致性。

3.3.4 谣言传播（Rumor mongering）

谣言传播，广泛地散播谣言，它指的是当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据：

节点 A 向节点 B、D 发送新数据，节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。其实，谣言传播非常具有传染性，它适合动态变化的分布式系统。

3.3.5 小结

在实际场景中，实现数据副本的最终一致性时，一般而言，直接邮寄的方式是一定要实现的，因为不需要做一致性对比，只是通过发送更新数据或缓存重传，来修复数据的不一致，性能损耗低。在存储组件中，节点都是已知的，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式，同步更新数据，实现最终一致。

四、分布式锁

4.1 初始锁

1. 锁的双面性

现在我们写的程序基本上都有一定的并发性，要么单台多进线程、要么多台机器集群化，在仅读的场景下是不需要加锁的，因为数据是一致的，在读写混合或者写场景下如果不加以限制和约束就会造成写混乱数据不一致的情况。

如果业务安全和正确性无法保证，再多的并发也是无意义的。

高并发多半是考验基础架构是否强悍，合理正确地使用锁才是个人能力的体现。

凡事基本上都是双面的，锁可以在一定程度上保证数据的一致性，但是锁也意味着维护和使用的复杂性，当然也伴随着性能的损耗，最大的锁可能就是CPython解释器的全局解释器锁GIL了。

2.单机锁和分布式锁

锁依据使用范围可简单分为：单机锁和分布式锁。

Linux提供系统级单机锁，这类锁可以实现线程同步和互斥资源的共享，单机锁实现了机器内部线程之间对共享资源的并发控制。

在分布式部署高并发场景下，经常会遇到资源的互斥访问的问题，最有效最普遍的方法是给共享资源或者对共享资源的操作加一把锁。

分布式锁是控制分布式系统之间同步访问共享资源的一种方式，用于在分布式系统中协调他们之间的动作。

4.2 分布式锁

1. 分布式锁的实现简介

分布式CAP理论告诉我们需要做取舍:

任何一个分布式系统有三大特性：一致性Consistency、可用性Availability和分区容错性Partition Tolerance，但是由于网络分区不受人为控制，在网络发生分区时，我们必须在可用性和一致性二者中选择之一。

在互联网领域的绝大多数的场景中，都需要牺牲强一致性来换取系统的高可用性，系统往往只保证最终一致性。在很多场景中为了保证数据的最终一致性，需要很多的技术方案来支持，比如分布式事务、分布式锁等。

分布式锁一般有四种实现方式：

基于数据库在数据库中创建一张表，表里包含方法名等字段，并且在方法名字段上面创建唯一索引，执行某个方法需要使用此方法名向表中插入数据，成功插入则获取锁，执行结束则删除对应的行数据释放锁
基于缓存数据库Redis Redis性能好并且实现方便，但是单节点的分布式锁在故障迁移时产生安全问题，Redlock是Redis的作者 Antirez 提出的集群模式分布式锁，基于N个完全独立的Redis节点实现分布式锁的高可用
基于ZooKeeper ZooKeeper 是以 Paxos 算法为基础的分布式应用程序协调服务，为分布式应用提供一致性服务的开源组件
基于Etcd Etcd是基于Raft算法为基础的分布式应用程序协调服务，为分布式应用提供一致性服务的开源组件

2. 分布式锁需要具备的条件

分布式锁在应用于分布式系统环境相比单机锁更为复杂，该锁需要具备一些特性：

互斥性：在任意时刻，只有一个客户端（进程）能持有锁
安全性：避免死锁情况，当一个客户端在持有锁期间内，由于意外崩溃而导致锁未能主动解锁，其持有的锁也能够被正确释放，并保证后续其它客户端也能加锁
可用性：分布式锁需要有一定的高可用能力，当提供锁的服务节点故障（宕机）时不影响服务运行，避免单点风险，如Redis的集群模式、哨兵模式，ETCD/zookeeper的集群选主能力等保证HA，保证自身持有的数据与故障节点一致。
对称性：对同一个锁，加锁和解锁必须是同一个进程，即不能把其他进程持有的锁给释放了，这又称为锁的可重入性。

4.3 基于Redis实现分布式锁

既然是锁，核心操作无外乎加锁、解锁。

Redis的加锁操作：

SET lock_name my_random_value NX PX 30000

lock_name，锁的名称，对于 Redis 而言，lock_name 就是 Key-Value 中的 Key，具有唯一性。
random_value，由客户端生成的一个随机字符串，它要保证在足够长的一段时间内，且在所有客户端的所有获取锁的请求中都是唯一的，用于唯一标识锁的持有者。
NX 只有当 lock_name(key) 不存在的时候才能 SET 成功，从而保证只有一个客户端能获得锁，而其它客户端在锁被释放之前都无法获得锁。
PX 30000 表示这个锁节点有一个 30 秒的自动过期时间（目的是为了防止持有锁的客户端故障后，无法主动释放锁而导致死锁，因此要求锁的持有者必须在过期时间之内执行完相关操作并释放锁）。

Redis的解锁操作：

del lock_name

在加锁时为锁设置过期时间，当过期时间到达，Redis 会自动删除对应的 Key-Value，从而避免死锁。注意，这个过期时间需要结合具体业务综合评估设置，以保证锁的持有者能够在过期时间之内执行完相关操作并释放锁。
正常执行完毕，未到达锁过期时间，通过del lock_name主动释放锁。

上述方式实现的redis分布锁有个缺点：

只作用在一个Redis节点上，即使Redis通过sentinel保证高可用，如果这个master节点由于某些原因发生了主从切换，那么就会出现锁丢失的情况：

在Redis的master节点上拿到了锁；但是这个加锁的key还没有同步到slave节点；

master故障，发生故障转移，slave节点升级为master节点；导致锁丢失。

由此 redis官方推荐 redlock 来解决这个问题。

Redlock

Redlock：全名叫做 Redis Distributed Lock;即使用redis实现的分布式锁；

使用场景：多个服务间保证同一时刻同一时间段内同一用户只能有一个请求（防止关键业务出现并发攻击）；

官网文档地址如下：https://redis.io/topics/distlock

这个锁的算法实现了多redis实例的情况，相对于单redis节点来说，优点在于防止了单节点故障造成整个服务停止运行的情况；并且在多节点中锁的设计，及多节点同时崩溃等各种意外情况有自己独特的设计方法；

多节点redis实现的分布式锁算法(RedLock):有效防止单点故障

假设有5个完全独立的redis主服务器

1.获取当前时间戳

2.client尝试按照顺序使用相同的key,value获取所有redis服务的锁，在获取锁的过程中的获取时间比锁过期时间短很多，这是为了不要过长时间等待已经关闭的redis服务。并且试着获取下一个redis实例。

比如：TTL为5s,设置获取锁最多用1s，所以如果一秒内无法获取锁，就放弃获取这个锁，从而尝试获取下个锁

3.client通过获取所有能获取的锁后的时间减去第一步的时间，这个时间差要小于TTL时间并且至少有3个redis实例成功获取锁，才算真正的获取锁成功

4如果成功获取锁，则锁的真正有效时间是 TTL减去第三步的时间差的时间；比如：TTL 是5s,获取所有锁用了2s,则真正锁有效时间为3s(其实应该再减去时钟漂移);

5.如果客户端由于某些原因获取锁失败，便会开始解锁所有redis实例；因为可能已经获取了小于3个锁，必须释放，否则影响其他client获取锁

4.4 基于etcd实现分布式锁

4.4.1 机制

etcd 支持以下功能，正是依赖这些功能来实现分布式锁的：

Lease 机制：即租约机制（TTL，Time To Live），Etcd 可以为存储的 KV 对设置租约，当租约到期，KV 将失效删除；同时也支持续约，即 KeepAlive。
Revision 机制：每个 key 带有一个 Revision 属性值，etcd 每进行一次事务对应的全局 Revision 值都会加一，因此每个 key 对应的 Revision 属性值都是全局唯一的。通过比较 Revision 的大小就可以知道进行写操作的顺序。
在实现分布式锁时，多个程序同时抢锁，根据 Revision 值大小依次获得锁，可以避免 “羊群效应” （也称 “惊群效应”），实现公平锁。
Prefix 机制：即前缀机制，也称目录机制。可以根据前缀（目录）获取该目录下所有的 key 及对应的属性（包括 key, value 以及 revision 等）。
Watch 机制：即监听机制，Watch 机制支持 Watch 某个固定的 key，也支持 Watch 一个目录（前缀机制），当被 Watch 的 key 或目录发生变化，客户端将收到通知。

4.4.2 过程

步骤 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 读取 keyValue 列表（keyValue 中带有 key 对应的 Revision），判断自己 key 的 Revision 是否为当前列表中最小的，如果是则认为获得锁；否则监听列表中前一个 Revision 比自己小的 key 的删除事件，一旦监听到删除事件或者因租约失效而删除的事件，则自己获得锁。
步骤 5: 执行业务

获得锁后，操作共享资源，执行业务代码。
步骤 6: 释放锁

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

4.4.3 原理

Lock()函数的实现很简单：

// Lock locks the mutex with a cancelable context. If the context is canceled
// while trying to acquire the lock, the mutex tries to clean its stale lock entry.
func (m *Mutex) Lock(ctx context.Context) error {
    s := m.s
    client := m.s.Client()

    m.myKey = fmt.Sprintf("%s%x", m.pfx, s.Lease())
    cmp := v3.Compare(v3.CreateRevision(m.myKey), "=", 0)
    // put self in lock waiters via myKey; oldest waiter holds lock
    put := v3.OpPut(m.myKey, "", v3.WithLease(s.Lease()))
    // reuse key in case this session already holds the lock
    get := v3.OpGet(m.myKey)
    // fetch current holder to complete uncontended path with only one RPC
    getOwner := v3.OpGet(m.pfx, v3.WithFirstCreate()...)
    resp, err := client.Txn(ctx).If(cmp).Then(put, getOwner).Else(get, getOwner).Commit()
    if err != nil {
        return err
    }
    m.myRev = resp.Header.Revision
    if !resp.Succeeded {
        m.myRev = resp.Responses[0].GetResponseRange().Kvs[0].CreateRevision
    }
    // if no key on prefix / the minimum rev is key, already hold the lock
    ownerKey := resp.Responses[1].GetResponseRange().Kvs
    if len(ownerKey) == 0 || ownerKey[0].CreateRevision == m.myRev {
        m.hdr = resp.Header
        return nil
    }

    // wait for deletion revisions prior to myKey
    hdr, werr := waitDeletes(ctx, client, m.pfx, m.myRev-1)
    // release lock key if wait failed
    if werr != nil {
        m.Unlock(client.Ctx())
    } else {
        m.hdr = hdr
    }
    return werr
}

首先通过一个事务来尝试加锁，这个事务主要包含了4个操作: cmp、put、get、getOwner。需要注意的是，key是由pfx和Lease()组成的。

cmp: 比较加锁的key的修订版本是否是0。如果是0就代表这个锁不存在。
put: 向加锁的key中存储一个空值，这个操作就是一个加锁的操作，但是这把锁是有超时时间的，超时的时间是session的默认时长。超时是为了防止锁没有被正常释放导致死锁。
get: get就是通过key来查询
getOwner: 注意这里是用m.pfx来查询的，并且带了查询参数WithFirstCreate()。使用pfx来查询是因为其他的session也会用同样的pfx来尝试加锁，并且因为每个LeaseID都不同，所以第一次肯定会put成功。但是只有最早使用这个pfx的session才是持有锁的，所以这个getOwner的含义就是这样的。

接下来才是通过判断来检查是否持有锁

m.myRev = resp.Header.Revision
if !resp.Succeeded {
    m.myRev = resp.Responses[0].GetResponseRange().Kvs[0].CreateRevision
}
// if no key on prefix / the minimum rev is key, already hold the lock
ownerKey := resp.Responses[1].GetResponseRange().Kvs
if len(ownerKey) == 0 || ownerKey[0].CreateRevision == m.myRev {
    m.hdr = resp.Header
    return nil
}

m.myRev是当前的版本号，resp.Succeeded是cmp为true时值为true，否则是false。这里的判断表明当同一个session非第一次尝试加锁，当前的版本号应该取这个key的最新的版本号。

下面是取得锁的持有者的key。如果当前没有人持有这把锁，那么默认当前会话获得了锁。或者锁持有者的版本号和当前的版本号一致，那么当前的会话就是锁的持有者。

// wait for deletion revisions prior to myKey
hdr, werr := waitDeletes(ctx, client, m.pfx, m.myRev-1)
// release lock key if wait failed
if werr != nil {
    m.Unlock(client.Ctx())
} else {
    m.hdr = hdr
}

上面这段代码就很好理解了，因为走到这里说明没有获取到锁，那么这里等待锁的删除。

waitDeletes方法的实现也很简单，但是需要注意的是，这里的getOpts只会获取比当前会话版本号更低的key，然后去监控最新的key的删除。等这个key删除了，自己也就拿到锁了。

这种分布式锁的实现和我一开始的预想是不同的。它不存在锁的竞争，不存在重复的尝试加锁的操作。而是通过使用统一的前缀pfx来put，然后根据各自的版本号来排队获取锁。效率非常的高。避免了惊群效应

如图所示，共有4个session来加锁，那么根据revision来排队，获取锁的顺序为session2 -> session3 -> session1 -> session4。

这里面需要注意一个惊群效应，每一个client在锁住/lock这个path的时候，实际都已经插入了自己的数据，类似/lock/LEASE_ID，并且返回了各自的index（就是raft算法里面的日志索引），而只有最小的才算是拿到了锁，其他的client需要watch等待。例如client1拿到了锁，client2和client3在等待，而client2拿到的index比client3的更小，那么对于client1删除锁之后，client3其实并不关心，并不需要去watch。所以综上，等待的节点只需要watch比自己index小并且差距最小的节点删除事件即可。

4.5 基于Zookeeper实现分布式锁

4.5.1 原理

zookeeper主要利用节点无法重复创建以及节点的监听通知机制来实现分布式锁的，当一个线程在zookeeper中创建了一个节点（假设“/node")，其他线程再创建这个节点会提示失败。因为zookeeper内部执行命令跟redis一样是单线程的，多线程下的操作节点请求会排队执行，当发现节点已经存在，则提示节点已存在！

当前线程加完锁，逻辑代码执行完毕后，还需要删除节点释放锁，供其他线程争抢。其他线程利用zookeeper的节点监听特性，一旦节点被修改（删除），就会收到来自服务端的消息，表示自己可以参与锁的争夺了，如果还是没有抢到则继续监听/等待此节点。zookeeper根据这两个特性可以实现分布式锁，分布式锁又分为公平锁、非公平锁、读写锁等等。

4.5.2 zookeeper实现非公平锁

可以使用持久化节点和临时节点实现。一般使用临时节点，因为持久化节点需要自己手动删除，临时节点session关闭就会过期，zookeeper内部线程自动删除！

加锁原理：

上述非公平锁的实现方式在高并发场景下，性能会下降得比较厉害。主要原因：所有的连接都在对同一个节点进行监听，当服务器检测到删除事件时，要通知所有的连接，所有连接同时接收到事件，再次并发竞争，竞争失败再次等待，这也称为“羊群效应”。羊群效应需要大量地通知其他连接，而且不止一次，会造成资源浪费。

为了避免羊群效应，可以采用公平锁的实现方式实现分布式锁。

4.5.3 zookeeper实现公平锁

公平锁的实现需要保证节点的顺序性，可以使用zookeeper的持久化顺序节点或者临时顺序节点，推荐使用临时顺序节点。

加锁原理：

/lock节点可以用 Container节点类型，该节点类型规定，如果Container节点下面没有子节点，则Container节点在未来会被Zookeeper自动清除,定时任务默认60s 检查一次。使用临时顺序子节点代表锁，在session关闭时，也会自动清理，进而触发/lock节点的自动删除，减少人工维护成本。

问题一：当前线程怎么判断自己能不能获得锁？

在公平锁的实现中，只有顺序最小的节点才能获取分布式锁，每当有一个线程进来就会对/lock节点下所有的子节点进行排序，并比较自己的序号是不是列表中最小的，如果是就获取锁，如果不是，就对序号比自己小的上一个节点进行监听。

问题二：排队中的某个子节点如果挂掉，会导致监听序列崩溃吗？

公平锁中，临时顺序节点中的每个节点都监听着前一个序号比它小的节点。以A-B-C三个节点为例，A为最小的节点，如果B节点挂掉了（或者被删除），此时A节点仍然在处理业务逻辑，未被释放，那么整个序列都会变为不连续的。但是B节点挂掉（或者被删除）会对C节点发送通知机制，C接收到B已挂掉的通知，要去竞争锁，所以C会获取/lock节点下所有的子节点，排序比较它是否为最小的节点，发现自己不是，因为A还在，然后C节点会对序号比它小的A节点进行监听，自动跳过了意外挂掉的B节点，这样就完成了监听关系的自动维护！

问题三：顺序子节点已创建，但服务端响应失败，造成节点多次创建如何解决？

客户端发送节点创建的命令，服务器接收到并创建成功，但是响应客户端的时候，服务器闪断了，又在session超时时间内连接上了。此时节点已经创建成功了，但是客户端并没有收到节点创建成功的消息，它认为节点已经创建失败，由于客户端重试机制的存在，会重新发送创建节点的命令，这样就会导致节点多次创建，会有部分顺序节点一直存在服务器中，不会被释放，称为僵尸节点。

4.5.4 zookeeper实现读写锁（共享锁）

zookeeper的公平锁和非公平锁的实现都有一个共同特性，都是互斥锁，同一时间只能有一个请求占有。如果请求并发量增大后，无论读写，所有的请求都得加锁，性能会急剧下降。所以，我们不需要所有请求都加锁，如果数据没有任何写操作只有读操作的话，可以不用加锁。

如果读数据的请求还没完成，这时候对数据的写请求到来。这时候已经有人在读数据了，这时候不能再写数据了，不然数据不正确。所以直到前面读锁全部释放完以后，写请求才能执行，所以需要给所有的读请求加一个读标识（读锁），让写请求知道，这个时候是不能修改数据的。不然数据不一致。

同样，当写操作还没完成，读操作是不允许执行的，不然也会导致数据不一致，所以要给写请求加一个写标识（写锁），避免同时对共享数据进行写操作。

（1）读请求：如果前面的请求都是read，则直接获取锁（读读共享），如果前面的请求有write请求，则该read请求不能直接获取锁（读写互斥），需要对前面的write请求节点进行监听。如果前面有多个write请求，则对距离自己最近的write请求进行监听。

（2）写请求：无论前面是read请求还是write请求，都会对其监听，与公平锁和非公平锁性质不同，对其他行为互斥。

五、总结

目前为止，已经对分布式的概念有了比较清晰的理解，了解了一些分布式协议的原理以及分布式锁的实现等，对自己学习与实现分布式锁有很大的帮助，当然我了解到的还只是分布式领域的冰山一角，还有许多知识等待我继续挖掘研究。

本文链接: https://lincx-911.github.io/2022/01/distribution/

License: CC BY 4.0 CN

lincxdeveloper

预防掉发，多敲代码

分布式相关算法总结

分布式相关算法总结

一、拜占庭将军问题

二、CAP、BASE、ACID理论

2.1 CAP原理

2.1.1 一致性（Consistency）

2.1.2 可用性（Availability）

2.1.3 分区容错性（Partition tolerance）

2.1.4 三者不可同时兼顾

2.1.5 三者权衡

2.2 BASE理论

2.2.1 基本可用（Basically Available）

2.2.2 软状态（Soft State）

2.2.3 最终一致性（Eventual Consistency）

2.3 ACID

三、分布式协议和算法

3.1 Raft 算法

3.1.1 背景

3.1.2 概念

3.1.3 工作机制

领导人选举（Leader Election）

日志复制（Log Replication）

安全性（Safety）

3.2 一致性算法

3.2.1 前言

3.2.2 分布式缓存

3.2.3 一致性哈希算法

优点

缺点

3.2.4 虚拟节点

3.3 Gossip 协议

3.3.1 Gossip 三板斧

3.3.2 直接邮寄（Direct Mail）

3.3.3 反熵（Anti-entropy）

3.3.4 谣言传播（Rumor mongering）

3.3.5 小结

四、 分布式锁

4.1 初始锁

4.2 分布式锁

4.3 基于Redis实现分布式锁

4.4 基于etcd实现分布式锁

4.4.1 机制

4.4.2 过程

4.4.3 原理

4.5 基于Zookeeper实现分布式锁

4.5.1 原理

4.5.2 zookeeper实现非公平锁

4.5.3 zookeeper实现公平锁

4.5.4 zookeeper实现读写锁（共享锁）

五、总结

lincxdeveloper

四、分布式锁