Distributed Systems for Fun and Profit 笔记（二）

2. 抽象的上下不同层次⌗

系统模型⌗

分布式系统中的程序：

• 在独立节点上同时运行

• 通过可能引入不确定性和消息丢失的网络连接

• 并且没有共享内存或共享时钟

系统模型列举了与特定系统设计相关的许多假设，实现分布式系统的环境和设施的假设：

• 节点具有什么功能以及它们如何失败
• 通信连接如何运行以及它们如何可能失败
• 整个系统的属性，例如关于时间和顺序的假设

健壮的系统模型做出最弱假设，强有力的假设创建易于推理的系统模型

此模型中的节点⌗

作为计算和存储的主机：

• 执行程序的能力
• 能够将数据存储到内存和稳定持久状态的能力

节点执行确定性算法

故障模型：崩溃恢复而非拜占庭容错（任意错误）

此模型中的通信连接⌗

通信连接将各个节点相互连接，并任一方向发送消息

网络不可靠，消息易延迟丢失

网络分区：网络断开但节点存活

时间和顺序的假设⌗

信息最多以光速传播

如果距离不同，节点间消息的到达时间、顺序可能不同

同步系统模型⌗

进程以锁定步骤执行；消息传输延迟有已知上限；每个进程都有准确的时钟

异步系统模型⌗

没有时间假设，进程以独立的速率执行；消息传输延迟没有限制；有用的时钟不存在

共识问题⌗

多个节点都同意一些值时达成共识

1. 一致：每个正确节点都同意相同的值

2. 完整：每个正确的进程最多只能决定一个值，如果决定某个值，那么一定是某些进程提议的

3. 终止：所有进程最终达成决定

4. 有效：如果所有正确进程提议相同的值 V，那么所有正确进程决定值 V

两种不可能的结果⌗

FLP 不可能⌗

假定节点只能因崩溃而失效；网络可靠，并且异步系统模型的典型时序假设成立：例如，消息延迟没有限制，

在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法

CAP 定理⌗

三个属性：

• （强）一致性：所有节点同时看到相同的数据

• 可用性：节点故障不会阻止幸存者继续运行

• 分区容错：网络或节点故障导致消息丢失时，系统仍可继续运行

同时具备这三种属性的系统无法实现：

三种不同的系统类型：

• CA（一致性+可用性）：完全严格的仲裁协议，例如两阶段提交
• CP（一致性+分区容错）：多数仲裁协议，其中少数分区不可用，例如Paxos
• AP（可用性+分区容错）：使用冲突解决方案的协议，例如Dynamo

一致性模型：程序员与系统之间的合同，其中系统保证，如果程序员遵循某些特定规则，则对数据存储区的操作结果将是可预测的

• 强一致性模型（能够维护单个副本）
  • Linearizable consistency （可线性化一致性）
  • Sequential consistency （顺序一致性）
• 弱一致性
  • Client-centric consistency models （客户端为中心一致性）
  • Causal consistency: strongest model available （因果一致性）
  • Eventual consistency models （最终一致性）

线性化一致性要求操作生效的顺序等于操作的实际实时顺序，顺序一致性允许对操作进行重新排序，只要在每个节点上观察到的顺序保持一致