6. 从 FLP 不可能到 CAP 和 PACELC

分布式系统的不稳定性

综合我们前几个章节的内容, 我们可以总结出分布式系统中的不稳定性主要源于以下几个方面:

故障模型 (Failure Model)

在这个模型中, 对节点和网络特性的定义如下:

节点(Nodes):
- 它们可以无限期地失败;
- 它们在恢复时不会丢失持久状态;
- 对任何特定的计算, 它们都没有时间限制;
网络(Network):
- 网络可以丢弃 drop 或延迟 latency 消息;
- 消息可能被无限期地延迟;
- 网络也可能对消息进行重新排序;

异步模型 (Asynchronous Model)

上述的故障模型被称为异步模型; 在该模型下, 核心挑战在于:

无法区分 Failure 与 Slow: 在一个异步模型中, 你通常无法区分失败(例如, 请求被丢弃或远程节点死亡)和极度缓慢(例如, 网络或节点速度很慢, 响应只是尚未到达);
No response 的含义: 缺少响应可能意味着请求被丢弃, 远程节点已死, 或响应被丢弃;但这也可能仅仅意味着网络或节点非常慢, 并且响应仍在路上;

也就是这些都 Not Distinguishable (无法区分);

FLP Impossibility Result

基于上面的 Async 模型的设定和讨论, 我们引出了一个结论: FLP Impossibility Result (FLP 不可能性结果):

在异步模型中, 如果哪怕只有一个进程可能失败, 学习分布式共识也是不可能的;这种不可能性迫使系统必须在安全性 Safety/Consistency (无限期等待答案) 和活性 Availability/Liveness (在不确定结果的情况下给出答案) 之间做出选择;

如果我们拿 paxos 举例, 其保证的是 安全性, 也就是在任何情况下不会产生不一样的结果
(因为 leader 唯一), 但是基于其 probablistic liveness 的性质, 其活性不可保证

但是现实工程需要确保这种同时保证安全性和活性, 所以就需要某种形式的同步性, 比如对网络延迟设置一个 时间限制, 超过时间限制就认为是节点 fail 了; 但是如果要确保 Linearizability, 那么就一定要确保 wait indefinitely.

CAP 定理

相比于 FLP 从学习分布式共识的角度来描述分布式系统中的不稳定性, 在应用界有非常著名的 CAP 理论从用户体验角度 (Service-Level Objectives, SLOs) 来描述分布式系统中的不稳定性, 并且强调了现实世界经常发生的 Network Partition 作为整个权衡机制的底座 (也就是讨论分布式系统一定要基于这个 Partition-Standable 的功能基石);

现代理论一般用 CAP 定理来描述分布式系统中的不稳定性和可用性平衡:

在一个分布式计算系统中, 无法同时满足以下三个属性: 一致性 (Consistency), 可用性 (Availability) 和分区容错性 (Partition-Tolerance)

一致性 (Consistency): 通常指线性一致性 (Linearizability), 即系统看起来像是由一个单一系统托管的, 所有的操作都以相同的顺序应用;
- 如果需要线性一致性, 副本只有在属于一个 多数派分区 时才能安全地响应读写请求;
- 如果想要保持线性一致性, 系统必须为某些事件 无限期地等待(例如, 提议者需要联系多数派);
可用性 (Availability): 每个请求都会在有限的时间内得到响应, 无论响应是成功还是失败;
分区容错性 (Partition-Tolerance): 系统必须在网络发生故障或分区的情况下继续正常运行;在分布式系统中, 网络分区是必然会发生的

由于网络分区是不可避免的, 实际中系统必须在 CP (一致性与分区容错性) 和 AP (可用性与分区容错性) 之间做出选择;

CP 策略: 以 线性一致性 为目标 (CP), 系统在发生分区时会牺牲可用性, 只有在属于多数派分区的副本才能安全响应;
AP 策略: 允许副本 始终响应 (AP), 但必须牺牲线性一致性;

PACELC

PACELC 是对 CAP 理论的扩展, 它认识到分布式系统中的权衡并不仅限于网络分区发生时 (Partition)

也就是要分类讨论是否发生了 Partition 的情形:

应用

说了这么多理论, 分布式系统最经典的(也是牢 Noble 最爱的)举例场景就是:

银行系统: 必须选择 CP 才能满足强 ACID 要求
社交媒体: 可以选择 AP 来提高可用性和响应速度