分布式系统复习-电子科技大学-曹晟-牛新征

分布式系统复习I1.分布式系统目标：资源共享、协同计算。2.分布式系统问题源于三大特点：并发性、无全局时钟、故障独立性。3.Internet&Intranet难点：可扩展性（DNS、IP）、资源的定位、异构。4.移动计算要解决的问题：避免由于移动需要重新配置的问题（DHCP）；无线带宽有限，需要考虑QoS；私密和安全问题；Adhoc网络的路由问题。5.P2P定义：计算机借助直接交换实现资源共享。6.P2P与C/S的区别：P2P网络中的节点既可以获取其他节点的资源或服务同时也是资源或服务的提供者，即兼具client和sever双重身份。7.挑战：异构性、开放性、安全性、故障处理、可扩展性、并发性、透明性（访问、位置、并发、复制、故障、移动、性能、扩展）。II1.结构模型：构成系统各部分的位置、角色、它们之间的关系。C/S、P2P、C/S变种2.基础模型：为分布式系统设计者揭示若干关键问题。交互模型：处理消息发送的性能问题，解决分布式系统中设置时间限制的难题。故障模型：试图给出对进程和信道故障的一个精确的约定，它定义了什么是可靠的信道和正确的进程。安全模型：讨论对进程和信道的各种可能的威胁，引入了安全通道的概念，它可以保证在存在各种威胁的情况下通信的安全。3.中间件：软件层，一组计算机上的进程和对象，它们相互交互，实现分布式系统的通信和资源共享。为系统开发者屏蔽系统的异构性，提供更方便的编程模式。4.交互模型：进程之间通过消息传递进行交互，实现系统的通信和协作功能；有较大的时延；时间是进程间进行协调的参考，在分布式系统中，很难有相同的时间概念；独立进程间相互配合的准确性受限于上面两个因素。5.故障模型：计算机和网络发生故障，会影响服务的正确性；故障模型的意义在于定义可能出现的故障形式，为分析故障带来的影响提供依据；设计系统时，知道如何考虑容错需求。6.安全模型：分布式系统的模块特性及开放性，使它们暴露在内部和外部的攻击下；安全模型的目的是提供依据，以此分析系统可能受到的侵害，并在设计系统时防止这些侵害的发生。III1.同步系统中的物理时钟同步一个进程发送时间t至另一个进程，且消息传输不确定性为u=max-min，则接收进程：将时钟设置为t+min，时钟偏移至多为u将时钟设置为t+max，时钟偏移至多为u将时钟设置为t+(max+min)/2，时钟偏移至多为u/22.Cristian方法存在时间服务器，消息往返时间Tround，服务器返回时间t设置时间为t+Tround/2若消息最小传输时间为min，则精度为+/-(Tround/2-min)3.Berkeley算法主机周期轮询从属机的时间，主机计算容错平均值，主机发送每个从属机的调整量。4.逻辑时钟：大题！5.快照算法目的：捕获一致的全局状态。假设：进程和通道均不会故障；单向通道，提供FIFO顺序的消息传递；进程之间存在全连通关系；任一进程在任一时间可以开始全局拍照；拍照时，进程可继续执行，并发送和接收消息。标记接收规则：强制没有记录状态的进程去记录状态。Pi接收通道C上的标记消息：if(pi还没有记录它的状态)pi记录它的进程状态；将C的状态记为空集；开始记录从其他接收通道上到达的消息；elsepi把C记录到从记录它状态以来它在C上接收到的消息集合中；endif标记发送规则：强制进程在记录下自己状态后但在发送任何其他消息前发送一个标记。在pi记录了它的状态之后，对每个外出通道C：(在pi从C上发送任何其他消息之前)pi在C上发送一个标记；IV1.分布式互斥目的：仅基于消息传递，实现对资源的互斥访问。假设：异步系统、无故障进程、可靠的消息传递。基本要求：安全性、活性、顺序。性能评价：带宽消耗、客户延迟、吞吐量。2.中央服务器算法：满足安全性和活性，不满足顺序要求。带宽消耗：enter()：2个消息，请求和授权；exit()：1个消息，释放。客户延迟：1个消息往返时间。同步延迟：1个消息往返时间。性能瓶颈：服务器。3.基于环的互斥算法：满足安全性和活性，不满足顺序要求。带宽消耗：由于令牌传递，持续消耗带宽。客户延迟：min：0个消息，正好收到令牌；max：N个消息，刚刚传递令牌。同步延迟：min：1个消息，进程一次进入临界区；Max：N个消息，一个进程连续进入临界区。4.使用组播和逻辑时钟的算法：进程进入临界区需要其他所有进程的同意。（组播+应答）并发控制：Lamport时间戳避免死锁。满足安全性、活性、顺序要求。带宽消耗：enter()：2(N-1)，请求和回应个N-1。客户延迟：1个消息往返时间。同步延迟：2个消息传输时间。伪码：初始化：state:=RELEASED;pi为了进入临界区：state:=WANTED;将请求组播给所有进程；waituntil(接收到的应答数=(N-1))state:=HELD;在pj(i≠j)接收一个请求(Ti,pi)：if(state=HELDor(state=WANTEDand(T,pj)(Ti,pi))将pi的请求放入队列，不予应答；else马上给pi应答；state:=HELD;endif为了退出临界区：state:=RELEASED;对已进入队列的请求给出应答;5.Maekawa投票算法：会产生死锁。伪码：初始化：state:=RELEASED;voted:=FALSE;pi为了进入临界区：state:=WANTED;将请求组播到vi中所有进程；waituntil(接收到回应数=K)state:=HELD;pj(i≠j)接收到来自pi的请求：if(state=HELDorvoted=TRUE)将pi的请求放入队列，不予应答；else将应答发送给pi；voted:=TRUE;endifpi为了退出临界区：state:=RELEASED;将释放消息组播给vi中的所有进程；pj(i≠j)收到来自pi的释放：if(请求队列非空)删除队列头pk；发送应答给pk；voted:=TRUE;elsevoted:=FALSE;endif6.基于环的选举算法：目的：在异步系统中，选举具有最大标识符的进程作为协调者。算法：最初，每个进程标记为非参加者；任何进程可以开始一次选举：将自身标记为参加者；idmsg=idlocal，发送{elect,idmsg}至邻居；非参加者转发选举消息：将自身标记为参加者；发送{elect,max(idmsg,idlocal)}至邻居；当idlocal=idmsg时，该进程成为协调者：将自身标记为非参加者；idcoordinator=idlocal，发送{elected,idcoordinator}至邻居；参加者转发选举结果消息：将自身标记为非参加者；记录idcoordinator;性能：最坏：3N-1个消息；最好：2N个消息。7.霸道算法：同步系统。、、、。8.可靠组播：有可能是大题！性质：完整性、有效性、协定。算法：初始化：Received:={};p为了将R-multicast消息发送到g：B-multicast(g,m);在q执行B-deliver(m)时，其中g=group(m)：if(m不属于Received)Received:=Received∪{m};if(q≠p)B-multicast(g,m);endifR-deliverm;endif9.拜占庭将军问题：N=3f，无解决方法。N=3，f=1时，N=4，f=1时的情况。V1.事务：由客户定义的针对服务器的一组操作，它们组成一个不可分割的单元，由服务器执行。目标：当多个事务访问对象以及服务器面临故障时，保证所有由服务器管理的对象保持一个一致的状态。ACID：原子性、一致性、隔离性、持久性。2.四大问题：（能够根据图表判断问题原因，并给出相应解决办法）更新丢失、不一致检索：串行等价性。脏数据读取、过早写入：严格两阶段加锁。3.冲突操作：两个操作的执行效果与它们的执行次序相关。读写操作的冲突规则：readread否readwrite是writewrite是串行等价性：两个事务中所有冲突操作都按相同次序在访问对象上执行。4.事务的严格执行：read和write都推迟到写同一对象的其他事务提交或放弃后进行。能真正保证事务的隔离性。5.锁：表格记住。两阶段加锁：保证两个事务的所有冲突操作都必须以相同次序执行。增长阶段：不断获取新锁。收缩阶段：释放锁。严格两阶段加锁：避免事务放弃导致的脏数据读取、过早写入等问题。所有获取的新锁必须在事务提交火放弃后才能释放。读锁和写锁的相容性：已设置的锁申请的锁readwritenoneokokreadok等待write等待等待嵌套事务的加锁：父事务继承子事务的所有锁。子事务获得读锁，只有其父事务可以持有该写锁；子事务获得写锁，只有其父事务可以持有该写锁或读锁。6.乐观并发控制：三个阶段：工作、验证、更新。（由于验证更新过程较短，每次只允许一个事务处于验证和更新阶段）冲突规则：TvTi规则writereadTi不能读Tv写的对象readwriteTv不能读Ti写的对象writewriteTi不能写Tv写的对象，Tv不能写Ti写的对象向后验证：检查Tv的读集是否与其他较早重叠事务的写集重叠。startTn：Tv进入工作阶段时已分配的最大事务号。finishTn：Tv进入验证阶段时已分配的最大事务号。booleanvalid=true;for(intTi=startTn+1;Ti=finishTn;Ti++){if(Tv的读集与Ti的写集相交)valid=false;}向前验证：比较Tv的写集和所有重叠活动事务的读集。设活动事务具有连续的事务标识符active1~activeNbooleanvalid=true;for(Tid=active1+1;Tid=active;Tid++){if(Tv的写集与Tid的读集相交)valid=false;}7.时间戳排序：每个事务启动时被赋予一个唯一的时间戳，时间戳定义了该事务在事务时间序列中的位置，不会引起死锁。冲突规则：写请求有效：对象的最后一次读访问或写访问由一个较早事务执行时；读请求有效：对象的最后一次写访问由一个较早事务执行时。写规则：是否接受事务Tc对对象D的写操作。if(TcD的最大读时间戳&&TcD的提交版本的写时间戳)在D的临时版本上执行写操作，写时间戳置为Tc；else放弃Tc；读规则：是否接受事务Tc对对象D的读操作。if(TcD的提交版本的写时间戳){设Dselected为D上具有最大写时间戳的版本=Tcif(Dselected已提交)在Dselected版本上进行读操作；else等待直到形成版本的事务提交或放弃，然后重新应用读规则；}else放弃Tc；8.比较：悲观：简单，并发度低。时间戳排序：静态的决定事务之间的串行顺序，适用于读操作占优的情况。两阶段加锁：动态的决定事务之间的串行顺序，适用于更新操作占优的情况。乐观：适用于并发事务之间冲突较少时，性能较高。放弃事务时，需要重复大量工作。VI1.复制动机：增强服务（增强性能，提高可用性，增强容错能力）。基本要求：复制透明性：对客户屏蔽多个物理拷贝的存在；客户只对一个逻辑对象进行操作。一致性：在不同应用中有不同强度的一致性需求；复制对象集合的操作必须满足应用需求。2.容错服务被动（主备份）复制：一个主副本管理器+多个备份副本管理器。主动复制：副本管理器的地位对等，前端组播消息至副本管理器组。3.gossip、bayou、coda：高可用性，较弱一致性。4.gossip查询：副本管理器收到查询q.preq.pre=valueTS将消息保存到保留队列前端收到查询响应合并时间戳frontEndTS:=merge(frontEndTS,new);按因果次序处理更新：前端发送多个更新请求：(u.op,u.prev,u.id)副本管理器i接收请求：丢弃：操作已处理过（查询操作表和日志记录）否则：ts[i]=ts[i]+1;logRocord:=i,ts,u.op,u.prev,u.id前端合并时间戳:fro