首页  思维导图  详情

分布式协议与算法实战

2021-06-18 14:25:07   1  举报





AI智能生成

分布式协议

架构

分布式

作者其他创作

大纲/内容

分布式协议与算法实战

理论

链路

分布式算法四度空间

拜占庭容错

拜占庭错误是莱斯利兰百特在《拜占庭将军问题》提出一个错误模型，描述了一个完全不可信的场景，除了存在故障的行为，还存在恶意行为，顾名思义，拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误了

非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，比如进程奔溃，服务器硬件故障等等。

一般而言，在可信环境（比如企业内网）中，系统具有故障容错能力就可以了，常见的算法有二阶段提交协议（2PC）、TCC（Try-Confirm-Cancel）、Paxos 算法、ZAB 协议、Raft 算法、Gossip 协议、Quorum NWR 算法。

而在不可信的环境（比如有人做恶）中，这时系统需要具备拜占庭容错能力，常见的拜占庭容错算法有 POW 算法、PBFT 算法。

一致性

分类

强一致性

保证写操作完成后，任何后续访问都能读到更新后的值

弱一致性：写操作完成后，系统不能保证后续的访问都能读到更新后的值。

最终一致性：保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。

首先，在埃里克·布鲁尔的猜想中，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，因为在实现事务时，需要预留和锁定资源，性能相对低。

拜占庭将军问题：最复杂的分布式容错模型

二忠一叛

故障行为

恶意行为

口信消息型拜占庭问题

n位将军，最多能容忍（n-1）/3位叛将

签名消息型拜占庭问题

通过签名防止信息篡改，来解决问题

拜占庭容错和非拜占庭容错

拜占庭容错算法：PBFT、PoW

POW

通过一定工作量证明你是好人