Follow me on GitHub

分布式系统 | 系统模型(System Model)

在分布式系统中,可能出现各种故障,例如机房断电、数据中心被炸毁、节点崩溃、网络延迟、网络分区、网络故障、时钟漂移、网络攻击、网络欺骗等等,因此分布式环境 极度不可靠,那分布式算法是如何建立在如此不可靠的基础上的呢?

任何算法都无法保证解决以上所有问题,但每个算法都能解决部分问题,那不能解决的剩余部分怎么办呢?

很简单,每个算法都假定它不能解决的那些问题 根本不存在,典型的“鸵鸟策略”。

分布式算法可以采用”鸵鸟策略“,但分布式系统必须考虑所有可能发生的错误,即使应对策略简单到打印日志,或通知管理员手动处理。

系统模型(System Model)就是形式化描述系统中可能发生什么故障,不可能发生什么故障的抽象,每个分布式算法都必须说明自己建立在什么样的系统模型上,否则算法没有意义。

当然,系统模型与真实世界 越接近,则建立在其上的算法就 越实用,如果算法假设的系统模型尽善尽美,不可能发生任何错误,那这算法屁用没有。

系统模型可从时间、节点两个维度分类。

时间维度

同步模型(synchronous model)

同步模型假设 故障有时间上界,即:

  • 有界网络延迟(bounded network delay)
  • 有界处理暂停(bounded process pause)
  • 有界时钟漂移(bounded clock drift)

同步模型并不实际,因为现实中的网络延迟、处理暂停时间可能是无限的。

部分同步模型(partially synchronous model)

部分同步模型假定系统大部分时间处于同步模型,但偶尔网络延迟、处理暂停、时钟漂移超出时间上界,但这种状态在 有限时间 内会被修复,重新回到同步模型。

部分同步模型非常实用,符合实际。

异步模型(asynchronous model)

异步模型没有 时间概念,进而没有 超时 概念,异步模型适用场景较少。

节点维度

崩溃-停止错误(crash-stop faults/model)

该模型假设节点只能以 崩溃 方式失败(can fail only by crashing),且节点崩溃后 无法恢复

注意,节点可能在 任意时间 突然崩溃。

崩溃-恢复错误(crash-recovery faults/model)

假设节点可以在 任意时间 突然崩溃,但经过 未知时间(无限 or 有限)后节点可以恢复,从而继续响应用户请求。

该模型假设节点恢复后可以 保持崩溃前的状态,这要求节点具备持久化、断电不易失的存储。

拜占庭错误(Byzantine/arbitrary faults/model)

该模型假设,节点可具有任何行为,比如欺诈、隐瞒等恶意行为,该模型与现实最为接近,但建立在该模型上的算法非常复杂。

最终模型

综合考虑时间和节点两个维度,系统模型可以有多种组合,其中:

  • 部分同步模型 + 崩溃-恢复模型

通常被视为最具实用价值的模型,很多算法建立在该模型之上。