System model

本文的 system model 我认为基本指的是 分布式系统的模型。
分布式系统的关键属性是分布。更具体地说，分布式系统中的程序:

  • 在独立节点上并发执行
  • 通过可能引入不确定性和信息丢失的网络连接
  • 没有共享内存或共享时钟

这同时有很多含义:

  • 每个节点同时执行一个程序
  • 信息是本地的: 节点只能快速访问它的本地状态，任何有关全局状态的信息都可能过时
  • 节点可能会失败并独立地从故障中恢复
  • 消息可能会延迟或丢失(与节点故障无关；区分网络故障和节点故障并不容易)
  • 并且节点不跨节点同步(本地时间戳与全局实时顺序不对应，不容易观察到)

系统模型对环境和设施的假设各不相同。这些假设包括:

  • 节点具有哪些功能以及它们可能如何失败
  • 通信链路如何运作以及它们如何失效
  • 整个系统的属性，例如关于时间和顺序的假设

这3个部分各有假设，都有自己的权衡取舍。 independent nodes, commuication links, timing / ordering assumptions.

Nodes in our system model(我们系统模型中的节点)

节点充当计算和存储的主机。他们有:

  • 执行程序的能力
  • 能够将数据存储到易失性存储器(可能在发生故障时丢失)并进入稳定状态(可故障后读取)
  • 时钟(可能会或可能不会认为是准确的)

节点执行确定性算法: 本地计算，计算后的本地状态以及发送的消息由接收到的消息和接收消息时的本地状态唯一确定。
有许多可能的故障模型描述了节点失败的方式。在实践中，大多数系统都裁员崩溃恢复故障模型: 即节点只能通过崩溃而失败，并且可能在稍候崩溃后恢复。
另一种选择是假设节点可能以任意方式行为不端而失败。这被称为拜占庭容错。在现实世界的商业系统中很少处理拜占庭故障，因为对任意故障具有弹性的算法运行起来更昂贵并且实现起来更复杂。我不会在这里讨论它们。

Communication links in our system model(我们的系统模型中的通信链接)

通信链路将各个节点相互连接，并允许以任一方向发送消息。讨论分布式算法的许多书籍假设每对节点之间存在单独的链接，链接为消息提供FIFO（先进先出）顺序，它们只能传递已发送的消息，并且发送的消息可以是丢失。
一些算法假设网络是可靠的：消息永远不会丢失，永远不会无限延迟。对于某些真实世界的设置，这可能是合理的假设，但一般来说，最好考虑网络不可靠并受到消息丢失和延迟的影响。
当网络出现故障而节点本身仍然可以运行时，会发生网络分区。发生这种情况时，消息可能会丢失或延迟，直到修复网络分区。某些客户端可以访问分区节点，因此必须与崩溃节点区别对待。

Timing / ordering assumptions(时间/排序假设)

物理分配的后果之一是每个节点以独特的方式体验世界。这是不可避免的，因为信息只能以光速传播。如果节点彼此处于不同的距离，则从一个节点发送到其他节点的任何消息将在不同的时间到达，并且可能在其他节点处以不同的顺序到达。
时间假设是一种方便的简写，用于捕捉关于我们将在这一现实考虑在内的程度的假设。两个主要替代方案是: 1. 同步系统模型。进程以锁步执行；消息传输延迟有一个已知的上限；每个过程都有一个准确的时钟。2. 异步系统模型。没有时间假设 - 例如，流程以独立的速率执行；消息传输延迟没有限制；有用的时钟不存在。
同步系统模型对时间和顺序施加了许多约束。它基本上假定节点具有相同的体验：发送的消息总是在特定的最大传输延迟内接受，并且该进程在锁定步骤中执行。这很方便，因为它允许你作为系统设计者对时间和顺序进行假设，而异步系统模型则不然。
异步性是一种假设：它只是假设你不能依赖于时间(或时间传感器)
解决同步系统模型中的问题更容易，因为关于执行速度，最大消息传输延迟和时钟精度的假设有助于解决问题，因为你可以根据这些假设做出判断，并通过假设它们永远不会发生来拍出不方便的故障情况。
当然，假设同步系统模型不是特别现实。现实世界的网络容易出现故障，并且消息延迟没有硬性限制。真实世界的系统最多是部分同步的；它们偶尔可以正常工作并提供一些上限。但有时候消息会无限延迟并且时钟不同步。

The consensus problem(共识问题)

如果几个计算机(或节点)都同意一些价值，那么它们就会达成共识。
共识问题是很多商业分布式系统的核心。毕竟，我们需要分布式系统的可靠性和性能，而不必处理分布的后果(例如节点之间的分歧)，并且解决共识问题可以解决几个相关的，更高级的问题，例如原子广播和原子提交。

Two impossibility results(两个不可能的结果)

FLP 设计分布式算法的人特别相关
CAP 从业者更相关的结果

The FLP impossibility result

这与设计分布式算法的人特别相关。

The CAP theorem

这个定理指出了三个属性。
Consistency(一致性) / Availability(可用性) / Partition tolerance(分区容差)
在分布式系统里面，Partition tolerance 是作为分区必不可少的一个属性，那么 Consistency 和 Availability 就变成二元选择。
作者提出几个结论:
1. 早期分布式关系数据库系统中使用的许多系统设计没有考虑分区容差
2. 网络分区期间强一致性和高可用性之间存在紧张关系
3. 在正常操作中强烈的一致性和性能之间存在紧张关系
4. 如果我们不想在网络分区期间放弃可用性，那么我们需要探索除了强一致性之外的一致性模型是否可用于我们的目的
因为 Strong consistency 比较严谨，确实带来性能问题、紧张问题。于是下面开始讨论 Strong consistency 和 别的 consistency model

Strong consistency vs. other consistency models

看了没 Get 到点。
Strong consistency models
Linearizable consistency
Sequential consistency

Client-centric consistency models
Eventual consistency

文章目录

  1. 目录结构:
  2. ## A system model
  3. ### Nodes in our system model
  4. ### Communication links in our system model
  5. ### Timing / ordering assumptions
  6. ### The consensus problem
  7. ### Two impossibility results
  10. ## The FLP impossibility result
  13. ## The CAP theorem
  16. ## Strong consistency vs. other consistency models
  17. ### Strong consistency models
  18. ### Client-centric consistency models
  19. ### Eventual consistency