分布式系统与WEB服务

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