分布式系统期末复习材料

发表于 13 Nov 2019 总计 14062字阅读时间 47分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

感谢我的室友DZH

1、分布式系统的定义、特点及主要设计目标

定义：分布式系统是若干计算机的集合，这些计算机对于用户来说就像是单个相关系统。
特性：
- 自主性：计算节点硬件或者软件进程是独立的；
- 耦合性：用户或者应用程序感觉系统是一个系统（节点之间需要相互协作）
设计目标：
- 使资源可访问：必须能够让用户方便地访问资源；
- 透明性：必须隐藏资源在一个网络上分布这样一个事实；
- 开放性：必须是开放的；
- 可扩展性：必须是可扩展的。

2、分布式系统透明性主要包括哪几方面？并简要描述

隐藏进程和资源在多台计算机上分布这一事实：

访问：隐藏数据表示形式的不同以及资源访问方式的不同
位置：隐藏资源所在位置
迁移：异常资源是否移动到另一个位置
重定位：隐藏资源是否在使用过程中移动到另一个位置
复制：隐藏是否对资源进行复制
并发：隐藏资源是否由相互竞争的用户共享
故障：隐藏资源的故障和恢复
持久化：隐藏数据在主存和磁盘这一事实

3、策略和机制有什么不同

策略是用户定制的方案，机制是系统提供的功能。

策略

需要为客户端的缓冲数据设置什么级别的一致性？
我们允许下载的程序执行什么操作？
当出现网络带宽波动的时候如何调整 QoS 需求？
通信的安全水平设置多高？

机制

允许动态设定缓冲策略；
支持为移动代码设置不同的信任级别；
为每个数据流提供可调整的 QoS 参数；
提供不同的加密算法；

4、分布式系统的可扩展性包括哪些方面？有哪些技术可以实现可扩展性

规模可扩展性：用户数量和进程数量增加
地理可扩展性：节点之间的最大物理位置；
管理可扩展性：管理域的数量；
隐藏通信等待时间：尽量避免等待远程服务对请求的响应
分布技术：在多个机器上划分数据和计算
复制技术：在多个不同的机器上创建多个数据副本

5、集群系统和网格之间的区别

集群系统：
- 同构：相同的 OS，近乎相似的硬件；
- 单个管理节点；
网格计算系统：
- 异构；
- 包含多个组织；
- 容易扩展到广域网的环境中

6、云计算作为一种新的计算模式适用于所有企业

错误。

面临安全和法规遵循方面的担心
企业有特殊的硬件要求不适合
对响应时间要求非常高的应用不适合

7、主要的软件体系结构包括哪几种

分层体系结构；
基于对象的体系结构；
以数据为中心的体系结构；
基于事件的体系结构。

8、主要的系统体系结构包括哪几种？与软件体系结构的主要区别是什么

集中式体系结构：整个系统包含一个控制中心
非集中式组织结构：系统没有一个整体的控制中心
混合组织结构：系统中既包含集中式结构也包含非集中式结构
确定软件组件、这些组件的交互以及他们的位置就是软件体系结构的一个实例，又称为系统体系结构

9、分布式的分层结构

用户接口层：用户接口层包含系统与用户直接交互的单元；例如：显示管理等；
应用处理层：包含应用的主要函数，但是，不与具体的数据绑定；；
数据层：数据层管理应用使用的实际数据。

10、非集中化的体系结构主要类型包括哪些

垂直分布：系统逻辑分层，不同层次分布式不同的机器上；
水平分布：客户或者服务器在物理上分成逻辑上相等的几个部分，每个部分相对独立，且分布在不同的机器上；
点对点的系统：水平分布，构成点对点的系统的进程完全相同（既是客户点优势服务器、无中心化系统）；

11、 Chord 结构的生成和查找

12、非结构化的点对点系统搜索内容的方式

泛洪方式：请求发出节点 u 会向其所有邻居节点发出数据搜索请求。如果之前已收到节点请求，则请求会被忽略。否则，节点会在本查找数据项。请求会迭代传递下去。（有 TT 了限制，通信代价高）
随机游走：请求发出节点 u 从其邻居节点钟随机选择一个节点，然后进行本地搜索。如果没有完成，继续从其邻居节点钟选择一个随机节点向下进行。（需要一种停止机制）

13、什么是超级对等节点？如何确定超级节点

维护一个索引或充当一个代理程序地节点；
在非结构化的 P2P 进行搜索时，索引服务器会提高性能；
通过代理程序可以更加有效地决定在哪里放置数据；
超级对等节点地作用：
- 维护索引；
- 监控网络的状态；
- 能够建立连接

14、在 P2P 系统中节点之间连接的方式

举例：Skype 中 A 连接 B 的原理

A 和 B 均在公共网络上
- A 和 B 之间建立 TCP 连接用于控制报文的传输
- A 和 B 之间实际通过 UDP 协议在商定的端口之间通信
A 在防火墙内，而 B 在公网上
- A 和超级对等节点 S 之间建议 TCP 连接用于控制报文的传输
- S 与 B 节点建立 TCP 连接用于中继报文的传输
- A 和 B 之间直接通过 UDP 协议传输数据
A 和 B 都在防火墙后面
- A 与在线的超级对等节点 S 通过 TCP 连接
- S 通过 TCP 协议与 B 连接
- 对于实际的呼叫，另外一个超级对等节点 R 作为中继节点：A 和 B 均会和 R 建立连接
- 所有的音频数据通过 R 以及两个 TCP 连接转发

15、分布式系统的自我管理

自我管理
自我恢复
自我配置
自我优化
自我*
自我计算往往通过反馈循环控制实现自适应性
Astrolabe 监视系统

16、分布式系统中为什么利用线程而不是进程

线程共享相同的地址空间。线程上下文的切换可以独立于操作系统；
一般来讲进程之间的切换要更复杂、代价更高，因为需要陷入到 OS 内核才能完成；
创建和销毁线程的代价要远远小于对进程的创建和销毁；

17、虚拟机化主要包含哪些方式，简要描述

进程虚拟机：分离的指令集合，实际是运行在操作系统之上的解释器或者模拟器
原生虚拟机监控器：底层的指令，同时具有跑在硬件上的最小的操作系统
主机虚拟机监控器：底层指令，但是需要一个完整的 OS

18、在客户端-服务器模型中，服务器的状态主要分为几种，简要解释

无状态服务器：处理完请求后，从来不保存关于客户端的精确的信息

不记录一个文件是否被打开（文件请求完成就关闭）；
不保证清空客户端的 cacha;
不去追踪客户的信息；
结果：客户端和服务器完全独立；由于客户端或者服务器的宕机导致的状态不一致减少；由于服务器不能预测客户端的行为，可能导致性能下降

有状态的服务器：记录客户端的状态信息

记录客户端打开的文件，这样就可以提前实现预取；
知道客户端缓存了哪些数据，允许客户端在本地保存共享数据的备份
有状态的服务器的性能非常高；可靠性问题是一个主要的问题

19、简述如何实现代码迁移？如何区分强迁移和弱迁移

负载分布

确保数据中心中的服务器的复杂运行更加充分（防止浪费能源）
让计算更加贴近数据端，最小化通信代价（例如移动计算）

灵活性

当需要的时候将代码迁移到客户端

强/弱可迁移性

代码片段：包含实际执行的代码；
数据片段：包含状态；
执行状态：包含线程执行对象代码的上下文；
弱移动性
- 仅仅移动代码和数据片段
- 相对简单，特别是如果代码是可移植的
- 需要区分两种模式：代码推送和代码拉取
强移动性：移动组件，包括执行状态
- 迁移：将整个对象从一个机器移动到另一个机器；
- 克隆：开始克隆，将其设置为相同的执行状态；

20、虚拟机迁移的种类及主要特点

迁移镜像：三个不同的方案

将内存特免推到新的机器，在迁移过程中重新发送被修改过的页面；
停止当前的虚拟机；迁移内存，然后重新启动虚拟机；
让新的虚拟机按需拉取内存页面：在新的虚拟机上立即创建进程，并且按需拷贝内存页面

21、 RPC 远程过程调用的概念及主要步骤

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

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

22、使用 socket 进行网络通信的主要模式及主要过程

berkley 套接字
- socket:创建心得通信端点
- bind:将本地地址附加到套接字上
- listen:宣布已准备好接受连接
- accept:在收到连接请求之前阻塞调用方
- connect:主动尝试确立连接
- send:通过连接发送数据
- receive:通过连接接受数据
- close:释放连接

avatar

23、什么是点对点通信、广播和多播

多播

其本质是将分布式系统组织成一个覆盖网络，然后利用这个网络分发数据覆盖网络的构建方法：
- 组织成树，导致每对节点之间只有唯一的路径；
- 组织成网络结构，每个节点都有多个邻居节点（健壮性高）；

广播

24、简述 Gossip 数据通信和反熵通信模型

感染协议
- 起源于流行病理论，包含「已感染的」、「易受感染的」、「已隔离的」；
假设信息传播过程中不存在写-写冲突
- 更新由单个节点发起的；
- 副本仅向有限的几个邻居传播；
- 更新传播是滞后的，并不是立即进行；
- 最终，每一次更新都会到达所有副本；
传播模型
- anti-entropy（反熵）模型；
- rumor spreading（流言传播）模型；

反熵模型

结点 p 随机选取另一结点 Q，然后与 Q 交换更新信息。这里交换更新信息的方法有如下三种：

P 只是把它自己的更新信息发出给 Q，即为基于 push 的方法；
P 只是从 Q 那里获得更新信息，即为基于 push 的方法；
P 和 Q 相互发送更新信息给对方，即为基于 push-pull 的方法。

25、简述 SSP 即转发指针的工作原理

当实体移动的时候，会在当前位置留下到下一个位置的指针

去引用对于客户端来讲变得完全透明，只需要沿着指针连搜索；
当实体的当前地址找到后，更新客户端的引用；
扩展性问题（地理可扩展性）
- 较长的传播链很脆弱，容易断开
- 实体的定位开销比较大；

SSP Chain

利用转发指针的原理，在客户存根中可以通过存储一个捷径达到重定向转发指针的目的
如果链中有服务器崩溃，如何解决？
- 直接向客户存根发送响应或沿着转发指针的相反方向响应，二者都有所长，如果服务器存根不再被任何客户引用，就可以删除它。

26、 Chord 指纹表的查找过程，节点如何加入和退出指纹表

27、简述在树结构目录中查询实体及插入实体的过程

查询

开始在一个叶节点上搜索；
如果节点知道实体 E=>继续搜索下游指针，否则返回父节点；
向上搜索的过程最终会以到达根节点而停止；

插入

插入请求被转发到知道实体 E 地址对的第一个节点；
建立一条从第一个知道实体 E 地址的节点到实体 E 的指针链

28、名称解析闭包

给定一个路径名，查找出存储在由该名称所指向的节点中的任何信息，查询名称的过程称为名称解析

29、实体的硬链接和软链接

硬链接

我们所描述的路径名即用于在命名图中按照特定路径搜索节点的名字就是「硬链接」；

软链接

允许一个节点 N 包含另外一个节点名字；用叶节点表示实体，而不是存储实体的地址和位置，该节点存储绝对路径名
- 首先解析 N 的名字；
- 读取 N 的内容返回名字；
- 利用返回的名字进行名字解析；

30、什么是挂接点和挂载点

挂接点：在当前命名空间中用于存储节点标识符的目录节点成为挂接点
挂载点：外部名称空间中的目录节点称为挂载点；挂载点是命名空间的「根」

31、什么是命名空间，命名空间的分层结构主要由哪几部分构成

基本问题

跨越多个机器的分布式命名解析过程与命名空间管理是通过将命名图分布在多个节点上实现的；

三层名称空间

全局层：由最高级别的节点构成，即由根节点以及其他逻辑熵靠近根节点的目录节点组成。特点是：稳定，目录表很少改变，可以代表组织或者组织群。
行政层：由那些在单个组织内一起被管理的目录节点组成。行政层中的目录节点所具有的特点是代表属于同一组织或行政单位的实体组；相对稳定，但是比全局层的目录变化频繁；
管理层：由经常改变的节点组成。如代表本地主机的节点及本地文件系统等，由终端用户维护；

32、迭代命名解析和递归命名解析

迭代命名解析

根服务器会尽量深入地解析路径名，然后把结果返回给客户。

递归名称解析

在名称解析过程中使用递归。与返回客户解析程序每个中间结果不同，在使用递归名称解析时，名称服务器会把结果传递给它找到的下一台服务器。

33、瞬时同步通信的主要问题以及解决方案

34、时钟同步：内同步和外同步

精度

目的是保证任意两个机器的时钟之间的偏差在一个特定的范围内，即精度 pi: Cp(t)-Cq(t) <=pi

准确度

对于准确度，我们的目的是保证时钟边界在 α 之内，即 Cp(t)-t <=α

同步

内部同步：保证时钟的精度；
外部同步：保证时钟的准确度；

35、如何在没有 UTC 的情况下保障时间的准确性

Berkeley 算法

原理：时间服务器周期性地扫描所有的服务器，计算时间均值，并告诉所有其他机器如何根据当前时间进行调整；

36、逻辑时钟？及算法

所有的进程并不一定在时间上达成一致，而只需要在时间发生顺序上达成一致，也就是需要「排序」

算法：为每一个时间 e 分配一个时间戳 C（e）使其满足以下属性：

P1 如果 a 和 b 是同一个进程的时间，并且 a->b,那么有：C(a)<C(b);
P2 如果 a 是信息 m 的发送方，并且 b 是信息的接收者，那么 c(a)<c(b)；

37、什么是全序广播

在一个副本数据库上的并发更新在任何地方都应该是同样的顺序

38、如何利用 Lamport 逻辑时钟解决互斥访问及临界区访问

关键区

在同一个时刻至多允许一个进程执行的代码片段。与多播类似，多个进程需要在访问顺序上达成一致。

解决互斥访问

利用全序的多播方法，所有的进程建立单独的队列，以相同的顺序发送消息；
互斥访问在进程进入关键区的顺序上达成一致；

39、因果有序的多播传播

与全序多播的关系

因果有序的多播比之前提到的全序多播更弱。尤其是如果两个消息互相没有任何关系，并不关心以哪种顺序发送给应用程序。

观察

使用向量时钟，可以入确保所有因果先于某个消息的所有消息接收后才传送这个消息。

调整

仅当$p_i$发送消息时才增加VC[i]，当$p_j$接收到消息后才调整$VC_j$；

p_j 推迟发送消息 m 直到

ts(m) [i] = VC_j[i]+1
ts(m) [k]<=VC_j[k], k!=i

40(1)、解决分布式系统中多进程互斥的方法

基于许可的方法：如果进程需要访问临界区或者访问资源，需要从其他进程获得许可。
基于令牌的方法：仅有的一个令牌在进程之间传递。拥有令牌的进程可以访问临界区或者将令牌传递给其他进程。

40、 Ricart & Agrawala 互斥算法

要求系统中所有事件都是完全排序的。对于每对事件，比方说消息，哪个事件先发生都必须非常明确
进程要访问共享资源，构造一个消息，包括资源名、它的进程号和当前逻辑时间。然后发送给所有的其他进程。

接收到的消息的决策动作分为三种情况

若接受进程没有访问资源，而且也不想访问资源，向发送者返回一个 OK 消息
若接收者已获得对资源的访问，那么它就不答应，而是将该请求放入队列中
如果接收者想访问资源但尚未访问时，它将收到消息的时间戳与它发送给其他进程的消息的时间戳进行比较。时间戳早的那个进程获胜，如果接收到的消息的时间戳比较早，那么返回一个 OK 消息。如果它自己的消息的时间戳比较早，那么接收者将收到的消息放入队列中，并且不发送任何消息；

41、无线网络中的选举算法

网络中的任意结点可以通过往其紧邻结点发送一个 election 消息开始选举
结点第一次收到 election 消息时，把该发送者指定为其父节点，然后把 election 消息发送给他的所有紧邻结点。
当结点从某个结点接收到一条 election 消息时，他只是确认这一接受
向父结点报告诸如其电池寿命和其他资源容量的信息
父结点利用这些消息将下游结点的进行比较，选择最合格的结点作为领导候选者。
这样源结点就知道选哪个结点做领导者更好

42、数据一致性模型

一致性模型实质上是进程和数据存储之间的一个约定，即如果进程统一遵守某些规则，那么数据存储将正常运行。

数据存储精确规约了当出现并发操作时读写操作的返回结果

43、连续一致性或者一致性程度主要包含哪些方面

连续一致性

数值偏差：不同副本之间的数值可能不同
新旧偏差：不同副本之间的「新旧」不同
顺序偏差：不同副本更新操作的顺序和数量可能不同

44、什么是顺序一致性和因果一致性

顺序一致性

重要的以数据为中心的一致性模型。
任何执行结果都是相通的，就好像所有进程对数据存储的读写操作是按照某种序列顺序执行的，并且每个进程的操作按照程序所定制的顺序出现在这个序列中。
进程可以看到所有进程的写操作，但是只能看到自己的读操作。

因果一致性

一种弱化的顺序一致性的模型。
所有的进程必须以相同的顺序看到具有潜在因果关系的写操作。
不同机器上可以以不同的顺序看到并发写操作。

45、数据为中心的一致性和客户为中心的一致性模型各自适用于什么场景

以数据为中心的一致性模型

读写并重的数据存储

以客户为中心的一致性模型

读多写少，提供弱一致性即最终一致性
最终一致性：如果在很长一段时间内没有更新操作，那么所有的副本将逐渐地成为一致的。

46、什么是最终一致性？有什么优缺点

没有更新操作时，所有的副本将最终逐渐成为一致的。实际上，也就是只要求更新操作被保证传到所有副本。
优点是，容易解决写-写冲突，实现开销通常较小。
缺点是，用户移动时可能重新连接到还没有更新的副本，那么用户就会注意到这个不一致。

47、读写一致性？写读一致性？具体场景

读写一致性

即「读」依赖「写」。一个进程对数据项 x 执行一次写操作的结果总是会被该进程对 x 执行的后续读操作看见。也就是说，一个写操作总是在同一进程执行的后续读操作之前完成，而不管这个后续的读操作发生在什么位置。

具体场景：一个论坛服务器可以使用读写一致性，它可以保证，如果用户刷新页面，他们总会看到自己刚提交的任何帖子和更新。它不会对其他用户的写入做出承诺，其他用户的更新可能稍等才会看到，但它保证用户自己提交的数据能马上被自己看到。

写读一致性

即「写」包含之前的「读」。同一个进程对数据项 x 执行的读操作之后的写操作，保证发生在与 x 读取值相同或比之更新的值上。也就是说，进程对数据项 x 所执行的任何后续的写操作都会在 x 的副本上执行，而该副本使用该进程最近读取的值更新的。

具体场景：网络新闻组的用户只有在已经看到原文章之后才能看到它的回复文章。

48、服务器副本的放置位置和内容放置

位置放置的三种⽅法

假定已经放置了 K 个服务器，需要从 N-K 个服务器中选择⼀个最佳的服务器与所有的客户端之间的距离最⼩
选择第 K ⼤的⾃治系统（在同⼀个机构管理下的⽹络称为⼀个⾃治系统），然后在含有最⼤数量的连接的路由器上放置⼀台服务器
假定在⼀个 D 维的⼏何空间中放置服务器，节点之间的距离反映了延迟。把整个空间划分为多个单元，选择 K 个密度最⼤的单元放置副本服务器

内容放置

永久副本：进程/机器持久存储副本数据
服务器启动的副本：进程可以动态的持有副本数据，该副本是在初始化数据存储的所有者时创建的
客户端启动的副本：当客户端初始化时创建的副本

49、内容分发的方式有哪些？ Pull-based 和 Push-based 的内容分发方法有什么不同

基于 push 的更新：服务器初始化的⽅法，不需要其他副本请求更新，这些更新就被传播到那些副本。（属于主动复制）永久副本与服务器启动的副本之间常使⽤这种⽅式，适⽤于读/更新比率较⾼时。
基于 pull 的更新：客户端初始化⽅法，客户端请求的更新。（属于被动复制）适⽤于读/更新比率较低时
租⽤（lease）的⽅式：在 pull 和 push 之间动态切换。在指定的时间内把更新推给客户，租⽤到期后改为 pull ⽅式。
pull 和 push 的不同：
- push 属于主动复制，永久副本与服务器启动的副本之间常使⽤这种⽅式，适⽤于读/更新比率较⾼时。
- pull 属于被动复制，适⽤于读/更新比率较低时。

50、在一致性协议中，如何限定数值偏差？限制新旧偏差

avatar

51、基于主备协议的复制协议主要包括哪两种方式？分别有什么特点

远程写

要在数据项 x 上执行一个写操作的进程，会把该操作转发给 x 的服务器。该主服务器在其 x 的本地副本上执行更新操作，随后把该更新转发给备份服务器。每个备份服务器执行这个更新操作，并往主服务器会送一个确认信息。当所有备份服务器都更新了它们的本地副本后，主服务器回送一个确认消息给初始进程。
特点:传统的分布式数据库和文件系统需要较高的容错性，副本位于 lan

本地写

当某个进程要更新数据项 x 时，先定位 x 的主副本，然后把他移到自己的位置上。
优点：可以在本地执行多个连续的写操作，而读操作仍可以访问其他本地副本；可应用于能够在离线模式下操作的移动计算机

52、如何理解基于团体的复制写协议

Nr 代表都团体的服务器数
Nr+Nw>N 用于防止读写操作冲突
Nw>N/2 防止读读操作冲突

53、什么是可依赖性？与可依赖性相关的需求包括哪些方面

含义：软件组件为用户提供服务。为了提供服务，组件可能需要来自其他组件的服务（服务依赖），即组件可能依赖于其他组件。
于可依赖型相关的需求：可用性；可靠性；安全性；可维护性

54、可靠性与可用性的定义及区别

可靠性

系统可以无故障地持续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义。高度可靠的系统可以在一个相对较长的时间内持续工作而不被中断

可用性

说明系统已经准备好，马上就可以使用。高度可用的系统在任何给定的时刻都能及时地工作。

55、分布式系统中主要包含哪些失效模型？简要描述

崩溃性故障

服务器停机，但在停机之前工作正常

遗漏性故障、接受故障、发送故障

服务器不能响应到来的请求
服务器不能接受到来地消息
服务器不能发送消息

定时故障

服务器的响应在指定的时间间隔之外

响应故障、值故障、状态转换故障

服务器的响应不正确
响应地值错误
服务器偏离了正确的控制流

随意性故障

服务器可能在随意的时间产生随意的响应

56、分布式系统中冗余的主要方式有哪些

信息冗余：在数据单元中添加额外的位数剧使错乱的位恢复正常；
时间冗余：如果系统出错，一个动作可以再次执行（事务处理）；
物理冗余：通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障；

57、在分布式系统中如何检测失效

如果 P 没有在规定的时间 t 内收到来自 Q 的心跳信息：P 怀疑 Q 失效；
如果 Q 稍后发出消息：P 停止怀疑 Q，P 增加 timeout 的时间；
如果 Q 确实宕机，P 会一直怀疑 Q；

58、如何设计可靠的 RPC 通信机制

两个简单的⽅案：
- 只是将错误信息反馈给客户端（不能定位服务器）
- 重新传输请求（请求丢失）
最多⼀次语义和最少⼀次语义：
- 最多⼀次语义：服务器保证它只执⾏⼀个操作最多⼀次。如抢票时我们只能买⼀张票，或者买票失败。
- ⾄少⼀次语义：不断发送请求直到服务器有返回
丢失应答信息：
- 客户端不能断定丢失原因是请求丢失还是服务器的响应丢失
- 部分解决⽅案：设计服务器时让其操作都是幂等的，即重复多次执⾏与执⾏⼀次的结果是相同的
客户端崩溃：
- 服务器在⼯作且持有资源，但没有客户端需要结果
- 解决⽅案：孤⼉消灭———— 客户端恢复时重启服务器或丢弃之前的计算；再⽣—— 把时间
- 分为顺序编号的时期，客户端恢复后向所有的服务器⼴播新时期的开始，由服务器杀死与客户
- 端相关的「孤⼉」；优雅再⽣；到期

59、什么是可靠多播？可靠多播存在的问题

消息发送和接受按照发送者发送的顺序
存在的问题：如果存在 N 的接收方，会导致大量返回 N 个确认信息，如果数量很大，发送方会被反馈消息淹没，形成反馈拥塞
简单方案：接收方不对消息进行反馈，而只是在消息丢失时才返回一个反馈消息；存在的问题是：需要缓存大量的陈旧的信息

60、简述两阶段提交协议？在参与者失效时如何恢复？协作者失效时如何恢复

协助者先发送一个 vote-request 给参与者（想得到参与者的支持）
参与者收到后返回一个消息 commit 或者 abort
协助者收集消息，如果都是 commit 则广播通知 global-commit，如果不是的话也会广播通知参与者取消 global-abort
参与者如果等到 commit 就执行提交，如果是 abort 则取消;

参与者失效：

Init
Ready：利用日志记录协助者的决定
Abort:此时状态是幂等的，重新执行一遍
Commit：同上

协作者失效

开始 2PC 时，记录进入 wait 状态，恢复之后重新发送 vote-request
在第二阶段作出决定后，只要记录表决结果就可以了，恢复时重发这个决定

61、分布式系统失效恢复的主要方式

回退恢复：将系统从当前的错误状态回到先前的正确状态。
前向恢复：当系统进入错误状态时，不是回退到以前的检查点处的状态，而是尝试从可以继续执行的某点开始把系统带入一个正确的新状态。

62、 Client-server 失效场景及恢复方法

63、什么是检查点方法

恢复线路：假定每一个进程都会周期性记录检查点，最近一次的全局一致的检查点就是恢复线路

64、独立检查点方法？协调检查点方法

独立检查点方法

协调检查点方法

65、什么是共识？主要的共识协议有哪些？共识的使用场景有哪些

共识：使所有非故障进程就由谁来执⾏命令达成⼀致，⽽且在有限的步骤内达成⼀致
共识协议：
- 基于泛洪的共识：可以准确检测到进程的状态，使⽤于⼩型局域⽹的消息传播
- Paxos 协议：⽆法解决拜占庭失效，适⽤于分布式数据库
- 在任意失效语义下的共识：指的是进程⾃⾝失效后可能会影响其他进程导致其他进程也失效
拜占庭失效：
分布式系统中算法执⾏过程中的任意⼀个错误。当拜占庭失效发⽣时系统可能会做出任何不可
- 预料的反应。
- 在存在消息丢失的不可靠信道上试图通过消息传递的⽅式达到⼀致性是不可能的
- PBFT 算法可以解决拜占庭失效。

66、 Paxos 的主要过程？Paxos 算法的特性？ Paxos 的主要变种

proposer:发起 paxos 的进程
acceptor:存储节点、接受、处理和存储消息
Quorum：n/2+1 个 acceptors
round:一轮包含 2 个阶段:phase-1&phase-2

主要变种

classic paxos：1 个实例写入需要 2 轮 RPC
multi paxos:约为一轮 RPC，确定一个值
fast paxos:没冲突则一轮，有冲突则两轮

67、 Raft 共识的主要特点是什么

简单，容易理解，容易实现，效率足够优秀，安全性有保障。

68、 NFS （客户-服务器体系结构）文件系统的主要架构

每个文件服务器都提供其本地文件系统的一个标准化视图；
每个 NFS 服务器都支持相同的模型；
底层模型是远程文件访问模型；

avatar

69、 GFS 文件系统的主要特点

主服务器只是在内存中维护了一张（文件名，块服务器）的映射表
- 最小化 IO，以日志的形式保存对数据的更新操作，当日志过大时将创建检查点，存储主存的数据；
大量的实际工作是块服务器完成的。文件采用主备复制，主服务器避开循环
上述两个特点决定了 GFS 主服务器不会构成瓶颈，为系统带来重要的可伸缩性，单个主服务器可以控制数百个块服务器

70、什么是文件系统语义模型？主要的语义模型包括哪些？简要描述其特征

Unix:立即将缓存文件的所有改动传播回服务器，简单但是效率低；（对所有进程即时可见）
会话：在文件关闭之前，所有改动对其他进程都是不可见的即会话语义
不可改变：所有文件都是不可改变的，文件上的操作只有 create 和 read
事务：使用原子事务处理共享文件

71、拜占庭容错的基本思想及基本过程

拜占庭容错是一种共识算法，即如何使远距离通信的人们对一个提案达成一致意见。与普通的共识算法（例如，majority wins，即超过一半人赞成即有效）不同的是，PBFT 可以容忍投票的人中产生叛徒或者不响应。如果叛徒的数量大于或等于 1/3，拜占庭问题不可解。

达到目标的简单方式是，指定一个协调器，它通过简单地给每个请求附加一个序号来序列化所有操作。当然，问题是序列器也很有可能失败。

用一个副官模型来理解：

假设只有 3 个人，A、B、C，三人中如果其中一个是叛徒。当 A 发出进攻命令时，B 如果是叛徒，他可能告诉 C，他收到的是「撤退」的命令。这时 C 收到一个「进攻」，一个「撤退「，于是 C 被信息迷惑，而无所适从。

如果 A 是叛徒。他告诉 B「进攻」，告诉 C「撤退」。当 C 告诉 B，他收到「撤退」命令时，B 由于收到了司令「进攻」的命令，而无法与 C 保持一致。

因此在只有三个角色的系统中，只要有一个是叛徒，即叛徒数等于 1/3，拜占庭问题便不可解。

算法整体的基本过程如下：

首先，通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）。
在某个视图中，客户端将请求 <REQUEST,operation,timestamp,client> 发送给主节点，主节点负责广播请求到所有其它副本节点。
所有节点处理完成请求，将处理结果 <REPLY,view,timestamp,client,id_node,response> 返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果，作为最终结果。

72、 P2P 系统中用于提高系统可用性的方案？以及方案的主要特点

复制：通过放置多个副本提高数据的冗余度从而提高可用性
擦除编码：通过把一个文件分成 m 块随后把它记录到 n>m 块中。任何 m 个编码块的集合都足以用于重构原始文件；冗余性因子 n/m

73、在分布式文件系统中主要关注的问题包括哪些？并分别给出一些解决问题的方案

同步解决方案

立即将缓存文件的所有改动传播回服务器，简单但是效率低；（对所有进程即时可见）
在文件关闭之前，所有改动对其他进程都是不可见的即会话语义
所有文件都是不可改变的，文件上的操作只有 create 和 read
使用原子事务处理共享文件

NFS 文件具有无状态服务器，需要额外的方式同步对文件的访问

实现方式：利用锁管理器
问题：文件加锁机制；锁的粒度
NFS 文件锁的操作：
1. lock:为一定范围的子节创建锁
2. lockt:测试是否授予了相冲突的锁
3. locku：删除一定范围的字节上的锁
4. renew:继续租用指定的锁

74、分布式机器学习的参数服务器如何理解

概括来说，参数服务器是一个为了解决分布式机器学习问题的编程框架。

该框架主要包括服务器端（Server ），客户端（Client）和调度器（Scheduler）。服务器端的主要功能是存放机器学习任务的参数，接收客户端的梯度，对本地参数进行更新。

客户端的主要功能有两点：一是从服务器端获取当前最新的参数；二是，使用本地或者远程节点的数据和从服务器端获取的参数，计算得到预测值，然后根据设定的损失函数，计算关于训练参数的梯度，最后将梯度发送给服务器端。

调度器的主要功能是管理服务器，客户端节点，完成节点之间数据同步，节点添加/删除等功能。

参数服务器的五个关键特征（设计理念）：

高效的通信（Efficient communication）：异步通信模型不阻碍计算，最优化机器学习任务来减少网络负担。
灵活的一致性模型（Flexible consistency models）：宽松的一致性进一步隐藏同步花销和延迟。允许算法设计者去平衡算法收敛率与系统效率。
灵活的可扩展性（Elastic Scalability）：在无需重启运行中的框架下便可添加新节点。
错误容忍和持久（Fault Tolerance and Durability）
易用（Ease of Use）

75、如何保障参数服务器状态的一致性

Sequential：这种情况下，所有任务顺序进行，因此数据严格一致，不会出现不同副本看到的数据有不同的情况，因此实际上跟前文介绍的 BSP 是等价的。
Eventual：这种情况下，所有任务并行执行，因此拥有最大的随机性。Eventual 只适用于对于数据一致没有要求，非常健壮的算法，比如 SGD。
Bounded Delay：在限定范围内其他节点同步结果，未及时同步的节点可等下一次更新

76、 MapReduce 计算泛型的主要流程是什么

先将数据划分为多个 key/value 键对值
然后输入 map 框架来得到新的 key/value
交给 reduce 框架做输出组合

流程

Input
InputSplits：定义了输入到单个 map 任务的输入数据
RecordReader：定义了如何从数据转化了一个 Key/value 的详细方法并输出到 mapper 类中
mapper
combiner：合并相同 Key 的键值对
partitioner&shuffle：将结果传到对应的 reducer 所在的节点，partitioner 决定具体位置
sort: 排序
reducer
output

77、 MapReduce 计算泛型的主要特点是什么

大规模的计算被分割成很多小的任务
使用磁盘存储中间结果
自动并行
自动容错
入门门槛低

78、 Kubernetes 的主要组成是什么？主要功能又是什么？Kubernetes 中的 service 如何理解

master node

API Server（API 服务器）：提供了资源操作的唯一入口，并提供认证、授权、访问控制、API 注册和发现等机制
etcd：使用 etcd 存储可以被集群每一个节点使用的配置数据，保存了集群的状态
scheduler: scheduler 负责资源的调度策略将 Pod 调度到相应的机器上
controller: 负责维护集群的状态，比如故障检测、自动扩展、滚动更新等

nodes

kubelet 负责维护容器的生命周期，同时也负责 CVI 和 CNI 的管理

services

A group of pods work together grouped by a selector
Defines access policy load balanced or headless
Can have a stable virtual IP and port also a DNS name
VIP is managed by kube-proxy
- watch all services
- updates iptables when backends change
- default implementation - can be replaced!

工作流程

user 向 APIserver 发出指令
API 响应指令，通过一系列认证授权，把 pod 数据存储到 etcd，创建资源并初始化
controller 创建
scheduler 检测发现新的 pod 并绑定到合适的主机
将绑定结果存储到 etcd
kubelet 获取自身 node 上要运行的 pod 并与自身缓存相比较，新增加 pod
创建 pod
kube-proxy 为新创建的 pod 注册动态 DNS 到 CoreOS
controller 将当前 pod 状态与用户所期望的状态作比较，不同则修改为用户期待状态，若不行则删掉重新建 pod

网络

容器间通信：同一个 Pod 的容器共享同一个网络命名空间，它们之间的访问可以用 localhost 地址 + 容器端口就可以访问
同一个 Node 中 Pod 间通信：同一 Node 中 Pod 的默认路由都是 docker0 的地址，由于它们关联在同一个 docker0 网桥上，地址网段相同，所有它们之间应当是能直接通信的
不同 Node 中 Pod 间通信：不同 Node 中 Pod 间通信要满足 2 个条件： Pod 的 IP 不能冲突；将 Pod 的 IP 和所在的 Node 的 IP 关联起来，通过这个关联让 Pod 可以互相访问

分布式系统期末复习材料

1、分布式系统的定义、特点及主要设计目标

2、 分布式系统透明性主要包括哪几方面？并简要描述

3、 策略和机制有什么不同

策略

机制

4、 分布式系统的可扩展性包括哪些方面？有哪些技术可以实现可扩展性

5、 集群系统和网格之间的区别

6、 云计算作为一种新的计算模式适用于所有企业

7、 主要的软件体系结构包括哪几种

8、 主要的系统体系结构包括哪几种？与软件体系结构的主要区别是什么

9、 分布式的分层结构

10、 非集中化的体系结构主要类型包括哪些

11、 Chord 结构的生成和查找

12、 非结构化的点对点系统搜索内容的方式

13、 什么是超级对等节点？如何确定超级节点

14、 在 P2P 系统中节点之间连接的方式

15、 分布式系统的自我管理

16、 分布式系统中为什么利用线程而不是进程

17、 虚拟机化主要包含哪些方式，简要描述

18、 在客户端-服务器模型中，服务器的状态主要分为几种，简要解释

无状态服务器：处理完请求后，从来不保存关于客户端的精确的信息

有状态的服务器：记录客户端的状态信息

19、 简述如何实现代码迁移？如何区分强迁移和弱迁移

负载分布

灵活性

强/弱可迁移性

20、 虚拟机迁移的种类及主要特点

迁移镜像：三个不同的方案

21、 RPC 远程过程调用的概念及主要步骤

22、 使用 socket 进行网络通信的主要模式及主要过程

23、 什么是点对点通信、广播和多播

多播

广播

24、 简述 Gossip 数据通信和反熵通信模型

反熵模型

25、 简述 SSP 即转发指针的工作原理

SSP Chain

26、 Chord 指纹表的查找过程，节点如何加入和退出指纹表

27、 简述在树结构目录中查询实体及插入实体的过程

查询

插入

28、 名称解析闭包

29、 实体的硬链接和软链接

硬链接

软链接

30、 什么是挂接点和挂载点

31、 什么是命名空间，命名空间的分层结构主要由哪几部分构成

基本问题

三层名称空间

32、 迭代命名解析和递归命名解析

迭代命名解析

递归名称解析

33、 瞬时同步通信的主要问题以及解决方案

34、 时钟同步：内同步和外同步

精度

准确度

同步

35、 如何在没有 UTC 的情况下保障时间的准确性

Berkeley 算法

36、 逻辑时钟？及算法

37、 什么是全序广播

38、 如何利用 Lamport 逻辑时钟解决互斥访问及临界区访问

关键区

解决互斥访问

39、 因果有序的多播传播

与全序多播的关系

观察

调整

p_j 推迟发送消息 m 直到

40(1)、 解决分布式系统中多进程互斥的方法

40、 Ricart & Agrawala 互斥算法

接收到的消息的决策动作分为三种情况

41、 无线网络中的选举算法

42、 数据一致性模型

43、 连续一致性或者一致性程度主要包含哪些方面

连续一致性

44、 什么是顺序一致性和因果一致性

顺序一致性

因果一致性

2、分布式系统透明性主要包括哪几方面？并简要描述

3、策略和机制有什么不同

4、分布式系统的可扩展性包括哪些方面？有哪些技术可以实现可扩展性

5、集群系统和网格之间的区别

6、云计算作为一种新的计算模式适用于所有企业

7、主要的软件体系结构包括哪几种

8、主要的系统体系结构包括哪几种？与软件体系结构的主要区别是什么

9、分布式的分层结构

10、非集中化的体系结构主要类型包括哪些

12、非结构化的点对点系统搜索内容的方式

13、什么是超级对等节点？如何确定超级节点

14、在 P2P 系统中节点之间连接的方式

15、分布式系统的自我管理

16、分布式系统中为什么利用线程而不是进程

17、虚拟机化主要包含哪些方式，简要描述

18、在客户端-服务器模型中，服务器的状态主要分为几种，简要解释

19、简述如何实现代码迁移？如何区分强迁移和弱迁移

20、虚拟机迁移的种类及主要特点

22、使用 socket 进行网络通信的主要模式及主要过程

23、什么是点对点通信、广播和多播

24、简述 Gossip 数据通信和反熵通信模型

25、简述 SSP 即转发指针的工作原理

27、简述在树结构目录中查询实体及插入实体的过程

28、名称解析闭包

29、实体的硬链接和软链接

30、什么是挂接点和挂载点

31、什么是命名空间，命名空间的分层结构主要由哪几部分构成

32、迭代命名解析和递归命名解析

33、瞬时同步通信的主要问题以及解决方案

34、时钟同步：内同步和外同步

35、如何在没有 UTC 的情况下保障时间的准确性

36、逻辑时钟？及算法

37、什么是全序广播

38、如何利用 Lamport 逻辑时钟解决互斥访问及临界区访问

39、因果有序的多播传播

40(1)、解决分布式系统中多进程互斥的方法

41、无线网络中的选举算法

42、数据一致性模型

43、连续一致性或者一致性程度主要包含哪些方面

44、什么是顺序一致性和因果一致性

45、数据为中心的一致性和客户为中心的一致性模型各自适用于什么场景

46、什么是最终一致性？有什么优缺点

47、读写一致性？写读一致性？具体场景

49、内容分发的方式有哪些？ Pull-based 和 Push-based 的内容分发方法有什么不同

50、在一致性协议中，如何限定数值偏差？限制新旧偏差

51、基于主备协议的复制协议主要包括哪两种方式？分别有什么特点

52、如何理解基于团体的复制写协议

53、什么是可依赖性？与可依赖性相关的需求包括哪些方面

54、可靠性与可用性的定义及区别

55、分布式系统中主要包含哪些失效模型？简要描述

56、分布式系统中冗余的主要方式有哪些

57、在分布式系统中如何检测失效

58、如何设计可靠的 RPC 通信机制

59、什么是可靠多播？可靠多播存在的问题

60、简述两阶段提交协议？在参与者失效时如何恢复？协作者失效时如何恢复

61、分布式系统失效恢复的主要方式

63、什么是检查点方法

64、独立检查点方法？协调检查点方法

65、什么是共识？主要的共识协议有哪些？共识的使用场景有哪些

70、什么是文件系统语义模型？主要的语义模型包括哪些？简要描述其特征

71、拜占庭容错的基本思想及基本过程

73、在分布式文件系统中主要关注的问题包括哪些？并分别给出一些解决问题的方案

74、分布式机器学习的参数服务器如何理解

75、如何保障参数服务器状态的一致性