最新《分布式系统》第七章 分布式事务处理(共42张PPT课件).pptx

《最新《分布式系统》第七章 分布式事务处理(共42张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新《分布式系统》第七章 分布式事务处理(共42张PPT课件).pptx（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 分布式事务处理 n事务处理的基本模型 n事务处理的分类(fn li) n提交协议 n并发控制 n检测并防止分布式死锁 n多复制副本数据 1第一页，共四十二页。事务处理模型(mxng) 事务处理模型是一种抽象化的计算模型。几乎所有对事务处理的定义都要求整个处理过程的原子性(atomicity) 。对某个客户(进程) 的一系列请求而言，事务处理的原子性体现在要么这些请求全部成功地执行，要么这些请求一个也没有执行(all-or-nothing)。原子性隐喻着两重含义：(1) 故障原子性(failure atomicity)：即便服务器出现故障也要保证执行过程的原子性；(2) 持久性(dura

2、bility)：当一次事务处理成功后，所有与该事务处理相关的结果都必须永久地保存下来。事务处理(chl)应该具备的第二特征是隔离性(isolation)，即每一个事务处理(chl)过程不允许受到其它事务处理(chl)的干扰，犹如一个黑盒子，其内在的中间处理(chl)步骤是完全隐蔽的。事务处理的第三个特征是一致性(consistency) ，一致性意味着如果一个系统必须保持某些一成不变的东西，则无论事务处理发生前或发生后，这些东西依旧不变。 2第二页，共四十二页。事务处理模型(mxng)基本性质 : ACIDnAtomicity-原子(yunz)性 nConsistency-一致性 nIsola

3、tion-隔离性 nDurability-持久性 事务处理模型是临界区模型的特殊化：临界区是对各种共享资源(打印机、文件、存储器等等(dn dn)进行互斥访问的抽象，而事务处理是对共享数据进行互斥访问的抽象。 3第三页，共四十二页。基本(jbn)服务调用 服务过程解释存款存款( (账号，数额账号，数额) )将指定数额数额的款项存入给定账号账号取款取款( (账号，数额账号，数额) )从给定账号账号取出指定数额数额的款项平衡平衡( (账号账号) )返回给定账号账号的当前平衡总平衡总平衡()()返回该客户所有账号的总平衡开始事务处理开始事务处理( (标号标号) )开始指定标号标号的事务处理结束事务处

4、理结束事务处理( (标号标号) )结束指定标号标号的事务处理流产事务处理流产事务处理( (标号标号) )迫使指定标号标号的事务处理流产银行基本(jbn)业务服务4第四页，共四十二页。开始开始(kish)(kish)事务处理事务处理(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)银行(ynhng)服务的例子 我们将用T、U、V代表事务处理标号，用K、M、N代表不同的银行(ynhng)分行，用A、

5、B、C代表客户的分行账号，一个客户发出的一系列服务过程调用就可以合并为一次事务处理。 5第五页，共四十二页。TS1T22T21T12T11T2T1TS3S2S2S6S5S4S1S3(a)分布式平面(pngmin)事务处理 (b)分布式嵌套事务处理S7S0事务处理分类(fn li) 其中方框(fn kun)代表事务处理，圆形代表执行操作的服务器 6第六页，共四十二页。分布式事务处理n分布式事务处理的关键在于服务及数据的分布，即一个事务处理所需的服务与数据可能分散在不同的服务器上，因此，事务处理过程就必须在多台服务器上执行。 n分布式事务处理的调度(diod)与同步-多台服务器联合执行一个事务处理

6、时需要彼此协调，才能做到整个事务处理的成功提交 -常用的方法是由一个协调者(coordinator)通过服务器之间的通信来实现最终提交 7第七页，共四十二页。分布式事务处理例子(l zi)开始(kish)事务处理(T) ；K：取款(A，100) ；M：存款(B，100) ；N：取款(D，200) ；M：存款(C，200) ；结束事务处理(T)某客户要在K、M、N三个银行分行的A、B、C、D四个账号上执行转帐业务，即从K分行的A账号取出100元，存入(cn r)M分行的B账号去，然后从N分行的D账号取出200元并存入(cn r)到M分行的C账号。假定这三个分行的数据库分别位于三台服务器上，其中S

7、1管理K分行的A账号 ，S2管理M分行的B、C两个账号，S3管理N分行的D账号 8第八页，共四十二页。分布式银行(ynhng)事务处理 TS1S3S2(1.1) 开始(kish)事务处理(T) ；(1.2) K：取款(A，100) ；(1.3) 结束事务处理(T) ；(2.1) 加入(jir)服务器(T，S1) ； (2.2) M：存款(B，100) ；(2.3) M：存款(C，200) ；(3.1) 加入服务器(T，S1) ； (3.2) N：取款(D，200) ；K分行M分行N分行协调者协调者参与者参与者参与者参与者由于每个服务器可能同时执行不同的分布式事务处理，因此在整个系统中事务处理标

8、号必须是唯一的。首先启动分布式事务处理的那台服务器是整个事务处理的协调者服务器 9第九页，共四十二页。更新(gngxn)操作分解动作n存款存款( (账号账号(zhn ho)(zhn ho)，数额，数额) ) ：/ 从数据库读出存款余额平衡平衡 账号读出账号读出()()； / 把更新的余额写回数据库 账号写入账号写入( (平衡平衡 + + 数额数额) ) ；10第十页，共四十二页。更新丢失(dis)问题表中含有两个转帐事务处理T和U。这两个事务处理都在分行K的同一(tngy)台服务器上执行 开始事务处理(T) ： K：取款(A， 40) ； K：存款(B， 40) ；结束事务处理(T) ；开始事

9、务处理(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读出()(B) 200元B写入(B平衡 + 30)(B) 230元B写入(B平衡 + 40)(B) 240元11第十一页，共四十二页。非一致检索(jin su)问题 开始事务处理(T) ： K：取款(A， 100) ； K：存款(B， 100) ；结束事务处理(T) ；开始事务处

10、理(U) ： K：总平衡() ；结束事务处理(U) ；分解操作分解操作平衡平衡分解操作分解操作总平衡总平衡A平衡 A读出()(A) 200元A写入(A平衡 100)(A) 100元总平衡 A读出()100元总平衡 总平衡 + B读出() 100 + 200元总平衡 总平衡 + C读出() 300 + 200元B平衡 B读出()(B) 200元B写入(B平衡 + 100)(B) 300元12第十二页，共四十二页。事务处理并发时顺序(shnx)等价 当多个事务处理访问同一个数据时，顺序(shnx)等价性要求必须把每一个事务处理对该数据的完整(读/写)访问一一排序，严格禁止任何冲突 开始事务处理(T

11、) ： 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元13第十三页，共四十二页。顺序(shnx)等价 na) c) 三个事务

12、处理 T1, T2, T3nd) 可能出现(chxin)的调度开始事务处理开始事务处理(T1)(T1) x = 0; x = x + 1;结束结束事务处理事务处理(T1)(T1) (a)开始事务处理开始事务处理(T2)(T2) x = 0; x = x + 2;结束结束事务处理事务处理(T2(T2） (b)开始事务处理开始事务处理(T3)(T3) x = 0; x = x + 3;结束结束事务处理事务处理(T3(T3） (c)调度调度 1x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3合法合法调度调度 2x = 0; x = 0; x =

13、 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;非法非法(d)14第十四页，共四十二页。并发(bngf)控制算法n悲观算法-两阶段锁算法两阶段锁算法 (2PL)n中央控制 2PLn分布式 2PL-时间戳排序时间戳排序(pi x)算法算法 (TO)n基本 TOn多版本 TOn保守 TO-混合式算法混合式算法n乐观算法- 互斥锁，时间戳15第十五页，共四十二页。n利用互斥锁来实现顺序等价是最简单的一种并行控制方法(fngf) n服务器试图锁定一个事务

14、处理所要访问的数据，一旦某个数据被锁定之后，其它的访问请求都被挂起，直到这个数据的互斥锁被释放为止 n为了保证互斥的正确性，我们规定当一个事务处理释放了一把锁之后，就不能再申请任何新锁，也就是说，任何一个事务处理都分成两个阶段：第一阶段称为膨胀阶段(growing phase) ，在这个阶段里可以申请(任意多的)新锁；第二阶段称为收缩阶段(shrinking phase) ，在这个阶段里只准释放锁。一个事务处理必须遵循从膨胀到收缩的周期，这种周期被称为两阶段上锁(two-phase locking) 互斥锁算法互斥锁算法(sun f)(sun f) 16第十六页，共四十二页。n 膨胀阶段膨胀阶

15、段 当一个事务处理要求访问某个数据时：n1) 如果该数据尚未锁定，则服务器锁定数据，操作可以继续；n2) 如果该数据已经被另一个事务处理用写锁(互斥锁)锁定，则必须等待，直到写锁被释放为止(wizh)；n3) 如果该数据被其它事务处理用读锁(共享锁)锁定，则申请锁定成功，操作可以继续；n4) 如果该数据被这个事务处理自身锁定，在必要情况下可以将锁的类型提升，操作可以继续；n 收缩阶段收缩阶段 当一个事务处理提交或流产，服务器释放所有被锁定的数据 两阶段两阶段(jidun)(jidun)锁算法（锁算法（2PL2PL） 17第十七页，共四十二页。两阶段两阶段(jidun)(jidun)锁算法图示锁

16、算法图示膨胀阶段收缩阶段时间TU冲突理由读读无一对读操作的效果与其执行次序无关读写有一对读/写操作的效果取决于它们的执行次序写写有一对写操作的效果取决于它们的执行次序18第十八页，共四十二页。利用(lyng)互斥锁进行事务处理并发控制 开始事务处理(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)结

17、束事务处理(T)释放A，B锁定BB写入(B平衡 + 30)结束事务处理(U)释放B，C19第十九页，共四十二页。n我们之所以“乐观” ，是因为大多数事务处理应用并不一定存在冲突，它们共享数据的可能性很低。于是(ysh)，我们不必采用“悲观” 的方式来层层加锁，而可以用“乐观” 的态度允许事务处理尽可能地并发执行，并期望它们圆满成功。万一出现冲突，则选择某个发生冲突的事务处理令其流产，通知客户该事务处理需要重新启动。 乐观并发乐观并发(bngf)控制控制 20第二十页，共四十二页。n读阶段读阶段 在读阶段，该事务处理所访问的数据都有一套暂时版本，这套版本不对外，只由拥有者使用。采用暂时版本可以使

18、事务处理流产而不会影响到长存数据。当执行一个读操作时，如果数据的暂时版本已经存在，则读操作立即访问之，否则，就必须访问那个数据最近提交的值。写操作把每一数据的新值作为暂时值记录在案。显然，如果若干个并发事务处理共享同一个数据，则这个数据可能有不同的暂时值。除了上述规则外，对每一个访问的数据，事务处理还要维护两个数值集合：读集合包括该事务处理读出的数据，写集合囊括该事务处理写入的数据。 n验证阶段验证阶段 当事务处理试图提交时，就进入验证阶段，其目的是检测是否它所访问的数据与其它事务处理的操作有冲突。如果验证无冲突，该事务处理可以提交；否则我们就必须消解冲突。消除冲突的方法很简单：或者(huzh

19、)命令该事务处理流产，或者(huzh)从卷入冲突的事务处理中选择一个令其流产。n n写阶段写阶段 如果该事务处理已经通过验证，暂时版本中所记录的数据更新就成为永久性的。如果该事务处理是只读型事务处理，则它马上提交；否则就要等到暂存数据全部写入长存存储器后，执行提交操作。乐观乐观(lgun)并发控制算法并发控制算法 21第二十一页，共四十二页。验证(ynzhng)阶段 n我们为每一个进入验证(ynzhng)阶段的事务处理赋予一个事务号。事务号是一个整型数，按照递增的方式分配给事务处理，用以定义事务处理的验证(ynzhng)时序 n我们用T代表任何事务处理，把事务号作为下标，则Ti在时序上先于Tj

20、(如果ij) 。验证工作要在每一对Ti和Tj之间进行：要使得事务处理Ti与重叠事务处理Tj顺序等价，它们的分解操作必须满足下表例举的规则 TiTj规则读写Ti决不允许读Tj写入的数据写读Tj决不允许读Ti写入的数据写写Ti决不允许复写Tj写入的数据；Tj决不允许复写Ti写入的数据22第二十二页，共四十二页。时间时间(shjin)(shjin)戳算法戳算法 n对每一个事务处理T，我们要赋予一个启动时间戳ts(T) ；对T的每一个操作，都要赋予ts(T) 。注意，时间戳必须遵循全局排序关系。 n除了对事务处理的操作打时间戳之外，我们还要对系统中每一个数据，如客户账号A，打上读/写时间戳，记为tsR

21、(A) 和tsW(A) n每当一对(y du)操作发生冲突时，调度程序率先处理那个时间最小的操作。与乐观并发算法类似，写操作都被记录在暂时数据版本中，而且暂时版本仅在事务处理提交时才存入长存存储器 23第二十三页，共四十二页。n假定调度程序接收到来自事务处理T的读出读出(A)(A) 操作请求 ，T的时间戳为ts(T) ，但如果(rgu)调度程序发现ts(T) tsW(A) ，调度程序便允许T执行读操作，同时，调度程序还要更新账号A的时间戳，使得A的读时间戳tsR(A) max(ts(T) ，tsR(A) 。 时间戳调度(diod)程序 事务处理(Tj)规则写操作假如某个Ti曾进行过读操作而且T

22、i Tj，则Tj不得执行写操作写操作假如某个Ti曾提交过写操作而且Ti Tj，则Tj不得执行写操作读操作假如某个Ti曾提交过写操作而且Ti Tj，则Tj不得执行读操作24第二十四页，共四十二页。原子提交原子提交(tjio)(tjio)协议协议(1)(1)n“提交” 表示一个事务处理已经成功完成，它所做出的数据更新都已经安全地存入长存存储器中。 n早期(zoq)的分布式提交通常采用单阶段提交(1PC: one-phase commit) 协议。在这种协议中，系统需要一个协调者，它与所有涉及该事务处理的服务器通信，通知这些参与者进行提交或者流产操作，然后收集来自这些参与者的回应，直到所有服务器都完

23、成指定的操作为止。然而，单阶段提交协议有一个明显的缺点，如果某一台服务器无法执行协调者指定的操作，协调者也无能为力，甚至无法知道这一点。 25第二十五页，共四十二页。原子提交原子提交(tjio)(tjio)协议协议(2)(2)n两阶段提交(2PC: two-phase commit) 协议(xiy)：把提交工作分成两个阶段。在第一个阶段中，每一台服务器对该事务处理是否提交或流产进行选举，一旦做出提交选举后，该服务器就不能改变自己做出的承诺。在第二阶段，每一台服务器都将根据选举信息对该事务处理做出最后决定：如果任何一个参与者选举流产，则最终决定是流产；如果所有参与者都选举提交，则整个事务处理得到

24、提交。n三阶段提交(3PC) 协议等等：目前还仅限于学术讨论和文献引用，并没有得到广泛应用 。26第二十六页，共四十二页。2PC基本操作 操作返回值解释能否提交(标号)同意/否定执行提交(标号)无协调者通知参与者提交它们各自的事务处理执行流产(标号)无协调者通知参与者流产它们各自的事务处理已经提交(标号，参与者)无参与者通知协调者已经完成它那一部分的事务提交询问结果(标号)同意/否定参与者向协调者询问最终选举结果(用于容错机制)协调者询问参与者是否可以提交(tjio)，参与者做出回答27第二十七页，共四十二页。2PC协议(xiy) n 第一阶段：选举第一阶段：选举 ：(1) 协调者向所有参与者

25、发送能否提交能否提交信件。(2) 当一个参与者接收到能否提交能否提交信件，根据自身的状态返回“同意/否定”。注意，在回答“同意” 之前，参与者必须准备需要写入长存(chn cn)存储器的数据；反之，若回答“否定” ，则参与者可以立即流产。n 第二阶段：根据选举结果完成指定操作第二阶段：根据选举结果完成指定操作 ：(3) 协调者收集选举结果(包括自己的选举结果) ：如果所有结果都是“同意” ，则协调者决定提交，向所有参与者发送执行提交执行提交信件；否则，协调者决定流产，向所有曾经返回“同意”的参与者发送执行流产执行流产信件。(4) 曾经返回“同意” 信件的参与者必须等待来自协调者的最终命令。当它

26、接收到执行提交执行提交或执行流产执行流产信件后，则立即执行相应操作。如果执行的是提交操作，则在提交后向协调者返回一封已经提交已经提交信件。(5) 为了增强算法的容错能力，参与者在等待协调者的命令时可以采用“超时” 技术，即当长时间后尚未得到协调者的信件(如信件丢失)，参与者便可以向协调者发出信件询问结果询问结果，然后回到第四步继续等待。(6) 当协调者接收到所有已经提交已经提交回应后，协调者工作结束。 28第二十八页，共四十二页。2PC 阶段(jidun)划分29第二十九页，共四十二页。2PC协调者和参与者的通信(tng xn)步骤 协调者：协调者：步骤 状态(1) 准备提交 (等待选举)(3

27、) 提交(5) 结束参与者：参与者：步骤 状态(2) 准备提交 (未确定)(4) 提交能否提交同意执行提交已经提交30第三十页，共四十二页。分布式 2PCn协调者启动 2PCn参与者运行(ynxng)分布式算法达成全局提交/流产T22T21T12T11T2T1TS2S5S4S1地S3S000T11流产T12临时提交T2流产T22临时提交T1临时提交协调者T21临时提交31第三十一页，共四十二页。2PC的问题(wnt)n2PC协议是最为常用的分布式事务处理提交(tjio)协议，但是，由于协议中涉及“等待” 问题，人们也把这种协议称为阻塞提交(blocking commit)协议。 -就绪隐喻参与

28、者“阻塞等待”协调者-如果协调者发生故障，参与者无法知晓n无法实现独立恢复。-如果多台服务器发生故障，无法进行独立的故障恢复工作。32第三十二页，共四十二页。分布式死锁分布式死锁n在各种涉及互斥的算法中，只要算法采用互斥锁，就有可能在各种涉及互斥的算法中，只要算法采用互斥锁，就有可能发生发生“死锁死锁” ” 现象。现象。 n死锁的典型特征是一组事务处理形成了一条循环等待链 n死锁处理：-置之不理 由程序员对其负责-预防 不存在(cnzi)运行系统支持-避免 运行系统支持-检测恢复 不同的算法33第三十三页，共四十二页。TUVWWUTV(a) 简单简单(jindn)循环循环链链(b) 复杂复杂(

29、fz)循环循环链链n互斥n持有并等待(a) TUVWTn不容(brng)抢占(b) VWTVn循环链 VWV死锁 - 循环等待链 34第三十四页，共四十二页。分布式事务处理的死锁例子(l zi)事务处理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死锁35第三十五页，共四十二页。分布式事务处理的死锁例子(l zi) S1A S2 S3DCBVWU等待锁定锁定锁定锁定等待等待S1: U VS2: V WS3: W

30、 U36第三十六页，共四十二页。n等待-消亡规则：-如果 (ts(Ti) ts(Tj) 则 Ti 等待， 否则 Ti 消亡-Ti不容许抢占Tj-新事务处理优先n回卷-等待规则：-如果 (ts(Ti) ts(Tj) 则 Tj 回卷，否则 Ti 等待-如果Ti 先于Tj，抢占 Tj -旧事务处理优先问题: 代价太高，死锁难得发生，随机性很强。强制性避免死锁算法需要检测(jin c)每一次互斥操作，给系统带来过多的开销。避免(bmin)死锁算法37第三十七页，共四十二页。死锁检测死锁检测(jin c)(jin c)n死锁是一种稳定的状态n尽管(jn gun)无法从局部状态检测分布式事务处理的死锁，但

31、死锁依旧是环形等待链。n死锁检测算法：-中央式 周期性地收集等待状态-分布式 推出等待状态-提示式 构造检测体系38第三十八页，共四十二页。 S1A S2 S3DCBVWUwaitlocklock locklockwaitwaitS1 ：U VS2 ：V WS3 ：W U中央检测中央检测(jin c)(jin c)算法算法 39第三十九页，共四十二页。分布式检测分布式检测(jin c)(jin c)算法算法 n分布式死锁检测技术，称之为边跟踪(edge chasing) 算法。n这个算法并不需要构造(guzo)全局等待图，而是由每一台服务器根据自己掌握的等待信息(局部等待图的边)来判断是否出现

32、死锁。 这个算法的关键是在服务器之间传送的一种叫作探测(probe)的信件，一封探测信件代表全局等待图里的一条有向(等待)路径(path)。如果这封探测信件到达某个服务器，而该服务器发现信件里描述的路径已经构成一条有向环，则这条路径上的结点(事务处理)便陷入死锁。40第四十页，共四十二页。边跟踪(gnzng)算法n 初始初始 ：当服务器Si发现事务处理T开始等待事务处理U，而U已经在等待另一台服务器Sj管辖的数据，则Si向Sj发送一封探测信件，信中内容为等待边T U。假如U所等待的是共享锁，则这封探测信就必须发往所有相关的服务器。n 检测检测 ：当服务器Sj接到探测信件，便根据自己掌握的局部等

33、待图判断是否出现死锁，并且(bngqi)进一步决定是否要把探测信件转发到其它服务器。例如，当Sj接收到探测信T U，它首先检查U是否也在等待。如果U正在等待V，则Sj把这条边加入到探测信的路径中，TUV，如果V所等待的是服务器Sk中的数据锁，则这封更新后的探测信被转发到Sk。按照这种方法，探测信件沿着全局等待图逐步形成一条路径，每次经过转发时，都在路径上添加一条新边。检测死锁的方法很简单，在转发一封探测信之前，只要检查一下信中的路径，如果头尾都是同一个事务处理，如TUVT，则出现有向环，发生死锁。n 解除解除 ：当发现死锁后，就必须在那个有向环内选择一个结点(事务处理) ，勒令它流产。41第四十一页，共四十二页。内容(nirng)总结第七章 分布式事务处理。第七章 分布式事务处理。事务处理模型是一种抽象化的计算模型。其中方框代表事务处理，圆形代表执行操作的服务器。/ 从数据库读出存款余额。/ 把更新的余额写回数据库。我们(w men)为每一个进入验证阶段的事务处理赋予一个事务号。对T的每一个操作，都要赋予ts(T)。“提交” 表示一个事务处理已经成功完成，它所做出的数据更新都已经安全地存入长存存储器中。协调者询问参与者是否可以提交，参与者做出回答第四十二页，共四十二页。