关于后端:分布式理论和一致性算法详解

分布式系统是一个硬件或软件组成散布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的零碎

散布性

分布式系统的多台计算机都会在空间上随便散布的，同时，机器的散布状况也会随时变动
对等性

分布式系统中的计算机没有主 / 从之分，既没有管制整个零碎的主机，也没有被管制的从机，组成分布式系统的所有计算机节点都是对等的。正本 (Replica)是分布式系统最常见的概念之一，指的是分布式系统对数据和服务提供的一种冗余形式。
在常见的分布式系统中，为了对外提供高可用的服务，咱们往往会对数据和服务进行正本解决。数据正本是指在不同的节点上长久化同一份数据，当某一个节点上存储的数据失落时，能够从正本上读取到该数据，这是解决分布式系统数据失落问题
最为无效的伎俩。另一类正本是服务正本，指多个节点提供同样的服务，每个节点都有能力接管来自内部的申请并进行相应的解决
并发性

在“问题的提出”局部，咱们曾经提到过与“更新的并发性”相干的内容。在一个计算机网络中，程序运行过程中的并发性操作是十分常见的行为，例如同一个分布式系统中的多个节点，可能会并发地操作一些共享的资源，诸如数据库或分布式存储等，如何精确并高效地协调分布式并发操作也成为了分布式系统架构与设计中最大的挑战之一。
不足全局时钟

后面提到，一个典型的分布式系统是由一系列在空间上随便散布的多个过程组成的，具备显著的散布性，这些过程之间通过替换音讯来进行互相通信。因而，在分布式系统中，很难定义两个事件究竞谁先谁后，起因就是因为分布式系统不足一个全局的时钟序列管制。对于分布式系统的时钟和事件程序中曾经做了十分粗浅的解说.
故障总是会产生

组成分布式系统的所有计算机，都有可能产生任何模式的故障。一个被大量工程实际所测验过的黄金定理是: 任何在设计阶段思考到的异常情况，肯定会在零碎理论运行中产生，并且，在零碎理论运行过程中还会遇到很多在设计时未能思考到的异样故障。所以，除非需要指标容许，在零碎设计时不能放过任何异常情况。

通信异样

从集中式向分布式演变的过程中，必然引人了网络因素，而因为网络自身的不可靠性、因而也引人了额定的问题。分布式系统须要在各个节点之间进行网络通信，因而每次网络通信都会随同着网络不可用的危险，网络光纤、路由器或是 DNS 等硬件设施或是零碎不可用都会导致最终分布式系统无奈顺利完成一次网络通信。
另外，即便分布式系统各节点之间的网络通信可能失常进行，其延时也会远大于单机操作。通常咱们认为在古代计算机体系结构中，单机内存拜访的延时在纳秒数量级(通常是 10ns 左右)，而失常的一次网络通信的提早在 0.1- 1ms 左右(相当于内存拜访延时的 105~106 倍)，如此微小的延时差异，也会影响音讯的收发的过程，因而音讯失落和音讯提早变得十分广泛
网络分区

当网络因为产生异常情况，导致分布式系统中局部节点之间的网络延时一直增大，最终导致组成分布式系统的所有节点中，只有局部节点之间可能进行失常通信。而另一些节点则不能咱们将这个景象称为网络分区，就是俗称的“脑裂”。当网络分区呈现时
分布式系统会呈现部分小集群，在极其状况下，这些部分小集群会独立实现本来须要整个分布式系统能力实现的性能，包含对数据的事务处理，这就对分布式一致性提出了十分大的挑战。
三态
后面提到，在分布式系统环境下，网络可能存在各种各样的问题；因而分布式系统的每一次申请和响应，存在特有的“三态”概念，即胜利、失败与超时。
在传统的单机零碎中，应用程序在调用一次函数之后，可能失去一个十分明确的响应，胜利或失败；而在分布式系统中，因为网络是不牢靠的，尽管在绝大部分状况下，网络通信也能接管到胜利或失败的响应，然而当网络出现异常时，就可能呈现超时的状况，通常有以下两种状况：
- 申请时音讯失落
- 响应时音讯失落
节点故障

节点故则是分布式环境下另一个比拟常见的问题，指的是组成分布式系统的服务器节点呈现的宕机或“死”景象。通常依据教训来说，每个节点都有可能会呈现故障，并且每天都在产生

CAP 实践通知咱们，一个分布式系统不可能同时满足一致性 (C:Consistency)、可用性(A: Availability) 和分区容错性 (P: Partition tolerance) 这三个根本需要，最多只能同时满足其中的两项。

Consistency 一致性：拜访分布式系统中任意节点，总能返回统一的后果
- Every read receives the most recent write or an error
Availability 可用性：分布式系统总能向客户端返回响应
- Every request receives a (non-error) response, without the guarantee that it contains the most recent write
Partition tolerance 分区容忍：当分布式系统节点间通信产生了音讯失落或音讯提早，依然容许零碎持续运行
- The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

CAP 定理：最多三选二，无奈兼得，通常在 CP 或者 AP 之间做出抉择

不统一的产生

client 向 Node1 写入新值 v1

写入胜利 Node1 更新成 v1

Node1 在没有将变更同步到 Node2 时，就向客户端返回了应答

client 发动向 Node2 的读操作

返回了旧值 v0（不统一）的后果

保障一致性

client 向 Node1 写入新值 v1

写入胜利 Node1 更新成 v1，此时不能立即向 client 返回应答，而是须要将 v1 同步到 Node2

同步 v1 胜利

此时能力向 client 返回应答

如果此时 client 再去拜访 Node2，不会呈现不统一的状况

保 CP 失 A

当产生了网络分区，Node1 与 Node2 曾经失去了分割，这时仍想对外提供服务（保 P）

client 向 Node1 写入新值 v1

写入 Node1 胜利，但无奈同步至 Node2

这时为了保障一致性，Node1 不能向 client 返回应答，造成操作挂起无奈实现（失去可用性）

保 AP 失 C

当产生了网络分区，Node1 与 Node2 曾经失去了分割，这时仍想对外提供服务（保 P）

client 向 Node1 写入新值 v1

写入 Node1 胜利，但无奈同步至 Node2

为了保障可用性，向 client 返回了应答（但就义了一致性）

一致性级别

CP 和 AP 之间须要做衡量，其实依据需要不同，也能够将一致性划分成几个级别，在这些级别里做一个衡量。

强一致性：零碎写入什么，读出来的也会是什么，但实现起来往往对性能影响较大，例如之前 CP 的例子
- 例如：火车站售票，有就是有，没有就是没有，不能呈现不统一的状况
- 典型算法：Paxos、Raft、ZAB
弱一致性：零碎写入胜利后，不承诺立即能够读到写入的值，也不承诺具体多久后数据能达到统一，还能够细分为：
- 会话一致性，同一个客户端会话中能够保障统一，其它会话不能保障
- 用户一致性，同一个用户中能够保障统一，其它用户不能保障
- 例如：网上购物，在商品详情页看到库存量还有好多，下单的霎时才被提醒“库存量有余”，实际上商品详情页展现的库存并不是最新的数据，只是在某个流程上才会做精确的查看
最终一致性：是弱一致性的特例，保障在肯定工夫内，可能达到一个统一的状态
- 例如：转账，转账实现后，会有一个提醒，您的转账会在 24 小时内到账，个别用户也能承受，但最终必须是统一的
- 典型协定：Gossip

BASE 是 Basically Available (根本可用)，Soft state (软状态) 和 Eventually consistent(最终一致性) 三个短语的简写，是由来自 eBay 的架构师 Dan Pritchet 在其文章 BASE An Acid Alternative 中提出的。
BASE 是对 CAP 中一致性和可用性衡量的后果，其来源于对大规模互联网零碎分布式实际的总结，是基于 CAP 定理逐渐演变而来
consistency)，但每个利用都能够依据的，其核心思想是即便无奈做到强一致性(Strong 本身的业务特点，采纳适当的形式来使零碎达到最终一致性(Eventualconsistency)。

Basically Available (根本可用)
是指分布式系统呈现不可预知故障的时候，容许损失局部可用性——但绝不等价于零碎不可用。以下举例说明
- 响应工夫上的失落：失常状况下，一个搜索引擎须要在 0.5s 之内返回给用户，但因为故障（机房断电或断网故障），查问响应工夫减少到了 1~2s
Soft state (软状态)

弱状态也称为软状态，和硬状态绝对，是指容许零碎中的数据存在中间状态，并认为该中间状态的存在不会影响零碎的整体可用性，即容许零碎在不同节点的数据正本之间进行数据同步的过程存在延时
Eventually consistent(最终一致性)

最终一致性强调的是零碎中所有的数据正本，在通过一段时间的同步后，最终可能达到一个统一的状态。因而，最终一致性的实质是须要零碎保障最终数据可能达到统一，而不须要实时保证系统数据的强一致性。

问题提出

集群中有 N 个节点，如果一个节点写入后要求同步到残余 N-1 个节点后再向客户端返回 ok，尽管看起来最保险，但其中任意一个节点同步失败，势必造成整个集群不可用，是否在此基础上略微进步可用性呢？

答案是 （写）多数派，集群节点设置为奇数，同步超过集群中 N/2 个节点胜利，则向客户端返回 ok，但存在程序性问题，如 3 形容
多数派写操作胜利后的读一致性暂不思考，思考下图中的两项操作，都满足了多数派通过，但 S3 这台服务器并没有与 S1，S2 达成统一，要 达到多数派外部一致性

Paxos

Paxos 是一种共识算法，目标是解决之前提到的写多数派时的程序性问题

Paxos 角色划分：集群中的每个节点都能够充当

Proposer：负责生成提案
- 留神：Paxos 算法容许有多个 Proposer 同时提案，但可能会引起活锁问题
Acceptor：负责批准提案
- Acceptor 如果只有一个的话，存在单点问题，因而该当有多个
Learner：负责获取提案，Acceptor 批准提案后，会将提案发送给所有 Learner

执行一个批改操作，不是一上来就能执行，分成两个阶段：

筹备阶段：Proposer 负责接管 client 申请并产生提案，必须由多数派 Acceptor 批准通过提案
承受阶段：提案通过后，再将要执行的批改操作播送给 Acceptor，这次依然多数派通过，此批改能力失效，能够返回响应给客户端

算法要点：

整个算法分成两个阶段：准备阶段，前两个箭头，承受阶段，后两个箭头。
- 准备阶段的目标是：第一拦挡掉旧的提案，第二找到最新的 acceptValue
对于 Proposer
- 准备阶段只发送 提案号 ，承受阶段发送 提案号 + 值
- 提案号 n 惟一且全局递增，大的 提案号 有更高优先级
- 如果见到最新 已承受值，就会替换掉 Proposer 本人原来的值，保障一致性
对于 Acceptor 会长久化以下信息
- minN（最小提案号），会在准备阶段和承受阶段被更新为更大提案号，会用来决定 Proposer 是否能选中提案
- acceptN（已承受提案号）和 acceptValue（已承受值），会在承受阶段被更新，如果 minN > n 则不会更新

例 1

P 播送提案号 1
有 3 个 A 接到提案，此时满足 n > minN，将 minN 更新为 1
3 个 A 胜利返回，P 收到的应答过半，但没有遇到更大的 acceptNo 和 acceptValue，因而应用本人的 value X
P 播送提案号和值 1:X
3 个 A 接到提案号和值，更新状态，返回 minN 值 1 给 P
P 收到过半应答，并查看发现没有呈现 minN > 1，便选中提案值 X

例 2

S1 播送提案号 1，想把值更新为 X
S5 播送提案号 2，想把值更新为 Y
S1、S2、S3 曾经经验了 Accept 阶段并选中值 X
关键点，S3 也接到了 S5 的 prepare 提案，这时是否会有不统一的状况呢？
此时 S3 状态已将 acceptN 和 acceptValue 别离更新为 1:X；再返回 S5 的 ack 时就会将 1:X 返回给 S5
S5 用返回的 X 替换掉了本人原有的值 Y，并执行后续流程，后续都会同步为 X

例 3

S1 播送提案号 1，想把值更新为 X
S5 播送提案号 2，想把值更新为 Y
S1、S2、S3 曾经经验了 Accept 阶段，与例 2 不同的是，值 X 还未选中
关键点，S3 也接到了 S5 的 prepare 提案，这时是否会有不统一的状况呢？
此时 S3 状态将 acceptN 和 acceptValue 别离更新为 1:X；再返回 S5 的 ack 时就会将 1:X 返回给 S5
S5 用返回的 X 替换掉了本人原有的值 Y，并执行后续流程，后续都会同步为 X

例 4

S1 播送提案号 1，想把值更新为 X
S5 播送提案号 2，想把值更新为 Y
关键点，S3 还未经验 Accept 阶段时，就拿到了 S5 的 prepare 提案，这时是否会有不统一的状况呢？
S3 在接到 S1 的 accept 申请时，n>=minN 条件不成立，因而没有更新 acceptN 和 acceptValue，并且返回的 minN 是 2
对 S1 来说，S3 返回的 minN 大于 n，选中失败；想更新 X 须要发动新一轮提案
对 S5 来说，accept 阶段发送的是它本人的 2:Y，后续会把值同步为 Y

例 5

回顾最早提到的程序性问题，看 Paxos 是否解决它

下图演示了 Paxos 是如何解决程序性问题的，剖析步骤参考例 3

Paxos 毛病

效率较低，两轮操作只能选中一个值
难于了解
活锁问题

Paxos 是容许多个 Proposer 的，因而如果按上图所示运行，则后一个提案总会让后面提案选中失败，显然死循环

参考资料

https://www.youtube.com/watch?v=JEpsBg0AO6o&t=41s Raft 作者解说 Paxos

另一种共识算法，目标是比 Paxos 更易了解，Raft 正是为了摸索一种更易于了解的一致性算法而产生的。它的首要设计目标就是易于了解，所以在选主的抵触解决等形式上它都抉择了十分简单明了的解决方案

整个 Raft 算法合成为三局部：

Leader 选举

① 只有一个 Server 能作为 Leader

② 一旦此 Server 解体，选举新 Leader
执行操作，以日志复制为例（Log replication）

① 由 Leader 执行本人的日志记录

② 将日志复制到其它 Server，会笼罩掉不统一的局部

③ 多数派记录日志胜利，Leader 能力执行命令，向客户端返回后果
确保安全

① 保障日志记录的一致性

② 领有最新日志的 Server 能力成为 Leader

Leader 选举

Leader 会一直向选民发送 AppendEntries 申请，证实本人活着
选民收到 Leader AppendEntries 申请后会重置本人的 timeout 工夫

选民收不到 AppendEntries 申请超时后，转换角色为 候选者 ，并将任期加 1，发送 RequestVote 申请，推选本人

选民收到第一个 RequestVote，会向该 候选者 投一票，这样即便有多个 候选者 ，必定会选出一个 Leader，选票过半即入选，如果落选会变回选民

每一任期最多有一个 Leader，但也可能没有（选票都不过半的状况，须要再进行一轮投票，timeout 在 T~2T 间随机）
任期由各个 server 本人保护即可，无需全局保护，在超时后加 1，在接管到任意音讯时更新为更新的任期，遇到更旧的任期，视为谬误

执行操作（以日志复制为例）

客户端 发送命令至 Leader
Leader 将命令写入日志（S1 虚框），并向所有选民发送 AppendEntries 申请

多数派通过后，执行命令（即提交，S1 虚框变实），此时就能够向 客户端 返回后果

在后续的 AppendEntries 申请中告诉选民，选民执行命令（即提交，S2,S3,S4,S5 虚框变实）

如果选民挂了，则 Leader 会一直尝试，待到选民重启，会将其缺失的日志陆续补齐

确保安全

Leader 日志的完整性

Leader 被认为领有最残缺的日志
一旦 Leader 实现了某条命令提交，那么将来的 Leader 也必须存有该条命令提交信息
投票时，会将候选者最新的 <Term，Index> 随 RequestVote 申请发送，如果候选者的日志还没选民的新，则投否决票

图中 S2 如果超时，发动选举申请，其它服务器只会对它投否决票，因为它的 Index 比其它人都旧
图中 S5 如果超时，发动选举申请，其它服务器也不会选它，因为他的 Term 太旧

选民日志的一致性

以 Leader 为准，对选民的日志进行补充或笼罩
AppendEntries 申请发送时会携带最新的 <Term,Index,Command> 以及上一个的 <Term,Index>
如果选民发现上一个的 <Term,Index> 可能对应上则胜利，否则失败，持续携带更早的信息进行比对

图中 Leader 发送了 <3,4,Command> 和 <2,3> 给 follower，follower 发现 <2,3> 可能与以后最新日志对应，这时间接执行 <3,4,Command> 即可

图中 Leader 发送了 <3,4,Command> 和 <2,3> 给 follower，follower 发现 <2,3> 不能与以后最新日志对应，会恳求 Leader 发送更早日志

Leader 这次发送了 <3,4,Command>，<2,3,Command>，<1,2> 给 follower，follower 发现 <1,2> 可能与以后最新日志对应，这时补全 <3,4,Command>，<2,3,Command> 即可

参考资料

https://www.youtube.com/watch?v=vYp4LYbnnW8 Raft 作者解说 Raft

https://raft.github.io/ Raft 资源

https://raft.github.io/raftscope/index.html Raft 可视化

它是为了解决在服务器增、删时一般 hash 算法造成数据大量迁徙问题的

一般 hash 算法

假如有 3 台服务器，10 个 key 在服务器上的散布如下图所示

增加一台服务器后，数据分布变成下图，能够看到除了一个 key（高低色彩雷同的）以外，其它 key 都得迁徙

一致性 hash 算法

假如有 3 台服务器，10 个 key 在服务器上的散布如下图所示

增加一台服务器后，数据分布变成下图，发现仅有 3 个 key 须要迁徙（高低色彩不同的）

好了，本文就到这里了！如果感觉内容不错的话，心愿大家能够帮忙点赞转发一波，这是对我最大的激励，感激🙏🏻

材料获取👇 最初面就是支付暗号，公众号回复即可！

本文由 mdnice 多平台公布

关于后端:分布式理论和一致性算法详解

1、什么是分布式系统

2、分布式系统的特色

3、分布式环境的各种问题

4、分布式实践

1、CAP 定理

2、BASE 实践

5、分布式一致性算法

1、Paxos 算法

2、Raft 算法

3、一致性 Hash 算法