Follow me on GitHub

分布式算法的正确性

我们通过 属性(properties)来描述算法的正确性,比如排序算法的正确性由以下属性定义:

  • 排序后,对于任何两个元素,左边的比右边的小;

分布式算法也一样,也要满足定义其正确性的各种属性;与普通算法不同,因为分布式算法建立在特定系统模型之上,因此还要保证,在发生任何系统模型假定出现的故障时,这些属性依然成立。

问题来了,分布式系统中有很多极端场景,比如节点全部崩溃,或网络延迟突然无限大,此时任何算法都无法推进,此时算法还算正确吗?

属性分类

为解答该问题,首先介绍属性的分类,通常,我们把属性分为两类:

  • 安全性(safety)
  • 活跃性(liveness)

考虑分布式 ID 生成算法,该算法的正确性由以下 3 个属性定义:

  1. 唯一性:任何两次请求结果必然不同;
  2. 单调性:若请求 x 返回 id1,请求 y 返回 id2,且请求 x 先于 y 完成,则 id1 < id2;
  3. 可用性:结点 n 请求 ID,若结点未崩溃,则最终必然收到响应 ID;

其中前两个属性属于安全性属性,第三个属性属于活跃性属性,可以简单认为:

  • 安全性定义 nothing bad happens
  • 活跃性定义 something good eventually happens

所以,活跃性属性的描述中常常有 最终(eventually)二字,比如:

  • 节点最终收到响应;
  • 节点之间数据最终保持一致(最终一致性);

若违反安全性属性,我们可以找到违反的 时间点,比如 ID 生成的唯一性被违反,那么必然可以找到哪两次请求生成了相同的 ID,且安全性属性违反后 无法恢复,是不可逆过程。

与安全性相反,活跃性属性可能在某时间点并不满足,但 未来 某个时间可能被满足,比如请求 ID 后,可能 1s 后没有收到响应,但再等一会可能就收到了。

安全性、活跃性对理解分布式算法的帮助

分布式算法建立在系统模式之上,需要处理系统模型假设会出现的 故障,但分布式算法的正确性属性要分开来看。

其中,在系统模型假设的 任何可能场景 中,安全性属性 必须 得到满足,即任何情况下都不会发生不可逆的破坏性行为。例如,即使所有节点崩溃,或网络永久故障,分布式 ID 生成算法也不会生成相同的或非单调的 ID。

但满足活跃性却需要一定的 前提条件,比如只有在大多数节点存活,且网络故障最终被修复的前提下,才能保证 ID 生成算法的可用性,否则节点全部都没了,谁来生成 ID?

总结一下,在系统模型允许的任何场景中,都必须满足安全性(不会发生破坏性行为),但只有满足一定前提条件时,才能满足活跃性。

这也回答了前面的问题,即使所有节点崩溃,也不影响算法的正确性,因为假定算法早已满足安全性属性,所有节点崩溃后安全性依然可以满足,而活跃性又有前提条件,此时节点崩溃不满足活跃性前提,所以此时可以不满足活跃性。

构建真实系统

系统模型是对真实世界的 简化的抽象,因此在构建真实系统时,模型假设 不会出现 的故障统统会出现。

比如在 crash-recovery model 中,模型假设节点恢复后,存储在非易失存储介质中的状态可以恢复,但实际情况是:

  • 重启后可能发现硬盘坏了;
  • 节点 crash 时,介质上的数据被损坏;
  • 底层软件故障导致恢复后读取数据失败;

当然可以设计一种 新的系统模型,把以上故障统统考虑进去,但这样的模型会过于复杂,从而 难以推导其正确性,考虑哪些故障是一种折中。

系统模型假设部分故障永远不会出现,但构建真实系统时必须考虑 所有故障,不过我认为可以只处理系统模型忽略的那些故障即可,处理方式多种多样,比如简单打印日志,或告警通知操作人员处理等,系统底层实现努力为算法提供一个干净的、满足系统模型的抽象,剩下的故障由算法自行处理。