最新《分布式系统》第八章 复制及复制一致性(共54张PPT课件).pptx

《最新《分布式系统》第八章 复制及复制一致性(共54张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新《分布式系统》第八章 复制及复制一致性(共54张PPT课件).pptx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 复制(fzh)及复制(fzh)一致性 复制：不仅可以对数据(shj)起到保护作用，也可以增强数据(shj)的可用性和数据(shj)服务的容错能力。 我们必须考虑复制的透明性、可调节性、一致性，以及快速的反应时间和较大的系统吞吐量。最为重要的是复制的一致性，因为透明性和可调节性仅仅影响到使用复制技术的方便程度，而一致性却影响到复制技术的成败。 一致性模型以及一致性协议 更新（update）以及更新传播算法。1第一页，共五十四页。动机动机(dngj)和目的和目的n改进性能 n如果数据被大量的客户共享，就不应该只由一台服务器管理这些数据，因为这样做就产生了一个系统瓶颈，限制了系统的反应时间和

2、吞吐能力。最好的方法就是(jish)把数据的副本分布在一组服务器上，每一台服务器都为地理位置就近的一组客户提供服务。 n增强容错能力 n如果对每一个客户请求，我们都用一组服务器来并行地提供服务，则即便有个别服务器发生故障，我们还是有可能保证客户请求被正确地执行。 n强化可用性 n如果数据和数据服务被复制到两台或多台服务器上，这些服务器都运行相同的软件，提供等价的服务，而且故障独立(即一台服务器的故障不会影响到其它服务器) ，则从原理上说，客户就可以从一台出现故障的服务器切换到另一台正常运行的服务器上，继续请求数据服务。 P: 一台服务器故障概率(gil); 1 P = 服务可用性， 例如： P

3、 = 5%， 则95% 的时间系统可以提供服务。Pn: n 台服务器故障概率; 1 Pn = 服务可用性， 例如， P = 5%, n = 3，则 99.875% 的时间系统可以提供服务。2第二页，共五十四页。复制技术的基本复制技术的基本(jbn)结构（结构（1）n复制透明性：客户不必了解系统中存在多个物理复制n 复制一致性：所有复制的副本在任何时刻都完全一样，于是，在任何一个副本进行读操作都会得到(d do)相同的结果。 客户客户前端前端RMRMRM客户客户前端前端客户客户前端前端服务服务服务器服务器服务器服务器服务器服务器复制管理器：Replica Manager3第三页，共五十四页。复制

4、技术的基本复制技术的基本(jbn)结构（结构（2）n我们用一个称为前端(front end) 的系统成份来沟通客户和数据服务。引入前端的主要目的是加强系统的透明性和模块化，客户只与前端通信，提交请求或者接收数据，而无需与复制管理器直接对话。 n前端与复制管理器之间的对话方式在不同的结构(jigu)模型中亦有所区别，例如，当一个前端在授理客户请求时，它可以只与一个服务管理器通信，也可以同时与多个服务管理器通信。此外，当一个客户请求在多个服务管理器上执行时，前端也可以用来核对这些复制管理器返回的结果，在少数出错的情况下，返回给客户多数一致的那个结果，从而体现系统的容错能力。4第四页，共五十四页。复

5、制技术的基本复制技术的基本(jbn)结构（结构（3）CLCLFEFERMRMRMCLFECLCLFEFEPRRMSLRMSLRMCLFEWW WR RR(a) 私语结构私语结构(b) 主副本结构主副本结构5第五页，共五十四页。复制技术的基本复制技术的基本(jbn)(jbn)结构结构（4）n私语结构(gossip architecture) ：复制管理器之间需要周期性地交换“私房话” ，通知彼此必须更新的数据。在这种结构中，通常的情况下每一个前端只与一个复制管理器对话，于是，当一个复制管理器执行更新操作后，就必须把更新后的结果通过内部协议传送给其它的复制管理器，以求数据一致(yzh)。n主副本(

6、primary copy) 结构：前端必须分别对待只读和更新操作。如果客户请求是只读操作，则可以由任意一个复制管理器执行；而当客户请求属于更新类操作，则必须由一个称为“主” 复制管理器的进程(服务器)授理。在一个系统中，只存在一个主复制管理器，而其它的都称为“从” 复制管理器，当然，在主管理器发生故障时，我们可以利用选举算法重新推选出一个主复制管理器。数据的更新操作都在主复制管理器上进行，并由它通知所有从复制管理器达到数据一致性。 6第六页，共五十四页。一致性模型一致性模型(mxng)n所谓一致性模型，本质上是介于进程和数据仓库之间的一种协议：如果进程同意遵循某个模型给定的规则，则数据仓库就能

7、正常运转，从而提供符合(fh)该模型定义的数据服务。 进程进程 副本副本副本进程数据仓库7第七页，共五十四页。一致性模型一致性模型(mxng)分类分类严格顺序 因果流水线弱释放入口以数据为中心的一致性模型 强弱以客户为中心的一致性模型 单调读单调写读随写写随读8第八页，共五十四页。严格严格(yng)一致性模型一致性模型 -假定假定x为数据仓库中的一项共享数据，任何为数据仓库中的一项共享数据，任何对对x的读操作都必须返回最近的读操作都必须返回最近(zujn)一次写入一次写入x的值。的值。-其中隐喻着一个全局绝对物理时钟，因此“最近” 这个术语含义精确，不存在多义性。 -然而，分布式系统无法实现这

8、种绝对时钟。9第九页，共五十四页。严格严格(yng)一致性模型图例一致性模型图例 nWi(x)a 以及 Ri(x)b ：Wi(x)a表示进程(jnchng)Pi把值a写入数据x；而Ri(x)b表示进程(jnchng)Pi从数据x读出值b；当无二义性时，我们会省略W/R操作的下标。此外，我们假定每一项数据的初始值为。 R(x)a(a) 严格一致(b) 非严格一致W(x)aR(x)aW(x)aR(x) R(x)aP2 P1：P2 时间时间P2 P2 P1 10第十页，共五十四页。顺序顺序(shnx)(shnx)一致性模型一致性模型 n假定假定x x为数据仓库中的一项共享数据，当一组进程对为数据仓库

9、中的一项共享数据，当一组进程对x x进行读进行读/ /写操作时，如果每个进程都遵循程序所确定写操作时，如果每个进程都遵循程序所确定的操作次序，而且所有进程遵循一种同样的交替操作的操作次序，而且所有进程遵循一种同样的交替操作顺序，就必然得到相同的结果。顺序，就必然得到相同的结果。 -当多个进程在不同的计算机上运行时，对共享数据的任何读/写交替顺序都是可以接受的，但有一条必须明确：所有的进程都必须看到(遵循) 相同的操作顺序。这个定义并没有提及时间，也就是说，“最近” 写入的要求被删除了。 -这个定义隐喻着一个弱点，即同样一个程序(同一组进程) 的两次执行(zhxng)过程或许会产生不同的结果，其

10、间的道理很简单，该定义只要求所有进程在一次执行(zhxng)中对共享数据的观点一致，而没有定义什么才是正确观点，因为共享数据的正确观点必然与全局绝对时间密切相关。 11第十一页，共五十四页。顺序顺序(shnx)(shnx)一致性模型图例一致性模型图例 (a) 顺序一致R(x)aP1：P2：P3：P4： W(x)aW(x)bR(x)bR(x)aR(x)bR(x)bP1：P2：P3：P4： W(x)aW(x)bR(x)bR(x)aR(x)a(b) 非顺序一致时间时间(a）尽管在物理时间上，W(x)b操作稍晚于W(x)a，但进程P3和P4的读操作对共享数据x都有一致的观点，先得到b，然后才得到a。(

11、b) P3和P4的读操作对共享数据x的观点就不一致，P3先看见(kn jin)b，后看见(kn jin)a，而P4恰恰相反，先a后b，不满足顺序一致性的定义。12第十二页，共五十四页。因果因果(yngu)(yngu)一致性模型一致性模型 n所有进程必须对具有所有进程必须对具有(jyu)(jyu)潜在因果关系的写操潜在因果关系的写操作持有一致的观点，而无因果关系的并发写操作持有一致的观点，而无因果关系的并发写操作可以在不同计算机上有不同作可以在不同计算机上有不同( (排序排序) )的观点。的观点。- 所谓因果关系指的是在同一进程内前后两个操作A 和B 之间存在着依赖关系，即B依赖于A，没有A，就

12、得不到B。13第十三页，共五十四页。因果因果(yngu)(yngu)一致性模型图例一致性模型图例 R(x)cP1：P2：P3：P4： W(x)aR(x)aR(x)aR(x)bR(x)aR(x)bR(x)cW(x)bW(x)c时间(a) 因果一致R(x)aP1：P2：P3：P4： W(x)aR(x)aR(x)bR(x)bR(x)aW(x)b时间(b) 非因果一致14第十四页，共五十四页。PRAM一致性模型一致性模型(mxng)(mxng)n所有所有(suyu)(suyu)进程必须对同一个进程发出的写操作持有一致的观点，进程必须对同一个进程发出的写操作持有一致的观点，而对不同进程的写操作可以有不同

13、而对不同进程的写操作可以有不同( (排序排序) )的观点。的观点。称为FIFO，或流水线式随机访问内存(PRAM)一致性，因为单一进程的写操作完全可以像流水线作业那样实现，不存在等待别的进程完成某个操作之后才能开始下一个操作的情况。 因为看上去每一个进程都把自己顺序执行写操作的结果放在一个先进先出的队列中，每个进程只保证自己的写操作排序，而与其它进程写操作的相对次序无关。从实现的角度来看，这种一致性要比前面几种一致性容易得多，我们仅需要为每一个写操作附加一对标记(进程，顺序号) ，然后按照顺序号执行写操作就可以了。15第十五页，共五十四页。PRAM一致性模型一致性模型(mxng)(mxng)图

14、例图例R(x)aR(x)cP1：P2：P3：P4： W(x)aR(x)aR(x)bR(x)cR(x)bR(x)aW(x)bW(x)c时间从x 读出的值必须满足先b后c，而a的次序可以(ky)任意16第十六页，共五十四页。基于基于(jy)(jy)读读/ /写次序的一致性模型之特征写次序的一致性模型之特征 一致性模型典型特征严格一致性按照全局绝对时间执行操作顺序一致性对操作进行全局排序因果一致性对具有因果关系的操作进行排序PRAM一致性对单进程操作进行排序17第十七页，共五十四页。基于(jy)同步操作的一致性模型 n这里我们讨论的模型不再关心每一个操作的具体次序，而是关心进程之间的同步。 n在实践

15、中人们发现许多应用具备下面(xi mian)两种特征：n(1)一个分布式系统中的许多(大多数) 进程没有必要了解每一个写操作；n(2)一个分布式系统中的许多(大多数) 进程没有必要了解中间性的写操作。实际上，这些所谓的中间性写操作往往是在一个临界区执行过程内部的写操作，根本没有必要暴露给临界区外的进程。n我们可以把一组写操作归结成一个临界区操作，仅当一个进程完成临界区操作之后，才把写入的最终结果通知所有进程，而没有必要担心中间写操作的次序或对外界的影响。 18第十八页，共五十四页。弱一致性模型弱一致性模型(mxng)(mxng)n(1) (1) 对同步变量的访问必须遵循顺序一致性模型；对同步变

16、量的访问必须遵循顺序一致性模型；n(2) (2) 在整个分布式系统中，仅当所有进程以前的写操作在整个分布式系统中，仅当所有进程以前的写操作都全部完成后，才允许对同步变量施加操作；都全部完成后，才允许对同步变量施加操作；n(3) (3) 仅当所有以前的同步变量操作全部完成后，才允许访问数仅当所有以前的同步变量操作全部完成后，才允许访问数据仓库中的数据。据仓库中的数据。 -第一条性质要求所有进程必须对同步变量的观点一致，也就是说，如果S和Q为同步变量，则对这两个变量的同步操作是否应为先S后Q还是先Q后S并不重要，重要的是所有进程都必须持有一致的观点，要么都是先S后Q，要么都是先Q后S。 -第二条性

17、质表示同步操作必须保证所有的局部写操作，无论是正在进行(jnxng)、半途完成、或者已经完成的写操作，都施加在数据仓库的所有副本上 。-第三条性质是针对同步操作的，当访问数据仓库时，无论是读还是写，所有以前的同步操作都必须已经结束。 19第十九页，共五十四页。弱一致性模型弱一致性模型(mxng)(mxng)图例图例同步(a) 弱一致P1：P2：R(x)a同步R(x)aW(x)b同步时间P1：P2：P3：W(x)aR(x)aR(x)b同步R(x)aR(x)b时间W(x)b同步R(x)bR(x)b(b) 非弱一致(a)进程P1在执行(zhxng)了两次写操作之后发出同步操作，而进程P2和P3在尚未

18、同步之前，它们对数据的观点不可能达成一致，因此可能以任何次序读出数据值，一旦同步之后，就只能读出b。(b)进程P2在执行读操作之前已经实施了同步操作，因此它必须遵守P1同步后的顺序一致性，也就是说，它读x的值应该是b，而决不是a。 20第二十页，共五十四页。n(1) (1) 当一个进程对某个共享变量执行读当一个进程对某个共享变量执行读/ /写操作之前，该进程写操作之前，该进程以前发出的所有以前发出的所有ACQACQ操作都必须已经成功完成；操作都必须已经成功完成；n(2) (2) 当一个进程执行当一个进程执行RELREL操作之前，该进程以前发出的所有读操作之前，该进程以前发出的所有读/ /写写操

19、作都必须已经成功完成；操作都必须已经成功完成；n(3) (3) 对同步变量的访问必须遵循对同步变量的访问必须遵循PRAMPRAM一致性。一致性。n我们也可以用屏障(barrier) 来实现(shxin)释放一致性模型。屏障是一种以程序阶段为基准的同步机制：在所有进程尚未完成阶段N之前，不允许任何进程开始N+1阶段。于是，当一个进程到达某个阶段的屏障时，它必须等在那里直到其它进程都到齐为止，然后再一起进入下一阶段。如果到达屏障的进程是该阶段的最后一个进程，则对所有共享数据进行同步(一致化) 。从一个屏障出发的操作对应于申请操作，而到达一个屏障的操作对应于释放操作。 释放释放(shfng)(shf

20、ng)一致性模型一致性模型21第二十一页，共五十四页。释放释放(shfng)(shfng)一致性模型一致性模型图例图例释放LW(x)bP1：P2：P3：申请L申请LR(x)aR(x)b时间W(x)aR(x)b释放L进程P1首先请求访问临界区，执行了两次写操作之后发出释放访问操作。进程P2亦请求访问临界区，然后执行读操作并释放访问。这种临界区机制保证进程P2读出x的值是b，除非P2的请求访问操作在P1的临界区请求之前被执行。而例子中进程P3没有要求进入临界区，所以系统不保证它能够得到(d do)x的最新值，也就是说，它可能得到(d do)b也可能得到(d do)a。 22第二十二页，共五十四页。

21、n(1) (1) 当一个进程对某个同步变量执行当一个进程对某个同步变量执行ACQACQ之前，这个同步变量所保护的之前，这个同步变量所保护的数据的所有更新操作都必须已经成功完成；数据的所有更新操作都必须已经成功完成；n(2) (2) 在一个进程以互斥方式访问某个同步变量之前，不得有其它进程在一个进程以互斥方式访问某个同步变量之前，不得有其它进程( (哪怕是以互哪怕是以互斥斥) )持有这个同步变量；持有这个同步变量；n(3) (3) 当对一个同步变量的互斥访问已经完成后，任何其它进程对该同当对一个同步变量的互斥访问已经完成后，任何其它进程对该同步变量的非互斥访问都必须等到该同步变量的拥有者完成之后

22、才能进步变量的非互斥访问都必须等到该同步变量的拥有者完成之后才能进行行。n第一条规则保证进入临界区之前的一致性，也就是说，当执行申请时，所有远程的数据更新都要可见，并且与局部副本取得一致。第二条规则保证互斥性，即在更改共享数据之前，一定要处于互斥的临界区内，外界进程不能干扰(gnro)。第三条规则是为非互斥访问共享变量的进程而设的，即在访问之前，必须首先与同步变量拥有者通信，以得到共享数据的最新更改。入口入口(r ku)(r ku)一致性模型一致性模型 23第二十三页，共五十四页。入口入口(r ku)(r ku)一致性模型一致性模型图例释放Lx释放LyW(y)bP1：P2：P3：申请Lx申请L

23、x申请LyR(x)a时间W(x)aR(y)bR(y)申请LyR(x)Lx和Ly分别为保护数据x和y的同步变量。进程P1首先请求同步变量Lx，写入x的新值，然后请求同步变量Ly，写入y的新值，完成之后，依次释放(shfng)Lx和Ly这两个同步变量。进程P2执行读操作，但它只请求同步变量Lx，却没有请求Ly，于是，x的值具备一致性，而y的值却有任意性，可能是(如例子所示) ，也可能是b。对进程P3来说，由于它请求同步变量Ly, 当Ly被P1释放之后，它的申请操作才得以成功，因此读出y的值必然是b。24第二十四页，共五十四页。基于(jy)同步操作的一致性模型之特征 一致性模型典型特征弱一致性仅当同

24、步操作后才保证数据一致化释放一致性退出临界区时实施数据一致化入口一致性进入临界区时对所保护的数据进行一致化25第二十五页，共五十四页。以客户以客户(k h)为主的一致性模型为主的一致性模型 n这类数据仓库的共同特征是以读为主，以写为辅：即便有更新操作，这些操作也很少同时进行，即便同时进行 ，也很容易解决时序冲突。这类数据仓库只满足一种非常弱的一致性模型，称为最终一致性。 n例子：-DNS:每个域只能由一个授权管理员进行更新工作 -WWW系统就是采用最终一致性的。一般而言，只要客户一直访问数据仓库中的同一个复制，最终一致性就可以得到保证(bozhng)。 n最终一致性模型面临的典型问题，往往发生

25、在一个客户使用不同的复制(副本) 的情况下。为了缓解这种不一致性，我们引入以客户为中心的一致性模型。之所以说以客户为中心，是因为我们只保证一个单独的客户在访问数据时，数据仓库满足一致性，而对不同的并发客户不提供任何保证。26第二十六页，共五十四页。以客户为中心以客户为中心(zhngxn)的一致性模型语义的一致性模型语义n假定进程 P 在两个副本上执行读x操作。n我们可以有四种语义：-单调读单调读-一旦读x，后续的读操作必须返回同样(tngyng)的值，或更新的值。n单调写单调写n在执行写操作时，前一次的写操作必须已经传播到所有副本。n读随写读随写:n在执行读x操作时，必须返回前一次的写x操作之

26、值。n写随读写随读-在执行写x操作时，必须依赖读x操作的同样的或更新的值。27第二十七页，共五十四页。单调单调(dndio)读一致性模型读一致性模型 n如果一个进程读出数据如果一个进程读出数据x的值，则在数据的值，则在数据x上的任何后继读操作要么上的任何后继读操作要么返回相同的值，要么返回更新的值。返回相同的值，要么返回更新的值。 n我们用xit 代表局部副本Li上数据x在时间t的版本，这个版本是自从初始化以来在该局部副本上执行了一系列写操作所形成的结果。为了描述这个写操作系列，我们冠以WS(xit) 。n当局部副本Li上数据x在不同时间t1、t2被更新的话，我们就在WS系列中用带下标的时间来

27、刻划这些操作，如WS(xit1 ；xit2) 。当然，在没有二义性的情况下，我们也可以省略时间参数，记作WS(xi ；xi)。n除了表述方法的不同之外，时间坐标上的客体也不再是进程，而是局部副本Li。值得指出的是，我们在时间坐标上用不同地理位置(d l wi zh)的局部副本代替了进程，根据我们的假定这些副本数据都只有一个拥有者，于是这些局部副本也只能由同一个进程所更改。 28第二十八页，共五十四页。单调单调(dndio)读一致性模型图例读一致性模型图例 n以电子信件系统为例，一个(y )用户的信箱可能被分布复制在不同的机器上, 于是，新来的信件或许被插入任何一台机器的副本中。对不同机器副本的

28、更新以懒惰的方式进行，仅当一个副本需要进行一致化的时候，才调入更新数据。如果一个用户在北京读过自己的电子信件，然后乘飞机到了上海，又开启了自己的电子信箱，满足单调读一致性的电子信件系统保证该用户在北京曾读过的信件一定会出现在上海的电子信箱中。 R(x2)(a) 单调读一致(b) 非单调读一致WS(x1)WS(x1;x2)R(x1)R(x2)WS(x1;x2)L2 L1：L2 时间时间R(x1)WS(x1)WS(x2)L1：29第二十九页，共五十四页。单调单调(dndio)读一致性模型读一致性模型 n一个进程写入数据一个进程写入数据x的操作必须在该进程对数据的操作必须在该进程对数据x上的上的任何

29、后继写操作之前完成。任何后继写操作之前完成。n这条规则意味着无论(wln)该进程如何变化其所处的地理位置(即无论访问任何副本) ，只要是该进程发出的写操作，都必须依次完成，不得“后来者居上” 。n其潜在的含义是一个进程在对某个副本执行写操作之前，必须把该进程以前做出的任何写操作反馈到这个副本上来。 30第三十页，共五十四页。单调读一致性模型单调读一致性模型(mxng)图例图例 n进程首先在局部副本L1上执行写x的操作，记作WS(x1) 。稍后，该进程在局部副本L2上执行另一次写x的操作，记作WS(x2) 。要想保证单调写一致性，第二次写入x之前，WS(x1) 这个先前的写操作都必须传播到副本L

30、2上。n副本L2在写入x之前没有(mi yu)执行同一进程先前发出的WS(x1) 操作，因此无法保证单调写一致性。WS(x2)(a) 单调写一致(b) 非单调写一致WS(x1)WS(x1)L2 L1：L2 时间时间WS(x1)WS(x2)L1：31第三十一页，共五十四页。读随写一致性模型读随写一致性模型(mxng) n一个进程在数据一个进程在数据x上的写操作必须在该进程对数据上的写操作必须在该进程对数据x上的任上的任何后继读操作之前完成。何后继读操作之前完成。n一个进程读出的值必须是该进程刚刚写入的那个值，无论该进程在哪个副本写入，在哪个副本读出，都必须遵循这个条件。n以WWW网页管理为例：假

31、定你是网页管理员，使用普通的编辑程序来修改某个页面。修改写入之后，你打开浏览器检查修改结果(ji gu)，但你可能发现读出来的仍然是修改前的网页。之所以发生这种情况，是因为浏览器调入了存放在缓存内的旧网页，而没有读入新修改的文件。要想解决这个问题，就必须使用文字处理和浏览器合为一体的程序，这种程序才保证读随写一致性，即读出你刚刚写入的网页。 32第三十二页，共五十四页。读随写一致性模型读随写一致性模型(mxng)图例图例 n进程首先在局部副本L1上执行写操作WS(x1)，稍后，该进程在局部副本L2上执行一次读x的操作。读随写一致性保证在读出x之前，WS(x1) 操作已经反映到副本L2上。也就是

32、图中的WS(x1 ；x2) ，意味着WS(x1) 是WS(x2) 的组成(z chn)部份 。n副本L2在读x之前所执行的WS(x2) 没有包括WS(x1) 操作，因此无法保证读随写一致性。读随写一致性在执行时序上非常相仿于单调读一致性，只不过此刻的一致性取决于最近的一次写操作，而非最近的一次读操作。 R(x2)(a) 读随写一致(b) 非读随写一致WS(x1)WS(x1;x2)L2 L1：L2 时间时间WS(x1)WS(x2)R(x2)L1：33第三十三页，共五十四页。写随读一致性模型写随读一致性模型(mxng) n一个进程在数据一个进程在数据x上的写操作必须遵循该进程对数据上的写操作必须遵

33、循该进程对数据x的的前一次读操作之结果而进行。前一次读操作之结果而进行。 n对数据x的更新必须以同一进程前次读出x的值为基准。 n在互联网上，人们可以根据自己的兴趣参加各种各样的新闻组，不同的新闻组都有自己独特的讨论课题或者关心的问题。同一个新闻组的数据库以分布式复制的方式存放在不同的地理位置上，用户可以访问就近的副本。假定某个用户阅读了一篇文章，并就此(jic)文章写了读后感。根据写随读一致性，必须在那篇文章写入到所有副本之后，读后感才能贴到其它的副本上，否则就会出现读后感写在文章出笼之前的情况34第三十四页，共五十四页。写随读一致性模型写随读一致性模型(mxng)图例图例 n(a）进程在局

34、部副本L1上读出x1，这个读操作马上反馈到局部副本L2上，即图中的WS(x1 ；x2) ，意味着R(x1) 所读出的值是WS(x2) 的组成(z chn)部份，然后这个进程执行写操作W(x2)。n(b) 副本L2在写x之前所执行的WS(x2) 没有包括R(x1) 操作后的更新工作，因此无法保证写随读一致性。 R(x2)(a) 写随读一致(b) 非写随读一致WS(x1)WS(x1:x2)L2 L1：L2 时间时间WS(x1)WS(x2)R(x2)R(x1)R(x1)L1：35第三十五页，共五十四页。复制(fzh)配置n在开始设计一个分布式数据仓库(复制系统) 时，我们要先回答三个问题：什么时候需

35、要建立副本？由何人建立？建立在哪里？首先，从逻辑(lu j)结构上看，我们可以有三种类型的复制，如上图所示。客户创建(chungjin)的复制长存复制长存复制服务器创建的复制客户客户高速缓存镜像外推36第三十六页，共五十四页。长存(chn cn)复制n通常情况下，一个分布式数据仓库由一组为数有限的常存复制构成，或者集中在同一地理区域内以提高服务性能，或者分散在不同的地理位置上以减少(jinsho)网络通信开销。例如，典型的WWW网站就采用上面两种形式的常存复制。n在一个网站中心，可能有若干台服务器管理各自的局部复制，并且以并发的方式为访问者提供服务，以期获得较大的吞吐率。n而另一方面，这个网站

36、也许会在不同的省份、国家建立称之为镜像(mirror site) 的服务器，这些服务器也管理相同的副本数据，客户可以根据自己的需要与方便访问任何一个镜像网站。值得指出，无论是位于一个网站内的一组复制服务器还是分散在不同地点的镜像服务器，其共同之处在于这种类型的副本个数有限，而且往往是静态构成的，在运行中基本不会发生变化。37第三十七页，共五十四页。服务器发起(fq)的复制 n在某些情况下，分布式数据仓库的服务器自身也可以发起创建新的复制，其目的是改善系统的服务性能。例如，某电视台的网站设在北京，在正常情况下完全可以为来访者提供及时的网页服务。但在春节期间，人们对这个网站的访问就突然增多，甚至多

37、到无法应付。于是，在不同的省份建立(jinl)一些暂时的副本就可以缓解这种突如其来的密集访问，我们把这一类的复制称为外推式缓冲(push cache) 。n近年来，由服务器动态地创建复制的技术在网页服务系统中得到广泛的重视。这类服务并不针对某个公司或单位，而是面向用户，把最常用的文件通过动态复制技术散布到互联网的网页主持服务器 (Web Hosting Server) 上，以便为用户提供快捷的查询服务。 38第三十八页，共五十四页。服务器发起(fq)的复制例子n对来自不同客户的请求进行计数：n(1) 系统设定两个值：del(S, F) 和 rep(S, F)n(2) 如果 countQ(P,

38、F) rep(Q, F) , 则在服务器P上复制(fzh) F n(3) 如果 countQ(P, F) del(Q, F) , 则在服务器P上删除 F C1C2 文件 F客户服务器P服务器P39第三十九页，共五十四页。客户发起(fq)的复制 n由客户发起的复制就是存放在客户高速缓存中的副本数据。原则上，客户缓存中的数据完全由客户(程序) 自行管理，分布式数据仓库对这些副本的一致性不承担任何责任。客户复制技术的主要目的是减少访问开销，是一种典型(dinxng)的用空间(客户空间) 换取时间(系统及网络传输时间) 的例子。我们这里所谓的客户空间可以是位于客户计算机上的内存或外存，也可以是一台局部

39、网里的服务器。客户缓存(可以是独享缓存，也可以是多个客户的共享缓存)里保存客户最近调入的副本数据，如果客户的大多数请求都是只读型操作，而且命中缓存内存放的副本，则马上就能够返回客户请求的数据。n 保留在客户缓存中的副本数据一般都是暂时性的，以网页浏览器为例，当缓存中某些网页数据太陈旧(以时间戳为基准) ，或者当缓存溢出，需要为新调入的网页腾出空间的时候，某些副本数据就被更新或删除，从而体现了(非常弱的)最终一致性。40第四十页，共五十四页。更新(gngxn)传播 n(1)传播更新通知传播更新通知：当某个副本被修改时，仅把更新消息传播给其它副本；n(2)传播更新数据传播更新数据：在某个副本被修改

40、后，把更新后的数据传播给其它副本；n(3)传播更新操作传播更新操作(cozu)：当某个副本执行修改操作时，把同样的更新操作传播给其它副本。41第四十一页，共五十四页。推出(push)和拽入(pull)协议(xiy)n推出指的是更新发起者主动向其它副本发送更新数据，根本不管对方是否需要。当一个分布式复制系统需要较高的一致性时，往往都采用(ciyng)推出方案。 n而拽入指的是当某个副本需要进行一致化时，才主动向外界寻求更新数据。拽入方案通常应用于客户发起的复制系统，仅当客户需要的时候，才向数据仓库索取更新数据。 42第四十二页，共五十四页。传染(chunrn)协议 n传染病科学家的研究目的是如何

41、防止病源的扩散，而传染算法的目的却是如何尽快地把数据更新传染给众多的副本。虽然目的不同，但我们可以使用同样的术语。n如果一台服务器已经得到了更新数据，则称为感染(infective) 服务器 ；而尚未得到更新数据的服务器被称为易感(susceptible) 服务器；如果某台感染服务器放弃向外传播更新，则被称作出局(removed) 服务器。 n我们采用传染算法的系统模型作出下列假定：n(1)系统中包括n个副本；n(2)对某个数据x的更新都源于同一台服务器S，这样就可以避免写冲突；n(3)记载(jzi)在任一台服务器S中的数据x之值为VAL(x, S) ；n(4)数据x的每一次更新都携带时间戳，

42、记作T(x，S) 。43第四十三页，共五十四页。反熵传染反熵传染(chunrn)算法算法n实现传染算法的一种常用模型是反熵(anti-entropy) 模型，其规则如下：n每一个复制周期性地随机选择另一个复制，交换更新，导致最终一致每一个复制周期性地随机选择另一个复制，交换更新，导致最终一致性。性。 n当服务器S随机选择服务器S交换更新数据时，我们可以采用(ciyng)三种策略之一：n推出：推出：S仅把自己的更新数据发送给S，即n如果T(x，S) T(x，S) ，则VAL(x, S) VAL(x, S) ；n推出推出/拽入：拽入：S和S彼此交换更新数据。44第四十四页，共五十四页。反熵传染算法

43、反熵传染算法(sun f)性能性能n在反熵模型中，如果只采用推出策略，传播更新的速度就比较慢。令Pi代表S在第i次反熵模型周期之后仍旧是易感服务器(即尚未被感染) 的概率，则在推出策略下(当n很大时)，下一个周期S依旧落选的概率为: nP i + 1 = Pi(1 1/n) n(1-Pi) Pi e-1n在很多服务器都已经被感染的情况下，拽入策略就很有效。因为这时发起更新的服务器是一台易感服务器，它随机选择的那台服务器很有可能已经被感染，于是便可以得到更新数据(shj)(即自身得到传染) 。同样，令Pi代表S在第i次反熵模型周期之后仍旧是易感服务器(即尚未被感染) 的概率，在拽入策略下，下一个

44、周期S选择一台易感服务器的概率为：nPi+1 = Pi2n在采用推出在采用推出/拽入混合策略时，更新传播可以在拽入混合策略时，更新传播可以在O(log(n) 周期内完成。周期内完成。45第四十五页，共五十四页。私语私语(sy)算法算法 n这个算法有点类似于我们前面讨论过的私语结构，像一群多嘴多舌的邻里，彼此之间悄悄传递着张家长李家短。简言之，私语算法的规则如下：n当一个复制已经被更新，则选择一个或若干个其它复制，向这当一个复制已经被更新，则选择一个或若干个其它复制，向这些复制所在的服务器发送更新数据。些复制所在的服务器发送更新数据。 n这条规则实现起来并不难，但有一个问题需要注意，即在何种情况

45、下停止传染。假定服务器S得到了更新数据x，它便任意选择另一台服务器S，并试图向S推出这个更新数据。然而，很有可能S早就从其它服务器那里得知了这个消息，已经处于感染状态。如果这种情况发生，服务器S便根据某种概率(gil)，如1/k，宣布自己出局，即不再与其它服务器联系。私语算法传播更新的速度相当快，可是却不能保证所有的副本都得到更新。 46第四十六页，共五十四页。私语私语(sy)算法性能算法性能 n从上表可以看出，要想保证把更新传播到所有副本，仅仅依靠私语算法是无法实现的。例如，如果每当遇到已经感染(gnrn)的服务器时就马上停止传播，即k=1，则可能会有20%的服务器得不到更新数据；而当k=3

46、，即遇到已经感染(gnrn)的服务器时，停止传播的可能性为33%，则得不到更新数据的服务器就下降到大约2%。然而，无论怎样增加k值，总有那么一小部份服务器无法进行副本一致化。为了克服这个缺点，人们往往把私语算法和反熵算法合并在一起使用。 k12345s0.2031880.0595200.0198270.0069770.00251647第四十七页，共五十四页。基于基于(jy)主副本的远程写协议主副本的远程写协议 n这是一种中央管理方案，所有的读/写操作都由这台服务器完成。这种方案不存在数据复制，尽管服务器或许(hux)是分布的，但数据仓库却是集中管理的，常见于传统的客户/服务器系统 客户客户主副

47、本服务器读/写服务器读/写读/写48第四十八页，共五十四页。主后备主后备(hubi)协议协议 n读操作(cozu)在局部后备副本进行，而写操作(cozu)必须由主副本管理，并且把更新数据传播到所有的(后备) 服务器。 客户客户服务器服务器服务器主副本后备副本后备副本写读读写更新传播更新传播49第四十九页，共五十四页。主副本主副本(fbn)迁移局部写协议迁移局部写协议 n由于每项数据都隶属于一个主副本，而主副本的地址(尽管可以变动) 为众所周知，故当一个客户进程发出写操作时，系统便将主副本迁移到客户进程所处(su ch)的服务器，然后由该进程执行局部写操作。 客户客户后备副本服务器主副本迁移服务

48、器申请迁移读服务器主副本主副本写更新传播50第五十页，共五十四页。法定人数法定人数(fdngrnsh)协议协议 n假定一个复制系统有N台副本服务器，当客户准备执行写操作时，我们规定该客户至少要与(N/2 + 1) 台服务器(即大多数) 联系，要求这些服务器同意该客户进行更新操作。一旦得到了大多数同意，该客户便实施更新操作，为更新后的副本建立一个新的版本号，并将更新传播到所有服务器。 n另一方面，假定一个客户请求读操作，也必须向同样(tngyng)数量的副本服务器发出信件，要求这些服务器返回各自副本的版本号。如果所有返回的版本号一致，则这个版本必然是最新版本，因为在此时申请的任何写操作都不可能得

49、到大多数的选票。 51第五十一页，共五十四页。法定人数法定人数(fdngrnsh)协议约定协议约定n假定一项数据x被复制在N台服务器中，每台服务器Si都对数据x赋予一个选举(xunj)加权vi(x) 。 n对数据x而言，我们需要引入法定人数概念，并且把读法定人数记作R(x)，写法定人数记为W(x) 。n客户读x, 必须满足： n客户写x, 必须满足：n R(x) 和 W(x) 必须满足右面的限定条件：n(1) (防止读/写冲突)n(2) (防止写/写冲突)NiixvxW.1)()(*2NiixvxWxR.1)()()(（1）（2）52第五十二页，共五十四页。法定人数法定人数(fdngrnsh)

50、协议图例协议图例S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15S16S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15S16S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15S16（1）合法读/写法定人数R(x) = 5 W(x) = 12 （2）可能出现写/写冲突 R(x) = 9 W(x) = 8 （3）ROWA模式R(x) = 1 W(x) = 16 53第五十三页，共五十四页。内容(nirng)总结第八章 复制及复制一致性。屏障是一种以程序阶段为基准的同步机制：在所有进程尚未完成阶段N之前，不允许任何进程开始N+1阶