东北大学分布式操作系统课件6

第6章分布式一致性东北大学信息学院于戈2006年4月主要内容6.1一致性与复制6.2以数据为中心的一致性模型6.3以客户端为中心的一致性模型6.4分布协议6.5一致性协议6.6分布式共享内存（DSM)6.7举例：基于页面的DSM6.8习题6.1一致性与复制复制的理由–提高可靠性：防止单点失败，数据校验–提高性能：并行性，可伸缩性复制的代价–一致性维护–例：Web页的Cache☺Internet☺☺☺对象复制问题（1）单副本对象的同步–例：两个客户并发访问一个分布式远程对象对象复制问题（2）解决方法(a)由远程对象自己处理对它的并发调用(b)由对象适配器处理并发调用对象复制问题（3）多副本对象的同步的解决方法(a)构造感知复制对象，由对象自己保证一致性(b)由分布式系统负责复制管理（由对象所在的服务器负责并发控制）可伸缩性问题将数据的副本放置在进程附近减少访问时间复制策略–设进程P对数据d的访问N次/秒，d的更新M次/秒–当NM时，不应复制可伸缩问题–紧一致性需对所有副本进行全局同步解决策略–松一致性，所有副本不一定保持完全相同，避免立即全局同步6.2以数据为中心的一致性模型分布式数据仓(datastore)模型–物理上分布的和复制的–例如，分布式共享内存、数据库、文件–操作：进程发出的读操作，写操作一致性模型数据相干性（coherency）–数据在各个数据仓中的值保持一致一致性模型–进程与数据仓之间的契约(contract)–如果进程遵守约定的规则，数据仓就能工作正常。–如果进程违反了这些规则，数据仓就不再保证操作的正确性严格一致性规则：对数据项x的读操作返回的值为最近写入x的值特点：绝对全局时间次序（使“最近”没有不确定性）例：严格一致性：101S1S2时间P1:W(x)1P2:R(x)1时间严格一致性不可实现性–没有全局时钟–光速限制：T1:W1(x)→S2,T2:R2(x);T2-T1=10-9例：非严格一致性101S1S20时间P1:W(x)1P2:R(x)0R(x)1时间顺序一致性规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。例：顺序一致性P2P1P4P3P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)2R(x)1时间顺序一致性所有进程看到相同的内存访问操作次序等价于数据库的可串行化（serializability）例：非顺序一致性P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)1R(x)2P2P1P4P3时间例：–3个并行执行的进程–90种正确的执行顺序顺序一致性举例x=1;print((y,z);y=1;print(x,z);z=1;print(x,y);Prints:001011(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:101011(b)y=1;z=1;print(x,y);print(x,z);x=1;print(y,z);Prints:010111(c)y=1;x=1;z=1;print(x,z);print(y,z);print(x,y);Prints:111111(d)P1P2P3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);形式化描述执行(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后的序列–就像在一个集中式数据仓上执行顺序一致性P1:W(x)1P2:W(x)2P3:R(x)2R(x)1P4:R(x)2R(x)1时间合法历程必须满足：–保持程序的操作次序，即必须维持原有的程序顺序–服务数据相干性，即读操作R(x)必须总是返回其执行之前最近执行的写操作W(x)v所写入的值–例：H=W2(x)2,R3(x)2,R4(x)2,W1(x)1,R3(x)1,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+w≥t–对于任何顺序一致性存储，改变协议以提高读操作性能必将降低写操作性能顺序一致性线性一致性（Linearizable）规则：具有顺序一致性，且如果tsop1(x)tsop2(y)，则OP1(x)OP2(y)–每个操作带有全局时钟戳–执行结果是顺序一致性的–每个进程的操作遵照时间戳顺序–注意：可线性化的数据存储是顺序一致性的。它们的区别是：线性化是根据一系列同步时间戳确定序列顺序的。因果一致性因果关系（三种情况）：–1.P1写x，P2读x，则R2(x)与W1(x)具有因果关系–2.P1读x，P2写x，则W2(x)与R1(x)具有因果关系–3.传递性：P1写x，P2读x，然后写y，则W2(y)与W1(x)具有因果关系定义：–对于具有因果关系的写操作，所有进程看到的执行顺序应相同。并发写操作在不同主机上被看到的顺序可以不同。–即所有进程必须以相同的顺序看到具有因果关系的写操作。不同机器上的进程可以以不同的顺序看到并发的写操作因果一致性例：因果一致性例：违反因果一致性P1：W(x)1W(x)3P2：R(x)1W(x)2P3：R(x)1R(x)3R(x)2P4：R(x)1R(x)2R(x)3P1：W(x)1P2：R(x)1W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)2因果一致性例：符合因果一致性（W1(x)与W2(x)是并行操作)实现技术–操作依赖图–时间戳向量P1：W(x)1P2：W(x)2P3：R(x)2R(x)1P4：R(x)1R(x)2FIFO一致性规则：同一个进程的写操作的执行次序，其它进程看到的都相同。不同进程的写操作的执行次序，不同进程看到的可以是不同的例：符合FIFO一致性，但不符合因果一致性P1：W(x)1P2：R(x)1W(x)2W(x)3P3：R(x)2R(x)1R(x)3P4：R(x)1R(x)2R(x)3FIFO一致性例：符合FIFO一致性，但不符合顺序一致性x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);Prints:00(a)x=1;y=1;print(x,z);print(y,z);z=1;print(x,y);Prints:10(b)y=1;print(x,z);z=1;print(x,y);x=1;print(y,z);Prints:01(c)ProcessP1ProcessP2ProcessP3x=1;print(y,z);y=1;print(x,z);z=1;print(x,y);FIFO一致性也称作内存管道一致性(PipelinedRAM)–分布式共享内存系统实现技术：–写操作标签（进程ID,顺序号）处理机一致性规则：与FIFO一致性相似–附加条件：–存储相干性：对于任意存储器地址X,对于写入X的顺序是全局一致的。–写入不同地址,对于不同进程来看,不需要相同顺序同步变量：与一个数据区相关联–Synchronize(S)–同步所有的数据局部拷贝–导出：导入：规则：–对同步变量的访问必须满足顺序一致性。–在所有先前的写操作完成之前,不能访问同步变量–在所有先前的同步操作完成之前,不能访问（读/写）数据。弱一致性写者读者弱一致性例：弱一致性例：非弱一致性P1：W(x)1W(x)2SP2：R(x)1R(x)2SP3：R(x)2R(x)1SP1:W(x)1W(x)2SP2:SR(x)1释放一致性(1)被保护数据：–需要保持一致的共享数据Acquire(L)操作：进入临界区–导入数据：使被保护数据的局部拷贝与远程的最新版本一致Release(L)操作：退出临界区–导出数据：将被保护数据上的变化传播到其它的局部拷贝上释放一致性(2)规则–在访问共享数据前，所有先前的acquire操作都必须完成。–在执行release前，先前的所有读写操作都必须完成。–对同步变量的访问必须满足FIFO一致性例：符合释放一致性P1：Acq(L)W(x)1W(x)2Rel(L)P2：Acq(L)R(x)2Rel(L)P3：R(x)1释放一致性(3)及时释放一致性(EAGERrelease)–当执行了释放操作，执行此操作的处理机将所有修改的数据传给所有那些已经有其缓冲拷贝且可能需要它的处理机滞后释放一致性（LAZYrelease）–在执行释放时，不发送任何数据。–在执行获取操作时，处理机试图从拥有这些变量的机器上取得它们的最新值入口项一致性（1）同步变量–与某个共享数据项相关联•不是与数据区中的所有保护型数据关联–所有者(owner)：最后一个acquire它的进程。•其他进程必须从当前所有者手中取得拥有权。–非互斥方式（non-exclusive）:可以读，但不能写入口项一致性（2）规则：1.在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成；2.在进程P以互斥模式获取同步变量S之前，不允许其他进程同时拥S，即使在非互斥模式下；3.在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非由S的拥有者P进行。入口项一致性（3）例：入口项一致性P1：Acq(Lx)W(x)1Acq(Ly)W(y)2Rel(Lx)P2：P3：Rel(Ly)Acq(Lx)R(x)1R(y)0Acq(Ly)R(y)2优点–减少开销–增加并行性一致性模型总结（1）无同步操作一致性说明严格所有的共享访问事件都有绝对时间次序顺序所有进程都以相同的次序看到所有的共享访问事件，不按时间排序因果所有进程都以相同的次序看到所有因果联系事件FIFO所有进程见到的其他进程的写操作次序就是该进程执行写操作的次序，但来自不同进程的写操作不必以相同的顺序看见一致性模型总结（2）同步操作一致性说明弱当同步操作完成后,共享数据才保持一致释放当退出临界区后，共享数据才保持一致入口项当进入临界区时,和该临界区有关的共享数据才保持一致6.3以客户为中心的一致性模型分布式数据存储区–没有同时更新（无写-写冲突）或容易解决–大多数操作为读操作–例：Web网页（服务器，代理缓存）最终一致性（eventualconsistency）–如果很长时间不发生更新操作，则所有的副本将逐渐变为一致的。最终一致性（1）移动用户问题最终一致性（1）客户为中心的一致性（Client-centric）–保证对一个客户对数据存储的访问是一致的–不考虑不同客户之间的并发访问假设–每个数据项x有一个拥有者，只有拥有者可以修改x–客户的读写操作在本地副本上进行–更新最终将传播给其他副本上。客户为中心的一致性记号–xi[t]:数据项x在局部场地Li上在时刻t的版本–WS(xi[t]):得出xi[t]的写操作集–WS(xi[t1],xj[t2]):WS(xi[t])中的写操作在t2时刻在Lj上执行单调读一致性当一个进程读了数据项x的值后，所有后续的对x的读操作，都将返回相同的值，或者更新的值–例：读email(旧金山--〉纽约）示例：(a)：符合单调读一致性b):不能保证单调读一致性单调写一致性一个进程对数据项x的写操作，必须在该进程对x的所有后续写操作之前完成。–例：软件库更新（版本1,...,n)示例：(a)：符合单调写一致性(b):不能保证单调写一致性读自己写一致性一个进程对数据项x的写操作结果，总能被该进程对x的后续读操作读到。–例1：Web网页更新、浏览–例2：数字图书馆密码更新示例：(a)：符合读自己写一致性(b):不能保证自己写一致性写跟随读一致性一个进程在对数据项x读操作之后对x的写操作