常见分布式理论(CAP、BASE)和一致性算法(Gosssip、Raft)介绍
2022-01-18 15:07:34 
阿炯
一、CAP理论与BASE理论1、什么是 CAP 理论：
C：Consistency 一致性：指强一致性，分布式系统中的所有节点在同一时刻具有同样的值、都是最新的数据副本，一致性保证了不管向哪台服务器写入数据，其他的服务器能实时同步数据。
A：Availability 可用性：部分结点宕机不影响整个集群对外提供服务，每次向未故障的节点发送请求，服务节点总能保证在有限的时间内处理完成并进行响应，从用户角度来看就是不会出现系统操作失败或者访问超时等问题，但是系统内部可能会出现网络延迟等问题。
P：Partition Tolerance 分区容错性：由于网络的问题错综复杂，如果某个节点因为网络等问题造成数据不一致，或者数据延迟很久才同步过来，虽然会影响部分节点数据的时效性，但是服务节点依然是可用的，分布式系统要能容忍这种情况的，也就是说，尽管网络上有部分消息丢失，但系统仍然可继续工作。
分布式系统中，CAP是无法同时满足的，只能满足CAP中的两种，因此在设计分布式架构时，必须做出取舍，而对于分布式系统，分区容忍性是基本要求，必须要满足，否则就失去了价值。因为是节点宕机和网络故障大概率事件，很难避免，而当出现这种情况时，不可能同时保持一致性和可用性，所以设计分布式系统，就是在一致性和可用性之间取一个平衡。
那为什么说在P满足的情况下，为什么说CA不能同时满足呢？我们来通过假设看一看，如果CA同时满足会怎么样：
(1)假设现在要求满足C(一致性)，那么就是说所有的节点在某一刻提供的数据都必须一致，我们知道在P的情况，是不可能保证的，要保证的话，就只能把其他节点全部干掉，比如禁止读写，那这其实就是和A是相悖的(某些节点虽然延迟，但是节点本身可用)
(2)假设现在要求满足A(可用性)，那么就是说只要节点本身没什么问题，就可以对外提供服务，哪怕有点数据延迟，很明显这肯定是和C相悖的。
2、一致性的类别：
CAP 是分布式事务处理的理论基础，在分布式事务的最终解决方案中一般选择牺牲一致性来换取可用性和分区容错性，但这里的 “牺牲一致性” 并不是完全放弃数据的一致性，而是放弃强一致性而换取弱一致性。一致性一般可以分为以下三种：
(1)强一致性：在任意时刻，所有节点中的数据是一样的，系统中的某个数据被成功更新后，后续任何对该数据的读取操作都将得到更新后的值。比如传统数据库的事务特性 ACID，就是追求强一致性模型。一个集群需要对外部提供强一致性，就务必会损耗可用性，只要集群内部某一台服务器的数据发生了改变，那么就需要等待集群内其他服务器的数据同步完成后，才能正常的对外提供服务。
(2)弱一致性：系统中的某个数据被更新后，后续对该数据的读取操作可能得到更新后的值，也可能是更改前的值，但即使过了不一致时间窗口后，后续对该数据的读取也不一定是最新值。
(3)最终一致性：是弱一致性的特殊形式，虽然不保证在任意时刻任意节点上的同一份数据都是相同的，但经过一段时间后，所有服务节点间的数据最终会达到一致的状态
弱一致性即使过了不一致时间窗口，后续的读取也不一定能保证一致，而最终一致性过了不一致窗口后，后续的读取一定保证一致。
3、什么是 BASE 理论：
BASE 理论是指，Basically Available(基本可用)、Soft-state(软状态)、Eventual Consistency(最终一致性)，是基于CAP定理演化而来，是对CAP中一致性和可用性权衡的结果。核心思想是即使无法做到强一致性，但每个业务根据自身的特点，采用适当的方式来使系统达到最终一致性。
BA 基本可用：指分布式系统在出现故障的时候，允许损失部分可用性，保证核心可用。但不等价于不可用。比如：搜索引擎0.5秒返回查询结果，但由于故障，2秒响应查询结果；网页访问过大时，部分用户提供降级服务等。
软状态：软状态是指允许系统存在中间状态，并且该中间状态不会影响系统整体可用性，即允许系统在不同节点间副本同步的时候存在延时。
最终一致性：系统中的所有数据副本经过一定时间后，最终能够达到一致的状态，不需要实时保证系统数据的强一致性。
很多时候我们并不要求数据的强一致性，而 BASE 通过牺牲强一致性来获得更好的可用性，所以 BASE 理论的适用性更广泛，比如更适合面向的是大型高可用可扩展的分布式系统
柔性事务和刚性事务：柔性事务满足BASE理论(基本可用，最终一致)，刚性事务满足ACID理论。
二、一致性协议
1、Gossip协议：
集群往往是由多个节点共同组成的，当一个节点加入集群或者一个节点从集群中下线的时候，都需要让集群中其他的节点知道，这样才能将数据信息分享给新节点而忽略下线节点。本站有关于分布式多副本一致性协议Paxos与Raft的介绍。
如上图，A、B、C节点之间可以互相传递消息，但是D节点在下线之后会被广播告诉其他存活节点。这样的广播协议就是今天要说Gossip协议，Gossip协议也叫Epidemic协议(流行病协议)，当一个消息到来时，通过Gossip协议就可以像病毒一样感染全部集群节点。Gossip的过程是由一个种子节点发起的，当一个种子节点有信息需要同步到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，所以不能保证某个时间点所有的节点都有该条消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。
Gossip协议的特点：
(1)Gossip协议是周期性散播消息，每隔一段时间传播一次
(2)被感染的节点，每次可以继续散播N个节点
(3)每次散播消息时，都会选择尚未发送过的节点进行散播，不会向发送的节点散播
(4)同一个节点可能会收到重复的消息，因为可能同时多个节点正好向它散播
(5)集群是去中心化的，节点之间都是平等的
(6)消息的散播不用等接收节点的 ack，即消息可能会丢失，但是最终应该会被感染
下面我们来看个例子：
① 种子节点是A ② A节点选择B、C节点进行散播 ③ C散播到D，B散播D和E，可以发现D收到两次 ④ D散播到F，最终整个网络都同步到了消息
Gossip有点类似图的广度优先遍历算法，一般用于网络拓扑结构信息的分享和维护，比如 Redis 集群中节点的运行状态就是使用 Gossip 协议进行传递的。
2、Raft一致性协议：
分布式协议的难点之一就是数据的一致性，当由多个节点组成的集群中只有一个节点收到数据，我们就算成功的话，风险太大，当要求所有节点都收到数据才响应成功，性能又太差，所以一般会在数据的安全和性能之间做个折中，只要保证绝大部分节点同步数据成功，我们就算成功。比较知名的一致性算法有Raft算法，被广泛应用于许多中间件中，接下来我们就看看Raft算法是实现分布式系统的不同节点间的数据一致性的，也就是说客户端发送请求到任何一个节点都能收到一致的返回，当一个节点出故障后，其他节点仍然能以已有的数据正常进行。
首先介绍下在Raft算法中，几种情况下每个节点对应的角色：
(1)Leader节点：同大多数分布式中的Leader节点一样，所有数据的变更都需要先经过Leader
(2)Follower节点：Leader节点的追随者，负责复制数据并且在选举时候投票的节点
(3)Candidate候选节点：参与选举的节点，就是Follower节点参与选举时会切换的角色
2.1、Leader 选举：
系统在刚开始的时候，所有节点都是Follower节点，这时都有机会参与选举，将自己变成Candidate，变成Candidate的节点会先投自己1票，同时告诉其它节点，让它们来投票，当拿到超过半数以上的投票时，当前Candidate就会变成Leader节点。但是如果每个Follower节点都变成Candidate那么就会陷入无限的死循环，于是每个Follower都一个定时器，并且定时器的时间是随机的，当某个Follower的定时器时间走完之后，会确认当前是否存在Leader节点，如果不存在再把自己变成Candidate。
① 由于A节点的定时器时间最短(10ms)，所以A会成为Candidate。
② A投自己一票，并告诉B、C来投票，B、C也投出自己的同意票后，A就会变成Leader节点，同时会记录是第M任。这个M是做版本校验的，比如一个编号是10的节点，收到了一个编号是9的节点的投票请求，那么就会拒绝这个请求。
在Leader节点选举出来以后，Leader节点会不断的发送心跳给其它Follower节点证明自己是活着的，其他Follower节点在收到心跳后会清空自己的定时器，并回复给Leader，因为此时没必要触发选举了。
如果Leader节点在某一刻挂了，那么Follower节点就不会收到心跳，因此在定时器到来时就会触发新一轮的选举，流程还是一样。但是如果恰巧两个Follower都变成了Candidate，并且都得到了同样的票数，那么此时就会陷入僵局，为了打破僵局，这时每个Candidate都会随机推迟一段时间再次请求投票，当然一般情况下，就是先来先得，优先跑完定时器的Candidate理论成为Leader的概率更大。
选举流程大致如上，接下来我们来看看数据日志的复制。
2.2、数据日志的复制：
当Leader节点收到客户端Client的请求变更时，会把变更记录到log中，然后Leader会将这个变更随着下一次的心跳通知给Follower节点，收到消息的Follower节点把变更同样写入日志中，然后回复Leader节点，当Leader收到大多数的回复后，就把变更写入自己的存储空间，同时回复client，并告诉Follower应用此log。至此，集群就变更达成了共识。
(1)正常情况下的日志复制：
① 一开始，Leader 和两个 Follower 都没有任何数据。
② 客户端发送请求给 Leader，储存数据 “sally”，Leader 先将数据写在本地日志，这时候数据状态还是 Uncommitted (还没最终确认，使用红色表示)
③ Leader 给两个 Follower 节点发送 AppendEntries 请求，数据在 Follower 上没有冲突，则将数据暂时写在本地日志，Follower 的数据也还是 Uncommitted
④ Follower 将数据写到本地后，返回 OK。Leader 收到后成功返回，只要收到的成功的返回数量超过半数 (包含Leader)，Leader 将数据 “sally” 的状态改成 Committed。( 这个时候 Leader 就可以返回给客户端了)
⑤ Leader 再次给 Follower 发送 AppendEntries 请求，收到请求后，Follower 将本地日志里 Uncommitted 数据改成 Committed。这样就完成了整个复制日志的过程，三个节点的数据是一致的
(2)Network Partition 网络分区情况下日志复制：
在 Network Partition 的情况下，部分节点之间没办法互相通信，Raft 也能保证这种情况下数据的一致性
① 一开始有 5 个节点处于同一网络状态下，如下图：
② Network Partition 将节点分成两边，一边有两个节点，一边三个节点：
③ 两个节点这边已经有 Leader 了，来自客户端的数据 “bob” 通过 Leader 同步到 Follower。
④ 只有两个节点，少于3个节点，所以 “bob” 的状态仍是 Uncommitted。所以在这里，服务器会返回错误给客户端。
⑤ 另外一个 Partition 有三个节点，进行重新选主。
⑥ 客户端数据 “tom” 发到新的 Leader2，并通过和上节网络状态下相似的过程，同步到另外两个 Follower；但因为这个 Partition 有3个节点，超过半数，所以数据 “tom” 都 Commit 了。
⑦ 网络状态恢复，5个节点再次处于同一个网络状态下。但是这里出现了数据冲突 “bob" 和 “tom"。
⑧ 三个节点的 Leader2 广播 AppendEntries。
⑨ 两个节点 Partition 的 Leader 自动降级为 Follower，因为这个 Partition 的数据 “bob” 没有 Commit，返回给客户端的是错误，客户端知道请求没有成功，所以 Follower 在收到 AppendEntries 请求时，可以把 “bob“ 删除，然后同步 ”tom”，通过这么一个过程，就完成了在 Network Partition 情况下的复制日志，保证了数据的一致性。
原作者：张维鹏
看完上面对部分业界有代理表的理论分析，再来看分布式系统可参考设计模式简介。
1、布隆过滤器
Bloom过滤器是一种节省空间的概率数据结构，用于测试元素是否为某集合的成员。它用于我们只需要检查元素是否属于对象的场景。
在BigTable(和Cassandra)中，任何读取操作都必须从组成Tablet的SSTable中读取。如果这些SSTable不在内存中，则读取操作可能最终会执行许多磁盘访问以便读取所需的SSTable。为了减少磁盘访问次数，BigTable 使用Bloom过滤器。
2、一致性哈希
一致的哈希允许您轻松扩展，从而允许以有效的方式复制数据，从而实现更好的可用性和容错能力。
通过对数据项的键进行哈希处理以产生其在环上的位置，然后顺时针遍历环以查找位置大于该项位置的第一个节点，将每个由键标识的数据项分配给节点。与节点关联的节点是数据项的位置。
一致散列的主要优点是增量稳定性；节点离开或到达集群仅影响其直接邻居，其他节点不受影响。
3、Quorum
在分布式环境中，quorum是在确认操作成功之前需要成功执行此分布式操作的最小服务器数。
Cassandra，为了确保数据一致性，每个写入请求都可以配置为仅当数据已写入至少一个quorum(或大多数)副本节点时才成功。
对于领导者选举，Chubby使用Paxos，它使用quorum来确保强大的一致性。
Dynamo 将写入复制到系统中其他节点的草率quorum，而不是像Paxos那样的严格多数quorum。所有读/写操作都在首选项列表中的第一个NN正常节点上执行，该节点可能并不总是在遍历一致哈希环时遇到的第一个NN节点。
4、领导者(Leader)和追随者(Follower)
为了在管理数据的系统中实现容错，需要在多个服务器上复制数据。在集群中选择一个服务器作为领导者。领导者负责代表整个集群做出决策，并将决策传播到所有其他服务器。
三到五个节点的集群，就像在实现共识的系统中一样，领导者选举可以在数据集群本身内实施，而不依赖于任何外部系统。领导者选举在服务器启动时进行。每个服务器在启动时都会启动领导者选举，并尝试选举领导者。除非选出领导者，否则系统不接受任何客户端请求。
5、心跳
心跳机制用于检测现有领导者是否失败，以便可以启动新的领导者选举。
6、Fencing
在领导者-追随者模式中，当领导者失败时，不可能确定领导者已停止工作。例如，慢速网络或网络分区可能会触发新的领导者选举，即使前一个领导者仍在运行并认为它仍然是活动的领导者。
屏蔽是指在以前处于活动状态的领导者周围设置围栏，使其无法访问集群资源，从而停止为任何读/写请求提供服务。使用以下两种技术：
资源屏蔽：系统会阻止以前处于活动状态的领导者访问执行基本任务所需的资源。
节点屏蔽：系统会阻止以前处于活动状态的领导者访问所有资源。执行此操作的常见方法是关闭节点电源或重置节点。
7、WAL(预写日志Write-ahead Log)
预写日志记录是解决操作系统中文件系统不一致的问题的高级解决方案。受数据库管理系统的启发，此方法首先将要执行的操作的摘要记入“日志”中，然后再将其实际写入磁盘。在发生崩溃的情况下，操作系统只需检查此日志并从中断的位置继续。
8、分段日志
将日志拆分为多个较小的文件，而不是单个大文件，以便于操作。
单个日志文件在启动时读取时可能会增长并成为性能瓶颈。较旧的日志会定期清理，并且很难对单个大文件执行清理操作。
单个日志拆分为多个段。日志文件在指定的大小限制后滚动。使用日志分段，需要有一种将逻辑日志偏移量(或日志序列号)映射到日志段文件的简单方法。
9、高水位线(High-Water mark)
跟踪领导者上的最后一个日志条目，该条目已成功复制到追随者的quorum。日志中此条目的索引称为高水位线索引。领导者仅公开到高水位线索引的数据。
Kafka：为了处理非可重复读取并确保数据一致性，Kafka broker会跟踪高水位线，这是特定分区的最大偏移量。使用者只能看到高水位线之前的消息。
10、租约(Lease)
租约就像一个锁，但即使客户端离开，它也能工作。客户端请求有限期限的租约，之后租约到期。如果客户端想要延长租约，它可以在租约到期之前续订租约。Chubby客户端与领导者保持有时限的会话租约。在此时间间隔内，领导者保证不会单方面终止会话。
11、Gossip协议
Gossip协议是点对点通信机制，其中节点定期交换有关自己和他们所知道的其他节点的状态信息。每个节点每秒启动一轮Gossip回合，以与另一个随机节点交换有关自己和其他节点的状态信息。
12、Phi 累计故障检测(Phi Accrual Failure Detection)
此算法使用历史检测信号信息使阈值自适应。通用的应计故障检测器不会判断服务器是否处于活动状态，而是输出有关服务器的可疑级别。Cassandra使用Phi应计故障检测器算法来确定群集中节点的状态。
13、脑裂
分布式系统具有两个或多个活动领导者的场景称为脑裂。
通过使用生成时钟(Generation Clock)可以解决脑裂问题，生成时钟只是一个单调递增的数字，用于指示服务器的生成。每次选出新领导者时，时钟数字(generation number)都会增加。这意味着，如果旧领导者的时钟数为“1”，则新领导人的时钟数将为“2”。此时钟号包含在从领导发送到其他节点的每个请求中。通过这种方式，节点现在可以通过简单地信任具有最高数字的领导者来轻松区分真正的领导者。
Kafka：为了处理脑裂(我们可以有多个active controller broker)，Kafka使用“纪元数”(Epoch number)，这只是一个单调增加的数字来表示服务器的代次(generation)。
HDFS：ZooKeeper用于确保任何时候只有一个NameNode处于活动状态。epoch编号作为每个事务ID的一部分进行维护，以反映NameNode的代次。
14、校验和(checksum)
在分布式系统中，在组件之间移动数据时，从节点获取的数据可能会损坏。计算校验和并将其与数据一起存储。
要计算校验和，请使用MD5、SHA-1、SHA-256或SHA-512等加密哈希函数。哈希函数获取输入数据并生成固定长度的字符串(包含字母和数字)；此字符串称为校验和。
当系统存储某些数据时，它会计算数据的校验和，并将校验和与数据一起存储。当客户端检索数据时，它会验证从服务器接收的数据是否与存储的校验和匹配。如果没有，则客户端可以选择从另一个副本检索该数据。
HDFS和Chubby将每个文件的校验和与数据一起存储。
15、CAP定理
CAP定理指出，分布式系统不可能同时提供以下所有三个理想属性：
一致性(C)、可用性(A)和分区容差(P)。根据CAP定理，任何分布式系统都需要从三个属性中选择两个。这三个选项是CA、CP和AP。
Dynamo：在CAP定理术语中，Dynamo属于AP系统的类别，旨在牺牲强一致性为代价实现高可用性。
BigTable：就CAP定理而言，BigTable是一个CP系统，即它具有严格一致的读取和写入。
16、PACELEC定理
PACELC定理指出，在复制数据的系统中：
如果有一个分区('P')，分布式系统可以在可用性和一致性(即'A'和'C')之间进行权衡。否则('E')，当系统在没有分区的情况下正常运行时，系统可以在延迟('L')和一致性('C')之间进行权衡。
定理(PAC)的第一部分与CAP定理相同，ELC是扩展。整个论点假设通过复制来保持高可用性。因此，当失败时，CAP定理占上风。但如果没有，仍然必须考虑复制系统的一致性和延迟之间的权衡。
17、提示交接(Hinted Handoff)
如果节点关闭，系统会保留它们错过的所有请求的提示(或注释)。故障节点恢复后，将根据存储的提示将请求转发给它们。
当节点关闭时，领导者会在本地磁盘上的文本文件中写入提示。此提示包含数据及其所属的节点信息。当领导者意识到它为其保留提示的节点已恢复时，它会将每个提示的写入请求转发到该节点。
18、读取时修复
在分布式系统中，数据跨多个节点复制，某些节点最终可能会拥有过时的数据。
在读取操作期间修复过时的数据，因为此时可以从多个节点读取数据以进行比较并找到具有过时数据的节点。此机制称为读取修复。一旦已知具有旧数据的节点，读取修复操作就会将较新版本的数据推送到具有较旧版本的节点。Cassandra和Dynamo使用“读取修复”将最新版本的数据推送到具有旧版本的节点。
19、默克尔树(Merkle Trees)
“读取修复”可在处理读取请求时消除冲突。但如果某个副本明显落后于其他副本，则可能需要很长时间才能解决冲突。副本可以包含大量数据。单纯地拆分整个范围来计算校验和进行比较并不是很可行；有太多的数据需要传输。相反，可以使用Merkle树来比较一个范围的副本。
Merkle树是哈希的二叉树，其中每个内部节点是其两个子节点的哈希，每个叶节点是原始数据一部分的哈希。
比较Merkle树在概念上很简单：
比较两个树的根哈希。
如果它们相等，请停止。
在左边和右边的孩子上递归检查。
为了实现反熵和在后台解决冲突，Dynamo使用Merkle树。
本部分分享的资料来自网络收集和整理，所有文字和图片版权归属于原作者所有，且仅代表作者个人观点。