2017电子科技大学分布式系统考点

第一章概述分布式系统的目标资源共享RESOURCESHARING计算机通过网络连接起来，并在这个范围内有效地共享资源硬件的共享，软件的共享，数据的共享，服务的共享媒体流的共享（动态的资源形式）协同计算COLLABORATIVECOMPUTING并行计算，分布式计算分布式系统是指把多个处理机通过网络互连而构成的系统，系统的处理和控制功能分布在各个处理机上。分布式系统的问题源于下面三个特点并发性（CONCURRENCE多个程序（进程，线程）并发执行，共享资源没有全局时钟GLOBALCLOCK每个机器都有各自的时间，没有办法做到统一，程序间的协调靠交换消息故障独立性INDEPENDENTFAILURE一些进程出现故障，并不能保证其它进程都能知道分布式的挑战异构性网络协议,硬件,操作系统,编程语言,开发者实现方式的不同开放性可扩展性安全性机密性防止未经授权的个人访问资源完整性防止数据被篡改和破坏可用性防止对所提供服务的干扰故障处理检测故障,屏蔽故障,故障容错,故障恢复,冗余策略并发正确性多个进程并发访问共享资源，要保证被访问数据的正确性，不能出现不一致。性能多个并发操作保证性能透明性访问透明使用同样的操作去访问本地资源和远程资源。位置透明访问资源的时候，不需要知道资源的位置。并发透明几个进程同时访问资源，互不干扰。复制透明使用多个资源的副本来提高可靠性和性能，用户或者应用程序开发者并不需要了解副本技术。故障透明,移动透明,性能透明,扩展透明第二章系统模型结构模型构成系统各部分（COMPONENTS,COMPUTERS,PROCEDURES的位置、角色和它们之间的关系，它定义了系统的各组件之间相互交互的方式以及它们映射到下面的计算机网络的方式。客户/服务器结构对等结构（客户/服务器模型的变种）基础模型体系结构模型所涉及的问题系统中的主要实体是什么它们如何交互影响他们单个和集体行为的特征是什么模型的目的显式地表示有关正在建模的系统假设；给定这些假设，就什么是可行的，什么是不可行的给出结论。交互模型通信性能不可能维护一个全局时间概念同步分布式系统进程执行每一步的时间有一个上限和下限。每个在网络上传输消息可在已知时间范围内接收到。每个进程的局部时钟相对于实际时间的漂移是在已知的范围内。异步分布式系统没有可预测的时限进程执行速度每一步都可能需要任意长的时间消息传递延迟收到一个消息的等待时间可能任意长时钟漂移率漂移率可能是任意的故障模型遗漏故障OMISSIONFAILURES随机故障ARBITRARYFAILURES时序故障TIMINGFAILURES安全模型进程的安全性通信信道的安全性对象的安全性交互模型时序问题，不能一个人看到的回答先于问题到达。故障模型消息丢失，保证每个组成员都要收到相同的消息。安全模型消息的加密。第三章时间和全局状态重点CRISTIAN方法理解应用条件存在时间服务器，可与外部时间源同步消息往返时间与系统所要求的精度相比足够短协议进程P根据消息MR，MT计算消息往返时间TROUND根据服务器在MT中放置的时间T设置时钟为TTROUND/2精度分析若消息的最小传输时间为MIN，则精度为TROUND/2MIN注意可暂时不考虑从A到B和从B到A的消息传输路径不同而导致的传输时间不同S在MT中放置时间最早点是在P发出MR之后的MIN应答消息到达时S的时钟时间位于TMIN,TTROUNDMIN上面的范围宽度是TROUND2MIN网络时间协议NTP设计目标可外部同步使得跨INTERNET的用户能精确地与UTC通用协调时间同步高可靠性可处理连接丢失，采用冗余服务器、路径等扩展性好大量用户可经常同步，以抵消漂移率的影响安全性强防止恶意或偶然的干扰协议结构层次结构主服务器直接与外部UTC同步同步子网可重新配置NTP三种同步模式组播MTP时间服务器SMRTTTROUNDMINTTROUND/2TMINTTROUND适用于高速LAN准确度较低，但效率高过程调用与CRISTIAN算法类似准确度较低对称模式按对称模式操作的一对服务器交换有时序信息的消息保留时序信息准确度最高如下图所示，有P1、P2、P3三个进程以及发生的事件A，B，C，假定逻辑时钟的初始值为0。1为每个事件标定LAMPORT时钟。2为每个事件标定全序逻辑时钟。3为每个事件标定向量时钟。4割C1，C2是否是一致割集，如果不是为什么P1P20CEFGHDABC1P3C2LAMPORT时钟全序逻辑时钟（T,PI）PI为进程号向量时钟每个进程维护它自己的向量时钟VI，如图3个进程3个分量ABCDEFM1M22,0,01,0,02,1,02,2,02,2,20,0,1P1P2P3PHYSICALTIME全局状态单个进程状态的集合SS1,S2,SN割集系统全局历史的子集C割集的一致性割集C是一致的对于所有事件EC,FEFC一致的全局状态对应于一致割集的状态S0S1S2“快照”算法进程PI的标记接收规则PI接收通道C上的标记消息IFPI还没有记录它的状态PI记录它的进程状态；将C的状态记成空集；开始记录从其他接入通道上到达的消息ELSEPI把C的状态记录成从保留它的状态以来它在C上接收到的消息集合ENDIF进程PI的标记发送规则在PI记录了它的状态之后，对每个外出通道C在PI从C上发送任何其他消息前PI在C上发送一个消息标记分布式调试判定可能的从初始状态开始，遍历可达状态的网格。L0STATESS01,S02,S0NWHILE对所有可能的SSTATES，SFALSELL1REACHABLESH中从一些SSTATES可到达的状态LEVELSLSTATESREACHABLEENDWHILE输出“可能的”见书上P368的求解明确的可能的和明确的区别从初始状态开始，经过从这点开始可到达的所有一致状态，在每一步判定。当判定为T时停止计算。为了判定明确的，监控器进程必须试图找到所有线性化走向必须经过的判定为T的状态集第四章协调和协定重点基于环的算法构架（进程安排在一个逻辑环中，每个进程PI与环中下一个进程P（I1）MODN有一个通信信道）满足安全性和活性要求，但不满足顺序要求。客户延迟MIN0个消息，正好收到令牌MAXN个消息，刚刚传递了令牌同步延迟MIN1个消息，进程依次进入临界区MAXN个消息，在一个进程离开和下一个进程进入临界区之间的同步延迟。使用组播和逻辑时钟的算法进程进入临界区需要所有其它进程的同意初始化STATERELEASED为了进入临界区STATEWANTED组播请求给所有进程T请求的时间戳如果一个进程在收到令牌时，不需要进入临界区，那么，它立即把令牌传给它的邻居。WAITUNTIL接收到的应答数N1STATEHELD在PJIJ接收一个请求IFSTATEHELDORSTATEWANTEDANDT,PJIDMSG若自身标记为参与者，则不转发消息若自身标记为非参与者，则发送ELECT,MAXIDLOCAL,IDMSG至邻居，并将自身标记为参与者当IDLOCALIDMSG时，该进程成为协调者，发送ELECTED,IDCOORDINATOR至邻居，邻居节点依次转发该消息，并设置协调者信息，直至该消息再次到达协调者。霸道算法下面解释有助理解，考的是算法知道自己有最大标识符的进程通过发送协调者消息给所有具有较小标识符的进程，选举自己。有较小标识符的进程通过发送选举消息给那些有较大标识符的进程，开始一次选举，并等待应答消息。如果它具有最大的进程标识符，它会决定自己是协调者，并向其他进程宣布。该算法为“霸道算法”。算法选举初始化进程P在发现协调者失效后启动一次选举，将选举消息发送给具有更大标识符的进程。接收进程回送一个回答并开始另一次选举协调者发送协调者消息若进程P没有收到回答消息，则给所有具有较小标识符的进程发送协调者消息。若进程P收到回答消息，则等待协调者消息；若消息在一段时间没没有到达，则启动一次新的选举算法。进程收到协调者信息后，设置ELECTEDIIDCOORDINATOR用IP组播实现可靠组播组G中的每个进程维护一个序号SGP下一个要传送的消息序号。RGQ来自进程Q的最新消息序号。进程P要RMULTICAST一个消息到组G捎带SGP和确认SGPSGP1。RDELIVER一个消息M1当且仅当MSRGP1传递消息；RGPRGP12若MSRGP1或对任意封闭的确认有MRRGQ,则漏掉了一个或多个消息,将消息保留在保留队列中,并发送否认确认。全排序如果一个正确的进程在传递M前传递消息M，那么其它传递M的正确进程将在M前传递M，只要该顺序在不同进程中是一样的即可，不必是FIFO或者因果使用顺序者的全排序算法1组成员P的算法初始化RG0为了给组G发TOMULTICAST消息BMULTICASTGSEQUENCERG,I是M的一个唯一标识符。在BDELIVERMORDER时，其中GGROUPMORDERWAITUNTIL在保留队列中并且SRGTODELIVERM/在从保留队列删除它之后RGS12顺序者G的算法初始化SG0在BDELIVER时，其中GGROUPMORDERBMULTICASTG,SGSG1基于顺序者的算法缺点顺序者会成为瓶颈拜占庭将军问共识问题N进程，F错误随机故障假设N个进程中最多有F个进程会出现随机故障N3F无解决方法N3F1LAMPORT于1982给出了解决算法第五章事务和并发控制重点乐观并发控制向后验证1检查它的读集是否和其它较早重叠事务的写集是否重叠要做，规则22检查它的读集是否和其它较早重叠事务的读集是否重叠不需要做算法STARTTNTV进入工作阶段时已分配的最大事务号码FINISHTNTV进入验证阶段时已分配的最大事务号码验证失败后，冲突解决方法放弃当前进行验证的事务事物的验证过程T1、T2、T3是较早开始的事务T1在TV开始之前提交T2、T3在TV完成其工作阶段前提交STARTTN1T2，FINISHTNT3向前验证比较TV的写集合和所有重叠的活动事务的读集合规则1活动事务是那些在工作阶段中的事务，并无事务号算法设活动事务具有连续的事务标示符ACTIVE1ACTIVEN验证失败后，冲突解决方法，几个策略放弃当前进行验证事务推迟验证放弃所有冲突的活动事务，提交已验证事务。事物的验证过程T1、T2、T3是较早开始的事务T1在TV开始之前提交T2、T3在TV完成其工作阶段前提交STARTTN1T2，FINISHTNT3向后验证将较大的读集合和较早事务的写集合进行比较向前验证将较小的写集合和活动事务的读集合进行比较时间戳排序时间戳排序的写规则是否接受事务TC对对象D执行的写操作时间戳排序的读规则是否接受事务TC对对象D执行的读操作第六章复制重点系统模型基本模型组件副本管理器接收前端请求对副本执行原子性操作前端接收客户请求通过消息传递与多个副本管理器进行通信副本对象的操作请求前端将请求发送至一个或多个副本管理器协调保证执行的一致性对不同请求进行排序（FIFO，因果，全序）执行包括临时请求的执行协定就提交请求的影响达成一致响应一个或多个副本管理器响应前端被动主备份复制一个主副本管理器多个次副本管理器若主副本管理器出现故障，则某个备份副本管理器将提升为主副本管理器。模型被动复制时的事件次序请求前端将请求发送给主副本管理器协调主副本管理器按接收次序对请求排序执行主副本管理器执行请求并存储响应协定若请求为更新操作，则主副本管理器向每个备份副本管理器发送更新后的状态、响应和唯一标识符。备份副本管理器返回确认。响应主副本管理器将响应发送给前端前端将响应发送给客户主动复制副本管理器地位对等，前端组播消息至副本管理器组模型主动复制时的事件次序请求前端使用全序、可靠的组播原语将请求组播到副本管理器组协调组通信系统以同样的次序全序将请求传递到每个副本管理器执行每个副本管理器以相同的方式执行请求响应每个副本管理器将响应发送给前端前端将响应发送给客户GOSSIP体系结构查询和更新操作流程请求前端将请求发送至副本管理器查询客户可能阻塞更新无阻塞更新响应副本管理器立即应答收到的更新请求协调收到请求的副本管理器并不处理操作，直到它能根据所要求的次序约束处理请求为止。执行副本管理器执行请求查询响应副本管理器对查询请求作出应答协定副本管理器通过交换GOSSIP消息进行相互更新GOSSIP消息的交换是偶尔的发现消息丢失后，才和特定的副本管理器交换消息查询操作副本管理器收到查询一个查询请求Q包含操作的描述和一个前端发送的时间QPRE，这个值反映了前端已读到或作为更新已提交的值最新版本。QPREVALUETS（副本管理器的值时间戳）立即响应返回消息中的时间戳为VALUETS否则副本管理器将消息保存到保留队列（将要执行的操作表），等待丢失的更新，能从相关副本管理器获取更新。前端收到查询响应合并时间戳FRONTENDTSMERGEFRONTENDTS,NEW2,5,6按因果次序处理更新前端发送更新请求发送同样的请求U给若干副本管理器。副本管理器I接收请求丢弃操作已经处理过，根据已执行操作表和它的日志中的记录否则，将更新记录日志副本管理器将TS返回给前端，TS是副本服务器分配给更新的唯一时间戳。更新请求U的稳定性条件UPREVVALUETS即所有由发起更新的前端观察到的更新已经执行了，指副本服务器如果更新提交时这个条件不满足，它将在闲聊消息到达时重新检查。副本管理器的更新操作第七章分布式文件系统组件文件服务的三个组件平面文件服务对文件内容进行操作唯一的文件标识（UFID），用于在所有平面文件服务操作的请求中标识文件UFID是一长串比特，每个文件的UFID在分布式系统的所有文件中是唯一的目录服务提供文件名到UFID的映射客户模块提供应用程序对远程文件服务透明存取的支持，可供客户计算机上的用户级程序使用如对目录的