分布式计算的误区

  • 网络是稳定的：通常可以假设网络稳定可靠，因为网络可达才有用。但网络交换会有故障（物理故障、配置变更等）。
  • 网络是有延迟的：网络操作需要通过若干软件层和物理媒介，不是瞬间完成的。
  • 带宽是有限的：消息的数量、大小、发送速率需要被考虑。

请求处理

  • 发送远程请求后，需要通过网络传输（存在网络延迟）；远程进程收到消息后，可能进入等待队列（存在排队延迟）；从等待队列取出后，需要在本地处理（存在处理延迟）。
  • 木桶原理：如果完成一项任务需要等待几个并行工作的远程服务器响应，则整个执行的完成时间取决于最慢的服务器。
  • 队列容量：不是无限的，当生产者产生消息的速度大于消费者能够处理的速度时，可以使用背压策略减慢生产者的速度（并非必须）。
  • 队列的作用如下：
    • 解耦：使接收和处理在时间上分开。
    • 流水线化：不同阶段的请求由系统中独立的部分处理，负责接收消息的子系统不用阻塞到上一条消息处理完成。
    • 吸收瞬时突发流量：系统负载可能经常变化，但是请求到达的间隔时间对负责处理请求的组件是隐藏的。总体的系统延迟会由于排队而增加，但通常比响应失败并重试请求更好。

时钟和时间

  • 不同的远程计算机上的时钟是不同步的，因此不能依赖时间戳进行同步与排序，因为任何同步系统都依靠本地时钟实现超时。

状态一致性

  • 分布式算法并不总保证状态在节点间严格一致，一些方法具有较宽松的约束，允许各副本之间的状态存在分歧，并依赖冲突解决（检测和解决系统内分歧状态的能力）和读取时数据修复（读取期间当各副本响应结果不同时，使副本恢复同步的能力）。

远程调用

  • 远程调用的成本比本地调用高很多倍。

节点故障

  • 不能假设在长时间运行的系统中节点都总是可以正常工作。
  • 远程服务器没有响应可能是由于系统崩溃、网络故障、远程进程或网络链路太慢导致的。一些分布式算法使用心跳协议、故障检测机制来确定哪些参与者还存活可达。

网络分区

  • 系统可能出现两个或更多节点无法互相通信的情况。通常可以通过故障测试来尝试构建一个高可用性的系统。

级联故障

  • 故障能够从系统的一部分传播到另一部分，扩大了问题的范围。如，被高负载压垮的进程会增加集群其余部分的负载，从而使其它节点也有可能发生故障。
  • 可以通过退避（backoff）或抖动（jitter）来减少重连的影响。

分布式系统抽象

  • 链路：两个进程通过链路相连并相互发送消息。

公平损失链路

  • 概念：链路的发送方没有任何方法确定消息是否已经送达。
  • 消息被发送后，它可能处于以下三种状态：
    • 还未送达但会在将来送达
    • 在途中丢失且不可恢复
    • 已送达
  • 公平损失链路有以下三个属性：
    • 公平损失：如果发送方和接收都是正确的，发送方经过无限多次重复发送，消息最终会被送达。
    • 有限重复：发送的消息不会被送达无限次。
    • 不会无中生有：链路不会传递一个从未发送过的消息。

消息确认

  • 确认机制：接收方通知发送方消息已送达。
  • 序列号：单调递增的唯一标识符
  • 进程A可以发送消息M(n)，其中n是单调递增的消息计数器，B收到消息后立即向A发送确认ACK(n)。

消息重传

  • 重传：发送方重试可能失败的操作。
  • 幂等：操作可以多次执行，也不会产生其他的副作用。
  • 重传通常与确认机制相结合，且为了不导致消息重复，应该保证操作是幂等的。

消息顺序

  • 不可靠的网络可能导致：消息乱序到达；重传消息多次送达。
  • 由于每条消息都有一个序列号，接收方可以跟踪一些信息：
    • 最大连续序列号：所有小于或等于该序列号的消息都已经收到，用于排序。可以安全地丢弃小于此序列号的消息。
    • 最大已处理序列号：所有小于或等于该序列号的消息都已经按照原来的顺序被处理，用于去重
  • 如果收到的消息序列号不连续，接收方会将其放入重新排序缓冲区。
  • 完美链路有以下三个属性：
    • 可靠传递：正确的进程A发送一次到正确的进程B的每个消息最终都会被传递。
    • 没有重复：消息不会被传送多次。
    • 不会无中生有：链路不会传递一个从未发送过的消息。

共识

两将军问题

  • 是对分布式系统一致性的描述。
  • 该问题说明，如果链路可能发生故障，且通信是异步（进程不共享时间，意味着没有超时机制）的，则不可能在通信的双方之间达成共识。

FLP不可能定理

  • 共识协议：给定具有初始状态的多个进程，共识协议将所有进程转换为决定的新状态。一个正确的共识协议必须具备以下三个属性：
    1. 一致性：每个进程都做出了决定，所有进程的决定是相同的。
    2. 有效性：达成共识的值由某一个参与者提出。
    3. 终止性：当所有进程都达到决定状态时，协议结束。
  • FLP不可能定理：假设通信过程是异步的，那么不存在任何协议能保证在有限时间内达成共识。

系统的同步性

  • 分布式系统同步的概念：系统中具有时间，假定各个进程处理速度相近、传输延迟有限、传递消息不会花费任意长的时间。在同步模型中可以使用超时机制。
  • 分布式系统可认为是部分同步的，部分同步的系统具有同步系统的某些属性，但是在消息传递、时钟漂移和相对处理速度的边界范围可能并不精确，且仅在大多数时候成立。

故障模型

  • 崩溃故障：
    • 崩溃-停止：进程停止执行算法，不再发送任何消息给其他进程。
    • 崩溃-恢复：进程停止执行算法，在稍后恢复并尝试执行剩下的步骤。
  • 遗漏故障：进程跳过了某些算法步骤，或者无法执行这些步骤，或者执行过程对其他参与者不可见。
  • 任意故障/拜占庭故障：进程以违背算法的方式执行了算法的步骤。
  • 故障处理：引入冗余。