导言#

本文作为分布式系统的复习，力求完成十章内容的重新学习，从而期望可以考点正常分数。

不过也不浪费时间，可以当某些实现方案的了解，方便以后设计上做 trade off 和参考。

比较重点的章节是第三、四、五、六这几章。

课程提纲和考试题型
第一章

分布式系统的构建原因

分布式系统的定义、特征

分布式系统举例

分布式系统面临的挑战

第二章

分布式系统体系结构模型 1.1 C/S、P2P两种不同结构 1.2 分层模型、层次化模型

交互、故障、安全三种基础模型

同步、异步两种不同的分布式系统

第三章

事件、进程历史概念

时钟漂移及产生原因

内部、外部物理时钟同步

时钟正确性含义

物理时钟同步的三种方法

逻辑时间、逻辑时钟

发生在先关系、并发关系及分布式系统中的事件排序

Lamport时钟、全序逻辑时钟及向量时钟

割集、割集的一致性、一致的全局状态概念

Chandy-Lamport快照算法

分布式调试（全局状态谓词的判断）

第四章

分布式互斥的含义

解决分布式互斥的方法：中央服务器、环、组播+逻辑时钟、Maekawa投票算法

分布式选举含义

解决分布式选举的方法：环、霸道

基本组播、可靠组播的区别

实现可靠组播的方法

共识、交互一致性及拜占庭将军问题含义

三个、四个拜占庭将军问题

paxos算法

第五章

事务的ACID特性

串行等价性的概念、充要条件及应用

事务的三种基本控制方法：锁、乐观方法、时间戳，它们的原理、实现、比较

第六章

分布式事务概念

原子提交协议的概念

单阶段原子提交协议原理及缺陷

两阶段提交协议（设计动机、基本思想、基本操作、过程描述、通信、性能、缺陷）

分布式事务的并发控制（锁方法）

分布式死锁产生原因及检测方法（集中、分布式）

两阶段提交协议的恢复

第七章

复制的概念、动机、基本要求

四种一致性（可线性化、顺序一致性、因果一致性、最终一致性）

复制的系统模型: 主动复制、被动复制

单拷贝串行化的概念、“读一个/写所有”方案原理、适用条件及本地验证方法

闲聊系统的两个保证、体系结构（含关键数据结构及作用）、基本操作

第八章

分布式文件系统的需求

文件服务体系结构，即三个组件、作用、接口，设计理念

NFS体系结构、NFS服务器操作、路径解析、缓存机制

AFS应用场景、设计理念、缓存机制、一致性

第九章

GFS设计动机、设计思想、体系结构

Master不存在性能瓶颈原因

读、写、添加操作流程

写操作一致（consistent）、确定（defined）含义及分析

添加操作一致（consistent）、确定（defined）含义及分析

第十章

一致性哈希算法

分布式哈希表主要思想

Chord原理、Hash表分布规则、基于Finger Table的路由技术

选择：20分判断题：20分其他类型合计60分（简答、分析、计算等）

第一章分布式的基本特征#

分布式系统的目标、定义、特点#

分布式系统的目标：资源共享 + 协同计算
分布式系统的定义：分布式系统是指把多个处理机通过网络互连而构成的系统，系统的处理和控制功能分布在各个处理机上。分为同构分布式系统和异构分布式系统。
分布式系统的特点：并发性、没有全局时钟、故障独立性

分布式系统举例#

web 搜索、大型多人在线游戏、金融交易、区块链系统、语音系统、数据库系统、AI 大规模训推

分布式系统的趋势#

泛在联网和现代互联网
移动和无处不在的计算
分布式多媒体系统
将分布式计算作为公共设施

分布式系统面临的挑战#

异构性、开放性、安全性、可伸缩性、故障处理、并发、透明性

我们可以用中间件+移动代码（代码直接移动到另一个环境执行，我理解类似 slurm）的方式解决异构性的问题。

故障处理的流程则主要是

检测故障
屏蔽故障
故障容错
故障恢复
冗余策略

透明性又分为下面的几种

访问透明、位置透明、并发透明、复制透明、故障透明、移动透明、性能透明、扩展透明。

第二章系统模型#

主要考察的都是一些基本概念，如下：

物理模型：从计算机和所用网络技术的特定细节中抽象出来的分布式系统底层硬件元素的表示。
结构模型：构成系统各部分的位置、角色和它们之间的关系，它定义了系统的各组件之间相互交互的方式以及它们映射到下面的计算机网络的方式。分为客户/服务器结构和对等结构:
1. C/S 结构：Client 主动发起通信请求，Server 被动等待通信的建立，我们可以横向扩展Server，还可以增加 Proxy Server 做缓存，还可以用移动代码和移动代理。缺点也是伸缩性差。
2. 对等结构：系统由一堆边端设备构成，既是服务器又是客户端，用户可以意识到彼此的存在，构成一个虚拟或实际的整体。缺点是管理难度大。
在构建在相对原始的体系结构元素之上，提供组合的、重复出现的结构。
1. 分层：一个复杂的系统被分成若干层，每层利用下层提供的服务。在分布式系统中，等同于把服务垂直组织成服务层。硬件的上面是平台，平台的上层是中间件，中间件的上层是应用。
2. 层次化模型则与分层体系结构互补，是一项组织给定层功能的技术，比如 web 应用就采用了层次化模型。
基础模型：对体系结构模型中公共属性的一种更为形式化的描述，这里需要补充描述
1. 安全模型：提供依据，以此分析系统可能受到的侵害，并在设计系统时防止这些侵害的发生，保证在存在各种威胁的情况下通信的安全。
2. 故障模型：定义可能出现的故障的形式，为分析故障带来的影响提供依据。分为遗漏故障、随机故障、时序故障。
3. 交互模型：进程之间通过消息传递进行交互，实现系统的通信和协作功能，处理消息发送的性能问题，解决在分布式系统中设置时间限制的难题。
交互模型的变体：
1. 同步分布式系统：有严格的时间限制假设
2. 异步分布式系统：没有严格的时间限制假设

第三章时间和全局状态#

基础概念#

我们首先介绍一系列基础概念：

在每个进程在单处理器上执行，处理器之间不共享内存，进程之间仅能通过消息进行通信的条件下，我们把进程状态定义为所有变量的值及相关的本地操作系统环境中的对象的值。

在此基础上，我们定义了事件，事件指一个通信动作或进程状态转换动作。

进程历史则指在进程中发生的一系列事件，按发生先后排序。

在这些基础概念上，我们引入了一系列方法，下面主要讨论这些方法。

重点主要分成三个部分：

同步物理时钟
逻辑时间和逻辑时钟
全局状态

同步物理时钟#

计算机时钟的硬件实现是用晶体固定的震荡频率，我们的震荡频率有可能受电源稳定性和环境温度等因素影响，这就会带来时钟偏移。

那么我们如何确认一个正确的时钟呢？这就涉及到时钟同步。同步分为内部同步和外部同步。

很容易理解的，我们外部如果有权威的时钟源，同步的误差在 D 内是准确的。

那么此时内部同步要用到 2D 的同步误差。

既然误差不可避免，那就没有严格的正确，所以我们对时钟的正确性也就得有一个定义。

时钟的正确性可从以下三个层面进行定义：

基于漂移率：时钟的漂移率在一个已知范围内，即对任意时间点 $t < t'$ ，满足： $(1 - \rho)(t' - t) \leq H(t') - H(t) \leq (1 + \rho)(t' - t)$ 其中 $\rho > 0$ 为最大允许漂移率， $H(t)$ 表示物理时钟在真实时间 $t$ 时的读数。
基于单调性：时钟值随真实时间严格递增，即： $t' > t \implies C(t') > C(t)$ 其中 $C(t)$ 表示逻辑时钟或系统时钟在真实时间 $t$ 的值。
基于混合条件：同时满足单调性、漂移率有界，并允许在同步点发生跳跃前进，以实现快速收敛或校准。

物理时钟同步主要包括了三种方法，下面依次介绍

Cristian 方法#

方法的条件是存在时间服务器，作为外部事件源。并且消息往返时间相较于我们要求的精度比较短。协议是发送消息给外部时间服务器，外部时间服务器回复消息，最后我们根据消息最小传输时间修正我们实际的物理时钟。

那么若消息的最小传输时间为 $min$ ，则精度为： $Tround/2 – min$ 。

核心误差就来自往返时延不是最小且两条方向时延不对称。

Berkeley 算法#

方法的条件是参与者始终精度相近，然后主机周期轮询从属机器时间，然后取对应的容错平均值，发送每个从属机的调整量。

相当于协调者负责拿到所有机器的时间信息，再统一帮大家调成一个时间的。

NTP 协议#

当然，在现代用的比较多的是 NTP 协议，他的主服务器实现外部同步，使得和 UTC 同步，然后考冗余链路和扩展等避免干扰和漂移率的影响。

常见有三种模式：

组播模式，本地 LAN 时延很低的时候使用，效率高但是准确率低
CS 模式，与 Cristian 算法相近，准确性更高
对称模式，具体介绍如下。

NTP 对称模式用四个时间戳来实现双向测量

结合这张图来把 NTP 的对称模式说清楚：

图里 A、B 互为对等体，每一轮交换会产生 4 个时间戳：
$t_1=T_{i-3}$ （A 发送）， $t2=T_{i-2}$ （B 接收）， $t_3=T_{i-1}$ （B 发送回去）， $t_4=T_i$ （A 接收）。 NTP 用它们估计偏移与往返时延（这里的时钟偏移因为每个参与者参与了两次，被抵消了）：

\text{offset } o_i=\frac{(t_2-t_1)+(t_3-t_4)}{2},\qquad \text{delay } d_i=(t_4-t_1)-(t_3-t_2)

我们还可以算出来对应偏移的误差：

结论 $o = o_i + (t'-t)/2$ 的来龙去脉是这样的（符号对应图里的 $T_{i-3},T_{i-2},T_{i-1},T_i)$ ：

设定

两个时钟相差常数 $o$ ： $C_b - C_a = o$ （在一次往返期间漂移可忽略）。
单向链路时延：A→B 为 $t$ ，B→A 为 $t'$ （可能不相等）。
事件时间戳：
A 发送 $m$ 时为 $t_1=T_{i-3}$ （A 时钟）；B 接收为 $t_2=T_{i-2}$ （B 时钟）；
B 回发 $m'$ 时为 $t_3=T_{i-1}$ （B 时钟）；A 接收为 $t_4=T_i$ （A 时钟）。

写出两条等式

A 到 B：B 的读数 = A 发送时刻 + 传播时延 + 时钟偏移

t_2 = t_1 + t + o \quad\Rightarrow\quad T_{i-2}-T_{i-3}=t+o

B 到 A：A 的读数 = B 发送时刻换算到 A 的时间 + 传播时延 $t_4 = (t_3 - o) + t' \quad\Rightarrow\quad T_i-T_{i-1}=t' - o$

把两式相加并整理

(T_{i-2}-T_{i-3}) + (T_{i-1}-T_i) = (t+o) + (o - t') = 2o + (t - t')

\Rightarrow\quad o = \frac{(T_{i-2}-T_{i-3}) + (T_{i-1}-T_i)}{2} + \frac{t' - t}{2}

把

o_i {=} \frac{(T_{i-2}-T_{i-3}) + (T_{i-1}-T_i)}{2}

看作对称链路假设（ $t=t'$ ）下的偏移估计，就得到

\boxed{o = o_i + \frac{t'-t}{2}}

逻辑时间和逻辑时钟#

Lamport 时钟#

节点具有独立时钟，缺乏全局时钟，后发生的事件反而可能会更早，主要是因为物理时钟的完美同步是做不到的，但是对事件排序又在许多情况下不得不用。

这里得用逻辑时钟：众多应用只要求所有节点具有相同时间基准，该时间不一定与物理时间相同。

不进行交互的两个进程之间不需要时钟同步，但是所有进程对事件排序又要达成一致。

所以我们引入了 Lamport 时钟。

这基于两个基本事实：

同一进程中先后两个事件存在前后关系
任一消息的发送事件发生在该消息的接收事件之前

那么也就是说，我们有两种改变时钟的源：

外部发送事件，我们接收事件的时间戳一定要大于外部发送事件
进程内部前置事件，我们的后发生事件的时间戳一定大于前置事件

可以参考这个练习：

Lamport 全序时钟#

我们发现，两个不同进程的时间戳可能相同，但是时间不一样，我们可以加一个进程的标识，这样我们就可以基于进程号做比较。不过这种情况没啥物理意义，人为给定了个顺序罢了。

向量时钟#

然后我们引入了向量时钟，我个人的理解是这样的：

上面讲到有两种改变时钟的源。我们把他们独立核算。

我们可以对 i 进程的 j 进程来源信息取向量时钟 v[i][j] ，对于 v[i][i] 我们核算进程内部前置事件，其他的用来核算外部事件，如果我们收到进程 j 对应消息，我们当然要更新对应的外部事件，但是因为只是一个收到消息的内部前置事件，所以我们要更新合并外部消息的其他时间戳（取本地远程最大值），这个相当于我不仅拿到了这个进程的信息，还拿到了这个进程知道的外部最大的信息，然后我们的 v[i][i]++ 即可（要先合并，因为外部对“我”的判断可能比“我”晚，不过一般不存在顺序的问题）。

下面是流程的一个解析

初始化：每个进程 i 的 V[i] 全 0。
本地事件/发送：V[i][i]++，消息带上 V[i]。
接收：V[j] := max(V[j], V_msg)，然后 V[j][j]++。
因果判断：e → e' 当且仅当 V(e) < V(e')（逐分量 ≤ 且至少一处 <）。

这个向量时钟也可以证明等号和并发性。

全局状态#

一致割集#

有的时候，有些决策要我们知道所有进程的状态才可以做。

比如垃圾回收和死锁检测，我们就会要有个全局状态来做个类似快照，毕竟我们每个程序都是静态去处理类似这种图的算法。

那么我们的全局状态要满足什么条件呢？

首先肯定是不能有没有因的事件，但是可以有因无果，只要满足这个条件，就可以看作一个全局状态。所以我们就可以用一个割集来表示。

我们可以参考上面的图片来看，不一致的割集有 (0,2) 这个果，却没有 (1,1) 这个因。反之，另一个则是对齐的。

线性化走向和可达#

我们还有一个概念，叫做走向，就是往前走一步的可能执行过程，这个不一定是一致的，不过如果所有的状态都是一致的，那么这是一个线性化走向，如果某个状态到某个状态中存在线性化走向，则说这两个状态 S 可达状态 S’。

快照算法#

既然我们需要一个一致的全局状态来做死锁检测或检查点恢复，但又不能暂停整个系统（否则就失去了“分布式”的意义），那么如何在系统持续运行的过程中“拍下”一个逻辑上一致的快照呢？

Chandy 和 Lamport 给出了一套优雅的解决方案——基于 marker 消息的分布式快照算法。

Chandy-Lamport 快照算法
算法的流程如下，

发起快照

任一进程 Ps 决定发起快照时：

记录自身的本地状态 Ss 。

向其所有邻居进程发送 marker 消息（不携带应用数据）。

响应 marker 消息

当进程 Pi 首次收到 marker 消息（从某条入通道）时：

若尚未记录本地状态：

立即记录本地状态 Si ；

为每条入通道开启“记录模式”（即缓存此后收到的消息）；

向所有邻居发送 marker 消息。

此后，对于每条入通道 c ：

在收到该通道的 marker 之前，将所有收到的消息加入通道状态 chan_state(c) ；

一旦收到该通道的 marker，关闭该通道的记录模式。

快照完成

当所有进程都已记录本地状态，且所有入通道都已关闭记录模式时，快照完成。

每一个进程的地位其实是等同的，所有人收到第一个 marker 消息以后都要告知所有的邻居自己收到了 marker 消息，收到谁的 marker 消息以后，相当于这个进程的快照我已经拿到了。

分布式调试#

我们有了快照，可以不暂停整个系统的情况下拿到一致的全局状态。有的时候，我们还要判断某个命题是否为真，在单机系统中，我们很容易判断某个条件是否为真，但是多机环境下就不一定了。

因此我们要对全局状态有一个全局状态谓词，如果：

存在一个一致的全局状态 $S$ ，使得在历史 $H$ 的某一个线性化走向中，系统经历了这个状态 $S$ ，并且 $\phi(S)=True$ 。那么这就是 possibly $\phi$
对于历史 $H$ 的所有线性化走向 $L$ ，都存在一个在 $L$ 中经历的一致全局状态 $S$ （不同 $L$ 可对应不同 $S$ ），使得 $\phi(S)=True$ 。

我们引入一个监控器进程用来收集进程状态信息，每个进程状态 $s_i$ 附带向量时钟 $V(s_i)$ ，供监控器构建全局状态 $S = (s_1, ..., s_N)$

一个全局状态 $S = (s_1, s_2, \dots, s_N)$ 是一致的，当且仅当： $\forall i,j \in \{1,2,\dots,N\}, \quad V(s_i)[j] \geq V(s_j)[j]$

有了这些信息，我们就可以解题了，例题如下

因为一个事件只会增加一个的逻辑时钟，对所有的可能的一致的全局状态，逻辑时钟之和总是在线性递增（本质上就是历史的事件总数），所以我们的设计上将多个进程的逻辑时钟之和作为路径的代表，就可以画出类似上图的右图。

然后我们的通信事件，天然地为画图提供了约束，我们就可以利用右边那个约束后画出来的图来进行分布式调试的分析。

第四章协调与协定#

分布式互斥#

我们希望仅基于消息投递，实现对资源的互斥访问，这就是我们的分布式互斥。

我们假设这是一个异步系统，无故障进程且消息投递可靠。

我们假设有这么几种应用层协议，包括 enter() resourceAccesses() exit() 这些，相当于 tryLock() doSomething() unlock()。

基于这些协议，我们可以对相关实现做性能评价，包括：

带宽消耗
客户延迟（从 tryLock 到实际拿到，从 unlock 到实际解锁）
同步延时（切换进程的时间）

我们还有这些对分布式互斥的要求

安全性：临界区内最多单进程
活性：保证进入临界区和离开临界区的请求最终成功执行
顺序：希望实现公平的进入临界区

那么我们提供了几种常见的方法，去满足这些要求的分布式互斥。

中央服务器算法#

实现类似下图

相当于对于我们的共享区域，实际上服务器负责处理客户端的请求，这样就能保证客户端分布式互斥的安全性和活性，但是不满足对应的顺序要求，相关性能指标评价如下：

带宽消耗和客户延迟上，进入临界区要有两个消息，释放只需要一个消息。

同步延迟上，要有一个消息的往返时间。

Ring-based 算法#

实现类似下图，Ring-Based 算法将所有参与进程组织成一个逻辑环（Logical Ring），每个进程知道它的后继节点（Successor）。令牌（Token）在环中单向传递（通常是顺时针或逆时针）。只有持有令牌的进程才能进入临界区。当它使用完资源后，把令牌传给下一个进程。

这个的带宽消耗是一直都在的，但是运气好，我们的客户延迟可以为 0，但是运气不好，则要为 N 个消息。同步时延最小为 1，但是最大为 N，就是恰好我用完投递出去了，我又要用临界区的资源。这样没有中心服务器，但是依旧不能保证顺序。

组播+逻辑时钟#

该算法为每个进程维护一个状态变量 state，有三种值：

RELEASED：空闲，未请求临界区
WANTED：已请求，正在等待所有回复
HELD：已获得所有许可，正在执行临界区

并用逻辑时间戳 + 进程 ID 构成全序关系 <T, p> 来决定谁优先。

所有进程一开始肯定都处于 Released 的状态，如果发现我们需要，那就改成 wanted，随后我们把请求组播给所有进程，所有进程也能拿到我们的时间戳，直到所有人都回复了我们。

我们如果收到了消息，这时候我们应当做的是检查本地状态，如果我本地是持有或者我想要且我要的比这个消息早，我就不回~（非常像在 slurm 节点申请卡的情况啊~）。直到我用完了，这个时候我要更改本地状态，让新人不必排队，再一个一个回复之前没回的消息。

这个时候，满足我们的安全性，活性和顺序要求。

不过组播的带宽成本还是不低，需要一组组播， $2 \times (N - 1)$ 的带宽成本。

客户延迟就是 1 round-trip 而同步时延就是一个回复的消息时间。

Maekawa 投票算法#

事实上，上面那个算法的主要缺点是我们的带宽成本太高了。所以我们设计了下面的算法

每个进程 pi 都有一个对应的“选举集” Vi，它是整个进程集合 {p1, p2, ..., pn} 的一个子集，这时候满足四个条件：

选举集包含 pi
选举集两两交集不为空
选举集大小相同，都为 K
每个进程出现在 M 个选举集中

实践上，为了公平，往往取 M = K，K = $[\sqrt{N}]$ 。

只要选举集都同意了，我就可以拿到资源，但是构造选举集比较麻烦。

除此以外，还可能出现死锁。

这个时候，我们可以类似组播＋逻辑时钟的方法，加一个时间戳，维护我们请求的顺序，就不会出现死锁了。这时候还满足了分布式互斥的顺序要求。

分布式选举#

我们可以发现之前的算法实现中很多地方要有一个特别的进程来扮演特殊的角色，比如内部同步的 berkeley 算法，那么我们怎么选出这个进程呢？

这就涉及到分布式选举。选择一个特别的进程来扮演特殊的角色的算法就叫选举算法，一个进程如果启动了选举算法的一次运行，那么就称为召集选举。如果进程参与了某次选举算法的运行，那么这个进程就是这个选举算法的参与者，如果没有参加任何选举算法，那就是非参与者。之前在逻辑时钟上，我们为了有全序关系，给进程增加了进程标识符，在这里，由于选举算法的需要，我们依然依赖这么一个实现。

分布式选举有如下的要求

对任意进程 $P_i$ ，其本地选举变量 $\text{elected}_i$ 满足：

\text{elected}_i = \bot \quad \text{或} \quad \text{elected}_i = P_{\max}

其中：

$\bot$ 表示“未选举出领导者”，
$P_{\max}$ 表示所有存活进程中具有最大 PID 的进程。

这是安全性，也就是要么选不出来，要么能选出唯一。

只要系统中存在存活进程，算法必须在有限步内终止并达成一致。

若进程 $P_i$ 未崩溃，则最终必有：

\text{elected}_i \neq \bot

若进程 $P_i$ 崩溃，则不对其选举状态做要求。

这是活性，也就是只要存活进程，最后一定能选出来。

当然也有性能指标，就是所有进程发送的消息总数。周转时间则是从算法启动到所有存活进程终止选举所经历的最大串行消息传递步数。

下面介绍 RingBased 和 Bully 两种分布式选举的方法：

RingBased Election#

我们任意将进程排成逻辑环，此时 id 不一定有序。

最开始，任意一个进程可以发起选举，并将消息的 id 设为自身的 id，然后我们把消息扔出去，每次收到消息后，首先如果我是非参与者，先将自己设置为参与者。

如果我的 id 字典序更大，那么就证明我才更可能是那个唯一，所以这时候要终止收到的这次选举，然后再自己发起选举。
如果自己的 id 字典序更小，那么我们直接转发这个消息。
如果收到的消息的 id 和自己的 id 相同，那么证明我发起的选举结束了，我就是存活进程中进程标识符最大的。我成为对应的协调者。

在这之后，我们找到了协调者，协调者还要通知大家自己是协调者。

最好的周转时间和消息条数是 $2N$ 最坏则是 $3N-1$ 。显然，任何一个消息出问题了，整个选举过程都会出问题。

Bully Election#

霸道算法建立在下面的前提

同步系统，使用超时检测进程故障
信道可靠，但允许进程崩溃
每个进程知道哪些进程具有更大的标识符
每个进程均可以和所有其它进程通信

整体可以参考上面的流程

协调者崩溃，触发选举（这里是 P6）
接下来我们的某一个进程发现对应进程崩溃，召集选举，只发消息给 id 更大的进程（这里是 P3）
如果我们发现 id 更大的都没回我，那么我就是新的协调者（但是这里不是）
如果有 id 更大的进程的回复，我们直接让他接管选举（这里先是 P4 后是 P5）
最终选出协调者，发送协调者消息给所有其他进程（这里是 P5）

运气好的情况下，发现崩溃的恰好直接是下一个协调者，只需要发送 $N - 1$ 个消息就可以了。周转时间就一个消息。

反之，运气坏的情况下，最后一个找到我们的协调者，要 $O(N^2)$ 的成本。周转时间是 $N - 2$ 次选举加一条协调者的消息。

组播通信#

组播是发送一个消息给进程组中的每个进程。广播是发送一个消息给系统中的所有进程。这两个操作都是在分布式里面很常见的。我们要保证效率和投递保证。

系统模型包括两种操作

multicast(g, m)
deliver(m)

相当于发消息和确认处理完了回复。

当然，还有两种不同的模型，一种是开放组，一种是封闭组。顾名思义，开放组就是任意其他进程都可以组播该组，反之，则是只能互相发起组播。

基本组播非常简单，记作 B-multicast(g,m)，对于任意 $p \in g$ 都有 send(p,m) 然后进程 $p$ 执行 B-deliver(m)。

但是基本组播不一定满足

完整性，一个正确的进程 $p$ 投递一个消息 $m$ 至多一次
有效性，如果一个正确的进程组组播消息 $m$ ，最终将投递 $m$
协定，如果一个正确的进程投递消息 $m$ ，那么 group 中其他正确的进程最终将投递 $m$

基本组播的 sender 可能会崩溃。

可靠洪泛法实现可靠组播#

实际上很简单，就是完成

\text{multicast} \rightarrow \text{receive} \rightarrow \text{(optional forward)} \rightarrow \text{deliver}

这里的转发消息也是用的基础组播。 $receive$ 则是去重保证一个正确的进程 $p$ 投递一个消息 $m$ 至多一次。

重复消息过滤满足了完整性
一个正确的进程终将 B-deliver 消息到它自己满足了有效性
每个正确的进程在B-deliver消息中都B-multicast该消息到其它进程

但是效率低，每个消息被发送到每个进程 $|g|$ 次，累计 $|g|^2$ 次。

IP 组播实现可靠组播#

主要用了三个操作

IP 组播
捎带确认（piggyback）
否认确认（NACK）

当然，我们还可以提供一个保留队列，这并不是可靠性必须的，但它简化了协议，能使用序号来代表已投递的消息集，提供了投递顺序保证。

我们每个进程维护两个变量，一个是自己要发送的下一条消息的序号Sg.p，一个是来自进程 q 的最新消息的序号Rg.q。相当于维护了一个窗口。

当且仅当 m.S = Rg.p + 1，投递消息 Rg.p = Rg.p + 1
若 m.S <= Rg.p，则该消息已投递，直接丢弃
若 m.S > Rg.p + 1 或对任意捎带过来的确认 <q, Rq> 有 Rq > Rg.q，则漏掉了一个或多个消息。将消息暂存在保留队列中，并发送否认确认 NACK，要求重新发送丢失消息。相当于每个人都会发消息让别人检查组播是否漏消息了。

就是我们能拿到一个类似向量时钟的状态，来检查这个消息的 B-deliver 和 B-multicast 发没发生过。

这个算法用检测重复消息和 IP 组播性质实现了完整性，在 IP 组播具有有效性的时候，该方法也有有效性，如果无限组播消息+无限保留消息副本的时候，协定也成立。

这里主要用到了 IP 组播，否则我们的 NACK 要发给很多人就不对了。

有序组播#

当然，我们的组播还能有序，分别是 FIFO 因果和全排序。

我们利用 IP 组播+捎带确认+否认确认+保留队列就可以实现 FIFO。

但是 FIFO 并不能保证消息的因果性，因为我们可能存在很多进程，所以我们接着给消息加上向量时钟，这样我们就能拿到因果序是正确的组播了，这时候我们叫 CO-multicast 和 CO-deliver。

再往后是全排序，我们就要生成一个全局的序列。

ISIS 全排序协议核心变量
Ag.q：已确认的最大协定序号 → “已提交的序号” Pg.q：自己提出的最大序号 → “本地提议的序号”
协议流程：

发送者广播消息 ID

接收者计算 Pg.q = max(Ag,q, Pg,q)+1

附加 Pg.q 并回复发送者

发送者选最大值 a，广播 <id, a>

所有进程更新 Ag,q = a，按 a 排序并投递

解决进程并发发送

P1 和 P2 同时发送 M1 和 M2。

P1 收到自己的 M1 → 提议序号 1

P2 收到自己的 M2 → 提议序号 2

但 P2 收到 M1 后，也提议序号 2 给 M1

P1 收到 M2 后，也提议序号 2 给 M2

结果：M1 和 M2 都被分配了序号 2 → 冲突！

解决办法，并发的序号用 proposal_number 排序，序号是一个二元组

共识和相关问题#

共识是指一个或多个进程提议一个值后，使进程对这个值达成一致意见。

观察两将军问题，我们就能发现这是个很难的问题，假设我们的信道不可靠或者有个进程崩溃了，需要 ACK：

那么就会陷入 ACK 地狱。所以首先我们就要假设信道有效，且进程不崩溃，否则我们根本不知道是进程崩溃了还是消息太慢了。

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

那么这就涉及到三个概念，进程 p，提议值 v，最终决定变量 d。

共识有三个基本要求

终止性：我们的正确进程要最终设置决定变量
协定性：如果这些是正确的并且进入了决定状态，那么最终决定变量相同
完整性：如果正确的进程都提议了一个值，那么最终都将选择这个值

共识算法如下：

每个进程组播他的提议值
每个进程收集其他进程的提议值
每个进程靠一定的函数majority()决定最终决定变量

我们还有交互一致性的概念：每个进程提议一个值，就向量达成一致。

在共识的基础上，我们提供了决定向量，向量中的每个分量与一个进程的值对应。

拜占庭将军问题#

我们有很经典的拜占庭将军问题。

有3个或更多将军协商是进攻还是撤退，1个将军（司令）发布命令，其他将军（中尉）决定进攻或撤退，一个或多个将军可能会叛变，能否让所有未叛变的将军执行相同的命令？

相当于只有一个独立进程提出协议的共识问题。

为什么我们关注这个问题呢？

如果能解决 单一提议者 的共识（BG），那么通过多次运行它，就能解决 所有进程都是提议者 的共识（IC）。
如果能解决所有初始值的共识（IC，得到一个向量），那么通过简单的多数投票，就能解决单一决定值的共识（C）。
如果能解决一般共识（C），那么当然可以解决由单一司令发起的特定共识（BG）。

也就是说这三个问题是等价的。

解决拜占庭问题的算法如下（Lamport 算法）：

司令发送初始命令。
第一轮： 每个中尉将他们从司令那里收到的命令（哪怕是叛徒伪造的）转发给所有其他中尉。
第二轮到第 $f$ 轮： 进程继续转发他们收到的所有非重复命令。
决策： 在所有 $N$ 个进程（司令 $+ (N-1)$ 个中尉）发出的信息中，每个忠诚进程对收到的信息进行多数投票。

特征	案例一：N=3 (3位将军)	案例二：N=4 (4位将军)
总将军数 ( $N$ )	3	4
叛徒数 ( $f$ )	1	1
定理判断 ( $N > 3f$ )	$3 \ngtr 3 \times 1$ (不满足)	$4 > 3 \times 1$ (满足)
结果	共识失败 (无法保证)	共识成功 (可以保证)
角色假设 (叛徒 G1)	G2 (司令, 忠诚), G1 (叛徒), G3 (中尉, 忠诚)	G1 (司令, 忠诚), G4 (叛徒), G2/G3 (中尉, 忠诚)
司令命令	进攻 (A)	进攻 (A)
叛徒行为	G1 给 G2 发 R，给 G3 发 R。	G4 给所有忠诚将军发 R。
忠诚将军 (G3) 接收集	收到 [来自 G2 的 A, 来自 G1 的 R]	收到 [来自 G1 的 A, 来自 G2 的 A, 来自 G4 的 R]
决策依据	多数票失败： G3 只有 2 条信息 (A, R)，无法区分司令是否是叛徒。信息被叛徒完全掩盖。	多数票成功：收到 3 条信息 (A, A, R)。忠诚信息 (A) 2 票，叛徒信息 (R) 1 票。正确信息压倒错误信息。
最终决定	G2 和 G3 可能做出不同的最终决定。	G1, G2, G3 都决定执行 A (进攻)。

我们让 3f 个人分成 3 个 f 个人代表的组，就划归到 3 个进程的问题了。

注意，消息的真假不是绝对的，我们只要能达成协定就行了。

根据上面我们可以知道，至少要有 $3f + 1$ 个人，才能保证问题的解决。

paxos 算法#

接下来是最难的 paxos 算法。

Paxos 的目标是让一组进程（节点）在存在崩溃故障（不存在恶意）的情况下，就一个值达成一致。当然，Paxos 认为分布式系统是部分同步的，信道不可靠，但是可检测。

Paxos 算法最后目的的要求是

安全性要求保证在任何情况下，系统都不会做出错误或不一致的决定。即使所有节点崩溃，已做出的决定也必须是正确的。
活性要求保证系统在没有出现过多故障时，能够持续运行并最终做出决定，Paxos 算法要求大多数进程（即 $\lceil (N+1)/2 \rceil$ 个，通常称为 Quorum）必须是忠诚且活跃的，才能保证系统的进展。

Paxos 算法将共识过程中的节点分为三种逻辑角色。一个物理节点可以同时承担一个或多个角色。包括提议者，接收者和学习者。

学习者是最终知道协定结果的节点。

Paxos 的流程我们称为三阶段协议：

三阶段流程

在 Prepare 阶段，Proposer 会向 Acceptor 多数集发送 Prepare( $N$ ) 消息。Acceptor 收到后，会承诺不再接受任何编号小于 $N$ 的提议，并回复 PROMISE，同时报告其记录的已接受的最高编号值（如果有的话）。Proposer 必须收到 Quorum 的 PROMISE 响应。在这些响应中，如果存在历史值： Proposer 必须选择所有报告中编号最大的那个值作为提议值（安全继承）。如果不存在历史值： Proposer 可以自由选择其最初想要提议的新值。如果 Proposer 未收到足够多的 PROMISE 响应（因超时或收到 $\text{NACK}$ 拒绝），则本次提议失败。Proposer 将学习到失败的最高编号，并生成一个更大的 $N'$ ，重新发起 Prepare 阶段。

在 Accept 阶段，Proposer 会向 Acceptor 多数集发送 ACCEPT( $N, V$ ) 消息（ $V$ 是根据 Prepare 阶段的安全继承规则确定的值）。Acceptor 收到 $\text{ACCEPT}$ 消息后，会检查它是否已向编号大于 $N$ 的提议做出过承诺。如果 $N$ 仍是它见过的最大编号： Acceptor 接受值 $V$ ，记录下来，并回复 ACCEPTED 响应。如果 $N$ 不是最大编号： Acceptor 会根据它之前做出的承诺忽略该 $\text{ACCEPT}$ 请求。Proposer 必须收到 Quorum 的 ACCEPTED 响应。如果 Proposer 成功收到足够多的 ACCEPTED 响应：则值 $V$ 被选中 (Chosen)，Proposer 推进到 Learning Phase。如果 Proposer 未收到足够多的 ACCEPTED 响应（因超时或 Acceptor 被更高编号提议超车），则本次提议失败。Proposer 必须回到 Prepare Phase，生成一个更大的 $N'$ ，重新发起 Prepare 阶段。

Learning Phase 在 Proposer 成功收到法定人数的 $\text{ACCEPT ACK}$ 响应、值 $V$ 被选中 (Chosen) 后立即启动。Acceptor（图中所示，且通常是那些接受了 $V$ 的 Acceptor）会向 Learner 集合发送 COMMIT( $V$ ) 消息。Learner 收到 $\text{COMMIT}$ 消息后，将记录接收到的值。Learner 必须从 Quorum 的 Acceptor 处收到或确认值 $V$ （即收到足够多的 $\text{COMMIT}$ 消息）。这是确保 Learner 学习到的是真正被选中的值的关键安全步骤。如果 Learner 成功确认值 $V$ ：则 Learner 确定最终共识结果，执行相应操作（如写入状态机或响应客户端）。如果 Learner 未能确认值 $V$ （例如，消息丢失或 Proposer 崩溃），Learner 必须等待进一步的消息，直到它能从 Quorum 处确认 $V$ 为止。

看起来很复杂，实际上可以通过划分我们的三个角色对模型进行简化。

Raft 协议不在课程提纲上，按下不表。

第五章事务与并发控制#

事务的基本概念#

事务是由客户定义的针对服务器对象的一组操作，它们组成一个不可分割的单元，由服务器执行。在多个事务访问对象以及服务器面临故障的情况下，保证所有由服务器管理的对象始终保持一个一致的状态。

事务具有四个经典的特性 ACID

Atomicity（原子性）：事务必须全有或者全无
Consistency（一致性）：将系统从一个一致性状态转换到另一个一致性状态
Isolation（隔离性）：事务执行过程中的中间效果对其它事务不可见
Durability（持续性）：一旦事务完成，它的所有效果将被保存到持久存储中

串行等价#

如果并发事务交错执行操作的效果等同于按某种次序一次执行一个事务的效果，那么这种交错执行是一种串行等价的交错执行。

如果两个操作的执行效果和他们的执行次序相关，称这两个操作相互冲突。

事务 T1 的操作	事务 T2 的操作	是否冲突	冲突的原因 (依赖执行次序)
read (读)	read (读)	否	由于两个 $\text{read}$ 操作的执行效果不依赖这两个操作的执行次序。
read (读)	write (写)	是	由于一个 $\text{read}$ 操作和一个 $\text{write}$ 操作的执行效果依赖于它们的执行次序。
write (写)	write (写)	是	由于两个 $\text{write}$ 操作的执行效果依赖于这两个操作的执行次序。

两个事务串行等价的充要条件是：两个事务中所有的冲突操作都按相同的次序在它们访问的对象上执行。

根据上面的原理，我们就可以分析两个事务是否串行等价。

另外，有的时候我们可能对事务进行放弃，这就可能产生脏数据。

如果我们的隔离做的很烂，是读未提交的，那么我们可能

放弃了的事务的数据被读取
放弃了的事务的数据作为恢复值被错误恢复

这些显然都会导致我们的数据不满足一致性。

并发控制方法#

并发控制协议都是基于串行等价的标准，源于用来解决操作冲突的规则。

我们包括三种方法，锁、乐观并发控制和时间戳排序。

锁#

互斥锁是一种简单的事务串行化实现机制

事务访问对象前请求加锁
若对象已被其它事务锁住，则请求被挂起，直至对象被解锁

为了保证两个事务的所有冲突操作对必须以相同的次序执行，事务在释放任何一个锁之后，都不允许再申请新的锁。每个事务都进行两阶段加锁：

在第一个阶段，事务不断地获取新锁
在第二个阶段，事务释放它的锁

这样子能保证如果这两个事务都提交，那么最终保证串行等价，目的是防止不一致检索和更新丢失问题。

但是我们的事务有可能出现上文提到的脏数据的问题，因此我们可以引入严格两阶段加锁，就是只有事务提交或者放弃的时候，我们才会释放锁。

在这个基础上，我们要对对应的算法进行优化，一个经典的实现就是读写锁。我们可以对读操作加可重入锁，对写操作加互斥锁，这样子我们就可以尽可能提高并发度。

但是锁的算法也有他的问题，可能会引发死锁。

预防死锁我们有如下的几种办法：

每个事务在开始运行时锁住它要访问的所有对象。这样子事务 B 就不会锁住事务 A 的资源，也就不存在死锁了。这打破了破坏死锁的“持有并等待”条件。
为所有资源定义一个全局的、固定的线性顺序（如 $\text{ID}_1 < \text{ID}_2 < \text{ID}_3$ ）。事务只能按此顺序请求锁。这打破了循环等待。这个代价稍微小一点。
维护等待图并且放弃部分事务。
锁超时，也是破坏持有并等待，但是很多事务很容易被放弃。

后两种方法代价是回滚（放弃）事务，允许死锁发生，但在事后解除。

乐观并发控制#

锁其实是一种悲观的并发控制，死锁检测和锁超时这两种解除死锁的方法，对于交互式程序（如用户等待响应）而言，延迟是不可接受的。两阶段的协议也很大地降低了并发度。

大多数应用中，两个事务访问同一对象的可能性很低。所以不要一开始就加锁，相信事务不会冲突。只在事务准备提交时，才检查是否真的发生了冲突。若存在冲突，则放弃一些事务。如果发现冲突，则必须放弃发生冲突的事务，并让其重试。

每个事务拥有所修改对象的临时副本。所有修改都在这个临时副本上进行，对其他事务不可见。系统使用 RS 和 WS 来检查并发执行的其他事务是否干扰了本事务的执行，以保证串行等价。然后我们把不冲突的事务写入数据库。

根据上面串行等价的表，我们就可以检测冲突，首先我们要拿到两个时间戳

编号名称	获取时机	作用
Start Time ( $ST_i$ )	事务 $T_i$ 开始运行时获取。	定义 $T_i$ 的开始时刻。
Validation Time ( $VT_i$ )	事务 $T_i$ 进入验证阶段时获取。	定义 $T_i$ 的逻辑提交顺序。

策略一：向后验证 (Backward Validation)

要比较的对象： 所有在 $T_i$ 开始后 ( $ST_i$ ) 已经提交 (Commit) 的事务 $T_j$ 。
判断规则:将 $T_i$ 与所有已提交事务 $T_j$ 进行比较，其中： $Commit Time_j>ST_i$
目的： 检查 $T_i$ 是否看到了不该看到的旧数据。

策略二：向前验证 (Forward Validation)

要比较的对象： 所有在 Ti 验证时仍然活跃着（尚未提交或放弃）的事务 Tj。
判断规则：将 $T_i$ 与所有活跃事务 $T_j$ 进行比较，其中： $ST_j<VT_i$
目的： 检查 $T_i$ 的提交是否会破坏其他正在努力工作的 $T_j$ 的未来正确性。

比较两种策略：

向后验证将较大的读集合和较早事务的写集合进行比较
向前验证将较小的写集合和活动事务的读集合进行比较
向后验证需要存储已提交事务的写集合
向前验证不允许在验证过程中开始新事务

由于冲突，某个事务被反复放弃，阻止它最终提交的现象叫做饥饿。我们可以用信号量实现资源的互斥访问。

时间戳排序#

我们如果给每个事务提供一个时间戳 $TS$ ，为了进行验证，系统为每个数据对象 D 维护两个时间戳：

$TS_读(D)$ (Read Timestamp): 成功读取 D 的所有事务中，最大的那个 TS。
$TS_写(D)$ (Write Timestamp): 成功写入 D 的所有事务中，最大的那个 TS。

假设 $\text{TS}(T_i) < \text{TS}(T_j)$ （ $T_i$ 应该先于 $T_j$ 执行）：

规则	冲突类型	验证内容	后果
1.	$\text{T}_j$ $\rightarrow$ $\text{T}_i$ $\text{Write-Read}$	$\text{T}_i$ 不能读取 $\text{T}_j$ 写入的对象。	反转：如果 $T_i$ 试图读取 $\text{D}$ ，发现 $\text{TS}_{\text{写}}(\text{D}) > \text{TS}(T_i)$ ，则 $T_i$ 读到了本不该读到的未来数据。 $\rightarrow$ $T_i$ 放弃并重试。
2.	$\text{T}_i$ $\rightarrow$ $\text{T}_j$ $\text{Write-Write}$	$\text{T}_j$ 不能覆盖 $\text{T}_i$ 写入的对象。	覆盖检查：如果 $T_j$ 试图写入 $\text{D}$ ，发现 $\text{TS}_{\text{写}}(\text{D}) > \text{TS}(T_i)$ ，则 $T_i$ 的写入已被覆盖。 $\rightarrow$ $T_i$ 放弃并重试。
3.	$\text{T}_i$ $\rightarrow$ $\text{T}_j$ $\text{Read-Write}$	$\text{T}_j$ 不能写入 $\text{T}_i$ 读取的对象。	读后写检查：如果 $T_j$ 试图写入 $\text{D}$ ，发现 $\text{TS}_{\text{读}}(\text{D}) > \text{TS}(T_j)$ ，则 $T_j$ 的写入可能会破坏 $T_i$ 的逻辑。 $\rightarrow$ $T_j$ 放弃并重试。

方法之间的比较#

时间戳排序（T/O）和两阶段锁（2PL）均属于悲观并发控制方法，但它们在确定事务的串行顺序和处理冲突的方式上存在根本区别。T/O 静态地决定了事务之间的串行顺序（基于事务开始时的 $\text{TS}$ ），它对于只读操作占优的事务具有优势，因为它允许高并发读取。然而，当发生冲突时，T/O 会选择最激进的方式：立即放弃事务，使其必须重试。相对地，2PL 动态地决定事务间的串行顺序（基于锁的获取顺序），它对更新操作占优的事务更具优势，因为它允许事务在冲突时等待。但 2PL 机制可能导致死锁，需要额外的检测和解除机制，最终也可能为了打破死锁而不得不放弃事务。

在低冲突环境，我们使用乐观方法比较好，反之，则用基于锁的悲观方法比较好，这是为了提高吞吐率。

第六章分布式事务#

基本概念#

如果有的事务访问由多个服务器管理的对象，我们就称之为分布式事务。

当一个分布式事务结束时，事务的原子特性要求所有参与该事务的服务器必须全部提交或全部放弃该事务。

其中一个服务器承担了协调者的角色，负责事务的开始、提交和放弃，保证所有服务器上获得相同结果。

一般分成两类，平面事务和嵌套事务：

在平面事务中，客户给多个服务器发送请求。
在嵌套事务中，顶层事务可以创建子事务，子事务可以进一步以任意深度嵌套子事务。

客户在启动一个事务时，向任意一台服务器上的协调者发出一个 openTransaction 请求协调者处理完 openTransaction 请求后，将事务标识符（TID）返回客户。

协调者接口提供了一个额外的方法 join，用于将一个新的参与者加入当前事务。协调者和参与者互相知道。

原子提交协议#

当一个分布式事务结束时，事务的原子特性要求所有参与该事务的服务器必须全部提交或全部放弃该事务。原子提交协议允许服务器之间相互通信，以便共同决定提交或放弃。

我们有几种实现方法，如单阶段原子提交协议和两阶段提交协议。

单阶段原子提交协议#

单阶段原子提交协议是一种简单的原子提交协议。协调者向事务所有的参与者发送 Commit 或者Abort 请求。协调者不断地发送请求直至所有参与者都确认。

但是单阶段原子提交协议有其固有缺陷

单阶段提交协议中，协调者直接要求所有参与者执行并提交操作。如果任何一个参与者在执行过程中失败，或者未能及时响应，整个系统将无法保证原子性。下面两点就是参与者的本地系统可能因为处理其他事务或内部检查，发现了导致其无法提交的冲突。
不允许参与者单方面决定放弃事务，但是有可能提交后发生这种情况
可能有一些并发控制问题会阻止参与者提交，协调者可能不知道这种变化

两阶段提交协议#

两阶段提交协议则允许任意一个参与者自行放弃他自己的那部分事务。

假定一个协调者和多个参与者共同完成一个事务，分两个阶段完成事务。在第一个阶段，我们的协调者询问所有参与者是否准备好提交，第二阶段，协调者通知所有参与者提交或者放弃事务。

下面我们组织一系列原语来描述这个过程：

canCommit?(trans) -> Yes/No
- 协调者使用该操作询问参与者是否能提交事务。
- 参与者将回复它的投票结果（Yes 或 No）。
- 阶段： 投票/准备阶段 (Phase 1)。
doCommit(trans)
- 协调者使用该操作告诉参与者提交它那部分事务。
- 阶段： 提交阶段 (Phase 2 - 成功)。
doAbort(trans)
- 协调者使用该操作告诉参与者放弃它那部分事务。
- 阶段： 提交阶段 (Phase 2 - 失败/回滚)。
haveCommitted (trans, participant)
- 参与者使用该操作告知协调者它已经提交了事务。
- 作用： 用于协调者记录状态，特别是在协调者从崩溃中恢复时进行事务清理。
getDecision(trans) -> Yes/No
- 当参与者投Yes票后一段时间内未收到应答时，参与者使用该操作向协调者询问事务的投票表决结果。
- 作用： 该操作用于从服务器崩溃或消息延迟中恢复，解决阻塞问题。

我们当然会有各种的异常情况

故障场景	丢失的操作/阶段	协调者/参与者如何处理	核心原则/结果
消息丢失	`canCommit` 丢失	参与者在超时后可能会决定单方面放弃事务。	协调者最终会放弃（Abort）该事务。
消息丢失	`Yes/No` 丢失	协调者在超时后放弃事务，它必须向那些投了票的参与者宣布 `doAbort`。	避免进入阻塞状态，默认回滚。
消息丢失	`doCommit` 丢失	参与者可以等待超时，然后发送 `getDecision` 请求（重试直到收到答复）。	**在投`Yes`之后但在接收 `doCommit/doAbort` 之前无法单方面放弃
消息丢失	`haveCommitted` 丢失	事务能正确提交，但影响服务器删除过期时的协调者信息。	不影响事务的原子性，仅影响资源清理。
服务器崩溃	参与者在投“Yes”后进程崩溃	由于在投`Yes`票之前，所有对象已保存在持久性存储中（写入日志）。	进程重启后可恢复，即事务仍能正确提交（或回滚，取决于协调者的最终决定）。

在没有崩溃的情况下，一共要有 N 个 canCommit 消息，N 个应答和 N 个 doCommit 消息。

但是在异常情况下，不同的通信的丢失会带来不同的情况。

两阶段提交协议显然存在很多缺点：

在应答之后但在接收 doCommit/doAbort 之前无法单方面放弃，一直同步阻塞。
协调者可能存在性能瓶颈和单点失效，如果协调者发送 doCommit 后崩溃，导致只有部分参与者提交了，那么就会破坏原子性。

分布式事务并发控制#

上面的协议保证了分布式事务的原子性，但是分布式的事务之间同样要保证串行等价。

首先每个服务器本地都要有对应的并发控制机制。

其次多个本地并发控制要构成分布式的并发控制，分布式事务中所有服务器共同保证事务以串行等价方式执行。即如果事务 T 对某一服务器上对象的冲突访问在事务 U 之前，那么所有服务器对对象的冲突操作，事务 T 都在事务 U 之前。

本地则用悲观的加锁策略实现。

其他并发控制方法
时间戳排序：在分布式事务中，为保证串行等价，协调者必须就时间戳的唯一性及排序达成一致。时间戳定义为 <本地时间戳，服务器id>，先比较本地时间戳，再比较服务器id，确保可以全排序
乐观并发控制：在分布式事务验证中，由于两阶段提交性能较低，故需要允许多个事务并行验证。同一分布式事务的不同服务器可能按不同的次序来串行化同一组事务。如在服务器 X 上先执行 T 再执行 U ，在服务器 Y 上先执行 U 再执行 T。为保证串行等价，必须防止该情况的发生。其中一种方案为使用全局唯一的事务号。

如果我们用对应的并发控制策略，都有可能会出现死锁，那么死锁如何解决呢？我们一般采用等待图的办法。

各服务器只有局部等待图，需要通过通信才能发现全局环路，所以我们一共有两种方案：

选一个对应的协调者，担任全局死锁检测器，收集局部等待图构造全局等待图，并且指定对应的方案。显然可靠性差，协调者易成为瓶颈。这就是集中式死锁检测。

还有一种方案是分布式算法，叫边追逐方法。

当一个服务器上的事务发现自己正在等待另一个远程服务器上的事务时，它会沿着等待关系链发送一个探针消息，不过一般也不是对等的，而是由协调者转发。

这个探针消息会沿着等待边（如 $W \to U \to V \to \dots$ ）在各个服务器之间传递。
如果一个探针消息绕了一圈，又回到了它出发的那个等待边上，就意味着检测到了环路，即死锁。

边追逐法用服务器的逻辑环自然地构造全局等待图，不再具有单点瓶颈和故障的问题。

事务恢复#

事务恢复就是保证服务器上对象的持久性并保证服务提供故障原子性。所谓 TCC 架构里的 C。

他要求对象被保存在持久性存储中并一直可用，并且即使在服务器出现故障时，事务的更新作用也是原子的。事务的恢复过程实际上就是根据持久存储中最后提交的对象版本来恢复服务器中对象值。

我们通过意图列表，来记录所有的修改，从而实现事务的提交和放弃。意图列表包含修改对象的引用和 id。

这里的日志非常类似 Redis 的 AOF，记录了操作序列或意图。通过重放这些操作可以重建状态，并且支持回滚/放弃。当然，为了保证事务的感知，还需要事务状态。事务状态为了方便回滚，还要保留前一个事务状态记录的指针。

对于分布式事务，我们一般实现两阶段提交协议的恢复。

相较于一般的日志恢复，我们在 prepared 和 commited 之外引入了两种不同的记录类型

事务状态	描述	意义	谁记录？
完成 (done)	事务已经成功提交或回滚，并且所有相关的清理工作都已完成。	标志着事务的最终结束。协调者或参与者在处理完 `doCommit` 或 `doAbort` 后记录此状态。	协调者/参与者
不确定 (uncertain)	（通常指参与者状态）参与者已经投了 `Yes` 票（已准备好），但尚未收到协调者最终的 `doCommit` 或 `doAbort` 指令。	这是 2PC 中最关键的阻塞状态。在此状态下，参与者必须等待协调者的最终决定，不能单方面提交或放弃。	参与者

必须要区分不同的记录者

记录者	记录类型包含的内容	目的
协调者	事务标识符 (TransID), 参与者列表 (P1, P2, …)	记录哪些参与者参与了该事务，以及事务的全局状态（例如，`prepared`, `committed`, `aborted`）。
参与者	事务标识符 (TransID), 协调者 (Coordinator ID)	记录该事务的本地状态（例如，`prepared`, `uncertain`），以及出现故障时应向哪个协调者询问最终结果。

最后我们两阶段提交协议拿到了这些信息以后

第七章复制#

基本概念#

复制的基本概念是在多个节点上保存相同数据的一个副本。

一个拥有数据拷贝的节点称为副本管理器。

我们为什么要进行复制呢？

可以增强性能，也就是可以多个副本管理器处理读的请求，避免单点瓶颈。当然缓存也是一种复制。
可以提高容错能力，也就是就算一部分节点出了问题。PS：容错是部分组件出问题还可用的能力。我觉得算可用的因。
可以提高可用性，也就是一主多备，可以随时增强。比如发生日本东京地震什么的，贵州的服务器还可以响应。PS：可用是系统保持正常运行时间的能力。

复制的基本要求是透明和一致，下面会详细介绍，透明性指的是操作的是一个逻辑对象，即使对应多个物理拷贝。

复制需要客户端、前端、副本管理器等组件协同工作，系统模型定义了这些组件如何交互，是理解整个复制机制的基础框架。

系统模型如下：

前端　 - 接收客户请求　 - 通过消息传递与多个副本管理器进行通信

副本管理器（副本+操作副本的组件）　 - 接收前端请求　 - 对副本执行原子性操作　 - 副本管理器是一个状态机：当前状态+一组序列操作可以拿到一个新的确定状态

虽然前端和副本管理器看起来是独立的组件，但是实际上单个机器可以兼任。

那么我们对一个副本对象的操作是怎么调配的呢？实际上有这么些过程

客户端对前端发起请求，前端负责发送请求给副本管理器
协调来保证请求的顺序和一致性，也就是建立是否处理，怎么处理的共识
副本处理器有了处理的共识，开始执行
随后执行的结果因为并发控制的问题，可能需要回滚，协定是否放弃
最终的结果响应给前端

容错与一致性#

容错是在进程出现故障时仍能提供正确的服务，复制是提高系统容错能力的有效手段之一，但是这就要求我们的复制有高度的一致性。

至于一致性，有不同的标准，一共是四个，下面详细介绍。

可线性化#

所有操作都像在单个副本上操作（尽管事实上是多个副本）。每一个读操作都返回最新的值（强一致性）。

一个被复制的共享对象服务，如果对于任何执行，存在某一个由全体客户操作的交错序列，满足以下两个准则，则该服务被认为是可线性化：

操作的交错执行序列符合对象单个副本所遵循的规约
操作的交错执行序列和实际运行中的次序实时一致

可线性化和串行化辨析
可线性化处理的是单个原子操作的顺序和实时可见性。可串行化处理的是包含多个操作的事务的隔离和顺序。

我们 a.write(x) 你理解成一个必须得提交的事件，你就知道这时候 a 已经被锁住了，没写入成功是不能读的，这个时候就不是可线性化的。这写的很容易让人误会。

事实上，这个时间顺序也是自定义的，接下来讲的链式复制的情况，就以提交的时间作为串的基线。

我们写入的请求必须打到链表头，读和最终决策提交都得等到链表尾。

顺序一致性#

线性化能力对实时性要求过高，更多的时候要求顺序一致性。一个被复制的共享对象服务被称为顺序一致性，满足以下两个准则：

操作的交错序列符合对象单个正确副本所遵循的规约
操作在交错执行中的次序和每个客户程序中执行的次序一致。

顺序一致性同样保障所有操作都像在单个副本上操作（尽管事实上是多个副本）。每一个读操作都返回最新的值。

但是两个并发客户请求的执行顺序，只要不同的顺序执行效果一致，也没有冲突，那么在顺序一致性下不同也无所谓，但是线性化很在乎。

说的更清楚一点就是，如果客户 A 的操作 $Op_A$ 和客户 B 的操作 $Op_B$ 在物理时间上是并发的，SC 允许系统：

忽略它们的物理完成时间。
自由选择将 $\langle Op_A, Op_B \rangle$ 或 $\langle Op_B, Op_A \rangle$ 放入最终的全局全序中。

但这并不是说不存在唯一的顺序，只是这个顺序没有时间这个强约束。

强一致性辨析
强一致性的线性化和顺序一致性的区别很抽象，相当于这俩一致性都有一个共识的顺序，但是只有线性化满足物理时间，顺序一致性只要有共识，不需要保障这个物理时间。可以对这个物理时间进行重排。

虽然物理时间上，setBalance(x,1) 更早，但是只要客户都承认 getBalance(x) -> 0 更早即可。这个满足顺序一致性。

因果一致性#

所有进程必须以相同的次序看到因果相关的写操作，不同进程可能会以不同的次序看到并发的写操作。

上面这种情况满足因果一致性。

但是不能有类似下图的因果冲突

这里 R(x) 看到了 W(x) 的结论，然后我们做了 W(X)，P3 就不该再做到 R(x) -> 1。不过，如果不存在 P3 其实是满足对应的因果一致性乃至顺序一致性的。

最终一致性#

CAP 定理指出，在一个分布式计算系统中，我们最多只能同时满足以下三个核心保证中的两个。在面对实际的网络问题时，系统必须在其中一个属性上做出牺牲。在一个真实世界的分布式系统中，分区 (P) 是不可避免的。

缩写	中文名	英文	经典解释
C	一致性	Consistency	任何对数据的读取操作，都必须返回最近一次成功的写入数据。所有客户端在同一时间点看到的数据副本必须是相同的。
A	可用性	Availability	对系统发出的任何非失败请求，系统中的每个非故障节点都必须及时给出响应（不能无限期阻塞），无论该响应成功或失败。
P	分区容错性	Partition Tolerance	即使网络中出现任意多的消息丢失或延迟，导致系统被分割成多个独立运行的小组（网络分区），系统仍能继续运行和响应。

这里的 C 一般指强一致性乃至于线性化。事实上，如果我们不保障严格的一致性，我们只保证

副本管理器只根据它们局部的状态处理操作
如果没有更多的更新，最终所有的副本管理器会处于相同的状态（并不保证多长时间可以达到这种状态）

复制的系统模型#

被动复制#

给我们的副本管理器划分主从，前端的所有请求都只打到主副本管理器，并且进行协调顺序，有了一个全局的顺序后（如果满足时间顺序，就是可线性化，至少是顺序一致性的），如果是写操作，那么主副本管理器会协定让副本管理器更新，最终主副本管理器响应前端。

这也叫被动复制。

主动复制#

如果不给我们的副本管理器划分主从，前端就要组播了，那么组播的顺序就只能由有序组播来保证了。但是因为对应的算法本身和线性化的时间约束无关，所以最多只能实现顺序一致性。

对应的流程如下，前端使用全序、可靠的组播原语将请求组播到副本管理器组，组通信系统以同样的次序(全序)将请求传递到每个副本管理器，每个副本管理器以相同的方式执行请求，每个副本管理器将应答发送给前端，接收的应答数量取决于故障模型的假设和组播算法。最终前端响应客户请求。

这里的协定依赖于 deliver 这个组播的语义。

单拷贝可串行化#

单拷贝可串行化（Single-Copy Serializability）指的是客户在复制对象上执行的事务的效果应该与它们在一组对象上逐一执行相同，相当于结合串行等价+复制透明性（一致性）。

单拷贝串行化可以通过读一个/写所有实现复制方案。

读取操作可以在任何一个副本上，反正都是一致的。

写入操作必须在全部副本上。

因为完全不故障时不可能的，读一个/写所有在副本管理器崩溃或者通讯故障时不是一个现实的方案，可用副本复制方案允许某些副本管理器暂时不可用。

只要可用的副本管理器集没有变化，本地的并发控制和读一个/写所有复制一样可获得单拷贝串行化，但如果执行过程中副本管理器故障或恢复，需要额外验证。

比如如下的一个情景；

核心操作	事务 T	事务 U	关键冲突与系统状态
读一个 (T 对 A 加锁, U 对 B 加锁)	持有 A 的锁 (在 $Y$ 上)；下一步：`deposit(B, 3)`。	持有 B 的锁 (在 $P$ 上)；下一步：`deposit(A, 3)`。	状态：两个事务成功开始。系统进入死锁准备状态： $T$ 握 $A$ 等 $B$ ； $U$ 握 $B$ 等 $A$ 。
写所有 (U)	保持 A 的锁。	试图执行 `deposit(A, 3)`，发送写入请求到 $A$ 的副本。	冲突： $U$ 的写入请求到达 $Y$ 时，发现 $A$ 正被 $T$ 的锁占用。 $U$ 被阻塞/等待 $T$ 释放 $A$ 。
写所有 (T)	试图执行 `deposit(B, 3)`，发送写入请求到 $B$ 的副本。	保持 B 的锁。	冲突： $T$ 的写入请求到达 $P$ 时，发现 $B$ 正被 $U$ 的锁占用。 $T$ 被阻塞/等待 $U$ 释放 $B$ 。

这样虽然可能会死锁，但是保证了串行等价。

核心操作	事务 T 状态	事务 U 状态	关键冲突与系统状态
读一个 (T 读 A, U 读 B) + 故障发生	持有 $A$ 的锁 (在 $Y$ 上)；准备写入 $B$ 。	持有 $B$ 的锁 (在 $P$ 上)；准备写入 $A$ 。	状态：事务建立了两个读操作。故障使 $A$ 可用 $\{Y\}$ ； $B$ 可用 $\{M, P\}$ 。潜在冲突已存在。
写所有 (U) (在 $Y$ 上)	保持 $A$ 的锁。	成功写入 $A$ (在 $Y$ 上)。	不可串行化冲突 I (T 读 $A$ $\to$ U 写 $A$ )：事务 $U$ 成功写入 $A$ ，这意味着 $T$ 对 $A$ 的读操作发生在 $U$ 写入 $A$ 之前。 $T$ 必须在 $U$ 之前提交 ( $T \to U$ )。
写所有 (T) (在 $M, P$ 上)	成功写入 $B$ (在 $M, P$ 上)。	$U$ 已经释放了 $A$ 和 $B$ 的锁。	不可串行化冲突 II (U 读 $B$ $\to$ T 写 $B$ )：事务 $T$ 成功写入 $B$ ，这意味着 $U$ 对 $B$ 的读操作发生在 $T$ 写入 $B$ 之前。 $U$ 必须在 $T$ 之前提交 ( $U \to T$ )。
最终结果	不可串行化	不可串行化	1CS 失效：两个依赖关系 ( $T \to U$ 和 $U \to T$ ) 形成循环依赖。这证明了在副本故障的情景下，原始的加锁机制未能正确阻止冲突，单拷贝可串行化（1CS）被破坏。

但是在故障的情况下，原始的加锁机制未能正确阻止冲突，单拷贝可串行化（1CS）被破坏。

上面的情景分别是死锁和崩溃导致锁失效，因此必须引入一个本地验证才能解决。

也就是事务提交前检查已访问的副本管理器集是否变化（故障和恢复），如在事务执行过程中副本管理集发生变化则放弃该事务。

步骤	事务操作	本地验证 (主副本 Y 和 P)	2PC + 全局协调 (解决冲突)
I. T 读 $A$	$T$ 向 $Y$ 请求 $A$ 的 $S$ -Lock。	$Y$ 验证： $Y$ 授予 $T$ 锁。	状态： $T$ 成功持有 $A$ 的 $S$ -Lock。
II. U 读 $B$	$U$ 向 $P$ 请求 $B$ 的 $S$ -Lock。	$P$ 验证： $P$ 授予 $U$ 锁。	状态： $U$ 成功持有 $B$ 的 $S$ -Lock。
III. U 写 $A$	$U$ 尝试执行 `deposit(A, 3)`。	$Y$ 验证： $Y$ 检测到 $T$ 持有 $S$ -Lock，阻塞 $U$ ，要求 $U$ 等待 $T$ 释放锁。	解决冲突 I ( $T \to U$ )： $Y$ 上的本地验证阻止了 $U$ 在 $T$ 读后写入 $A$ ，从而避免了 $T$ 对 $A$ 的旧值依赖。
IV. T 写 $B$	$T$ 尝试执行 `deposit(B, 3)`。	$P$ 验证： $P$ 检测到 $U$ 持有 $S$ -Lock，阻塞 $T$ ，要求 $T$ 等待 $U$ 释放锁。	解决冲突 II ( $U \to T$ )： $P$ 上的本地验证阻止了 $T$ 在 $U$ 读后写入 $B$ ，从而避免了 $U$ 对 $B$ 的旧值依赖。
V. 提交阶段	(两者阻塞)	死锁检测：系统（例如协调者）检测到 $T \to U \to T$ 循环等待。	2PC 介入（原子性）：协调者选择回滚 $T$ 。 $T$ 释放对 $A$ 的锁。 $U$ 恢复执行，成功获取 $A$ 的 $X$ -Lock。 $U$ 完成操作，并在 2PC 下原子性提交。 $T$ 重新执行。

gossip 系统#

我们上文知道了，实际上 CAP 不能同时保证，那么我们实际上的系统比如 GOSSIP 保证的其实是 AP，对于一致性，我们的 GOSSIP 系统只保证最终一致性，但是可以用如向量时间戳的手段，在前端支持因果一致性。

如果更准确的表述，就是

随着时间的推移，每个用户总能获得一致服务
副本之间松弛的一致性

下面分析 Gossip 的体系结构

我们并不强保证各个副本管理器可用，所以我们只需要让前端自己去挑选对应的副本管理器就好了，另外，我们提供两种原语：update 和 query。但是为了完成最终一致性，副本管理器定期通过 gossip 消息来传递客户的更新。

在这种基础我们增加了向量时间戳，前端利用这个向量时钟，就能拿到对应操作的因果关系，并最终保证因果一致性。不过因为 Gossip 的特点，我们只有两类消息，一种是

update 和 query 其请求和响应可以更新 frontend 的时间戳
gossip 消息则是负责副本管理器之间的时间戳同步

我们利用下面这些维护一个副本管理器的状态

值：副本管理器维护的应用状态的值
值的时间戳：更新的向量时间戳
副本的时间戳：已经被副本服务器接收到的更新
更新日志：记录更新操作
已执行操作表：记录已经执行的更新的唯一标识符，防止重复执行
时间戳表：时间戳来自gossip消息，确定何时一个更新已经应用于所有的副本管理器。

这些比较难理解的个人觉得是更新日志和时间戳表。

事实上，我觉得如果你了解过 Mysql，大家知道 Undo Log 可以用来归档，binlog 可以用来做主备同步，那么肯定觉得这个更新日志不陌生，他充当两个角色：

更新前先写日志，做归档，在提交前，操作必须先写入更新日志，才能释放锁，从而更好的实现恢复。相当于 Undo Log。
记录了所有更新操作。在 Gossip 系统中，它作为消息的内容源，用于将更新异步传播给其他副本。这里相当于 Binlog。

副本的时间戳则是告诉这个接受了多少更新，而时间戳表则记录了其他的更新到哪，方便我们删掉不需要的更新日志。

下面我做一个详细的分析，有这么个流程

我们有3个副本管理器 rm0、rm1、rm2，3个对应的前端fe0、fe1、fe2。

fe0 发起一个更新请求：update(x,1)；标识符 fe0_1 时间戳 (0,0,0)
rm0 处理更新请求；更新副本时间戳 rm0.replica.ts[0]++ 本地的值，然后赋值值时间戳 ts = rm0.replica.ts log=<i,ts,u.op,u.prev,u.id>=<0,(1,0,0),x=1,(0,0,0),fe0_1> 此后 fe0 merge 时间戳 fe0.ts = (1,0,0) ，然后 rm0 处理因果序
rm0 将 gossip 消息发送至 rm1、rm2；发送的有 log=<i,ts,u.op,u.prev,u.id>=<0,(1,0,0),x=1,(0,0,0),fe0_1> 和 rm0.replica.ts
rm1、rm2 处理 gossip 消息；各自 merge(rm0.replica.ts) 和更新日志，并且处理因果序
fe1 发起一个请求：query(x)；时间戳 (0,0,0) $\leq$ (1,0,0) 所以可以响应，并 merge(1,0,0)
rm1 处理查询请求，时间戳 (0,0,0) $\leq$ (1,0,0) 所以可以响应；
fe1 发起一个更新请求：update(x,2)；标识符 fe1_2 时间戳 (1,0,0)
rm1 处理更新请求；更新副本时间戳 rm1.replica.ts[1]++ 本地的值，然后赋值值时间戳 ts = rm1.replica.ts log=<i,ts,u.op,u.prev,u.id>=<1,(1,1,0),x=2,(1,0,0),fe1_2> 此后 fe1 merge 时间戳 fe1.ts = (1,1,0) ，然后 rm1 处理因果序。
rm1 将 gossip 消息发送至 rm0、rm2；发送的有 log=log merge <i,ts,u.op,u.prev,u.id>=<1,(1,1,0),x=2,(1,0,0),fe1_2> 和 rm1.replica.ts
rm0 处理 gossip 消息，但发至 rm2 的 gossip 消息丢失了；rm0merge(rm0.replica.ts) 和更新日志，并且处理因果序
fe0 发起一个请求：query(x)；时间戳 (1,0,0) 并 merge(1,1,0)
rm0 处理查询请求；时间戳 (1,0,0) $\leq$ (1,1,0) 所以可以响应
fe0 发起一个更新请求：update(x,3) 时间戳 (1,1,0)
rm0 处理更新请求，同理啊～
rm0 将 gossip 消息发送至 rm1、rm2；
rm1、rm2 处理 gossip 消息，这里的不同是 rm2 缺失了一个更新，所以要根据日志补更新

我们有了这些信息，很简单就可以判断日志该不该删。

第八章分布式文件系统#

分布式文件系统的需求#

我们为了满足用户有多台计算机，数据被多个用户共享，并完成统一的数据管理的场景，引入了分布式文件系统。

分布式文件系统应该满足透明性，也就是类似本地文件系统。

我们有复杂机制去保障

访问的一致性
位置的唯一性
移动
性能
可扩展

这些操作如同本地的系统一样。

那么我们就要支持并发的文件更新，文件复制，硬件和 OS 的异构性以及容错（保证幂等）。

还需要一致性，安全性和效率。

文件服务体系结构#

我们包含了

客户模块，运行在客户计算机上，提供对远程文件服务透明存取的支持，有缓存保证性能
目录服务，提供元数据管理和层次文件结构，能保证位置的唯一性，主要有 lookUp,addName,unName,getName 这些接口，顾名思义即可
平面文件服务，基于UFID，对文件内容进行操作，包括 read,write,create,delete,getAttributes,setAttributes，因为没有 open 所以 read write 需要有对应的开始位置，但是好处是都是幂等的。重点是写操作，重试的时候相当于直接覆盖上一次写。

但是也存在对应的问题，就是我们因为无状态，很难做访问的控制。

Kerberos 认证
Kerberos 是一种基于对称密钥的分布式认证服务，为网络中的实体提供安全的身份验证。其核心思想是引入可信第三方（KDC，Key Distribution Center）来解决分布式环境中的信任问题。
三个关键组件：

AS（Authentication Server）：负责验证用户身份，发放TGT（Ticket Granting Ticket）

TGS（Ticket Granting Server）：负责发放服务票据（Service Ticket）

KDC（Key Distribution Center）：集成AS和TGS，管理所有密钥

认证流程（三步交互）：

Client → AS：请求 TGT

AS验证用户身份，生成会话密钥和TGT（用用户的密钥加密）

TGT包含：会话密钥、用户ID、有效期等，用TGS的密钥加密

Client → TGS：请求服务票据

Client向TGS提交TGT和请求的服务ID

TGS验证TGT有效性，生成Service Ticket（用服务的密钥加密）

Service Ticket包含：会话密钥副本、服务ID、有效期等

Client → Server：访问服务

Client向服务提交Service Ticket和Authenticator（用会话密钥加密的时间戳）

服务解密票据，验证Authenticator，建立安全通道

关键特点：

单点登录（SSO）：一次认证获得多个服务的访问权限

会话密钥：避免在网络上传输用户密码

时间戳防重放：Authenticator包含时间戳，防止重放攻击

票据有效期：限制票据的使用期限，过期自动失效

典型应用： NFS、SSH、LDAP等分布式系统中的身份认证，是现代分布式安全架构的基础。

NFS 体系结构#

我们的 VFS 的设计如下，本地的文件引用对应的 i 节点，而远程的文件引用一个句柄，服务器之间的传输依赖句柄，但是句柄对用户不可见。i 节点由 i 节点数和 i 节点产生数，i 节点数在一个特定的文件系统里是唯一的，i 节点数是用于标识和定位文件的数值。i 节点产生数则是相当于被用了多少后次的一个标识，每次删除以后发生变化，也可以用来避免正在打开的节点被删除。当然，我们的一个服务可能要支持多个文件系统，所以还要暴露一个文件系统标识符。

我们 NFS 的访问控制是无状态的，因此要么每次根据 ID 校验，要么根据 Kerberos 认证进行相关的工作。我们的访问则可以通过 mount 安装后直接利用 UNIX 系统调用访问文件，一个客户模块通过使用一个共享缓存存储最近使用的文件块，为所有的用户级进程服务。这样子我们传输给服务器用于认证用户ID的密钥可以由内核保存，防止用户级客户冒用客户。

CAUTION
open 调用流程

客户端进程 持有指向当前目录的 vnode 引用。

客户端 向服务器发送 LOOKUP (目录句柄, “notes”) 请求。

服务器 从文件句柄中提取 i-number。

服务器 请求本地文件系统将该 i-number 转换为本地 vnode。

服务器 调用本地 vnode 的 lookup 方法。

dir->lookup("notes") 返回 “notes” 文件的 vnode。

NFS 服务器代码 从 vnode 中提取 i-number，并 创建新的文件句柄。

服务器 将 新的文件句柄 返回给客户端。

客户端 创建新的 vnode，并设置其文件句柄。

客户端 创建新的文件描述符 指向新的 vnode。

read 调用流程

客户端应用程序 发出 read(fd, ...)。

最终结果是 READ(文件句柄, …) 请求被发送到服务器。

vnode 是文件系统本地的，我们的客户端往往会发送 lookup 消息给服务端，服务端在句柄里能拿到对应目录的 i-number，又可以找到对应的 vnode，最后再调用本地的 lookup 找到文件的i-number，从而创建句柄返回给客户端，客户端就可以借此创建 vnode 和描述符。

在此基础上，我们 UNIX 文件系统也会有很普通的缓存，比如预取和延迟+定时落盘。

NFS 也有读缓存，和 UNIX 本地类似，但是写缓存有两种模式，一种是写透，不管题没提交，直接落盘，还有一种也是在 commit 的时候再落盘。

为了减少传输给服务器的请求数量，NFS客户模块将 read, write, getattr, lookup 和 readdir 操作的结果缓存起来。

那么为了检查缓存是否有效，我们怎么做了？还是基于时间戳去做：

时间戳	名称	含义	存储位置
$\mathbf{T_c}$	缓存验证时间	缓存条目上一次被客户端验证为有效的时间点。	客户端（本地缓存）
$\mathbf{T_m}$	文件修改时间	文件块在服务器上一次被修改的时间。	客户端（缓存值）和服务器
$\mathbf{T}$	当前时间	客户端发起请求时的系统时间。	客户端（本地系统）

当然，我们并不是直接比较，而是先判断是否过时，我们直接拿 T 和 Tc 就能校验是否过时，如果过时，我们再去获取这些时间戳做进一步校验。这里为了减轻缓存压力，可以自适应 t 并且更多的更新对应的 Tmserver，比如父项更新或者其他操作的时候，我们可以直接更新对应的 Tmserver。

AFS 体系结构#

在 NFS 的基础上，为了增加可扩展性，我们设计了 AFS：

整体文件服务：AFS服务器将整个文件和目录的内容都传到客户计算机上
整体文件缓存：当一个文件或文件块被传输到客户计算机上时，它被存储到本地磁盘缓存中

AFS 相当于要用什么直接拉到缓存，更新同步到服务器，这主要是因为大部分文件比较小，而且一个文件经常都是一个人在更新和读写，读操作明显多于写操作。

AFS中的文件分为本地的或共享的。本地文件可作为普通的UNIX文件来处理，它们被存储在工作站磁盘上，只有本地用户可以访问它；共享文件存储在服务器上，工作站在本地磁盘上缓存它们的拷贝。每个工作站本地磁盘上都有一个文件分区被用作文件的缓存。Venus进程采用 LRU 策略管理这一缓存。

Venus 利用 fid 去存取文件，并且用单独的分区用作文件缓存。Vice 则是接收用 fid 表示的文件请求，提供平面文件服务。Vice 主要提供了拉取，更新，删除等操作，此外，为了保证一致性和安全，还提供了锁和 callback。

我们的文件更新就是 open read write close 这么一个流程。open 阶段，通过校验合法的回调承诺，来判断更新是否会破坏一致性，此时，我们会提供一个回调承诺，从而在之后找到要给谁发送回调消息，随后拉取到本地，进行读写操作，并给拥有这个文件回调承诺的其他客户端发送回调。这样子，明显减少客户端和服务器之间的交互，具有更强的扩展性。

在更新语义上，我们有两个级别，AFS-1 实现的类似单个文件拷贝的语义，open 和 close 都是严格生效的，failure 的时候则是严格失效的。AFS-2 则接受缓存可能因为回调丢失而不是最新的。

AFS 还做了很多其他修改，比如对内核进行改造，并发，只读复制，批量传输和部分文件缓存等。基本可以理解将文件化成了 64KB 的基本块。我们的 AFS 还有位置数据库，用于将卷名映射到服务器。

第九章 GFS#

GFS 简介#

Google 的三驾马车开启了云计算时代，他们的搜索业务也需要大量的存储，显然，再怎么贵的小型机也无法承载这种工作，他们搭建了一套具有充分伸缩性的，用大量家用 PC 构建出来的系统。其中，最核心的部分就是存储，也就是所谓的 GFS。

事实上，正因为这些业务上的特性，铸就了 GFS，因为机器是家用级别的，所以实际上无法避免地陷入失效状态；文件在谷歌这个体量的存储上，既有很大的文件，又有极多的文件，还在以很快的速度增长；进一步的，大部分文件实际上很少随机写入，都是进行顺序的追加写；谷歌并不是单单提供存储的，存储仅仅作为基础架构，因此 API 还要考虑到上层的应用程序。上面四点，构成了 GFS 的动机。

那么，在这样的动机下，我们的 GFS 是怎么设计的呢？

既然我们的组件不稳定，那就要用大量的副本来提高可用性。Chunk 服务器在硬盘上存储实际数据。每个 Chunk 服务器跨越3个不同的 Chunk 服务器备份以创建冗余来避免服务器崩溃。一旦被Master 服务器指明，客户端程序就会直接从 Chunk 服务器读取文件。

文件由文件块的形式组织，每个块有他的句柄，master 维护所有文件系统的元数据。元数据包含了文件的命名空间，文件到数据块的映射信息，数据块的位置信息，访问控制信息与数据块版本号。文件快相当大，64MB 的大数据块，这样子我们就可以减少 metadata，从而保证内存容量不成为 master 的瓶颈，也可以减少客户端的缓存压力。同时，块比较大，相当于我们可以一个长连接做很多事情，减少网络的负载。

当然，我们的元信息是有可能变动的，所以我们的 master 需要通过心跳去更新这些信息。因为 master 拿到的 metadata 甚至可以放在内存里面，所以 master 的操作很快，那么当然可以利用一些算法实现 GC，负载均衡以及副本复制，虽然 metadata 可能会受到 master 内存的限制，但是相较于我们那么大的系统，代价是很小的。

因为大量的流式读取，实际上缓存没有意义，我们的客户端只需要缓存元数据就行了，Chunk 服务器本身就是 Linux 服务器，所以 Linux 的缓存就足以应对这种场景了。

为什么 master 不存在瓶颈？

只存储元数据，不存储文件数据，不让磁盘容量成为 master 瓶颈；

元数据会存储在磁盘和内存里，不让磁盘 IO 成为 master 瓶颈；

元数据大小内存完全能装得下，不让内存容量成为 master 瓶颈；

所有数据流，数据缓存，都不走 master，不让带宽成为master瓶颈；

元数据可以缓存在客户端，每次从客户端本地缓存访问元数据，只有元数据不准确的时候，才会访问 master，不让CPU成为成为 master 瓶颈；

GFS 的读、写、添加操作#

不过显然，我们的客户端，chunk 服务器以及我们的主服务器之间是有很多交互的。主服务器和 chunk 之间要有上面提到的 heartbeat 消息，客户端和其他两者也要通信。我们下面详细介绍。

主服务器显然是一个需要保证一些一致性的中心服务，所以他要有日志，这里叫操作日志。但是我们的主服务器显然也有宕机的风险，为了安全又实际存储在多个 chunk 服务器上。Master 依靠这个日志来恢复自身的文件系统状态。不过显然，我们也不能把所有的日志直接发给我们的 chunk，因此这有一个类似归档的机制，叫 checkpoint。本地 checkpoint 之后的日志 + checkpoint 的日志共同构成了操作日志。它作为逻辑时间基线定义了并发操作的执行顺序。文件、块以及它们的版本号都由它们被创建时的逻辑时间而唯一地、永久地被标识。

我们的 Client 怎么和 GFS 通信呢？为了不让 Master 的 CPU 成为瓶颈，所以 Client 直接和 chunk 通信，而主服务器仅仅提供数据块所在的 chunk 以及详细偏移。

考虑到主服务器只有元信息和我们的 chunk 有多个副本，下面的逻辑很合理。

对于读操作，流程如下：

应用程序发起读取请求。
GFS 客户端从（文件名，字节范围）->（文件名，组块索引）转换请求，并将其发送到 Master服务器。
Master 服务器以块句柄和副本位置（即存储副本的 Chunk 服务器）作为响应。
客户端选择一个位置，然后将（块句柄，字节范围）请求发送到该位置。
Chunk 服务器将请求的数据发送到客户端。
客户端将数据转发到应用程序。

对于写操作，流程如下：

GFS客户端发送请求到主服务器；
主服务器返回块的句柄和副本的位置信息；
客户端将写数据发送给所有副本管理器；
数据存储在副本管理器的缓存中；
客户发送写命令到主副本管理器；
主副本服务器给出写的次序；
主副本服务器将该次序发送给二级副本管理器；
二级副本管理器响应主副本管理器；
主服务器响应客户端。

考虑到副本管理已经有现成的客户端、前端、副本管理器模型，我们只需要将 chunk server 视为这里的副本管理器就行。

上面我们说了，事实上大部分操作都是追加写，不过这个实现很自然，我们有如下的操作：

应用程序提出添加操作的请求。
GFS client 解释该请求，然后发向主服务器。
主服务器返回块句柄和副本位置。
Client 将要写入的数据推入各个副本。
Primary 检查添加操作是否会导致该块超过最大的规模，太大就尽量塞，塞不下塞到下一块。

一致性模型#

我们的客户端的请求可以由客户端来保证写入，因此，客户端自己知道写入文件范围以及写入数据内容，且本次写入在数据服务器的多副本上均执行成功。所以结果是 defined 的，但是多个 client 同时写入时, 由于多个客户端由于写入范围可能交叉覆盖。单个客户端无法决定写入顺序，所以是 consistent but undefined，相当于由前面讲的副本的机制保证了因果一致性。

不过 client 的 append 操作无需指定 offset，由 chunk 的 primary 根据当前文件大小决定写入offset，在写入成功后将该 offset 返回给客户端。因此，客户端能够根据 offset 确切知道写入结果，无论是串行写入还是并发写入，其行为是 defined。不过一旦出现写失败，我们有可能会出现问题，此时是 interspersed with inconsistent。

defined 和 consistent 的定义
这里的 defined 与否，由我们的客户端是否知道自己的写入位置和操作次序决定。也就是说，我们的客户端能否感知操作的全局状态。consistent 则是副本的一致性，这里指的是强一致性。

第十章 P2P DHT 以及 Chord#

P2P 及其问题#

我们传统的架构都是非对等的 C/S 架构，但是在今天个人设备越来越强，所以接收者获取数据的副本，然后将数据重新分发给其他接收者，最后起到减轻服务器负担的作用，并不是不可能。毕竟阿里巴巴照抄那一套云服务，喊出“去 IOE”化，就是要用个人 PC 级别的机器（比如 8C16G 甚至 4C8G 是比较经典的配置）。

那么我们要接受者承担这个活，但是有时候他可能需要带宽资源做别的，那么我们需要节点频繁加入和退出，还需要激励节点留在系统（不过 PCDN 警告下，这也就是课上学学），下载还要越快越好。那么我们就得好好设计 P2P 的系统。

首先当然用中心化网络是可以的，但是这样子还会出现单点的故障和瓶颈问题。

所以我们采用分布式非结构化的拓扑，分布式非结构化拓扑采用了重叠网络，重叠网络是在现有的网络体系结构上加多一层虚拟网络，并将虚拟网络的每个节点与实际网络中的一些节点建立一个连接。首先要搞定的是路由，我们要保证最终两点之间可达。所以我们往往设计一个环形的方案，下面介绍 Chord 的时候会想详细介绍这样的路由表和消息平均跳数的设计。

除此之外，我们还得快速定位资源，这可没有 master 服务器了，我们怎么搞定元数据那一套的对等版本呢？这就要用到分布式哈希，所谓的 DHT（Distributed Hash Table）。这里也暂且按下不表。

实际实现上，我们往往用半分布式拓扑结构吸取了中心化网络拓扑和分布式网络拓扑的优点，选择性能较好的结点作为超级结点，各个超级节点上存储了其余节点的信息。

一致性哈希#

上面聊到了哈希，这里重点介绍一下，哈希听起来很简单，做个 index 罢了，但是实际上哈希算法尽量要满足下面的条件：

首先要完成平衡性和负载，数据要到所有对等节点，而且多个对等节点之间负载相对均衡。这一点虽然看起来很简单，比如取余，但是世界上并不天然存在 UUID，因此实际上很容易出现数据倾斜。
其次要完成单调性，我们节点的缓存扩充或者节点增多的时候，我们要求不需要重新计算所有 hash，这个代价太大了。
这个算法还要实现分散性，我觉得这点很难，就是大家看到的空间都不一样，甚至可能没有交集，但是我们尽量要把我俩都得看到的东西存储到交集的缓冲中，但是同时还要满足其他特性

那么有哪些算法呢？最简单的肯定是模余，相对于将 key 打散（就是让取余后分的相对均匀）后按服务器数量取余。但是问题是，一旦有节点上线或者下线，我们就得全盘重算 hash，相当于牺牲了单调性。

我们用 4 个字节的数据去存储一个 hash 值，构造一个 hash 环，我们不单单将 key 映射到这个 hash 值，还将节点映射到 hash 上，然后我们就在这 4 个字节也就是 32 位的空间顺序找到第一个服务节点上。这样子，我们就能利用 hash 的特性把节点打散，这样也就相对满足平衡性，单调性和负载，同时因为任何子集都是相对打散的，所以我们能最大限度的完成上述的要求。

然而，仅有高效的数据放置机制是不够的。在这个高度分散的 $2^{32}$ 环形空间中，如果每个节点只知道其直接邻居，那么从一个节点找到环上任意另一个节点仍然需要线性时间（即 $O(N)$ 次查询，其中 $N$ 是节点总数），这在节点规模巨大时是无法接受的。为了将查询效率从 $O(N)$ 提升到 $O(\log N)$ （即实现跨越式查找），节点不仅存储直接相连的下行节点位置信息，还要知道一定深度的间接下行节点信息，并动态地维护这个跳跃点列表。下面会详细介绍，这里暂时不表。

DHT 主要思想#

我们的文件索引都对应了 <hash, location> 的信息的键值对，分布式哈希表（DHT）将所有文件的索引（K, V 对）根据键的哈希值分散到所有节点上，使得每个节点只负责维护全局索引的一部分。

节点通过特定的路由规则（如 Chord）建立高效的邻居关系，并利用这些关系将查询报文层层转发，直到找到持有目标键值索引的那个特定节点，从而完成查找。不过正如前言，这个 location 多半也是个 list，作为不同的副本。

Chord#

我们的 Chord 是一种上面的分布式 hash 表的实现，在哈希算法上，我们维护一个 Chord 环，在路由算法上，维护一个 32 格的 finger table，那么再怎么远我们也可以至少减半距离，所以就能在 $O(logN)$ 的时间复杂度找到任意节点。

这个数字 32 是直接由哈希空间的位数决定的：

哈希空间大小： 如果使用 32 位的哈希函数，哈希空间 $M = 2^{32}$ 。
对数查找： 为了实现 $O(\log N)$ 的查找效率，指纹表的设计要求能够覆盖环上的每一个指数级距离（ $2^0, 2^1, 2^2, \dots$ ）。
条目数计算：因此，指纹表的条目数 $m$ 等于哈希空间的位数，即： $m = \log_2 M = \log_2 (2^{32}) = 32$ 这 32 个条目确保了每一步查找都能最大程度地缩小与目标的距离，从而保证了整个查找过程在 $\log N$ 步内完成。

容易证明，这里的 $logN$ 已经是最坏的情况了。

不过要记住在 Chord 协议中，前驱是一个独立的直接邻居指针，用于定义谁将数据交给当前节点存储。它与指纹表中的任何条目都没有直接关系，指纹表全部用于顺时针的路由加速。

导言#

第一章 分布式的基本特征#

分布式系统的目标、定义、特点#

分布式系统举例#

分布式系统的趋势#

分布式系统面临的挑战#

第二章 系统模型#

第三章 时间和全局状态#

基础概念#

同步物理时钟#

Cristian 方法#

Berkeley 算法#

NTP 协议#

逻辑时间和逻辑时钟#

Lamport 时钟#

Lamport 全序时钟#

向量时钟#

全局状态#

一致割集#

线性化走向和可达#

快照算法#

分布式调试#

第四章 协调与协定#

分布式互斥#

中央服务器算法#

Ring-based 算法#

组播+逻辑时钟#

Maekawa 投票算法#

分布式选举#

RingBased Election#

Bully Election#

组播通信#

可靠洪泛法实现可靠组播#

IP 组播实现可靠组播#

有序组播#

共识和相关问题#

拜占庭将军问题#

paxos 算法#

第五章 事务与并发控制#

事务的基本概念#

串行等价#

并发控制方法#

锁#

乐观并发控制#

时间戳排序#

方法之间的比较#

第六章 分布式事务#

基本概念#

原子提交协议#

单阶段原子提交协议#

两阶段提交协议#

分布式事务并发控制#

事务恢复#

第七章 复制#

基本概念#

容错与一致性#

可线性化#

顺序一致性#

因果一致性#

最终一致性#

复制的系统模型#

被动复制#

主动复制#

单拷贝可串行化#

gossip 系统#

第八章 分布式文件系统#

分布式文件系统的需求#

文件服务体系结构#

NFS 体系结构#

AFS 体系结构#

第九章 GFS#

GFS 简介#

GFS 的读、写、添加操作#

一致性模型#

第十章 P2P DHT 以及 Chord#

P2P 及其问题#

一致性哈希#

DHT 主要思想#

Chord#

第一章分布式的基本特征#

第二章系统模型#

第三章时间和全局状态#

第四章协调与协定#

第五章事务与并发控制#

第六章分布式事务#

第七章复制#

第八章分布式文件系统#