分布式系统相关资源汇总及简要笔记。


基础概念

一致性相关

Strong consistency models

中文版 英文版

正确性 (Correctness)

  • 我们说一个系统是由状态和一些导致状态转移的操作组成的
  • 系统的正确性:给定一些涉及状态与操作的规则,随着操作的演进,系统将一直遵循这些规则。我们把这样的规则成为一致性模型
  • 更加正式地说,一致性模型是所有被允许的操作记录的集合。如果任意可能执行的操作都在这个被允许的操作集合内,那么系统就满足一致性模型

光锥 (Light cones)

  • 读写不是一个瞬时的过程,而是一个类似 光传播(调用) -> 反射面(执行) -> 反向传播(完成) 的过程
  • 因此,调用的先后顺序并不等于操作真实执行的先后顺序

线性一致性 (Linearizability)

每个操作会在它调用和完成之间的某个时间点原子地生效.

  • 对于观察者来说,所有的读和写都在一个单调递增的时间线上串行地向前推进
  • 所有的读总能返回最近写操作的值

顺序一致性 (Sequential consistency)

如果我们允许进程在时间维度发生偏移,从而它们的操作可能会在调用之前或是完成之后生效,但仍然保证一个约束 —— 任意进程中的操作必须按照进程中定义的顺序 (即编程的定义的逻辑顺序) 发生。这样我们就得到了一个稍弱的一致性模型:顺序一致性。

  • 不要求操作按照真实的时间顺序发生 (可能读到过期数据)
  • 不同进程间的操作执行先后顺序没有强制要求,但必须是原子的
  • 单个进程内的操作顺序必须和编码时的顺序一致

因果一致性 (Casual consistency)

不对一个进程中的每个操作都施加顺序约束。只有因果相关的操作必须按顺序发生。

串行一致性 (Serializable consistency)

串行一致性是事务的隔离属性,每个事务可以读写多个对象 (行,文档,记录)。它确保事务的行为,与它们按照某种顺序依次执行的结果相同 (每个事务在下一个事务开始之前运行完成)。这种执行顺序可以与事务实际执行的顺序不同,和调用时间与完成时间无关。

  • 串行一致性是对多操作,多对象的保证,对总体的操作顺序无要求
  • 线性一致性是对单操作,单对象的保证,所有操作遵循真实时间序

CAP 定理相关

CAP 定理指出对于一个分布式计算系统来说,不可能同时满足以下三点:

  • 一致性 (Consistency): Every read receives the most recent write or an error
  • 可用性 (Availability): Every request receives a (non-error) response, without the guarantee that it contains the most recent write
  • 分区容错性 (Partition tolerance): The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes

CAP Twelve Years Later: How the “Rules” Have Changed

中文版 英文版

  • 三选二具有误导性
  • ACID、BASE、CAP 的关系
    • BASE: Basically Available, Soft state, Eventually consistent
  • CAP 与延迟的联系
  • 管理分区
    1. 检测分区开始

    2. 明确进入分区模式,两种可行的策略

      • 限制部分触犯不变性约束的操作,因此会削弱可用性
      • 额外记录一些有利于分区恢复的操作信息,如版本向量等
    3. 分区恢复,修复分区期间造成的错误

Please stop calling databases CP or AP

中文版 英文版

  • CAP 定义非常狭隘

    • 一致性在 CAP 中其实是指线性一致性 (linearizability)
    • 可用性要求任何非故障节点都能够处理请求
    • 分区容错性基本上意味着你的通信建立在可能会延迟或丢包的异步通信网络上. 互联网和我们的数据中心都有这个属性, 所以在这个问题上其实没有任何选择.
    • CAP 系统模型是一个单一读写寄存器 (single, read-write register),没有涉及多个对象的事务
    • CAP 定理只考虑了网络分区 (network partition) 这一故障场景
    • CAP 定理没考虑到延迟 (latency)
  • 多数系统既不线性可用 (linearizable) 也不 CAP 可用 (CAP-available)