分布式一致性算法
2022-08-03 14:46:26 19 举报AI智能生成
一致性算法
作者其他创作
大纲/内容
理论
CAP
C强一致性
BASE
NWR
集群结构
中性化：星星结构
Basic Paxos
multi Paxos
去中心化
CRQS 链式复制
Gossip
日志复制
主从复制
mysql主从复制
基于语句的复制
存储和传输 效率高
需要重新执行，锁数据
有的改变可能不会记录
基于行的复制
更占空间
所有改变都会被复制，更安全
数据大的操作更花时间
混合复制
先基于语句复制，失败改用基于行的复制
无主复制
多主复制
机制
Quorum机制
读取节点个数>总节点个数-写入节点数
通常 R = N-W+1
通常 R = N-W+1
共5个副本，写入3个副本，
至少保证要读3个副本，才能读到新数据
至少保证要读3个副本，才能读到新数据
lense机制
一致性
事务一致性
2PC
3PC
canCommit
preCommit
doCommit
分布式共识算法
有主
Multi Paxos 思想
（引入leader和事先对日志项编号）
（引入leader和事先对日志项编号）
分类
单主
Raft（2013 Diego Ongaro 和 John Ousterhout）
应用：etcd
问题分解
Leader Election
String Leader只能有一个Leader
Log Replication
只从 Leader 传给 Follower
从不会覆盖自身本地日志中已经存在的条目
snapshot
多主
ZAB
ZK
multi-raft Group
应用：Cockroach，TiDB
在 CockroachDB 中，数据被分成不同的范围，每个范围都有自己的共识组。
思想
执行多个 Basic Paxos 实例，就一系列值达成共识
无主
Basic Paxos (1990 Lamport)
无主
无主
应用
MGR
开源软件
Chubby
LibPaxos
问题
活锁
提案依赖关系
只能就单个值达成协议
Gossip
理论
六度分割
传播方式
直接邮寄
反熵
谣言传播
Pow
分类
客户端侧的一致性
强一致性
通过任意一个节点都返回最新的数据
弱一致性
存在不一致窗口，可能为新，也可能为旧的
最终一致性
案例：DNS
保证
变体
因果一致性
读写一致性
会话一致性
单调读一致性
服务端侧的一致性
容错算法
非拜占庭容错算法
拜占庭容错
PBFT
只能防止少数人(n-1) / 3 作恶
只能防止少数人(n-1) / 3 作恶
领导者作恶
非领导者作恶
心跳检测
lease机制的心跳检测
避免出现误判时引入新的问题
普通心跳检测
误报警：普通的心跳机制是无协议和承诺约定的，所以它的检测结果可能不可靠
Paxos族群
multi-poxos
Disk Paxos
Cheap Paxos
Generalized Paxos
Stoppable Paxos
Mencius
Vertical Paxos
Classic Paxos
FastPaxos(2005)
epaxos
0 条评论
下一页
