分布式一致性与共识算法（一）

是什么

从实现效果上来说，很多人或多或少都了解或者设计过具有强一致性的系统。但是，大部分人并不了解强一致性的系统是如何运作的，也不知道该怎么设计。老实说这确实很难，以至于计算机科学界有一类专门解决这种问题的算法 —— 共识算法。

ACID

就数据库来说，我们都知道要保证原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

• Atomicity（原子性）：一个事务（transaction）中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。
• Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设规则，这包含资料的精确度、串联性以及后续数据库可以自发性地完成预定的工作。
• Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括读未提交（Read uncommitted）、读提交（read committed）、可重复读（repeatable read）和串行化（Serializable）。
• Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

CAP

就分布式来说，也需要保证CAP：一致性，可用性，分区容错性
CAP 理论是 Eric Brewer 教授在 2000 年提出 的，是描述分布式一致性的三个维度，分别是指：

• 一致性（Consistency）
  每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后，所有的请求都可以读到其最新的值，这样的系统就被认为具有严格的一致性。
• 可用性（Availablity）
  任何一个没有发生故障的节点，会在合理的时间内返回一个正常的结果，也就是对于每一个请求总能够在有限时间内返回结果。
• 分区容忍性（Partition-torlerance）
  当节点间出现网络分区，照样可以提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。那么，什么是网络分区呢？分区是系统中可能发生的故障之一，可能有节点暂时无法提供服务：发生了像 长时间 GC、CPU 死循环、链接池耗尽或者是网络通信故障等问题。

组合

• CP 系统：一致且容忍分区的系统。更倾向于减少服务时间，而不是将不一致的数据提供出去。一些面向交易场景构建的 NewSQL 数据库倾向于这种策略，如 TiDB、阿里云 PolarDB、AWS Aurora 等。但是它们会生成自己的 A，也就是可用性很高。
• AP 系统：可用且具有分区容忍性的系统。它放宽了一致性要求，并允许在请求期间提供可能不一致的值。一般是列式存储，NoSQL 数据库会倾向于 AP，如 Apache Cassandra。但是它们会通过不同级别的一致性模式调整来提供高一致性方案。

CP 系统的场景实现思路是需要引入共识算法，需要大多数节点参与进来，才能保证一致性。如果要始终保持一致，那么在网络分区的情况下，部分节点可能不可用。

而 AP 系统只要一个副本就能启动，数据库会始终接受写入和读取服务。它可能最终会丢失数据或产生不一致的结果。这里可以使用客户端模式或 Session 模型，来提供一致性的解决方案。

一致性概念

• 严格一致性
  这只是理论模型，现实中无法实现。因为各种物理限制使分布式数据不可能一瞬间去同步这种变化。
• 线性一致性
  如 TiKV
• 顺序一致性
  如 Google Megastore 这类系统都是使用 Paxos 算法实现了顺序一致性。也就是说在 Megastore 内部，如果有一个数据更新，所有节点都会同步更新，且操作在各个节点上执行顺序是一致的。
• 因果一致性
  因果一致性典型案例就是 COPS 系统，它是基于 causal+一致性模型的 KV 数据库。它定义了 dependencies，操作了实现因果一致性。这对业务实现分布式数据因果关系很有帮助。另外在亚马逊 Dynamo 基于向量时钟，也实现了因果一致性。
• 最终一致性
  Gossip协议

共识

共识性描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。 在实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。

为什么需要共识算法

从实现效果上来说，很多人或多或少都了解或者设计过具有强一致性的系统。但是，大部分人并不了解强一致性的系统是如何运作的，也不知道该怎么设计。老实说这确实很难，以至于计算机科学界有一类专门解决这种问题的算法 —— 共识算法。

共识算法解决的是对某个提案（proposal）大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等。可以认为任何可以达成一致的信息都是一个提案。对于分布式系统来讲，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，state-machine replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。因此，系统中多个节点最关键的是对多个事件的顺序进行共识，即排序。

会如何发展

列举

Paxos算法

Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。 Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。
Paxos算法除了难懂之外，还难以实现。尽管如此，以下服务还是在生产环境中使用了Paxos算法和Paxos算法的修改版。

Google Chubby：分布式锁服务
Google Spanner：NewSQL
Ceph
Neo4j
Amazon Elastic Container Service

ZAB（Zookeeper Atomic Broadcast）协议

官网上最古老的版本是 27 October, 2008: release 3.0.0 available

---

Zookeeper 通过 Zab 协议保证分布式事务的最终一致性。
【1】Zab协议是为分布式协调服务 Zookeeper专门设计的，是 Zookeeper保证数据一致性的核心算法。Zab借鉴了 Paxos算法，但又不像 Paxos那样，是一种通用的分布式一致性算法。支持崩溃恢复 和 原子广播协议。
【2】在 Zookeeper中主要依赖 Zab协议来实现数据一致性，基于该协议，zk实现了一种主备模型（即 Leader和 Follower模型）的系统架构来保证集群中各副本之间数据的一致性。主备系统架构模型指只有一台客户端（Leader）负责处理外部的写事务请求，然后 Leader客户端将数据同步到其他 Follower节点。

Raft 算法

由斯坦福大学的 Diego Ongaro 和 John Ousterhout 在 2014 年提出，在证明了算法的正确性之外，还提供了相关实现及参考代码。
Raft算法的应用：
分布式KV系统，etcd
微服务基础设施，consul

参考引用

分布式系统的一致性与共识性
分布式一致性与共识算法简介
从 Paxos 到 Raft，分布式一致性算法解析
分布式一致性算法，你确定不了解一下
分布式一致性算法-Paxos、Raft、ZAB、Gossip