分布式算法概览

分布式协议和算法属于比较新的概念，发展也比较迅速，1989年莱斯利·兰伯特（Leslie Lamport）提出了Paxos，2006年，谷歌研发团队让Paxos在生产环境中落地，但是Paxos缺乏编程实现的必须细节，最终的算法实现仍是建立在一个未证明的算法之上。再后来，也就是到了2013，斯坦福大学的迭戈·安加罗（Diego Ongaro）和约翰·奥斯特霍德（John Ousterhout）提出了Raft。

拜占庭容错

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

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

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

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

分布式共识算法概览

算法拜占庭容错一致性性能可用性
2PC否强一致性低低
TCC否最终一致性低低
Paxos否强一致性中中
ZAB否最终一致性中中
Raft否强一致性中中
Gossip否最终一致性高高
Quorum NWR否强一致性中中
POW是N/A低中
PBFT是N/A低中

一致性

一致性可以分为三类：

  • 强一致性 写操作完成后，保证任何后续访问都能读到更新后的值。

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

  • 最终一致性 写操作完成后，经过一段时间后续访问都能读到更新后的值。

可用性

可用性说的是任意节点发生故障，均不影响其他节点提供服务，但是不能保证提供最新的数据。

性能

  • Gossip协议是AP模型，所以性能是最好的。

  • Paxos，ZAB， Raft这三个协议都是领导者模型，写性能受限于领导者，读性能取决于一致性实现，比如ZAB协议读性能就比较高。

  • 2PC，TCC协议需要预留一定的资源来实现一致性，性能是最差的。

CAP理论

CAP理论对分布式系统的特性做了高度抽象，形成了三个指标：

  • 一致性（Consistency）

  • 可用性（Availability）

  • 分区容错性（Partition Tolerance）

一致性指的是，写入成功后，如果客户端无论读哪个节点，获取的都是最新的节点数据。 可用性说的是任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据。 分区容错性则是指，当节点间出现任意数量的消息丢失或高延迟的时候，系统仍然在继续工作。

在一个系统中，CAP三者不能同时满足。

CAP模型

  • CA模型，在分布式系统中不存在。因为舍弃P，意味着舍弃分布式系统，就比如单机版关系型数据库MySQL，如果MySQL要考虑主备或集群部署时，它必须考虑P。

  • CP模型，采用CP模型的分布式系统，舍弃了可用性，一定会读到最新数据，不会读到旧数据。一旦因为消息丢失、延迟过高发生了网络分区，就影响用户的体验和业务的可用性（比如基于Raft的强一致性系统，此时可能无法执行读操作和写操作）。典型的应用是Etcd，Consul和Hbase。

  • AP模型，采用AP模型的分布式系统，舍弃了一致性，实现了服务的高可用。用户访问系统的时候，都能得到响应数据，不会出现响应错误，但会读到旧数据。典型应用就比如Cassandra和DynamoDB。

CAP模型强调在数据一致性（ACID）和服务可用性（BASE）之间权衡妥协，帮助我们思考如何设计系统，在一致性和可用性之间进行妥协折中，设计出满足场景特点的分布式系统。

ACID理论

  • ACID理论是对事务特性的抽象和总结，方便我们实现事务。

  • ACID理论重点是强调CAP中一致性。

2PC协议

  • 一旦参与者投票要求提交事务，那么就不允许放弃事务。

  • 在第二个阶段，事务的每个参与者执行最终统一的决定，提交事务或者放弃事务。这个约定，是为了实现ACID中的原子性。

TCC协议

  • TCC是Try（预留）、Confirm（确认）、Cancel（撤销） 3个操作的简称，它包含了预留、确认或撤销这2个阶段。

  • 核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作。

  • 需要入侵代码，实现复杂度高。

BASE理论

  • BASE理论属于CAP中的AP系统的延伸。

  • BASE理论的核心思想就是基本可用和最终一致性。

基本可用

保证基本可用的方式：流量削峰、延迟响应、体验降级、过载保护。

最终一致性

实现最终一致性的几种方式：

  • 以最新写入的数据为准。

  • 以第一次写入的数据为准。

数据修复的方式：

  • 读时修复

  • 写时修复

  • 异步修复 通过定时对账检测副本数据的一致性，并修复。