中科大分布式云计算期末考试版本4.0
需积分: 10 142 浏览量
2019-04-28
01:20:35
上传
评论 2
收藏 193KB DOCX 举报
1、分布式系统的定义：分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像
单个相关系统。
2、分布式系统的特点：各种计算机之间的差别以及计算机之间的通信方式的差别对用户来说
是隐藏的；用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行
交互。
3、分布式系统的目标：分布式系统必须能够让用户方便地访问资源；必须隐藏资源在一个网
络上分布这样一个事实；必须是开放的；必须是可扩展的。
4、透明性：分布式系统的重要目标之一是将它的进程和资源实际上在多台计算机上分布这样
一个事实隐藏起来。如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机的系统 ，
这样的分布式系统就称为透明的。
透明性的类型：
访问透明性：隐藏数据表示形式的不同以及资源访问方式的不同 位置透明性：隐藏资源所在的
位置迁移透明性：隐藏资源是否移动到另一个位置重定位透明性：隐藏资源是否在使用过程中
移动到另一位置复制透明性：使用资源是否对资源进行复制并发透明性：隐藏资源是否由若干
相互竞争的用户共享故障透明性：隐藏资源的故障和恢复
5、开放的分布式系统：系统应该符合定义良好的接口、系统应该支持应用程序的可移植性、
系统应该容易互操作。
6、系统的可扩展性：规模上可扩展、地域上可扩展和管理上可扩展。
7、扩展技术：Hide communication latencies 隐藏通信等待时间、Distribution 分布技术、
Replication/caching 复制技术。
复制缓冲：将组件复制并拷贝分布到系统各处；缓冲与复制不同的是，是否进行缓存是由要
访问资源的客户决定的，而不是资源拥有者决定。缺点是一致性问题。
8、分布式系统类型：Distributed Computing Systems 分布式计算系统、Distributed
Information Systems 分布式信息系统、Distributed Pervasive Systems 分布式嵌入系统，
又叫分布式普适系统。
9、体系结构样式：根据组件、组件之间相互的连接方式、组件之间的数据交换以及这些元素
如何继承到一个系统中。组件是一个模块单元，可以提供良好定义接口，在其环境中是可替换
的。
10、连接器 connector：在组件之间传递通信、使组件相互协调和协作。
根据组件和连接器的使用，划分成不同体系结构：分层体系结构、基于对象的体系结构、以数
据为中心的体系结构、基于时间的体系结构。
11、幂等的（idempotent）：某个操作可以重复多次而无害出。有些请求是幂等的，有些
不是，不能用某一个解决方法来处理消息的丢失问题。
点对点体系结构（P-to-P）
1、P2P 的一个常见问题是如何高效的定位节点，也就是说，一个节点怎样高效的知道在网络
中的哪个节点包含它所寻找的数据。
2、DHT 的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K 称为关键字，可以是
文件名（或文件的其他描述信息）的哈希值，V 是实际存储文件的节点的 IP 地址（或节点的其
他描述信息）。所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只
要输入目标文件的 K 值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面
的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中
的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询
报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。
Chord 算法就是解决网络内节点定位问题的一种 P2P 协议，它通过多个节点跳转找到我们所
查找的资源。
3、Chord 里面的基本要素：节点 ID：NID（node identi&er），表示一个物理机器；资源
ID ：KID （ key identi&ers ）， 原 为 键 ID ， 其 实 际 表 示一 个 资 源 ； Chord 环 ： Chord
Ring，NID 和 KID 被分配到一个大小为 2^m 的环上，用于资源分配（给某一个节点）和节点
分布，以及资源定位。首先我们说资源分配，资源被分配到 NID>=KID 的节点上，这个节点
成为 k 的后继节点，是环上从 k 起顺时针方向的第一个节点，记为 successor(k)。而节点分
布则顺时针将节点 N 由大到小放在这个环上。
现在 节点要加入系统，首先它指向其后继 ，
然后通知 ， 接到通知后将 标记为它的前
序节点（）。然后 修改路由表，下一
次 运行 询问其后继节点 的前序节
点是不是还是自己，此时发现 的前序节点已经是
。于是 就将后继节点修改为 ，并通知
自己已经将其设置为后继节点， 接到通知后将 设置为自己的前序节点。
Chord 资源定位（Key Location）：资源定位是 Chord 协议的核心功能
这个加入操作会带来两方面的影响：
正确性方面：当一个节点加入系统，而一个查找发生在 结束前，那么此时系统会
有三个状态：
所有后继指针和路由表项都正确时：对正确性没有影响。后继指针正确但表项不正确：查
找结果正确，但速度稍慢（在目标节点和目标节点的后继处加入非常多个节点时）。
效 率方 面： 当 完 成时 ， 对 查 找 效 率 的 影 响 不 会 超 过 的 时间 。当
未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。
可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响。
4.Chord 节点失败的处理
我们可以看出， 依赖后继指针的正确性以保证整个网络的正确性。但如图，若 !!
同时失效，那么 " 是不会知道 " 是它新的后继节点。为了防止这样的情况，每个节点
都包含一个大小为 的后继节点列表，一个后续节点失效了就依次尝试列表中的其他后继节点 。
可以证明，在失效几率为 的网络中，寻找后继的时间为
4、Chord 的特征和应用，特征：去中心化，高可用度，高伸缩性，负
载平衡，命名灵活。应用：全球文件系统、命名服务、数据库请求处理、
互联网级别的数据结构、通信服务、事件通知、文件共享。
第三章：进程
1、不同层次提供 4 个不同界面：①由机器指令组成，可由任何程序及
其的软硬件界面；②由机器指令组成，只有特权程序才可激活的软硬件
界面；③由操作系统提供的系统调用组成的界面；④由库调用组成的界
面，通常形成了所谓的应用程序编程接口。
2、虚拟化可采用的两种方式：①构建运行时系统，提供一套抽象指令集
执行程序—进程虚拟机；②做成一层完全屏蔽硬件但提供一个人同样指
令集的界面—虚拟机监视器。
第六章：同步化
1、物理时钟：高频振荡器（石英晶体）、计数器和保持寄存器。高频振
荡器的每次震荡使计数器减 1，档计数器减为 0 时，产生一个中断，计
数器从保持计数器中重新装入初始值。
国际原子时间（TAI）.UTC 统一协调时间 is TAI with leap seconds.
3、Lamport 逻辑时钟：
为了同步 logical clocks，Lamport 定义了一个关系叫做 happens-
before（先发生），记作 a->b 意味着所有的进程都 agree 事件 a 发生
在事件 b 之前。
在两种情况下，可以很容易的得到这个关系：①如果事件 a 和事件 b 是
同一个进程中的并且事件 a 发生在事件 b 前面，那么 a->b；②如果进程
A 发送一条消息 m 给进程 B，a 代表进程 A 发送消息 m 的事件，b 代表
进程 B 接收消息 m 的事件，那么 a->b(由于消息的传递需要时间)。如
果事件 a 和事件 b 发生在不同的进程，并且这两个进程没有传递消息，
那么既不能推到 a->b 也不能推到 b->a，这样的两个事件叫做并发事件
三个机器上各自跑着一个进程，分别为 P1，P2，P3，由于不同的机器
上的 quartz crystal 不一样，所以不同的机器上的时钟速率可能是不同
的，例如当 P1 所在的机器 tick 了 6 次，P2 所在的机器 tick 了 8 次。图
中，P1 给 P2 发送了消息 m1，m1 上附带了发送 m1 时的时钟 6，随后
P2 收到了 m1，根据 P2 接收到 m1 时的时钟，认为传输消息花了 16-
6=10 个 tick，随后，P3 给 P2 发送消息 m3，m3 附带的发送时钟是
60，由于 P2 的时钟走的比 P3 的慢，所以接收到 m3 时，本机的时钟
56 比发送时钟 60 小。这是不合理的，需要调整时钟，如图中，将 P2
的 56 调整为 61，即 m3 的发送时钟加 1。
Lamport logical clocks 的实现：每个进程 Pi 维护一个本地计数器
Ci，相当于 logical clocks，按照以下的规则更新 Ci；①每次执行一个
事件(例如通过网络发送消息，或者将消息交给应用层，或者其它的一些
内部事件)之前，将 Ci 加 1；② 当 Pi 发送消息 m 给 Pj 的时候，在消息
m 上附着上 Ci；③当接收进程 Pj 接收到 Pi 的发送的消息时，更新自己
的 Cj = max{Cj,Ci}。
向量时钟:Lamport logical clocks 的问题是：事件 a 和事件 b 实际发
生的先后顺序不能仅仅通过比较 C(a)和 C(b)来决定。Lamport logical
clocks 没 有 capture causality( 因果关 系 )，而 causality 可 以 通 过
Vector Clocks 来 capture，用 VC(a)来表示事件 a 的 Vector Clock。
有性质：VC(a) < VC(b)可以推出事件 a 发生在事件 b 之前。
为每个进程 Pi 维护一个向量 VC，也就是 Pi 的 Vector Clock，这个向量
VC 有如下属性：① VCi[i] 是到目前为止进程 Pi 上发生的事件的个数；
② VCi[k] 是进程 Pi 知道的进程 Pk 发生的事件的个数(即 Pi 对 Pj 的了
解)。每个进程的 VC 可以通过以下规则进行维护(和 Lamport logical
clocks 算法类似)：①进程 Pi 每次执行一个事件之前，将 VCi[i]加 1；②
当 Pi 发送消息 m 给 Pj 的时候，在消息 m 上附着上 VCi(进程 Pi 的向量
时钟)；③当接收进程 Pj 接收到 Pi 的发送的消息时，更新自己的 VCj[k]
= max{VCj[k],VCi[k]} ，对于所有的 k。
因果有序多播
一个进程组中，每个进程需要广播消息给其它进程(相当于一个并发更新
问题)，一个消息被 delivered 到应用层，仅当所有的 causally 发生之
前的消息都被收到。假设：Pi 给 Pj 发送消息 m，那么 Pj 可以将消息 m
交给应用层必须首先满足上面两个条件：
①VCj[i] = VCi[i] - 1
②VCi[k] <= VCj[k] for all k≠i
第一个条件的意思是指 Pj 看到了 Pi 发生的所有的事件(不包括本次发送
消息 m 的时间)；第二个条件意味着，Pj 看到了其它的所有的进程看到
的事件。以上两个条件说明，对消息 m 做下一步动作(比如本例中的将
消息 m 交给应用层)之前，所有的 m 依赖的消息都收到了。
4、互斥：
① 基于令牌的解决方案：拥有令牌这获得使用资源的权限，可以避免饿
死和死锁，但令牌可能会丢失；②基于许可的解决方案：获得其他进程
的许可来使用资源。
集中式算法:保证互斥的实现，且公平，但协调者是故障点，会出现单点
崩溃。
非集中式算法：扩展集中式协作者，进程每次访问资源需要多于一半的协作者同意即可，解决
单点故障。
分布式算法：如该进程不想进入临界区，则立即发送 OK 消息；如该进程想进入临界区，则把
自己的 request 消息时间戳与收到的 request 消息时间戳相比较。获得大多数进程的许可即
可。
令牌环算法。四种算法中集中式算法是最简单也最有效的。
第七章：一致性和复制
进行数据复制主要出于两个目的：可靠性和性能。数据一旦被复制，就会带来一致性的问题。
以数据为中心的一致性模型
1.严格一致性（strict consistency）：对于数据项 x 的任何读操作将返回最近一次对 x 进
行写操作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系统中实现这种
模型代价太大，所以在实际系统中运用有限。
2.顺序一致性：任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种
序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。也就是说，
任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。顺序一致性由
Lamport（1979）在解决多处理器系统的共享存储器时首次提出的。
3.因果一致性：所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进
程可以以不同的顺序看到并发的写操作（Hutto 和 Ahamad 1990）。假设 P1 和 P2 是有因
果关系的两个进程，例如 P2 的写操作信赖于 P1 的写操作，那么 P1 和 P2 对 x 的修改顺序，
在 P3 和 P4 看来一定是一样的。但如果 P1 和 P2 没有关系，那么 P1 和 P2 对 x 的修改顺序，
在 P3 和 P4 看来可以是不一样的。
4. FIFO 一致性：在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以
被其他所有的使用者按照顺序的感知到，而从不同使用者中来的写操作则无需保证顺序，就像
一个一个的管道一样。 相对来说比较容易实现。
5. 弱一致性：要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一
致性，是全局可见的，且只有当没有写操作等待处理时才可进行，以保证对于临界区域的访问
顺序进行。在同步时点，所有使用者可以看到相同的数据。
6.释放一致性：弱一致性无法区分使用者是要进入临界区还是要出临界区， 释放一致性使用
两 个 不 同 的 操 作 语 句 进 行 了 区 分 。 需 要 写 入 时 使 用 者 acquire 该 对 象 ， 写 完 后
release，acquire-release 之间形成了一个临界区，提供 释放一致性也就意味着当 release
操作发生后，所有使用者应该可以看到该操作。
7.入口一致性：入口一致性要求每个普通的共享数据项都要与某种同步变量关联。数据存储满
足下列条件，那么它符合入口一致性：
在一个进程获取一个同步变量签，所有由此同步变量保护的共享数据的更新都必须已经由相应
进程执行完毕。、在一个进程对一个同步变量的独占访问被允许前，其他进程不可以拥有这个
同步变量，也不能以非独占方式拥有这个同步变量、、一个进程对一个同步变量执行独占访问
之后，对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个独占访问。
以客户为中心的一致性模型
1.最终一致性：最终一致性指的是在一段时间内没有数据更新操作的话，那么所有的副本将逐
渐成为一致的。例如 OpenStack Swift 就是采用这种模型。以一次写多次读的情况下，这种
模型可以工作得比较好。
2.单调读：如果一个进程读取数据项 x 的值，那么该进程对 x 执行的任何后续读操作将总是
得到第一次读取的那个值或更新的值
3.单调写：一个进程对数据 x 执行的写操作必须在该进程对 x 执行任何后续写操作之前完成。
4.写后读：一个进程对数据 x 执行一次写操作的结果总是会被该进程对 x 执行的后续读操作
看见。
5.读后写：同一个进程对数据项 x 执行的读操作之后的写操作，保证发生在与 x 读取值相同
或比之更新的值上
第八章：容错性
、系统容错的一些要求：
（）可用性（availability）用来描述系统在给定时刻可以正确的工作。
（2）可靠性（reliability）指系统在可以无故障的连续运行。与可用性相反，可靠性是根据时
间间隔而不是任何是可以来进行定义的。如果系统在每小时中崩溃 #，那么他的可用性就超
过 $$$$$$%，但是它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每年
" 月中停机两个星期，那么它是高度可靠的，但是它的可用性只有 $"%。因此，这两种属性并
不相同。(3)安全性（safety）指系统偶然出现故障的情况下能正确操作而不会造成任何灾难。
(4)可维护性（maintainability）发生故障的系统被恢复的难易程度。
如果一个系统无法满足对用户的承诺，这个系统被称为失灵(fail)。一个系统在正常工作时会在
若干种运行状态之间变迁，一旦出现异常，则该系统进入错误状态。一个系统的错误状
态可能是导致系统失灵的原因。这里使用了一个模糊的术语“可能”，因为有的错误状态并不一
定导致系统失灵，如系统死锁是一种错误状态，当死锁被排除后，系统又可以恢复正常运行。
造成错误的原因是故障&'，故障的种类繁多，软件和硬件都可能产生故障!而且!某些场合下，
与系统无关的外部环境也可能引发故障。
2 、 故 障 分类 ： 故 障 通 常 被 分 为 暂 时 的 （ ） 、间 歇的 （#( ） 和持 久 的
资源评论
