2022秋学期 高级操作系统的期末整理-精简版

封面

134A2E93CA5B322CD6AECF9E157C0347

C0 引言

本文内容来自于对高级操作系统课程资料的整理；

本文所涉及的课程指东北某沿海高校，计算机学院硕士生必修课“高级操作系统”，课程资料包括课程PPT、教材《分布式系统原理与范型 第二版》1、《Distributed Systems Principles and Paradigms 2nd edition》2，以及网络资料。

1. 《分布式系统原理与范型 第二版》 作者: （美）特尼博姆 出版社: 清华大学出版社 原作名: Distributed Systems: Principles and Paradigms 译者: 辛春生 :出版年: 2008-6-1 页数: 490 ISBN: 978730217279 ↩
2. 《Distributed Systems Principles and Paradigms 2nd edition》:作者: Tanenbaum, Andrew S. / Steen, Maarten van 出版社: Pearson 出版年: 2001-9-1 页数: 803 ISBN: 9780131217867 ↩

C1 分布式系统概述

什么是分布式系统

定义：分布式系统是若干独立计算机的集合，它们对于用户来说就像一个系统

分布式系统中透明性的种类

透明性 描述
访问 隐藏数据表示形式以及访问方式的不同
位置 隐藏数据所在的位置
迁移 隐藏资源是否已移动到另一个位置
重定位 隐藏资源是否在使用中已移动到另一个位置
复制 隐藏资源是否已被复制
并发 隐藏资源是否由若干相互竞争的用户共享
故障 隐藏资源的故障和恢复
持久性 隐藏资源（软件）位于内存里或磁盘上

透明度：透明性受到的限制 必须将透明性与其他因素（如性能）结合起来考虑（如复制透明性中的复制更新）

分布式系统中的扩展技术有哪些

  1. 隐藏通信等待时间

    • 异步通信

    • 减少通信量

      image-20230214154410735
      a 由服务器检查表单； b 由客户端检查表单

  2. 分布技术：分割组件，分散到系统中，如DNS和WWW

    image-20230214154453523

    将DNS名字空间划分为区的例子

  3. 复制技术：多拷贝

    复制：增加可用性，有助于负载均衡

    缓存：在访问资源的客户周围制作资源备份

    一致性问题

C2 体系结构

客户端-服务器模型

集中式

  • 服务器：实现某个特定服务的进程
  • 客户：向服务器请求服务的进程
  • 客户端-服务器之间的一般交互：请求/回复
  • 无连接的协议：高效，受传输故障的影响，适合局域网
  • 基于连接的协议：性能相对较低，适合广域网

image-20230204223917125

客户服务器应用程序通常组织为三个层次：

  • 用户界面层：用户交互所需的一切
  • 处理层：应用程序核心功能
  • 数据层：操作数据或文件系统，保持一致性

image-20230204223932539

客户端-服务器模型可能具有多层体系结构，可能的组织结构如下图a-e所示：

image-20230204223940536

服务器可充当客户端角色，应用服务器向数据库服务器发出了请求，这里应用服务器作为客户端，如下图例中所示：

image-20230204223946064

C3 分布式进程管理

进程和线程的比较

  • 地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享该进程地址空间和其他资源；某进程内的线程在其他进程不可见
  • 通信：进程间通信通过IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信；需要进程同步和互斥手段的辅助，以保证数据的一致性
  • 调度：线程上下文切换比进程上下文切换要快得多
  • 线程是CPU调度单位；进程只作为其他资源分配单位
  • 结论：多线程能提高性能；线程不像进程那样彼此隔离，并受到系统自动提供的保护，因此多线程应用程序开发需要付出更多努力

多线程服务器的优点

  • 在某一线程阻塞时，其他线程可以继续工作
  • 利用多处理器，并行工作
  • 缩短IPC通信的时间
  • 出于软件工程的考虑：例如 字处理程序（用户输入、拼写检查、语法检查、文档布局）

多线程技术不仅能够显著简化服务器代码，还能够使得应用并行技术来开发高性能的服务器变得更加容易，即使在单处理器系统上也是如此。多线程能够保留顺序处理的思路，使用阻塞性系统的系统调用，仍然能到达并行处理的目的。使用阻塞系统调用使编程更容易，并行处理能提高系统的性能。

  • 简化服务器代码
  • 提高并行性
  • 提高服务器性能
  • 保留顺序处理思路
  • 使用阻塞系统调用使得编程更容易

代码迁移的动机有哪些

代码迁移的定义：将程序或执行中的程序传递到其他计算机

动机：

  • 实现负载均衡：将进程从负载重的系统迁移到负载轻的系统，从而改善整体性能
  • 改善通信性能：交互密集的进程可迁移到同一个节点以减少通信开销；当进程要处理的数据量较大时，最好将进程迁移到数据所在的节点
  • 可用性：需要长期运行的进程可能因为当前运行机器要关闭而需要迁移
  • 使用特殊功能：可以充分利用特定节点上独有的硬件或软件功能

* 迁移与本地资源

image-20230204232028094

进程对资源的绑定类型有哪些

按标识符（URL）、按值和按类型

资源对机器的绑定类型有哪些

未连接（数据文件）、附着连接（数据库）和紧固连接（本地设备）

C4 分布式系统通信

什么是远程过程调用？远程过程调用的步骤

远程过程调用（Remote Procedure Call， RPC）是分布式系统通信处理的事实标准，实现消息传输的透明性

远程过程调用(Remote Procedure Call)RPC 是指本地程序调用位于其他机器上的进程，调用方通过消息的形式把参数传递到被调用方的进程，然后等待被调用方执行完后用消息的方式把结果传回调用方。

远程过程调用：当机器A上的进程调用B上的进程时，A上的调用进程被挂起，而B上的被调用进程开始执行。调用方可以通过使用参数将信息传送给被调用方，然后可以通过传回的结果得到信息。编程人员看不到任何消息传递过程。这种方法称为远程过程调用。

步骤：

  1. 客户过程以正常的方式调用客户存根
  2. 客户存根生成一个消息，然后调用本地操作系统
  3. 客户端操作系统将消息发送给远程操作系统
  4. 远程操作系统将消息交给服务器存根
  5. 服务器存根将参数提取出来，然后调用服务器
  6. 服务器执行要求的操作，操作完成后将结果返回给服务器存根
  7. 服务器存根将结果打包成一个消息，然后调用本地操作系统
  8. 服务器操作系统将含有结果的消息发送给客户端操作系统
  9. 客户端操作系统将消息交给客户存根
  10. 客户存根将结果从消息中提取出来，返回给调用它的客户过程

消息持久通信和暂时通信的区别？

  • 持久通信：通信双方不必保持运行
  • 暂时通信：通信系统只在发送者和接收者运行时存储消息

消息同步通信和异步通信的区别？

  • 持久异步通信：提交消息后立即执行其他程序，如电子邮件
  • 持久同步通信：提交消息后会被阻塞，直到消息已到达并存储在接收主机

能够判断消息通信的类型

image-20230205161835070

image-20230205162528274

image-20230205162658740

上图中：

  • a）持久异步通信

  • b）持久同步通信

  • c）暂时异步通信

  • d）基于接收的暂时同步通信

  • e）基于交付的暂时同步通信

  • f）基于响应的暂时同步通信

多播通信：反熵和Gossiping

反熵

  • 提供最终一致性：保证所有的副本最终是一致的
  • 一个服务器可以是：
    • 传染性的：持有愿意向其他服务器散布的更新
    • 易感的：尚未更新的服务器
    • 隔离的：已更新的服务器如果不愿意或不能扩散其更新
  • 反熵传播模型：服务器P周期的随机选取一台服务器Q交换更新，方式包括：
    • P只把自己的更新推入Q：较差的选择？
    • P只从Q拉出新的更新
    • P和Q互相发送更新
    • 可以证明：如果初始只有一台服务器具有传染性，无论采用哪种形式，更新最终将被传播到所有服务器上；$O(log(N))$，N为系统节点数

Gossiping模型

  • 思想：
    • 如果服务器P刚刚因为数据项x而被更新，那么它联系任意一个其他服务器Q，并试图将更新推入Q
    • 如果Q已经被其他服务器更新了，P可能会失去继续扩散的兴趣，变成隔离的（这种可能性是1/k）
  • 快速传播更新的方法
  • 但不能保证所有的服务器都被更新了
  • $s=e^{-(k+1)(1-s)}$,$k=3$时，s小于2%；$k=4$时，s小于0.7%
  • 可以将gossiping和反熵模型结合

C5 命名系统

给定实体的一个无结构的名称（如标识符）如何定位该实体？（移动实体定位的方法有哪些？）

1

  • 广播和多播：广播适用于局域网，在广域网内变得低效；多播只发送给一组符合条件的主机，可进行多播实体的定位服务，可用于定位最近副本

  • 转发指针：原理是：当实体从A移动到B时，它将后面留下一个指针，这个指针指向它在B中的新位置，这种方法主要优点是它很简便：一旦找到实体以后（比如使用传统的命名服务），客户就可以顺着转发指针形成的链来查找实体的当前地址。

  • 基于起始位置的方法：原理是：每个移动主机都是用一个固定的IP地址，所有与该IP地址进行的通信一开始都被转发到移动主机的宿主代理（home agent）中。宿主代理位于局域网中，与包含在移动主机IP地址中的网络地址相对应。当一台移动主机转移到另一个网络中时，它会请求一个可以用来通信的临时地址。这种转交地址（care-of address）要在宿主代理中注册。

  • 分层方法：具体细节在下一节中。

* 分层方法介绍

  • 类似DNS 网络被划分为一组域

  • 目录节点：记录域包含的实体

    • 叶域的目录节点N记录实体E在域中的位置
    • 更高一层域的目录节点N’记录实体E的位置，包含指向N的指针

    这些节点构成一个目录节点树，顶级域的目录节点称为根（目录）节点，包含有全部的实体；根节点拥有每个实体的位置记录，其中每条位置记录都存储一个指向更底层子域目录节点的指针，该记录关联的实体当前就位于这里

    image-20230205185836239

  • 实体可以拥有多个地址，比如它被复制了，就会出现这种情况，如果实体分别在叶域D1和D2中拥有地址，那么同时包含D1和D2的最小域的目录节点将有两个指针，每个指针都指向一个包含地址的子域，也就是下图中的效果（通用组织树）

    image-20230205191704027

描述分层方法中查找一实体的过程

如下图所示，

  • 希望定位实体E的客户指向它所在的叶域D的目录节点发送一个查找请求。
  • 如果这个目录节点没有存储该实体的位置记录，那么就说明该实体不在D中。因此，这个节点会把请求转发给它的父节点。
  • 注意，这里父节点代表一个比它的子域更大的域，如果父节点也没有E的位置记录，那么就会把该查找亲求转发给更高一层的域，以此类推。
  • 如果节点M存储了E的位置记录，那么一旦请求到达M后，就可以知道E位于节点M代表的域dom（M）中。如下图所示，M存储了一条位置记录，其中包含一个指向其子域的指针。
  • 然后，把请求转发给那个子域的目录节点，那个子域会依次进一步向树的下方转发请求，直到请求最终到达叶节点位置。存储在叶节点中的位置记录会包含E在哪一个叶域中的地址。
  • 这样就可以把这个地址返回给发起请求的客户。

image-20230205191727779

一个与分层定位服务有关的重要因素是，查找操作是在局部进行的。原则上，对实体的搜索实在一个以发出查找请求的客户为中心，逐步增大的环中进行的。每当查找请求被转发到更高一层的目录节点是，都会扩大搜索区域。在最差情况下，搜索会连续进行。直至请求到达根节点为止。由于根节点拥有所有实体的位置记录，所以此时可以简单地沿着一条向下的指针路线把请求转发给一个叶节点。

描述分层方法中插入一实体的过程

更新操作以与查找类似的方式在局部进行，如下图所示。

  • 假设实体E在叶域D中创建了一个副本，就需要插入这个副本的地址。插入操作从D的叶节点dir（D）开始，然后D会立即把插入请求转发给父节点。
  • 父节点同样会转发插入请求，直到插入请求到达已经为E存储了位置记录的目录节点M为止。
  • 然后，节点M会在E的位置记录中存储一个指针，该指针指向转发插入请求的那个子节点。此时，该子节点会建立一条关于E的位置记录，该位置记录中包含一个指针，指向转发请求的下一层节点。这个过程会连续进行，直至到达发起请求的叶节点为止。
  • 最后那个叶节点会创建一条记录，这条记录包含实体在叶域中的位置。

也就是，插入请求转发到第一个知道实体E的节点；转发指向叶节点的指针所形成的链

image-20230205193234616

刚才介绍的插入地址操作会导致一条从上到下建立的指针链，它从一个最底层的目录节点开始，该节点拥有实体E的位置记录。另一种是在向父节点发送插入请求之前创建一条位置记录。换句话说，就是从下往上建立指针链。后者的优点是地址会尽快变得可用。这样的话，即使父节点暂时无法到达，仍然可以在当前节点所在的域内查找实体的地址。

C6 同步

Lamport时间戳算法的思想

基于Lamport算法，一种逻辑时钟同步化算法的被称为向量时间戳的Lamport扩展算法

时间戳（Time-Stamping）的算法：

  • 网络上的每个系统（站点）维护一个计数器，起时钟的作用
  • 每个站点有一个数字型标识，消息的格式为$(m,T_i,i)$，m为消息内容，$T_i$为时间戳，i为站点标识
  • 当系统发送消息时，将时钟加一
  • 当系统j接收消息时，将它的时钟设为当前值和到达时间戳这两者的最大值加一
  • 在每个站点，时间的排序遵循以下规则：对来自站点i的消息x和站点j的消息y，如果 $T_i<T_j$或$T_i=T_j$，且$i<j$，则说消息x早于消息y

哪个事件在实际上首先发生并不重要，重要的是所有进程对事件的发生顺序意见一致

例如下图中，消息 a 最早，接下来是消息 x，接下来是消息 b，最后是消息 j；可以看到消息 b 和消息 j 的时间戳是相同的，但是消息 b 来自站点P1，消息 j 来自站点P3，1<3，因此所有站点都认同消息 b 早于消息 j 的结论。

image-20230206003219662

类似的，在下图的例子中，消息a早于消息q

image-20230206012548962

选举算法中Bully算法的思想

当进程P注意到需要选举一个进程作协调者时：

  • 向所有进程号比它高的进程发ELECTION消息
  • 如果得不到任何进程的响应，进程P获胜，成为协调者
  • 如果有进程号比它高的进程响应，该进程接管选举过程，进程P任务完成
  • 当其他进程都放弃时，只剩一个进程时，该进程成为协调者
  • 一个以前被中止的进程恢复后也有选举权

下图例子中：

image-20230206013608023

image-20230206013620248

  • 进程4启动选举
  • 进程5和进程6响应，接管选举，成为协调者
  • 进程6响应进程5的消息，接管选举，进程6成为协调者，通知所有进程

选举算法中环算法的思想

  • 不使用令牌
  • 按进程号排序，每个进程都知道自己的后继者
  • 当进程P注意到需要选举一个进程作协调者时;
    • 就创建一条包含该进程号的ELECTION消息，发给后继进程
    • 后继进程再将自己的进程号加入ELECTION消息，依此类推
    • 最后回到进程P，它再发送一条COORDINATOR消息到环上，包含新选出的协调者进程（进程号最大者）和所有在线进程

具体过程如下图所示：

image-20230206015452065

分布式死锁检测Chandy-Misra-Haas算法的思想

2

思想

允许进程一次请求多个资源（加锁）而不是一次一个

  • 通过允许多个请求同时进行使得事务的增长阶段加速
  • 这使得一个进程可以同时等待两个或多个进程

例子

当某个进程等待资源时，例如P0等待P1，将调用Chandy-Misra-Haas算法。生成一个探测消息发送给占用资源的进程。

  • 消息由三个数组构成：阻塞的进程、发送消息的进程、接收消息的进程
  • 例如，由P0到P1的初始消息包含三元组（0，0，1）

image-20230206021624414

消息到达后，接受者检查以确认它自己是否也在等待其他进程。

  • 若是，就更新消息，字段 1 保持不变，字段 2 改成当前进程号，字段 3 改为等待的进程号
  • 然后消息接着被发送到等待的进程
  • 若存在多个等待进程，就要发送多个不同的消息

不论资源在本地还是在远程，该算法一直继续下去。

图中，（0，2，3），（0，4，6），（0，5，7）和（0，8，0）都是远程消息。

若消息转了一圈又回到了最初的发送者，即字段1所列的进程，就说明存在一个有死锁的环路系统。

C7 一致性和复制

复制的目的和代价

  • 可靠性

  • 性能

    • 服务器数量扩展
    • 地理区域扩展

  • 代价：一致性

    • 网络通信开销
    • 强一致性要求的原子操作很难快速完成

    解决办法：放宽一致性方面的限制，放宽程度取决于复制数据的访问和更新模式以及数据的用途

能区分是否符合严格一致性、顺序一致性、因果一致性和FIFO一致性

  1. 严格一致性（Strict Consistency）：

    • 任何对数据项X的读操作将返回最近一次对X进行写操作的值
    • 对所有进程来说，所有写操作都是瞬间可见的，系统维护着一个绝对的全局时间顺序

    image-20230206162412639

    上图中：a) 严格的一致性存储；b)非严格的一致性存储

  2. 顺序一致性

    顺序一致性对存储器的限制比严格一致性要弱一些，要满足以下的条件：

    • 每个进程的内部操作顺序是确定不变的
    • 加入所有的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确定的，即任一进程都可以感知到这些数据同样的操作顺序

    image-20230206163259554

    上图中：a) 顺序一致的数据存储；b) 非顺序一致的数据存储

  3. 因果一致性（Casual Consistency）

    • 所有进程必须以相同的顺序看到具有潜在因果关系的写操作
    • 不同机器上的进程可以以不同的顺序看到并发的写操作

    image-20230206163633652

    上图是，因果一致性存储允许的，但顺序和严格一致性存储不允许的顺序

    image-20230206163943745

    上图中：a) 违背因果一致性的时间存储顺序；b) 符合因果一致性的时间存储顺序

  4. FIFO一致性（FIFO Consistency）

    FIFO一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：

    • 由某一个进程完成的写操作可以被其他所有的进程按照顺序感知到，而从不同进程中来的写操作对不同的进程可以有不同的顺序。

    下图是一个符合FIFO一致性的时间存储顺序，b一定在c之前

    image-20230206164253123

    FIFO一致性与顺序一致性的区别：

    • 顺序一致性：尽管语句的执行顺序是非确定的，但所有的进程对顺序达成一致。
    • FIFO一致性：各个进程不需要达成一致，不同进程可以以不同的顺序看到

  5. 一致性总结

    | 一致性（Consistency） | 描述（Description） |
    | ——————————- | —————————————————————————————— |
    | 严格 | 所有共享访问按绝对时间排序 |
    | 线性化 | 所有进程以相同顺序看到所有的共享访问。而且，访问时根据全局时间戳排序的 |
    | 顺序 | 所有进程以相同顺序看到所有的共享访问。访问不是根据时间排序的 |
    | 因果 | 所有进程以相同顺序看到因果相关的共享访问 |
    | FIFO | 所有进程以不同进程提出写操作的顺序相互看到写操作。来自不同进程的写操作可以不必总是以相同的顺序出现 |

能区分是否符合单调读、单调写、写后读和读后写

  1. image-20230206180819954

    单调读（Monotonic Reads）

    定义：如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值

    上图中描述了，进程P对同一数据存储的两个不同本地副本执行的读操作；L1，L2表示数据存储的两个不同的本地副本，水平轴表示时间。WS（x1；x2）表示WS（x1）的操作已在L2更新完毕。

    图（a）表示保证单调读一致性的情况。图（b）表示不保证单调读一致性的情况。

  2. image-20230206195722821

    单调写（Monotonic Writes）

    定义：一个进程对数据项x执行的写操作必须在该进程对x执行的任何后续写操作之前完成。

    上图中描述了，进程P对同一数据存储的两个不同本地副本执行的写操作；图（a）为提供单调写一致性的数据存储；图（b）为不提供单调写一致性的顺序存储。

  3. image-20230206201539581

    写后读（读写一致性，Read Your Writes）

    定义：一个进程对数据项x执行的写操作总会被该进程对x执行的任何后续读操作看见

    也就是说，一个写操作总是在同一进程执行的后续读操作之前完成，而不管这个后续读操作发生在什么位置。

    上图（a）中描述了一个提供写后读一致性的数据存储；图（a）（b）非常相像，只是这里的一致性是通过进程P执行的最后一次写操作确定的，而不是通过进程P的最后一次读操作确定；图（a）为提供写后读一致性的数据存储；图（b）为不提供写后读一致性的顺序存储。

  4. image-20230206202159536

    读后写（写读一致性， Writes Follows Reads）

    定义：同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取之相同或更新的值上。

    也就是说，进程对数据项x所执行的任何后续写操作都会在x的副本上执行，而该副本是用该进程最近读取的值更新的。

    上图中，图（a）为提供读后写一致性的数据存储；图（b）为不提供读后写一致性的顺序存储。

基于主备份的协议：远程写协议、本地写协议

  • 基于主备份的协议：每个数据x都有一个关联的主备份，负责协调x的写操作，根据主备份的位置分为：远程写协议，本地写协议

  • 远程写协议

    • 基于主备份的远程写协议，所有读操作和写操作都被转发到一个固定的服务器上

    image-20230206221419729

    • 允许进程在本地可用的副本上执行读操作，但必须向一个固定的主拷贝上转发写操作

    • 提供实现顺序一致性的直接方法

    image-20230206221335448

  • 本地写协议

    • 基于主备份的本地写协议，其中一个单一的拷贝在多个进程间移动
    • 保证一致性
    • 需要跟踪数据项的当前位置：广播、转发指针、基于原始位置的方法和层次定位服务。

    image-20230206222403651

    • 多个连续的写操作可在本地进行，而读操作的进程还可以访问它们的本地拷贝
    • 支持离线操作
    • 主机备份协议，其中主备份移动到要执行更新的进程那里

    image-20230206222602702

复制的写协议：主动复制、基于法定数目的协议

  • 复制的写协议：写操作可以在多个副本上执行

  • 主动复制

    • 写操作可以在多个副本上执行，每个副本对应一个进程，该进程执行更新操作
    • 写操作导致更新传播
    • 操作需要在各地按相同顺序进行：
      • 时间戳(Lamport)
      • 定序器

  • 基于法定数目（多数表决）的协议

    • 要更新一个文件，必须先联系至少半数加一个服务器，并得到它们同意后执行更新，修改文件后这些服务器上的文件将得到一个新的版本号；要读取一个文件，必须联系至少半数加一个服务器，请求它们返回该文件关联的版本号，若版本号一致则该版本为最新版本，因为剩余服务器的个数不够半数以上，试图只更新剩余服务器的请求将会失败。

    • Gifford方法：客户在读写一个复制的数据时，先向多个服务器提出请求，获得许可；读团体$N_R$，写团体$N_W$，$N$个副本；满足$N_R+N_W>N,且 N_W>N/2$

    • Gifford方法中，上述第一个条件用于防止读写操作冲突；而第二个限制条件用于防止读读操作冲突。只有在适当个数的服务器同意参与文件的读写后，客户才能读或写该文件。
    • 下图中的三个实例：(a) 读集合和写集合的正确选择；(b)可能导致写写冲突的读集合和写集合，例如两个写集合{A, B, C, E, F, G}和{D, H, I, J, K, L}就会发生写写冲突；(c)读集合和写集合的正确选择，ROWA（read one, write all）。

    image-20230206223622108

C8 容错性

什么是容错性

  • 容错意味着系统即使发生故障也能提供服务
  • 容错与可靠性相联系，包含以下需求：
    • 可用性（Availability）：任何给定的时刻都能及时工作
    • 可靠性（Reliability）：系统可以无故障地持续运行
    • 安全性（Safety）系统偶然出现故障能正常操作而不会造成任何灾难
    • 可维护性（Maintainability）发生故障的系统被恢复的难易程度

拜占庭将军问题

这里被用于描述分布式系统中的进程故障，故障进程无法发送信息或发出干扰信息，影响其他进程的正常工作，导致系统一致性出现问题。

在拜占庭将军问题中，叛将代表故障进程，忠将代表正常进程。

Lamport的论文中提到的算法指出：如果存在k个叛将（故障进程），那么至少需要总共N=3k+1个将军（进程），才能最终达到一致的行动方案。

例如，下图中，有三个忠诚将军和一个叛将，叛将（故障进程）的代号是3，其余是忠诚将军（无故障进程），也就是k=1，N=4；简单来说，图（a）为将军宣布他们的兵力，图（b）为在（a）基础上每个将军收到的兵力组成的向量，图（c）为每个将军收到的向量；更具体地说，算法分为四步进行。

image-20230207121836845

  1. 如图（a）；每个无故障进程 i 使用可靠单播给其他每个进程发送 vi ，这里假设 vi=i；故障进程则可能发送其他内容，且故障进程可能给不同进程发送不同的值，例如上图中故障进程3给其他进程1，2，4分别发送x，y，z。
  2. 如图（b）；每个进程把第一步收到的结果组织成向量形式。
  3. 如图（c）；把组织好的向量发送给其他进程，此时，每个进程将得到来自其他三个进程的三个向量；由于进程3是故障的，产生了$a-l$共12个值。
  4. 每个进程检查每个接收到向量中的第 i 个元素。如果存在占多数的值，那就将占多数的值放置到结果向量中；如果不存在占多数的值，那么结果向量的相应元素就标记为未知（UNKNOWN）。从（c）中可以看出，1、2、4都与v1、v2、v4的值一致，是正确的结果。从这些进程得出的结论无法确定v3，但也是不相关的。拜占庭协定的目标是一致性意见只与无故障进程的值有关。

下图中，有两个忠诚将军和一个叛将，叛将（故障进程）的代号是3，其余是忠诚将军（无故障进程），也就是k=1，N=3；在图（c）中，无故障进程的向量中无法看到元素1、2和3占大多数的情况，因此都标记为未知，该算法不能产生协定。

image-20230207132659842

一些网络上的参考资料对拜占庭将军问题做了更加具体的说明。

拜占庭将军问题(The Byzantine Generals Problem)提供了对分布式共识问题的一种情景化描述, 由Leslie Lamport等人在1982年首次发表. 论文同时提供了两种解决拜占庭将军问题的算法：

  • 口信消息型解决方案(A solution with oral message);
  • 签名消息型解决方案(A solution with signed message).

本文之后将详细讲述这两种算法. 事实上, 拜占庭将军问题是分布式系统领域最复杂的容错模型, 它描述了如何在存在恶意行为(如消息篡改或伪造)的情况下使分布式系统达成一致. 是我们理解分布式一致性协议和算法的重要基础.

参考：

如何理解拜占庭将军问题？

拜占庭将军问题 (The Byzantine Generals Problem)

拜占庭将军问题 (The Byzantine Generals Problem)

拜占庭将军问题

拜占庭问题与算法

什么叫原子多播

  • 可实现存在进程失败情况下的可靠多播
  • 原子多播：
    • 消息要么发送给所有进程，要么一个也不发送
    • 通常需要所有的消息都按相同的顺序发送给所有的进程
    • 分布式系统中的复制数据库
    • 原子多播确保没有故障的进程对数据库保持一致；当一个副本从故障恢复并重新加入组时，原子多播强制它与其他组成员保持一致
  • 原子多播=虚拟同步+消息排序

分布式提交-两阶段提交的思想

简单、使用、可靠，成为事实上的工业标准。

在两阶段提交（two-phase commit protocol, 2PC）协议中，将提交分为两个阶段

  • 第一阶段（表决阶段）：事务的协调者询问各个参与者是否可以提交，此时，各个参与者将回答消息发送给协调者。协调者根据收到的消息，看是否可以真正提交。
  • 第二阶段（完成阶段）：如果可以提交，则通知各参与者立即执行提交，否则，通知它们终止此事务。

image-20230207143627077

下图中，图（a）为2PC中的协调者的有限状态机；图（b）为2PC中的参与者的有限状态机。

image-20230207144141052

参与者一旦投票，则失去自主能力，必须等待协调者的最终决定，可能造成阻塞；可能的阻塞状态有：

  • 参与者在INIT状态等待协调者的VOTE_REQUEST消息
  • 协调者在WAIT状态等待来自每个参与者的表决
  • 参与者在READY状态等待协调者发送的全局表决消息

下图中，列出了参与者P在READY状态下与另一个参与者Q联系时采取的行动。

image-20230207144428943

当所有运行的参与者都处于READY状态时，尽管都已同意提交，但可能有崩溃的参与者（不一定同意提交），因而无法做出决定（即使选举出新的协调者），只能等待原协调者恢复。

C9 分布式安全

什么是机密性和完整性？

  • 机密性：系统将信息只向授权用户公开
  • 完整性：对系统资源的更改只能以授权方式进行

对称加密系统和公钥系统的区别？

  • 对称加密系统：加密与解密密钥相同，即$P=D_K(E_K(P))$
  • 非对称加密系统：加密与解密密钥不同（一个公开、一个保密），但构成唯一的一对，即$P=D_{KD}(E_{KE}(P))$，也称为公钥系统

* 相关的资料

image-20230207152444718

什么是安全通道？

安全通道：使客户与服务器之间的通信保持安全，免受对消息的窃听、修改和伪造的攻击。

阐述基于共享密钥的身份验证的思想。

质询-响应协议：一方向另一方质询一个响应，只有对方知道共享密钥时才能给予正确的响应。

下图的过程为：

  1. A希望联系B
  2. B发送质询RB
  3. A返回基于共享密钥加密RB后的信息$K_{A,B}(R_B)$
  4. 接下来A发送质询RA
  5. B返回基于共享密钥加密RA后的信息$K_{A,B}(R_A)$

image-20230207153333219

若使用三个消息代替五个，则可能会出现错误，存在被反射攻击的风险

image-20230207153356191

原因：协议的双方在两个不同方向都使用相同的质询

解决：协议的双方永远使用不同的质询

下图描述了反射攻击的过程，攻击者C通过建立两条信道，并将第二次质询的结果，作为第一次被质询的答案返回给B，假装C知道$K_{A,B}$以达到欺骗B冒充A的目的。

image-20230207160207303

阐述使用密钥发布中心的身份验证的思想。

基于共享密钥的身份验证可能存在扩展性问题：N台主机，需要$N*(N-1)/2$个密钥

使用密钥分发中心(Key Distribution Center, KDC)，系统中只需要管理N个密钥

KDC与每台主机共享一个密钥；下图展现了向通信的两台主机分发一个密钥的过程：

  • 首先A告诉KDC期望与B通信;
  • KDC返回分别使用A与KDC之间的密钥、B与KDC之间的密钥加密后的A与B之间的密钥，即$K_{A,KDC}(K_{A,B}), K_{B,KDC}(K_{A,B})$，将上述信息分别分发给A，B；这样就可以通信了

image-20230207163013135

但上图中的方法存在缺点，A可能希望在B接收到来自KDC的共享密钥之前就开始与B建立安全通道，且需要KDC通知B进入通信中。为了解决这些问题，出现了下图中的协议；

image-20230207163832307

KDC返回分别使用A与KDC之间的密钥、B与KDC之间的密钥加密后的A与B之间的密钥，即$K_{A,KDC}(K_{A,B}), K_{B,KDC}(K_{A,B})$，将上述信息都分发给A，最后由A转发给B。$K_{B,KDC}(K_{A,B})$被称为票据，显然，只有B能够使用票据，因为加密票据的密钥只有KDC与B知道。

阐述使用公钥加密的身份验证的思想。

使用公钥加密的审问认证的过程如下图所示，假定A、B都拥有彼此的公钥。

image-20230207163952758

具体过程为：

  • A向B发送一个是使用B的公钥$K_B^+$加密的质询RA，显然只有拥有B的私钥的人才能够解密该信息
  • B接收到信息后，会返回解密过后的质询RA、对A的质询RB、用于更进一步通信的会话密钥$K_{A,B}$；上述返回的信息均使用A的公钥$K_A^+$加密
  • 最后，A返回一个使用会话密钥$K_{A,B}$对质询RB加密后的信息给B，证明确实是AB之间在交谈。这样连接就建立完毕，可以进行后续的对话

使用公钥加密对消息进行数字签名的思想。

数字签名：

  • 如果消息签名检验为真，发送者不能否认消息签名这一事实
  • 消息与其签名的唯一关联防止了对消息进行修改而未发现的可能
  • 使用公钥加密对消息进行数字签名

下图描述了使用公钥加密对消息进行数字签名的过程。

image-20230207171804699

首先A，对原始消息m使用A的私钥$K_A^-$加密，作为签名，接下来为了使消息保密发出，使用B的公钥$K_B^+$进行第二轮加密，之后向B发出。

B收到消息后，首先使用B的私钥$K_B^-$解密，接下来使用A的公钥$K_A^+$解密，最后得到原始的信息；如果保证公钥确实属于A，那么解密m的签名版本以及成功地与m进行比较只能意味着该消息来自A。A受到防止B对m进行任何恶意修改的保护，因为B必须一直证明m的修改版本也是由A签名的。换句话说，经解密的消息本身在本质上从来不能作为证据。

但是上述方法还存在问题。比如：

  • A可以声称其私钥在消息发送前被盗了
  • A可以改变其私钥
  • 使用私钥加密整个消息的开销可能会过大；可使用消息摘要解决，消息摘要是固定长度的位串h=H(m), m是任意长度的消息，H是加密散列函数

下图描述了使用消息摘要对消息进行数字签名的过程

image-20230207174356982

上图中，消息摘要使用A的私钥加密后发送，消息使用明文发送，若需要保密可使用B的公钥加密后发送；B得到消息与加密后的摘要后，单独计算消息摘要，得到所接收消息的摘要，并使用A的公钥解密收到的摘要，若计算出的摘要与解密后的摘要相匹配，则证明该消息是由A签名的。

Diffie-Hellman 建立共享密钥的原理。

原理：

  • 首先A和B双方约定两个大整数n和g，其中1<g<n;这两个整数无需保密，然后执行下面的过程：
  • A随机选择一个大整数x（保密），并计算$X=g^x\mod n$
  • B随机选择一个大整数y（保密），并计算$Y=g^y\mod n$
  • A把X发送给B，B把Y发送给A
  • A计算
  • B计算
  • K即是共享的密钥
  • 监听者在网络上只能监听到X和Y，但无法通过X、Y计算出x和y，因此无法计算出K

下图描述了上述原理中的过程：

  • image-20230207175948018

权能和委派

权能

权能是对于指定资源的一种不可伪造的数据结构，它确切指定它的拥有者关于该资源的访问权限。

存在不同的权能实现方式，这里讨论的是Amoeba操作系统中所使用的实现方式。check字段用于是权能不可伪造；rights为权限位，rights在每种对象类型中的意义是不同的

为了调用一个对象的操作，客户必须将权能传递给服务器检查

image-20230207184459456

服务器创建对象时，客户得到是所有者权能（全1），check字段是随机选择的，同时存储在权能和服务器的一个表中

客户可以从一个所有者权能生成一个受限权能，并发送给另一进程

image-20230207184449453

委派

委派：将某些访问权限从一个进程传递给另一个进程

例如：

A可以构造证书，将权限R给证书的持有者，如B；

A授权R给B，需要向B传递两部分内容，被称为代理，分别是证书，和证书中公钥$S^+_{proxy}$对应的私钥$S^-_{proxy}$。用于委派的一般代理结构如下所示：

image-20230207194138422

证书由三部分构成，分别是权限R，公钥$S^+_{proxy}$和对证书的签名$sig(A,{R,S^+_{proxy}})$；证书可以使用明文传递。

公钥$S^+_{proxy}$对应的私钥$S^-_{proxy}$需要加密传递，用于检验B确实是被授权了。

使用代理来委派和证实访问的所有权的过程如下图所示：

image-20230207193429269

具体过程为：

  • 消息1传递委派代理给B，包括明文传递的由A签名的含有权限R和公钥$S^+_{proxy}$和密文传递的证书对应的私钥$S^-_{proxy}$
  • 消息2为B希望使用A赋予的权限R，在服务器执行操作
  • 消息3为服务器向B确认B是否为权限的合法所有者，即使用证书中的公钥加密一个信息N对B质询
  • 消息4为B返回使用私钥解密后的结果给服务器，证明B确实是该证书的合法持有者

显然，B还可以在A不知道的情况下，将权限赋予给其他人。

C10 分布式文件系统

NFS的共享预约

共享预约是一种锁定文件的隐含方法。共享预约完全独立于锁定，可用于在基于Windows的系统上实现NFS。

客户打开文件时，需要指定所需的访问类型（即READ、WRITE或BOTH），以及服务器应该拒绝其他客户的访问类型。如果服务器不能满足客户的需求，那么该客户的open操作会失败。

下图中确切地表示了一个新客户试图打开一个已被另一个客户成功打开的文件时的情况。对于一个已经打开的文件，使用两个不同的状态变量加以区分。访问状态表明当前客户目前如何访问该文件。拒绝状态表明新客户不要内需进行哪些访问。

img

上图中（a）表示给定一个文件的当前拒绝状态的情况下，客户试图请求以指定的访问类型打开此文件时所发生的事情；同样，（b）表示试图打开一个当前正被另一个客户访问的文件而所请求的访问类型不被该客户允许的情况。

NFS服务器的重复请求高速缓存

  • NFS的底层RPC不能保证可靠性，而且缺乏对重复请求的检测
  • NFS服务器提供重复请求高速缓存解决：XID事务处理标识符

重复性检查是为那些不能在两次执行中返回同一结果的操作而提供的。这方面经典的例子是rm命令。第一个rm命令也许成功了，但是如果应答丢失了，客户机将会重发这个命令。我们希望这样的重复请求能获得成功，此时重复高速缓存被查询，如果发现是一个重复请求则相同的（成功的）结果被作为第二个重复请求的结果返回，就好像是由第一个请求所产生的结果一样。

  • 具体描述为：每个来自客户的RPC请求都有一个唯一的XID。当RPC到来时，服务器缓存该XID。只要服务器还没有发出响应。就说明正在处理这个RPC请求。当服务器处理某个请求后，也缓存该请求的关联响应，与XID相联系，再将响应返回给客户。常见下图中三种情况：

2022第十章分布式文件系统

  • （a）客户端启动计时器，超时后客户仍未收到响应，因此使用原XID重发请求，若服务器收到了第一次请求但还没处理完成，则忽略第二次重发的请求
  • （b）服务器在返回响应后，收到了客户端的第二次请求，若返回响应的时间和收到第二次请求的时间接近，则忽略第二次请求
  • （c）服务器返回的响应丢失，且在相距应答发出后较远的时间收到了客户端发出的第二（或大于二）次请求，则重发该XID对应的响应结果

Coda的回叫（回调）承诺

对于每个文件，客户从服务器获取文件时，服务器记录哪些客户在本地缓存了该文件的拷贝，此时称服务器为客户记录回叫承诺。

客户端缓存的重要性：可扩展性、容错性

Coda高速缓存了整个文件

回叫承诺：服务器记录哪些客户在本地缓存了文件的拷贝，如果文件被客户更改，会通知服务器，服务器会向其他客户发送无效化消息，（这种消息被称为回叫中断，也就是服务器废弃回叫承诺，这是因为服务器随后会将废弃它为刚刚向其发送了无效消息的客户保存的回叫承诺）如果客户在服务器上有未废弃的回叫承诺，它就可以安全地在本地访问文件。如下图中所示：

2022第十章分布式文件系统

具体为当客户A开始会话$S_A$时，服务器会记录一个回叫承诺。同样，B开始会话$S_B$时也是如此。不过，当B关闭会话$S_B$时，服务器向客户A发送回叫终端，从而终端了它对回叫客户A的承诺。注意：由于Coda的事务处理语义，当客户A关闭会话$S_A$时，不会发生任何特殊的事情，整个关闭操作就像所预期的那样被简单地接收。

因此，当A随后要打开会话$S_A’$时，它会发现f本地的副本是无效的，所以它必须从服务器获取最新的版本。另一方面，当B开始会话$S_B’$是，它会注意到服务器仍有一个未被废弃的回叫承诺，该承诺意味着B可简单地重用从会话$S_B$获得的本地副本。

Coda的储藏技术

  • VSG（Volume Storage Group）是一个保存同一个复制卷的服务器集合。
  • 可用的VSG成员叫做AVSG（Available VSG members）。
  • Coda使用ROWA（Read One, Write ALL）来维护复制卷的一致性
  • 使用版本记录方案检测不一致性

下图描述了对于同一个复制文件，具有两个不同的AVSG的客户

2022第十章分布式文件系统

  • Coda 允许客户在断开连接时（ASVG为空）的继续操作，基于本地备份，再次连接后回传服务器。基于事实：两个进程打开相同文件进行写操作很罕见。使用储藏技术（hoarding）。
  • 也就是，为了成功地完成断开连接操作，需要解决的问题是确保客户缓存包含连接断开期间将访问的那些文件。如果采用简单的缓存方法，可以证明客户可能由于缺少必要的文件而不能继续执行。预先使用适当的文件填充高速缓存称为储藏。

下图描述了对于一个卷，Coda客户的状态转换图：

2022第十章分布式文件系统

END

2023.3.2

赏

Learn and Live