↓Skip to main content
Arc
  1. Posts/

分布式系统大局观（一）: 理论基础

·12 mins·
分布式系统
Tech Enthusiast running out of Coffee.
Table of Contents

这篇文章翻译自 distsys-class，但结构按照个人理解做了一些调整，并对其中一些关键内容做了补充和解释，这篇属于上半部分，更偏重于理论。

基本原语
#

是什么让一个东西变成分布式？
#

兰波特，1987年：

分布式系统是计算机出现故障的系统 你甚至不知道存在可以渲染自己的计算机无用。

  • 第一眼：*nix 盒子在 colo 中，进程通过 TCP 或 UDP 通信。
    • 或 EC2，Rackspace 等中的盒子
    • 也许通过 InfiniBand 进行交流
    • 以英寸计的局域网
    • 或以公里计的互联网
  • 大多数手机应用程序也参与了分布式系统
    • 通过糟糕的网络进行通信
    • 桌面网络浏览器也是如此
    • 不仅仅是服务器，还有客户端！
  • 更一般地说：分布式系统是
    • 由相互通信的部分组成
    • 慢
    • 不可靠
    • 这些对是使用者来说是透明的
  • 所以这些也是：
    • 飞机中的冗余 CPU
    • 自动柜员机和销售点终端
    • 太空探测器
    • 支付账单
    • 转诊医生
    • 尝试通过短信制定计划
    • 每次商务会议

节点和网络
#

  • 我们将分布式系统的每个部分称 Node
    • 也称为 process、agent 或 actor

节点
#

  • 节点延迟特征

    • 节点内的操作"很快"
    • 节点之间的操作"缓慢"
    • 但快慢取决于系统的功能

  • 节点是可靠的

    • 作为一个故障单元
    • 你应该知道什么时候会出现问题
    • 状态时连贯的
    • 状态转换以一种良好、有序的方式发生
    • 通常建模为某种单线程状态机

  • 节点本身可以是分布式系统（多核并行系统）

    • 但只要整个系统提供"快速、连贯“操作，我们可以将其视为单个节点。

  • 形式化进程模型

    • Communicating Sequential Processes (CSP)
    • Pi-calculus (π演算)
    • Ambient calculus（Ambient演算）
    • Actor model （演员模型）

  • 形式化节点故障模型

    • Crash-stop
    • Crash-recover
    • Crash-amnesia
    • Byzantine

网络作为消息流
#

  • 节点通过网络进行交互

    • 人类通过口头语言进行交流
    • 粒子通过场相互作用
    • 计算机通过IP、UDP、SCTP等方式进行交互

  • 我们将这些交互建模为节点之间传递的离散消息

  • 消息需要时间传播

    • 这是分布式系统中的 “slow” 部分
    • 我们称之为"latency”

  • 消息往往会丢失

    • 这是分布式系统中的 “unreliable” 部分

  • 网络很少是同构的

    • 某些连接比其他连接更慢/更小/更容易发生故障

因果关系图
#

  • 我们可以将节点和网络的交互表示为一个图表：
    • 时间从左到右流动，或者从上到下流动。
    • 节点以时间方向的线条表示（因为它们保持不动）。
    • 消息表示为连接节点的倾斜路径。

同步网络

  • 节点同步执行：节点步骤之间的时间始终为1。
  • 消息延迟有界限。
  • 实际上是一个完美的全局时钟。
  • 容易证明有关的事情。
    • 你可能没有这样的网络。

半同步网络
#

  • 类似于同步网络，但时钟只是近似的，例如在 $[c, 1]$ 之间。

    半同步网络提供了一种折衷方案。它允许节点在一定程度上进行同步，但并不要求所有节点在完全相同的时刻执行操作。相反，它允许节点之间存在一定的时钟偏差或不确定性，通常用一个时间窗口或范围 [c, 1] 来描述。在这个时间窗口内，节点可以按照自己的时钟步进执行操作，但是仍然保持着一定的相对顺序和协调。

    通过引入半同步性，分布式系统可以在一定程度上平衡同步和异步之间的要求。它提供了一种灵活性，使系统能够适应网络中可能出现的延迟、时钟偏差或其他不确定性。半同步网络通常会提供一些保证，例如在一定时间内节点之间的消息传递会被递交，但是它仍然允许一定程度的自由度和容错性。

异步网络
#

  • 独立执行，无论何时：步骤时间在 $[0, 1]$ 的范围内。
  • 消息延迟无界。
  • 没有全局时钟。
  • 比半同步或同步网络要弱。
    • 意味着某些算法无法达到同样的效率。
    • 意味着某些算法是不可能的。
    • 参考Attiya和Mavronicolas的论文"Efficiency of Semi-Synchronous vs Asynchronous Networks"。
  • IP网络肯定是异步的。
    • 但是，在实践中，真正病态的情况并不经常发生。
    • 大多数网络在几秒钟到几周内恢复，而不是"永远"。
      • 相反，人类的时间尺度大约是几秒到几周。
      • 所以我们不能假装这些问题不存在。

当网络发生错误
#

低级协议
#

TCP
#

  • TCP

    • 可以使用
    • 不是完美的；可以更快
    • 但你会知道何时需要更快的选项

  • 实际上，TCP在单个TCP连接的上下文中防止了消息重复和消息重新排序的问题

    • 但你可能会打开多个连接
    • 如果没有其他原因，TCP连接最终会失败
    • 当发生连接失败时，你要么a.)丢失了消息，要么b.)重试
    • 你可以通过在TCP之上编码自己的序列号来重构消息的顺序

UDP
#

  • UDP具有与TCP相同的寻址规则，但没有流的不变性
  • 许多人希望使用UDP “以获得速度”
    • 但他们没有考虑到路由器和节点可以任意丢弃数据包
    • 他们的数据包可能会被重复、重新排序
    • “但至少是公平的，对吧？”
      • 错！
    • 这在诸如指标收集等情况下会造成各种混乱
    • 而且调试困难
    • TCP为你提供了流控制并将逻辑消息重新打包成数据包
      • 你需要重新构建流控制和反压机制
    • UDP在TCP状态机开销过高的情况下非常有用
    • 内存压力
    • 大量的短连接和套接字重用
  • 特别适用于以尽力而为的传递方式（best-effort delivery）与系统目标相匹配的情况
    • 语音通话：人们会道歉并重复自己的话
    • 游戏：卡顿和延迟，但稍后会追赶上来
    • 更高级的协议对底层混乱施加了一定的合理性

时钟
#

  • 当系统分为独立部分时，我们仍然希望对事件进行某种排序
  • 时钟帮助我们对事物建立顺序排序：首先这个，然后是那个

墙上时钟
#

Lamport 时钟
#

  • Lamport在1977年提出的 “Time, Clocks, and the Ordering of Events in a Distributed System”

    • 每个进程有一个时钟
    • 每个状态转换都会使时钟单调递增：t' = t + 1
    • 每个发送的消息都包含时钟值
    • t' = max(t, t_msg + 1)

  • 如果我们有进程的全排序，我们可以对事件进行全排序

    • 但该排序可能相当不直观

向量时钟
#

  • 向量时钟将Lamport时钟推广为包含所有进程时钟的向量
  • t_i' = max(t_i, t_msg_i)
  • 对于每个操作，递增向量中对应进程的时钟
  • 提供部分因果顺序
    • 当且仅当 $A_i <= B_i$，并且至少存在一个 $A_i < B_i$，则 $A < B$
    • 具体而言，给定一对事件，我们可以确定它们之间的因果关系
      • A在B的因果过去意味着A < B
      • B在A的因果过去意味着B < A
      • 否则彼此独立
  • 实际上：过去是共享的；现在是独立的
    • 只需保留"现在"，即独立状态
    • 可以丢弃祖先状态
    • 允许我们垃圾回收过去的状态
  • 空间复杂度为 $O(P), \text{P 是进程数}$
    • 垃圾回收需要协调
    • 或者牺牲正确性，修剪旧的向量时钟条目
  • 变体
    • Dotted Version Vectors - 用于客户端/服务器系统，可以对更多事件进行排序
    • Interval Tree Clocks - 适用于进程的动态加入和退出

GPS和原子时钟
#

  • 比NTP更好
    • 全球分布的毫秒级总排序
    • 将异步网络转变为半同步网络
    • 可以使用更高效的算法
  • 目前只有谷歌拥有这项技术
    • Spanner：全球分布的强一致事务
    • 他们不会分享
  • 成本比你期望的高
    • 每个GPS接收器几百美元
    • 本地协调的原子时钟：$$$$？
    • 可能需要多种类型的GPS时钟
    • 我还不知道谁正在使用它，但我敢打赌未来的数据中心将提供专用的硬件接口以获取有界精度的时间。

回顾
#

我们已经介绍了分布式系统的基本原语。节点通过网络交换消息，节点和网络都可能以各种方式发生故障。TCP和UDP等协议为进程之间的通信提供了基本通道，我们可以使用时钟来对事件进行排序。现在，我们将讨论分布式系统的一些高级属性。

可用性
#

  • 可用性基本上是指尝试操作成功的比例。

Total availability
#

  • 简单的假设：每个操作都成功。
  • 在一致性中：在非故障节点上的每个操作都成功
    • 对于失败的节点无能为力

Sticky availability
#

  • 针对非故障节点的每个操作都成功
    • 但一个约束是：客户端始终与相同的节点通信

High availability
#

  • 比系统不分布式更好。
  • 例如，容忍最多 f 个故障，但不能超过该数目
  • 可能会出现一些操作失败

Majority available
#

  • 如果操作发生在可以与集群中的大多数节点进行通信的节点上，则操作成功
  • 针对少数组件的操作可能会失败

量化可用性
#

  • 我们经常谈论"uptime"
    • 如果没有人使用系统，系统算作正常运行吗？
    • 在高峰时段宕机是否更糟糕？
    • 可以测量"在时间窗口内满足请求的比例"
    • 然后在不同时间的窗口中绘制该比例
    • 时间尺度（Timescale ）影响报告的 uptime
  • Apdex
    • 不是所有的成功操作都是相等的
    • 将操作分类为 “OK”, “meh”, and “awful”
    • Apdex = P(OK) + P(meh)/2
    • 同样，可以报告基础的年度 Apdex
      • “我们在今年实现了99.999的 Apdex”
    • 也可以在更精细的时间尺度上报告！
      • “用户服务的 Apdex 刚刚下降到0.5；快速处理！”
  • 理想情况下：您的服务提供的满意度积分？

一致性
#

  • 一致性模型是系统中事件的"安全"历史记录的集合。

    我们系统中发生的事件建模为历史（history），事件历史可能存在多个时间线，一致性模型就是从这些事件线中找到一个合法的历史顺序.

线性一致性
#

  • 所有操作似乎是以原子方式执行的
  • 每个进程都同意操作的顺序
  • 每个操作似乎都是实时的
  • 实时、外部约束可以让我们构建非常强大的系统

Jepsen: Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A.

This model cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress.

Linearizability is a single-object model, but the scope of “an object” varies. Some systems provide linearizability on individual keys in a key-value store; others might provide linearizable operations on multiple keys in a table, or multiple tables in a database—but not between different tables or databases, respectively.

When you need linearizability across multiple objects, try strict serializability. When real-time constraints are not important, but you still want every process to observe the same total order, try sequential consistency

线性一致性也称为强一致性。在多个并发的历史时间线中，找到一个合法的顺序，该顺序满足线性一致性。线性一致性有两个重要的约束

  1. 线性一致性具有实时性约束，每个读都可以读取到最近一次写入的数据。
  2. 线性一致性需要一个全局时钟来排序让所有进程观察到一致的顺序。

例如在 raft 算法中，为了满足实时性约束和全局顺序一致，需要选举一个 leader 使用 term 作为逻辑时钟对事件定序，同时基于 leader 读取也满足线性一致性第一个要求。

即使多个客户端并发写，线性一致性也满足一个全局顺序。例如 C1, Put(k, v1) 和 C2, Put(k, v2) 是两个并发的写操作，如果客户端之间没有协调，它们对彼此是并发的，但是对于线性一致性的系统来说，无论先执行哪一个，其他副本都会得到相同的顺序。

顺序一致性
#

  • 类似于因果一致性，对可能的顺序进行约束
  • 所有操作似乎是以原子方式执行的
  • 每个进程都同意操作的顺序
    • 给定进程的操作总是按顺序进行
    • 但节点可能滞后

Jepsen: Sequential consistency is a strong safety property for concurrent systems. Informally, sequential consistency implies that operations appear to take place in some total order, and that that order is consistent with the order of operations on each individual process.

Sequential consistency cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress.

A process in a sequentially consistent system may be far ahead, or behind, of other processes. For instance, they may read arbitrarily stale state. However, once a process A has observed some operation from process B, it can never observe a state prior to B. This, combined with the total ordering property, makes sequential consistency a surprisingly strong model for programmers.

When you need real-time constraints (e.g. you want to tell some other process about an event via a side channel, and have that process observe that event), try linearizability. When you need total availability, and a total order isn’t required, try causal consistency.

对于同一个进程的操作, 顺序一致性要求所有其他观察的进程可以看到相同的顺序, 但是对于多个进程的并发操作, 顺序可能是任意的.

和线性一致性的区别在于, 顺序一致性不需要全局顺序，只需要对于一个进程来说，它做的操作在任意副本上在它观察是保持相同的顺序即可，也就是局部有序。但是顺序一致性也没有实时性约束， 进程什么时候可以在其他副本上看到最新的数据取决于其他进程什么时候观察到该事件, 这意味着进程可以从不同的副本获取到任意陈旧的状态.

例如，zookeeper 实现了顺序一致性，客户端执行的操作，zookeeper 保证副本按照发送的顺序执行。同时 zookeeper 允许客户端在任意副本读取，由于顺序一致性没有实时性约束，因此会读取到旧的副本，不过 zookeeper 提供了 Sync 命令来执行强制同步。

因果一致性
#

  • 使用一个 DAG 表示操作的因果关系图
    • 例如，读后写是因果相关的
      • 假设进程没有丢弃读到的数据
    • DAG 中没有边的操作是并发的
  • 约束：在进程执行操作之前，所有其前置操作必须在该节点上执行
  • 并发操作可以自由重排序

Jepsen: (Causal consistency captures the notion that causally-related operations should appear in the same order on all processes—though processes may disagree about the order of causally independent operations.

For example, consider a single object representing a chat between three people, where Attiya asks “shall we have lunch?”, and Barbarella & Cyrus respond with “yes”, and “no”, respectively. Causal consistency allows Attiya to observe “lunch?”, “yes”, “no”; and Barbarella to observe “lunch?”, “no”, “yes”. However, no participant ever observes “yes” or “no” prior to the question “lunch?”.

Convergent causal systems require that the values of objects in the system converge to identical values, once the same operations are visible. In such a system, users could transiently observe “lunch”, “yes”; and “lunch”, “no”—but everyone would eventually agree on (to pick an arbitrary order) “lunch”, “yes”, “no”.

Causal consistency is sticky available: even in the presence of network partitions, every client connected to a non-faulty node can make progress. However, clients must stick to the same server.

A slightly stronger version of causal consistency, Real-Time Causal, is proven to be the strongest consistency model in an always-available, one-way convergent system. Most “causally consistent” systems actually provide these stronger properties, such as RTC or causal+.

When a total order is required, and you’re willing to sacrifice availability (and latency), consider sequential consistency. If you need total availability, you’ll have to give up causal (and read-your-writes), but can still obtain writes follow reads, monotonic reads, and monotonic writes.

因果一致性是内存一致性主要模型之一, 也被称为 happend-before 关系. 因果一致性要求具有因果顺序的事件被所有观察者以相同的顺序观察到, 并发事件无保证.

P1 :	W(x)1		W(x)3		
P2 :	R(x)1	W(x)2			
P3 :	R(x)1			R(x)3	R(x)2
P4 :	R(x)1			R(x)2	R(x)3
Time -------------------------------->

上面中, w1, w2 是因果相关的, w3 和 w2 是并发的, 没有因果关系, P3, P4 可以观察到不同的顺序.

因果一致性是一种比顺序一致性更弱的一致性模型,

因果一致性和顺序一致性的区别在于, 顺序一致性要求同一个进程操作的顺序所有其他进程都以相同的顺序看到, 而因果一致性只对存在因果关系的读写进行约束, 其他顺序可以是任意的. 这意味着同一个进程的操作的顺序在多个副本上可能不同, 但满足因果关系的顺序相同.

同样的, 因果一致性没有实时性约束, 取决于观察者.

上述的四种模型也被称为数据中心视角的一致性，下面将的一致性则更多的是处于客户端的视角。

单调读
#

  • 一旦读取一个值, 后续的任何读取将返回该值或者更新的状态.

    Jespen: Monotonic reads ensures that if a process performs read r1, then r2, then r2 cannot observe a state prior to the writes which were reflected in r1; intuitively, reads cannot go backwards.

    Monotonic reads does not apply to operations performed by different processes, only reads by the same process.

    例如, 同一个客户端 Get(k) -> v1, 单调读保证客户端后续不会读到比 v1 更旧的值

单调写
#

  • 如果进行写入操作，后续的任何写入操作将发生在第一次写入之后.

    Monotonic writes ensures that if a process performs write w1, then w2, then all processes observe w1 before w2.

    Monotonic writes does not apply to operations performed by different processes, only writes by the same process.

    Monotonic writes can be totally available: even during a network partition, all nodes can make progress.

    例如, 同一个客户端 Put(k, v1), 后续的任何写操作都会在该操作之后执行，即保证串行写

读你所写（Read Your Writes）
#

  • 一旦写入一个值，后续任何的读操作将返回此次写入（或更新的值）.

    Jepsen: Read your writes, also known as read my writes, requires that if a process performs a write w, then that same process performs a subsequent read r, then r must observe w’s effects.

    Note that read your writes does not apply to operations performed by different processes. There is no guarantee, for instance, that if process 1 writes a value successfully, that process 2 will subsequently observe that write.

    Read your writes is sticky available: if a network partition occurs, every node can make progress, so long as clients never change which server they talk to.

    例如, 客户端 Put(k, v1) 之后，客户端在任何副本上执行读操作都能读取到该值或者更新的值, 这个保证只适用于同一进程, 不同进程无法保证.

FIFO 一致性 (PRAM: Pipeline Random Access Memory 补充)
#

  • 等价于 读你所写 + 单调写 + 单调读

    Jepsen: PRAM (Pipeline Random Access Memory) comes from Lipton & Sandberg’s 1988 paper PRAM: A Scalable Shared Memory, which attempts to relax existing coherent memory models to obtain better concurrency (and therefore performance). It enforces that any pair of writes executed by a single process are observed (everywhere) in the order the process executed them; however, writes from different processes may be observed in different orders.

    PRAM is exactly equivalent to read your writes, monotonic writes, and monotonic reads.

    PRAM is sticky available: in the event of a network partition, all processes can make progress so long as clients always stick to the same server.

    For a more strict consistency model which also enforces that writes follow reads, try causal consistency: it’s just as available, and provides more intuitive semantics. If you need total availability, consider sacrificing read your writes and choosing just monotonic reads + monotonic writes.

    简单来说, 一个客户端执行的写操作顺序, 将被所有其他进程按照同样的顺序观察到. 但不客户端的写操作对于观察者来说可能乱序. 例如, 下面事件序列满足 PRAM 一致性

    P1:W(x)1 
P2:       R(x)1W(x)2
P3:                  R(x)1R(x)2
P4:                  R(x)2R(x)1
Time ---->

    PRAM 满足 sticky 可用性, 在网络分区时, 客户端只要 “粘附” 在同一个服务器上, 客户端是可用的.

读后写 (Writes Follow Reads)
#

  • 一旦读取一个值，后续任何的写入操作将在该读取的值之后进行

    Jepsen: Writes follow reads, also known as session causality, ensures that if a process reads a value v, which came from a write w1, and later performs write w2, then w2 must be visible after w1. Once you’ve read something, you can’t change that read’s past.

    Writes follow reads is a totally available property. Every node can make progress regardless of network partitions.

    例如, 客户端 Get(k) -> v1 之后，后续该客户端的 Put(k, ( {v1 OR higher} -> v2)) 需要基于 v1 或者比 v1 更新的值执行。读后写也称会话因果一致性（session causality）

ACID 隔离级别
#

  • ANSI SQL的ACID隔离级别很奇怪

    • 基本上是对现有供应商实现效果的编码
    • 规范中的定义含糊不清

    在早期的事务概念中，为了提高并发性，人们尝试了很多相对于可串行化而言更弱的定义。这些尝试最大的困难是如何给出具有鲁棒性的定义。

    这方面最具影响力的成就来自于 Gray 早期 “Encapsulation of parallelism in the volcano query processing system” 的研究。

    这项工作试图说明一致性程度的定义，并通过锁的形式来实现它。受该工作的影响，ANSI SQL 标准定义了四个“隔离等级”。

    Adya 在 Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions对 ANSI SQL 隔离级别进行了更详细的解释，定义了

    • P0 (Dirty Write): w1(x) … w2(x)
    • P1 (Dirty Read): w1(x) … r2(x)
    • P2 (Fuzzy Read): r1(x) … w2(x)
    • P3 (Phantom): r1(P) … w2(y in P)

  • Adya 1999年的论文：Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions

    • 每个ANSI SQL隔离级别定义如何禁止一种异常情况

    • 未提交读

      • 防止 P0: 脏写
        • w1(x) … w2(x)
        • 在一个事务提交前，另一个事务不能覆盖
      • 可以在事务修改数据时读到数据
      • 可以读到将被回滚的数据

      这意味着读取不需要任何锁

    • 已提交读

      • 防止 P1：脏读
        • w1(x) … r2(x)
        • 不能读取未提交事务的值

      一个事务可以读任何已提交的数据，但对于同一个对象的重复读可能导致读到不同版本的数据。

      一般实现方式是，读数据前必须首先获得一个读操作锁，一旦数据读取之后该锁被立即释放。

    • 可重复读

      • 防止P2：不可重复读 OR 模糊读
        • r1(x) … w2(x)
        • 一旦事务读取一个值，该值在事务提交之前不会更改

      一个事务只能读取一个已提交数据的一个版本；一旦该事务读取了一个对象，那么，它将只能读取该对象的同一个版本。

      一般实现方式是，事务在请求读数据 之前必须获得一个锁，并且保持该锁直到事务结束。

      直觉上，可重复读似乎保证了完全的可串行化，但是，在早期的 R 系统中发生了一个“幽灵问题”。在幽灵问题中，一个事务使用同样的谓词多次访问了同一个关系，但是，最近的访问却得到了最初访问时没有发现的新的“幽灵元组”。原因在于，元组级的两段锁并不能阻止往表中插入元组。表级别的两段锁可以防止幽灵问题，但是，当事务通过索引访问表中的几个元组时，表级别的两段锁是被限制的。

    • 可串行化

      • 防止 P3：幻读
        • 给定一些谓词 P
        • r1(P) … w2(y in P)
        • 一旦事务读取满足查询的一组元素集合，该集合在事务提交之前不会更改
        • 不仅仅是值，而是甚至 哪些值会参与其中。

      简单来说，可串行化要防止可重复读中提到“幽灵问题”，也就是幻读。

      可串行化是事务控制中的概念，是一种事务模型。一个事务可以包括多个按顺序执行的子操作，可串行化保证事务的子操作与其他事务的子操作不会交错执行。

      可串行化是一个多对象属性：操作可以作用于系统中的多个对象。事实上，可串行性不仅适用于 事务中涉及的特定对象，而且适用于**整个系统——操作可以作用于谓词，比如“所有猫的集合”。

      ANSI SQL 1999 spec：可串行化被定义为并发执行的事务与某种串行执行达到相同的效果。串行执行是值每个 SQL 事务在下一个事务开始之前执行完成。

      可串行化可以防止脏写、脏读、不可重复度、幻读。

      Cerone、Bernardi 和 Gotsman 的 A Framework for Transactional Consistency Models with Atomic Visibility，它将可序列化性指定为三个属性的组合：

      • 内部一致性：在事务内，读取观察该事务的最新写入（如果有）
      • 外部一致性：事务 T 1中没有先前写入的读取必须观察事务 T 0 写入的状态，使得 T 0对 T 1可见，并且没有最近的事务写入该对象。
      • 全可见性：可见性关系必须是全序关系。

    • 游标稳定

      • 事务有一组游标
        • 游标引用事务访问的对象
      • 读取锁保持到游标被删除或提交为止
        • 在提交时，游标升级为写锁
      • 防止丢失更新

      游标稳定中的事务将根据查询游标在最近读取的数据项上加一个锁，当游标移走（如数据被提取）或者事务中止时释放该锁。游标稳定允许事务对个别数据 项目按照“读—处理—写”的顺序来操作，其间避免了其他事务的更新干扰

    • 快照隔离

      • 事务始终从事务开始之前的已提交数据的快照中进行读取
      • 只有在没有其他具有重叠的 [start..commit] 间隔的已提交事务写冲突时，才能提交
        • 第一个提交者获胜

      一个以快照隔离方式运行的事务，只对自身开始时的数据版本进行操作， 不受在这个时间点后发生的其他事务对该数据的改变的影响。当事务开始时，从一个单调递增的计数器中得到一个开始时间戳，当成功提交时得到一个终止时间戳。对于一个事务 T 而言，只有当具有与 T 重叠的开始/结束时间戳的其他事务不去写事务 T 要写的数据时，事务 T 才 会提交。这种隔离模型更依赖于多版本并发的实现，而不是锁机制。当然，在支持快照隔离的系统中锁方案可以共存。

    • 读一致（补充）

      • Oracle 定义的一种 MVCC，但和快照隔离存在一些差异
      • 每个 SQL 语句（一个事务中会有很多 SQL 语句）会看到语句开始之前最近的已提交数据版本。
      • 对于需要从游标处取数据的语句，游标取值的版本以它打开的时间为准
      • 通过保存元组的多个逻辑版本来实现
        • 一个事务可能引用一个元组的多个版本数据
        • 但并不保存每一个可能需要的版本，它只存储最近的版本
        • 当需要一个旧版本的数据时，通过对现有版本依据日志记录进行回滚处理来得到旧版本
      • 写锁决定事务修改的顺序
        • 两个事务需要写同一个数据项时，第二个提出写请求的事务将等待第一个提出写请 的事务完成后才能进行自己的写操作
        • 相对而言，在快照隔离中，第一个已提交的事务（而不是第一个提出写请求的事务）将首先写数据

异常情况（补充）
#

一致性明确了哪些行为是正常的，而隔离级别则相反，它指出了异常情况并如何防止这些异常情况发送。

  • 脏写（Dirty Write）

    • 一个事务另一个正在运行中的事务尚未提交的值

  • 脏读（Dirty Read）

    • 一个事务读取了另一个事务尚未提交的值

  • 不可重复读（Non-Repeatable Read, Fuzz Read）

    • 在一个事务中查询一个值两次，两次查询返回不同的结果

  • 幻读（Phantom Read）

    • 事务执行一个谓词查询时，其他事务在中间插入或删除了匹配为此的数据

  • 更新丢失（Lost Update）

    • 两个事务查询同一个值，并且都试图修改同一个值
    • 其中一个事务提交时另一个事务并不知道，当另一个事务提交时覆盖了第一个已提交事务的值

  • 读偏斜（Read Skew）

    • 读取的数据一致性约束被破坏
    • 一致性约束通常由业务层面定义

  • 写偏斜（Write Skew）

    • 并发事务读取了相同的数据集
    • 随后修改了不相关的数据集导致数据一致性约束被破坏

这真的有关系吗？
#

  • 现实世界并不那么并发
  • 许多公司只依赖于读取已提交
  • 但是恶意攻击者可以引起并发性
    • Flexcoin
      • 允许用户通过在帐户之间转移货币来创造资金的比特币交易所
      • 2014年遭受攻击，365,000英镑被盗
      • 交易所完全崩溃
    • Poloniex
      • 并发提款未正确隔离，允许用户超支
      • 安全审计没有注意到负余额
      • 12.3%的交易所资金被盗，损失分摊给用户
    • Warszawski & Bailis 2017: ACIDRain
      • 自动识别Web应用程序中的一致性违规
      • 例如，购买一张礼品卡，然后无限次地使用它
      • 例如，在结账过程中购买一支笔，将笔记本电脑添加到购物车中，获得一台免费笔记本电脑
      • 在50%以上的电子商务网站中发现了漏洞
        • 弱数据库隔离默认值
        • 不正确使用事务范围
        • 完全不使用任何事务
    • Chase银行的信用卡奖励系统
      • 允许在余额之间并发转账以创建价值7万美元的旅行券。
      • 可兑换为现金！

一致性最初源于多线程共享内存模型，在分布式系统中，一致性更多的描述的是对单个值原子读写。隔离级别往往在数据库中使用。对于一个支持满足 ACID 隔离级别的事务来说，一致性是微不足道的。但是当分布式 + 数据库时，一致性和隔离级别就需要同时考虑了。

权衡
#

  • 理想情况下，我们希望实现总可用性和线性一致性
  • 一致性需要协调
    • 如果允许任意顺序，我们就不需要做任何工作！
    • 如果我们想要禁止某些事件顺序，我们就必须通过交换消息
  • 协调通常伴随着代价
    • 更强的一致性意味着更慢的性能
    • 更强的一致性更容易推理
    • 更强的一致性可用性更低

可用性和一致性
#

  • CAP定理：Linearizability OR total availability
  • 但是，还有更多！

    • Bailis 2014年的论文： Highly Available Transactions: Virtues and Limitations

    • 其他定理不允许 totally 或 sticky 可用性…

      • Strong serializable
      • Serializable
      • Repeatable Read
      • Cursor Stability
      • Snapshot Isolation

    • 你可以实现 sticky 可用性…

      • Causal
      • PRAM
      • Read Your Writes

    • 你可以实现 totally 可用性…

      • Read Uncommitted
      • Read Committed
      • Monotonic Atomic View
      • Writes Follow Reads
      • Monotonic Reads
      • Monotonic Writes

Harvest 和 Yield
#

  • Fox＆Brewer, 1999年的论文： Harvest, Yield, and Scalable Tolerant Systems
    • Yield：完成请求的概率
    • Harvest：在响应中反映的数据比例
    • 例子
      • 在搜索引擎中，节点故障可能导致某些结果丢失
      • 更新可能反映在部分节点上
        • 考虑一个分区的AP系统
        • 可以写入某些人无法读取的数据
      • 流媒体降低视频质量以保持低延迟
    • 这并不是违反安全不变量的借口
      • 只是帮助你量化你可以超出安全不变量的程度
      • 例如，“99%的时间，你可以读取90%的先前写入”
    • 强烈依赖于工作负载、硬件、拓扑结构等因素
    • 可以根据每个请求的需要调整收获和产出
    • “请在10毫秒内尽可能多地返回”
    • “我需要全部数据，但我明白不可能无法回答”

混合系统
#

  • 因此，你有各种选择！
    • 你的基础设施不同部分可能具有不同的需求
    • 在满足你的约束条件下，选座最弱的模型
      • 但考虑概率边界；可见性延迟可能是限制因素
      • 参考Dynamo Quorums中的概率上的有界陈旧度(Probabilistically Bounded Staleness PBS)

        Berkely 有关 PBS 的解释: While eventually consistent data stores make no guarantees about the recency of data they return, we can model their operation to predict what consistency they provide. We call this Probabilistically Bounded Staleness, or PBS.

  • 不是所有数据都是相等的
    • 大数据通常不那么重要
    • 小数据通常至关重要
    • 用户操作通常要求线性化，社交动态一般因果一致

回顾
#

可用性是度量操作成功的比例。一致性模型是规定操作何时发生的规则。更强的一致性模型通常以性能和可用性为代价。接下来，我们将讨论从弱一致性到强一致性的不同构建系统的方法。

尽量避免一致性
#

CALM 猜想
#

  • 一致性视为逻辑单调性
    • 如果你能证明一个系统在逻辑上是单调的，那么它是无协调的 (coordination free)。
    • “协调"是什么鬼？
    • 同样，“单调性"是什么鬼？
  • 简单来说，单调性是指没有撤销操作
    • 根据部分信息进行推导的结果不会被新信息所否定
    • 关系代数和不带否定的数据记录都是单调的
  • Ameloot等人，2011年的论文： Relational transducers for declarative networking
    • 定理表明，在进程之间不知道网络范围的无协调网络中，只能计算数据记录中的单调查询
      • 这篇论文不容易理解
    • “无协调"并不意味着没有通信
      • 即使任意分区，算法仍然成功
  • 从实际角度来看
    • 尽量将问题表述为仅向系统中添加新事实
    • 当基于当前已知信息计算新事实时，你能否确保该事实永远不会被撤销？
    • 考虑特殊的"封存事实 (sealing facts)"，用于标记一组完整的事实 (fact as complete)
    • 这些"只增长 (grow-only)“的算法通常更容易实现
    • 可能的折衷：不完整的读取
  • Bloom Language
    • 通过流分析进行无序编程
    • 可以告诉您哪里需要协调

[Consistency Analysis in Bloom: a CALM and Collected Approach](Consistency Analysis in Bloom: a CALM and Collected Approach) 这篇论文基于 CALM 原则将分布式一致性的思想与逻辑单调性的程序测试组合，引入了Bloom，一种适用于高级一致性分析并鼓励无序编程的分布式编程语言。论文将 Bloom 作为一种 DSL 在Ruby中提供了一个原型实现。论文提出了一种程序分析技术，用于识别 Bloom 程序中的顺序点：程序员可能需要在这些代码位置注入协调逻辑以确保一致性。论文通过两个案例研究来说明这些思想：一个简单的键值存储和一个分布式购物车服务。

Gossip
#

  • 消息广播系统

  • 用于集群管理、服务发现、健康检查、嗅探 (sensors)、CDN等

  • 一般具有较弱的一致性/较高的可用性

  • 全局广播

    • 向每个其他节点发送消息
    • $O(nodes)$

  • Mesh 网络

    • 传染病模型
    • 转发给邻居节点
    • 传播时间与最大自由路径(max-free-path)的数量级相当

  • Spanning trees

    • 不使用网状结构，而使用树状结构
    • 跳到中继到其他连接器节点的连接器节点
    • 减少多余的消息
    • 减少延迟
    • Plumtree（Leit ̃ao、Pereira和Rodrigues，2007年的论文： Epidemic Broadcast Trees）

    消息复杂性是指在通信系统中传递消息所需的计算和通信资源的量。它通常衡量了在进行特定任务或操作时所需的消息数量和传输成本。较低的消息复杂性表示在完成相同任务时需要较少的消息，而较高的消息复杂性则表示需要更多的消息。

    在论文中，作者提到了基于树的广播方法在稳态下具有较小的消息复杂性，这意味着在正常运行状态下，使用树结构进行广播所需的消息数量相对较少。另一方面，作者提到了Gossip或epidemic协议具有较高的消息复杂性，这意味着在该协议下，广播所需的消息数量较多。

    综合两种方法的特点，论文提出了一种集成广播方案，旨在在保持较低的消息复杂性的同时提供较高的弹性和可靠性。该方案使用低成本的方法构建和维护广播树，并利用gossip覆盖网络的其他链接进行快速恢复和加速树的恢复。通过这种方式，论文中的方案可以在面对故障和大规模问题时仍保持较高的可靠性，同时减少了广播过程中所需的消息数量和传输成本。

    该算法在 rika 数据库中实现和使用。

  • Push-Sum 等

    • 对来自每个接收数据的节点进行求和
    • 将求和结果广播给一个随机对等节点
    • 扩展到最小值、最大值、平均值
    • 有助于实时监控、限流、路由、识别集群热点

CRDT
#

  • 可以收敛的无序数据类型
    • Counters, sets, maps 等
  • 可以容忍重复、延迟和重排序
  • 与顺序一致性系统不同，没有"唯一的真相源 (single source of truth)”

    顺序一致性的系统需要定序

  • 但与朴素的最终一致性系统不同，不会丢失信息
    • 除非明确使它们丢失信息
    • 我们将此属性称为 “merge”
  • 在高度可用的系统中工作良好
    • Web/移动客户端
    • Dynamo
    • Gossip
  • INRIA：Shapiro、Preguiça、Baquero、Zawirski，2011年的论文：“A comprehensive study of Convergent and Commutative Replicated Data Types”
    • 由数据类型 $X$ 和合并函数 $m$ 组成，满足：
      • 结合律：$m(x1, m(x2, x3)) = m(m(x1, x2), x3)$
      • 交换律：$m(x1, x2) = m(x2, x1)$
      • 幂等性：$m(x1, x1) = m(x1)$
  • 容易构建。容易推理。解决了各种头疼问题。
    • 通信失败了？重新尝试！它会收敛！
    • 消息乱序到达了？没关系！
    • 如何同步两个副本？只需要合并！
  • 缺点
    • 某些算法需要顺序，并且无法用CRDT表示
    • 读到过时(stale)的数据
    • 空间成本较高

HATs
#

  • Bailis、Davidson、Fekete等人，2013年的论文：“Highly Available Transactions, Virtues and Limitations”
    • 可以保证从任意副本都能获得响应
    • 低延迟（比串行化协议快1-3个数量级！）
    • 读已提交
    • 单调原子视图
    • 对于可交换/单调系统非常有效
    • 用于多项更新的外键约束
    • 有限的唯一性约束
    • 可以确保在任意有限延迟下收敛（“最终一致性”）
    • 在 geo-分布式系统中是很好的选择
    • 可与更强的事务系统结合使用
    • 另请参阅：COPS、Swift、Eiger、Calvin等

好吧，我们需要共识，现在怎么办？
#

共识问题
#

  • 进程的三个角色

    • Proposers：提出值
    • Acceptors：选择一个值
    • Learners：学习选择到的值

  • Acceptor 的分类：

    • $N$ 个 acceptor
    • $F$ 个允许失败的 acceptor
    • $M$ 个恶意 acceptor

  • 三个不变量：

    • 非平凡性（Nontriviality）：只能对用户发出的值进行学习
    • 安全性（Safety）每个位置最多只能对一个值取得共识
    • 活性（Liveness）：如果一个 proposer $p$、一个 learner $l$ 以及一组非故障的 $N-F$ 个 acceptor 能够彼此通信，且 $p$ 提出一个值，$l$ 最终会学习到该值

  • 许多类别的系统与共识问题是等价的

    • 因此，我们在这里的任何证明也适用于这些系统
    • 锁服务
    • 有序日志
    • 复制状态机

  • FLP 定理告诉我们在异步网络中共识是不可能的

    • 在特定的时间 kill 一个进程，可以破坏任何共识算法
    • 不过，情况并没有你想象的那么糟糕
    • 实际上，网络在大多数情况下能够达成共识
    • 此外，FLP定理假设进程是确定性的
      • 真实的计算机不是确定性的
      • Ben-Or在1983年的研究中指出：“Another Advantage of free choice”
        • 非确定性算法可以实现共识

  • Lamport在2002年提出了: tight bounds for asynchronous consensus

    • 至少有两个 proposer 或一个恶意 acceptor 时, $N > 2F + M$
      • “需要多数派 (majority)”
    • 至少有两个 proposer 或一个恶意 proposer 时，学习一个提议至少需要2个消息延迟。

  • 下面是一个实际上可行的界限

    • 在稳定的集群中，只需要与大多数节点进行一次往返通信即可达成共识。
    • 在集群转换期间可能需要更多的通信往返。

Paxos
#

  • Paxos 是共识算法的黄金标准
    • Lamport在1989年提出的 The Part Time Parliament 一文中
      • 描述了一个想象中的希腊民主制度
    • Lamport 2001 - Paxos Made Simple
      • “Paxos算法用于实现容错分布式系统一直被认为很难理解，也许是因为最初的表述对许多读者来说像希腊语一样晦涩难懂。事实上，它是最简单、最明显的分布式算法之一……最后一节解释了完整的Paxos算法，它通过将共识直接应用于状态机方法来构建分布式系统，这一方法应该是众所周知的，它可能是被分布式系统理论研究引用最多的文章。”
    • Google 2007 - Paxos Made Live
      • 记录了他们在生产环境中使用Chubby（Google的锁服务）的经验。
    • Van Renesse 2011 - Paxos Made Moderately Complex
      • 需要进行优化
      • 提供伪代码会有帮助
      • 一页伪代码转化为几千行C++代码
  • Paxos 实现独立提案的共识
  • 通常部署在多数派的配额上，例如5个或7个节点
  • 有几种优化方法
    • 多Paxos（Multi-Paxos）
    • 快速Paxos（Fast Paxos）
    • 广义Paxos（Generalized Paxos）
    • 并不总是清楚应该使用哪种优化方法，以及哪些方法可以安全地组合使用
    • 每种实现都使用了稍微不同的变种
    • Paxos实际上更像是一个算法家族，而不是一个明确定义的单一算法
  • 在各种生产系统中使用
    • Chubby
    • Cassandra
    • Riak
    • FoundationDB
    • WANdisco SVN Server
  • 新的研究：Paxos多数派不一定要占多数，可以优化第二阶段的多数派(quorum)快速达成 Howard, Malkhi, and Spiegelman。
    • 目前我们还不确定如何使用这项技术
    • 持久性仍然需要分布式支持

ZAB
#

  • ZAB 是 Zookeeper 实现的原子广播协议
  • Junqueira, Reed, 和 Serafini在2011年提出的 Zab: High-performance broadcast for primary-backup systems
  • 与Paxos不同
  • 提供顺序一致性（写入线性化，滞后的顺序读取）
    • 这对于ZooKeeper客户端通常需要快速的本地读取读取非常有用
    • 但也有一个SYNC命令，可以保证实时可见性
    • （SYNC + op）还可以实现线性化读取
  • 同样需要 quorum，例如5个或7个节点

Humming Consensus
#

  • Humming Consensus是用于管理分布式系统重新配置的元数据存储
  • 稍微类似 CORFU 的复制日志
  • 另请参阅：链式复制（ chain replication）

Viewstamped Replication
#

  • 被描述为复制协议，但也是一个共识算法
  • 事务处理加上视图更改算法
  • 可以保证大多数已知值会在未来存活下来
  • 我不知道是否有任何生产系统使用，但我相信肯定有的
  • 与Paxos一起，为Raft在某些方面提供了灵感

Raft
#

  • Ongaro和Ousterhout在2014年提出的: In Search of an Understandable Consensus Algorithm
  • Lamport说它很简单，但我们仍然难以理解Paxos
    • 如果有一个我们可以真正理解的共识算法会怎样呢？
  • Paxos是针对独立决策的，而我们想要的是状态机
    • Raft通过维护状态机转换的复制日志来实现
  • 还内置了群集成员身份转换，这对于实际系统非常关键
  • Raft非常新颖，但我们已经对核心算法进行了Coq证明
  • 可用于编写任意顺序或线性化状态机
    • RethinkDB
    • etcd
    • Consul

分布式事务
#

  • 迭代式共识使我们可以就操作的单一总排序达成一致
  • 事务之间存在不必要的阻塞，这些事务本可以独立执行
  • 我们如何提高性能？
  • 分布式事务架构
  • 单一写者
    • 所有更新通过单个队列进行，读取者在快照上执行
    • 通常涉及某种持久化数据结构
    • 可串行化到严格一致性（strict-1SR）
    • 参考 Datomic
  • 好，但如果有多个写者呢？
    • 一般来说，有几个分片，每个分片运行一个受共识支持的状态机
    • 某种用于跨分片事务的协议
  • 独立分片
    • 是通用事务的一种中间步骤
    • 不允许跨分片事务
    • 只运行一组独立的共识状态机
    • 可以添加一个全局共识组来处理跨分片事务
      • 但吞吐量有限！
    • 参考 VoltDB
  • Percolator
    • 在可线性化的分片上使用快照隔离
    • 时间戳Oracle分配顺序事务时间戳（使用共识）
    • Read timestamp, read from leaders, prewrite, commit timestamp, commit, finalize
    • 14 跳，可能涉及跨数据中心通信
    • 参考 TiDB
  • Spanner
    • “外部一致性”（严格一致性吗？）
    • 通过使用GPS+原子时钟加快时间戳分配
    • 基本上是 Paxos 共识组之上的 2PC
      • 锁住 paxos leader
      • 选择一个Paxos 共识组作为整个事务的提交记录
    • 固定延迟下限以确保时间戳的单调性
    • 参考 Yugabyte DB
    • 参考 CockroachDB
  • Calvin
    • 使用共识对日志中的事务进行排序
    • 对日志进行分片以实现任意高吞吐量
    • 定期封存日志窗口(seal log window) 并将事务应用于分片
    • 应用程序无需通信！
    • 严格一致性（strict-1SR）
    • 1个跨数据中心的往返时间，本地通信需要多跳
    • 可扩展的吞吐量
    • 最小延迟下限
    • 事务必须是纯的，需要预先表达
      • 可以通过协议扩展使其变为交互式
    • 参考 Fauna

      Calvin 使用了一种叫确定性事务的协议.

回顾
#

只添加事实而不撤销它们的系统需要较少的协调来构建。我们可以使用 Gossip 系统向其他进程广播消息，使用CRDT从对等节点合并更新，并使用HAT进行弱隔离的事务。串行化和线性化需要共识，我们可以通过Paxos、ZAB、VR或Raft获得共识。现在，我们将讨论不同规模的分布式系统。

Related

论文阅读笔记 - InfiniFS: An Efficient Metadata Service for Large-Scale Distributed Filesystems
·3 mins
论文 分布式系统 分布式存储
分布式系统全序和偏序关系: 以 Lamport 论文举例
·4 mins
分布式系统 数学
论文阅读: Analysis of Six Distributed File Systems
·5 mins
论文 分布式系统 分布式存储
论文阅读: Finding a needle in Haystack: Facebook’s photo storage
·2 mins
论文 分布式系统 分布式存储
论文阅读: The Hadoop Distributed File System
·4 mins
论文 分布式系统 分布式存储
mmap-sync: cloudflare 对于低延迟 IPC 的解决方案
·8 mins