Computer System Engineer

Chapter 0. Concepts

• System: Interacting set of components with a specified behavior at the interface with its environment;

• Course Target: 在学习了一行代码从 C -> ASM -> CPU -> Pipeline 的过程是细节；这门课会从宏观角度（千万行代码执行）讨论系统多出来的特性特征；

• 14 Properties：

  • Correctness：以一个 UB 为例：

    xxxxxxxxxx
    char *buf = <...>;
    char *buf_end = <...>;
    unsigned int len = <...>;
    if (buf + len >= buf_end)
        return; /* len too large */
    if (buf + len < buf)
        return; /* overflow */
    /* write to buf[0...len-1] */
    

    指针加法溢出是一个 Undefined Behaviour，最后两行代码会被删除；

  • Latency：当今的芯片，光速也是瓶颈；

  • Throughput / Capability;

  • Scalability：分工的例子；

  • Performance Isolation：系统资源隔离，性能是否能隔离开？

  • Utilization：服务器资源利用最大化；

  • Energy Efficiency：能源利用率；

  • Compability: Intel Itanium vs AMD；

  • Usability: Windows Mobile；

  • Consistency: 12306 数据库；

  • Fault Tolerance: Cosmic Radiation；

  • Security / Privacy;

  • Trust: Fighting Club;

• Conflicts between 14 properties;

• M.A.L.H: Modularity、Abstraction、Layering、Hierarchy；

Chapter 1. Distributed System

1.1 Concepts

• Distributed System: A distributed system is a collection of independent computers that appears to its users as a single coherent system.

• Fault, Error, Failure

• Availability: X-nines to downtime;

  Metrics: MTTF（平均故障时间）、MTTR（平均修复时间）、MTBF（平均故障间隔）；

  MTBF = MTTF + MTTR；

  如何达到高可用性？

  • 使用 replication（重复备份）handling failures，只要一个能访问就行；

    会出现 data consistency 的问题。解决方案：主从备份、重复状态机；

  • retry（重复）handling failures

    对于 stateless app / service 来说是可行的。

    1. stateless 的 应用没有 data consistency 的问题；

    2. 某些类型的应用可以容忍 occasional inconsistency（如 Google Search）；

    3. LLM 服务不能通过 retry 容忍 inconsistency；

CAP: Consistency、Availability、Partition Tolerance（一致性、可用性、分区容忍）

• Consistency：分布式系统所有结点同一时间对某一数据的值是一致的；

• Availability：能保证一次请求一定能收到一次关于请求成功或失败的回复；

• Partition Tolerance：分布式系统中某个部分出现消息丢失或者错误，系统仍然可以正常运行；

  Partition tolerance means that a distributed system can continue to operate even if there is a communication breakdown between nodes. In other words, the system can handle network partitions, where some nodes cannot communicate with others due to network failures or delays. This ensures that the system remains functional and can recover gracefully once the partition is resolved.

CAP Theorem：一个分布式系统中，最多只能满足上述 3 中特性的其中两种。

并不是说满足了两种后，剩下一种完全没有，而是说剩下的一种无法完全保证。

1.2 Filesystem Intro: Single-node inode-based Filesystem

1.2.1 文件的定义

• 一种存储数据最自然的方法，一种高级别的对于存储的抽象；

• 两种性质：持久性、具有名称；

• 系统层使用硬件层的 modules 来构建对于文件的抽象：

  • OS Kernel 提供：OPEN、READ、WRITE；

  • Hardware 提供：API 相当复杂，但可以简化为：Read(block_idx: int)、Write(block_idx: int, data: Sector)；

    无法直接使用 Hardware 的抽象来实现文件，考虑几个问题：

    1. 存储一个远大于 Sector 的文件？

    2. 文件需要增大、缩小？

1.2.2 实现文件系统的目标：从 Native FS 开始

规定一个文件系统的 API（抽象文件系统的接口）：

• READ('name', offset, size) -> Array of data;

• WRITE('name', offset, size, data)；

然后 data 需要是一个有限随机大小；

如果我们直接用 Hardware 的 API 做一个 Native File System：

• 每个 sector index 作为文件名；

• 写文件要么是 append，要么 reallocate；

问题是：

• 如何找到空闲空间？（暴力扫描，效率低）

• 如何扩充一个文件？（可能需要移动大量的 sector 内容，效率低）

• meta-data overhead 比例很大：如果每个文件持有的 sector indices 都要保存（离散式），那么相当于每个 sector（大小由硬件厂商决定，4 ~ 256 bytes 不等）就要额外存放 8 bytes（需要能表示 sector 总大小）的数据，这是不能忍受的；

• 如果想要以字符串作为用户友好的文件名？

• 如果想对文件施加认证措施？

• ……

肯定不行。

我们需要借鉴 UNIX File System 的抽象（Naming Layers）：

1.2.3 Block Layer

Block：文件系统最基本的数据单元。把多个连续的 sector 看成一个 block；

• 一般大于磁盘 sector 大小、允许对硬件资源更灵活的管理（因为管理 sector 粒度非常影响性能 以及存储效率）；

  一个 block 如果等于 4 个连续的 sectors，那么 metadata 的 overhead 就会下降 4 倍；

  如何决定一个 block 的大小？它会影响 efficiency & utilization（回想 Memory Allocation）；

  太小（~ 1 sector）就会遇到和 sector 一样的问题，太大就会出现更多的 internal fragments；

• 目标：使用方法将 block 和 block number 映射起来：

  xxxxxxxxxx
  // 给定一个 block number 就能访问指定 block 数据
  procedure BLOCK_NUMBER_TO_BLOCK(int b) -> block
  return devices[b]
  

• 存储结构划分（加入 block 思想）：

  首先，我们将存储空间划分为 n 个 block。

  其次，我们需要让系统知道 block 是如何划分的，就需要将 block 的划分大小记录在指定区域内；我们定义这个区域为 Super block：

  

  一个文件系统中只有一个 super block，在一个文件系统被 Kernel mount 的时候会去读这个块；

  这个 super block 包括：

  • blocks 划分的大小；

  • 空闲的 block 数；

  • 有哪些空闲的 block（列表形式？）；

  • 其他文件系统的元信息（例如 inode 信息，之后讨论）；

  对于 “有哪些空闲的 block” 的问题，我们可以用 bitmap 的方式存放信息，每个 bit 1/0 来代表空闲情况，每个 bit 的 index 来代表 block 的 index；

  这样做的好处是，存放信息紧凑（节省空间），但读取麻烦（遍历），不过在很多场景下表现是不错的；

  

注：为了方便起见，在今后讨论 block 时默认一个的大小是 4 KB（现实中可以有其他大小）；

总结：block layer 把磁盘存储资源抽象成了一个大数组，每个 index 可以访问一个 block；

1.2.4 File Layer

有了 block 的抽象，在其上形成 file 的抽象就合理一些。

目标：我们想要抽象出以下内容：

• 一个文件是随机长度的线性的 bytes 数组；

• 文件可以存储大于一个 block 大小的数据；

• 文件可以自由扩大、缩小；

然后想要抽象文件的思路就很简单了：用 meta-data 声明一个文件所拥有的 block index 的集合。

这个声明 block index 的 meta-data 被称为 index node（inode）：

xxxxxxxxxx
struct inode {
    long block_nums[N]; // 8 bytes 来表示 block number
    size_t size;
    // other fields here...
};

理所当然地，inode 信息也应该持久化，那么它应该放在哪个 block 中由谁指定呢？

也很简单，我们单独指定一些 blocks 来专门存放文件的 inode 信息。那么又有一个问题：文件的数量很大导致 inode 的数量也很多，这样一个 inode 能描述的文件 block 数量很有限。

于是我们借鉴页表的思想，让 inode 越靠后的 blocks 指向越深的 indirect blocks，像这样：

但不直接使用页表的设计。因为考虑索引次数和实际大小：磁盘上索引一次的耗时很长，而且一个文件往往没有一整个 address space 那么大；

这样文件靠前位置的数据能很快索引（靠后的数据也可以先 pre-fetch），性能上获得提升。

另外，一个 indirect block 可以放在 data blocks 中，有些实现也会放到 inode table 中，和具体实现有关。

值得注意的是，一个 inode 的大小取决于文件系统的具体实现。它的大小会反过来限制一个文件最大能承载的容量上限（主要是限制了 block number 数，即便采用了多层 indirect 的方式也有影响）。

通过上面的设计，我们现在能够实现这样的映射关系：

xxxxxxxxxx
// 给定一个文件的 inode 和文件内偏移量，就能找到指定位置所在的 block
procedure INODE_TO_BLOCK(int offset, inode i) -> block
    o <- offset / BLOCKSIZE
    b <- INDEX_TO_BLOCK_NUMBER(i, o)
    return BLOCK_NUMBER_TO_BLOCK(b)

// 给定 inode 内的 block 在列表中的 index 就能找到 block number
procedure INDEX_TO_BLOCK_NUMBER(inode i, int index) -> int
    return i.block_nums[index]

总结：为了组织很多离散的 block 为一个文件，引入 inode 数据结构。inode.block_num[N] 中记录了文件的第 i 个 4K 内容放在哪个 block 上（block number）。

但是如果文件很大，那么就需要很多 block 来存放，这样 N 会很大（一个 4KB block 需要 8 bytes 描述 block number，那么一个 16GB 文件需要 4M 个 block，也就是 32MB 空间来记忆所有 block number），不现实。

因此我们给 inode block_num 数组靠后的几个 entry 采用多级 indirect 的方式来索引获得 block number，这样能存放更多的 block number；

1.2.5 Inode Number Layer

现在解决了一个文件的抽象。但是要找一个文件的数据首先就找 inode，我们说要单独为它们准备一个地方，这个 inode 存放的专门的位置就称为 inode table，这些 inode 的索引就是寻找 inode 的唯一标识：inode number。我们将这个抽象层称为 inode number layer；

其中 inode table 由一块块 block 组成，每个 entry 的大小就是一个 inode 的大小；

为了节省空间，防止开辟的 inode table 大小过大，我们可以考虑存放 inode table 的 table，让这个 table 的每个 entry 指向下一级 inode table 的起始地址（indirect）。这也是一种方法，不过性能会差点。

Inode Table 的起始地址是固定在 bitmap for free blocks 之后的位置，它可以放在 super block 中；而 inode table 可以指示哪些 inode number（index）是空闲的；

这样我们能实现新的映射关系：

​x
procedure INODE_NUMBER_TO_INODE(int num) -> inode
    return inode_table[num]

// 给定一个文件的 inode number，以及文件内偏移量，就能找到指定位置所在的 block
procedure INODE_NUMBER_TO_BLOCK(int offset, int inode_num) -> block
    inode i = INODE_NUMBER_TO_INODE(inode_num)
    return INODE_TO_BLOCK(offset, i)    // 之前实现的

到这为止，我们已经实现 “通过一个标识符（inode number）自由访问一个可伸缩文件的内容” 的目标了。但是还有一些需求没有满足：

• file 能否有一个 user-friendly 的名字？

• 考虑到用户态的 application，能否在此基础上包装一层，以便 OS 做权限控制？

总结：指定 inode 就需要让 inode 能够描述。这个时候我们将 inode 单独组织在一片 block 中（inode table），并且用索引来标识它们（所以 inode number 和位置有关）；

1.2.6 File Name Layer

现在我们为了实现 user-friendly name，我们再加一层 file name layer，将文件名（字符串）和 inode number 联系起来。这是个表的结构，也需要存起来，它应该存放在哪？答案是一种特殊的文件：目录。

也就是说，这种文件名 - inode number 的映射关系就用名为 “目录” 的特殊文件来保存（目录内也只包含这样的映射，不包含文件内部的任何信息）：

然后 inode 的结构可以更新为：

xxxxxxxxxx
struct inode {
    long block_nums[N];
    size_t size;
    int type;   // directory or regular file
    // other fields here...
};

注：在 EXT4（一个现代的 UNIX FS）中，规定 type：

• 0x0: Unknown;

• 0x1: Regular file;

• 0x2: Directory;

• 0x3: Character device file;

• 0x4: Block device file;

• 0x5: FIFO;

• 0x6: Socket;

• 0x7: Symbolic link;

这样我们能建立起新的映射关系：

xxxxxxxxxx
// 给定一个文件字符串名，以及它位于的目录文件的 inode number，就能找到文件的 inode number
// 就是在目录文件中找映射结果，LOOKUP
procedure NAME_TO_INODE_NUMBER(string filename, int dir) -> int
    block b
    inode i = INODE_NUMBER_TO_INODE(dir)
    if i.type != DIRECTORY then return FAILURE  // Not a directory
    // 遍历 directory 文件的所有 block data 匹配字符串
    for (int offset = 0; offset <= i.size - 1; ) do
        b <- INODE_NUMBER_TO_BLOCK(offset, dir)
        if STRING_MATCH(filename, b) then
            return INODE_NUMBER(filename, b)
        offset <- offset + BLOCKSIZE
    return FAILURE  // Cannot find the filename in dir

总结：inode number 是与 inode table 位置相关的标识，直接使用会各种问题，例如文件 inode 用户不友好、不好控制权限等问题。于是我们引入了 “目录” 这种特殊文件，来单独保存这种映射关系。

因此文件名不在文件里、不在文件的 inode 里，而是仅存在于目录文件里。

一般情况下 UNIX 目录没法直接看 directory 文件中的 raw content，需要用 /sbin/debugfs 来查看：

xxxxxxxxxx
$ debugfs <disk device> # enter interactive mode
$ dump <file> <output>
$ quit
$ xxd <output> # or hexdump -C <output>

注意到 2 个问题：

1. 上面的目录是按照 block 查找匹配的，如果文件名跨两个 block，应该怎么办？

   两种方法：一种是把算法写复杂一点，考虑边界情况；另一种是限制文件名长度，并且利用数据结构大小做对齐，使得文件名不会跨越两个 block。

   在 UNIX v6 中规定了一个文件名最大长度是 14 bytes，可能就说明了它是使用了后一种方法来处理的。

2. 上面的 LOOKUP 算法只能针对同一级目录下的文件。如果文件数量很多，我需要分多个目录层级（目录里套目录），这个时候我们要么使用递归查找（效率慢），要么引入一种新的描述方法，直接描述文件在层层嵌套的目录中的位置。这就是 path name；

1.2.7 Path Name Layer & Absolute Path Name Layer

为了解决上面多层目录文件定位的问题，我们引入了新一层抽象：path name layer；

对应新的映射关系如下：

xxxxxxxxxx
procedure PATH_TO_INODE_NUMBER(string path, int dir) -> int
    // 如果是单独的文件名（没有由“/”组成的 path），即递归终止条件
    if PLAIN_NAME(path) return NAME_TO_INODE_NUMBER(path, dir)
    else
        // 在当前目录（dir，context）下找最前项目录文件（例如 FIRST("a/b/c") = "a"）
        // 找到最前项目录后更新 context 为该目录，进入下一层
        // 找不到也递归终止
        dir <- LOOKUP(FIRST(path), dir)
        // 例如 REST("a/b/c") = "b/c"
        path <- REST(path)
        // 递归查询
        return PATH_TO_INODE_NUMBER(path, dir)

注意到目录结果是否有终极父结点？答案是有的。UNIX FS 的所有文件全部是 /（根目录）的子文件。

而以 / 开头的就是绝对路径。当然 / 目录文件会放在 inode table 的特殊位置（一般 inode number 为 1），方便让系统查找（提供递归终止条件）。

那么一个相对路径和绝对路径是能相互转换的。

xxxxxxxxxx
procedure GENERATEPATH_TO_INODE_NUMBER(string path) -> int
    // 就以 / 的 inode number 为 context 开始查找
    if path[0] == '/' then return PATH_TO_INODE_NUMBER(path, 1)
    // 开头没有 '/' 说明是相对路径，则从 wd（working directory）的 inode number 开始
    else return PATH_TO_INODE_NUMBER(path, wd)

1.2.Ex Quiz

如下图的文件系统中，系统如何查找 /programs/pong.c？

• 解析 path 为绝对路径，找 /（inode number = 1）的目录文件的 block number：14, 37, 16；

• 先在 block number = 14 的 block 中查找 "programs"，找到其映射的 inode number 为 7；

• 索引到 inode table 中，发现 "programs" 目录文件占用 block number：23, 28, 55, 51；

• 现在 block number = 23 的 block 中查找 "pong.c"，找到其映射的 inode number 为 9；

• 索引到 inode table 中，发现 "pong.c" 的内容占用 block number：61, 44, 15；

• 现在可以按 offset 在 block 中读取数据了；

1.2.8 Hard Links

在 path name layer 的基础上，做一种快捷方式，可以用较短的 path name alias 到很长的 path name，实现快速的解析和访问。

为了实现这个目标，我们想出两种接口：

• LINK(filename, shortcut)：为一个 path name 建立 shortcut，实际上就是在 dirname(shortcut) 目录文件下创建新的映射，这个映射用的 filename 的 inode number 和 shortcut 的名字；

  这就是 UNIX 中的 “硬链接”（hard-link）。

  这下就能回答，为什么硬链接不能跨磁盘（文件系统）创建了。

  因为硬链接名和原文件名映射的是同一个 inode number，而一个磁盘上有一个独立的 inode table，相互独立、两个表间一个 inode number 可以表示不同文件；

• UNLINK(filename)：解除 filename 与 inode number 的映射。

  就是 UNIX 中的 “删除”（rm）；

另外我们需要设计几条规则：

• 引用计数：当 file name 与 inode number 的最后一条映射解除后，可以视作文件被删除（free inode / block）；

  因此我们需要 inode 的结构中含有引用计数：

  xxxxxxxxxx
  struct inode {
      long block_nums[N];
      size_t size;
      int type;   // directory or regular file
      int refcnt; // reference count
      // other fields here...
  };
  

• 有向无环：由于建立了 path name layer 后，文件系统组织成了树形结构，因此需要有向无环（directed-acyclic）的特性；

  因为如果存在自环，引用计数的系统就会存在问题。这会给系统带来无法释放的 inode，明明已经没有用了（没有任何从 / 出发能访问到这个 inode 的文件名），但引用计数仍然存在，导致磁盘空间资源泄漏；

  

  因此 UNIX 系统规定不允许给目录创建硬链接，就为了避免这种情况。

  但是 . 和 .. 是特例，它们是指向当前目录 或 上层目录的硬链接，只能由文件系统自己创建确保不会出现资源泄漏的问题；

  同样，UNIX 系统不允许直接删除一个非空目录，而是需要先删除内部映射的文件，再删除目录本身，其目的也是类似的（防止资源泄漏）。

• 根目录回环，对于 /. 和 /.. 都指向 / 自身；

有了 LINK 和 UNLINK 的接口和语义，我们就能在此基础上实现更丰富的功能。

例如重命名 和 移动，它们本质上在 UNIX FS 中是同一种操作。无非是 将一个文件原来记录在目录 A 中的映射关系移动到目录文件 B 中记录，其中 A 和 B 可以相同（重命名操作），并且移动过程中映射的文件名可以改变（移动操作）；

那么实现这个功能：move(from_name, to_name)，就可以由下面的操作完成：

1. UNLINK(to_name)：如果有 to_name 就会覆盖，相当于先删除；

2. LINK(from_name, to_name)：在 dirname(to_name) 下创建一个 from_name 的 inode number 和 basename(to_name) 的映射；

3. UNLINK(from_name)：最后把原先的文件删除即可；

但这么做有问题：如果 OS 在 1~2 步骤间掉电，那么 to_name 的文件会被删除，但 from_name 还没有移动，这就会产生意料之外的行为。

1.2.9 Symbolic Link Layer

为了解决 “不在一个文件系统下，却想要创建快捷方式” 的问题，UNIX 提供了更高一层抽象：软链接层。

这个软链接也是一个文件，不过它和硬链接产生的 regular file 不一样，它是一种特殊的文件，里面只包含要链接文件的 pathname；

因此，和硬链接不一样的一点是，甚至目标文件不存在时，我也能创建一个软链接（因为这个文件只包含 path name，并且是独立的、特殊文件类型，本身有独立的 inode）；

例如：

x
lrwxrwxrwx  1 xhw xhw   14 Oct  7 20:36  tiler-json -> tiler/geojson/

为什么 tiler-json 软链接的大小是 14 bytes？因为它内部内容只有字符串 "tiler/geojson/"（长度 14）！

我们可以通过 readlink 指令阅读软链接的实际内容。

所以，symbolic link 是以 path name 与目标文件关联，不受 reference count 影响；

hard link 是以 inode number 与目标文件关联，会影响 reference count，并且不能跨文件系统；

总结区别：

• inode 是否独立？

• 是否影响 reference count？

• 是否能跨文件系统？

• 存放内容的机制是怎样的？

sidebar: 在 cd 到一个软链接指向的目录后，如果想显式去往当前目录的真实上级目录（不考虑软链接），则需要指定 cd -P ..，否则大多数 shell（bash / zsh 等）会认为你是想去历史上上一次 context 位于的目录；

1.3 Implement the File System API

在了解 FS 基本的设计理念和规约之后，我们可以着手实现一个 file system 了。首先列出 OS system call 需要的 File System API：

• CHDIR, MKDIR；

• CREAT, LINK, UNLINK, RENAME；

• SYMLINK；

• MOUNT, UNMOUNT；

• OPEN, READ, WRITE, APPEND, CLOSE；

• SYNC；

在此之前，我们揭晓 inode 数据结构中剩下的数据成员。剩下的数据成员没有体现在 File System 的设计理念中，是因为它们是 OS 管理文件必要的其他元信息，和文件存储本身关系不大：

xxxxxxxxxx
struct inode {
    long block_nums[N];
    size_t size;
    int type;   // directory or regular file or symbolic link
    int refcnt; // reference count
    // other fields here...
    int userid;
    int groupid;
    int mode;
    int atime;  // 文件内容上次被访问的时间（READ）
    int mtime;  // 文件内容上次更改的时间（WRITE）
    int ctime;  // inode 上次更改的时间（例如 LINK 改了 refcnt，或者改了权限）
};

现在我们再回头看看磁盘文件系统中详细是什么：

提问：2T 硬盘的 data free block bitmap 大约占多大的空间（忽略 inode free block bitmap 和 boot/super block）？

2TB bytes 空间需要 2T / 4K 个 bit 作 data free block bitmap；

2T / 4K (bit) / 8 (bit / bytes) = 64 MB；

1.3.1 OPEN

此操作需要完成以下步骤：

1. 检查当前用户权限；

2. 更新文件 atime（也可在 READ 时更新）；

3. 返回临时的、对某个进程而言的，该文件的 short name（file descriptor），这样不必反复进行字符串比较；

为什么 short name 不使用 inode number（或者 inode 指针 / block number）？有以下几点考量：

• Security：file descriptor 相当于一层 indirect layer，让用户态无法直接访问内核态数据；

• Non-bypassability：任何 FS 操作都由 Kernel 完成；

其中还需要回想一下 file descriptor table、file table、v-node table 三者的关系及其组成。

fd table 保存了：

• file descriptor；

• file table entry index；

file table 中保存了：

• inode number；

• file cursor；

• file table entry reference count（不是 inode reference count）；

其中 fork 出的父子进程一开始复制 fd table（但不共享）、共享 file table entry；

所有进程共享一个 file table，但不一定共享 file table entry，如图：

注意 file cursor 可以被 SEEK 操作改变、随着 READ 而不断前进；

搞清楚细节后就可以开始实现 OPEN 方法了：

xxxxxxxxxx
procedure OPEN(string filename, int flags, int mod) -> int
    inode_num <- PATH_TO_INODE_NUMBER(filename, wd)
    if inode_num == FAILURE and flags & O_CREATE then
        inode_num <- CREATE(filename, mode)
    if inode_num == FAILURE then
        return FAILURE
    
    inode <- INODE_NUMBER_TO_INODE(inode_num)
    // 检查当前用户权限和其要求的权限，对于指定的 file 是否有权
    if PERMITTED(inode, flags) then
        // 更新 file table 和 fd table
        file_table_index <- INSERT(file_table, inode_num)
        fd <- FIND_UNUSED_FD_TABLE_ENTRY(fd_table)
        fd_table[fd] <- file_index
        return fd
    else return FAILURE

1.3.2 READ

在打开文件后，READ 操作也不难，尤其是我们已经清楚了 fd table 和 file table 的机制：

xxxxxxxxxx
procedure READ(int fd, char[] &buf, int n) -> int
    // 获取 file cursor
    file_table_index <- fd_table[fd]
    cursor <- file_table[file_table_index].cursor
    // 检查实际能读取的长度
    inode <- INODE_NUMBER_TO_INODE(file_table[file_table_index].inode_number)
    m <- MINIMUM(inode.size - cursor, n)
    // 更新 atime
    atime of inode <- now()
    
    // 读取文件数据
    if m <= 0 then return EOF
    for (int i = 0; i <= m - 1; ) do
        // 一次读取不超过一个 block
        b <- INODE_NUMBER_TO_BLOCK(cursor + i, inode_number)
        copy_size_in_one_time <- MINIMUM(m - i, BLOCKSIZE)
        COPY(b, buf, copy_size_in_one_time)
        i <- i + copy_size_in_one_time
    file_table[file_table_index].cursor <- cursor + m
    return m

现在我们综合起来讨论一下，1 次 OPEN、1 次 READ 大量数据需要多少次磁盘的 read 和 write：

xxxxxxxxxx
/* /foo/bar 存在 */
int fd = open('/foo/bar', O_RDONLY);
char buf[3 * BLOCKSIZE + 1];
read(fd, buf, 3 * BLOCKSIZE);

• 首先 open 时：

  • 按 / inode number = 1，找到 / 的 block number（磁盘 read 一次）；

  • 按 / 的 block number 找到 / 的 block 中的内容并扫描 "foo"（磁盘 read 一次），顺便找到它的 inode number；

  • 按 /foo 的 inode number 去 inode table 找 block number（磁盘 read 一次）；

  • 按 /foo 的 block number 找 block 中的内容并扫描 "bar"（磁盘 read 一次），顺便找到它的 inode number；

  • 注意：最后得到 /foo/bar 的 inode number 后，还需要去 bar 的 inode 中读取并检查权限信息（磁盘 read 一次）；

• read 因为跨了 3 个 block，因此分 3 次 read；

• 第一次 read 时：

  • 按照 fd table & file table 找到 inode number（读内存），然后去 inode table 中找 /foo/bar 的 block number（磁盘 read 一次）；

  • 再按 block number 去文件占用的 block 中读取并复制一段数据到内存 buffer 中（磁盘 read 一次）；

  • 再去文件 inode 中修改文件 atime（磁盘 write 一次）；

• 第二次、第三次同理，不过遍历了 /foo/bar 的 inode 中的 block number 数组；

在 UNIX FS 加载过程中，如果有参数 -noatime，那么 READ 就不会每次 磁盘 read 时写一遍 atime，而是在文件关闭时写一次；

1.3.3 CREAT

如果是创建的话，除了文件（包括目录文件）内自身的数据，还需要注意更改 data free block bitmap、inode free block bitmap 的数据（一般不考虑 super block，因为在 FS 加载时就读完了）；

下面的图片是这段代码的 timeline：

xxxxxxxxxx
/* /foo/bar 不存在 */
int fd = open('/foo/bar', O_CREAT | O_WRONLY);
char buf[3 * BLOCKSIZE + 1];
read(fd, buf, 3 * BLOCKSIZE);

那么现在有个问题，在写一个新的文件的时候，下面哪个顺序更好？

1. Update block bitmap, write new data, update inode (size and pointer)；

2. Update block bitmap, update inode (size and pointer), write new data；

3. Update inode (size and pointer), update block bitmap, write new data；

最好的是第 1 种方案。

第二种坏在如果在第二步~第三步间断电，那么内存中原来被释放的数据可以在下次启动时被完好地读出来，造成信息泄漏的隐私安全问题。

第三种在哪一步断电都有安全危险。

第一种最坏的情况不过是泄漏了一些磁盘空间，而且可以通过磁盘扫描（扫描 free bitmap 和实际 inode 引用）进行纠正。

1.3.4 WRITE, APPEND, CLOSE

• 就像上面演示的一样，WRITE 操作类似 READ 操作，不过需要分配一些新的 block、更新 inode 的 size 和 mtime；

• APPEND 操作和 WRITE 类型，向文件尾的 block 写数据，必要时分配新 block，更新 inode size 和 mtime；

• CLOSE 操作则需要完成 释放 fd table、减小 file table reference count、释放 file table 中 refcnt 为 0 的 entry；

上面的操作在中途断电后都会造成 inconsistency 的问题；

1.3.5 SYNC

反复的磁盘 read 和 write 在磁盘看来问题不会那么大，因为磁盘厂商可能会在其中做一些 block cache；

因此可能在写完一组数据后 / 批处理后 / 关机前需要真正落盘（force flush），而不是放在 cache 中。所以产生了这个指令。这条指令会让所有对 file 的更改全部落盘。

这条指令的问题是，在断电后会出现 inconsistency；

1.3.6 DELETE

其实就是我们之前实现的 UNLINK（取消硬链接）接口，和 WRITE 是类似的反操作。

不过需要注意的是，如果一个进程打开一个文件的时候，另一个进程删除了这个文件，虽然这个 file 的 inode reference count 为 0，但在 file table 中如果这个 inode 的 file table entry reference count 不为 0，因此 inode 不会被释放。直到进程关闭了这个 inode 文件后、file table entry 中所有对于 inode 的 entries 全被释放，该文件的 inode 才会被释放（+ free bitmap）。

Window 上删除一个被打开的文件是禁止的，实现方式类似文件锁。

1.3.7 RENAME

实际上我们之前讨论过这个问题，使用 LINK 和 UNLINK 方法实现 RENAME，但是 UNLINK + LINK + UNLINK 的操作在第 1-2 步间掉电时会出现意外的行为（to_name 丢失），所以改成两步：

1. LINK(from_name, to_name)（weak specification）：将 to_name 映射的 inode number 转为映射 from_name 指向的 inode number，并且减小 to_name 指向 inode 的 refcnt；

   Q&A：思考是否有必要增大 from_name 的 inode refcnt？

2. UNLINK(from_name)（weak specification）；

注意到：

• to_name 的 inode number 与原来的 from_name 的 inode number 完全相同；

• 如果在 1-2 步间断电，那么需要注意，from_name 的 inode refcnt 在理论上是需要增大的，但实际上上面的步骤没有更改，所以为了保证 inode 一致性需要在恢复时增大 from_name 的 inode refcnt；

  并且在文件系统恢复时需要删除 to_name 的映射；

1.4 RPC

• 定义：远程跨进程调用；

• 一段话概括：

  RPC simplifies programming w/ an interface similar to local function call;

  RPC uses stubs to avoid handling argument encoding/decoding and send/receiving messages, etc.

  Ensure correctness & efficiency.

• 目标：It should appear to the programmer that a normal call is taking place；

• 实现思路：build the RPC atop of the socket interface；

  • 要求：Hide the construction of messages and remote invocation logic from the developers；

在单个语言层面其实有各自实现。

例如 Java 中有 RMI（Remote Method Invocation，面向对象版本的 RPC）；

1.4.1 RPC Message

应该包含：

• Service ID (e.g., function ID)；

• Service parameter (e.g., function parameter)；

• Using marshal / unmarshal；

  保证在内存中的数据结构在网络上传递，并且在 server 端能够正确解析；

  例如：[TYPE][SIZE][DATA...]；

费时：

• 系统调用 domain switch；

• 消息 copy、marshal；

注：最初的 RPC 库安排的 Request Message 有如下构成：

Xid（Transaction ID）、call/reply、rpc version（for compatibility）；

program #（Process ID / port）、program version、procedure #（Function ID）；

auth stuff、arguments；

而 Reply Message：

Xid（Transaction ID）、call/reply；

accepted? (Yes, or No due to bad RPC version, auth failure, etc.)；

success? (Yes, or No due to bad prog/proc #, etc.)；

auth stuff；

results；

其中消息传递的挑战性很大：

• 消息传递方式是 value 而不是 reference。所以传输前需要确保 pointless；

• DSM（Distributed Shared Memory）：可行性有点低。关键是任务难以干净地切割。如果两台机器需要操作同一片内存地址，那么数据需要频繁在多台机器间传递。因此它只能用在特殊的业务场景中；

• 分布式系统间兼容性不佳。有很多不同:

  • byte ordering;

  • sizes of integers and other types,floating point representations;

  • character sets

  • alignment requirements

  • etc.

我们对于消息传递的目标如下：

• 正确传输：Correctly encode and decode a object to a byte stream；

• 兼容性：Support multiple language, multiple versions of program；

• 传输信息效率：Reduce the traffic transferred from the network; Network bandwidth is a scarce resource!

如果是 Texture Format：

• 优点：human-readable、easy to debug；

• 缺点：

  • Ambiguity around encoding of numbers（如整型类型模糊）；

  • Binary String have to re-encode the string as Base64（二进制字符串需要特殊编码）；

  • use more bytes to store the data（空间效率低）；

如果是 Binary Format：

• 优点：可以极致压缩、表达数据更准确（约定 schema: Interface Definition Language (IDL)）、解析/存储更快、传输效率高；

• 缺点：less human-readablity；

1.4.2 RPC Implementation

框架通过声明自动化生成代码，实现 参数编解码、收发消息、消息传输 等动作；

Generate stubs from an interface specification；

• Tool to look at argument and return types；

• Generate the marshal and unmarshal code；

• Generate stub procedures；

消息传递需要确保：正确性、固实性、兼容性；

RPC 传输协议：

• TCP/UDP：根据实际场景选择；

  • 对网络环境要求高的请求使用 TCP；

  • 网络本身很好几乎不出问题的内网中，或者网络环境要求不高的请求可以使用 UDP；

• 是否使用新的网络协议？例如 RDMA（Remote DMA，某设备绕过 CPU 复制内存中的数据）；

1.4.3 How does RPC Handle Failures?

A user sends an RPC but the server does not reply, possible reasons:

• 请求丢失；

• 消息拥塞（网络或服务器超负荷）；

• 远程服务器节点崩溃；

处理方式要根据：

• 前提语义：at-least-once、at-most-once、exactly-once；

• 服务性质：是否幂等（重试的可行性）；

1.5 Distributed File System

在 RPC 的帮助下可以建立一个分布式文件系统。

目的：file system scalability；

访问远程文件的设计办法：

• 显式声明（主动写网络访问的函数，例如 FTP/Telnet/网盘等） (knowing it is a distributed file system)；

• Transparent Approach（例如 NFS/GFS 等）：应用程序访问远程文件就像访问本地文件一样的方式；

  这使用了 remote access model：

  文件服务通过 RPC 暴露了一系列和本地文件系统类似的 API 以供调取；

如果我们使用显式访问的方式来访问文件行不行？有问题：

• （资源浪费）Wasteful “what if client needs small pieces?”；

• （异常处理）Problematic “what if client does not have enough space?”；

• （数据一致性保持）Consistency “what if others modify the same file?”

1.5.1 NFS: Network File System

Designs

设计目标：

• 任何机器可以作为 client 或 server；

• 可以支持 diskless 工作站；

• 支持不同的部署特性（Different HW, OS, underlying file system）；

• 远程调用无感知（使用 remote access model）；

• 轻松从 failure 中恢复（Stateless, UDP）；

• 高性能（Use caching and read-ahead）；

NFS 对外界发布的 API：

注意到几点：

• No Open & Close;

  为什么 NFS 中没有 OPEN，主要看 OPEN 的作用：

  • 检查用户权限；

  • 更新 atime；

  • 返回一个同进程中使用的 file short name（fd），并且 file descriptor 管理在 fd table 中；

  如果要在 NFS 中实现 OPEN，则 RPC 会变成 stateful 的请求。

  而 stateful RPC 难以维持：

  • better fault tolerance（server 挂了/reboot）；

  • scalability & performance（大量 client 请求？）；

• Use file handler instead of fd / inode number;

  file handler 应该用什么？

  它的作用就是用来指定/区别 server 上的文件。

  • 不是 fd: fd 在打开时生成，但 NFS 没有 OPEN 操作；

  • 不能用 pathname / filename：因为假设有两个 client，一个在改目录名 dir1 -> dir2; dir3 -> dir1，另一个在打开这个目录中的文件 dir1/f；

    按 Unix Spec，最终修改的文件应该是 dir2/f，这在 NFS 内不方便实现；

  • 不能用 inode number：假设有两个 client，A 在打开某个文件，B 在这个文件打开后、阅读前删除了这个文件，并创建了新文件；如果这个时候 A 如果读这个文件，就会发现文件根本不是之前的；

    解决方案：让 A 读之前的文件（但是是 stateful 的，并且 client 可能不会释放，因此在 NFS 场景下不能使用这个方法），或者报错；

    这里就没有遵循 Unix Spec（读 previous file）；

  最终实现方法：在 Inode Number 基础上加入 Generation Number（File Handler 的真实身份）。每当分配一个 inode number 后，generation number 自增；如果出现上述情况，则 reader 的 file handler 和新的 file handler 的 generation number 不一致，因此可以报错；

• Use offset directly instead of file cursor;

  保持 Stateless（幂等性）: 简化错误处理，at-least-once 语义；

  但是像 WRITE 这样的调用，显然还是 at-most-once 语义。两个 client 如果在写一个文件，如果不做具体措施处理，一个很可能会覆盖另一个的操作。

  一个可行的解决方案是 server 管理一个 “soft state”（例如 reply cache）；

当一个应用尝试读一个远程文件时：

Performance & Improvements

分析：有时候 Network File System 会比本地磁盘还要快（取决于网速和文件服务器性能）；

优化：在 client 端做 cache；

系统优化 3 大件：Cache、Hash、Batch；

• 目标：减少远程操作数；

• 缓存内容：read, readlink, getattr, lookup, readdir；

  • client 缓存文件数据：buffer cache；

  • client 缓存文件属性信息；

  • client 缓存 pathname bindings（为了更快的 lookup）；

注：在 Server 端，OS 会自动地 cache；

• 缓存的问题：数据一致性。无法读到最新修改的数据。解决方案：

  • Close-to-open Consistency：

    • 打开文件前检查文件属性（最后修改时间）并与 cache 对比；

    • 当关闭时向服务器 flush cached 信息，server 在 CLOSE 这个文件时发现是 dirty 的，则写回文件；

  • Read/Write Coherence：

    • server、client 都保存一份文件的 timestamp；

    • 当文件打开 / server 提醒时，比较最后修改时间，如果 remote 更新则 invalidate cache；

    • 总是在一段时间后取消 cache 的有效性（文件 3s，目录 30s）；

    因此 inconsistency 可能总是会存在 NFS 中，但是能保证最终一致性；

除了 cache，还可以从 read-ahead（顺序读文件时，预加载）、消息网络传输压缩等思路考虑。

Drawback

NFS 目前还是基于单机的远程文件系统。

• （Capacity）单服务器容量上限（一个服务器最多插那么多磁盘）；

• （Reliability）可靠性不佳（server 挂了就没了）；

• （Performance）文件读写性能限制在一个文件、一个服务器的网路带宽上；

想法：把很多台机器放在一起组成一个超大的文件系统。

具体实现思路是做手动的分区和备份——但不好，又回到了 FTP 的样子。

也许我们没法完全重用 inode-based file system，需要对它做一些改进：

• Block Layer 改进为 Distributed Block Layer（增添 scability）：

  • 访问方式改进：将访问 block_id 扩充为 <mac_id, block_id>（MAC 地址可以定位机器）；

  • 如何找 free blocks：最好不要轮询尝试。最好使用 master 结点管理 free blocks 的 meta-data，并且所有 block allocation/deallocation 工作移交给 master node 完成；

• File Layer （Inode）：几乎不需要变动，只需要把查找 File Inode Block 的 block_id 改成上面定义的扩展形式就行；

  不过还要考虑性能问题，以后再来讨论；

• Inode Number 改进为 Distributed Inode Number Layer：把 Inode Table 和 free blocks 信息一起放到 master node 中。

• File Name Layer 目前还不需要改变！

这样的改进也只能改进 capacity，没法提升：

• reliability（master 结点、存放 blocks 的结点挂的问题）；

• fault tolerance / correctness（一旦有一个错误出现，会导致整个系统 file system corrupted，这是很严重的问题）；

• performance：由于需要多次反复查询，path lookup 会很慢（不过可以通过 cache 缓解）；

想要进一步解决上面的问题，还需要更强的武器（如 data replication，但又会引入数据一致性问题）；

1.5.3 Case Study: Google File System

Design Assumptions: environments

• 文件本身很大（例如 large web index）；

• failures 很常见（成百上千台机器，出错是普遍而不可避免的）；

• 文件写的方式大多数是 Append-Only 的（随机写的情况相当少）；

• workload 大部分是 sequential read（large read streams）；

• 设计需求：scalable、data-intensive、fault-tolerant、high performance；

GFS Interface

• 不完全支持 POSIX API；

• 基本操作：create/delete/open/close/read/write；

• 额外操作（基于应用场景作出优化）：snapshot/append；

• 不支持的操作：link, symlink, rename；

  原因：这些操作在 failure 时需要保证一致性，需要花精力处理这些问题。而目前分布式事务实际上没法解决所有问题，所以就干脆不用了；

GFS Architecture

这很像我们之前尝试改进的 NFS 的做法：

• 一个 master 管理 chunks，map files to chunks；

• chunks server 提供固定大小的数据存储空间，并且可以提供 replication & backup（异地亲和性和容灾措施）；

为什么文件使用 64 MB 的 large chunks 作为文件存储基本单位？

• 减小网络交流频率：网络通信开销大，通过增大 chunks 牺牲一部分 utilizations 换取更少次数的请求（而且在 design assumptions 中说了 workload 的大部分文件都很大）；

• 提升可连接的 TCP 数量上限：更小的 blocks 分散在更多的机器上，需要维持的 TCP 连接更多，实际能连接的能力就下降了；

• 减小 metadata 的大小，以便 master node 可以将信息存在内存中，加快访问速率；

GFS 还有更多的机制：

• 32-bit checksum for each chunk；

• globally assigned 64-bit integer ID for chunks（by master when creation）；

• （scalable replicas）more replicas for popular files；

Comparison between Improved NFS & GFS

• GFS 抛弃了 Inode Layer，直接将文件和 chunks 管理在 master node 中；

  有助于简化设计、提升性能、简化正确性管理；

• 使用相当大的 chunks 来直接存放文件；

• huge chunks 会做 replications 来保证 fault tolerance 和 high performance；

• GFS 只使用 1 个 master node：可以保证设计简单，同时有多种方式保证安全和可用性；

• "file-chunks" map 建立在 master 的内存中（用 operation log 持久化保证数据安全）；

  而 "chunk ID - chunk" map 可以不需要 log 放在内存中，然后在 startup 时询问 chunk servers 建立起来就行；

  优势有很多：

  • "file-chunks" map 本身是 hotspot，这样能极大优化性能；

  • 更简单的数据一致性的管理；

  • master 控制整个映射机制，确保数据最新；

GFS Interaction Model

• 没有 OS 级别的 API；

• 只有需要 meta-data 时与 master 交互，其余时候直接与 chunk server 交互，不会造成 master node 拥塞

  这也是设置 1 个 master node 的原因之一；

• No Cache: client/server 都是这样。这是由 design assumptions 决定的。workload 中大多数是超大文件，用到 cache 的机会很少；

  Client 也可以 cache meta-data，进一步减轻 master node 的负担；

Reading a file in GFS

Writing a file in GFS

特点：

• （原理复杂）more complex, because we need to deal with the consistency issue（应对两个 client 改一个文件的问题）；

• GFS adopts a relaxed consistency model（后面讨论 “relaxed consistency model”）；

• 方法的实现高效简单；

设计目标：

• 仅保证最终一致性：Each replica eventually have the same data；

• 减少与 master 的交互（不然 master 就会成为瓶颈）：Reduced communication with the master；

为了保证一致性、消除并发写冲突，需要在同一组 replicas 中选一个 chunk server 作为 a single primary（leader）来统一协调写操作。有两个问题：

master 如何选择一个 primary？这个 primary 不能持久，因为每台机器都有可能故障，而是定期随机地在每组 replicas 中通过给予 “a chunk lease”（租约）来选 primary，在这些 replicas 中只有这个 chunk server 才能修改 chunk（并且心跳连接）；

允许允许续租机制；

更改 primary 后，master node 会通过更新（增加）chunk version 并通知 replicas 来完成。

因此写操作分为以下几个阶段：

• phase 1 传输数据（Data Flow）：

  • Client App 会得到一个要修改数据所保存的 replicas list，然后向最近的 chunk server 传输数据，并且采用 pipeline forwarding 的方法向其他 replicas list 中的 chunk server 传递；

    不关心顺序、不存在写冲突，只管数据传递，解决性能、吞吐量；

    注意：这种 pipeline forwarding 的效率优于从单个机器上并行传数据（由于一台机器的网络带宽上限），可以自己画图理解。

  • Chunk Server 在收到数据后不会保存，而是放在内存中（memory cache）；

• phase 2 写数据（Control Flow）:

  • Client App 等待 replicas list 中的 chunk server 回复确认（ACK）后，再向 Primary Node 传递写请求；

  • Primary Node 再串行向各个剩余 replicas 中下达将刚刚 cache memory 中收到的数据修改落盘；

    The primary is responsible for serialization of writes (applying then forwarding);

    并且利用 master 管理的 chunk version 判断 replicas 中是否有过时数据、是否应该覆盖等等。

    由 Primary Node 关心写顺序，解决写冲突、一致性问题；

  • 当 Primary Node 获得所有 replicas 的修改确认后，再向 Client App 发送确认回复；

GFS 的写操作对 atomic append 非常友好：

• Google 业务逻辑大多是日志型的数据结构：顺序写远多于随机写；

• Append 写法总是能保证最终一致性（哪个行数多哪个新，不需要考虑覆盖问题），因此 GFS 的 weak consistency model 是有效的；

Naming in GFS

GFS 采用 simple flat naming，也就是不存在常见文件系统的 “目录” 结构、不存在 alias（即软硬链接）。因此 files namespace 就是一个查找表（lookup table），直接将 pathnames 映射到 file metadata（就像 KV Store）；

HDFS

HDFS（Hadoop Distributed File System）：一个 Apache 开源的分布式文件系统实现，受到 GFS 的启发（架构几乎一样，只是改了术语）；

Summary

• 设计一个 Distributed File System 并不简单，没法直接用 single inode-based file system + RPC 实现；

• 考虑 performance、consistency model、failure handling；

• 学习了 NFS 和 GFS 的案例：

  • NFS 不是 scalable 的；

  • NFS 不支持 fault tolerance；

  • NFS 在大多数场景（局域网文件共享）下足够；

  • GFS 使用 relaxed consistency model 在并发写同一数据时是 undefined behavior，但是可以支持 append 的最终一致性；

  • GFS 使用 single-node master：好处是简化设计、加速请求（并且交换数据量少）；坏处是牺牲一部分可用性。这在后续的 GFS 版本中有所改进；

  • GFS 是一种根据 Google workload 改良的文件系统，适用于它的 design assumptions（例如像数据库场景，就不适用）；

1.6 KVStore: System with a Simpler API

Concepts

首先进行存储抽象，来定义讨论的范围：

• 每个数据值（Value）对于底层存储设备/数据库需要是模糊的；

  • The K and V can be arbitrary byte-sequence (e.g., JSON, int, string)；

• 数据由 Key（K）索引，其本身也是一个数据；

• 数据需要存放在磁盘上（需要 fault tolerance、a large capacity），也可以放在内存中；

我们定义针对这种数据的存储系统为 “Key-Value Store System”（KVStore / KVS）；

然后定义 KVS 的 API：

• Get(K) -> V；

• Scan(K1,K2) -> V[]（Optional）；

• Update(K,V)、Insert(K,V)、Delete(K,V)；

Design Natïve KVS

那么如何实现 KVStore 系统呢？有个 naïve 解决方案：

• Key: The file name (may include the path)

  • Assume the key is not so long；

• Value: The file content;

这样 GET 就是 OPEN + READ，INSERT 就是 CREATE + WRITE 等等，我们就可以利用类似文件系统的方法来处理 KV Store 的问题啦！

但有问题：

• 文件系统是为比较大的文件所设计的（例如图片、视频的 KV 存储）。对于较小较多的文件，基础的 block 大小会降低存储效率（如何快速高效存取小型数据）；

• 并且文件系统没法有效 索引/查找 每个文件内的数据，不满足 KV Store 中的需求；

综上：

• 系统调用开销大（mismatched interface）的问题；

• 空间利用率比较低的问题；

• 数据索引性能问题；

Improvements I: Redesign Implementation & Pack Data

我们想出一个主意：

让一个/多个文件放多个的 kv data，让不同的 kv 打包进同一个 disk block 中；

这样缓解了上面系统调用开销大、空间膨胀等问题；

接下来，我们只需要在文件系统的基础上来设计 KV Store 系统就行了！

为什么要借鉴文件系统？

• We still need a system to interact with the disk hardware

• （还是要依赖于 file system）Though modern KVS may also bypass the file system, but is uncommon；

第一个目标：如何在 natïve KVS 上实现 UPDATE(K, V)？

两种策略：

• 直接改文件内容；

• 在文件后面追加更改的信息；

根据 ICS / 存储介质基本知识，顺序写远远快于随机写，因此我们选择第二种方案。

这样 INSERT 轻松完成，DELETE 可以通过插入 (K, NULL) 来完成（最后需要进行定期 GC 来避免写放大）；

这种 Append-Only 的文件格式被称为 Log-structured file（an append-only sequence of records）；

最终我们获得如下好处：

• Suits the performance of underlying hardware（磁盘顺序写快）；

• Ensure consistency under failure，因为 append 写总是能保证最终一致性；

但是！我们还有最后一个 API 没考虑：GET(K)（或者 SCAN(K1, K2)）。

结果因为追加更新的性质，我们需要最坏 $O(n)$$O(n)$ 的查找力度（这在大型文件中相当讨厌！）；

Improvements II: In-memory / On-Disk Index For Read & Search

为了解决这个问题，我们可以借鉴数据库的 “索引” 来加速查找工作。

• 索引是从 primary data 中提取出的额外数据结构；

• 它可以添加、删除而不影响原始信息的正确性（只会影响性能）；

像 B+Tree, HashTable 都可以作为索引。其实我们发现之前已经用过类似的索引结构了：文件系统中的 inode table 就是对 inode 的索引（不过太过简单）；

我们可以先试一试用一个 in-memory hash map 来将 key 与 KV 数据所在 log file 的偏移量关联起来：

这种方法被一些商用系统采用（例如 Bitcask in riakKV）；

优点：读写高性能；

局限性：INDEX 只在 RAM 中。而 RAM 大小有限，太多的插入操作（新建 key）会导致 INDEX 在内存中溢出；因此它仅仅在一些 workload 中适用：

适用场景：when workloads have many updates but not insertions；

因此，我们需要把 index 周期性搬到磁盘上。那么这个时候需要好好选择数据结构了，主要因为：

• 虽然有很多 hash 数据结构，但它们的性能在磁盘上的表现差异更为突出（这在内存上很难看出来）；

• 有些 hash 数据结构天生适用于在磁盘（例如利用了磁盘的存储特性），但有些 hash 数据结构从内存移到磁盘上放反而会降低它的效率；

总之，我们需要基于某类 hash 数据结构作出针对磁盘存储介质的优化。

我们看看哪些数据结构符合我们的要求：

• Linked-list based hash index：最简单的基于 hash table 的索引数据结构；

  • 优点：易于实现；

  • 缺点：hash collision 时，读写性能都有较大影响（尤其是并发时需要锁一个 bucket）；

• Cuckoo Hashing：高级数据结构中介绍的一种 Data Structure；

  • 优点：读性能很好，最多两次随机 I/O；

  • 缺点：插入比较耗时，可能需要多个 random disk I/O；并且插入较多时需要 rehashing（相当耗时，但不做的话可能死循环）；

我们发现选取这样满足条件的数据结构并不是一件简单的事，需要考虑很多问题，做些 trade-off：

• Read performance vs. update performance（而且在 update 时需要对 index 进行插入/删除）；

• 这种 index data structure 的访问模式是否对存储设备友好（随机读写/顺序读写）？

• 其他问题：如存储效率、存储开销问题；

Improvements III: Alleviate Write Amplification

事实上目前除了前面提到的问题，还有一个问题是，KVS 中的 Log file 会不断增长，总有一天会超过磁盘容量。

除了分出多个 log files 以外，我们还想到之前设计实现 API 的时候，写和删除会出现多个重复、没用的 entries，因此我们的思路是：

Compaction with segmentation + Merge：

• 将文件再分成多个 segmentation（方便 compaction 快速进行）；

• 一个 segmentation 满了后分裂新文件；

• 可以通过控制 segmentation 的大小来控制 compaction 的粒度；

• Compact 时，在 segmentations 中移除多余重复的 records（称为 GC，可以通过标记时间戳）；

• Compact 导致 segmentations 缩小后，可以通过 merge 把两个 segmentations 合并起来，适当减小 segmentations 数量；

Improvements IV: Large Range Query Supports

我们可以使用 B+ Tree（或者用 B Tree）来存放 Key & Log File，以起到 Range Query 的作用。

这种数据结构针对磁盘进行了优化：

• 每个结点是固定大小的，可以存放多个有序键；

• 所有叶子结点都位于树的底层；

• 支持高效的顺序扫描、对于大规模数据读写有优势；

所以我们需要用 B+ Tree 来索引日志吗？不需要！如果我们用的话，应该直接把日志内容放在叶结点上。因为如果叶结点还要索引的话又会引入 merge & compaction，平白无故地多出了一次 disk random access；

综上，B/B+ Tree 对于存储 KVS 方面：

• GET / INSERT / UPDATE 相对较慢（$O(\log n)$$O(\log n)$），而且每个结点大小较大，性能还慢；

• 对于插入频繁的 workload，需要很多的 random disk I/O 操作，开销比较大；

在综合考虑上面的几个问题后：

• 顺序写远快于随机写：使用 Log File Append-Only；

• 为了防止 Log File 过大：Log File 需要 Compaction with segmentation + Merge；

• 没有解决 Range Query、GET 效率不高的问题；

我们打算使用 SSTable（String Sorted Table）来索引 Log File 的方法来做 KV Store System：

• 使用固定大小的 segments 来存储键，每个 segment 间维护有序性，以及值位于 Log File 的位置信息；

• 一旦一个 segment 被填满，就新建一个文件；

这么做有一些好处：

• 二分查找，在一个 segment 中查找的效率相当高；

• 在 segment 中支持范围查找；

• 甚至合并两个 SSTable segment 都是高效的（相当于两个有序的数组 merge）；

我们还可以作出一些优化：

• 应对快速的读写请求，可以留存一个不超过最大阈值大小的 in-memory table（MemTable，可用红黑树/跳表等等）。

  先在内存中进行增删改查，直到 MemTable 满了后再作为一个 SSTable 的 segment 生成一个新文件。

  内存中的 fault tolerance、data consistency 可以通过 Write Ahead Log 来确保；

• SSTable segments 过多时，由于多个文件间需要扫描有序性，查找比较旧的值变慢、de-duplication 变慢、范围查找仍然不高效；

  所以我们可以将 SSTable 以树形结构组织起来；

最终还要考虑：

• Write Stall 的问题（多线程写？多个 MemTable 轮转使用？层级更高用更好的存储设备？），但都只能缓解；

• 对不存在数据查找很慢（一直找完所有 SSTable。引入 Bloom Filter？）；

1.7 Consistency Model

1.7.1 Intro

假设我们正在建构一个 Chat App，消息结构如下：

• 一个 Chat（CID 标识）中包含多个 Sentences（SID 标识）；

我们想部署一个 KV Store System 来存储消息，想了一种方法：将 KVS 放在中心化的服务器中；

不过这么做有问题：

• 不高效。每步动作都需要服务器确认；

• 一旦离线就无法得到消息；

那么改进一下：在中心化 KVS server 的基础上，每个端侧设备有一个 KVS 做数据备份；

这样就有一个 Naïve solution：

• 读数据：从本地 KVS 读最新的备份；

• 写数据：在更新本地 KVS 的同时同步其他的 KVS，最终 client 返回；

还是有两个问题：

• 写数据时同步不高效 ：每次写都要等，而设备间 RTT 通常 100-400 ms；

• 没法应对网络断连的问题（可靠性问题）：发送方可能会被阻塞；

Fix 为 Naïve solution++（这就是 WeChat 应用使用的）：

• 写数据：立即更新本地 KVS，然后直接返回，同时在后台向其他 KVS 发起同步请求；

但是这里存在一些 consistency issue（unexpected behavior）：

• 数据有丢失（但是已经返回，Missing an update）；

• 顺序有问题（Order Mismatch），不能保证两次同步的数据谁先到达；

所以在网络上，对 KVS 的操作请求可能没法及时同步其他设备看到的信息，从而导致数据不一致性。因此我们需要建立一套 Consistency Model。

1.7.2 Definitions

Consistency Model 描述了一个数据存储系统在并发 / 分布式 / 出现错误（failure）时的应对行为；

例如，in GFS, the consistency model is that all the chunk will eventually be the same（最终一致性）；

而一个 Strong Consistency Model：可以精确的保证哪些事会发生、哪些事不会发生，不会出现 unexpected behavior；

这是一个 Weak Consistency Model 所没法达到的。所以下面我们先考虑 Strong Consistency Model；

注意，没有正不正确的说法总是在：是否容易实现、效率高低、数据一致性之间做 trade-off；

一个 Consistency Model 的光谱如下：

我们本章关注的是可线性化、严格的 Consistency。

那么直观上什么是 Strong Consistency Model 呢？

• Everything has only one-copy；

• The concurrent read/write behavior is equivalent to some serial behavior；

• The overall behavior can be viewed as a system that never fails（后面讨论）；

而一个正确的 strong consistency model，需要对一连串的并发请求，deduce 出一个正确的 serial behavior，就像数据库的并发调度。

从这个 deduce/调度策略，我们可以区分出 3 种比较强的 consistency model：

Strict Consistency

Strict Consistency：需要根据 global issuing order（global wall clock time）来决定这个 serial behavior！

优点：

• 单次值操作所能达到的最强的一致性模型；

• 所有并发操作都等价于一个正确的单线程串行操作；

缺点：

• 在分布式系统环境中几乎不可能正确实现；

  出于性能和正确性的考虑：

  • 很难高效、100% 正确地维持一个所谓的 “global wall clock time”；

  • 而存在误差的 “global wall clock time” 会导致并发操作没法真正的等价为 100% 正确的串行操作；

  很可能落得花了很大力气，最终却做错的下场。

• 网络环境永远不可靠：即永远无法确定一条指令之前是否有 global issuing order 在此之前需要被执行的（究竟等多久？）；

如下图：

Sequential Consistency

Sequential Consistency：只有每个终端处理的一系列事务需要有序，Per-process issuing/completion order；

也就是说，只需要一个物理结点上的连续发生的事务间保持顺序就行。

优点：效率高；

主要缺点：Missing Update（Write Done but read old data）。像上面的例子，实际物理时间 GET(X) 在 PUT(X) 结束后，但是没法获得修改完成后的信息，因为分布式系统使用的是 sequential consistency，上述真实物理时间排布会最终同步成下面的线序。

Linearizability

Linearizability：除了保证每个终端处理的一系列事务需要有序，还要保证 Done-to-Issuing Order；

也就是说，所有的 done event 和 issuing event 的时间需要确保顺序。如下图：

蓝色标注说明，在使用 Linearizability Consistency 的分布式系统中，串行化时会考虑到 所有操作的 done time 和 issue time 在真实物理时钟下的先后关系，确保最终 Put(X, 1) 在 Get(Y) 操作之前完成。这种程度的同步会比 Sequential 的更严格，但比 strict consistency 轻松。

例如上面的例子我们就能发现，如果使用 Linearizability，那么 GET(X) 能获得 PUT(X) 的最新值，缓解了 Sequential Consistency 的 Missing Updates 的问题；

另外，可以反证法证明：

If each object’s op is linearizable, then overall system is linearizable.

综上，真实应用中总是倾向于 Linearizability；

1.7.3 Implementation of Linearizability

如何实现 Linearizability？

第一种方法：Primary-backup approach，即：对每个对象，Clients 都会向某个指定的结点发送读/写的请求；

对读：返回本地关于 primary（M0）数据的缓存；

对写，在保证先后写有序（in-order）的同时：

1. M0 向所有 replicas 发送写数据指令；

2. 完成后，M0 在本地执行写指令;

3. Respond OK;

如下图：

注：“in-order” 是指，两次写操作的顺序不会因为先后到达 node 而受到影响。

如何实现？有序性这个点不必要用 global wall time，使用 sequence number 给每个写操作计数就行（确保不会因为一些原因导致到达两个物理结点的写的信号不同）。

但有很严重的性能问题：

• 读请求：每个 client 都要承受联系 primary node 带来的额外 RTT（Real Time Transform）开销；

• 写请求：每个 client 都要承受联系 primary node，以及写多个 replica backups 造成的 RTT 开销；

• 可扩展性问题：随着 client 数量增大，primary node 就会成为性能瓶颈；

此外还有可靠性（可用性）问题：primary 具有脆弱性，一旦某块数据对应的 replicas 中，primary 挂了，系统应该如何应对？

我们先看 performance 问题。能不能读一个随机的 replica 中的数据（不总是读 primary machine），就像 GFS Read 一样？

不行，因为这存在一个 linearizable 的问题。如果尝试读一个不是 primary node 的结点，可能会读到系统的中间值，出现数据不一致性。例如下面的场景：

所以，为了防止 primary 成为性能瓶颈（fallback 到中心化 KVS 系统的性能），我们定义了 partition：

将所有数据对象存储在 KVS 时分为不同的 partition，不同的 partition 可以有不同的 primary，这样可以分散掉读写的请求；

Different objects have different primaries ，如下图：

现在落到实处思考一下：

这种 Primary-backup model 实现 Linearizability 的方式对于一般 Mobile Chat Application 来说，显然是不合适的：

• （性能缺陷）发送一个消息，就要等待所有设备都同步？

• （在保证性能的情况下很难保证 fault tolerance）如果某个设备的状态是离线的，难道服务就不可用了吗？

所以，对于分布式 Chat Application 而言，数据不一致性时时刻刻都可能存在，只不过是一致性的要求、同步的方式随着业务逻辑调整，更加灵活。因此我们需要了解一种对一致性要求更宽松的一致性模型，它在上面这种 Mobile Chat App 的情况下更为适用。

1.8 Eventual Consistency

最终一致性模型是一个相当宽松的数据一致性模型之一，其地位如下图所示：

1.8.1 Definitions

这种应用场景下，我们更关心性能、fault tolerance，而不是 consistency。这是一种 weak consistency model，只要：

• 所有服务器最终会（不保证实时性）接收到并同步所有写操作，对某组数据的内容是一致的；

  即：当一个数据不再更新后，最终所有对这个数据的请求都只返回上一次更新的值；

这样我们可以如此定义实现最终一致性：

• Read（和 Linearizability 的实现方法不一样！这样的结果可能不是 linearizable 的）: return the latest local copies of the data；

• Write：在本地写，然后直接返回在后台逐步传播这个更新的数据（不要求后台一定请求同步更新，所以是 propagate）；

但是，对于 “如何实现最终一致性” 的相同问题，在不同的实际场景下的回答（解决方案）是不一样的。

• 对 GFS（data center）：传播数据的方法是，选出 primary 来写所有份的数据（回想：data flow + control flow）。这不适合像 mobile app 的场景；

• 对 mobile chat app：传播数据的方法是，直接向离 client 最近的 server 写数据：

  • 在这个 server 确认后，就没有 client 的责任了，这个 server 可以之后将这个 update 传播到其他的 server 中；

  • 这个 “最近的 server” 可以和 client 位于同一个物理节点上（co-locate）；

考虑这种对 mobile chat app 的方案是否有问题？

是的，会出现 write-write conflict: 也就是说不同的 client 可能同时（concurrently）向最近的 server replica 更新同一个数据，而相互不知晓。

这样在数据传播后，最终会导致 data diverges，也就是出现同一时刻的两个数据版本（在一个 server 上先 X 再 Y，而另一个 server 上相反），永远没法达成最终一致性，如下图：

回想我们在 Linearizability 中的解决方案，它采取 “pessimistic conflict handling”（类似悲观锁），认为冲突是常见的，除非交给 primary node 的请求是 serialized，否则不应该生效（也就是说，先到 primary 的请求先生效）。

而在 eventual consistency 中采取 “optimistic conflict handling”（类似乐观锁），认为写冲突不常见（所以不设置 primary，每个结点自己都可以写），但希望修改最终会 propagate 到所有的设备中。

也就是说，选择 linearizability 和 eventual consistency，实质上是在 consistency 和 performance 间做 trade-off：

• 是否允许在确定能够串行化前就写一个值（以后在传播的过程中确定操作顺序）；

• 是否接受在更新后可能读到一个旧值，并且没有绝对的全局顺序；

  这个 “没有顺序” 是有要求的，也就是不能丢失因果性，参见下文。

  所以，在不丢失因果性的前提下，最终一致性不会保证绝对的全局操作顺序，也就是微信上常常见到的两人同时发消息顺序可能双方看起来不一样。

但是说到底，eventual consistency 还是需要 cope with anomalies：

• Write-write conflict：最终一致性模型需要 converging state（例如在上面的例子中，合并不同结点间的不同状态）；

• Loss of causality：最终一致性模型需要 causality preserving（保持因果一致，同一个前后依赖的事务间的顺序需要保持）；

1.8.2 Converging State: Update ID & Write Ahead Log

先看如何合并不同结点间的不同状态（解决 write-write conflict）。我们可以像 git 处理冲突一样，只有必要才解决冲突，否则 auto-merge。也就是在传播途中：

• 在一次本地写操作后，适时（例如放入任务队列）在后台向其他 server 发送写请求；

• 每个收到传播请求的 server 需要在更新本地数据的同时，尽可能解决冲突；

例如，对于两个 client 向两个 KVS 中同时用 PUT 的方法更新一个数据记录 chat[cid] = [...chat[cid], new_sid]；

这样如果不加处理，可能会出现数据丢失（因为 PUT API 的语义，最终只有一方的修改存在）；

于是解决方案是引入 “Append Update” 的语义：chat[cid].append(sid)，这样保证数据不会丢失。

丢失问题解决了，那么合并顺序呢？我们需要两个 KVS 所在的 server 对全局的顺序达成一致共识。如果一开始都更改 KVS，那么最后肯定分不清了（没有排序依据了）。

所以我们应该使用 Write Ahead Log，为操作打上时间戳（先不考虑两个 server 的 timestamp 不一致的问题）。如果不巧时间戳也相同呢？那么可以使用 server node ID 来决定，也就是 update ID 组：<time T, node ID>，这样一定能区分两个操作的先后（因为 timestamp 在 server 上不同的问题，不保证绝对全局顺序）。

注：肯定不能反过来 <node ID, time T>（先判断 Node ID 再判断时间），这样 “某些 node 的更新操作总是在另一些 node 之前” 的现象会很明显。

但是，还有一个问题，为了尽可能确保状态成功合并，应该先 merge（achieve state convergence），再将写的数据 update 到 KVS（如果先 update 的话，不同的 server 原始数据就不同了，更没法合并了）。但是如果先等 merge 完成再 update，会导致更新延迟，用户无法在提交后立即看见，这是在 mobile app 中不可容忍的。

我们再想一种解决方案，是否可以先 update，再处理 merge？

答案是，可以。我们从单机中的数据库事务处理策略中获取灵感，可以采用回滚（rollback/undo）和重做（replay/redo）来管理不恰当的 update，让状态在后续过程中合并、再次修正并达到一致：

• 当本地写操作发生时，立即 update 到 local KVS 中；

• 当接收到其他 server 的传播请求时，如果发现没有冲突，KVS 直接写；如果发生冲突（例如收到的 timestamp 小于当前本地最新的 timestamp），KVS 就通过 WAL resolve 出最终的合并的顺序，然后 rollback 到 empty state（指 sync 前的某次一致的状态），并且根据最终的 update 顺序 replay 一次，得到正确的数据；

  如果直接 rollback 到 empty state，会出现两个问题：

  1. sync 时间可能很长，影响性能；

  2. 日志文件可能很大，影响存储效率；

  我们在本章最后讨论。

1.8.3 Causality Preserving: Lamport Clock & Vector Clock

好。现在假设我们通过上面的方法解决了 write-write conflict 的问题，那么 loss of causality 呢？

我们回想之前的做法，我们使用 <time T, node ID> 作为操作时间戳，但是两个 server 的 timestamp 是不同步的。

就像我们之前说的，这的确不影响 write-write conflict 的解决（sort & converging state），但是它会影响用户体验的因果性（loss of causality），例如：

假设在全局时钟（global wall time，应用并不知道）下，client 对 SRV-1 写了 X（其中 SRV-1 产生的时间戳为 10），而在此后的很短一段时间内，SRV-1 和 SRV-2 间传播了一次数据（sync），SRV2 没有冲突立即写入 KVS 并在 WAL 中记录；

但是在这之后又是很短的一段时间内，iPhone 向 SRV-2 删除了 X，这个时候由于 SRV-2 和 SRV-1 时间戳不同步，SRV-2 此时才生成时间戳 9，并写入 KVS；如果这个时候，SRV-2 又向 SRV-1 传播一次数据（sync），那么 SRV-1 看见时间戳 9，会以为 Delete 事件发生在写入 X 前，在 resolve conflict & replay 时会导致 delete 在 add 前操作，X 实际并没有在 SRV-1 上删除，因此 SRV-1 和 SRV-2 数据又一次不同步了。

这就说明没有 preserve causality（没有保证前后依赖的事务的因果顺序）。为了解决这个问题，我们就需要指定好事件间的因果。

或者说，我们需要 clock 真实地反映因果（Clock should reflect the causal order）。但是不同机器时钟是不同步的！怎么办？那么就不用不准确的绝对时钟了。

人们想出了 “逻辑时钟”（相当于事件驱动时钟），这就是著名的 Lamport clock；思路如下：

• 每个 server 维护一个时钟值 T；

• 当 server 时钟嘀嗒一下，T 进行自增；

• 当 server 感知到其他 server 传播信息中的时间戳 T' 后，再次更新 T = max(T, T' + 1)

  这保证了已发生的事件 T' 标记始终小于接下来要发生的事件 T 标记；

注意比较 tricky 的一点：同步后的两个有因果事件的 Lamport clock 值才有明显可比性。因为它展示的是 global order，例如：

• 当 $E_1$$E_1$ 事件在机器上发生后，同步到另一台机器发生 $E_2$$E_2$，那这个时候保证 $T_L(E_1)<T_L(E_2)$$T_L(E_1)\lt T_L(E_2)$；

但是从 $T_L(E_1)<T_L(E_2)$$T_L(E_1)\lt T_L(E_2)$ 没法推出下列的情况：

• $E_1,E_2$$E_1,E_2$ 是否经过一次数据传播（各机器 timestamp 并不准确和同步）；

• $E_1,E_2$$E_1,E_2$ 的 global wall time 的关系；

• $E_1$$E_1$ 事件导致机器向 $E_2$$E_2$ 所在机器 sync 时，$E_1$$E_1$ 仍然不一定在 $E_2$$E_2$ 的 global wall time 前发生。因为并没有阐述 $E_1,E_2$$E_1,E_2$ 的因果关系；

现在，我们使用 <Logical Time, Node ID> 作为 Update ID，就既能解决 write-write conflict 的顺序问题，又能解决 loss of causality 的问题了！

但是很不幸，这样还有一个问题：这种测定方法过强了（对于已经沟通的两个 servers 来说，事件关系要么前要么后）。如果我需要做两件不相干的事，它们实际上可以（或者需要）在同一时间进行，也就是需要 incomparable timestamps！

在离散数学上说，就是我们不一定需要强的线序关系，而是需要偏序关系（partial order）！

这个时候，人们基于 Lamport clock，设计出了 vector clock。思路如下：

我们根据不相干事务数量 $n$$n$，设定 $n$$n$ 个 Lamport clock $[c_1,c_2,\dots ,c_n]$$[c_1,c_2,\ldots,c_n]$，每个 Lamport clock $c_i$$c_i$ 的管理方法同上。

这样我们就可以比较多种不相干事务间的先后关系，在某些应用场景中比较有效。

总而言之，大部分场景下 sort & converging state + Lamport clock 已经能实现 eventual consistency 并解决大部分问题了，少部分场景下还要借助 vector clock；

1.8.4 Truncate WAL

最终还有一个问题：我们在 sort & converging state 中在本地写了 Write Ahead Log（WAL）。它不仅可以决定 merge order，还可以让我们在发生 write-write conflict 时进行 sync replay，但这并不高效。因此我们需要从两个方面下手：

1. 尽量不要全部回到 empty state 并重做所有的 update（只做部分 replay）；

2. 减小 Log 文件大小；

先来看如何只做一部分的 update。

我们把那些不确定后面会不会有数据传播造成顺序重写（例如分布式网络中存在正在传播中的、在此之前的更改操作）的数据写操作称为 “tentative writes”（unstable writes），这些写操作可能在后续的传播同步的过程中出现 write-write conflict 需要 replay；

确定不会有其他传播对这个数据造成影响的写称为 “stable writes”；

于是整个 WAL 中由上下两部分构成：stable writes 和 tentative writes。借鉴了单机数据库的事务日志（redo/undo log），这里也相当于有个 checkpoint 的概念，不过是用 stable 和 tentative 来区分的。

在发现 write-write conflict 需要 replay 时，server 可以按照 WAL 回滚到 tentative 记录之前，不需要回滚 stable writes 的部分，初步提升了回滚效率。

那么我们如何判断一个写操作是 stable 的还是 tentative 的呢？

方法 1（de-centralized approach）是利用 Lamport clock：

• 一个 UPDATE 操作是 stable write 当且仅当 目前没有任何一个 entry 的 Lamport clock 值比它更小；

举一个例子：对 UPDATE <10, A> 操作，如果分布式系统中所有的 nodes 都发现了不少于 10 的 UPDATE 操作，那么这个操作就是 stable write；

但是显而易见，这种方法有个缺陷，就是分布式集群中有任意一个 node 掉线了，那么就无法继续判断 stable write 了，仍然会有很多 tentative writes 需要在 conflicts 时回滚。

方法 2（centralized approach）是借助 primary node：

设定一个 server 作为 primary，它不作为专门写数据的结点，而是专门生产一个特殊信息的结点：

• 当最后一个针对某个数据的写操作向 primary 请求后，primary 会生成一个标记 CSN（Commit-Seq-No，已提交流水号），并将修改后的信息 <CSN, LocalTS, SrvID> 广播（broadcast）出去，可以理解为终结了一组有 causality 关联的 writes（相当于分布式事务的 commit）；

• 所有收到 CSN 的 server 在此之前的所有 write 都会被视为 stable writes；

• CSN 本身可以在各个 server 间传递，但只由 primary 产生；

这样，只要 primary node 是存活的，分布式系统就能一直判断 stable writes；

还有一个问题，向 primary 申请 CSN 的 server 可能 Local Timestamp 并不是当前最小的（$M_1$$M_1$ 机器事件 $E_1$$E_1$ 触发 $M_2$$M_2$ 的 $E_2$$E_2$ 事件，这样 $T_L(E_1)<T_L(E_2)$$T_L(E_1)\lt T_L(E_2)$，但如果 $M_2$$M_2$ 先向 primary 申请 CSN），应该怎么办？

这比较简单：我们可以让一个机器向 primary 申请 CSN 时，带着前面所有依赖的（因事件）一起申请 CSN，这样一定能保证 CSN 也能反映 Causality；

考虑这个问题：两个没有因果关系的事件在传递时，由于没有互相通信，因此 $T_L$$T_L$ 的大小关系是不一定的；这个时候如果 $T_L$$T_L$ 大的（不一定是 global wall time 靠后的）先向 primary 申请 CSN，primary 同步到剩余结点时就会出现顺序调换的现象：

不过因为没有改变 causality（主要是 Srv1 和 Srv2 无关），并且发生的次数不多，不影响总体用户体验，因此也是满足 eventual consistency 的。

1.8.5 Conclusion

总而言之，Eventual Consistency 的 Anomalies 到底是否重要（发生的频率和相关的后果），取决于应用的场景。

对于一个 Mobile Chat App 而言，可能 Eventual Consistency 就足够了，但对于银行系统甚至 Linearizability 可能都不足够。

1.9 Consistency Under Single-Machine Faults: All-or-Nothing

回忆 strong consistency model 的定义：

• 每个数据对象都只有一份；

• 并发读写行为和串行的行为是一致的；

• 系统整体的行为相当于这个系统从来没有 fails（系统的 fails 对用户无感）；

我们前面几节想要尽量通过保证第二条来实现较强的一致性。现在我们考虑第三条，如果系统出现 fails，分布式系统应该如何处理才不至于直接崩溃？

1.9.1 Shadow Copy for Atomicity

首先，我们要确保某一类操作要么不做，要么全部做完（all-or-nothing atomicity），例如对文件 / 数据库的写操作。

注：在数据库领域，all-or-nothing 就被称为 atomicity（原子性）；

我们在学习单机数据库事务执行时讨论过这个原子性，那么在分布式系统中，如何实现 all-or-nothing 呢？

同样，仿照之前的做法，我们首先想到 shadow copy：

先把要修改的文件 / 数据库 copy 一份，操作时直接在上面修改；等到修改完成 + fsync 后，再将 copy rename 到使用的文件 / 数据库上。这样无论在操作的哪个步骤故障，总不会出现事情做到一半的情况（最多出现多出一个有问题的 shadow copy，这个在下次恢复时清除即可）。

在单机数据库的事务保证时，shadow copy 就是一种 No-STEAL/FORCE 性质的算法。

但是这种方法执行效率低，没法支持事务的大规模并发。为什么？我们后面讨论。

好，shadow copy 把 atomicity 的问题交给了 file system；

我们分析 file system 的 RENAME 究竟有几步、出错的可能性。rename(temp, final)最简单的情况是，rename 的两个文件在同一目录下：

1. directory data block 中，final inode number 改为 temp 的 inode number；

2. final inode 中的 refcnt 减 1；

3. temp inode 中的 refcnt 加 1；

4. 在 directory data block 中移除 temp 的 inode number 和名称映射；

5. 原先 temp、现在 final 的 inode 的 refcnt 减 1；

如何保证上述步骤执行的没问题？我们在 OS file system 中先想到的是 “journal”（相当于逻辑日志）；

但是问题是所有操作都要重复到磁盘上写两次（尤其是文件比较大的时候，这种方法不可取）。如果解决这个问题？

首先观察：

• 不是文件系统上的所有东西都一样重要；

• 通常情况下，文件的 metadata 更为重要（例如 inode 结点所在的 blocks 需要关注）；

因此作出缓解问题的方案：在 journaling 中只保护重要的 metadata。这样真正的数据只会被写一次；

但如果 data 也很重要呢？具体的 workout：

• EXT4 文件系统提供了几种 journal 的选项：data=journal/ordered/writeback；

• 操作这些数据的应用程序也需要自己关注这个问题，例如等待 fsync 同步刷盘后再继续处理接下来的任务；

那么写 journal 本身的时候挂了呢？

• 硬盘厂商本身会提供一定的能源供应最后一个 sector 完整写完；

  • 例如内置的小电容可以维持几毫秒的 disk 能量供应；

  • 这建立在 “写一个 sector花费的时间很短” 的假设上。

• 当然，如果写还没开始，那就更不用担心了，因为 nothing 也是符合 all-or-nothing 的策略的。

好，那如果仅仅 journal 的大小仍然超过一个 sector 大小呢？那么我们就需要更 generalized 的方案了（我们后面讨论）。

上面讨论，如果使用 shadow copy 会导致并发性问题。如果两个 client 同时对一个资源进行修改，这个时候 shadow copy 需要确保第二个 client 不要基于原来的数据直接创建新的文件（因为可能出现覆盖的问题）。但是如果共享一个新文件，那么其中一个 client 写完后 fsync 可能会把另一个的 intermediate 脏数据刷盘，在断点时会造成数据不一致。

因此还要保证只要有一个 client 在写，就暂时不要写回，以免出现数据不一致的现象。

所以我们需要：

• 同一时间只能进行一个操作；因为正常地执行并发操作会出现一致性问题，哪怕这些操作原理上可以一起执行；

• 很难同时合并处理多个文件、目录，特别是多个 client 需要进行多个 subdirs 的重命名操作；

• 哪怕发生了很小的更改也需要 shadow copy 整个文件；

这在客观上就限制了 shadow copy 操作的并发性。

如何改进 shadow copy？我们借鉴单机数据库的事务处理方案：Logging；

1.9.2 Logging for Atomicity

我们引入 undo log 和 redo log、checkpoints 来实现单机上的 all-or-nothing atomicity；

STEAL + NO-FORCE：基于 redo/undo log 的恢复算法；

• 在故障恢复时，需要：

  1. 反向扫描 undo log、正向扫描 redo log，出现没有闭合的 <T start> 则判定为未完成事务、反之是已完成事务；

  2. 重做阶段：在正向扫描 redo log 后按序将已完成（标注重做）的部分再次执行（重放历史）、未完成部分插入 <T abort>；

  3. 撤销阶段：在反向扫描 undo log 后将未完成（标注回滚）的部分撤销执行，并插入 <T abort>。

• 补偿日志机制：为了防止在恢复过程中再次崩溃而不知晓恢复的进度，人们设立 “补偿日志”，每次执行 undo 日志记录后，数据库需要向日志中写入一条补偿日志记录（compensation log record，CLR），记录撤销的动作，也就是实现了 undo 日志的 redo，记录已经 undo 的日志，保证 undo 不被重复执行；

• 检查点机制：数据库的日志会随着事务的执行不断变长，这会使恢复时间也相应地变长，需要压缩日志大小来降低恢复的时间。人们因此设计了一种检查点(checkpoint)机制，检查点定义了一个脏页刷盘的时刻，要求检查点之前的日志记录对应的缓冲区数据页面修改已经刷新到磁盘。这样：

  • 在检查点之前完成（commit/abort）的事务不需要处理；

  • 在检查点之后 commit/abort 的事务需要重做；

  • 所有未完成的事务（不含commit/abort）需要回滚；

这同时也回答了之前 file system 中 journal sector 大小不足的问题。这个 generalized 的方案就是用专门的 logging file 来存储多出来的数据。

注意，在 OS 中，我们将 undo-log 和 redo-log 结合起来，一个 entry 包含：

• Transaction ID；

• Operation ID；

• Pointer to previous record in this transaction；

  之所以需要当前 transaction 的前一个记录的指针，是因为在 OS 中存在调度问题，可能在一个 transaction 中途调度到其他线程，因此需要连接前一记录的指针。

• Value (file name, offset, old & new value)；

• …

然后恢复过程也有变化：

• 从后向前扫描，标记所有不闭合的事务（没有 COMMIT/ABORT），并且：

• 同时 undo 所有 Checkpoint 后 ABORT 的完整事务，以及不闭合的事务；

• 然后从前到后 redo 所有 Checkpoint 后 COMMIT 的事务（如果有部分在 Checkpoint 前，则该部分可以不做）；

为什么 redo 在 undo 之后？因为 undo 可能会擦除 redo 的修改，即一个未提交的事务把另一个提交的事务回滚了。

为什么 undo 要从 end to start？因为后续的事务可能会依赖于前序的事务；

checkpoints 标记的方法：

• native：直接 run 一遍 recovery process（非常慢）；

观察：

• 对 redo log，事务的脏数据都在 page cache 上，因此我们需要 flush page cache 到磁盘上才能清空当前 redo log；

• 对 undo log，但是我们需要等待所有 transactions 全部结束，才能清空当前 undo log；

所以优化后的方法（basic approach）：

1. 等待所有事务全部完成；

2. 刷新 page cache；

3. 丢弃所有的 redo & undo log；

但这种方案是有问题的：如果一个事务进行的时间很长，怎么办？因为有些应用场景下一个事务可能需要执行 1~2 hours。

我们能接受在有正在执行事务的情况下，进行 checkpoint 标记吗？

现在改进一下 basic approach：

定义一个 action（粒度细于 transaction，例如转账事务中一个 action 就是 deposit），然后：

1. 等待所有的 action 全部完成；

2. 向 log 中写入 CKPT（checkpoint）记录；

   • Contains a list of all transaction in process and their logs；

3. flush page cache；

4. 丢弃所有除了 checkpoint 记录的其他记录；

这样含有 checkpoints 的恢复情况如下：

注意：

• 每个 action 都会让日志落盘；

• 在 Checkpoint 前，无论是否是脏页，肯定刷盘；

• 在 Checkpoint 后、Crash 前的 action，因为是 STEAL 策略，因此可能已经刷盘（state modification），需要 undo 这部分以防万一。就像数据库的 STEAL + FORCE/NO-FORCE 策略；

1.9.3 Conclusion

对比 redo(only)-logging 和 redo-undo logging，redo-only 的优势：

• 相比 undo-redo logging，前者有更少的磁盘操作；

• 仅需要从前到后扫描一次日志文件；

实际：除了那些在内存中状态很大的事务，Redo-Only Logging 都是首选（NO-STEAL + NO-FORCE）；

我们发现，高并发数据库其实会存在很多 “内存中状态很大” 的事务，它如果使用 redo-only logging，那么内存缓冲区小的弊端就会显现，因此像 MySQL 数据库就用 redo-undo logging。

而操作系统和其他需要保证 all-or-nothing atomicity 的应用只需要 redo-only logging 就足够了。

为什么很少用 undo(only)-logging（STEAL + FORCE）？

因为它既需要 STEAL（提交前的各个时刻都可落盘），又需要 FORCE（提交前一定需要落盘），因此 disk I/O 更大，比其他所有情况的时延更大（即便 undo-logging 可能恢复更快一点）；

1.10 Consistency for Isolation: Before-or-after Atomicity

1.10.1 Definitions & 2PL

我们再讨论另一种情况。现在我们实现了 all-or-nothing atomicity，也有 linearizability 保证数据一致性，那么一定就没问题了吗？

非也，因为还会存在并发访问共享数据的问题。

分布式系统下，如果出现多线程共享数据时，可能出现 race condition。这也许可以用一致性模型解决？

我们回顾一下前面讨论的好实现的 Linearizability 一致性模型。这样行吗？不一定行，因为：

正常情况下，Linearizability 这么做是没问题的，但是如果 $X,Y$$X,Y$ 需要是原子变化的呢（一个对象的不同属性，共享资源）？我们不希望其他 clients 读到中间状态，这就不能避免 race condition 了。

所以现在我们还需要再引入一种 consistency model，这种 model 可以有效避免多线程程序下出现共享资源的 race condition 的问题，也就是实现了 before-or-after atomicity（在数据库领域被称为 Isolation，在 OS 领域还被称为 Serializability Model）。

我们详细定义一下 before-or-after atomicity：

Concurrent transactions have the before-or-after property if their effect from the point of view of their invokers is as if the transactions occurred either completely before or completely after one another；

用数据库领域的话说，就是并发执行的两个事务能够等价于事务的串行执行（可串行化）。

回忆一下，在数据库领域我们如何实现事务的 isolation？

我们采用的方法不就是 调度策略 + 锁吗？这里也是！

如果是分布式数据库事务呢？Two-Phase Commit，这里也是！

和数据库处理事务的 isolation 一样，我们要实现 before-or-after atomicity 就可以用锁来完成。解决办法：

• Coarse-Grained Lock（Global Lock）：每个 action 修改共享资源前后加一把大锁；

  缺陷：粒度太粗，同时只会有一个 action 执行，甚至不考虑读写的区别，严重影响并发性能；

• Fine-Grained Lock：每个共享资源有一个锁，一个 action 必须获得一个资源的锁才能访问它；

  能否避免所有的 race condition？显然不能。

  从数据库角度来看，只是加了互斥写锁，避免了基本的并发冲突，就是可能出现脏读（隔离级别 read uncommitted 不够）；

  同时为了避免全局脏读（例如全局 audit 程序可能查询正在转账的 A、B 时脏读），我们引入了新的 fine-grained lock 管理方式：Two-Phase Lock（和 Two-Phase Commit 无关）；

  它指的是，一个获取共享资源的 action 必要时拿锁，然后必须在 action 结束时释放。

  也就是说，第一个阶段只拿锁，第二个阶段只放锁。

  这里和 Global Lock 相比，虽然都有全部上锁的情况，但是毕竟这里的粒度小一点，阻塞时长短一点。

对比一下 Global Lock 和 Fine-Grained Lock：

• Fine-Grained Lock 需要的锁更多（尤其是涉及数据记录多的时候），内存资源占用率更大；

  Fine-Grained Lock 也可 on-demand 调整锁的数量，只需要确保访问同一个数据记录时用同一把锁就行。

• 但 Global Lock 的并发性能更差一点（同一时刻只允许一个 action 访问）；

Serializability Model 中有几类并发顺序，恰好和数据库领域的 “调度” 的概念对应：

• Final-state serializability（数据库中的 “终态可串行化调度”）；

• Conflict serializability（数据库中的 “冲突可串行化调度”）；

• View serializability（数据库中的 “视图可串行化调度”）；

我们定义：交换事务相邻两操作（action）的顺序，如果不改变最终结果相同，则称这是一次等价交换（两个调度是等价的）。并且，如果调度 $S$$S$ 仅通过等价交换，就能变成串行调度，则称 $S$$S$ 是冲突可串行化调度。

也就是存在一个这样的调度就行！

根据交换等价以及 冲突可串行化调度的定义，我们直接有结论（通过等价类理解）：若冲突可串行化调度 $S$$S$ 中调度的分别属于两事务 $T_i,T_j$$T_i,T_j$ 的某两个操作 $O_m,O_n$$O_m,O_n$ 间存在冲突（不可等价交换），则在 $S$$S$ 等价的串行调度 $S^{\prime }$$S'$ 中，$T_i,T_j$$T_i,T_j$ 中的 $O_m,O_n$$O_m,O_n$ 一定和 $S^{\prime }$$S'$ 的 $T_i,T_j$$T_i,T_j$ 中的 $O_m,O_n$$O_m,O_n$ 的顺序相同（保序性）。

因为这个保序性，我们可以借助拓扑排序描述等价类间互不可等价交换的关系，称 “优先级图”。若调度 $S_i$$S_i$ 与调度 $S_j$$S_j$ 是进行一次不等价交换后的两类调度，且 $S_i$$S_i$ 与 $S_j$$S_j$ 中事务 $T_i,T_j$$T_i,T_j$ 交换顺序的冲突操作对 $O_m\in T_i,O_n\in T_j$$O_m\in T_i,O_n\in T_j$ 中，实际执行顺序 $O_m$$O_m$ 在 $O_n$$O_n$ 之前，则构建一条 $(T_i,T_j)$$(T_i,T_j)$ 的有向边。最终会在两事务所有操作顺序的等价类间形成一张图，称 “Conflict Graph”；

我们再定义：一个调度是视图可串行化的，当且仅当最终写状态，以及中间的读状态和对应的串行调度是相同的。

也就是说，终态可串行化只关心事务调度的最终状态与串行调度一致（也是我们的目标），视图串行化除了关注最终状态，还关注中间读的状态；冲突可串行化不仅关注最终状态，还关注了数据依赖。因此严格性依次上升，但判断难度逐级下降。

如何证明 2PL 协议是 Conflict Serializability 的？我们假设一个前提，所有共享资源冲突都可以用锁来管理。

反证：假设不是这样的，因此 Conflict Graph $G$$G$ 中存在一个环 $T_1\to T_2\to \cdots \to T_k\to T_1$$T_1\rightarrow T_2\rightarrow\cdots\rightarrow T_k\rightarrow T_1$；

设 $T_i\to T_{i+1}$$T_i\rightarrow T_{i+1}$ 代表的冲突操作为 $x_i$$x_i$，因此：

xxxxxxxxxx
T1 and T2 conflict on x1
T2 and T3 conflict on x2
...
Tk and T1 conflict on x_k

紧接着：

xxxxxxxxxx
T1 acquires x1.lock
T1 releases x1.lock
T2 acquires x1.lock and x2.lock
...
Tk acquires x_{k-1}.lock and x_k.lock
T1 acquires x_k.lock

发现前两步骤违背了 2PL 的定义，因此假设不成立。

1.10.2 Case: Salary System

那么如果没有 “所有共享资源冲突都可以用锁来管理” 的前提，2PL 还能保证 conflict serializability 吗？

我们假设在一个工资数据库中，每一个雇员的记录都有一把 Fine-Grained Lock。

如果 $T_1$$T_1$ 是全表扫描并更新工资；$T_2$$T_2$ 是插入新雇员，那么会发现问题：

如果 $T_2$$T_2$ 在 $T_1$$T_1$ 间执行，突然发现多出了一些记录。这就是 幻读（Phantom Read）。核心原因就是全表扫描和记录的增删间没法用锁来管理（仅仅锁住 action 访问的记录是不行的），这种冲突没法用 2PL 来控制。

解决方案有：

• 谓词锁：通过标记相关联的数据记录，对这些记录任意之一上锁就是将它们全部上锁。粒度在 Coarse/Fine Grained Lock 间；

• 在 B/B+ 树索引结点上范围锁；

但一般不会处理它，因为代价很高。

1.10.3 Deadlock

对于 2PL （悲观的）锁，极有可能因为拿锁顺序的问题而持续地相互等待。

解决方案是：

• 尝试避免 deadlock：每个以 pre-defined 的顺序来拿锁。

  • 问题是这与具体业务逻辑（read-write pattern）有关，不支持通用的事务；

• 尝试检测 deadlock：固定周期检测 conflict graph；

  • 如果有环就可能死锁，于是 abort 一个事务来破除冲突环；

  • 问题是代价很大。在大规模分布式系统中难以实现；

• 启发式缓解方案：例如超时重试、pre-abort；

  • 可能的问题是 false positive、live locks；

因此我们需要反思，悲观的 2PL 协议可能引发死锁，而且不得不付出代价解决。

那么我们能不能使用乐观的方式来实现 Before-and-after Atomicity？

1.10.4 OCC: Optimistic Concurrent Control

乐观的并发控制机制主要有 3 个流程：

1. Concurrent local processing：读、写都在本地 buffer 进行并记录在 read/write set 中；

2. Validation serializability in critical section：

   检测 serializability 是否能保证（也就是 read set 中是否被修改过）；

3. Commit the results in critical section or abort：

   • 如果 validation 失败了，abort 这个事务；

   • 如果 validation 成功了，刷入 write set 指定的 buffer 并提交事务；

也就是说：

当事务开始时：tx.begin()，初始化 read set 和 write set；

• 此后事务内对特定资源第一次读操作，读并更新 read set（read set 需要缓存这个数据值。此步需要 atomic）；

• 写操作写入本地 buffer 并更新 write set，并且检查当前事务的 read set 是否有这个数据，有则更新 read set 缓存的数据；

• 对特定资源的第二次及以后的读操作，需要看 read set 中是否有缓存，有直接返回，无则说明是 “第一次读操作”；

当事务提交时：tx.commit()，同时包含 phase 2 和 3；

• 如果 read set 中的内容被其他事务更改，则 abort；

• 否则对每个 write set 内容刷回数据库；

注意 phase 2 和 3 需要在 critical section 中（事务互斥），有两个原因：

1. 因为可能出现 ABA problem：

   如果 $T_1$$T_1$ 中 $A=A_0$$A=A_0$，然后 $T_2$$T_2$ 更改 $A=B$$A=B$，$T_3$$T_3$ 又改回来 $A=A_0$$A=A_0$，这个时候 $T_1$$T_1$ 只检查 $A$$A$ 可能无法发现修改。

   解决方案是在数据基础上加上版本号（64 bytes）。我们在 read set / write set 中就可以用这种方法。

2. 并发事务同时执行 phase 2 时，都对 $A$$A$ 写，但都只看了 read set 发现没改，同时提交会导致其中一个写被覆盖；

那么如何实现 phase 2 和 3 的 critical section？

• 使用 global lock（和 2PL global lock 不一样，这个大锁只存在 phase 2 和 3 中，不会对性能有很严重影响）；

  但客观上还是降低了并发性能；

• 使用 2PL 协议，对 read set、write set 排序上锁（尝试避免死锁）；

  能否不对 read set 上锁，只是检查 read set 是否被更改？

  不行，因为只能说明 read set 目前没被改，不能说明没有上锁。如果有同步 commit 的两个事务，也会有问题：

  

  因此如果不锁 read set，就还需要检查 read set 中的数据是否被上锁。如果被上锁也 abort。伪代码：

  xxxxxxxxxx
  def validate_and_commit() // phase 2 & 3 with before-or-after
      for d in sorted(write-set):
          d.lock()
      for d in read-set:
          if d has changed or d has been locked:
             abort()
      for d in write-set:
          write(d)
      // release the locks
      ...
  

   

OCC 的优势：

OCC (in the optimal case, i.e., no abort):

• 1 read to read the data value;

• 1 read to validate whether the value has been changed or not (as well as locked)

2PL:

• 1 operation to acquire the lock (typically an atomic CAS);

• 1 read to read the data value;

• 1 write to release the lock;

  • A single CPU write is atomic, no need to do the atomic CAS;

综上：Locking is costly especially compared to reads！

OCC 的劣势：显然，在 serializable 情况下，即便没有出现 conflict cycle 也可能判断需要 aborts，如下：

注：这种情况下可以串行化为 $T_1$$T_1$ 先执行，$T_2$$T_2$ 后执行；

这种情况就是 False Aborts；尤其是在很多读的情况下（read set 很大）；

更严重的情况时，当大量事务并发时，两个 aborts 的事务在重试时又再次 aborts，结果可能造成 live locks！

这样 2PL 和 OCC 在不同并发数量情况下的吞吐量关系如下：

1.10.5 Lock Preliminary：锁如何实现

底层主要借助硬件实现。只是软件上的话不是很充分。互斥锁的硬件原语如下：

• Compare-and-swap (on SPARC);

• Compare-and-exchange (on x86);

最终编译器遇到上述指令后使用 Lock Prefix 确保在内存地址中原子执行；

Lock prefix to ensure an instruction is atomically executed on a memory address;

也就是提供了 CAS 的语义，软件可以在 CAS 的基础上实现对应的原子语义。

但是这 CAS 会极大地影响性能（比 L1 cache 慢 10 倍以上）；

1.10.5 OCC & Hardware Transaction Memory (HTM)

硬件厂商，例如 Intel、ARM 会提供对内存的 Before-or-After Atomicity 的读写，这样就不需要软件层面的 2PL 和 OCC，进而提升并发性能。

Intel 推出 Restricted Transaction Memory (RTM)，ARM 推出 Transactional Memory Extension (TME)。

以 Intel 的 RTM 为例，它提供了两个新的汇编指令：xbegin 和 xend，相当于事务的开始和结束。

在 OS 及以上层次，可以这么使用：

xxxxxxxxxx
if _xbegin() == _XBEGIN_STARTED:    // 成功启动事务
    if conditions:  // 手动取消事务
        _xabort();  // abort (rollback)
    // critical code here（访问共享资源）
    // ...
    _xend();    // 事务 commit
else:   // 与其他线程冲突，启动失败
   abort case

优点：

• 处于 xbegin() 和 xend() 间在内存中执行的操作满足 before-or-after atomicity；

• 大多数情况下，比 2PL 和 OCC 编程起来更简单；

• 大多数情况下，性能会很好（硬件高效于软件实现）；

缺点：不保证成功（可能多次 abort），因此处理 abort case 时较为麻烦；

• 而且不能直接使用 retry（可能导致 live lock）。一般的做法参见下文；

为什么 RTM 不保证成功？

因为 RTM 底层是采用 OCC 的思想实现的：

• Use CPU cache to track the read/write sets of CPU reads/writes；

• Use cache coherence protocols to detect conflicts ；

  什么是 cache coherence protocols？

  在多处理器系统中，很多情况下多个进程可能需要一些相同内存块。主要由于：

  • 可写数据共享，例如两个进程通过 mmap 共享一块匿名页或文件页；

  • 多核间进程调度（process migration）；

  • ……

  那么需要 cache 做一些统一措施，确保多进程能看到的数据是一致的。

  实现这个协议有两类思路：directory-based 和 snooping；

  前者提出将一块物理内存的共享状态存放在特定的位置（称为 “directory”，不宜译为目录）；

  后者设计比前者简单，提出对 CPU Cache 的共享总线进行侦测，如果侦测到总线上的操作与当前中的某个 block 相符 (tag一致)，则采取某种动作（具体动作由具体的实现决定，比如 MSI），这种系统需要支持广播功能的总线。

  更多信息请查阅网络。这是 CPU 设计领域的知识。

问题是 CPU cache 比较小（取决于硬件），一旦用完了就会导致无条件 abort；

一般情况下 RTM 使用 L1 Cache 跟踪 writes，L2/L3 Cache 跟踪 reads；

为什么 L2/L3 Cache 不会同时跟踪读写？

RTM 除了受到 CPU Cache 的限制，还有 Limited Execution Time：事务的执行时间越长，transactions abort 的可能性更大：

• 主要原因：CPU 中断会无条件打断 RTM 操作；

• 为什么会打断 RTM 操作？因为 Context Switch 会污染 CPU Cache，导致需要重新再来；

如何处理不成功的情况？

就是因为 RTM 是基于 OCC 的硬件实现，因此会因为 false validations 或者硬件上的限制（cache 不够大）而出现频繁的 Aborts。

所以在使用 RTM 时，在尝试一定次数（counter）后就需要切换到 fallback path 上（pessimistic sync），例如：

xxxxxxxxxx
if _xbegin() == _XBEGIN_STARTED:    // 成功启动事务
    if lock.held():
        _xabort()
    // critical code here（访问共享资源）
    // ...
    _xend();    // 事务 commit
else:   // 与其他线程冲突，启动失败
    // switch to perssimistic sync
   lock.aquire()

简单总结一下：

• OCC 是区别于 2PL 的实现 before-or-after atomicity（isolation）的另一种经典协议；

  • OCC 的思想也被硬件设计者所接受（出现了各种 HTM）；

• 硬件实现了对 Transaction Memory 的支持；

  • 编程模型很简单（不需要锁）：程序员只要在内存中进行计算就能利用到（例如 in-memory database）；

  • 底层基于硬件支持，如果使用得当，性能很好；

    • 也不需要软件层面的锁和原子操作；

    • 但是编程人员需要注意一些常见陷阱（CPU cache 和执行时间的局限，需要特殊处理 aborts 的情况）；

1.10.6 MVCC

我们知道，无论是 2PL 还是 OCC，在大量的只读事务情况下性能很差。OCC 是因为 read validation fails，2PL 是因为读的时候锁住了其他线程。

当问题是大多数实际应用场景（例如淘宝页面）都是以读为主的，因此不得不针对读的性能优化。

我们先从 OCC 下手。OCC 多数的 False Aborts 主要是因为一下两种情况：

• 无关读写冲突（T1 Read(A)=A0 -> T2 Write(A=A1) -> T1 Validate(A)）：不违反 serializability，但是无法通过 read validation；

• 无关写读冲突（T2 Write(B=B1) -> T2 Read(B)=B1 -> T1 Validate(B)）：没有 isolation 的情况下，写会影响到读，但我们希望预先隔离起来；

能否让读的情况不发生 false aborts（也就是能不能不 validate read）？

于是我们引入 “多版本” 的概念，每个事务操作的数据都有多个版本（multiple-versions），于是一个事务操作的一组数据就被称为 snapshot：

• 事务总是从一个持久化的 snapshot 中读；

• 事务修改 snapshot 的数据时更新数据的版本；

带有版本的数据的结构如下：

因此减少 false aborts 的目标就是：尽量避免在读 snapshot 时 race condition（如何让 read 总是读到符合顺序的 snapshot 上的数据）。

如何确定版本？可以使用时间戳来表示。我们需要它反映事务的串行执行顺序：

• 如果 $T_1$$T_1$ 在 $T_2$$T_2$ 前就结束，则 $T_1$$T_1$ 的 start 和 commit 时间都更小；

最简单的解决方案的就是使用 global counter：

• Using atomic fetch and add (FAA) to get at the TX’s begin & commit time；

• TX Begin: use FAA to get the start time；

• TX Commit: use FAA to get the commit time；

但有两个问题：

• 全局 FAA 可能在高并发情况下仍然不能很好；

• 在分布式系统中不同物理结点是不同步的（以后讨论更先进的 timestamp）；

现在我们用 MV 改进一下 OCC（incomplete）：

1. 获取 start time；

2. Phase 1: Concurrent local processing

   • Reads data belongs to the snapshot closest to the start time（总是从最接近当前 start time 但 commit time 不晚于这个时间的 snapshot 中读）；

   • Buffers writes into a write set；

3. 获取 commit time；

4. Phase 2: Commit the results in critical section；

   • Commits: installs the write set with the commit time；

这样我们就不需要 validation 了！

xxxxxxxxxx
Commit(tx):
   for record in tx.write_set: 
       lock(record)
   let commit_ts = FAA(global_counter)
   for record in tx.write_set:
       record.insert_new_version(commit_ts, ...) 
       unlock(record) 

Get(tx, record):
   while record.is_locked():
         pass
   for version,value in record.sort_version_in_decreasing():
       if version <= tx.start_time: 
          return value

但是仍然需要锁来锁住从获取 commit time 到提交完成的区间，因为可能出现 partial updated snapshot;

我们看一个读过程（一个 start，另一个准备 commit）：

在 $T_1$$T_1$ 先获取到 start time 的情况下，确实读是正确的，不需要 read validations。但是出现了 partial snapshot（也就是中间状态对外可见）的问题。试想如果 $T_1$$T_1$ 和 $T_2$$T_2$ 的顺序交换了呢？

这个时候就会出现没法跟踪到另一个串行顺序在 $T_1$$T_1$ 之前的 $T_2$$T_2$ 的更新，从而导致 $T_1$$T_1$ 只能读到 $T_2$$T_2$ 修改一半的内容；

综上，我们需要确保 $T_2$$T_2$ 的一个 snapshot 完整的更改过程（一般短于这个 transaction）是 atomic 的，也就是对 snapshot 的更改过程上细粒度锁：

xxxxxxxxxx
Commit(tx):
   for record in tx.write_set: 
       lock(record)
   let commit_ts = FAA(global_counter)
   for record in tx.write_set:
       record.insert_new_version(commit_ts, ...) 
       unlock(record) 

Get(tx, record):
   while record.is_locked():
         pass
   for version,value in record.sort_version_in_decreasing():
       if version <= tx.start_time: 
          return value 

这样在完全修改 snapshot 的状态前，未修改的部分不会被读到：

考虑一个问题，能否交换 commit 阶段的 “获取 commit time” 和 “上锁” 的顺序？不行：

xxxxxxxxxx
    T1                  T2
                    CTS = 1
  STS = 2
  Read(A) = A0
                    Lock(A)
                    Lock(B)
                    Write(A)
                    Write(B)
  Read(B) = B1

相当于 $T_1$$T_1$ 最终还是读到了 partial snapshot！所以不行。

最终，我们可以使用改进的 incomplete MVCC 完成 read 过程的 isolation！

但还是要 validate writes，因为两个并发写冲突通常不可串行化，难以避免。

validate writes 的方式就是在 commit 阶段，其他事务针对当前事务已经写的 write set 中的数据，commit time 是否晚于当前事务的 start time（是否有更新的版本），如果有就 abort；

总结一下：

1. 事务开始阶段，先从 global time 获得事务的 start time；

2. 读数据 $X$$X$ 时检查最大的 $X$$X$ 的版本，并且早于当前事务的 start time（保证串行顺序）：也就是到数据库读 snapshot；

3. 写数据 $X$$X$ 时向 buffer 中写，并且加入 write set；

4. 最后事务提交时，先从 global time 获得事务的 commit time，然后逐一检查 write sets 中每一个数据是否有比当前事务 start time 更晚的 commit time。如果有则 abort，如果无，则更新所有 write set 中的数据，并将数据对应的 commit time 更新为当前事务的 commit time；

现在这个 incomplete MVCC 就没问题了吗？大部分情况都符合 Before-or-After Atomicity 了，但现在还有一个问题需要解决：Write Skew；

可能会出现这种情况：

$T_1$$T_1$ 和 $T_2$$T_2$ 在先后读取共享资源后，分别修改对方之前读的资源。这种情况实际上是应该 abort 的，但在 incomplete MVCC 下都能正常提交事务。

主要是只 validate writes 而没有 validate reads 造成了这个问题。

解决这个问题很简单：

• 对于 read-write transaction 的情况 fallback 到 OCC（再检查一次 read set）；

• 但 read-only transaction 仍然能够享受 incomplete MVCC 的没有 aborts、没有 validations 的优势；

这个 incomplete MVCC 就被称为 Snapshot Isolation（SI）；

其实，除了在 snapshot isolation 中首先实现了 multiple-versions，现在的 2PL/OCC 的变种也用到了 multiple-versions（以后讨论）。

1.10.7 Conclusion

总结一下事务中的 consistency。

我们在 OS 系统中讨论 “事务”，其实是一种管理数据行为的抽象。这个数据可以是 KVStore entries、文件系统的 meta-data、处理器 meta-data 等等；

我们要让事务保证 ACID 的性质：

• Atomicity: all-or-nothing

• Isolation：确保两个线程间的 before-or-after 的 atomicity，不会读到中间结果、避免 race condition；

• Durability：一旦事务被提交，就需要对数据的更改是持久化的；

• Consistency：它的必要条件是 atomicity；在此基础上，还需要编程人员保证程序语义的正确性，才能实现数据一致性；

之所以需要这些性质，就是想要实现 failure atomicity 并避免 race condition，最终简化管理数据的抽象。

我们通过 Logging 和 Recovery 策略，实现了 Atomicity 和 Durability；通过 Concurrent Control Methods（2PL/OCC/SI）实现了 Isolation；最终数据库约束系统和编程人员共同确保 Consistency（这里不讨论）。

1.11 Replications & Multi-site Atomicity

如何让 1000 台机器像 1 台机器一样工作？

1.11.1 2-PC

回忆一下，OCC 和 2PL 在大量读的情况下性能不佳，因此我们引入了 MVCC，利用 Snapshot Isolation 实现一个更高效的读，规避了 read validation；

假设一台机器的物理资源已经不足，现在我们希望分布式存储，将同类数据存在不同机器上；

• Clients + coordinator + two servers；

• 在每台机器上，我们都有 logs 来确保 atomicity；

这个时候显然单机的数据库的通过 logging 是不能实现整个系统的 all-or-nothing atomicity 的！

这是因为事务分布在不同物理节点上，于是，事务会被切分为两种：

• high-layer transaction：全局语义下的事务；

• low-layer transaction: nested 在 high-layer 事务中的每个物理节点中的事务；

问题转化为，如何使 high-layer 事务协调 low-layer 事务，保证所有 low-layer 事务的 all-or-nothing atomicity；

我们需要知道，在分布式场景下，仅仅有 commit 和 abort 的状态是不行的，还需要 tentative commit 状态，表示已经准备好 commit，需要等到 coordinator 判断让其他所有 servers 都写入时再进行；

于是人们基于这个思想，引入一种新的协议：Two-Phase Commit；

Phase 1: Preparation / Voting

• 推迟所有 low-layer transaction 的 commitment，而是进入 tentative commit 状态；

• 当前 low-layer 事务要么 tentative commit，要么 abort，higher-layer 事务需要逐一发送 prepare 请求，判断是否全部准备好 commit；

Phase 2: Commitment

• 一旦有任何一个 low-layer 事务 abort，coordinator 向其他所有事务发送 abort 请求；

• 一旦所有 low-layer 事务 tentative commit，coordinator 发送 commit 请求，通知所有事务提交；

看起来很美好，对吧？我们讨论一个 conner case 来考虑系统的 fault tolerance：假设分布式系统中任一台机器挂了 / 任一次请求通信挂了（不可靠）怎么办？

我们回忆单机的 logging 会写 redo-undo log，如果事务应该提交，但是准备 commit 时挂掉，那么单机会在重启时重做，而如果全局决定了 abort 那么数据就会不一致！因此我们需要更改记录 log 的方式。

解决方案是：

• 在 low-layer 事务中，将原先的 commit 的 log entry 改成 tentative commit entry（PREPARED）；

• 在 high-layer 事务中，收集所有 low-layer 事务是否有 ABORT / timeout，有则 ABORT / retry（可能是网络连接问题）；

  如果没有 ABORT，则 COMMIT（也记录日志）；

总而言之，我们有原则：

• 总是遵循 coordinator 的决定；

• 一个 low-layer 事务如果 abort 就等待 coordinator 的处理；如果 tentative commit，则还是等待 coordinator 处理（没有消息就不动），让它 commit 再进行，让它 abort 再 abort；

举个例子，一个 high-layer 事务有两个 low-layer 事务：

现在我们在新的解决方案下讨论所有故障的情况：

• High-layer 事务 phase 1 发送错误：timeout，resend 即可解决问题；

• High-layer 事务 phase 1 接收错误：timeout，resend 即可解决问题；

• High-layer 事务 phase 1 发送时 low-layer 事务所在 server 宕机：重试超时，认为 abort，全局 abort。

  无论这个宕机的 low-layer 事务是否准备好（prepared/abort），都不会让当前事务 commit 的；

  后者好理解，如果是前者，在重启后看到日志是 prepared，还会向 high-layer 事务 server 发送请求查询，发现 abort；

• High-layer 事务 phase 2 发送错误：timeout，可以 resend，也可以等这个接收方超时询问，即可解决问题；

• High-layer 事务 phase 2 接收错误：此时收到 commit 的 server 已经提交，为了防止问题发生，会 resend commit 指令直至有回应；

• High-layer 事务 phase 2 发送时 low-layer 事务所在 server 宕机：high-layer 事务 server 必须等待（因为有的 server 已经交了），直到挂掉的 server 重启后，看到自己日志 prepared，会再次向 high-layer 事务所在 server 确认，这个时候再 commit 和确认就行；

• High-layer 事务 server 自身在 phase 1 任意时间宕机：其他 servers 等待，重启后发现原来事务的 log 没有结束，因此 undo 并向其他 servers 发送 abort；

• High-layer 事务 server 自身在 phase 2 任意时间宕机：某些 servers 已提交，某些 servers 正在等待，重启后发现原来事务已经 commit 但是为了防止没有 commit 完全，再重新全部对这个事务发送一次 commit 请求；

  这个是否重试的依据，可以考虑在 phase 2 结束时，在所有 low-layer 事务 commit 后再记一个 log 表示全部 commit 已经核实（类似 checkpoint）；

Remaining challenge：我们最终发现，这个解决方案看起来实现了 all-or-nothing atomicity，但是可用性不强，尤其是 coordinator 挂了后，事务就需要一直等待它重启了。

此外，我们还需要知道：

• 尽可能少记日志（就像 redo vs undo-redo logging，对性能好）。只在必要的时候（例如 commit/abort 时）才记日志；

• low-layer 事务如何处理 checkpoints（方便移除日志）？需要 high-layer 事务做一些 additional work；

最终，Two-Phase Commit 需要在 2PL 和 OCC 上应用：

• 2PL：只有到 high-layer TX 决定 commit 或 abort 时，每个 low-layer TX 才能放锁；

• OCC：其中 phase 2 和 3（the validation & commit phases）会被转移到 coordinator 中执行；

1.11.2 Replication

那么 2PC 实现了 CAP 的哪些特性？答案是只保证了 Consistency。因为：

• 如果 coordinator 挂了，其他相关的 transaction 都需要等待它恢复；

• 参与分布式事务的一个服务宕机后，需要一直等待这个服务可用后才能继续进行；

因此我们需要 replication 来确保高可用性。

实现 high availability 的优点：

For performance:

• Higher throughput: replicas can serve concurrently;

• Lower latency: cache is also a form of replication;

For fault tolerance: Maintain availability even if some replicas fail;

这里我们主要讨论如何备份多份数据，对 coordinator 的备份是类似的。

有两种备份方法：

• Optimistic Replication (乐观备份，只保证 eventual consistency)

  • 容忍一定程度的数据不一致，之后在慢慢 fix；

  • 适用于允许 out-of-sync replicas（备份节点可以存在过时数据）时的场景；

• Pessimistic Replication (悲观备份，保证 linearizability)

  • 在各个 replicas 间保持强一致性；

  • 在 out-of-sync replicas 会造成严重问题的时候应该使用这种方法；

有些情况下应该采取 悲观备份方法，例如 2PC 的 coordinator（需要 commit 决定是统一的），也就是要求 “Single-copy Consistency”（多台机器和一台机器是一样的），需要从外界看起来只有一份数据。强一致性的代价就是牺牲一部分性能和可用性。

我们可以用 Replicated State Machine（RSM）这个模型来做 pessimistic replication（尽管 RSM 中会有很多 replicas）：

1. （初状态相同）Start with the same initial state on each server；

2. （完全相同的输入）Provide each replica with the same input operations, in the same order；

3. （保证操作不随机）Ensure all operations are deterministic

   E.g., no randomness（把随机数生成也作为统一输入）, no reading of current time, etc.

理想情况下 RSM 能实现 single-copy consistency；

问题是，clients 的请求到达不同 servers 的顺序可能不一致（这是物理情况决定的）。由于我们现在要实现 pessimistic replication，因此不能之后再 re-order，而是需要立即 re-order。我们后面讨论这个问题。

现在来看 RSM 模型的实现。一般来说类似 GFS 的 primary backup（主从备份）就能解决问题：

也就是：使用 view server（可以是独立物理节点/独立进程），来确保只有一个 server（primary）从 clients 接收请求。并且 primary 应该：

• 统筹所有的写操作，One-Write Principle：

  • 决定所有操作的唯一顺序；

  • 决定所有的 random value（random() / time() 等等）；

  • 在确定所有 replicas 全部写好后向 coordinator ACK 确认（和 GFS 的 Write，以及 Linearizability 的 Primary-backup 实现一样）；

• 在某个 backup failed 后重新建立一个新的 backup（有些问题需要注意，之后讨论）；

这个 primary-backup 为什么这么构建？

首先，我们需要 primary、backup 来做 replication；谁做 primary、谁做 backup 可以事先指定。

如果 backup 挂了，primary 来检查并建立新的 backup；

如果 primary 挂了，则依赖于 coordinator（知晓 primary/backup 的状态），用它来选举新的 primary。

这种解决方案还是有问题：

如果 coordinator 挂了？那么我们建立多个 coordinator 来确保容错性。

如果两个 coordinator 间 “split-brain”（network partition）了，怎么办（Partition Tolerance）？这可能会选举出多个 primary，在 network 恢复后出现问题！

因此我们引入唯一一个 view server，将 coordinator 中判断、任命 primary 的工作分离出来，与所有 primary 和 backup 维持心跳，并告知 coordinator 谁是 primary。

View Server 的具体任务是：

• 与其他所有 server 构成心跳连接；

• 维护一个表，记录 a sequence of view，每个 view 包括：

  • view number：相当于版本号；

  • primary server：当前谁做 primary；

  • backup servers：剩下在线的做 backup 的 servers 列表；

• 必要时提醒指定 server 是 primary 或 backup 的身份（例如切换 primary 的时候）；

• 回复 coordinator 的查询：“谁是 primary”；

  一般回答一次后 coordinator 的后续请求就向该 primary 发送，可以减小 view server 的负担；

  直至 coordinator 无法联系该 primary 或对方一直拒绝；

• 在一个 server 挂掉后，动态地 recruit 新的空闲 server（之前 primary 的任务）；

此外，primary 和 backup 需要遵循下列规则：

• primary 统筹写操作需要完成上述 3 个同样的要求；

• backup 必须拒绝来自 coordinator 的写请求；

• 相反，primary 必须拒绝来自其他 server 让它 forward 和写的请求；

• primary 必须是上一轮 view 的 backup/primary，不能是新被 recruit 的 server；

考虑一个 corner case：

如果此时 View Server 因为无法和 S1 建立心跳连接（但 S1 是存活的，和 S2 和 coordinator 都能联系），而决定选 S2 为 primary 时，它会先更新一轮 view 并且向 S2 发送身份变更信息：

此时无论 coordinator 联系谁都会错误：

• 一开始 coordinator 按缓存的信息联系 S1，由于 S2 称为 primary（现在两个 primary），拒绝 S1 的 forward 请求，导致 S1 返回错误；于是 coordinator 重新咨询 view server；view server 告诉 coordinator 应该找 S2；

• coordinator 找 S2 也会被上面同样的理由拒绝；

这个中间状态称为 “repair time”，我们一般允许系统短时间地处于该状态。

有了上述规则，即便 coordinator 也有 replicas，整个系统也能有 partition tolerance 了。

现在还有一个重要问题：如果唯一的 view server 挂了怎么办？我们知道，为了保证 partition tolerance，我们不应该再对 view server 继续 replication 了。

不过幸运的是，view server 的任务足够简单、本身足够轻量，我们可以使用分布式协调服务来确保多个 view server 的对外完全一致性。

这个分布式协调服务像 ZooKeeper、Raft 都可以胜任，它们的思想都起源于 Paxos（经典，但晦涩），下面介绍 Paxos 的基本原理。

1.11.3 Single-Decree Paxos: Distributed Consensus Mechanism

Paxos 这样的分布式协调机制需要解决的问题就是，如何在系统存在大量并发读写、延迟、network partition、每个 server 随时可能宕机的情况下确保数据的写操作能够以正确和唯一的顺序最终传达给所有分布式 servers 并持久化。

而 single-decree Paxos 则是用来解决上述问题的子问题：如何确保系统不受上述因素影响 agree on one value。

也就是，实现 RSM 的某个状态在所有 replications 上都能保证最终顺序一致，不论现在的情况如何；

或者说，让 RSM 的单个 Log Entry 维持一致；

Single-decree Paxos 机制如下：

在 Paxos 这个独立的 “岛” 中，有 3 类角色：Proposers（提议者）、Acceptors（选举者）、Learner（记录者）。

这 3 类角色都是逻辑角色，实际上可以一个物理节点分饰两角。

其中：

• Proposers（Leader）需要接收外界 clients 发来的请求，并且执行整轮 Paxos 协议；

• Acceptors 需要记录：期间 proposers 提出的决议、接受过的协议，以及其他状态信息。下文中，我们将超过半数的 acceptors 同意称为 “多数同意”；

• Learners 在协议最终达成共识后，从 acceptors 广播的信息中记录固定下的结果，并且将结果响应外部 clients；

注意，提出的 proposal 有一个 ID 和对应的 Value，Value 是什么不重要，只要知道一个 proposal 中有一个 ID 和对应的 proposal value 能携带信息就行。

此外，在 paxos 协议中，存在决议轮数（round），每一轮有唯一的 ID 标识。每轮之间不需要维持同步关系。可以使用超时等待的机制。

并且当一个位于 $j$$j$ 轮或更早 server（不论是谁）因为延迟原因接收到了来自 $j+1$$j+1$ 轮的信息，那么 abort 当前的 $j$$j$ 轮的信息，转到 $j+1$$j+1$ 轮（后面详细阐述）；

而每一轮可以分为不同的 phases。下面详细阐述不同 phases 的内容：

Phase 1A: Prepare

Leader 视角：

Proposers 中的 leader（optional，也可以不选举，每个 proposer 都行）创建一个 proposal $N$$N$ 向 acceptors 提议；

并且要求 $N$$N$ 比当前 proposer 看见的（包括不是自己提出的）proposal ID $N_h$$N_h$ 更大。

注意：这里的 proposal 不含有 proposal value，只是为了确认是否能获得多数同意。

具体为什么，后面介绍。

Phase 1B: Prepare

Acceptors 视角：

接收来自 leader 的 proposal(s)，并且判断：

如果这个 proposal ID $N$$N$ 比之前见过的所有 proposal ID 都大，那么 promise（同意），并且：

1. 回复之前同意过的 proposal ID 最大的 proposal ID $N_a$$N_{a}$（但是对应的 proposal value $V_a$$V_a$ 留空到 Phase 2B 记录）；

2. 保证从这之后拒绝所有 ID 小于 $N$$N$ 的 proposals；

3. 更新 “见过最大的 proposal” 的 ID $N_h$$N_h$（见过和同意过不一样，参见 Phase 2B 的解释）；

否则直接忽略（不予回复）；

Phase 2A: Accept

Leader 视角：

如果一段时间后没有收集到 Acceptors 的多数同意（超时或者发现 proposal $N+1$$N+1$ 被同意了），则 abort 掉这个 proposal；如果 clients 还有请求，这个 proposer 就回到 phase 1A 继续；

反之，如果 Leader 收到了 acceptors 的“多数同意”（定义参见上文，下面不再赘述），则说明自己的 proposal ID 极有可能（为什么是可能？因为可能存在 network partition）是目前最新的，因此判断：

• 如果 acceptors 返回的 “之前同意过 proposal ID 最大的 proposal value” $V_a$$V_a$ 不为空（NULL），说明：之前的 proposal 已经有过多数同意的决议并且成功达成一致，或者有过多数同意的决议但因为其他原因该轮协议没有继续进行；

  那么为了保证分布式协调一致性，这轮 proposal 只能使用该轮的 proposal value $V_a$$V_a$ 作为本轮 proposal value $V$$V$（这也是为什么 phase 1A prepare 时不用发送 proposal value 的原因），这样可以在各种场景下让 learners 确定唯一值；

  注：如果 acceptors 返回有很多种 proposal value（来自不同 proposal ID），那么总是取最大 proposal ID 的非空 proposal value；

• 如果 acceptors 返回的 “之前 proposal ID 最大的 proposal value” $V_a$$V_a$ 全部是 NULL，说明这个 proposal 是第一次获得多数同意的提议，因此可以设置来自 client 请求的值作为 proposal value；

然后，在上述判断确定好 proposal value 后，向 acceptors 声明：proposal $N$$N$、proposal value $V$$V$ 获得多数同意。这一步的作用是：

• 让 acceptors 补充记录 “同意过最大的 Proposal” 对应的 proposal value $V_a$$V_a$；

• 让 acceptors 知道当前被多数同意的 proposal，并且让 acceptors 广播给 learners；

Phase 2B: Accept

Acceptors 视角：

如果 leader 发来的 “声明获得多数同意” 的信息 $\text{Accept}(N,V)$$\text{Accept}(N,V)$ 中 $N$$N$ 仍然是见过的最大 ID，那么：

1. 补充记录 “同意过最大的 Proposal ID” 对应的 proposal value $V_a$$V_a$；

2. 向 Proposers 广播 proposal ID $N$$N$ 已经达成一致的信息；

   发给 proposers 是为了：

   • 让处于 phase 2A 等待的未拿到多数同意的 proposers abort 更旧的 proposal，回到 phase 1A；

   • 让所有 proposers 更新 “看到的最大的 proposal ID” $N_h$$N_h$；

否则（期间有 proposal ID 更大的 leader 声明 “获得多数同意”）会忽略这个声明。这种情况可能是 leader 遭遇了延迟，或者其他原因。

这也是为什么 acceptors 存放的 “同意过的最大的 Proposal ID” $N_a$$N_a$ 和 “见过的最大的 Proposal ID” $N_h$$N_h$ 不一定一样。

Phase 3: Learn

如果 leader 获得了多数 acceptors 的 “达成一致” 的响应，则说明真正确定了 Proposal Value（因为确保多数 acceptors 已经在 Phase 2B 记录了这个 value 作为 $V_a$$V_a$，后面的 proposal 只能 “继承遗志”），就向 Learner 广播决定消息（decide）；

否则 leader 重新回到 Phase 1A，带着这个值重新提出一次 proposal。

最终获得消息的 Learner 持久化决定（decide）的 proposal value，并且向 clients 回复。

最终，无论 clients 输入什么请求，所有 learners 总是会保持这个 proposal value 不变。

现在我们最终考虑几个问题：

思考 1：如果 “获得多数同意” 的声明 $\text{Accept}(N,V)$$\text{Accept}(N,V)$ 被忽略，会对 paxos 的正确性有影响吗？

答：不会有影响。此时多数 acceptors 已经记录了 $N_a$$N_a$，其中 $V_a$$V_a$ 要么是前些轮的 proposal value，要么是 NULL；如果是前些轮的 proposal value，则由于 Phase 2A 的性质，这个获得多数同意的 $V$$V$ 一定与 $V_a$$V_a$ 相同，因此完全等价；

如果 $V$$V$ 是 NULL，那么就和 “leader 刚准备 propose 就挂了” 的情况一样，也不会对正确性有影响。

思考 2：可能出现 $N_a$$N_a$ 和 $V_a$$V_a$ 不匹配的情况吗（例如 $N_a$$N_a$ 是一轮 proposal ID，但 $V_a$$V_a$ 是和这一轮不同的 proposal value，不包括 NULL）？

答：不会的。因为如果 Phase 1B 同意并记录了 $N_a$$N_a$，在到 Phase 2B 前其他更新的 proposal 被同意了，那么说明此时更新的 proposal 也已经通过 Phase 1B 刷掉了旧的 $N_a$$N_a$，此时 $V_a$$V_a$ 只有可能是 NULL 或者与本轮相同的 proposal value（由 Phase 2A 决定）；

思考 3：如果多数 acceptors 虽然达成一致，但因为某些原因未能向 proposers 发送达成一致的信息，会不会造成出现多个 “达成一致” 的 Proposal Value $V$$V$？

答：不会的。不用担心这个多数达成一致的 $V$$V$ 被丢失，因为多数达成一致的 $V$$V$ 的 acceptors 一定已经在 Phase 1B 中记录了 “同意过的最大 Proposal ID” $N_a$$N_a$ 以及 Phase 2B 中记录对应的 $V_a$$V_a$；

所以，之后即便有 proposal ID 更大的 leader 声明获得了多数同意，也会 “继承它的遗志”（原因参见 Phase 2A，“总是取最大 proposal ID 的非空 proposal value”），选这个最早达成一致并广播的 $V$$V$ 作为它的 proposal value。

因此无论怎样，最终总会保持最先多数达成一致的 proposal value。

思考 4：最终达成一致的 Proposal Value 最早在什么时候被确定的？

答：

• 不是在 leader 获得多数同意时。因为 Leader 可能挂掉、可能因为延迟，期间有更新的 proposal 被多数同意并且首次设置了 proposal value；

• 不是在超过半数 acceptors 收到 “声明获得多数同意” 的信息时。首先这个时间节点只有从上帝视角才能知道（acceptors ）。其次，收到声明的 acceptors 可能之后立即挂了，导致回应少于半数，leader 重试；

• 只有当超过半数 acceptors 发送 “达成一致” 的信息（这个也只有上帝视角才能知道），或者说 leader 收到超过半数 acceptors “达成一致” 的信息（这个比前面稍微晚一点点，但系统能感知到）；

思考 5：如果 Phase 1B 中 acceptors 在发送完成同意后立即挂掉，是否应该保存一些信息？

答：应该利用日志等手段持久化 $N_h$$N_h$；防止重启后状态丢失对 paxos 正确性的影响（例如其他 leader 并不是最大的 proposal ID 却被同意）；

思考 6：如果 Phase 2B 中 acceptors 在接收到 “声明获得多数同意” 的消息后挂掉，是否应该保存一些信息？

答：应该持久化 $N_h,N_a,V_a$$N_h,N_a,V_a$，防止重启后状态丢失对 paxos 确定唯一决定值造成影响；

思考 7：如果 leader 在发出 “声明获得多数同意” 的消息后挂掉，应该怎么办？

答：应该持久化 $M_h$$M_h$（比 $N_h$$N_h$ 更大的、决定作为 proposal ID 的值），并且重启后重新 propose；

但是 $M_h$$M_h$ 也不必要（不会影响正确性），只是如果没有的话 proposers 需要一轮一轮尝试，会增大 conflicts 和 restart 的次数，降低性能；

思考 8：从第一次 propose，到 learners 最终得到决定的值，最少需要几个 Phase 的通信？最多呢？

答：不考虑其他干扰因素，完整需要 2 个 phase（两个来回），最坏情况一直没法选出决定的值。

思考 9：如果没有 Learner，能否知道 paxos 最终决定的值？

答：可以，但是过程会更复杂，性能会下降。proposers 需要 2 次请求并对比结果才能知道最终决定的值；

1.11.4 Multi-Paxos

Basic Approach

我们注意到，single-decree Paxos 只是解决统一一个值的子问题（确定 RSM 中的一个状态在所有 replications 中统一，也就是让 RSM 单个 Log Entry 统一），如果希望统一一系列值（RSM 继续转移状态），就没法办到了（因为 single-decree Paxos 总会保持最先多数达成一致的 proposal value）。

永远只投出单个值的 single-decree paxos 在实际场景中几乎不可用。

例如我们没法用 single-decree paxos 来实现 View Server（对于不同 view 的变化没法应对）。

最简单的解决方案是，我们可以为每个 Entry 创建一个独立的 single-decree paxos 实例，让它们各自沉淀出唯一确定的值。

例如对于一个正常情况，我要向 RSM Log 中插入一个 Entry yyy（状态转移），正常情况初状态如下：

然后接收到 client 请求的 $S_1$$S_1$ 会选择第 3 个 Single-Decree Paxos 实例并进行 propose，经过最少 2 轮的协议，Learner 成功得到决定的值，填写到 Log 中，如下：

如果之前是有问题的呢？例如假设有一个 server $S_1$$S_1$ 因为 network partition / 延迟等等原因迟迟不知道上一轮决定的 value（部分 learner 不知道），如下：

现在 client 想向 $S_1$$S_1$ 发送插入 yyy 的请求，这个时候 $S_1$$S_1$ 会选中（旧的）第 3 个 Single-Decree Paxos 实例，然后进行 propose，我们知道，yyy 肯定无法获得多数同意（因为在旧的实例中，多数 acceptors 已经对 zzz 达成一致了），因此最多只会补上第 3 轮的 zzz；

还需要重新再请求一轮才能真正写入 yyy：

依此类推，如果 client 请求的是比最新决议晚 $x$$x$ 轮的 server，那么至少需要重复 $x+1$$x+1$ 次请求才能达成插入的目标。

Improvements

我们知道这样是不高效的，原因有几点：

1. 每轮 Single-Decree Paxos 可能有多个 proposers 并发 propose，会频繁出现 conflicts 和 restart 的情况（例如它们都没能拿到多数同意）；

2. 不同 Server 间的 Learners 情况不一，可能造成需要多轮请求才能写入的情况；

我们可以作出如下改进（以下改进不必要，但可以提升 multi-paxos 的性能）：

• 每次只选出一个 Leader 可以 propose（随机选取一个就行，因为不需要保证唯一，只是尽可能减少）；

• 一个 Leader 收到 requests 后，可以先向多个 paxos 实例提前发送 Prepare（Phase 1，反正不需要 propose value），提升性能；例如下面两个做法的结果一样：

不过除了性能问题，multi-paxos 还可能出现日志空洞的问题：

有些 server 有、有些没有决定值的情况我们前面就讨论过，可能是因为延迟或者 partition 或者宕机等等原因。一般需要再过一段时间才能最终一致；

而对一个 paxos 实例所有 server 都没有决定，则可能是一个 server 在提出 propose 时立即挂了，或者决定前立即挂了，则需要 client 单独重新请求（但不影响分布式协调的特性，RSM 可以最终统一）。

总的来说，paxos 从数学理论层面描述了分布式协调系统的可行性，但是对于工程上如何实现 RSM 而言并不友好。因此人们提出了 Raft 算法来在工程实现层面支持分布式协调机制。

1.11.5 Raft

Raft 作为一个与 Paxos 等价的分布式协调系统，它在工程实现方面非常友好。

其中，Raft 与 Paxos 最重要的一点不同就是，它们的目标不同。Paxos 确保在分布式环境中选取出唯一稳定、一致的 proposed value，需要 multi-paxos 多实例实现一系列稳定的值（也就是日志），并且它不保证日志的 entries 全部填满；

Raft 目标就是在分布式系统下，为 Replicated State Machine 维护 replicated log，确保这些 log 的顺序一致（前缀内容相同），最终一定能相同。

Raft 的实现方法从较高的层次上看，有如下几点：

1. Leader Election：仍然坚持 One-Write Principle，选举其中一个 server 作为 leader；当 leader 挂了后重选；

2. Log Replication: Leader 负责接受来自 Clients 的请求，将它们按照某种顺序 append 到日志中，并且通过 overwrite inconsistencies 来 replicates 到其他所有 servers 中；

3. Safety：为了保证 logs 的 consistent 特性，只有 log 相对更新的 servers 才能成为 leader；

对于 Leader Election，Raft 设计了和 Paxos 类似的 “身份系统”：

在任意时刻，Raft 中的每个 server 都是以下身份之一：

• Leader：接受 clients 请求，并进行 log replication；

  • 和 multi-paxos 不一样，必须同时有且仅有一个 leader，才能保证正常工作；

  • 当 follower slow/crash 时一直尝试 retry replication；

• Follower：被动接收并执行 leader 发送的请求；

• Candidate：等待选举、准备成为 leader 的 server；

上图的过程解释两点：

• candidate 在发现当前存在一个更大的 term（选举 leader 时使用的任期）的 server 作为 leader，则转为 follower；

• leader 如果发现当前存在一个更大的 term 的 server 作为 leader，则可能是之前出现了 network partition，但由于更新的 leader 有多数承认，于是当前 leader 重选转为 follower；

其中 term（任期）代表的选举周期符合：