分布式系统的核心问题

分布式系统是计算机科学中十分重要的一个研究领域。随着现代计算机集群规模的不断增长，所处理的数据量越来越大，同时对于性能、可靠性的要求越来越高，分布式系统相关技术已经变得越来越重要，起到的作用也越来越关键。

分布式系统中如何保证共识是个经典的技术问题，无论在学术上还是工程上都存在很高的研究价值。令人遗憾地是，理想的（各项指标均最优）解决方案并不存在。在现实各种约束条件下，往往需要通过牺牲掉某些需求，来设计出满足特定场景的协议。

实际上，工程领域中不少问题都不存在一劳永逸的通用解法；而实用的解决思路是，合理地在实际需求和条件限制之间进行灵活的取舍。

更新于 2025-03-18 15:26

一致性问题

一致性（consistency），早期也叫 agreement，是指对于分布式系统中的多个服务节点，给定一系列操作，在约定协议的保障下，试图使得它们对处理结果达成“某种程度”的认同。

分布式系统达成一致的过程，应该满足：

可终止性：一致的结果在有限时间内能完成；
约同性：不同节点最终完成决策的结果是相同的；
合法性：决策的结果必须是某个节点提出提案；

共识算法

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

一般地，把出现故障（crash 或 fail-stop，即不响应）但不会伪造信息的情况称为“非拜占庭错误”（non-byzantine fault）或“故障错误”（Crash Fault）；伪造信息恶意响应的情况称为“拜占庭错误”（Byzantine Fault），对应节点为拜占庭节点。

FLP 不可能原理

FLP 不可能原理：在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。

FLP 不可能原理实际上是告诉人们，不要浪费时间，去为异步分布式系统设计在任意场景下都能实现共识的算法。

虽然无法实现在任意场景下都能实现共识的算法，但可以通过设计，使得在特定场景下，能够实现共识。学术界做研究往往考虑的是数学和物理意义上最极端的情形，很多时候现实生活要美好的多！

Tip

科学告诉我们什么是不可能的；工程则告诉我们付出一些代价，可以把它变成可行。这就是科学和工程不同的魅力。

CAP 原理

Note

CAP 原理最早是 2000 年由 Eric Brewer 在 ACM 组织的一个研讨会上提出的猜想，后来 Lynch 等人进行了证明。原理被认为是分布式系统领域的重要原理之一。

CAP 原理: 分布式计算系统不可能同时确保以下三个特性：一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance），设计中往往需要弱化某个特性的保障。这里，一致性、可用性和分区容错性的含义如下：

一致性: 任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性;
可用性: 在有限时间内，任何非失败节点都能应答请求;
分区容错性: 网络可能发生分区，即节点之间的通信不可保障。

比较直观地理解如下，当网络可能出现分区的时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其他节点的确认而不应答（牺牲可用性），要么节点只能应答非一致的结果（牺牲一致性）。

由于大多数时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（多数场景下），要么牺牲掉可用性。

应用场景

既然 CAP 三种特性不可同时得到保障，则设计系统时必然要弱化对某个特性的支持。那么可能出现下面三个应用场景。

弱化一致性。对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才最终更新成功，期间不保证一致性。例如网站静态页面内容、实时性较弱的查询类数据库等，简单分布式同步协议如 Gossip，以及 CouchDB、Cassandra 数据库等，都是为此设计的。
弱化可用性。对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等是为此设计的。Paxos、Raft 等共识算法，主要处理这种情况。在 Paxos 类算法中，可能存在着无法提供可用结果的情形，同时允许少数节点离线。
弱化分区容错性。现实中，网络分区出现概率较小，但较难完全避免。两阶段的提交算法，某些关系型数据库及 ZooKeeper 主要考虑了这种设计。实践中，网络可以通过双通道等机制增强可靠性，达到高稳定的网络通信。

更新于 2025-03-18 16:17

ACID 原则

ACID 原则指的是: Atomicity (原子性)、Consistency (一致性)、Isolation (隔离性)、Durability (持久性)，用了四种特性的缩写。ACID 也是一种比较出名的描述一致性的原则，通常出现在分布式数据库领域。具体来说，ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

ACID 特征如下:

Atomicity: 每次操作是原子的，要么成功，要么不执行；
Consistency: 数据库的状态是一致的，无中间状态；
Isolation: 各种操作彼此之间互相不影响；
Durability: 状态的改变是持久的，不会失效。

与 ACID 相对的一个原则是 BASE（Basic Availability, Soft-state, Eventual Consistency）原则，牺牲掉对一致性的约束（但实现最终一致性），来换取一定的可用性。

Paxos 算法与 Raft 算法

Paxos 问题是指分布式的系统中存在故障（crash fault），但不存在恶意（corrupt）节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。这也是分布式共识领域最为常见的问题。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

更新于 2025-03-18 17:42

Paxos 算法

// TODO

Raft 算法