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