星罗棋布:《分布式系统与安全》课程笔记

星罗棋布:《分布式系统与安全》课程笔记

《分布式系统与安全》这门课,说不定会成为我从本科到硕士期间最有价值的课。

我最初因为选了《恶意软件》这门课,没敢选同一学期同样硬核的《分布式系统与安全》。后来一方面是因为《恶意软件》过于形式化、一方面是因为接触了分布式系统的生态,我选择了换课。第一节课开始没多久,我便确信自己做出了明智的(或许还是影响深远的)决定。

Brad Karp 老师讲解清晰又不失风趣,硬是把线上课上出了线下课的体验。尽管才上了两周的课,我相信这门课会让我受益匪浅。

一开始给我留下比较好的印象的就是老师摒弃了学校的课程平台 Moodle,转而使用 GitHub Classroom 和 Piazza。众所周知,所谓学校的课程平台并不会给师生带来什么好的体验。

此外,GitHub Classroom 还能自动测试和批改作业,很有意思,使用体验也很好。

这门课是没有教材的,这实际上对老师的水平提出了很高的要求:他必须自己四处收集资源备课、讲述自己的理解,而非将教材上的内容略作修改、照本宣科。取而代之的阅读材料是一系列经典论文。

背景

中心化系统面临的问题

  • 单节点故障
  • 难以支撑流量较大的应用
  • 易受攻击,且受到攻击后损失较大(这其实也应该算到单节点故障里?可能不能算故障)
  • 难以伸缩以提高资源利用率
  • 升级与维护时必须中止服务
  • 地理距离带来的网络延迟

分布式系统引入的问题

  • 数据一致性
  • 节点间的网络延迟、网络错误
  • Heterogeneity 异质性,不同节点可能使用不同语言、接口、API 等
  • 节点间并发问题
  • Partition resilience,不知道怎么翻译,弹性划分问题?

关于 Partition resilience 问题:假设两个用户在两个不同的服务节点上同时购买了最后一张机票,这张机票就会被卖出两次。有点像数据一致性问题。

OS 相关

这个部分基本是本科《操作系统》课和 Pwn 的内容,记录时顺便复习下。

Syscall

例如,应用通过 close(3) 关闭文件。而在 C 函数库中是这样调用 syscall 的:

1
2
3
4
5
6
close(x) {
R0 <- 73
R1 <- x
TRAP
RET
}

TRAP 实际上做的是:

1
2
3
4
XP <- PC
// switch to kernel address space
// set privileged flag (to enter high privlege mode)
PC <- address of kernel trap handler

这里的 XP 是某个用来暂时存放 PC 的寄存器。我们容易想到,之后就要在内核中运行代码了,这其实是十分危险的操作。怎么保证应用不会在内核里乱搞呢?答案是 Protected Transfer 机制。

为了避免用户在内核里随便运行代码,只有通过 kernel entrypoint 进入内核才能运行代码,而这个 entrypoint 就是 trap handler。至于具体跳到内核的什么位置则由硬件决定,而不能由应用来指定。这个具体位置则只能通过在启动时运行的内核态代码来决定,确保了用户态程序无法随意跳转到内核任意位置。

接着,在内核的 trap handler 中:

1
2
3
4
5
6
// save regs to this process' PCB
SP <- kernel stack
sys_close()
// executing in "kernel half" of process
// restore regs from PCB
TRAPRET

最后的 TRAPRET 的流程就比较简单了:

1
2
3
4
PC <- XP
// clear privileged flag
// switch to process address space
// continue execution

可以看到,TRAP 和 TRAPRET 要保存 / 恢复 PC、切换地址空间、切换用户态 / 内核态,而 trap handler 要保存 / 恢复寄存器,这些过程是必需的但又并没有产生实际的价值,还相对比较耗时。

并发 IO

而且,Syscall 常常涉及阻塞 IO 操作,很大程度上降低了资源利用率。一般来说有如下三种解决方法:

  • 多进程
  • 单进程、多线程
  • 事件驱动 IO

但首先,OS 本身对单进程单线程也提供了一定程度的并发 IO,比如:

  • 在文件系统中,会进行 read-ahead 和 write-behind 预读写磁盘数据
  • 类似地,read() 接收网络包时也会拷贝到 kernel socket buffer,write() 发送数据包时也会拷贝到 kernel socket buffer

多进程

多进程很容易理解:当一个进程阻塞后,切换到另一个进程运行。优点在于:

  • 进程间本身就相互隔离,不会互相影响
  • (如果有多个 CPU)同时还自动获得了 CPU 并发

不过 CPU 并发没有 IO 并发那么重要,相对 IO 并发而言更难实现,两者对速度的提升也是 2 倍和 100 倍的数量级。此时,氪金多买几台机器显然是更好的选择。

然而,多进程也有缺点:

  • fork() 调用本身比较耗时、耗内存,300 微秒左右的耗时并不能通过提升机器配置来缩短
  • 隔离性同时也是缺点,不共享内存意味着构建缓存或是记录统计数据比较麻烦

多线程

另一种方法是使用更轻量级的线程,此时线程们共享内存且分别拥有自己的栈,维持了一定的独立性。这一好处带来的是非常棘手的问题,那就是线程之间本身会互相影响、线程对数据的读写同样如此,使得我们不得不引入锁的机制来避免这些问题。但是引入新机制又会带来新问题,比如饥饿、死锁等。

这很像之前看到的火箭工程:要让火箭飞起来就需要带足够的燃料,但这些燃料本身也有重量,于是需要更多的燃料让整个火箭飞起来……(坎巴拉太空计划核心玩法)

几乎所有现代操作系统都对多线程有原生支持,这一般是通过内核线程实现的。这种实现下,内核清楚地知道每个线程的状态,也可以亲自调度线程到 CPU 上,非常灵活且同时支持 CPU 并发和 IO 并发。对于线程来说,每个线程不仅需要原有的用户态栈,还需要维护自己的内核栈和寄存器表。

这么做的代价就是:

  • 创建线程要内核干涉
  • 线程上下文切换要内核干涉
  • 加锁解锁也要内核干涉
  • 实现起来很大程度上依赖于 OS,难以移植

至于用户线程,对内核来说就是不可见的,内核只负责调度进程。此时,进程内部就需要一个线程调度器,清晰地知道每个线程的状态如何并及时调度。这样我们就可以进行非阻塞式 Syscall 了:

1
2
3
4
5
6
7
8
9
10
11
12
read() {
// tell kernel to start read
// mark thread waiting for read
sched();
}

sched() {
// ask kernel for IO completion events
// mark corresponding threads runnable
// find runnable thread
// restore regs and return
}

看起来很不错,但是仔细想想,这中间涉及的事件通知机制,需要我们的调度器具备相当强大的能力。它需要让内核通知它:

  • 创建网络连接事件
  • 数据到达 socket 事件
  • 磁盘读取完成事件
  • socket 能够继续被 write() 事件

……这基本上就是在组装一个小型 OS 了。更不用说,事件通知机制在 OS 里一般也没有完整的支持,比如在 Unix 中就没有文件系统操作完成事件的通知机制。Syscall 也并不总是能完全不进行阻塞等待,比如 open()stat() 等。

最后,非阻塞式 Syscall 还很难实现。例如可以看下 sys_read() 的大致实现:

1
2
3
4
5
6
7
8
9
10
11
sys_read(fd, user_buffer, n) {
// read the file's i-node from disk
struct inode *i = alloc_inode();
start_disk(..., i);
wait_for_disk(i);
// the i-node tells us where the data are; read it
struct buf *b = alloc_buf(i->...);
start_disk(..., b);
wait_for_disk(b);
copy_to_user(b, user_buffer);
}

这个函数分为两步,先获取 inode,再写入 buffer,期间都需要 wait_for_disk(),使得程序在内核中被挂起。这种情况下,非阻塞式的 Syscall 此时需要从内核中返回防止阻塞,但这样内核就无从知晓 sys_read() 刚才执行到哪里了,sys_read() 也没法继续执行下去了。

因此,如果要使用用户线程,我们要么只能使用一个支持不那么完整的实现,要么就是重写底层的 Syscall 使得一个 Syscall 内部执行一个非阻塞的过程。这会导致一个 open() 的系统调用可能会被拆成几十个小系统调用,比如通过 lookup_one_path_component() 查找一层目录。毫无疑问,这会导致代码极其繁琐。

总的来说,可能只有对性能有苛刻要求的情况下才会使用用户线程,以节省掉用户态 / 内核态切换的开销。

NFS

这里主要讨论 NFS v2。

设计目标

  • 应当能够用于现存的应用,即提供与 Unix 文件系统相同的语义
  • 应当能够简单地部署
  • 应当支持多种平台
  • 应当足够高效,但不需要和 Unix 本地文件系统一样高效

远程文件与目录的命名

NFS Client 使用 mounter 将远程目录挂载到本地目录。mounter 向指定的 NFS Server 发送 RPC 请求并获得一个 32 字节的 file handle 用于后续请求,可以将 file handle 理解为 inode。对 NFS Server 而言,file handle 实际上由 fs identifier、inode number 和 generation number 三部分组成。

为什么 NFS 不直接用常规的文件路径来标识文件呢?当然是为了处理数据一致性的问题。假设一个 Client 打开了 dir1 下的文件正准备读取,此时另一个 Client 却重命名了这个目录为 dir2,那么根据 Unix 规范最终读取的路径是 dir2/xxx 。如果 NFS 直接用文件路径标识文件,就无法与 Unix 文件系统的行为保持一致,这也是 file handle 中引入 inode 的原因。

那么 generation number 又有什么用?假设一个 Client 打开了一个文件正准备读区,此时另一个 Client 却删除了这个文件,创建了新的同名文件,那么根据 Unix 规范最终读取的是旧文件的内容。如果 NFS 恰好将旧文件的 inode 分配给新创建的文件,就会导致读到的是新文件的内容。generation number 则会在重用 inode 时 +1,确保读到的是原来的旧文件。解决了重用 inode 的风险,NFS Server 就能立刻回收 inode。

即使 Client 打开文件获得 file handle 后 Server 宕机,这个 file handle 在 Server 恢复后依然有效。

RPC

以读文件为例:

sequenceDiagram
    participant A as Application
    participant C as Client
    participant S as Server
    A->>C: OPEN("f",0)
    C->>S: LOOKUP(dirfh,"f")
    S->>S: Look up "f" in directory dirfh
    S->>C: fh and file attributes
    C->>A: fd
    A->>C: READ(fd,buf,n)
    C->>S: READ(fh,0,n)
    S->>S: Read from fh
    S->>C: Data and file attributes
    C->>A: Data
    A->>C: CLOSE(fd)

图中的 fh 指 file handler,并且默认 Application 之前已经获得了目录的 file handler 即 dirfh

从图中可以看到,Server 并不需要维护任何客户端状态,每次 RPC 请求中带着读文件所需要的全部信息,也就是说 Server 是一个无状态服务。无状态服务的好处在于:

  • 对 Server 来说,从故障中恢复并不需要做任何额外的事,就好像故障从来没发生过一样
  • 对 Client 来说,如果请求没有得到响应,只要不断重试即可

重试导致的结果是,同一个请求可能被 Server 执行多次,如果是类似删除文件等请求,就会出现奇怪的结果。后来,NFS 通过让 Server 维护一个 transaction ID 和 reply cache 来避免这一问题,不过 reply cache 就会在重启后失效了。换而言之,如果 Client 在 Server 正常时删除了文件,Server 重启后再次删除,依然会得到“文件不存在”的错误,但这种情况已经是小概率事件了。

如果使用一种更健全的方案,就需要持久化到磁盘上这会带来很大的开销和实现复杂度。NFS 选择不这么做,就是为了确保系统的内部实现足够简单,同时保持了无状态的特性。这种为了实现简单而有意牺牲一小部分正确性、一致性和完备性的做法正是 Worse is Better 的设计思想。

扩展 Unix 文件系统

为了更无缝地适配到 Unix 文件系统,NFS 引入了 vnode 的概念,这实际上是对 inode 的一层抽象,使得 vnode 既可标识本地文件,又可标识远程文件。同时,vnode 还可以标识同一台机器上几种不同文件系统中的文件。

vnode 提供的接口使得开发者无需关心操作的文件来自哪里,许多现有程序代码也更容易迁移。

例如,当应用程序调用 open 系统调用时,会通过 File syscall layer->Vnode layer->Client->Server->Vnode layer->File system 的路径一步步 LOOKUP 并最终打开文件。

Client 也会对最近使用的 vnode 进行缓存以减少 RPC 请求。然而,多个 Client 缓存了同一个文件时,就会缓存一致性的问题。

缓存一致性

如果一个应用写了本地文件,文件的改动通常会写入缓存而不是立刻写入 Server。在这段时间里,另一个 Client 读取到的文件就是尚未更新的文件,引起缓存一致性问题。

NFS 提供了两种保证缓存一致性的方法:

  • close-to-open consistency
    • 如果先 CLOSE OPEN,就能保证 READ 读到的数据一定是 WRITE 操作之后的
    • 如果在 CLOSEOPEN,则无法保证这一点,这也是缓存一致性和数据一致性的区别所在
  • read-write consistency:如果 OPEN 了同一文件,则 READ 读到的数据一定是 WRITE 操作之后的,显然这样更能保证一致性但开销更大

close-to-open consistency 的具体原理,是每次应用 OPEN 文件时,都会检查本地缓存中文件的修改时间和 GETATTR RPC 请求所获得的 vnode 修改时间,如果不一致,则删除缓存重新获取文件。而 WRITE 则只会写到本地缓存,直到 CLOSE 后改动才会写到 Server 中。

局限性

  • 安全性:NFS 并没有把安全性放在一个重要的地位,未授权访问、中间人攻击都是可行的
  • 可伸缩性:NFS Server 承受的流量压力较大,无法支持过多 NFS Client
  • 因为性能、丢包处理等原因,难以在大规模复杂网络中使用

为什么 NFS 安全措施极弱,但却没有受到严重的攻击?主要原因可能是 file handle 难以猜解。

RPC 透明性

设计目标

编写分布式系统代码时,尽可能减少对客户端和服务端的代码和行为上的改动,并使得开发者无需关心网络带来的问题。也就是说,RPC 希望能让分布式编程写起来就像在单点系统中一样,提供“透明性”。

抽象

首先面临的问题就是,在不同机器上对数据的表示不同,例如 32 位 / 64 位、小端法 / 大端法等等。因此,在数据传递时,必须使用一种和机器无关的数据表示方式,即 Interface Description Language。

IDL 所做的事不外乎两件:

  • 将不同编程语言原生的数据类型,序列化为机器无关的字节流以在网络上传递(反之同理)
  • 在客户端上使用 stub 将请求发送至服务端

例如,对于 Sun RPC 来说,IDL 就是 XDR,也是在 CW1 中使用的 IDL。首先在 proto.x 中编写 API 定义,随后 rpcgen proto.x 自动生成代码。

🌰 NFS

在 NFS 中,Client 本质上就是针对文件 syscall 的一个 RPC stub。此时,syscall 的参数、返回值都没有受到影响,提供了一定程度的透明性。

然而,这种透明性仅仅是形式上的。如果只有形式上的透明性而没有语义上的透明性,现有的代码尽管能够运行,却会产生错误的结果。所谓语义透明性,即同样的调用是否在 NFS 和 Unix 本地文件系统上表现一致。显然,NFS 没能提供这种语义透明性:

  • 在 Unix 上,只有文件不存在时 open() 才会失败;在 NFS 上,如果服务器宕机,open() 也会失败,甚至可能一直挂起
  • 在 Unix 上,close() 不可能失败;在 NFS 上,调用 close() 时会触发批量写操作(也就是含有隐性的 write() ),在 Server 空间不足时可能失败
  • 在 NFS 上,假如 Client 发送重命名请求,Server 完成了重命名但未能发送响应就宕机了,那么在 Server 恢复后 Client 的重传会得到“文件不存在”的响应,这在 Unix 上不可能发生
  • 在 Unix 上,如果 A 打开文件后该文件被 B 删除,A 依然能继续读文件;在 NFS 上,A 则无法再读该文件

第一个问题并不是 NFS 特有的,而是分布式系统均面临的问题;而后三个问题虽然可以修复以提升语义透明性,但都需要付出性能的代价。同理,提升性能也常常需要牺牲一部分一致性,例如上文提及的 close-to-open consistency,并不是什么时候都能提供足够强的一致性。

异常处理

RPC 需要处理类似服务端宕机、网络丢包等单点系统中不存在的异常,并采用 At-most-once 的执行策略。这是因为,如果响应丢包了,客户端会重传已经执行过的请求,此时如果操作具有幂等性则不会出问题,但如果是类似于充值 / 收费等请求,再次执行显然会带来大麻烦。因此,服务端可以维护 replay cache,使得收到重复请求时直接返回 cache 中的值,而不是再执行一次。

Ivy

RPC 对于提升透明性的尝试基本失败了,它显式的通信方式需要开发者小心地定义节点间的通信接口,没能提升太多透明性。我们转而思考,能不能使用一种隐式的通信方式来达到这一目的呢?分布式共享内存提供了这样一种可能性。

Ivy 创建了一种所有节点共享同一块内存的幻象,隐藏了在访问其他节点内存时底层的网络传输,从而实现隐式的通信。当然,既然用到网络,就要面临网络带来的性能、正确性、一致性等问题……

因为 Ivy 让分布式系统的节点“共享”同一内存,我们不妨将各节点具象为 CPU。首先需要解决的问题就是怎么把程序的不同部分交给不同 CPU 去执行,并确保正确性。

现代 CPU 并不会按指令顺序来逐条执行指令。所谓正确性,即执行结果看起来就像是指令逐条执行后产生的结果一样。

如果我们让每个 CPU 都持有一份全部共享内存的复制,那么读内存会非常快。然而,写内存则需要将写操作引入的改变传播到其他 CPU,而网络延迟在这里是不可忽视的。本地读和异地写的时间差,以及节点间网络延迟的差异,都会使得变量值的变化在时间上不一致,从而破坏正确性。因此,这种方案不可行,每个 CPU 必须持有共享内存的一部分而不是全部。

这就引出了如何划分内存给 CPU 的问题。容易想到,固定的划分方法无法顾及局部性,势必会效率低下。而动态的划分方法——比如 CPU 对某个页进行读写时将其移动到 CPU 上——不能处理多个 CPU 读同一个页的情况。

因此,我们可以考虑仅仅在写时移动页。而当 CPU 需要读异地内存时,只需要找到最后写该页的 CPU 并复制一份只读的拷贝。

机制简介 - 中心化 Manager

Ivy 就采用了类似的思想,用中心化的 Manager 管理页的分配,下面用例子阐释其中的机制。假设存在三个 CPU,其中第三个 CPU 同时还是 Manager。每个 CPU 维护自己的 page table,Manager 则额外维护一个 info table。

ptable lock access owner
CPU0
CPU1
CPU2
info lock copy_set owner
Manager

lock 列用来锁定表的编辑权限,access 可以为 R / W / nil 表示 CPU 对该页有读 / 读写 / 无权限,owner 则标志当前 CPU 是否为最后写该页的 CPU。最后,info 表中 copy_set 维护了该页的所有只读拷贝,owner 保存了最后写该页的 CPU 名称。

注意这里每个 CPU 的 ptable 和 Manager 的 info table 都被简化到了一行,即对应某一特定的页。

CPU1 读 CPU0 的页

假设初始状态如下,页为 CPU0 所拥有:

ptable lock access owner
CPU0 W
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {} CPU0

现在,CPU1 想要读取该页。于是它首先 lock 了自己 ptable 中对应的行,向 Manager 发送 read query。Manager 接收后,lock 自己 info 中对应的行,将 CPU1 加入 copy_set

ptable lock access owner
CPU0 W
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {CPU1} CPU0

随后,Manager 向 Owner 也就是 CPU0 发送 read forward。CPU0 接收后,lock ptable,将 access 改为 R

ptable lock access owner
CPU0 R
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {CPU1} CPU0

随后,CPU0 向 CPU1 发送 read data 后 unlock ptable。CPU1 接收后,向 Manager 发送 read confirm,并将 access 改为 R,最后 unlock ptable。Manager 收到后,也 unlock info。

ptable lock access owner
CPU0 R
CPU1 R
CPU2 nil
info lock copy_set owner
Manager {CPU1} CPU0

CPU2 写 CPU0 的页

书接上回,此时 CPU2 想写 CPU0 的页,那么它会 lock ptable,向 Manager 发送 write query。Manager 接收后,lock info,并向 copy_set 中的 CPU1 发送 invalidate,以撤销 CPU1 的读权限。CPU1 接收后,lock ptable 并将 access 改为 nil

ptable lock access owner
CPU0 R
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {CPU1} CPU0

随后,CPU1 向 Manager 发送 invalidate confirm 并 unlock ptable。Manager 接收后,从 copy_set 中移除 CPU1,向 Owner 即 CPU0 发送 write forward。

ptable lock access owner
CPU0 R
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {} CPU0

CPU0 接收后,lock ptable,将 access 设为 nil 并放弃 Owner 身份,最后向 CPU2 发送 write data。

ptable lock access owner
CPU0 nil
CPU1 nil
CPU2 nil
info lock copy_set owner
Manager {} CPU0

随后,CPU0 unlock ptable。CPU2 接收后,将 access 设为 W 并成为新的 Owner,最后向 Manager 发送 write confirm 并 unlock ptable。

ptable lock access owner
CPU0 nil
CPU1 nil
CPU2 W
info lock copy_set owner
Manager {} CPU0

Manager 接收后,将 owner 设为 CPU2,最后 unlock info。

ptable lock access owner
CPU0 nil
CPU1 nil
CPU2 W
info lock copy_set owner
Manager {} CPU2

可以注意到,ptable 的锁的存在本质上防止了并发写的发生,使得写操作必须是原子的。

我们也可以将 copy_set 移动至每个 CPU 上而不是放在 Manager 上,使得 confirm 类的消息不需要再被发送。此外,还可以使用分布式 Manager 进一步提升性能。

与 RPC 对比

相比 RPC,分布式共享内存的优点在于:

  • 提供了更强的透明性
  • 使得分布式系统编程更为容易

然而,RPC 同样具备分布式共享内存欠缺的优点:

  • 更好的隔离性
  • 对通信更可控
  • 对网络延迟容忍度更高
  • 更容易移植到不同平台

2PC

NFS 和 Ivy 都没有处理系统中节点故障的问题。在一些场景下(比如银行转帐),我们希望当参与的节点故障时,所有参与的节点要么都完成状态变更,要么都没有状态变更。比如,我们显然不希望发起转账的节点被扣除了余额,而收到转账的节点没有增加余额。

2PC(Two-Phase Commit)即两阶段提交,通过一种非常简单的思路来确保系统中的节点能达成共识。如果这种 all-or-nothing 的语义能够被正确执行,即要么全 commit 要么全 abort,那么就达成了 Safety 的目标;如果在没有故障的情况下能尽快全 commit,并在出现故障的情况下尽快决定是 commit 还是 abort,那么就达成了 Liveness 目标。显然,Safety 和 Liveness 两者之间需要权衡。

为此,我们需要引入交易协调者 TC。假设系统中只有两个节点 A 和 B,那么 TC 先向两者发送 prepare 消息。A 和 B 随后回复他们是否能够 commit。如果 TC 收到了两个 Yes,那么就会向两者发送 commit 消息;如果 TC 收到了至少一个 No,那么就会向两者发送 abort 消息。最后,A 和 B 根据 TC 的指令完成相应动作。

我们可以很容易看出,上述做法一定能保证 Safety。但是,如果:

  • 任意节点(TC / A / B)接收消息时超时了(宕机、丢包种种原因)
  • 任意节点重启了

我们都无法保证 Liveness 了,因为 TC 可能在能够 commit 的情况下选择了 abort。

超时的情况

为了处理超时的情况,确保 Safety 的前提下尽量保证 Liveness:

  1. 我们可以让 TC 等待 Yes / No 消息超时的时候选择 abort 来尽快作出决定,但此时依然有可能在能 commit 的情况下选择了 abort,过于保守。

  2. 我们可以让 A / B 等待 commit / abort 消息超时的时候自动选择 commit,但由于另一方可能回复了 No,这样很可能失去 Safety。

  3. 我们可以让 A / B 等待 commit / abort 消息超时的时候自动选择 abort。不失一般性,假如 B 之前回复了 No,那么超时自动 abort 不会出问题,也能保证 Liveness;但如果 B 之前回复了 Yes,那么 TC 就有可能收到两个 Yes,然后给 A 发送 commit,而给 B 发送的 commit 没有送达。此时 A 选择 commit 而 B 自动 abort 了,失去了 Safety!

至此,我们解决了问题的一半:B 如果之前回复了 No,那么只要超时自动 abort 就好了。

而如果 B 之前回复了 Yes,那么它可以向 A 发送 status 消息,询问 A 的状态:

  • 如果 A 没有回复,B 无法决定,只能继续永远等 TC 的消息;
  • 如果 A 收到了 commit / abort 并回复给了 B ,B 就做相同的决定;
  • 如果 A 还没有回复 Yes / No,两者都 abort(此时 TC 不可能决定全 commit);
  • 如果 A 没收到 commit / abort 但之前回复了 No,两者都 abort;
  • 如果 A 没收到 commit / abort 但之前回复了 Yes,B 同样无法决定,因为无法判断 TC 是不是收到了两者的 Yes 并决定 commit 了。

因此,我们发现即使采用了这样的终止协议并保证了 Safety,Liveness 依然无法保证,TC 宕机 / TC 的消息丢了的情况下,A / B 依然需要永远等待 TC。

重启的情况

重启的 TC 可能不知道自己发送过 commit,重启的 A / B 可能不知道自己发送过 Yes,结合丢包的可能性,这使得作出能保证 Safety 的决定也不那么容易了。

对于这类问题,分布式系统采用的一种通用方案就是借助持久化存储。TC 发送 commit 前先写一条记录到磁盘,A / B 在发送 Yes 前也先写一条记录到磁盘,就能使状态被保留下来。

因此,只需要:

  • TC 重启后,如果磁盘上没有 commit 消息,就 abort;
  • A / B 重启后,如果磁盘上没有 Yes 消息,就 abort;
  • A / B 重启后,如果磁盘上有 Yes 消息,就使用上述的终止协议作决定

FLP Result

分析了 2PC 协议之后,我们发现尽管它能保证 Safety,但却不能在所有情况下保证 Liveness。实际上,根据 FLP Result,异步消息传递式的分布式系统中,只要有一台机器存在宕机且不恢复的可能(crash-failure),就不存在确定性的共识算法,也就是说不可能同时保证 Safety 和 Liveness。

Paxos

称 Paxos 为分布式领域最重要的算法应该不会有太大争议。Paxos 实际上可以认为是 2PC 的升级版,因为两者都是为了解决共识问题,只不过 Paxos 通过更复杂的机制获得了更高的可用性。在之前介绍的案例中(NFS、Ivy、2PC)其实都没有将可用性纳入考量。

共识算法

需要注意的是,Paxos 是共识算法而不是一致性算法,尽管这两个概念很相似。共识指的是系统中的节点对某个 / 某些变量的值、或者是某个概念、某个行动能够达成共识,而一致性则指的是不同的分布式数据库节点上,存储的数据是否一致。

🌰 Primary 选举

假如有这样一个场景:我们要选择一个节点作为 primary,负责接收客户端请求并分发给其他 backup 节点。但是 primary 的引入同时也会引入单点故障问题,此时可能就需要选出一个新的 primary,这时就会极易产生多于一个 primary。在这个场景下,Paxos 要解决的问题就是:确保所有节点最终只会选出一个 primary。而对于其他不同场景,Paxos 解决的问题也可以不同。

一个很自然的想法是给每个节点预先编号,当前存活的节点中编号最小的当选。这就需要所有节点对“当前存活的节点集合”这个值达成共识。然而未必所有节点都能够正常地给出自己的反馈,因此只需要某个值被超过半数节点同意,我们就认为节点关于这个值达成了共识。

这实际上表明,Paxos 能成功执行必须要至少半数以上的节点存活。

共识协商

由于可能出现网络丢包和网络分区,单纯的互 ping 来确定哪些节点存活是行不通的。为此,Paxos 引入了 Leader 机制。当一个节点决定成为 Leader 后,它会向包括自身在内的所有节点广播一个 proposal,其中包含一个 proposal 序号 n 和相应的值 value(在这个例子里,是存活节点集合,下不赘述)。n 必须是全局唯一的,一般取目前存在的最大的 n 的值 + 1。

我们用 n_a表示节点之前已经 accept 过的 proposal 中最大的 n,然后用 v_a 表示对应 proposal 的 value。再用 n_h 记录节点所收到的 proposal 中最大的 n。当节点收到一个 proposal,并发现其序号 n 大于 n_h 时,就将 n_h 设为 n,并向 Leader 回复 (n_a, v_a)

Leader 收到了超过半数的这样的消息后,就可以查看其中是否有某个 v_a 非空。如果所有 v_a 都是空的,那么就自己选择一个值作为 value;否则,就选择 n_a 最大的那个消息中的 v_a 作为 value。随后,向这次回复过自己的节点广播 (n = 最大的 n_a, v = 选择的 value)

节点收到后,如果发现 n 大于等于 n_h,那就接收这个 proposal。所谓接收 proposal,就是设置 n_h = n_a = nv_a = v 来更新这几条记录,随后回复一条没有内容的消息。

Leader 收到超过半数的这样的消息后,就可以认为节点达成了共识,并向这次回复过自己的节点广播一条没有内容的消息,表示共识已达成。节点收到消息后,就知道最终达成的共识的值为 v_a。在选 primary 的例子里,v_a 集合里序号最小的节点就是公认的 primary 了。

那么,一个节点怎么决定自己要成为 Leader 呢?很简单,只要为每个节点设置一个随机的超时时间,一旦过了这个时间依然没有来自 Leader 的消息,节点就会自己成为 Leader。

Safety

Paxos 能保证 Safety 的关键在于:

  • 任何节点收到一个 n < n_h 的消息后,都会直接无视,这使得即使出现多个 Leader,节点最终也只会 accept 那个序号最大的 proposal(注意 n 是全局唯一的)
  • 任意两个“超过半数”的集合之间必定存在交集,这是由“超过半数”的定义得来的。这使得即使出现多个 Leader,并且都几乎获得了超过半数的支持,最终也会由这个交集中的节点(哪怕只有一个)决定要 accept 的 proposal
  • 新的 proposal 会沿用现存的 n_a 最大的 proposal 对应的 value,这使得不同 Leader 发起的处于不同阶段的 proposal,无法影响到最终达成共识的 value

Bayou

Bayou 是为了移动设备构建成的分布式系统设计的,而移动设备经常会遇到没有网络或者网络质量差的情况,这使得很多问题,比如数据一致性,看起来非常困难甚至不可解。Bayou 解决这些问题的手段主要是通过节点间通信,比如通过蓝牙之类的协议使得两部手机交换数据来达成一致性。这是因为 Bayou 主要想解决的问题就是严重网络分区情况下的数据读写可用性。

🌰 会议室预订系统

Bayou 使用了一个会议室预订系统来说明协议的运作原理和场景。最终,系统需要确保同一时间段同一会议室不会被两个用户预订。为此,需要一种自动解决冲突的机制,使得不同节点上的数据同步之后能像 git 那样 merge 掉冲突。为了实现这个机制,需要节点维护一个更新操作的有序列表,并确保节点收到的更新操作是一致的、以及确保节点会按相同的顺序逐个应用这些更新操作。这样一来,数据同步就只需要像归并排序那样,合并两个有序列表即可。

冲突合并

不过 Bayou 并不是仅仅用于会议室预订系统,而是一个通用的协议,因此需要考虑的问题是:什么才算冲突?这个问题的答案对于不同应用是不同的。同理,合并操作也是类似的。举个例子,对于会议室预订系统,假如我们想预订从下午一点半开始持续一小时的会议,我们会在写操作里添加这样的依赖检查和合并算法:

1
2
3
query = "SELECT key FROM Meetings WHERE day=12/18/95 AND start < 2:30pm AND end > 1:30pm"
expected_result = EMPTY
merge_proc = ......

随后,Bayou 就会检查 query 的结果是否等于 expected_result ,是的话可以直接更新,否则就需要调用 mergeproc 来合并冲突。需要注意的是,依赖检查和合并算法需要是确定性的。这样一来,由于每个服务器都会按照相同顺序解决冲突,每个服务器最终获得的结果也是相同的。

写操作

当一个写操作被接收时,它首先处于 tentative 状态,并且会根据其 timestamp 被排序;最终,写操作会变成 commited 状态,同样根据其被 commit 时的 timestamp 进行排序,并且必定排在 tentative 写操作的前面。这里 Bayou 使用了 Lamport Clock 来避免解决不同设备上的时钟同步问题。

一个让人不爽但又无可奈何的事情是,当 Bayou 服务器接收到新的写操作时,之前的写操作可能不得不被撤销,然后根据新的顺序重新执行。因为新的写操作的加入,旧的写操作甚至可能出现和之前不同的执行结果。当一个写操作最后一次被执行完毕,我们就称该操作已经是稳定的了。对于预订会议室的用户来说,了解自己的预订是否已经稳定显然十分重要。

判断稳定状态

那么,Bayou 服务器如何确定一个写操作是否已经稳定了呢?一种办法是用 Lamport Clock 里的 timestamp,如果一个写操作的 timestamp 已经小于任何服务器收到的新的写操作的 timstamp,那说明在这个写操作之前已经没有其他写操作了,所以一定是稳定的。但是,如果一个服务器长期断线,那么它上线的时候就会导致大量写操作重新执行。

Bayou 采用的方法是 primary commit 方法。因为 commited 排在 tentative 前面,我们可以说一个写操作被 commit 之后,只要节点已经获得了之前所有 commited 的写操作(必然成立,这是由 Bayou 按顺序传播写操作的机制决定的),那么这次就是已经是稳定的了。primary commit 即选择一个服务器作为 primary,由它来执行 commit 的操作,并将数据同步给其他服务器。这样做的好处有:

  • 即使 primary 出现单点故障,影响的也只是 commit,而不是正常的读写操作。
  • 即使某些节点长期断线,也不影响 commit,因为只有 primary 能 commit。
  • 节点接收到来自 primary 的数据同步后,就不再需要最新 commit 之前的任何记录了,因为那些记录都不可能再改变了。

最后,必须注意的是,primary 在决定 commit 顺序的时候,对于来自同一节点的若干次写操作,其顺序必须被保留。如果在某个节点上先执行了 create,然后执行 modify,那么让 modify 在 create 前面 commit 是毫无意义的。

可以看到,Bayou 的问题主要在于实现依赖检查和合并算法,很大程度上增加了开发 / 使用一个应用的复杂度,也并不是对所有应用都适合用这种办法。

GFS

GFS 是谷歌设计的分布式存储系统,其设计基于如下前提:

  1. 系统组件失效是常态,而非异常情况
  2. 从传统标准来看,需要存储的文件十分巨大,往往是 GB 级和 TB 级的
  3. 相比覆盖文件中已有的内容,在文件后追加内容更为频繁
  4. 协同设计应用程序和文件系统的 API 能提高灵活性

同时,也要考虑到所需要的文件系统的行为模式:

  • 由于容易出现组件失效,因此需要迅速地自动检测、容忍和恢复故障
  • 主要存储大文件,如大于 100 M 的
  • 读操作往往是大规模的流式读取,如大于 1 M 的;一般不会重复读取,即 Read once
  • 写操作往往是大规模的顺序写入,而且是追加写入;一般不会重复写入,即 Write once
  • 需要原子的并行追加写入机制,避免引入锁等开销较大的同步机制

架构

一个 GFS 集群中只有一个 Master 节点(可能包含多个 Master 服务器),这种中心化的方式正是为了简化整个系统的管理。Master 节点上只有文件的元数据,而多个 Chunkserver 上则是文件实际存储的地方。

文件被分割为 64 M 的 Chunk,每个 Chunk 被 Master 分配一个 64 位的 ID。Master 节点上的元数据包括:

  • Namespace
  • 针对文件的访问控制信息
  • 文件到 Chunk 的映射
  • Chunk 当前所处的 Chunkserver

值得一提的是,这些元数据都保存在 Master 的内存中,又快又简单。此外,Master 节点还负责管理 Chunk 租用、垃圾回收、Chunk 迁移等等,并通过心跳信息确认 Chunkserver 状态。

Chunk 一般会在若干个 Chunkserver 上保存一份冗余,默认是 3 个。保存的方式就是放在 Linux 文件系统里。然而,GFS 并没有像 NFS 一样尽量模仿 Unix 文件系统 API,而是自己实现了 create、delete、open、close、read、write 等常用操作。此外,还有 snapshot 和 record append 两个特有的操作,分别用于文件备份和对文件并行追加写入。

record append 和常规追加写入的主要区别在于,它遵循 at least once 语义,并且追加的位置未必是文件尾部,而是由 GFS 计算决定。

由于利用了 Linux 文件系统,Chunkserver 上不需要缓存机制;而由于流式的读取模式,GFS 客户端也不需要本地缓存文件,只需要缓存元数据即可。这使得缓存一致性不再是问题。

读操作

图 1|读操作流程

  1. 客户端向 Master 发送 read 请求,包含文件名和 Chunk index
  2. Master 回复元数据:Chunk ID、Chunk 版本号以及副本所处的位置
  3. 客户端向最近的副本所处的 Chunkserver 发送 read 请求,包含 Chunk ID 和读取的字节范围
  4. Chunkserver 回复实际的文件数据

可以看到,客户端和 Master 之间只有控制信息的交互,而实际的数据交互仅仅发生在客户端和 Chunkserver 之间。

写操作

图 2|写操作流程

对于每个 Chunk 来说,某个存放了该 Chunk 副本的 Chunkserver 会成为 primary(其余均为 secondary),由 Master 向 primary 提供 60s 的租约(并更新 Chunk 版本号)。租约通过心跳信息延续,也可以被 Master 主动取消。

  1. 客户端首先向 Master 询问 primary 和 secondary 的位置
  2. Master 回复 primary 和 secondary 所处的位置
  3. 客户端向最近的副本所处的 Chunkserver(可能是 primary 或 secondary)发送要写入的数据,数据通过 daisy chain 的方式在 Chunkserver 间传递
  4. 当所有副本都确认接收到了数据后,客户端向 primary 发送 write 请求
  5. primary 给该请求分配一个序号(用于在本地对写操作顺序进行排序),并通知所有 secondary 执行该 write 请求
  6. secondary 执行后向 primary 回复执行结果
  7. primary 向客户端回复执行结果

所谓 daisy chain,即数据在不同 Chunkserver 之间类似流水线一样一一传递的方式。这种方式不仅利用了现代网线全双工的特性,更重要的是可以配合流式传输,在尚未完全接收到全部数据时就开始向下传递数据,提高传输速率。

record append 操作

record append 操作的流程和写操作基本一致,在 primary 的逻辑上略有区别。在上述第 4 步中,primary 接收到来自客户端的请求后,会检查这次 record append 操作是否会导致 Chunk 超出最大尺寸 64 M。

  • 大多数情况下不会超过,因此 primary 把数据追加到自己的副本内,通知 secondary 也这么做,然后通知客户端执行结果
  • 而如果超过了,那么 primary 会将当前 Chunk 先填满,通知 secondary 也这么做,然后通知客户端重新发送 record append 请求。这样,当客户端第二次发送请求时,就不会再出现超出最大尺寸的情况了

那么,如果一部分 secondary 在追加写入时成功了,另一部分失败了呢?毫无疑问,这会使得 primary 通知客户端执行失败了,从而让客户端再次发送 record append 请求。此时就可能会出现一种现象,即有些副本上该数据已经被写入了多次,而在有些副本上则只写入了一次。这看起来很混乱,但实际上就是 at least once 的语义。

一致性模型

首先可以肯定的是,元数据的变更是原子的,毕竟只有一个 Master 节点。由于 Master 会维护元数据变更的日志并同步到远程服务器,即使 Master 重启之后依然可以重放日志来恢复元数据,从而恢复整个文件系统。

但对于数据变更而言就要复杂很多。GFS 定义了两个一致性指标:

  • consistent 意味着,一个文件区域上的内容对任何客户端而言都是相同的,无论它们是从哪个副本中读取的
  • defined 意味着,在写操作或 record append 操作后,一个文件区域不仅是 consistent 的,而且任何客户端都能看到对其的所有修改操作

根据这两个指标,我们可以得到:

Write Record Append
串行修改成功 defined defined interspersed with inconsistent
并行修改成功 consistent, undefined defined interspersed with inconsistent
修改失败 inconsistent Inconsistent

对于成功的并行写操作,尽管 GFS 可以保证文件区域内容一致,但由于 primary 对并行操作的排序未必和实际发起操作的顺序一致,客户端未必能看到一致的修改操作记录,因此 defined 是无法保证的。因此 GFS 设计者不建议使用 concurrent write。

而对于成功的串行或并行 record append 操作,GFS 能通过 at least once 语义和 primary 对操作的排序保证存在 defined 区域,但 defined 区域之间可能会存在 inconsistent 的区域。这其实就是上文 record append 操作流程中介绍的部分副本上写入失败引起的混乱结果导致的。

这种语义看起来相当奇怪,因此应用程序在编写时也需要针对这种语义进行特殊处理。

应用程序

在执行 record append 时,应用程序需要包含一个 checksum。这样在读取数据时,就可以比较容易地分辨哪些数据是填充数据、哪些数据是有效数据。而如果应用程序不能容忍重复读取到同一份数据,就需要在 record append 时包含一个 unique ID 来辅助去重。

组件失效

如果 Master 失效,那么如上文所述,它会在重启时重放日志来恢复 Namespace 信息以及文件到 Chunk 的映射信息。随后,它询问 Chunkserver 其持有的 Chunk,从而恢复 Chunk ID 到 Chunkserver 的映射信息。这一映射信息是通过询问 Chunkserver 恢复的,因为它本来就没必要存在 Master 上。

根据版本号不同,Chunkserver 上可能会存在更旧或更新的 Chunk 副本。更旧的副本会被认为是过期的,会被忽略,且会在垃圾回收时被移除;更新的副本则会使得 Master 也采用该副本的版本号。

而如果 Chunkserver 失效,Master 因为收不到心跳信息会发现这一点并减少对应的副本数量。随后,Master 在后台重新复制缺少的这些副本,缺少的越多优先级越高。

文件删除

当客户端删除文件时,Master 记录删除日志并将文件重命名为“文件名-删除时间戳”的形式,从而避免向多个副本发起多个删除请求,影响性能。同时,Master 在后台扫描文件 Namespace,当扫描到已经被删除超过 3 天的文件时才会真正执行删除操作,并删除对应的元数据。同理,Master 也会扫描 Chunk 的 Namespace,并通知 Chunkserver 删除未被引用的 Chunk。

Receive Livelock

影响性能的因素有很多。硬件常常能决定性能的上限,而不当的软件层面的设计却无法使硬件充分发挥其性能。相反,良好的设计则能使性能尽可能逼近这一上限。

这里讨论的 Receive Livelock,就是在中断驱动的系统中,当过量的请求到达时,系统忙于通过中断处理请求,而无法执行真正有用的其他操作。和 Deadlock 相反,系统并没有卡死在一个状态上,但两者的效果是相同的。

轮询与中断

在介绍 Receive Livelock 的例子前,我们需要先了解一些背景知识。当 IO 设备完成一些工作时、或是发生一些事件时,需要通知 CPU:比如收到网络包、完成磁盘读取、收到键盘输入等等。这种“通知”通常是通过两种方式实现:

  • 轮询:CPU 每隔一段时间就询问 IO 设备是否有事件发生,这是一种同步的方式
  • 中断:发生事件时,IO 设备向 CPU 发送信号,这是一种异步的方式

乍一看,似乎显然是后者效率更高,然而实际上未必如此。要判断需要使用哪种方式,我们需要考虑两点:处理事件的延迟时间和 CPU 的负载。

对于轮询来说,要降低处理延迟,就需要提高轮询频率,但这会增加 CPU 负载。因此,使用轮询的场景,是处理那些经常发生、并对处理延迟要求较高的事件。注意这里的“经常”采用的是 CPU 的时间尺度,也就是微秒至毫秒级的。

而中断相反,适合处理发生不频繁、且处理延迟要求不高的事件。中断发生时,如果中断优先级 IPL 高于 CPU 优先级,那么 CPU 会保存当前运行程序的上下文、跳转到内核中的中断处理程序 ISR 对中断进行处理、最后恢复运行程序的上下文并继续。可以发现,中断带来的潜在问题就是对其他系统任务的抢占,也就是引起 Receive Livelock 的根因。

我们知道,磁盘 IO 必定是由 CPU 自己发起的,因此磁盘 IO 导致的中断频率实际上是 CPU 可控的,然而网络 IO 则没有这一限制。而且,许多应用使用的多媒体传输协议或是 RPC 协议往往基于 UDP 等没有流量控制的协议以提高实时性,这使得网络负载能够达到极高的水平,进而导致系统将全部时间花费在通过中断接收网络包上,导致 Receive Livelock。

网络 IO 机制

我们设计网络 IO 系统时,想要达到的目标主要有:

  • 低延迟,即尽可能快地处理 IO 事件
  • 低抖动,即延迟的变化幅度较小
  • 公平性,即不同任务都能得到执行,不会出现饥饿的情况
  • 高吞吐量,如收发网络包的吞吐量

而一个网络 IO 系统需要完成的任务则可以分为这几类:

  • 接收网络包
  • 传输网络包
  • 处理协议数据(通常在内核中执行)
  • 处理其他 IO 事件
  • 应用层面的事件处理

由于任务种类和预期目标都比较复杂,我们需要先了解传统中断驱动系统中的网络 IO 机制。

当一个网络包到达网卡时,会产生一个高 IPL 的中断。对应的 ISR 查看以太网包头后就放入 input queue 并返回。这是因为高 IPL 的中断不能花费太多时间,否则会影响其他正常任务的运行。之后,一个较低 IPL 的软件中断会从 input queue 中读取数据包并处理 IP / TCP / UDP 包头,再将数据包放入 socket buffer 供目标应用程序使用。而目标应用程序运行在用户态,通过 read() 系统调用读取数据包,因此拥有更低的 IPL。

图 3|网络 IO 机制

而发送数据包时,大致就是相反的流程,只不过 input queue 变成了 output queue,而 传输包的 IPL 是略低于接收包的 IPL 的。可以看到,这种设计将接收数据包放在最优先的位置,这是因为早期网卡缓冲区较小,如果不尽快接收数据包,缓冲区满后就会丢弃后续到达的数据包。

如今已经不存在网卡缓冲区较小的问题了,但这种设计导致诸多问题依然存在,例如:

  • 当网络包到达速率超过“最大无丢包接收速率”时,本应保持不变的网络包发送速率会逐步下降至 0
  • 系统浪费 CPU 去接收大量数据包放入队列,而队列中许多来不及被处理的包最终都会被丢弃
  • 大量网络包在极短时间内到达时,只有接收完全部包之后才能将第一个包发送给用户态的应用程序
  • 由于发送的 IPL 小于接收,发送包的操作会饥饿

避免 Receive Livelock

为了避免 Receive Livelock,首先很容易想到的办法就是限流,不是限制数据包到达的流量,而是限制中断触发的“流量”。只要在接收包的 ISR 里:

  • 设置标志位,表示该网卡收到了一个或多个数据包
  • 调度内核线程,用轮询网卡的方式接收数据包
  • 不重新打开接收数据包的中断开关

这样一来,后续接收数据包都不会采用中断的方式,而是通过轮询来接收包,因为在高频 IO 的情况下轮询的表现更优。类似地,我们不仅仅可以根据系统中的各项指标动态控制接收数据包的中断开关,也可以动态控制多个其他中断的开关来让渡 CPU 给用户态程序,例如在 socket buffer 接近满时。

那么内核线程是怎么轮询网卡的呢?当内核线程被调度时,它会检查哪些网卡上设置了“收到数据包”的标志位,对这些网卡上的数据包,它会一直处理 IP / TCP / UDP 包头直到将这些包放入 output queue 或是 socket buffer。对于每次调度,内核线程中设置了一个 quota 来限制单次调度中在一个网卡上最多能处理多少数据包,以保证公平性。同时,内核线程不仅采用 round-robin 的方式轮询网卡,也用同样的方式轮询接收操作与发送操作,避免饥饿现象。最后,只有一个网卡上没有待处理的包时,该网卡的接收数据包的中断开关才会被打开。

采用这种方式,当过量流量到达时,即使要丢弃数据包也不再需要中断、不再需要 CPU 参与了,而是直接在网卡处就被丢弃。

Kerberos

在讲 Kerberos 之前先讲了一些信息安全相关的基础知识,没有什么记录的必要。Kerberos 是 MIT 研发的一种开放环境下的认证协议,最初认识这个协议还是在 Windows 的域里。

这里介绍的 Kerberos 版本是原始论文中的版本。

基础概念

在 Kerberos 中,一个要使用服务的用户通过客户端向服务器发起请求,由服务器提供服务并完成对应的作业。一个要使用 Kerberos 服务的实体被称为 principal,可以是一个用户或者一个服务器。

每个 principal 都有自己的对称密钥,只有 principal 自己和 Kerberos 系统本身知道。如果 principal 是一个用户,那么这个密钥一般就是该用户密码的哈希。

最后,所谓“开放环境”,即网络中的机器并不是由某个组织控制,而是用户自己能够完全控制的(用户拥有机器的管理员权限),并且用户还可能能够访问多台机器。这种情况下,不仅需要认证机器、还需要认证用户本身。

架构

Kerberos 协议依赖于中心化的 Kerberos 数据库,里面存放了 principal 和对应的密钥。Kerberos 数据库一般由一个 Master 和多个只读的拷贝 Slave 构成。每隔一段时间,Master 数据会更新到 Slave 上。

KDBM 系统可以读写这个数据库,必须和 Master 运行在同一机器上;Kerberos 系统只负责认证,所以只有数据库读权限,可以运行在任意拥有 Slave 的机器上。

无论是服务本身还是使用服务的 principal,都需要在 Kerberos 系统中注册并协商一个密钥。Kerberos 系统还会生成临时的 session key,用于加密某次服务请求过程中的通讯。

Kerberos 采用当时依然安全的 DES-CBC 加密,如今 DES 已经不再安全了。好在加密模块是独立的,可以轻松被 AES 之类的加密算法替换。

主体名称

每个主体在认证时都有自己的名称,格式形如:$p rimaryName.$instance@$realm,例如 rlogin.priam@ATHENA.MIT.EDU

primaryName 是用户或服务的名称,instance 一般表示该用户在哪台服务器上操作、或是该服务在哪台服务器上运行。realm 则表示维护认证信息的管理实体,比如一个组织、一个部门等。

原理

用户请求服务的过程可以分为两步:

  1. 请求一个用于请求其他服务的 credential
  2. 用这个 credential 请求对应的服务

credential 又分为 ticket 和 authenticator。ticket 用于传递关于用户的认证信息,而authenticator 用于传递关于用户所处客户端的认证信息。一个 ticket 通常长这样:

$$
\{s,c,addr,timestamp,ttl,K_{s,c}\}K_s
$$

符号 含义
s 服务器(的名称)
c 客户端(的名称)
addr 客户端 IP 地址
timestamp 时间戳
ttl ticket 有效时长
$K_{s,c}$ s 和 c 的 session key
$K_s$ s 的密钥
$\{abc\}K$ 用 $K$ 加密 $abc$ 得到的密文

ticket 颁发后能被用多次,但 authenticator 只能用一次;ticket 由服务器生成,而 authenticator 由客户端生成。一个 authenticator 通常长这样:
$$
\{c,addr,timestamp\}K_{s,c}
$$

获取 TGS ticket

最初,用户只能通过密码来证明身份。因此用户首先要输入用户名,此时客户端向 Kerberos 系统发送:
$$
c,tgs
$$

符号 含义
tgs ticket-granting 服务器(的名称)

表示想要使用 ticket-granting 服务器上的服务。Kerberos 系统检查 c 后生成 c 和 tgs 的 session key。随后回复:
$$
\{\ K_{c,tgs},\{T_{c,tgs}\}K_{tgs}\ \}K_c
$$

符号 含义
$T_{c,tgs}$ c 使用 tgs 服务的 ticket

用户收到后,输入密码。此时密码被转化为密钥并解密这个消息。这样,用户就可以访问 tgs 了。

获取服务 ticket

如果用户还没有获取过这个服务的 ticket 或者 ticket 已经过期了,那么就需要从 tgs 那里获取服务 ticket。客户端向 tgs 发送:
$$
s,\{T_{c,tgs}\}K_{tgs},\{A_c\}K_{c,tgs}
$$

符号 含义
$A_c$ c 的 authenticator

tgs 随后解密并检查 ticket 和 authenticator,并生成 c 和 s 的 session key。随后回复:
$$
\{\ \{T_{c,s}\}K_s,K_{c,s}\ \}K_{c,tgs}
$$
用户收到后,不需要再次输入密码就可以自动使用 $K_{c,tgs}$ 解密消息,获得 c 使用 s 服务的 ticket。这样,用户就可以访问 s 了。

访问服务

客户端向 s 发送:
$$
\{A_c\}K_{c,s},\{T_{c,s}\}K_s
$$
s 随后解密并检查 ticket 和 authenticator,如果合法则认证成功,开始提供服务。为了防止重放攻击,服务器会丢弃 timestamp 来自未来的、或者和已接收 timestamp 重复的那些请求。

最后,如果客户端也需要服务器证明身份,s 只需要回复:
$$
\{timestamp+1\}K_{c,s}
$$
图 4|Kerberos 认证过程

局限性

  • 要求系统中所有系统时钟同步
  • 中心化存储敏感信息,容易单点故障
  • 难以更改密码、升级密钥数据库
  • authenticator 默认 5 分钟后过期,依然存在重放攻击可能
  • ticket 过期机制导致无法长时间运行后台任务

TAOS

TAOS 的论文中提供了一种基于公钥密码体制和证书的分布式认证协议,以及对应的形式化的理论基础。

符号

  • $A\ says\ S$:表示主体 $A$ 支持声明 $S$
  • $A\Rightarrow B$ 或 $A\ speaks\ for\ B$:表示主体 $A$ 发布的任意声明都可以认为是 $B$ 发布的
  • 也就是说,如果 $A\Rightarrow B$ 且 $A\ says\ S$,那么 $B\ says\ S$

这里的主体包括:

  • 简单主体:如用户和机器等。
  • 信道:指网络地址和加密密钥。如果声明 $S$ 出现在了信道 $C$ 上,那么 $C\ says\ S$;如果用 $K$ 签名一张包含 $S$ 的证书,那么 $K\ says\ S$。需要注意,只有信道可以直接发布一个声明,因为声明只能出现在信道上。
  • 组:一组主体。如果 $A$ 在组 $G$ 中,那么 $A\Rightarrow G$。
  • 代表某一角色的主体:例如 $Bob$ 以 $Admin$ 的身份执行操作时,我们说 $Bob\ as\ Admin$。此时 $Bob\Rightarrow (Bob\ as\ Admin)$。
  • 主体的逻辑与。
  • 引用某一主体的主体:我们用 $B|A$ 表示 $B$ 引用了 $A$,即 $B\ says\ A\ says\ S$ 等于 $(B|A)\ says\ S$。
  • 代表某一主体的主体:我们用 $B\ for\ A$ 表示 $B$ 代表了 $A$,这比 $B|A$ 更强,因为此时 $B$ 已经获得了 $A$ 的授权。

公理

  1. handoff 公理:如果 $A\ says\ (B\Rightarrow A)$,那么 $B\Rightarrow A$。
  2. delegation 公理:如果 $A\ says\ ((B|A)\Rightarrow (B\ for\ A))$,那么 $(B|A)\Rightarrow (B\ for\ A)$。

注意到 delegation 和 handoff 看起来差不多,但重要的是在 delegation 中额外记录了被授权的主体 $B$。如果 $B$ 发布的声明出现了问题,这一特性结合日志审计使得我们不必再向很可能是无辜的 $A$ 追责,而是直接向 $B$ 追责。

🌰 认证复合主体

一台机器 $Vax4$ 运行了操作系统 $OS$,两者形成了一个节点 $WS$。用户 $Bob$ 登陆了 $WS$,现在需要向远程文件服务器 $FS$ 发送认证请求。为此,$Vax4$ 必须有自己的密钥对,不妨令其公钥为 $K_{vax4}$,私钥为 $K_{vax4}^{-1}$,其中私钥仅仅对 $Vax4$ 的启动固件可见,对 $OS$ 是不可见的。

$Vax4$ 启动时,用私钥签名一个启动证书,将权限移交给新生成的节点公钥 $K_{ws}$。这个证书可以表示为:
$$
(K_{vax4}\ as\ OS)\ says\ (K_{ws}\Rightarrow(K_{vax4}\ as\ OS))\tag{1}
$$
因此,启动后 $WS$ 获得了启动证书、节点私钥 $K_{ws}^{-1}$,但无法知道 $K_{vax4}^{-1}$。

登陆操作可以看作一种特殊的 delegation。$Bob$ 登陆时,用自己的私钥 $K_{bob}^{-1}$ 签名一个 delegation 证书,将权限委托给 $WS$:
$$
K_{bob}\ says\ ((K_{ws}|K_{bob})\Rightarrow(K_{ws}\ for\ K_{bob}))\tag{2}
$$
现在,需要向 $FS$ 发送请求。首先需要一个发送请求的信道 $C_{bob}$,以及请求本身 $RQ$。发送请求可以写作:
$$
C_{bob}\ says\ RQ\tag{3}
$$
并且,$WS$ 需要签名一个信道证书,将权限移交给信道:
$$
(K_{ws}|K_{bob})\ says\ (C_{bob}\Rightarrow(K_{ws}|K_{bob}))\tag{4}
$$
结合 (4) 和 (2),使用 delegation,$FS$ 可以推出:
$$
(K_{ws}\ for\ K_{bob})\ says\ (C_{bob}\Rightarrow(K_{ws}\ for\ K_{bob}))\tag{5}
$$
结合 (5) 和 (3),使用 handoff,$FS$ 可以推出:
$$
(K_{ws}\ for\ K_{bob})\ says\ RQ\tag{6}
$$
结合 (6) 和 (1),使用 handoff,$FS$ 可以推出:
$$
((K_{vax4}\ as\ OS)\ for\ K_{bob})\ says\ RQ\tag{7}
$$
最后,$FS$ 还需要证明 $K_{vax4}$ 和 $K_{bob}$ 确实代表了 $Vax4$ 和 $Bob$。为此,必须引入受信任的第三方机构 $CA$,也就是说相信 $K_{ca}\Rightarrow$ 任意的主体。因此,$FS$ 可以使用如下证书:
$$
K_{ca}\ says\ (K_{vax4}\Rightarrow Vax4)\\
K_{ca}\ says\ (K_{bob}\Rightarrow Bob)
$$
结合 (7),使用 handoff,最终得到:
$$
((Vax4\ as\ OS)\ for\ Bob)\ says\ RQ
$$
其语义是:$FS$ 得知运行着 $OS$ 的机器 $Vax4$ 代表用户 $Bob$ 发送了请求 $RQ$。

星罗棋布:《分布式系统与安全》课程笔记

https://signormercurio.me/post/DistributedSystems/

Author

Mercury

Posted on

2021-10-18

Licensed under

CC BY-NC-SA 4.0

Comments