分布式系统期末复习材料 LeeRinji

感谢我的室友DZH

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

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

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

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

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

策略

机制

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

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

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

错误。

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

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

9、 分布式的分层结构

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

11、 Chord 结构的生成和查找

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

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

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

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

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

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

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

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

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

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

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

负载分布

灵活性

强/弱可迁移性

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

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

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

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

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

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

avatar

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

多播

广播

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

反熵模型

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

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

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

SSP Chain

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

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

查询

插入

28、 名称解析闭包

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

硬链接

软链接

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

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

基本问题

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

三层名称空间

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

迭代命名解析

递归名称解析

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

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

精度

准确度

同步

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

Berkeley 算法

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

36、 逻辑时钟?及算法

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

算法:为每一个时间 e 分配一个时间戳 C(e)使其满足以下属性:

37、 什么是全序广播

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

关键区

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

解决互斥访问

39、 因果有序的多播传播

与全序多播的关系

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

观察

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

调整

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

p_j 推迟发送消息 m 直到

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

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

40、 Ricart & Agrawala 互斥算法

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

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

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

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

42、 数据一致性模型

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

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

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

连续一致性

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

顺序一致性

因果一致性

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

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

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

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

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

读写一致性

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

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

写读一致性

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

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

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

位置放置的三种⽅法

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

内容放置

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

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

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

avatar

avatar

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

远程写

本地写

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

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

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

可靠性

可用性

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

崩溃性故障

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

定时故障

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

随意性故障

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

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

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

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

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

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

参与者失效:

协作者失效

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

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

63、 什么是检查点方法

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

独立检查点方法

协调检查点方法

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

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

主要变种

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

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

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

avatar

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

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

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

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

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

用一个副官模型来理解:

  • 假设只有 3 个人,A、B、C,三人中如果其中一个是叛徒。当 A 发出进攻命令时,B 如果是叛徒,他可能告诉 C,他收到的是“撤退”的命令。这时 C 收到一个“进攻”,一个“撤退“,于是 C 被信息迷惑,而无所适从。
  • 如果 A 是叛徒。他告诉 B“进攻”,告诉 C“撤退”。当 C 告诉 B,他收到“撤退”命令时,B 由于收到了司令“进攻”的命令,而无法与 C 保持一致。

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

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

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

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

同步解决方案

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

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

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

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

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

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

参数服务器的五个关键特征(设计理念):

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

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

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

流程

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

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

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

master node

nodes

services

工作流程

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

网络