《[计算机软件及应用]dos-ch6-consistency》由会员分享，可在线阅读，更多相关《[计算机软件及应用]dos-ch6-consistency（102页珍藏版）》请在金锄头文库上搜索。
1、第6章 分布式一致性,东北大学信息学院 于 戈 2006年4月,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,2,主要内容,6.1 一致性与复制 6.2 以数据为中心的一致性模型 6.3 以客户端为中心的一致性模型 6.4 分布协议 6.5 一致性协议 6.6 *分布式共享内存（DSM) 6.7 *举例：基于页面的DSM 6.8 习题,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,3,6.1 一致性与复制,复制的理由 提高可靠性：防止单点失败，数据校验 提高性能：并行性，可伸缩性 复制的代价 一致性维护 例：Web页的Cache,Internet,2006-
2、4-11 东北大学软件所 于戈,第六章 分布式一致性,4,对象复制问题（1）,单副本对象的同步 例：两个客户并发访问一个分布式远程对象,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,5,对象复制问题（2）,解决方法 (a) 由远程对象自己处理对它的并发调用 (b) 由对象适配器处理并发调用,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,6,对象复制问题（3）,多副本对象的同步 (a) 构造感知复制对象，由对象自己保证一致性 (b) 由分布式系统负责复制管理,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,7,可伸缩性问题,将数据的副本放置在进
3、程附近减少访问时间 复制策略 设进程P对数据d的访问N次/秒，d的更新M次/秒 当NM时，不应复制 可伸缩问题 紧一致性需对所有副本进行全局同步 解决策略 松一致性，所有副本不一定保持完全相同，避免立即全局同步,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,8,6.2 以数据为中心的一致性模型,分布式数据仓(data store)模型 物理上分布的和复制的 例如，分布式共享内存、数据库、文件 操作：进程发出的读操作，写操作,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,9,一致性模型,数据相干性（coherency） 数据在各个数据仓中的值保持一致 一致性模
4、型 进程与数据仓之间的契约(contract) 如果进程遵守约定的规则，数据仓就能工作正常。 如果进程违反了这些规则，数据仓就不再保证操作的正确性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,10,严格一致性,规则：对数据项x的读操作返回的值为最近写入x的值 特点：绝对全局时间次序 例：严格一致性：,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,11,严格一致性,不可实现性 没有全局时钟 光速限制：T1:W1(x)S2, T2:R2(x); T2-T1=10-9 例：非严格一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,12,顺序一
5、致性,规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。 例：顺序一致性,P2,P1,P4,P3,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,13,顺序一致性,所有进程看到相同的内存访问操作次序 等价于数据库的可串行化（serializability） 例：非顺序一致性,P1: W(x)1 P2: W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2,P2,P1,P4,P3,时间,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,14,例： 3个并行执行的进程 90种正确的执行顺
6、序,顺序一致性举例,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,15,形式化描述 执行(Execution)：进程Pi在数据仓S上的读写操作序列，记为Ei 例：E1 = W1(x)1; E2 = W2(x)2; E3 = R3(x)2,R3(x)1 E4 = R4(x)2,R4(x)1 历程(History):合并E1,E2,En后的序列 就像在一个集中式数据仓上执行,顺序一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,16,合法历程： 保持程序的操作次序 符合数据相干性 例：H= W2(x)2,R3(x)2,R4(x)2,W1(x)1,R3(x)1
7、,R4(x)1 非法历程 例： H= W2(x)2,R3(x)2, R4(x)1,R4(x)2, W1(x)1,R3(x)1 性能问题： 设读操作时间为r,写操作时间为w, 包传输时间为t 则r+wt,顺序一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,17,线性一致性（Linearizable）,规则：具有顺序一致性，且如果tsop1(x) tsop2(y)，则OP1(x) OP2(y) 每个操作带有全局时钟戳 执行结果是顺序一致性的 每个进程的操作遵照时间戳顺序,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,18,因果一致性,因果关系(Causal
8、ity)： P1写x,P2读x，则R2(x)与W1(x)具有因果关系。 P1读x,P2写x，则W2(x)与R1(x)具有因果关系。 传递性：例，P1写x,P2读x,然后写y，则W2(y)与W1(x)具有因果关系。 否则，为并发关系 定义： 对于具有因果关系的写操作，所有进程看到的执行顺序应相同。 并发写操作在不同主机上被看到的顺序可以不同。,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,19,因果一致性,例：因果一致性 例：违反因果一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,20,因果一致性,例：符合因果一致性 实现技术 操作依赖图 时间戳向量,2
9、006-4-11 东北大学软件所 于戈,第六章 分布式一致性,21,FIFO一致性,规则：同一个进程的写操作的执行次序，其它进程看到的都相同。不同进程的写操作的执行次序，不同进程看到的可以是不同的 例：符合FIFO一致性，但不符合因果一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,22,FIFO一致性,例：符合FIFO一致性，但不符合顺序一致性,P1 P2 P3,P1 P2 P3,P2 P3 P1,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,23,FIFO一致性,也称作内存管道一致性(Pipelined RAM) 分布式共享内存系统 实现技术： 写操
10、作标签（进程ID,顺序号）,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,24,处理机一致性,规则：与FIFO一致性相似 附加条件： 存储相干性：对于任意存储器地址X, 对于写入X的顺序是全局一致的。 写入不同地址,对于不同进程来看,不需要相同顺序,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,25,同步变量：与一个数据区相关联 Synchronize(S) 同步所有的数据局部拷贝 导出： 导入： 规则： 对同步变量的访问必须满足顺序一致性。 在所有先前的写操作完成之前,不能访问同步变量 在所有先前的同步操作完成之前,不能访问（读/写）数据。,弱一致性,20
11、06-4-11 东北大学软件所 于戈,第六章 分布式一致性,26,弱一致性,例：弱一致性 例：非弱一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,27,释放一致性(1),被保护数据： 需要保持一致的共享数据 Acquire(L)操作：进入临界区 导入数据：使被保护数据的局部拷贝与远程的最新版本一致 Release(L)操作：退出临界区 导出数据：将被保护数据上的变化传播到其它的局部拷贝上,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,28,释放一致性(2),规则 在访问共享数据前，所有先前的acquire操作都必须完成。 在执行release前，先前的
12、所有读写操作都必须完成。 对同步变量的访问必须满足FIFO一致性 例：符合释放一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,29,释放一致性(3),及时释放一致性(EAGER release) 当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机 滞后释放一致性（LAZY release ） 在执行释放时，不发送任何数据。 在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,30,入口项一致性（1）,同步变量 与某个共享数据项相关联 不是与数
13、据区中的所有保护型数据关联 拥有者(owner)：最后一个获取（acquire）它的进程。 其他进程必须从当前所有者手中取得拥有权。 非互斥方式（non-exclusive）:可以读，但不能写 多个进程可以非互斥方式同时拥有一个同步变量,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,31,入口项一致性（2）,规则： 在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成； 在进程P以互斥模式访问同步变量S之前，不允许其他进程同时拥有S，即使在非互斥模式下； 在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非在S的拥有者P执
14、行之后。,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,32,入口项一致性（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,优点 减少开销 增加并行性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,33,一致性模型总结（1）,无同步操作,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,34,一致性模型总结（2）,同步操作,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,35,
15、6.3 以客户为中心的一致性模型,分布式数据存储区 没有同时更新（无写-写冲突）或容易解决 大多数操作为读操作 例：Web网页（服务器，代理缓存） 最终一致性（eventual consistency） 如果很长时间不发生更新操作，则所有的副本将逐渐变为一致的。,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,36,最终一致性（1）,移动用户问题,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,37,最终一致性（1）,客户为中心的一致性（Client-centric） 保证对一个客户对数据存储的访问是一致的 不考虑不同客户之间的并发访问 假设 每个数据项x有一个
16、拥有者，只有拥有者可以修改x 客户的读写操作在本地副本上进行 更新最终将传播给其他副本上。,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,38,客户为中心的一致性,记号 xit: 数据项x在局部场地Li上在时刻t的版本 WS(xit): 得出xit的写操作集 WS(xit1, xjt2): WS(xit)中的写操作在t2时刻在Lj上执行,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,39,单调读一致性,当一个进程读了数据项x的值后，所有后续的对x的读操作，都将返回相同的值，或者更新的值 例：读email(旧金山-纽约） 示例：,(a)：符合单调读一致性,b): 不能保证单调读一致性,2006-4-11 东北大学软件所 于戈,第六章 分布式一致性,40,单调写一致性,一个进程对数据项x的写操
