分布式系统探幽-建模与挑战

(Updated: )
分布式系统

分布式系统建立在不可靠的网络和不可靠的物理节点上，为了容错，我们必须使用复制， 而复制既是一切的解决方案，也是问题与挑战的来源(一致性)。

本文只讨论分布式系统的假设、强一致性与共识；复制以及一致性的选择是和系统设计目标紧密相关的，结合具体系统讨论才有价值。写得有点干巴，但为了内容完整，写就完了。

分布式系统的假设

此处讨论的分布式系统是无共享架构，即系统通过网络消息通信来获取彼此的状态信息。
在详细展开前，我们不得不对网络、消息语义以及节点故障引入乏味的学术分类(提取自深入理解分布式系统)。
**网络链路模型(双向)**：

  1. 可靠链路：可靠传递，无重复，不会无中生有
  2. 公平损失链路：消息可能会丢失、重复或排序，但会到达。
    1. 公平损失：发送方和接收方都正常运行，发送方重复发送，消息最终会到达
    2. 有限重复
    3. 不会无中生有
  3. 任意链路：允许任意链路执行任意操作

TCP是可靠链路；
公平损失链路+重发+接收端过滤重复 = 可靠链路
任意链路+加密技术（TLS）= 公平损失链路

节点故障类型：

  1. 崩溃-停止(fail-stop)
  2. 崩溃-恢复(fail-recovery)
  3. 拜占庭故障：故障节点可能以任意方式偏离算法，破坏系统

时间划分类型：

  1. 同步：消息响应时间有限且已知
  2. 异步：消息响应时间无限，无法知道消息什么时候会到达
  3. 部分同步：系统大部分时间同步，偶尔因为故障转变为异步

幂等操作:多次操作产生相同结果且无额外影响
消息传递语义：描述消息传递和处理次数

  1. 最多一次：最多传递一次，消息可能丢失但不会重复
  2. 至少一次：消息不会消失但在故障时可能重复
  3. 精确一次：有且仅有一次，不丢失不重复
    网络，消息语义与节点故障

常用且合理的假设是：

  1. 部分同步网络，建立在公平损失链路之上
  2. 节点会随机出现非拜占庭故障：fail-stop/fail-recovery
  3. 消息会被至少传递一次
  4. 系统需要正确处理过期消息和重复消息(确保操作幂等)

线性一致性

理论

分布式系统中的一致性指的是节点的写入被其他节点看到的顺序保障（数据的新鲜度问题，能够容忍读取什么样的数据）；

强一致性指的是线性一致性(Linearizability)，线性一致性可以确保一组节点组成的分布式系统对外表现地像一个系统一样。
一旦一个客户端成功完成写入，所有从数据库读取的客户端都必须能够看到刚刚写入的值。
维护单一数据副本的假象，意味着要保证读取到的是最新值，而不是来自过时的缓存或副本

最直觉的理解方式是， 将各个节点(客户端)的请求按照时间顺序排列，请求开始/发出时称为Invoke,收到响应称为Return; 在这个过程中，写入操作在某个时间点CAS原子地更改系统状态，在这个时间点之后处理的读操作读到最新值，否则读到旧值；同一个时间点只会发生一个写操作，在这个写操作原子更新时，不会发生其他写入(系统保证)。
linearizability

微妙的地方在于如果读请求和写请求并发，那么它可能读取到更新前的值或者更新后的值，线性一致性保证操作可以在全局时间中排成一条线，但它无法给出一个具体的，预先计算的顺序，我们得到的不过是众多请求执行顺序的一种

验证线性一致性

显然，验证的方式就是将客户端的请求进行排序，排序后的执行结果对应每次请求得到的响应，只要找到一种这样的顺序便可以验证。
由前文((5 封私信) 分布式系统探幽-时间与顺序 - 知乎)可知，请求之间要么具有happened before关系，要么是并发的，对于具有happened before关系的请求，需要保证执行顺序，对于并发请求，可以任意安排顺序，但是如果不满足实际得到的响应，需要进行回溯。
这就是WG算法的思路，本质是深度优先遍历，找到一条合法路径即停止，因此虚线路径不会被执行。
WG
对于WG算法，有两个常见优化：

  1. WGL：缓存 + 剪枝。缓存当前系统的值和待执行操作的响应值，如果两者一致，那么相同配置下后续搜索过程相同，因此可以跳过
  2. P-compositionality: 分治。核心思想是，如果一个调用序列的所有子序列都满足线性一致性，那么该序列肯定满足线性一致性。因此我们可以将互不相关的命名空间拆分，独立进行线性一致性验证
    常用的验证线性一致性工具：
  3. Knossos，基于Clojure实现的WGL；
  4. Porcupine，基于Go实现的P-compositionality； 被etcd-raft用作验证器

共识

共识算法是一种让多个节点在容忍部分系统故障的前提下，对某个值或者连续的值达成一致的算法，通常用于实现强一致性分布式系统。一般不讨论容忍拜占庭错误的共识算法（区块链使用，节点会发送恶意信息）
此处的值意义广泛，可以是一个整型，可以是一对KV，可以是一条日志，可以是一个操作。

共识具有如下性质：

  1. 活性
    • 终止性: 所有正确的进程最终都会认同某个值
  2. 安全性
    • 协定性: 所有正确的进程认同的都是同一个值
    • 有效性: 如果正确的进程都提议同一个值v,那么任何正确进程最终决定的值一定是v
    • 完整性: 正确进程如果决定了一个值，那就不能在本轮共识过程修改

活性要求节点必须推动系统状态变化，即使有部分节点崩溃，也需要做出决定。
安全性则保障系统处于一致的状态。
系统的容错是有限度的，奇数个节点可以容忍n/2个节点故障(向下取整)，在活跃节点无法满足多数时，共识算法会放弃活性来保障安全性。

FLP

FLP定理推导出了共识算法的上限，没有完美的共识算法

FLP定理通常被表述为：异步网络下不存在确定性且可以容错的共识算法。为什么说FLP定理推导出共识算法的上限呢？因为强的共识算法(成立条件更普遍，容错能力更高)显然可以用于实现/替换弱的共识算法，如果连弱的共识算法都无法成立，显然也推导/设计不出强共识算法。

上文提到通常假设网络为部分同步网络，一旦出现网络故障，那么消息传递时延失去上限，这种情况下，部分同步网络
转换为了异步网络，由FLP定理可知，共识算法的活性和安全性无法同时得到保证。

FLP定理从直觉上来理解分为两步：

  1. 系统存在悬而未决/二义的状态，该状态下处理不同的输入序列会走向不同的结果(决定不同的值)
  2. 系统可能始终保持悬而未决的状态

定理一可以这样理解：
假设每个节点存在如下的局部投票数组，数组中的值要么是0,要么是1，只能通过消息通信获取其他节点的决定，共识算法停止时，每个节点的投票数组票型一致，一致的决定一个值。局部投票数组的组合叫做配置。

1
2
[0,0,0,0,0] → [1,0,0,0,0] → [1,1,0,0,0] → [1,1,1,0,0] -> [1,1,1,1,0] → [1,1,1,1,1]
 决定0          决定0          决定0         决定1           决定1         决定1

从决定0到决定1的过程，一定会出现翻转，如果系统最终处于[1,1,1,0,0]状态，但是决定1的某个进程在发送决定1的消息前崩溃了，由于其他节点无法确定它是死了，还是慢了，因此会一直等待，系统一直无法达成共识（违背活性）

超时是随机性算法

定理二采用反证法，假设可以从二义状态经过任意调度走向单值态，但证明存在某些调度，使得矛盾，因此得到系统可以一直处于悬而未决状态。
假设系统每次只处理一个事件，一个配置接收事件后转换到新的配置。固定关键事件e,暂时不执行它，执行一段调度后得到：

1
C0 → C1 → C2 → C3 → ... → Ck

其中有

1
Ci --fi--> Ci+1

现在在每个配置后补上同一个事件 e：

1
2
3
4
5
C0 --e--> ?
C1 --e--> ?
C2 --e--> ?
...
Ck --e--> ?

假设没有任何一个结果是双价，那么它们都只能是 0 价或 1 价。
由于原配置是双价，可以构造出既有 0 价结果，也有 1 价结果，因此序列中必然存在一次翻转：

1
2
Ci   --e--> 0 价
Ci+1 --e--> 1 价

又因为：

1
Ci --fi--> Ci+1

于是有：

1
2
3
4
5
6
7
                    e
Ci  --------------------------------> 0 价
|
| fi
↓
Ci+1 -------------------------------> 1 价
                    e

若 e 和 fi 发生在不同进程，则它们可交换：

1
fi(e(Ci)) = e(fi(Ci))

所以两条路径到达同一配置。但是从 0 价配置继续执行 fi，仍然必须是 0 价；另一条路径又要求同一配置是 1 价。两者矛盾。
因此必然存在某个 Ci：

1
Ci --e--> 双价

初始配置 + 一组事件调度 可以理解为 一次共识执行；在FLP的前提条件下，系统可以在某些时候达成共识，但它无法总是达成共识。

CAP

CAP的经典表述是一致性，可用性，网络分区是不可能三角，最多满足其二。但是这个说法并不准确，因为一致和可用是系统对外保障而网络分区是一种故障。并且一致性是一个模糊的词语，AP系统(dynamo)提供的通常是最终一致性。CAP的一致性理解为强一致性。

更准确的说法是，在发生网络分区故障时，系统要么保障强一致性(少数派节点无法运行)，要么保障高可用性(所有节点正常运行)。
由于网络分区只是众多故障的一种(谷歌统计，约占数据中心的8%),因此CAP的精确描述范围其实非常狭窄。

PACELC

PACELC是对CAP定理的推广：

  • P(网络分区)时系统要在可用(A)和强一致(C)中二选一
  • E(否则)，系统要在延迟(L)和强一致(C)二选一

由此可见，强一致还是尽可能用到最必要的地方吧，不然既没有常态的低延迟也没有分区下的高可用！

参考文献

  1. 设计数据密集型应用（第二版）
  2. Distributed systems for fun and profit
  3. 深入理解分布式系统 (豆瓣)
  4. FLP.pdf
  5. 18-distributed-systems-flp.pdf图解FLP证明
  6. FLP and CAP aren’t the same thing | Paper Trail
  7. Intuitive explanation of the FLP impossibility result – After Hours Academic
  8. 如何验证线性一致性 | CatKang的博客