分布式的一致性问题的算法

 

在分布式系统中，一致性（consensus）问题，是指对于系统中的多个服务节点，给定一系列操作，在一致性协议保障下，试图使得它们对处理结果达成一致。

 

在实际的计算机系统中，存在如下问题：

• 节点间的网络通讯是不可靠的，包括任意延迟和内容故障；
• 节点的处理可能是错误的，甚至节点自身随时可能宕机；
• 同步调用会绕过系统变得不具备可扩展性；

一个分布式的一致性算法应该满足：

可终止性（Termination）：一致性的结果在有限的时间内能完成；

一致性（Consensus）：不同节点最终完成决策的结果应该相同；

合法性（Validity）：决策的结果必须是其他进程提出的提案；

 

绝对理想的一致性在分布式系统中很难达成，但可以使用带约束的一致性放宽要求：顺序一致性（Sequential Consistency）、线性一致性（Linearizability Consistency，依赖于全局时钟或锁）。

 

一致性的最坏界限在哪里呢？一般情况下，分布式系统的一致性问题无解。

FLP 不可能原理：在网络可靠，存在节点失效的最小化异步模型系统中，不存在一个可以解决的一致性问题的确定性算法。

三个人在不同房间进行电话沟通投票（投票结果是0或1），但经常会有人睡着。某刻A投票0，B投票1，C收到两人的投票时刚好睡着了，A和B则永远无法在有限时间内获知最终结果。若重新投票，类似情景都可能在取得结果前发生。

 

但在付出一些代价的情况下，我们能做到多少？

 

CAP原理：分布式系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition）。

一致性（Consistency）：任何操作都应该是原子的，发生在后面的事件能看到前面事件发生导致的结果；

可用性（Availablity）：在有限时间内，任何失败节点都能应答请求；

分区容忍性（Partition）：网络可能发生分区，即节点之间的通讯不可保障。

 

当网络不可靠时，系统要么牺牲掉一致性（过一段时间后更新结果，期间不保证一致性），要么牺牲掉可用性（系统故障时拒绝服务，如Paxos、Raft等算法），要么不保证分区容忍性（通过双通道等机制增强可靠性，达到高稳定网络）。既然CAP 不可同时满足，则在设计系统时必然要弱化对某个特性的支持。

 

ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。

Atomicity（原子性）：每次操作都是原子的，要么成功，要么不执行；

Consistency（一致性）：数据库的状态是一致的，无中间状态；

Isolation（隔离性）：各种操作彼此互相不影响；

Durability（持久性）：状态的改变是持久的，不会失效；

 

一个与之相对的原则是 BASE（Basic Availiability，Soft state，Eventually Consistency），牺牲掉对一致性的约束，来换取一定的可用性。

 

Paxos 问题

Paxos 问题是指分布式的系统中存在故障，但不存在恶意节点（无伪造消息，但可能丢失或重复）场景下的一致性问题。

Paxos 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。它们通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。

Paxos 一致性算法，基于两阶段提交并进行扩展，在工程角度实现了一种最大化保障一致性（存在极小概率无法实现一致性）的机制，广泛应用在 Chubby、Zookeeper系统中。

算法中将节点分为三种类型，并满足三点约束要求：proposer（提出一个提案，等待大家批准为结案）、acceptor（负责对提案进行投票）、learner（被告知结案结果，并与之统一，不参与投票过程）。决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；再一次执行实例中，只批准（chosen）一个最终决议；learners 智能获得被批准的决议。

基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。proposer 在此过程中出现故障，可以通过超时机制来解决。若每一轮新的提案 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。

Poxos 能保证在超过一半的正常节点存在时，系统能达成一致。

 

 

若系统中限定只有某个特定节点是提案者，则一致性肯定能达成，要么达成，要么失败（提案者故障，系统无法工作）。

 

若存在多个提案者，问题就变得复杂了。

 

一种情况是同一时间片段（一个提案周期）内只有一个提案者。需要设计一种机制来保障提案者的正确产生，如按照时间、序列、或者比较之类。实际是非常难的。

另一种情况是允许同一时间片段可以出现两个提案者。那同一个节点可能收到两份提案，节点根据提案序号来判断接受哪个。如何为提案分配序号呢？一种可能的方案是每个节点的提案数字区间彼此隔离开，互不冲突。为了满足递增的需求可以配合用时间戳作为高位字段。

 

两阶段的提交：

提案者发出提案后，收到一些反馈，此时得知的结果是自己的提案被大多数接受了，或者没被接受。即便受到来自大多数的接受反馈，也不能认为最终确认了。

因此引入一个新的阶段（commit 阶段），提案者在前一阶段（prepare阶段）拿到所有反馈后，需要判断和确认该提案是否为可能被大多数接受的提案。

准备阶段，多个提案者可以发送提案：<id, value>, 接收者收到提案就返回收到消息，并只保留最新提案，若收到一个请求的提案号比目前保留的小，则返回保留的提案给提案者，告诉他已经有人发出更新的提案了。

提交阶段，若一个提案者在准备阶段收到大多数的回复（表示大部分人听到它的请求，可能做好了最终确认的准备啦），则再次发出确认消息。若再次收到大多数的回复，并且大家都返回空，则带上原来的提案号和内容；若返回中有更新的提案，则替换提案值为更新提案的值。若没有收到足够多的回复，则需要再次发出请求。接受者若发现该提案号跟自己目前保留的一致，则确认该提案。

 

 

Raft 问题

Raft 是对 Paxos 的重新设计和实现，是Paxos 算法的一种简化实现。包括三种角色：leader、candiate 和 follower。

Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选举为 leader；

同步 Log：leader 会找到系统中各种事件发生记录的 log 最新记录，并强制所有 follower 来刷新到这个记录；

 

 

拜占庭问题与算法

 

拜占庭问题讨论的是允许少数点作恶（消息可能被伪造）场景下的一致性达成问题（最坏情况下的保障）。

假设只有3个人，A、B、C，三人中如果其中一个是叛徒。当A发出进攻命令时，B如果是叛徒，他可能告诉C，他收到的是“撤退”的命令。这时C收到一个“进攻”，一个“撤退“，于是C被信息迷惑，而无所适从。

如果A是叛徒。他告诉B“进攻”，告诉C“撤退”。当C告诉B，他收到“撤退”命令时，B由于收到了司令“进攻”的命令，而无法与C保持一致。

正由于上述原因，在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于1/3，拜占庭问题便不可解。

面向拜占庭问题的容错算法 （Byzantine Fault Tolerant，BFT 算法），解决的是网络通讯的可靠，但节点可能故障情况下的一致性达成。

PBFT 算法是第一个得到广泛应用的 BFT 算法，包括三个阶段来达成共识：Pre-Prepare、Prepare 和 commit。

 

解决思路：

比特币的区块链网络在设计时提出了 PoW（Proof of work）算法思路。一个是限制一段时间内整个网络中出现提案的个数，另一个是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率上存在的，即时有人试图破坏，需要付出超过系统一半算力的代价。各个系列的 PoX 算法都是采用经济上的惩罚来制约破坏者。

 

可靠性指标

一般来说，单点服务器系统至少能满足两个九（99%）概率可靠性，企业信息系统三个九（99.9%），互联网系统能达到四个九（99.99%）已经是业内领先水平，电信级应用一般能达到五个九（99.999%）。该如何提高可靠性呢？

一是让单点系统变得更可靠，通过替换单点的软硬件来改善可靠性。

二是消灭单点，通过主从、多活等模式让多个节点集体完成原先单点的工作。