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