分布式算法路线图

Posted 2021-02-03 01:02:18 ‐ 4 min read

开发分布式系统最关键的是根据场景特点,选择合适的算法,在一致性和可用性之间折中

分布式算法的四度空间:

协议拜占庭容错一致性性能可用性
2PC(2阶段提交协议)强一致性
TCC最终一致性
Paxos强一致性
ZAB最终一致性
Raft强一致性
Gossip最终一致性
Quorum NWR强一致性
PBFTN/A
POWN/A

一致性

  • 强一致性:保证写操作完成后,任何后续访问都能读到更新后的值
  • 弱一致性:写操作完成后,系统不能保证后续访问都能读到更新后的值
  • 最终一致性:保证如果某个对象没有新的写操作了,最终所有后续访问都能读到相同的最近更新的值

强一致性是具有多种含义的。

首先,在埃里克·布鲁尔的猜想中,CAP 中的强一致性(也就是 C)是指 ACID 的 C,系统状态的一致性,而这种一致性,可以通过二阶段提交协议来实现。

其次,在 CAP 定理中,CAP 中的强一致性(也就是 C)是指原子一致性(也就是线性一致性)。其中,Paxos、Raft 能实现线性一致性,而 ZooKeeper 基于读性能的考虑,它通过 ZAB 协议提供的是最终一致性。

一般而言,在需要系统状态的一致性时,你可以考虑采用二阶段提交协议、TCC。在需要数据访问是的强一致性时,你可考虑 Raft 算法。在可用性优先的系统,你可以采用 Gossip 协议来实现最终一致性,并实现 Quorum NWR 来提供强一致性。

可用性

可用性强调的是服务可用

一般来讲,采用Gossip协议实现最终一致性的系统,可用性最高。其次是Paxos、ZAB、Raft、Quorum NWR、PBFT、POW,可以容忍一定数量节点故障

最后是二阶段提交协议、TCC,只有当所有节点都运行时,才能工作,可用性最低

性能

一般来讲,采用 Gossip 协议的 AP 型分布式系统,具备水平扩展能力,读写性能是最高的。其次是 Paxos 算法、ZAB 协议、Raft 算法,因为它们都是领导者模型,写性能受限于领导者,读性能取决于一致性实现。最后是二阶段提交协议和 TCC,因为在实现事务时,需要预留和锁定资源,性能相对低。

111