# Quorum机制与分布式一致性问题 By [Grivn](https://paragraph.com/@grivn) · 2022-05-31 --- > 本文将主要讨论Quorum机制与分布式一致性问题，并给出一般意义上Quorum相关数值的计算方式。 在有冗余数据的分布式存储系统当中，冗余数据对象会在不同的机器之间存放多份拷贝。但是在同一时刻，一个数据对象的多份拷贝只能用于读或者写。为了保持数据冗余与一致性，需要对应的投票机制进行维持。 WARO（Write-All-Read-One）是一种简单的副本控制协议。当请求向某副本执行写操作时，需要将全部副本更新成功，才意味着本次写操作完成，否则视为失败。此时，只需要读任何一个副本上的数据即可。WARO 让读操作变得简单，但是让写操作的可用性很低。对于写操作比较频繁的分布式系统，或者系统内存在不可用节点，该协议不能提供稳定的服务。 为了更广泛地适应实际系统要求，通过对于读写操作的折衷，可以在满足一致性要求的基础上设计特定的投票机制，即 Quorum 决议机制。该机制下，对于同一份数据对象的每一份拷贝，不会被超过两个访问对象读写，并且权衡读写时的集合大小要求。在一个分布式集群当中，每一份数据拷贝对象都被赋予了一票。假设系统中有 v 票，这就意味着一个数据对象有 v 份冗余拷贝；对于每一个读操作，获得的票数必须不小于最小读票数 r 才可以成功读取；对于每个写操作，获得的票数必须不小于最小写票数 w 才可以成功写入。为了维持集群一致性，首先需要满足 r+w>v ，即某个数据不会被同时读或写。其次需要满足 w>n/2 ，保证某个数据的冗余拷贝不可能同时被两个写请求修改。Quorum 机制无法保证强一致性，是一种用来保证数据冗余与最终一致性的投票方法。该机制被广泛应用在共识算法中，以满足各类分布式一致性问题的容错需求。 分布式一致性问题，最早在 1978 年由 Lamport 提出 。早期的的分布式一致性问题中，主要考虑宕机节点带来的影响。在 1982 年，Lamport 等人 又提出了著名的拜占庭将军问题，将节点主动的攻击行为，即拜占庭行为（出现拜占庭行为的节点被称作拜占庭节点）。拜占庭问题的引入，拓宽了分布式系统的容错类型，提升了分布式一致性问题的复杂程度。 为了达成分布式系统的一致性，需要采用共识算法来维护集群成员的状态。通常来说，共识算法需要满足三项基本性质 ，分别为一致性（agreement）、正确性（integrity）、最终确定性（termination）。一致性，要求所有的正确节点都获得相同的状态。正确性，决策的结果需要来自于正确节点的提案。最终确定性，要求决策在有限的时间内产生。这三项基本性质也可以概括为两项，即活性（liveness）与安全性（safety）。对于活性与安全性，有一种比较直观的描述方式：某个事件最终会发生，且这个最终会发生的事件合理 。活性指的就是最终确定性，意味着该系统最终总能获取某个状态。安全性指的是一致性与正确性，意味着处理的提案来自于正确节点，且正确节点最终状态总能一致。 在共识算法的运行当中，主要考虑的是并发写相关的问题，需要通过 Quorum 决议保证集群写的一致性。共识算法应用 Quorum 机制时，所需投票数 q根据不同的容错需要，取值范围也会不同，相应的节点总数与能够容纳最多错误节点数之间的关系也会不同。 假设集群中总共有 n个节点，最多出现 f个错误节点。如果错误节点只会出现宕机这种行为，任何节点不会主动发出错误消息。为了满足活性要求，需要容忍最多 f 个节点发生宕机，需满足 q ≤ n − f ；为了满足安全性要求，需要保证所有节点状态的一致性，因此需要满足 q > n/2 。如果错误节点不止会发生宕机，还有可能主动发送错误的消息，即可能出现拜占庭行为。这就意味着节点的响应不一定可靠，即使出现失败写入，拜占庭节点也可能做出写入成功的反馈。此时，集群内只有 n − f 个节点的状态可靠，当我们收集到 q个投票时，其中也只有 q − f个投票来自可靠的节点。为了满足活性要求，需要满足 q ≤ n − f 。为了满足安全性要求，需要保证状态可靠的节点之间不会发生分歧，即满足 q − f > (n − f)/2 ，也就是 q > (n + f)/2 。 由此，也可以获得节点总数与拜占庭节点之间的关系。由于存在 f个节点可能发生宕机，至少需要在收到 n − f条消息时进行响应，而对于收到的来自 n − f 个节点的消息，由于其中最多可能存在 f 条消息来自于不可靠的拜占庭节点，因此在一个能够容忍拜占庭错误的集群中，节点总数需要满足 n > 3f 。当节点总数为 3f + 1 时，达成一致性决议的最小投票要求即为 2f + 1 。 --- *Originally published on [Grivn](https://paragraph.com/@grivn/quorum)*