第7章高级操作系统一致性和复制ppt课件.ppt

《第7章高级操作系统一致性和复制ppt课件.ppt》由会员分享，可在线阅读，更多相关《第7章高级操作系统一致性和复制ppt课件.ppt（48页珍藏版）》请在三一办公上搜索。

1、第7章 一致性和复制,2,主要内容,7.1 一致性与复制7.2 以数据为中心的一致性模型7.3 以客户为中心的一致性模型7.4 复制管理7.5 一致性协议,3,7.1 一致性与复制,复制的理由提高可靠性：防止单点失败，数据校验提高性能：并行性，可伸缩性复制的代价一致性维护：更新问题例：Web页的Cache,Internet,4,支持伸缩性的复制技术,将数据的副本放置在处理它们的进程附近以减少访问时间，解决可伸缩性问题复制策略设进程P对数据d的访问N次/秒，d的更新M次/秒当NM时，访问/更新比非常低，由于一致性维护带来更大代价，因此，不应复制,5,支持伸缩性的复制技术,一致性维护与可伸缩性问题

2、保证所有的副本都是相同的，-紧密一致性当某个副本上执行更新操作时，需对所有副本进行全局同步，在大型系统上很难实施-可伸缩性问题解决策略松驰一致性，所有副本不一定保持完全相同，尽量减少立即的全局同步,6,7.2 以数据为中心的一致性模型,分布式数据仓(data store)模型物理上，分布的和复制的例如，分布式共享内存、数据库、文件操作：每个进程可执行读操作，写操作写操作在本地副本上进行，再传播给其他副本,7,一致性模型,数据相干性（coherency）同一个数据在各个数据仓中的值保持一致从单个数据的视角一致性模型多个进程与多个数据之间的操作，保持一致性进程与数据仓之间的契约(contract)

3、如果进程遵守约定的规则，数据仓就能工作正常。如果进程违反了这些规则，数据仓就不再保证操作的正确性,8,持续一致性模型,范围：副本之间的数值偏差：已应用于给定副本但还没有应用于其他副本的更新数目副本之间的新旧程度偏差：与副本最近一次更新有关副本之间的更新操作顺序偏差：副本之间不同的更新顺序,9,持续一致性模型,一致性单元（conit）：受控的数据集举例：conit（x,y）,10,一致性单元的粒度选择,粗粒度：任一个更新操作都导致更新传播虚假共享问题细粒度：当一个数据更新时，另一个数据无需更新,11,顺序一致性,记法规则：Wi(x)a:表示进程Pi把数值a写入数据项xRi(x)b:表示进程Pi从

4、数据项x读取数据后返回数值b,12,顺序一致性,规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。例：顺序一致性,P2,P1,P4,P3,13,顺序一致性,所有进程看到相同的内存访问操作次序等价于数据库的可串行化（serializability）操作粒度：命令 vs.事务例：非顺序一致性,P1:W(x)1P2:W(x)2 P3:R(x)2 R(x)1 P4:R(x)1 R(x)2,P2,P1,P4,P3,时间,14,例：3个并行执行的进程90种正确的执行顺序,顺序一致性举例,15,因果一致性,因果关系(Causality)：P1写x,

5、P2读x，则R2(x)与W1(x)具有潜在的因果关系。P1写x,P2读x,然后写y，则W2(y)与W1(x)具有潜在的因果关系。否则，操作之间的关系为并发(Concurrent)关系例：P1写x,P2写z，则W1(x)与W2(z)不具有潜在因果关系。定义：对于具有潜在因果关系的写操作，所有进程看到的执行顺序应相同。并发写操作在不同主机上被看到的顺序可以不同。,16,因果一致性,例：因果一致性例：违反因果一致性,17,因果一致性,例：符合因果一致性实现技术操作依赖图向量时钟(vector clock),18,同步变量：与一个数据区相关联Synchronize(S)同步所有的数据局部拷贝导出：导入

6、：规则：对同步变量的访问必须满足顺序一致性。在所有先前的写操作完成之前,不能访问同步变量在所有先前的同步操作完成之前,不能访问（读/写）数据。,分组操作,19,入口一致性（1）,同步变量与某个共享数据项相关联不是与数据区中的所有保护型数据关联拥有者(owner)：最后一个获取（acquire）它的进程。其他进程必须从当前所有者手中取得拥有权。非互斥方式（non-exclusive）:可以读，但不能写多个进程可以非互斥方式同时拥有一个同步变量,20,入口一致性（2）,规则：在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成；在进程P以互斥模式访问同步变量S之前，不允许其

7、他进程同时拥有S，即使在非互斥模式下；在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非在S的拥有者P执行之后。,21,入口一致性（3）,例：入口项一致性,P1：Acq(Lx)W(x)1 Acq(Ly)W(y)2 Rel(Lx)P2：P3：,Rel(Ly)Acq(Lx)R(x)1 R(y)0 Acq(Ly)R(y)2,优点减少开销增加并行性,22,7.3 以客户为中心的一致性模型,分布式数据存储区没有同时更新（无写-写冲突）或容易解决大多数操作为读操作例：Web网页（服务器，代理缓存）最终一致性（eventual consistency）如果很长时间不发生更新操

8、作，则所有的副本将逐渐变为一致的。,23,最终一致性（1）,移动用户问题,24,最终一致性（1）,客户为中心的一致性（Client-centric）保证对一个客户对数据存储的访问是一致的不考虑不同客户之间的并发访问假设每个数据项x有一个拥有者，只有拥有者可以修改x客户的读写操作在本地副本上进行更新最终将传播给其他副本上。,25,客户为中心的一致性,记号xit:数据项x在局部场地Li上，在时刻t的版本WS(xit):产生xit的所有写操作的集合WS(xit1,xjt2):WS(xit)中的写操作在t2时刻在Lj上执行,Xj,Xi,X,WS(xi),WS(xi,xj),26,单调读一致性,当一个客

9、户读了数据项x的值后，所有后续的对x的读操作，都将返回相同的值，或者更新的值例：读email旧金山-纽约）示例：,(a)：符合单调读一致性,b):不能保证单调读一致性,27,单调写一致性,一个客户对数据项x的写操作，必须在该客户对x的所有后续写操作之前完成。例：软件库更新（版本1,.,n)示例：,(a)：符合单调写一致性,(b):不能保证单调写一致性,28,读自己写一致性,一个客户对数据项x的写操作结果，总能被该客户对x的后续读操作读到。例1：Web网页更新、浏览例2：数字图书馆密码更新示例：,(a)：符合读自己写一致性,(b):不能保证自己写一致性,29,写跟随读一致性,一个客户在对数据项x

10、读操作之后对x的写操作，必须在x已读出的相同值或者更近的值之上进行例：BBS跟帖（读文章A,写文章B）示例：,(a)：符合写跟随读一致性,(b):不能保证写跟随读一致性,30,7.4 复制管理,副本服务器的放置问题从N个位置中选出K个最优位置基于距离的方法最优：所有客户与所有位置的距离最短距离：延时、带宽等指标,31,副本服务器的放置策略,基于单元的方法将m维空间划分成多个相同大小的单元选择K个密度最大的单元放置副本服务器计算复杂度：O(N*maxlog(N),K)选择适当的单元大小太大：节点太多，而副本服务器太少；太小：导致副本服务器太多,(太大),(太小),正好,32,内容复制与放置,分布

11、式数据仓的设计复制副本的类型：永久型、服务器发起型、客户发起型,33,永久型副本,构成分布式数据仓的初始集合静态的、固定的副本数量较少例1：Web场地的分布类型局域网：轮回策略型服务器Internet：镜像服务器例2：分布式数据库工作站集群（COW）联邦数据库,34,服务器发起型副本（1）,推送式缓存（push cache）由服务器，动态地设置新的副本作用：当负载发生变化时，如突然增加。减少服务器负担减少客户的通信开销问题？在何时、何地发起复制,35,服务器发起型副本（2）,实现方法访问计数：cnt(S,F)，S为服务器，F为文件复制阈值：rep(S,F)删除阈值：del(S,F)距离：dis

12、t(S,C),C为客户。该信息来自路由数据库,36,服务器发起型副本（3）,复制副本复制副本条件：cnt(S,F)rep(S,F)删除副本删除副本条件：cnt(S,F)del(S,F)迁移副本迁移副本条件：del(S,F)cnt(S,F)rep(S,F),37,服务器发起型副本（4）,举例：计数来自不同客户的请求，将文件复制到离客户附近的服务器上。如果cntQ(P,F)cnt(Q,F)/2，将F从Q迁移到P,38,客户端发起型副本,客户缓存(cache)客户端的本地存储缓存命中率(cache hit)：请求的数据可在缓存中取出的概率提高命中率：缓存可由多个客户共享客户缓存的设置场地与客户相同的

13、机器局域网上多个客户共享的机器上广域网上的代理服务器上,客户端,服务器,代理服务器,39,内容分发,当客户执行一个更新操作后，该操作将传播到所有副本传播状态与传播操作策略传播更新通告传输数据拷贝传播更新操作,40,更新传播,通告无效协议（invalidation）只传输被修改的数据的位置信息数据量少，占用很少网络带宽适用于读/写比非常低的情况数据传输(data shipping)传输被修改的数据数据量多，占用较多网络带宽适用于读/写比非常高的情况,41,更新传播,操作传输(operation shipping)主动复制技术-每个副本有一个进程主动地进行更新占用最少网络带宽要求有较高处理能力,4

14、2,推送式与拉取式协议,推送式(push)协议：基于服务器的协议不需要请求，就将更新传播给副本可保持高度的一致性，通常用于永久性副本和服务器副本之间优点：适用于读/写比非常高的情况拉取式(pull)协议：基于客户的协议由客户请求服务器发送更新优点：适用于读/写比非常低的情况缺点：当cache miss时，响应时间长,43,7.5 一致性协议,一致性协议：对一致性模型的实现方法的描述基于主副本的协议主副本：在数据的所有复制副本中，写操作必须先在主副本上进行。实现了顺序一致性远程写协议：所有写操作由远程服务器执行本地写协议：将主副本读到执行写操作的本地上执行,44,远程写协议,带有备份的主副本服务器,45,本地写协议,带有备份的主副本服务器,46,复制式写协议(1),写操作可在多个副本上执行主动复制协议将各更新操作发给各个副本上的进程问题：更新顺序问题解决方案：全序多播机制：如Lamport时间戳向量顺序管理器（sequencer）：集中式协调器，负责为每个操作赋予唯一的顺序号，转发给各个副本。,47,基于合法数的协议（1）,基于多数表决的复制写协议与主副本协议的区别：多个副本同时执行写操作基本算法：设有N各副本设置读合法数NR，写合法数Nw要求：NR+Nw N；Nw N/2,48,基于合法数的协议（2）,举例：,ROWA协议,不正确写合法数,正确读写合法数,