分布式系统是一个硬件或软件组成分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统
CAP理论告诉我们,一个分布式系统不可能同时满足一致性 (C:Consistency)、可用性(A: Availability) 和分区容错性 (P: Partition tolerance) 这三个基本需求,最多只能同时满足其中的两项。
CAP 定理:最多三选二,无法兼得,通常在 CP 或者 AP 之间做出选择
不一致的产生
保证一致性
保 CP 失 A
保 AP 失 C
一致性级别
CP 和 AP 之间需要做权衡,其实根据需求不同,也可以将一致性划分成几个级别,在这些级别里做一个权衡。
BASE是 Basically Available (基本可用), Soft state (软状态) 和Eventually consistent(最终一致性) 三个短语的简写,是由来自eBay的架构师Dan Pritchet在其文章BASE An Acid Alternative中提出的。 BASE是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于 CAP定理逐步演化而来 consistency),但每个应用都可以根据的,其核心思想是即使无法做到强一致性(Strong自身的业务特点,采用适当的方式来使系统达到最终一致性(Eventualconsistency)。
问题提出
image-20210902151020777
Paxos
Paxos 是一种共识算法,目的是解决之前提到的写多数派时的顺序性问题
Paxos 角色划分:集群中的每个节点都可以充当
执行一个修改操作,不是一上来就能执行,分成两个阶段:
image-20210902151606775
算法要点:
提案号
,接受阶段发送提案号 + 值
提案号
n 唯一且全局递增,大的提案号
有更高优先级已接受值
,就会替换掉 Proposer 自己原来的值,保证一致性例1
image-20210902152006734
例2
image-20210902152121752
例3
image-20210902152345674
例4
image-20210902152544031
例5
回顾最早提到的顺序性问题,看 Paxos 能否解决它
image-20210902152742816
下图演示了 Paxos 是如何解决顺序性问题的,分析步骤参考例3
image-20210902152753028
Paxos 缺点
image-20210902153136877
参考资料
另一种共识算法,目的是比 Paxos 更易理解,Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解,所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案
整个 Raft 算法分解为三部分:
Leader 选举
image-20230627091942873
image-20230627091949621
image-20230627091955888
执行操作(以日志复制为例)
image-20230627092005987
image-20230627092011961
image-20230627092018983
确保安全
Leader 日志的完整性
<Term,Index>
随 RequestVote 请求发送,如果候选者的日志还没选民的新,则投否决票image-20230627092026251
选民日志的一致性
<Term,Index,Command>
以及上一个的 <Term,Index>
<Term,Index>
能够对应上则成功,否则失败,继续携带更早的信息进行比对image-20230627092032627
<3,4,Command>
和 <2,3>
给 follower,follower 发现 <2,3>
能够与当前最新日志对应,这时直接执行 <3,4,Command>
即可image-20230627092040603
<3,4,Command>
和 <2,3>
给 follower,follower 发现 <2,3>
不能与当前最新日志对应,会央求 Leader 发送更早日志<3,4,Command>
, <2,3,Command>
,<1,2>
给 follower,follower 发现 <1,2>
能够与当前最新日志对应,这时补全 <3,4,Command>
, <2,3,Command>
即可参考资料
它是为了解决在服务器增、删时普通 hash 算法造成数据大量迁移问题的
普通 hash 算法
image-20230627092052703
image-20230627092105234
一致性 hash 算法
image-20230627092112658
image-20230627092118400