分布式系统与WEB服务培训课件.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学计算机学院,分布式系统与,WEB,服务,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学计算机学院,分布式系统与,WEB,服务,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学计算机学院,分布式系统与,WEB,服务,第五章 分布式系统文件共享,分布式系统与WEB服务培训课件,第1页,5.1,共享文件语义,两个以上用户共享同一个文件时，会产生各种情况，从而产生不一样语义故文件服务时必须准确定义服务读写语义。,一,.UNIX,语义,(,时间次序,),对于单处理机而言，在,UNIX,系统中，其读操作语义是，读取结果是它前面最近一次写操作形成结果。写操作语义是，若先后连续有两个写操作，则文件结果决定于后面写操作。所以，,最终形成语义是严格意义下时间序操作。,分布式系统与WEB服务培训课件,第2页,在对分布式文件系统中文件进行读操作时，能看到以前全部对该文件执行写操作效果。尤其是，客户对于已打开文件写操作可马上为其它打开此文件客户所见。客户可共享文件当前位置指针。这么，一个客户将指针向前推进时将影响全部共享客户视图。,此种语义特点是易于了解和实现。,二,.,会话语义,对于打开文件写操作能够马上为当地客户所见，远程客户也同时打开该文件，但却不可见。,一旦文件关闭，对此文件所作修改仅为后面进行操作所见，该文件已经打开各副本不表现这些修改,.,分布式系统与WEB服务培训课件,第3页,三,.,不可改变文件语义,一但文件为共享文件，则全部用户均不能再修改它。这里不可改变有两个含义：一是其名字不可再变；二是其内容不可改变。这么，不可改变文件名字代表该文件固定内容，而不再是信息存放机制。,这一语义非常简单，易于实现，但应用起来，很不灵活,四,.,事务语义,用户若要访问一个文件或了组文件，,首先要执行一个开启事务操作,表示下面操作必须独立执行，然后对文件进行读写操作，当工作完成后，再执行一个结束事务操作。,分布式系统与WEB服务培训课件,第4页,其关键特征是,确保事务期间全部文件操作按序执行，而不受其它用户干扰，也就是说，在事务内部严格含有,UNIX,语义、显然，,事务语义是一个比较实用文件语义。,事务完成要求一个客户机与一个或几个服务器进行协作。,分布式系统与WEB服务培训课件,第5页,5,2,原子事务,在分布式系统中，,原子事物又简称事物，,事务实际上就是一组逻辑上连续执行操作，其含有动态性，有三种状态：,提交 事务中文件数据项修改永久保留,中止 因为同其它事务冲突或硬件故障造成事务中止,暂时 事务执行中存在暂时状态,分布式系统与WEB服务培训课件,第6页,5.2.1,事务特征,事务含有以下四个特征,简称,ACID,特征,原子性,(Atomic):,即事务作用要么完整，要么没有。,一致性,(,Consistent),：事务处理不影响系统中不变性：意思是，当系统含有某种不变特征需要保持时，在事务执行前后该不变性一定要保持。比如，银行业务系统中有一个关键不变特征是,“,金钱不灭,”,，经过内部任何转帐之后，银行总钱数是不变。,孤立性,(Isolated),：并发事务不会相互影响，多个事务处理可并发执行，其结果和各事务处理串行执行结果一样，也叫串行等价性。,分布式系统与WEB服务培训课件,第7页,三个事务,A,、,B,、,C,被三个独立进程同时执行,若次序执行其结果为,1,、,2,或,3,BEGIN_TRANSACTION A BEGIN_TRANSACTION B BEGIN_TRANSACTION C,X=0;X=0;X=0;,X=X+1;X=X+2;X=X+3;,END_TRANSACTION END_TRANSACTION END_TRANSACTION,时间,调度,1,x=0;x=x+1;x=0;x=x+2;x=0;x=x+3;,正当,调度,2,x=0;x=0;x=x+1;x=x+2;x=0;x=x+3;,正当,调度,3,x=0;x=0;x=x+1;x=0;x=x+2;x=x+3;,不正当,分布式系统与WEB服务培训课件,第8页,持久性,(Durable),：假如事务处理成功完成、则结果将永不消失，除非发生硬故障。,5.2.2,事务需求,银行基本业务服务,服务过程,解释,存款,(,账号，数额,),将指定,数额,款项存入给定,账号,取款,(,账号，数额,),从给定,账号,取出指定,数额,款项,平衡,(,账号,),返回给定,账号,当前平衡,总平衡,(),返回该客户全部账号总平衡,开始事务处理,(,标号,),开始指定,标号,事务处理,结束事务处理,(,标号,),结束指定,标号,事务处理,流产事务处理,(,标号,),迫使指定,标号,事务处理流产,分布式系统与WEB服务培训课件,第9页,银行服务例子,开始事务处理,(T),；,K,：取款,(A,，,100),；,K,：存款,(B,，,100),；,K,：取款,(C,，,200),；,K,：存款,(B,，,200),；,结束事务处理,(T),我们将用,T,、,U,、,V,代表事务处理标号，用,K,、,M,、,N,代表不一样银行分行，用,A,、,B,、,C,代表客户分行账号，一个客户发出一系列服务过程调用就能够合并为一次事务处理。,分布式系统与WEB服务培训课件,第10页,5,3,并发控制,并发控制主要目标是满足事务处理一致性,(,串行等价性,),最早方法,:,A.,某一时刻只允许执行一个事务,B,在开启多个事物操作之前先检验是否满足一致性,缺点,:,处理不好,.,为填补不足,.,提出,下面三种方法,.,分布式系统与WEB服务培训课件,第11页,5.3.1,加锁,当某一事务访问一共享数据项时，由服务器对该数据项加锁，当完成访问时，再由服务器开锁，方便于其它事务访问。在上锁期间，只有锁定该数据项事务才能对其访问，这么就确保了在某一时刻访问数据进程唯一性和确定性。,一,.,基本原理,一个锁可由三都分组成：,一个二值逻辑变量，用以指示上锁开锁；,一个类似于信号灯条件变量；,访问该锁宿主事务标识符,分布式系统与WEB服务培训课件,第12页,实现上锁机制时，需要注意锁粒度。粒度是指被加锁数据项大小，粒度越细，则并行度越高，反之，并行度越低。对整个文件加锁是一个极端情况，这时候，事务串行执行。,在下面讨论中，上锁普通施加于文件中数据项上。,锁定机制是分两个阶段进行。,一个事务在工作过程中，可分为“生长”和“消亡”两个阶段。生长阶段需要上锁，消亡阶段需要开锁，这就是两阶段锁定机制。,在生长阶段，事务处于暂时状态，其暂时数据不为其它事务所见。在消亡阶段，暂时数据要变成永久数据，为了保持事务特征，必须在事务关闭最终，才能开锁。,分布式系统与WEB服务培训课件,第13页,二、几个加锁方案,1,最简单加锁方法,在这种方案中，文件服务器对客户事务访问每一个数据项加锁，而在事务完成,(,或中止,),时打开全部锁，当另一事务试图访问已上锁数据项时，它必须等候到开锁为止。,2.,读写锁方案,因为简单锁定机制无须要地将全部访问到数据项锁定，从而降低了事务并发性。,尤其是当事务中均是读操作时，便没有必要上锁,。,分布式系统与WEB服务培训课件,第14页,基于这种分析，,提出了读写锁方案，即允许多个事务并发读同一数据项，只允许一个事务写一个数据项。也称为“多读单写”,方法,。在这种方法中，对于读操作，还不能放弃上锁，因为不上锁，可能会有其它事务修改它，造成不一致。为此，,要采取两种不一样锁，即读锁和写锁,对于访问全部数据项均可上读锁，只对写操作访问数据项上写锁。上写锁数据项不能被其它事务所访问，上读锁数据项只能为其它事务读，但不能写,。,分布式系统与WEB服务培训课件,第15页,上锁和开锁基本规则如示,:,1,当客户在事务中访问数据项时，有以下情况,：,假如数据项还未上锁，服务器将其锁定，并让客户防问该数据项；,假如数据项已被其它事务上锁，客户必须等候该锁打开：,假如服务器已经锁定了本事务中一个数据项，客户能够继续防问。,假如事务想要写自己已上有读锁数据项，应该将读锁改为写锁。,2.,当事务提交或中止时，服务器打开它为该事务锁定全部数据项。,分布式系统与WEB服务培训课件,第16页,3.,读写锁死锁问题,以上两种方法都在一定程度上提升了并发性，但与此同时也会带来另一个问题,死锁。,所谓死锁就是一组事务中每个操作都处于上锁且又等候开锁状态,，比如以下两个事务,U,和,T,，在时间次序上依次采取以下动作，结果将造成死锁。,T,等候事务,U,释放读锁,b,，而它本身又对其加读锁引发事务,U,对其解锁等候，由此，便造成了,相互牵制。,处理方法有以下,4,种,分布式系统与WEB服务培训课件,第17页,在事务开始执行前便对其所要访问数据加锁,，这虽能预防死锁，但却降低了资源共享率。,给资源要求一个序号,，申请资源时必须按序号单调递增或递减方向申请，这种方法也降低了并行性。,经过资源申请占有图来检测有没有死锁，一旦发觉死锁便由服务器中止一个事务来打破循环占有等候,，处理死锁。,“时限”控制，是文件系统中较惯用方法，即给,每个锁要求一个时间段。在此时段内，该锁是稳定，若超出此时限后，该锁便变成易损锁，,若此时没有别事务对上锁数据项竞争，则该锁继续保持；不然话，便打破此锁，与此同时，原上锁事务中止。这种方法也有两个不足，第一是增加了系统开销；第二是“时限”取值问题,分布式系统与WEB服务培训课件,第18页,4,意向写锁,读写锁中读锁存在阻止了其它事务对其进行写操作，在一定程度上降低了并发性。然而,事务执行要经过两个阶段，在暂时阶段，写操作实际上只是将改写内容写到一个暂时缓冲区中，并未改写实际数据项。只有在提交阶段才写回数据项，基于此原理可把读写锁改成意向写锁和提交锁来提升并发性,.,分布式系统与WEB服务培训课件,第19页,5.3.2,乐观并发控制方法,一,.,问题提出,使用锁机制处理并发控制时存在一些缺点：,分布式系统中锁机制是一个额外开销。,比如，在只有读操作事务中，锁能够确保所读数据项不被别事务修改，但这种锁只有在最坏情况下才有必要。又比如，两个客户进程并发地对,n,个数据项进行增值运算，若它们同时开启，执行时间量也相同，以互不相关序列访问数据项，而且各自使用一个事务来访问和增值数据项，则这两个程序试图同时访问同一数据项机会仅有,1,n,，也即每,n,个事务中实际有用锁只有一次。,分布式系统与WEB服务培训课件,第20页,使用锁机制会造成死锁，而且没有令人满意死锁处理算法,。在锁机制中，只有在一个事务终止时才释放它全部锁，这显著有损于并发性。正是基于以上原因，有些人提出另一个算法,乐观并发控制方法,。之所以称其为,“,乐观,”,，是基于这么一个假设,，,两个客户事务同时访问某一数据可能性很小,所以两个事务能够执行下去，直至发出,C1oseTransaction,请求。当产生冲突时，普通要中止一些事务，并由客户重新开启。这么，每个事务便分为以下三个阶段：,分布式系统与WEB服务培训课件,第21页,1.,读阶段：,在这一阶段中，每个事务有一个待更新数据暂时版本,。,读请求能够马上执行,，假如有暂时版本存在，则要访问最近提交数据值。,而写请求以一个其它事务不可见形式缓存起来，,若有几个并发事务，可能会同时存在同一数据项几个不一样暂时值。另外，,针对于每一个事务需要设置两个集合：读集合和写集合，读集合列出事务所读数据项集合，而写集合则列出事务创建、修改、删除数据项集合。,2.,确认阶段：,当服务器收到,CloseTransaction,请求之后，进入这个阶段,，在该阶段中，,对该事务进行确认是否能够将该事务写操作结果永久保留下来。,分布式系统与WEB服务培训课件,第22页,假如事务确认成功，则进入写阶段,(,写操作结果统计到相关文件中，事务成功完成，,发出,commit);,不然，要处理冲突，需要中止一些事务。,确认阶段是建立在一致性基础上,，即假如事务执行结果等价于各个事务次序执行结果，则该事务视为确认成功。,3.,写阶段：,假如一个事务确认成功，则暂时版本统计全部修改均能够变为永久性修改。,只读事务能够在确认经过后马上提交。写事务在暂时版本中数据变为永久数据之后马上提交。,分布式系统与WEB服务培训课件,第23页,二、,事务确实认,确认是利用读写冲突规则来确保一组重合事务,(,即当前事务还未提交便已开始事务,),调度符合一致性,当一个事务完成第一阶段工作后,为其指定一个事务号，若该事务确认成功完成,则事务号被保留下来：不然，若事务未被确认，或事务是只读事务，则释放该事务号,确认工作主要基于两个事务操作冲突来完成 对于两个重合事务,Ti,和,TJ,，,必须满足以下规则,。,分布式系统与WEB服务培训课件,第24页,确认方法有两种，,一个叫做向后确认,(Backward Validation),，以正在执行确认事务为基准，检验已经进入确认阶段事务。,一个叫做向前确认,(,Forward Validation),，以正在执行确认事务为基准，检验后续进人确认阶段事务,.,三,.,饿死现象,事务中止后,通常由客户程序重新开启,但有可能该事务依然无法经过确认,于是其又被中止,重启,再中止,.,如此,该事务则被剥夺了提交能力 此现象即为饿死,分布式系统与WEB服务培训课件,第25页,5.3.3,时间戳,要利用时间戳完成并发控制，,需要对每个事务操作进行有效性检验，若检验未能经过,则该事务马上中止并重新开启,基本时间规则,:,事务对数据项写请求，仅当该数据项最近由前一个事务,(,有冲突,),读和写，才能有效。,事务对数据项读请求，仅当该数据项刚才由前一个事务,(,有冲突,),写，才能有效。,该规则允许并发事务共享暂时数据项，从而确保每个数据项暂时值按时间戳次序提交,.,分布式系统与WEB服务培训课件,第26页,5,4,恢复,事务原子性要求事务要么提供完整运行结果，要么么作用都没有，即持久性和失效原子性。这两个需要并不是独立，,能够由服务器上独立机制来管理，我们称这个机制叫做恢复管理器。,恢复管理器主要任务是；,将提交事务数据保留到永久性存放介质,(,恢复文件,),上；,故障重启后，恢复服务器数据；,组织恢复文件，改进恢复性能；,回收恢复文件包括到空间。,分布式系统与WEB服务培训课件,第27页,5,5,事务服务中文件版本,5.5.1,文件版本实现,经过在每个文件索引表中扩充一项,即版本号,经过对影子页操作,到事务提交时,若无版本冲突,则合并暂时版本与当前版本得到最新版本,.,若有冲突则放弃暂时版本,.,5.5.2,意向表实现,也可经过对影子页操作实现意向表,意向表统计,:,操作类型、事务标识符、文件标识符、页号、影子页面指针,分布式系统与WEB服务培训课件,第28页,文件版本方法,处理两类问题,:,版本冲突和串行冲突,版本冲突,:,并发事务访问同一个文件不一样数据段,从而产,生不一样版本,但无一版本包含全部修改,.,串行冲突,:,并发事务访问同一数据段,从而有多个写操作,造成数据项决定于最终版本,.,版本冲突处理如图,:,分布式系统与WEB服务培训课件,第29页,老版本,老版本,当前版本,合并最新版本,事务,T,暂时版本,事务,U,暂时版本,版本合并,分布式系统与WEB服务培训课件,第30页,老版本,老版本,上一个版本,当前版本,事务,T,暂时版本,事务,U,暂时版本,串行冲突处理,分布式系统与WEB服务培训课件,第31页,意向表方法,意向表实际上是一个事务操作日志统计,是两阶段提交机制,.,即,:,第一阶段,事务处于暂时状态,第二阶段,事务进入提交阶段,.,如图,DATA,为服务器为待修改数据暂时拷贝,.,意向操作只是统计到意向表并不是真对文件操作,一个意向只有给出足够信息,才能到第二阶段执行,.,本事务视图,DATA1,DATA2,其它事务视图,分布式系统与WEB服务培训课件,第32页,第六章,分布事务与文件备份,分布式系统与WEB服务培训课件,第33页,6,1,合作服务器,合作服务器是由多个物理服务器合作完成一个逻辑服务器功效,各个服务器由网络互连,每个服务器可具备不一样性能,可位于不一样地点,并持有整个合作服务器中全部文件一部分,分布式系统与WEB服务培训课件,第34页,6,2,分布事务,分布事务是指一个事务将包括到多个服务器操作,即该事务是由合作服务器完成,结构分布事务方法有简单分布事务和嵌套分布事务两种,简单分布事务,:,客户机能够屡次访问不一样服务器,服务器仅响应客户机请求,不引发其它服务器操作,嵌套分布事务,:,一个服务器上操作可能引发其它服务器操作,分布式系统与WEB服务培训课件,第35页,客户机,服务器,1,服务器,2,服务器,3,在分布事务中,多个服务器需要相互通信和合作,各自完成部分工作,最终是事务提交完成,.,在分布事务处理中,第一个响应客户机请求服务器为该事务协调服务器,负责中止、提交该事务，其后加入服务器为工作服务器。,分布式系统与WEB服务培训课件,第36页,T,S,1,T,22,T,21,T,12,T,11,T,2,T,1,T,S,3,S,2,S,2,S,6,S,5,S,4,S,1,S,3,(a),分布式平面事务处理,(b),分布式嵌套事务处理,S,7,S,0,事务处理分类,其中方框代表事务处理，圆形代表执行操作服务器,分布式系统与WEB服务培训课件,第37页,分布式事务处理,分布式事务处理关键在于服务及数据分布，即一个事务处理所需服务与数据可能分散在不一样服务器上，所以，事务处理过程就必须在多台服务器上执行。,分布式事务处理调度与同时,多台服务器联合执行一个事务处理时需要彼此协调，才能做到整个事务处理成功提交,惯用方法是由一个协调者,(coordinator),经过服务器之间通信来实现最终提交,分布式系统与WEB服务培训课件,第38页,分布式事务处理例子,开始事务处理,(T),；,K,：取款,(A,，,100),；,M,：存款,(B,，,100),；,N,：取款,(D,，,200),；,M,：存款,(C,，,200),；,结束事务处理,(T),某客户要在,K,、,M,、,N,三个银行分行,A,、,B,、,C,、,D,四个账号上执行转帐业务，即从,K,分行,A,账号取出,100,元，存入,M,分行,B,账号去，然后从,N,分行,D,账号取出,200,元并存入到,M,分行,C,账号。假定这三个分行数据库分别位于三台服务器上，其中,S,1,管理,K,分行,A,账号，,S,2,管理,M,分行,B,、,C,两个账号，,S,3,管理,N,分行,D,账号,分布式系统与WEB服务培训课件,第39页,分布式银行事务处理,T,S,1,S,3,S,2,(1.1),开始事务处理,(T),；,(1.2)K,：取款,(A,，,100),；,(1.3),结束事务处理,(T),；,(2.1),加入服务器,(T,，,S,1,),；,(2.2)M,：存款,(B,，,100),；,(2.3)M,：存款,(C,，,200),；,(3.1),加入服务器,(T,，,S,1,),；,(3.2)N,：取款,(D,，,200),；,K,分行,M,分行,N,分行,协调者,参加者,参加者,因为每个服务器可能同时执行不一样分布式事务处理，所以在整个系统中事务处理标号必须是唯一。首先开启分布式事务处理那台服务器是整个事务处理协调者服务器,分布式系统与WEB服务培训课件,第40页,6,3,分布事务提交协议,最简单方法,:,1,一阶段原子提交协议,:,即由协调服务器不停查询全部工作服务器,直到全部工作服务器都回答提交成功,完成整个事务提交,2,两阶段提交协议,(2PC,协议,),，能够确保分布事务原子性，在此协议中，任何服务器都能够随时中止自己子事务而不影响客户机事务正常提交或中止。,分布式系统与WEB服务培训课件,第41页,协调服务器分为两阶段工作,(2PC),：,第一阶段 投票阶段,A,协调服务器向每个工作服务期发出提交请求,B,工作服务器收到请求后,回答,YES,或,NO,如回答有,NO,则终止,第二阶段 完成阶段,C,协调服务器查看搜集票数,若无反对票,协调服务器则提交该事务并通知全部工作服务器,不然,若有反对票协调服务器则终止事务,并向全部回答,YES,工作服务器发出终止请求,分布式系统与WEB服务培训课件,第42页,3,嵌套事务两阶段提交协议,嵌套事务两阶段提交协议执行过程第一阶段与非 嵌套事务不一样，当工作服务器接到提交：,1),假如工作服务器含有暂时提交且是顶层事务子事务,A.,检验它有没有前辈事务处于中止事务表中，准备提交,B,中止含有中止前辈事务事务,C,向协调服务器投票,YES,分布式系统与WEB服务培训课件,第43页,2),假如工作服务器没有处于暂时提交状态、且是顶层事务子事务，它必定已经失败，应向协调服务器投票,NO,注意,:,A.,子事务标识符能够经过扩充其父事务标识符,;,B.,子事务提交决定于其父事务提交,但父事务提,交并不决定于其子事务提交,分布式系统与WEB服务培训课件,第44页,6,4,分布事务中并发控制,当多个事务处理访问同一个数据时，次序等价性要求必须把每一个事务处理对该数据完整,(,读,/,写,),访问一一排序，严格禁止任何冲突,开始事务处理,(T),：,K,：取款,(A,，,40),；,K,：存入,(B,，,40),；,结束事务处理,(T),；,开始事务处理,(U),：,K,：取款,(C,，,30),K,：存款,(B,，,30),结束事务处理,(U),；,分解操作,平衡,分解操作,平衡,A,平衡,A,读出,(),(A)100,元,A,写入,(A,平衡,40),(A)60,元,C,平衡,C,读出,(),(C)300,元,C,写入,(C,平衡,30),(C)270,元,B,平衡,B,读出,(),(B)200,元,B,写入,(B,平衡,+40),(B)240,元,B,平衡,B,读出,(),(B)240,元,B,写入,(B,平衡,+30),(B)270,元,分布式系统与WEB服务培训课件,第45页,1.,分布事务中锁,每个服务器都要提供锁管理机制，当地锁管理机制能够决定是否接收事务请求操作。,利用互斥锁进行事务处理并发控制,分布式系统与WEB服务培训课件,第46页,开始事务处理,(T),：,K,：取款,(A,，,40),；,K,：存款,(B,，,40),；,结束事务处理,(T),；,分解操作,互斥锁,分解操作,互斥锁,开始事务处理,(T),开始事务处理,(U),A,平衡,A,读出,(),锁定,A,C,平衡,C,读出,(),锁定,C,A,写入,(A,平衡,40),C,写入,(C,平衡,30),B,平衡,B,读出,(),锁定,B,B,平衡,B,读出,(),等候,B,锁,B,写入,(B,平衡,+40),结束事务处理,(T),释放,A,，,B,锁定,B,B,写入,(B,平衡,+30),结束事务处理,(U),释放,B,，,C,开始事务处理,(U),：,K,：取款,(C,，,30),K,：存款,(B,，,30),结束事务处理,(U),；,分布式系统与WEB服务培训课件,第47页,分布式死锁,在各种包括互斥算法中，只要算法采取互斥锁，就有可能发生,“,死锁,”,现象。,死锁经典特征是一组事务处理形成了一条循环等候链,死锁处理：,置之不理,（鸵鸟算法,）,由程序员对其负责,预防,（静态使死锁在结构上不可能）,不存在运行系统支持,防止,（合理分配资源）,运行系统支持,检测恢复,（允许死锁发生，检测到后恢复）,不一样算法,分布式系统与WEB服务培训课件,第48页,T,U,V,W,W,U,T,V,(a),简单循环链,(b),复杂循环链,互斥,持有并等候,(a)T,UVWT,不容抢占,(b)V,WTV,循环链,V,WV,死锁,-,循环等候链,分布式系统与WEB服务培训课件,第49页,分布式事务处理死锁例子,事务处理,U,事务处理,V,事务处理,W,存款,(D,，,100),锁定,D S,3,存款,(B,，,300),锁定,B S,2,存款,(A,，,200),锁定,A S,1,存款,(C,，,500),锁定,C S,3,取款,(B,，,200),等候,B S,2,取款,(C,，,100),等候,C S,3,取款,(A,，,300),等候,A S,1,死锁,分布式系统与WEB服务培训课件,第50页,死锁检测,死锁是一个稳定状态,尽管无法从局部状态检测分布式事务处理死锁，但死锁依旧是环形等候链。,死锁检测算法：,中央式,周期性地搜集等候状态,分布式,推出等候状态,提醒式,结构检测体系,分布式系统与WEB服务培训课件,第51页,2.,分布事务中时间戳,利用时间戳进行读写协作,3.,分布事务中乐观并发控制,分布事务经过一组独立服务器进行确定，每个服务器都要确认事务访问是自己数据项，全部确认均经过两阶段进行。,分布式系统与WEB服务培训课件,第52页,读阶段,在读阶段，该事务处理所访问数据都有一套暂时版本，这套版本不对外，只由拥有者使用。采取暂时版本能够使事务处理流产而不会影响到长存数据。当执行一个读操作时，假如数据暂时版本已经存在，则读操作马上访问之，不然，就必须访问那个数据最近提交值。写操作把每一数据新值作为暂时值统计在案。显然，假如若干个并发事务处理共享同一个数据，则这个数据可能有不一样暂时值。除了上述规则外，对每一个访问数据，事务处理还要维护两个数值集合：读集合包含该事务处理读出数据，写集合囊括该事务处理写入数据。,验证阶段,当事务处理试图提交时，就进入验证阶段，其目标是检测是否它所访问数据与其它事务处理操作有冲突。假如验证无冲突，该事务处理能够提交；不然我们就必须消解冲突。消除冲突方法很简单：或者命令该事务处理流产，或者从卷入冲突事务处理中选择一个令其流产。,写阶段,假如该事务处理已经经过验证，暂时版本中所统计数据更新就成为永久性。假如该事务处理是只读型事务处理，则它马上提交；不然就要等到暂存数据全部写入长存存放器后，执行提交操作。,乐观并发控制算法,分布式系统与WEB服务培训课件,第53页,6,5,分布事务中恢复,分布事务恢复工作,服务器 状态 恢复管理器工作,协调服务器 准备提交,表示服务器故障时还未做出仟何决定将向全部工作,服务器发出,AbortTransaction,，将中止状态加入到恢,复文件中若状态是中止，工作相同。,假如没有工作服务器，将以超时判断，中止对应事务,协调服务器 提交,表示服务器故障时已做出提交决定若是还没有做完,要发送,DoCommit,，给各工作服务器，从这一步开始恢,复两阶段提交协议执行。,分布式系统与WEB服务培训课件,第54页,工作服务器 提交,表示已经提交假如还未向上作服务器发送,HaveCommited,消息，则发送之；然后，执行整个事务中属于本身那一,部分操作,(,若文件操作是可重复，这么做就不会引发不,一致性,),。,工作服务器 不确定,表示工作服务器在知道事务输出之前故障，必须等到协调,服务器作山决定，能够有,GetDecison,获取。收到应答后，,依据情况提交或中止。,工作服务器 准备提交,表示工作服务器还没有投票，能够中止事务,协调服务器 完成,不需要任何工作,分布式系统与WEB服务培训课件,第55页,6,6,备份,备份是与分布事务及合作服务器亲密相关问题,。一个备份对象,(,如文件或数据项,),由位于多个服务器中许多副本组成，我们称组成一个备份对象副本集合中任意副本为该备份对象一个代理。,备份对象有以下特点：,(1),降低分布式系统中通信量，并经过为用户提供当地副本而加紧响应时间；,(2),能够从多台服务器上访问同一对象，从而提升系统有效性，降低服务器故障影响及通信失败可能性；,(3),能够在不一样服务器上并行执行多个用户对同一对象请求，从而提升系统吞吐率。,分布式系统与WEB服务培训课件,第56页,按照客户观点，,备份事务服务应该与非备份事务服务一样含有单副本可串行性，即经过并发控制，使多个事务表现为在一定次序下串行执行。,6.6.1,基本模型,最简单策略就是读一写全,即读时只读一个副本，写时要写全部副本。这么能够随时确保各副本一致性。,不过因为多个客户可能同时写某一副本而产生写冲突，所以,必须提供并发控制机制来确保分布事务基本特征,.,分布式系统与WEB服务培训课件,第57页,6.6.2,主从模型,备份对象服务需求有,一个基本服务器及多个二级服务器，,基本服务器拥有一个基本对象副本并响应全部修改请求，其它副本只响应用户读请求，不响应用户写请求。只接收来自基本服务器修改消息来修改副本或直接拷贝基本对象副本。,客户,客户,服务器,服务器,服务器,主副本,后备副本,后备副本,写,读,读,写,更新传输,更新传输,分布式系统与WEB服务培训课件,第58页,6.6.3,可用副本模型,主从模型主要不足在于：备份文件在基本服务器失效时不能修改，而且仅适合用于修改极少对象。而读一写全策略又是不现实，因为当有些副本服务器因故障或通信问题不能工作时，是绝对达不到,“,写全,”,要求,其,基本思想是：即使有部分副本服务器故障时系统仍可工作，,其基本策略是，客户读请求能够在任何可用副本上执行，但客户写请求必须在可用副本同时执行。,可用副本模型要求副本服务器之间通信无误,.,分布式系统与WEB服务培训课件,第59页,6.6.4,含有分布控制系统,我们要使用分布式控制机制，来完成副本管理，目标是即使一些副本失效，修改依然能进行下去。在这种方法中，任何一个副本服务器都能接收读写请求，并让客户得到有效一致数据,一,.,文件组,:,备份文件副本集合,为支持备份策略，文件组必须存放在每台副本服务器上。在完全一致情况下，文件组中副本有相同初始值，,而且各次修改都是针对整个文件组而言，全部副本自始至终保持一致。,分布式系统与WEB服务培训课件,第60页,二,.,版本号,:,服务器在读副本之前，必须能从版本号和时间戳上判断该代理是不是最新版本。,副本初态普通被认为是第一版，以后每一次修改,就生成文件一个新版本,.,三,.,多数一致算法,:,多数副本取得一致,即可完成操作,多数一致算法是最早提出处理备份分布控制算法，其原理能够应用于两个方面：,(1),备份：两个多数集合中最少含有一个相同元素，故多数原理能确保最新版副本选择。,(2),备份并发控制：它对于非当前版文件能够作否决修改决定。,分布式系统与WEB服务培训课件,第61页,6.6.5,分割与法定数,分割是指某一时刻,副本所包括到全部服务器之间不能两两相互通信而造成一个难以确保副本一致性情况,相当于将副本服务器分成若干个组,组内副本服务器能够相互通信,但组间服务器不能通信,.,法定数,:,一个组内副本服务器个数,目标是让处于不一样组副本服务器能够独立决定是否执行客户请求,.,分布式系统与WEB服务培训课件,第62页,6.6.6,法定数算法,原理,:,给文件组中每个副本分配一个带权选票,不一样服务器权值不一样,首先得到一个到达,读法定数,R(,即,R,个选票,),后,才能从最新副本执行读操作,在写操作执行前,必须到达,写法定数,W(W,个选票,),R,和,W,值设定所要遵照规则,:,W,选票总数二分之一,R+W,选票总数,分布式系统与WEB服务培训课件,第63页,6.6.7 虚拟分割算法,可用副本算法和法定数算法结合而来,实现:虚拟分割一个备份文件涉及服务器,划分成若干组,注意这是逻辑分组,一个组中含有足够副本服务器,能满足读法定数和写法定数则事务可在该组服务器上执行,这时候实际是采取法定数算法.若出现服务器故障便试图创建新分割,使得分组可以满足读法定数和写法定数,从而保证单拷贝可串行性.这种算法效率很高,在每个虚拟组内使用是可用副本算法,此方法是基于假设(实际分割较少产生,也是一种乐观方法.),分布式系统与WEB服务培训课件,第64页,