分布式与云计算总结

《分布式与云计算总结》由会员分享，可在线阅读，更多相关《分布式与云计算总结（4页珍藏版）》请在装配图网上搜索。

1、进行数据复制主要出于两个目的：可靠性和性能。数据一旦被复制，就会带来一致性的问题。 以数据为中心的一致性模型1. 严格一致性(strict consistency):对于数据项x的任何读操作将返回最近一次对x进行写操 作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系统中实现这种模型代 价太大，所以在实际系统中运用有限。2. 顺序一致性:任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种 序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。也就是说， 任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。顺序一致性由 Lampo

2、rt (1979)在解决多处理器系统的共享存储器时首次提出的。3. 因果一致性:所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进 程可以以不同的顺序看到并发的写操作(Hutto和Ahamad 1990)。假设P1和P2是有因果关 系的两个进程，例如P2的写操作信赖于P1的写操作，那么P1和P2对x的修改顺序，在P3 和P4看来一定是一样的。但如果P1和P2没有关系，那么P1和P2对x的修改顺序，在P3 和 P4 看来可以是不一样的。4. FIFO 一致性:在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以 被其他所有的使用者按照顺序的感知到，而从不同使用者中

3、来的写操作则无需保证顺序，就像 一个一个的管道一样。 相对来说比较容易实现。5. 弱一致性:要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一 致性，是全局可见的，且只有当没有写操作等待处理时才可进行，以保证对于临界区域的访问 顺序进行。在同步时点，所有使用者可以看到相同的数据。6. 释放一致性:弱一致性无法区分使用者是要进入临界区还是要出临界区， 释放一致性使用 两个不同的操作语句进行了区分。需要写入时使用者 acquire 该对象，写完后 release ， acquire-release 之间形成了一个临界区，提供 释放一致性也就意味着当 release 操作发生后，所

4、 有使用者应该可以看到该操作。7. 入口一致性:入口一致性要求每个普通的共享数据项都要与某种同步变量关联。数据存储满 足下列条件，那么它符合入口一致性: 在一个进程获取一个同步变量签，所有由此同步变量保护的共享数据的更新都必须已经由相应 进程执行完毕。、在一个进程对一个同步变量的独占访问被允许前，其他进程不可以拥有这个 同步变量，也不能以非独占方式拥有这个同步变量、一个进程对一个同步变量执行独占访问 之后，对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个独占访问。对，然后把它们传给Reduce(规约)函数，把具有相同中间形式key的value合并在一起。 文件存储位置：源文件：

5、GFSMap处理结果：本地存储Reduce 处理结果： GFS 日志： GFS单词计数： Step 1: 自动对文本进行分割节点N8寻找K54这个资源，首先，在N8上查找后继节点为N14，发现K54并不符合54c (8;14的要求，那么直接在N8的路由表上查找符合这个要求的表项(由远及近查找)，我们发现 路由表中最远的一项N8+32-N42满足42c (8; 54，则说明N42这个点离持有K54这个资源的 节点最近(因为N42在该路由表中离N8这个节点最远)，那么此时跳到N42这个节点上继Mello Wiorlci 33yc WorlciFIcllo 1-Ia.cioop Bye f-Jaxi

6、oopBye LJa.doop Hello Haxioop0Mello Worlci Tlyc WorldT lollo LTiicloopI liitloopBye I liiduop T I ello I iaJoop续查找。N42的后继节点为N48,不符合54c (42; 48的要求，说明N48不持有资源54,此时, 开始在N42的路由表上查找，我们由远及近开始查找，发现N42+8-N51满足51c (42; 54,则 说明N51这个点离持有K54这个资源的节点最近，那么此时跳到N51这个节点上继续查找。N51节点的后继节点为N56，符合54c (51; 56,此时定位完成，N56持有资

7、源节点K54。Finger tableFinger tableStep 2:在分割之后的每一对进行用户定义的Map进行处理，再生成新的 对N8* 1N14N8- 2N14N84N14N88N21N8*16N32N8+32N42N42+ 1N48N42 2N48N42+4N48N42+8N51N42H6N1N42+32N143.Chord的节点加入：Chord通过在每个节点的后台周期性的进行stabilization询问后继节点的 前序节点是不是自己来更新后继节点以及路由表中的项successor N21)N26 N21致性描述严格所有共享访问按绝对时间排序线性化所有进程以相同的顺序看到所有的共

8、享访冋。而且，访问是根据(非唯一的)全 局时间戮排序的顺序所有进程以相同顺序看到所有的共享访问。访冋不是按时间排序的因果所有的进程以相同的顺序看到困果相关的共享访问FIFO所有进程以不同的进程提出写操作的顺彤晅看到写操作。来自不同妣程的写 操作可以不必总是以同样的顺序出现另一种不同的方罐引AS式的號述，下表是这样的一致性模型的总结Step 3:对输出的结果集归拢、排序(系统自动完成)Step 4:通过 Reduce 操作生成最后结果N32回|K30|N32|K30|致性描述弱只有在执行一次同步后，共享数据才被认为是一致的释放退出临界区时，使共享数据成为一致入口进人临界区时，使属于一个临界区的共

9、享数据成为一致以客户为中心的一致性模型1.最终一致性:最终一致性指的是在一段时间内没有数据更新操作的话，那么所有的副本将逐 渐成为一致的。例如OpenStack Swift就是采用这种模型。以一次写多次读的情况下，这种模 型可以工作得比较好。2. 单调读：如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是 得到第一次读取的那个值或更新的值3. 单调写：一个进程对数据x执行的写操作必须在该进程对x执行任何后续写操作之前完成。4. 写后读：一个进程对数据 x 执行一次写操作的结果总是会被该进程对 x 执行的后续读操作 看见。5. 读后写：同一个进程对数据项x执行的读操作之后的写

10、操作，保证发生在与x读取值相同 或比之更新的值上 时钟：在一般意义上指的是一个计算机的物理时间，每个计算机都会包括他们自己的物理时钟， 不同的计算机的物理可能会不同。时钟漂移：经过在同个地方的计算机，他们的物理也有可能会不一样，如果他们从刚刚开始相 同的时间计时开始，过了 1 过月， 1 年也可能会有快又慢，这在专业名词上讲叫做时间漂移。 本质的原因是每秒的时间偏移，经过日记月累之后，就会有可能达到 1 秒钟的差距，解决的办 法很简单，就是过一段时间之后，将时间纠正回来就可以了。UTC：全称是Coordinated Universal Time,协调世界时，又称世界统一时间，用来进行高进度 时

11、间的同步。协调世界时以原子时秒长为基础，在此时刻上尽量接近于世界时的一种时间计量 系统。同步物理时间：主要手段分为2个External synchronization，靠的是UTC协调世界时，给定一 个边界值D0,满足条件|S(t)-Ci(t)|D,另外1个是Internal synchronization,同样给定时间边界D, 相互之间进行同步， |Ci(t)-Cj(t)|D。同步系统中的时间同步：我们首先在一般情况下进行考虑，比如2个进程，相互之间只允许进 行消息传递来进行通信，如何进行事件同步，假设传输的时间为T(trans)，假设发送进程P1 发送的时间为t,则P2的时间应该设置成t+

12、T(trans)，这个很好理解，基于这个思路继续，发送的 传输时间一般不可能是固定的，可能受网络环境的影响或快或慢，所以定义了传输的时间上界 u(max)，下界u(min)，则此时的抵达时间应该设置成t+(max+min)/2， Cristian 时钟同步方法：利用了时间服务器，连接上设备并且能够接受从 UTC 资源发来的信 号进行同步，以UTC的时间作为同步的时间。定义一个进程p, 个TimeServer s,请求消息 为M(r)，接收消息M(r), M(r)中包含了从时间服务器中获取的最新的时间，进程p记录了收 发的总延时T(round),则进程p接收到消息后，他的时间应该是p(t)=M(

13、r)中的时间t+T(round)/2 The Berkeley Algorithm：用的是 Internal synchronization 的方法，给定一组计算机，选出一个 作为Coordinator，作为master，这个master选择机器中将要被同步的机器，叫做slave，通过计 算与这些机器之间进行时间交换，平均快的和慢的时间，最终达到时间一致性，在比较的过程 中，就可以排除明显偏差大的时间了。The Network Time Protocol：Cristian 和 Berkeley 算法都是偏向于用于小规模的内网中，而 Network Time Protocol则是一种在因特网上的

14、分布式时间服务。他定义了 Time Service的结构。 NTP 有下面几个特点。1、NTP提供了一个客户端可以从网络中精准同步UTC时间的客户端。2、服务端通过接口的形式方便客户端的调用。3、NTP服务器与服务器之间的时间同步是以层级控制的方式构成。1级节点同步2个2级节 点， 2(1)可能又同步2个3级节点， 2(2)也可能2个3级节点。其中的时间交互协议通过信 息之间的交换。逻辑时间和时钟：逻辑时间，从字面上理解当然不同于物理时间，在分布式系统中，运用逻辑 时间的例子也不少，假设L(i)表示的是消息事件的发生事件，当p1进程接收到的时候，就需 要对时间做递增操作， L(i) = L(i

15、) + 1，逻辑意义上的时间增加。全局有序逻辑时间-Vector Clock： Vector Clock是向量时钟，可以可以保证全局有序的逻辑时 间，通过Vti保存了 Pi进程的当前进行到的时间，当进程Pi接收到相应的消息事 件时，则在对应的位置上ti上进行ti = ti + 1的操作，当做Vector Clock向量比较的时候，需要 对V每个位置上进行比较，如果V1中的ti全部小于V2中的ti时，才算事件1早于事件2发MapReduce 的容错Worker故障:Master周期性的ping每个worker。如果master在一个确定的时间段内没有收到 worker返回的信息，那么它将把这个w

16、orker标记成失效 重新执行该节点上已经执行或尚未执行的Map任务 重新执行该节点上未完成的 Reduce 任务，已完成的不再执行Master 故障：定期写入检查点数据、从检查点恢复1、系统容错的一些要求：(1) 可用性(availability)用来描述系统在给定时刻可以正确的工作。(2) 可靠性(reliability)指系统在可以无故障的连续运行。与可用性相反，可靠性是根据时 间间隔而不是任何是可以来进行定义的。如果系统在每小时中崩溃1ms,那么他的可用性就超 过 99.9999%，但是它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每 年 8 月中停机两个星期，那么它是

17、高度可靠的，但是它的可用性只有98%。因此，这两种属性 并不相同。(3)安全性(safety)指系统偶然出现故障的情况下能正确操作而不会造成任何灾 难。4)可维护性(maintainability)发生故障的系统被恢复的难易程度。2、故障分类：故障通常被分为暂时的(transient)、间歇的(intermittent)和持久的(permanent)。现在N26节点要加入系统，首先它指向其后继N32,然后通知N32, N32接到通知后将N26 标记为它的前序节点(predecessor)。然后N26修改路由表，下一次N21运行stabilize()询问 其后继节点N32的前序节点是不是还是自己

18、，此时发现N32的前序节点已经是N26。于是N21 就将后继节点修改为N26,并通知N26自己已经将其设置为后继节点，N26接到通知后将N21 设置为自己的前序节点。这个加入操作会带来两方面的影响：1) 正确性方面：当一个节点加入系统，而一个查找发生在 stabilization 结束前，那么此时系统 会有三个状态：A. 所有后继指针和路由表项都正确时：对正确性没有影响。B. 后继指针正确但表项不正确：查找结果正确，但速度稍慢(在目标节点和目标节点的后继处 加入非常多个节点时)。2) 效率方面：当 stabilization 完成时，对查找效率的影响不会超过 O(log N) 的时间。当 st

19、abilization 未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。 可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响。4. Chord 节点失败的处理我们可以看出，Chord依赖后继指针的正确性以保证整个网络的正确性。但如图，若N14, N21, N32同时失效，那么N8是不会知道N38是它新的后继节点。为了防止这样的情况，每个节点 都包含一个大小为r的后继节点列表，一个后续节点失效了就依次尝试列表中的其他后继节点。 可以证明，在失效几率为1/2的网络中，寻找后继的时间为O(log N)。5. Chord 的特征和应用特征：去中心化，高可用度

20、，高伸缩性，负载平衡，命名灵活。应用：全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件 通知、文件共享。访问透明性：用相同的操作访问本地资源和远程资源。位置透明性：不需要知道资源的物理或网络位置(例如，哪个建筑物或IP地址)就能够访问 它们。并发透明性：几个进程能并发地使用共享资源进行操作且互不干扰。复制透明性：使用资源的多个实例提升可靠性和性能，而用户和应用程序员无须知道副本的相 关信息。故障透明性：屏蔽错误，不论是硬件组件故障还是软件组件故障，用户和应用程序都 能够完成它们的任务。移动透明性：资源和客户能够在系统内移动而不会影响用户或程序的操 作。性能透明性：当

21、负载变化时，系统能被重新配置以提高性能。伸缩透明性：系统和应用能 够进行扩展而不改变系统结构或应用算法。最重要的两个透明性是访问透明性和位置透明性 ， 它们的有无对分布式资源的利用有很大影响。有时它们统一称为网络透明性。云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系 统能够根据需要获取计算力、存储空间和信息服务。云计算的类别：崩溃性故障服务器停机，但是在停机之前工作正常云计算特点(1)超大规模(2) 虚拟化(3) 高可靠性(4) 通用性(5) 高可扩展性 (7) 极其廉价(8) 潜在的危险性生。MaPReduce模式的主要思想是将自动分割要执行的问题(例如程

22、序)拆解成Map (映射) 和Reduce (化简)的方式，流程图如下图1所示：遗漏性故障接受故障发送故障服务器不能响应到来的请求服势期不能接收到耒的消息服务期不能发送消息定时故障服务器的响应在指定时间间隔之外相应故障值故障 、使用冗余:障：如果系统是容 术是使用冗余服务期的响应不正确响应的值错误黯最好的事情就是对其他进程 破信息冗余、时间冗余和物理隐藏Google的云计算应用均依赖于四个基础组件1)分布式文件存储， GFS 2)并行数据处理模型 MapReduce 构化数据表 BigTableChubby的作用为 GFS 提供锁服务，选择 Master 节点；记录 Master 的相关 描述

23、信息通过独占锁记录Chunk Server的活跃情况、为BigTable提 供锁服务，记录子表元信息(如子表文件信息、子表分配信3)分布式锁Chubby 4)结故障的发生。彳譴冗余中添加额外的位可以使Hamming码来从传输线路上的噪声中恢复数据。关于利用信息冗余进行错误检测和纠正 在后续内容中叙述。错乱的位恢复正常。例如可以在传输的数据中添加一息、子表服务器信息)、(可能)记录MapReduce的任务信息、为第三方提供锁服务与文件存储GFS的作用存储BigTable的子表文件、为第三方应用提供大尺寸文件存储功能 文件读操作流程：API与Master通信，获取文件元信息、将 时间冗余中，执行一

24、个动作，如果需要就再次执行。使用事务就是这种方法的一个例子。如果 一个事务中止，那么它就可以无害的重新执行。当错误是临时性或间歇性时，时间冗余特别有 用。TCP/IP协议中的重传机制，是另外一个例子。 物理冗余中，通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障成 为可能。物理冗余可以在硬件上也可以在软件上进行。其中，一种著名的设计是TMR (三倍 模块冗余，Tiple Modular Redundancy )。在包括TMR的系统中，每个关键模块中的部件都被 复制了三份，采用多数表决的方法，确保当某些某块中的单个部件发生故障时，系统还可以正 确的运行。 两种基本的策略用于错

25、误处理过程。一种方法是在信息块中包含足够的冗余信息，以便推断出 这些数据中肯定有哪些内容，即使用纠错码的策略。另一种也是包含一些冗余信息，但是这些 信息只能推断出发生了错误，却推断不出发生了哪些错误，即使用检错码的策略。使用纠错码 的技术通常也被称为前向纠错。DHT的主要思想是：首先，每条文件索引被表示成一个(K,V)对，K称为关键字，可以是文件 名(或文件的其他描述信息)的哈希值，V是实际存储文件的节点的IP地址(或节点的其他 描述信息)。所有的文件索引条目(即所有的(K,V)对)组成一张大的文件索引哈希表，只要 输入目标文件的 K 值，就可以从这张表中查出所有存储该文件的节点地址。然后，再

26、将上面 的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中 的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询 报文路由到相应的节点即可(该节点维护的哈希表分块中含有要查找的(K,V)对)。1. Chord 里面的基本要素节点ID： NID(node identifier)，表示一个物理机器，m位的一个数字(m要足够大以保证不 同节点的NID相同的几率小的可以忽略不计)，由节点机器的IP地址通过哈希操作得到。 资源ID； KID(key identifiers),原为键ID,其实际表示一个资源(因为Key与一个资源value 哈希

27、绑定)，故在本文中统称资源ID (这样比较直观)，m位的一个数字(m要足够大以保 证不同资源的KID相同的几率小的可以忽略不计)，由Key通过哈希操作得到。 常哈希函数：较之一般哈希函数，节点的加入和离开对整个系统影响最小，另外还有一些优势 在此不赘述。在Chord中使用SHA-1来进行常哈希计算。Chord环：Chord Ring, NID和KID被分配到一个大小为2Am的环上，用于资源分配(给某 一节点)和节点分布，以及资源定位(注：在这个环上的ID为0-2Am-1)。首先我们说资源 分配，资源被分配到NID=KID的节点上，这个节点成为k的后继节点，是环上从k起顺时 针方向的第一个节点，

28、记为successor(k)。节点分布则顺时针将节点N由大到小放在这个环上。 m=6的环，有10个节点，5个资源，K10的后继节点为N14，也就是说K10被分配给了 N142. Chord资源定位(Key Location):资源定位是Chord协议的核心功能简单的资源定位方法；节点n寻找KID为id的资源，此时节点n首先问询是否在下一个节点 上 (find_successor)，这要看资源k的KID是否在该节点NID和下一个节点的NID之间，若 在则说明资源k被分配给了下一个节点，若不在则在下一个节点上发起同样的查询，问询下下 一个点是否有该资源。节点N8寻找K54这个资源，发现下一个节点N

29、14不合符54c (8; 14,于是N14发起同样的搜 索，然后一跳一跳后直到节点N56满足54c (51; 56，于是得知资源K54在N56这个节点上。 可伸缩方法：在每个节点N上都维护了最多有m项(m为ID的位数)的路由表(称为finger table),用来定位资源。这个表的第i项是该节点的后继节位置，至少包含到2人(i-1)后的位置。 每个节点只包含全网中一小部分节点的信息。每个节点对于临近节点负责的位置知道的更多，比如N8节点对于N14负责的位置知道3处， 而对N21负责的位置只知道1处。 路由表通常不包含直接找到后继节点的信息，往往需要询问其他节点来完成。 当在某个节点上查找资源时

30、，首先判断其后继节点是不是就持有该资源，若没有则直接从该节 点的路由表从最远处开始查找，看哪一项离持有资源的节点最近(发现后跳转)，若没有则说 明本节点自身就有要寻找的资源。如此迭代下去。根据指定的读取位置和读取长度，API发起并发操作，分别从若干ChunkServer上读取数据、API组装所得数据，返回结果MapReduce 的作用对 BigTable 中的数据进行并行计算处理(如统计、归类等)使用BigTable或GFS存储计算结果BigTable的作用为 Google 云计算应用(或第三方 应用)提供数据结构化存储功能 类似于数据库、 为应用提供简单数据查询功能(不支持联合查询)为 Ma

31、pReduce 提供数据源或数据 结果存储BigTable的存储与服务请求的响将软件作刈服务SaaS (Software as a Service)将平台柞为服务PaaS (Platform as a Service)特基础设施作为服务laaS (infrastrueLure as a Service)如；Salesforce online CRM如：Google App EngineMicrosoft Windows Azure如：Amazon EC2/S3划分为子表存储，每个子表对应一个子表文件，子表文件存储于GFS之上、BigTable通过元数据组织子表、每个子表都被分配给一个子表服务器

32、、一个子表服务器可同时分配多个子表、子表服务器负责对外提供服务，响应查询请求MapReduceHadoopOrgGoogleYahoo/ApacheImplC+JavaDistnbuted File SysGFSHDFSData BaseBigtableHBaseDistnbuted lock mgrChubbyZooKeeperHadoop云计算应用HBase MapReduceHDFSGoogle云计算应用BigTable MapReduce ChubbyJGFSHDFS为了做到可靠性(reliability)创建了多份数据块(data blocks)的复制(replicas)，并 将它们

33、放置在服务器群的计算节点中(compute nodes) , MapReduce就可以在它们所在的节点 上处理这些数据了。HDFS 关键运行机制-保障可靠性的措施1) 一个名字节点和多个数据节点-数据复制(冗余机制)2) 存放的位置(机架感知策略) -故障检测3) 数据节点-心跳包(检测是否宕机) -块报告(安全模式下检测)数据完整性检测(校验和比较)4) 名字节点(日志文件，镜像文件) -空间回收机制HDFS 关键运行机制-读文件流程客户端缓存、流水线复制、并发写控制、客户端联系NameNode，得到所有数据块信息，以及数据块对应的所有数据服务器的位置信息、 尝试从某个数据块对应的一组数据服

34、务器中选出一个，进行连接(选取算法未加入相对位置的 考虑)、数据被一个包一个包发送回客户端，等到整个数据块的数据都被读取完了，就会断 开此链接，尝试连接下一个数据块对应的数据服务器，整个流程，依次如此反复，直到所有想 读的都读取完了为止HDFS 与 GFS 比较中心服务器模式的差异：GFS：多台物理服务器，选择一台对外服务，损坏时可选择另外一台 提供服务；HDFS：单一中心服务器模式，存在单点故障。原因：Hadoop缺少分布式锁服务 子服务器管理模式差异：GFS： Chunk Server在Chubby中获取独占锁表示其生存状态，Master 通过轮询这些独占锁获知Chunk Server的生

35、存状态HDFS： DataNode通过心跳的方式告知NameNode其生存状态GFS 中, Master损坏时，替补服务器可以快速获知Chunk Server的状态；HDFS 中, NameNode 损坏后，NameNode恢复时需要花费一段时间获知DataNode的状态。在添加数据存储节点时， GFS的伸缩性较HDFS要好 原因：Hadoop缺乏分布式锁服务e Intenriedkite values wittnhti same (key.can be (and often are) m the ones in map()分布式系统的定义：分布式系统是若干独立计算机的集合，这些计算机对于用户

36、来说就像是单 个相关的系统（中间件）。2.分布式的目标：分布式系统必须能够让用户方便地与资源连接； 必须隐藏资源在一个网络上分布这样一个事实；必须是开放的；必须是可扩展的。3.透明性： 一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统；3.透明性的种类： 访问透明性：隐藏不同数据表示形式以及资源访问方式的不同。位置透明性：隐藏资源在系统 中的物理位置。并发透明性：隐藏资源是否由若干相互竞争的用户共享。持久性透明性：隐藏 资源位于内存中还是硬盘中。迁移透明性：指分布式系统中的资源移动不会影响该资源的访问 方式。复制透明：指对同一个资源存在多个副本的隐藏。5. 一个开放的分布式系统就是根

37、据 一系列准则来提供服务，这些谁则描述了所提供服务的语法和语义。6.可扩展性至少可以通 过 3 个方面度量：规模上扩展用户和进程的数量、地域上可扩展节点之间的最大距离、管 理上可扩展管理域的数量。 7. 分散式算法与集中式相比不同的特性：没有任何计算机拥有 关于系统状态的完整信息；计算机只根据本地信息做出决策；某台计算机的故障不会是算法崩 溃；没有存在全局性时钟的假设。 8. 扩展技术：隐藏通信等待时间避免等待远程服务对请 求的响应，做其它工作。 分布技术：把某个组件分割成多个部分，然后再将它们分散到系统中去（如 DNS、WWW）。 复制/缓冲：将组件复制并拷贝分布到系统各处；缓冲与复制不同的

38、是，是否进行缓存是由要 访问资源的客户决定的，而不是资源拥有者决定。缺点是一致性问题。 9. 分布式系统的分类： 分布式计算系统、分布式信息系统、Distributed Pervasive Systems。10.分布式事务处理的特 性，原子性；一致性：事务处理不会违反系统的不变性；独立性：并发的事务处理不会相互干 扰；持久性：事务处理一旦提交，所发生的改变是永久性的。6.根据组件和连接器的不同， 分布式系统体系结构最重要的有4种，它们是：分层体系结构、基丁对象的体系结构（MVC-J2EE）、以数据为中心的体系结构、基于事件的体系结构7.在客户-服务器的体系结构 中，应用分层通常分为3层，用户接

39、口层、处理层和数据层。8.有两种类型的分布式操作系 统，多处理器操作系统和多计算机操作系统9. 系统体系结构：软件体系结构的具体实例。确定了软件组件、这些组件的交互以及它们的 位置就是软件体系结构的一个实例。13.分布式软件体系结构主要分集中式、非集中式和各种 混合形式三大类。其非集中式体系结构又分为结构化的点对点、非结构化的点对点、超级对等 体三种。集中式体系结构-客户/服务器体系结构：客户机怎么告诉请求消息丢失：超时。 客户机怎么检测请求丢失和回复丢失的区别：最多一次服务，至少一次服务。 幂等性：一个操作重复多次而没有害处就说它是幂等的。10. 客户/服务器结构的应用程序通常划分为三层，它

40、们是：用户接口层、处理层和数据层11. 在结构化点对点体系结构中覆盖网络是用一个确定性的过程来构成的，这个使用最多的进 程是通过一个分布式哈希表来组织进程的。新型体系结构：垂直分布（不同功能的分布）、水平分布（相同功能的分布）、对等型（P2P）分布。 覆盖网络：建立在另一个网络上的网络，属于应用层，很少考虑网络层物理层的问题。 P2P网络是建立在Internet之上的一种覆盖网络。P2P Chord是基于分布式Hash （DHT）的结构化P2P16. 一个线程独立地执行它自己的程序代码。线程系统一般只维护用来让多个线程共享CPU 所必需的最少量信息。17. 有两种实现线程线程包的基本方法：一是

41、可以构造一个完全在丽模式干执行的线程；二 是由内核来掌管线程并进行调度。18. 分布式系统中的多线程通常有：多线程用户和多线程服务器两大类型。而以分发器/工作者 模型组织起来的多线程服务器是最为流行的一种。19. 虚拟化可采用两种方法，一是构建一个运行时系统，提供一套抽象指令集来执行程序。二 是提供虚拟机监视器19. 在引进线程的操作系统中，调度和分派的基本单位是线程，拥有资源的单位是进程57. 常用的进程调度算法有先来先服务、优先数法和轮转法58. 进程的三个基本状态是就绪、执行、等待（阻塞）。59. 进程是程序在一个数据集合上的运行过程是系统进行资源分配和调度的一个独立单位60. 进程通常

42、的四个特征是动态性,并发性,独立性，异步性61. 解决死锁的基本方法包括预防死锁，避免死锁,死锁检测,死锁恢复 互斥锁：防止多个线程同时读写某一块内存区域；信号量：用来暴走多个线程不会相互冲突。 操作系统的设计：（1）以多进程的形式，允许多个任务同时执行；（2）以多线程形式，允许 单个任务分成不同的部分运行； （3）提供协调机制，一方面防止进程之间和线程之间产生冲 突，另一方面运行进程之间和线程之间共享资源。34. 在流与服务质量（QOS）描述中，服务质量特性指的是数据传输所要求的比特率、创建会话 的最大延时、端到端的最大延时、最大延吋抖动以及最大往返延吋等。35. 流同步类型，一是在离散数据

43、流与连续数据流之间保持同步；二是连续数据流之间的同步。36. 在流同步的机制中，需要研究的两个问题是：一个是两个流同步的基本机制；二是在网络 环境下这些机制的分布式版本。40.在基于gossip的数据通信中，通常采用感染协议传播信息。流行的传播模型是anti-entropy46. 向量时钟能捕获囚果关系。创建向量时钟是让每个进程Ti维护一个向量VCi来完成。47. 互斥集中式算法的优点是易于实现、很公平、保证了顺序 致性。而缺点是协作者是单个 故障点，如果它崩溃了，整个系统可能瘫痪48. 分布式互斥算法的优点是不会发生死锁与饿死现象，也不存在单个故障点。其缺点是单个 故障点被n个故障点所代替，

44、所以故障率高；要求更多的网络流量。49. 分布式系统中的互斥算法有四种类型，一是集中式算法、二是非集中式算法、三是分布式 算法、四是令牌环算法。50. 分布式系统中，传统的选举算法有两种，一是欺负选举算法；二是环选举算法。53. 令牌环算法每次进/出需要的消息数是 L-；进入前的延迟是 Lnl；但存在令牌丢失和 进程崩溃的问题。66.在逻辑时钟算法中，Lamport定义了一个称作“先发生”的关系，表达式a b表示a在 之前发生。先发生关系是一个传递关系。4. 集群计算系统一个突出的特征是它的同构性；它提供了最大限度的分布式透明性。可用于 单个程序在多台计算机上并行地运行。5. 网格计算系统具有

45、高度的异构性：其硬件、操作系统、网络、管理域和安全策略等都不尽 相同。6. 网格计算系统一个关键问题是如何把来自不同计算机组织的资源集中起来，使一组人或机 构进行协调工作。12. 超级对等体通常是维护一个素引或充当一个代理程序的结点。15. 分布式的自主系统指的是自我管理、自我恢复、自我配置和自我优化等各种自适应性。20. 在服务器的组织结构中，迭代服务器是自己处理请求，将响应返回给客户；而并发服务器 将请求传递给某个独立线程或其他进程来处理。21. 服务器集群在逻辑上由三层组成，第一层是逻辑交换机；第二层是应用/计算服务;第三层 是文件/数据库系统。23. 进程对资源的绑定有三种类型：一是按

46、标识符绑定；二是按值绑定；三是按类型绑定。而 三种类型的资源对机器的绑定是未连接资源、附着连接资源和紧固连接资源。24. 中间件是一种应用程序，它在逻辑上位于应般中，但在其中包含有多种通用协议，这些 协议代表各自所在的层，独立于其他更加特别的应用。25. 在RPC操作中，客户存根的功能是将得到的参数打包成消息，然后将消息发送给服务器 存根。26. 所有DCE的底层编程模型都是客户-服务器模型。而DCE本身的一部分是由分布式文件服 务、目录服务、安全服务以及分布式时间服务等构成的。27. IDL编译器的输出包括三个文件，它们是头文件、客户存根和服务器存根28. 在面向消息的通信中，通常分为面向消

47、息的瞬时通信和持久通信两种机制。29. 在面向消息的瞬时通信中，通常采用套接字接口和消息传递接口。30. 在面向持久的通信中，消息队列系统为持久异步通信提供多种支持。它提供消息的中介存 储能力。31. 在消息队列系统中，队列由队列管理器来管理，它与发送或接收消息的应用程序直接交互。32. 在消息队列系统中，转换是由队列网络中特定结点完成的，这些结点称为消息转换器37. 应用层多播的基本思想是结点组织成一个覆盖呻，然后用它来传播信悬给其成员。一个 重要的因素是网络路由器不在组成员中。38. 在覆盖网络构建时，主要有两种方法，一种是结点本身直接组织成树；另一种是结点组织 成一个网状网络39. 应用

48、层多播树的质量通常以三种不同的尺度来度量，一是链接树；二是相对延时补偿；三 是树成本41. 分布式系统中，有三种不同的命名系统，它是无层次命名；结构化命名和基丁属性的命名。42. 在无层次命名中，通常有广播和多播、转发指针、基于宿主位置、分布式散列表、分层结 构等方法实现实体定位。43. 基于属性的命名系统实现的方式有两种。一种是分层实现，使得目录项集合形成了分层的 目录信息树。而另一种是非集中式实现，它是采用映射到分布式散列表的方式。45. 一次将所有的消息以相同的顺序传送给每个接收的多播操作称为全序多播。Lamport时间 戳可以用于以完全分布式的方式实现。52.高速缓存相关性协议的设计与

49、实现是基于两种策略的：一是相关性检测策略；二是相关性 实施策略。54. 在开发的持久一致性协议中，有三种限定的偏差：它们是限定复制的数字偏差、限定复制 的新旧程度偏差和限定顺序偏差。65.在名称解析的实现中，通常采用两种方法，一是迭代名称解析；二是递归名称解析。1. 下面特征分别属于计算机网络和分布式计算机系统，请加以区别：分布式计算机是指系统内部对用户是完全透明的;系统中的计算机即合作又自治；系统可以利 用多种物理和逻辑资源，可以动态地给它们分配任务。计算机网络是指互连的计算机是分布在不同地理位置的多台独立的“自治计算机”。2. 点到点通信子网的拓扑结构主要有以下几种：星型、环型、树型、网状

50、型，请根据其特征 填写相应结构。网状型：结点之间的连接是任意的，没有规律。环型：节点通过点到点通信线路连接成闭合 环路。星型：节点通过点到点通信线路与中心结点相连；树型：结点按层次进行连接。3. 分布式计算系统可以分为两个子组，它们是集群讣算系统和网格讣算系统10. DCE本身是由多个服务构成的，常用的有分布式文件系统、目录服务、安全服务以及分 布式时间服务等。12. Windows NT的结构借用了层次模型和客户/服务器两种模型。17.操作系统通常可以分为以下几种类型：批处理系统、分时系统、实时系统、网络操作 系统和分布式操作系统20. 在面向流的通信中，为连续提供支持数据流的模式有异步传输

51、模式、同步传输模式和等时 传输模式三种。21. 在流同步机制，通常有在数据单元层次上进行显式同步和通过高级接口支持的同步两种。24.在名称解析的实现中，通常采用两种方法，一是迭代名称解析；二是递归名称解析。28. 在以数据为中心的一致性模型中，顺序一致性是指“任何执行结果都是相同的，所有进程 对数据存储的读/写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺 序出现在这个序列中”。29. 在因果一致性中，所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器 可以以不同的顺序看到并发的写操作。30. 以客户为中心的一致性模型中，满足最终一致性的数据存储具有以下属性：没有

52、更新操作 时，所有副本逐渐成为相互完全相同的拷贝。31. 以客户为中心的一致性模型中，一个写操作总是在同一进程执行的后续读操作之前完成， 而不管这个后续的读操作发生在什么位置。32. 在一致性协议中，基于主备份的协议比较盛行，它包括远程写协议和本地写协议两种。33. 在一致性协议中，复制的写协议包括主动复制和基于多数表决的一致性协议两种。34. 在容错性中，故障通常被分为暂时性故障、间歇性故障和持久性故障三大类型。35. 如果系统是容错的，使用冗余掩盖故障的方法有信息冗余、时间冗余和物理冗余三种。36. 在可靠的客户-服务器通信中，失败时的RPC系统中发生客户不能定位服务器、请求消息 丢失、服

53、务器崩溃、应答消息丢失和客护端崩溃等5种形式。37. 在原子多播里，消息排序通常有4种不同的排序方法，它们分别是：不排序的多播、FIFO 顺序的多播、按因果关系排序多播和全序多播。38. 容错性的基本要求是从错误中恢复，本质上有两种形式的错误恢复，一是読恢复；另一 种是前向恢复。50.在容错性中，人们定义了一些不同类型的故障，主要的有崩溃性故障、遗漏性故障、定时 性故障、响应性故障以及随意性故障等五大类。90.在容错性中，消息日志的基本思想是：如果消息的传输可以重放，那就能够到达一个全局 -致的状态而不需要从稳定存储中恢复该状态。1. 分布式系统中的扩展技术通常有：隐藏通信等待时间 、复制技术

54、；2. 下面属于分布式混合体系结构的是：边界服务器系统、协作分布式系统；7. 在迁移与本地资源的关系中，资源对机器的绑定有：未连接资源、附着连接的资源、紧固 连接的资源8. 在DEC 中, IDL中的头文件包含：唯一标识符、类型定义、常量定义与函数原型16. IDL编译器的输出包括的文件是：文件头、客户存根、服务器存根9. 在面向消息的持久通信中，消息队列系统中的基本接口有： Put、get10. 在流同步中，同步机制要搞清楚问题：两个流同步的基本机制、在网络下机制的版本1. 网络体系结构可以定义为：建立和使用通信硬件和软件的一套规则和规范2. 在0SI参考模型中，数据链路层的数据服务单元是：

55、帧3. 下面属于分布式计算系统的是：集群计算、网格计算4. 目前分布式信息系统按集成可分为事务处理系统、企业应用集成7. DNS 属于（应用层）层协议。9.对于域名：, DNS服务器查找顺序是：先查找.com域，再查找test主机12. 远程客户端登录终端服务器必须提供一定的信息，必要的信息:用户名、服务器IP地址。13. 在多播通信中，应用层多播树的质量的度量尺度：链接树 、相对延时补偿、树成本14. 以多播流方式传递内容时只能采用（广播发布点）类型的发布点。15. DNS 名称空间是分层组织的一棵有根树，标识符是有：字母和数字组成17.下列属于流同步的是：离散数据流与连续数据流之间同步、口

56、型同步19. 多线程服务器可行的设计方法:多线程文件服务器/单线称文件服务器/作为有限状态机20. 与迭代名称解析比较，递归名称解析的优点是：缓存结果更为有效、能减少通信开销23. 分布式系统的全局状态是指：每个进程的本地状态、当前正在传输中的消息24. 面向消息的中间件模型一般提供：持久异步通信、电子邮件、工作流25. 在分布式系统中，实现事务的方法是：为进程分配私有工作空间、做写前日志26. 并发控制的总体思想是：正确调度相冲突的操作27. 下面属于进程间同步算法的是：选举算法、互斥算法28. 严格一致性中存在的问题是：依赖于绝对的全局时间29. 属于“以数据为中心的一致性模型”：线性化和

57、顺序一致性、因果一致性、FIFO 一致性30. 属于“以客户为中心的一致性模型”：单调读一致性、写后读一致性、读后写一致性31.下面属于一致性协议的是：基于主备份的协议 、复制的写协议32.基于主备份的协议是指：负责协调X上的远程写操作、负责协调X上的本地写操作34.在可靠多播通信中，解决反馈拥塞的方法是：无等级的反馈控制、分等级的反馈控制35.实现可靠原子多播的方法是：消息排序、虚拟同步三简答题（每小题n分，共m分）7在深度为k的分层定位服务中，当移动实体改变它的位置时，最多需要更新多少条位 置记录？答：移动实体改变位置会产生删除操作和插入操作，删除操作至少需要更新 k 条位置 记录。同样，

58、插入操作也需要更新k条位置记录。最后，删除与插入更新移动实体位置的记录 共需要 2k+1 条。8要使用Lamport时间戳实现全序多播，是不是每个消息都必须要被严格地确认？ 答：不需要，任何类型的消息，只要它的时间戳大于所接收到的消息的时间戳，就可以被 加入消息队列，使用Lamport时间戳实现全序多播。9.许多分布式算法需要使用协调进程。讨论一下，这样的算法实际上可以在什么程度上 被看作为分布式的？答：在集中式算法中，一般会选择一个固定的进程作为协调者，其它的进程可以分布在不 同的机器上运行。分布式算法中也同样可以引入协调进程，但是，这个进程并不是固定的，它 是从作为算法一部分的进程中选择的

59、。因此，使用协调进程并不会影响算法的分布性。11. 请解释DNS如何进行复制，以及它实际运行很好的原因。答: DNS进行复制的基本思想是：域名服务器可以缓存以前查找过的结果。由于DNS的 名称到地址的映射很少更改，因此，这些结果可以缓存很长一段时间。12. 简述进程与程序的联系和区别 答：（1）联系：一个进程可以涉及到一个或几个程序的执行；一个程序可以对应一个或 多个进程，即同一程序段可以在不同数据集合上运行，可构成不同的进程，例如打印输出程序 段，例如同一高级语言编译程序与多个用户源程序。（2）进程和程序的区别主要体现在： 1）进程是动态的，具有一定的生命周期，而程序是 静态的； 2）进程可

60、并发执行，而没有创建进程的程序是不能执行的； 3）进程是操作系统中申 请和分配资源的基本单位，而没有创建进程的程序是不能申请资源的； 4）进程包括程序、数 据和进程控制块； 5）同一程序的多次执行对应多个进程15. 原子多播的可扩展性重要到哪种程度上？ 答：它取决于一组包含多个进程的状态。如果进程为故障容错进行了复制，拥有少量的副本可能就足够了，在这种情况下，可扩展性几乎不成问题。如果是由不同进程构成的组，可扩 展性就可能成了一个问题。当为了性能而复制时，原子多播自身可能超出负荷的能力。16. 在两阶段提交协议中，为什么即使在参与者们选择一个新的协调者的情况下也不会 完全消除阻塞？答：因为选举

61、结束后，新的协调者也同样可能会崩溃。在这种情况下，其余的参与者也不 能做出最后决定，因为这需要由新当选的协调者发起选举。19. 一个网络中，DNS服务器应该部署在什么地方最合适？在一个网络中，DNS服务器应该 部署在客户端可以集中访问的网络位置上。20. 进程间同步和互斥的含义是什么?答：进程间同步是并发进程之间存在的相互制约和相互 依赖的关系。进程间互斥是若干进程共享一资源时，任何时刻只允许一个进程使用。1. 进程并发工作。（1）若对资源分配不加限制，会发生什么情况 （1）多个进程动态地共享系统 的资源可能会产生死锁现象。死锁的产生，必须同时满足四个条件：互斥、等待、非出让、 循环等待。 （2）为保证进程正确工作，应采用怎样的资源分配策略 （2） 银行家算法分配资源的 原则是：8. 一个最完备的分布式体系由以下模块组成：分布式任务处理、分布式节点注册和查询、分 布式数据库、分布式cache、分布式文件、网络通信、监控管理、分布式编程语言、分布式算 法。云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资