高级操作系统课件-第七章一致性和复制

1、第七章第七章 一致性和复制一致性和复制 概述概述 以数据为中心的一致性模型以数据为中心的一致性模型 以客户为中心的一致性模型以客户为中心的一致性模型 复制管理复制管理 一致性协议一致性协议 可靠性可靠性 性能性能 服务器数量扩展服务器数量扩展 地理区域扩展地理区域扩展 代价：一致性代价：一致性 网络通信开销网络通信开销 强一致性要求的原子操作很难快速完成强一致性要求的原子操作很难快速完成 解决办法：解决办法： 放宽一致性方面的限制，放宽程度取决于复制数据的放宽一致性方面的限制，放宽程度取决于复制数据的访问和更新模式以及数据的用途访问和更新模式以及数据的用途以数据为中心的一致性模型以数据为中心的

2、一致性模型逻辑数据存储的一般组织，物理上是分布的，并被复制到各个进程逻辑数据存储的一般组织，物理上是分布的，并被复制到各个进程讨论讨论共享数据共享数据读操作和写操作时的一致性问题读操作和写操作时的一致性问题一致性模型实质上是进程和数据存储间的约定：如果进程同意遵守某些规则，数一致性模型实质上是进程和数据存储间的约定：如果进程同意遵守某些规则，数据存储将正常进行。正常情况下，进程的读操作应该返回最后一次写操作的结果据存储将正常进行。正常情况下，进程的读操作应该返回最后一次写操作的结果没有全局时钟，精确定义哪次写操作是最后一次写操作是困难的没有全局时钟，精确定义哪次写操作是最后一次写操作是困难的作

3、为全局时钟的替代，产生了一系列一致性模型，每种模型都有效地限制了一个作为全局时钟的替代，产生了一系列一致性模型，每种模型都有效地限制了一个数据项上执行一次读操作所应返回的值数据项上执行一次读操作所应返回的值严格一致性严格一致性（Strict Consistency）a) 严格的一致性存储严格的一致性存储b) 非严格的一致性存储非严格的一致性存储任何对数据项任何对数据项X的读操作将返回最近一次对的读操作将返回最近一次对X进行写操作的值进行写操作的值对所有进程来说，所有写操作都是瞬间可见的，系统维护着一对所有进程来说，所有写操作都是瞬间可见的，系统维护着一个绝对的全局时间顺序个绝对的全局时间顺序a

4、) 顺序一致的数据存储顺序一致的数据存储b) 非顺序一致的数据存储非顺序一致的数据存储顺序一致性对存储器的限制比严格一致性要弱一些，要满足以下的条件：顺序一致性对存储器的限制比严格一致性要弱一些，要满足以下的条件： （1） 每个进程的内部操作顺序是确定不变的；每个进程的内部操作顺序是确定不变的； （2） 假如所有的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确假如所有的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确定的，即任一进程都可以感知到这些进程同样的操作顺序。定的，即任一进程都可以感知到这些进程同样的操作顺序。 顺序一致性可与事务串行化相比顺序一致性可与事务串行化相比

5、串行化串行化：如果一个并发执行的事务处理集合的结果可：如果一个并发执行的事务处理集合的结果可以按照某种顺序逐个执行事务获得，该事务处理集合以按照某种顺序逐个执行事务获得，该事务处理集合是可串行化的是可串行化的区别：粒度的不同区别：粒度的不同 顺序一致性：读写操作顺序一致性：读写操作 串行化：事务（一系列读写操作的集合）串行化：事务（一系列读写操作的集合）线性化线性化： 弱于严格一致性而强于顺序一致性弱于严格一致性而强于顺序一致性 根据一系列时钟同步确定序列顺序（利用时间戳）根据一系列时钟同步确定序列顺序（利用时间戳）顺序一致性和线性化提供了程序开发人员在并发程序顺序一致性和线性化提供了程序开发

6、人员在并发程序设计中期望的语义：设计中期望的语义：所有写操作都以相同的顺序被每所有写操作都以相同的顺序被每个进程看到个进程看到因果一致性因果一致性Casual Consistency (1) 所有进程必须以相同的顺序看到具有所有进程必须以相同的顺序看到具有潜在因果关系潜在因果关系的写操作的写操作 不同机器上的进程可以以不同的顺序看到并发的写不同机器上的进程可以以不同的顺序看到并发的写操作操作因果一致性因果一致性 (2)因果一致性存储允许的，但顺序和严格一致性存储不允许的顺序因果一致性存储允许的，但顺序和严格一致性存储不允许的顺序a)违背因果一致性的时间存储顺序违背因果一致性的时间存储顺序b)符

7、合因果一致性的时间存储顺序符合因果一致性的时间存储顺序FIFO 一致性一致性FIFO Consistency (1) FIFO一致性模型是在因果一致性模型上的进一一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：步弱化，它满足下面的条件： 由由某一个进程完成的写操作某一个进程完成的写操作可以被其他所有的进程可以被其他所有的进程按照顺序感知到，而从不同进程中来的写操作对不按照顺序感知到，而从不同进程中来的写操作对不同的进程可以有不同的顺序。同的进程可以有不同的顺序。 FIFO 一致性一致性 (2)符合符合FIFO 一致性的时间存储顺序一致性的时间存储顺序与顺序一致性的区别与顺序一致性

8、的区别:顺序一致性：尽管语句的执行顺序是非确定的，顺序一致性：尽管语句的执行顺序是非确定的，但所有的进程对顺序达成一致但所有的进程对顺序达成一致FIFO 一致性：各个进程不需要达成一致，不同一致性：各个进程不需要达成一致，不同进程可以以不同的顺序看到进程可以以不同的顺序看到引入同步的一致性引入同步的一致性 引入显示的同步变量引入显示的同步变量 当一个进程对数据进行操作时，不保证其他进程当一个进程对数据进行操作时，不保证其他进程何时看到这一操作，只是在执行一次同步时，数何时看到这一操作，只是在执行一次同步时，数据的改变才被传播据的改变才被传播 弱一致性弱一致性 释放一致性释放一致性 入口一致性入

9、口一致性 同步变量同步变量S仅有一个关联操作仅有一个关联操作synchronization(S),该操作同步数据存储的所有本地拷贝该操作同步数据存储的所有本地拷贝 弱一致性模型必须满足的条件有下面几点弱一致性模型必须满足的条件有下面几点: 对同步变量的访问满足一致性的要求对同步变量的访问满足一致性的要求 说明所有进程都以相同的顺序看到同步变量进行的所说明所有进程都以相同的顺序看到同步变量进行的所有操作有操作 对同步变量的访问，只有在以前的写操作在各处都完成对同步变量的访问，只有在以前的写操作在各处都完成之后才能进行。之后才能进行。 强迫在所有备份上完成所有的写操作强迫在所有备份上完成所有的写操

10、作 对数据的操作（读或写），只有在以前的对同步变量的对数据的操作（读或写），只有在以前的对同步变量的操作完成之后才能进行。操作完成之后才能进行。 保证所得到的数值是最新值保证所得到的数值是最新值a)对弱一致性有效的时间顺序对弱一致性有效的时间顺序b)对弱一致性无效的时间顺序对弱一致性无效的时间顺序释放一致性释放一致性Release Consistency (1)对释放一致性有效的时间顺序对释放一致性有效的时间顺序释放一致性使用两种类型的同步变量来代替原来的一种同步释放一致性使用两种类型的同步变量来代替原来的一种同步变量变量获取获取Acquire操作用于表明进程进入临界区操作用于表明进程进入临界

11、区释放释放Release操作用于表明进程退出临界区操作用于表明进程退出临界区释放一致性释放一致性 (2) 通常，如果一个分布式共享存储系统满足释放一致通常，如果一个分布式共享存储系统满足释放一致性，则它必须遵守以下的规则：性，则它必须遵守以下的规则： 某进程只有在成功完成某进程只有在成功完成Acquire操作之后，才能对共享数据进操作之后，才能对共享数据进行读写操作。行读写操作。 某进程只有在完成对共享数据的读写操作之后，某进程只有在完成对共享数据的读写操作之后，Release操作操作才能完成。才能完成。 Acquire和和Release操作必须满足操作必须满足FIFO一致性要求。一致性要求。

12、 进程执行获取操作时要保证数据更新，与远程数据保持一致，进程执行获取操作时要保证数据更新，与远程数据保持一致，但不保证本地数据改变被立即传播到其他拷贝但不保证本地数据改变被立即传播到其他拷贝 进程执行释放操作时已改变的数据被立即传播到其他拷贝，进程执行释放操作时已改变的数据被立即传播到其他拷贝，不保证一定从其他拷贝引入改变不保证一定从其他拷贝引入改变要求每个普通的共享数据都要与某种同步变量（如锁）关联要求每个普通的共享数据都要与某种同步变量（如锁）关联思想：使得多个包含不同共享数据的临界区可以同时执行，从而思想：使得多个包含不同共享数据的临界区可以同时执行，从而增加系统的并行度，付出的代价是每

13、个共享数据与某种同步变量增加系统的并行度，付出的代价是每个共享数据与某种同步变量关联的额外开销和复杂性关联的额外开销和复杂性满足入口一致性的条件是：满足入口一致性的条件是： 在一个进程可以获取一个同步变量前，所有由该同步变量保在一个进程可以获取一个同步变量前，所有由该同步变量保护的共享数据相对与该进程已经护的共享数据相对与该进程已经更新更新完毕完毕 在一个进程被允许以在一个进程被允许以独占独占模式访问某同步变量之前，任何别模式访问某同步变量之前，任何别的进程不可以拥有该同步变量，即使以非独占模式拥有。的进程不可以拥有该同步变量，即使以非独占模式拥有。 在一个进程以独占模式访问一个同步变量之后，

14、在对该同步在一个进程以独占模式访问一个同步变量之后，在对该同步变量的所有者变量的所有者检查检查之前，任何其他进程都不能执行下一个非之前，任何其他进程都不能执行下一个非独占访问。独占访问。对入口一致性有效的时间顺序对入口一致性有效的时间顺序一致性总结一致性总结a)不使用同步操作的一致性模型不使用同步操作的一致性模型b)使用同步操作的一致性模型使用同步操作的一致性模型ConsistencyDescription严格严格所有共享访问按绝对时间排序所有共享访问按绝对时间排序线性化线性化所有进程以相同顺序看到所有的共享访问。而且，访问是根据全局时间戳排序的所有进程以相同顺序看到所有的共享访问。而且，访问

15、是根据全局时间戳排序的顺序顺序所有进程以相同顺序看到所有的共享访问。访问不是根据时间排序的所有进程以相同顺序看到所有的共享访问。访问不是根据时间排序的因果因果所有进程以相同顺序看到因果相关的共享访问。所有进程以相同顺序看到因果相关的共享访问。FIFO所有进程以不同进程提出写操作的顺序相互看到写操作。来自不同进程的写操作可以不所有进程以不同进程提出写操作的顺序相互看到写操作。来自不同进程的写操作可以不必总是以相同的顺序出现。必总是以相同的顺序出现。(a)ConsistencyDescription弱弱只有在执行一次同步后，共享数据才被认为是一致的只有在执行一次同步后，共享数据才被认为是一致的释放

16、释放退出临界区时，使共享数据成为一致的退出临界区时，使共享数据成为一致的入口入口进入临界区时，使属于一个临界区的共享数据成为一致的进入临界区时，使属于一个临界区的共享数据成为一致的(b) 最终一致性最终一致性：很多情况下系统能容忍相对较高程度的：很多情况下系统能容忍相对较高程度的不一致性，共同之处在于：只有一个或少数几个进程不一致性，共同之处在于：只有一个或少数几个进程执行更新操作，如果较长时间内没有更新操作，那么执行更新操作，如果较长时间内没有更新操作，那么副本将逐渐成为一致的副本将逐渐成为一致的 数据库系统数据库系统 DNS WWW 特点：特点： 只有少数几个进程执行更新操作，只需要处理读

17、写冲突只有少数几个进程执行更新操作，只需要处理读写冲突 能容忍相对较高程度的不一致性能容忍相对较高程度的不一致性 实现开销小实现开销小 如果客户总是访问同一副本，最终一致性能工作得很如果客户总是访问同一副本，最终一致性能工作得很好好移动用户访问分布式数据库不同副本的原理移动用户访问分布式数据库不同副本的原理如果一个进程读取数据项如果一个进程读取数据项x的值，那么该进程对的值，那么该进程对x执行的任何后续读操作执行的任何后续读操作将总是得到第一次读取的那个值或更新的值将总是得到第一次读取的那个值或更新的值进程进程 P 对同一数据存储的两个不同本地备份执行的读操作对同一数据存储的两个不同本地备份执

18、行的读操作a)提供单调读一致性的数据存储提供单调读一致性的数据存储b)不提供单调读一致性的数据存储不提供单调读一致性的数据存储.WS(x1;x2)表示表示WS(x1)的操作已的操作已在在L2更新完毕更新完毕 一个进程对数据项一个进程对数据项x执行的写操作必须在该进程对执行的写操作必须在该进程对x执行的任何后续写操作之前执行的任何后续写操作之前完成完成 进程进程 P 对同一数据存储的两个不同本地备份执行的写操作对同一数据存储的两个不同本地备份执行的写操作提供单调写一致性的数据存储提供单调写一致性的数据存储不提供单调写一致性的数据存储不提供单调写一致性的数据存储 类似以数据为中心的类似以数据为中心

19、的FIFO一致性一致性一个进程对数据项一个进程对数据项x执行的写操作结果总会被该进程对执行的写操作结果总会被该进程对x执行的任何后续读执行的任何后续读操作看见操作看见提供写后读一致性的数据存储提供写后读一致性的数据存储不提供写后读一致性的数据存储不提供写后读一致性的数据存储同一个进程对数据项同一个进程对数据项x执行的读操作之后的写操作，保证发生在执行的读操作之后的写操作，保证发生在与与x读取之相同或更新的值上读取之相同或更新的值上提供读后写一致性的数据存储提供读后写一致性的数据存储不提供读后写一致性的数据存储不提供读后写一致性的数据存储数据存储的不同类型备份数据存储的不同类型备份分发协议分发协

20、议:将数据更新发送给各个副本的方法将数据更新发送给各个副本的方法副本放置副本放置：位置、时间和由谁来放置：位置、时间和由谁来放置永久副本：副本的初始集合，数量很少，用作允许被修改以保证一致性的永久副本：副本的初始集合，数量很少，用作允许被修改以保证一致性的唯一副本唯一副本服务器启动的副本服务器启动的副本:用于在客户附近放置只读备份，从而提高性能用于在客户附近放置只读备份，从而提高性能客户启动的副本：客户高速缓存，改善数据的访问时间；对只读客户启动的副本：客户高速缓存，改善数据的访问时间；对只读数据高效；可以让多个客户共享缓存；效率取决于数据类型数据高效；可以让多个客户共享缓存；效率取决于数据类

21、型来自不同客户的访问请求计数来自不同客户的访问请求计数更新传播更新传播更新传播更新传播：更新从一个拷贝传播到其他拷贝更新从一个拷贝传播到其他拷贝相关设计问题：相关设计问题：状态与操作状态与操作拉协议与推协议拉协议与推协议单播与多播单播与多播实际传播的信息实际传播的信息 只传播只传播更新的通知更新的通知：无效化协议：无效化协议 可以指定数据存储的哪些部分被更新了可以指定数据存储的哪些部分被更新了 请求在无效的拷贝上操作时，先更新该拷贝请求在无效的拷贝上操作时，先更新该拷贝 几乎不占带宽，适合更新操作比读写操作多的场合（两次更新间可能几乎不占带宽，适合更新操作比读写操作多的场合（两次更新间可能没有

22、读操作）没有读操作） 把把数据数据从一个拷贝传送到另一个拷贝从一个拷贝传送到另一个拷贝 适合读对写的比率相对高的场合：被修改的数据可能在下一个更新前适合读对写的比率相对高的场合：被修改的数据可能在下一个更新前被读取，即更新是有效的可能性较高被读取，即更新是有效的可能性较高 可以只传送修改的日志可以只传送修改的日志 通过将多个修改压缩到一个消息里来减少通信开销通过将多个修改压缩到一个消息里来减少通信开销 把把更新操作更新操作传送到其他拷贝：主动复制传送到其他拷贝：主动复制 假设每个副本由一个进程代表，该进程通过执行操作主动地更新数据：假设每个副本由一个进程代表，该进程通过执行操作主动地更新数据：

23、假设操作关联的参数少，传播更新的带宽代价小假设操作关联的参数少，传播更新的带宽代价小在多客户、单一服务器系统中，基于推式协议与基于拉式协议比较在多客户、单一服务器系统中，基于推式协议与基于拉式协议比较问题问题基于推式基于推式基于拉式基于拉式服务器的状态服务器的状态客户副本和高速缓存的列表客户副本和高速缓存的列表无无发送的消息发送的消息更新（以及以后可能获取的更新）更新（以及以后可能获取的更新）轮询和更新轮询和更新客户响应时间客户响应时间立即（或获取更新的时间）立即（或获取更新的时间）获取更新的时间获取更新的时间基于推式协议：基于服务器的协议基于推式协议：基于服务器的协议 永久副本和服务器启动的

24、副本更新永久副本和服务器启动的副本更新 用于副本需要完全相同的时候用于副本需要完全相同的时候 适合读对写的比率相对高的场合（更新对读操作有效），高效适合读对写的比率相对高的场合（更新对读操作有效），高效基于拉式协议：基于客户的协议基于拉式协议：基于客户的协议 一台服务器或客户请求其他服务器向它发送持有的更新一台服务器或客户请求其他服务器向它发送持有的更新 用于客户高速缓存：用于客户高速缓存：Web高速缓存，客户轮询服务器高速缓存，客户轮询服务器基于租用的更新传播基于租用的更新传播 更新传播的混合形式更新传播的混合形式 租用是服务器的承诺，它将在指定的时间内将更新推给客户。租用是服务器的承诺，它

25、将在指定的时间内将更新推给客户。 租用到期后：租用到期后： 客户被迫轮询服务器以实现更新客户被迫轮询服务器以实现更新 客户请求一个新的租期客户请求一个新的租期 三种类型的租用三种类型的租用 根据数据项的年龄：为预期保持不变的数据授予一个长期根据数据项的年龄：为预期保持不变的数据授予一个长期的租用，可以减少更新消息的数量的租用，可以减少更新消息的数量 根据客户请求高速缓存副本的频率：频率高的客户授予长根据客户请求高速缓存副本的频率：频率高的客户授予长期的租用，只跟踪对数据感兴趣的客户期的租用，只跟踪对数据感兴趣的客户 基于服务器的状态空间开销：将要过载时，缩短新租用的基于服务器的状态空间开销：将

26、要过载时，缩短新租用的期限期限单播与多播单播与多播 多播：服务器向其他多播：服务器向其他N台服务器发送更新时，底层台服务器发送更新时，底层的网络负责向多个接收者发送一个消息，高效的网络负责向多个接收者发送一个消息，高效 与推式更新结合更高效与推式更新结合更高效 单播：服务器向其他单播：服务器向其他N台服务器发送更新时，要发台服务器发送更新时，要发送送N个单独的消息个单独的消息 与拉式更新结合更高效：只有一个客户请求更新与拉式更新结合更高效：只有一个客户请求更新Epidemic协议协议 提供提供最终一致性最终一致性：保证所有的副本最终是一致的：保证所有的副本最终是一致的不解决更新冲突，只关心使用

27、最少的消息将更新传播到所有副本不解决更新冲突，只关心使用最少的消息将更新传播到所有副本一个服务器可以是：一个服务器可以是： 传染性的：持有愿意向其他服务器散布的更新传染性的：持有愿意向其他服务器散布的更新 易感的：尚未更新的服务器易感的：尚未更新的服务器 隔离的：已更新的服务器如果不愿意或不能扩散其更新隔离的：已更新的服务器如果不愿意或不能扩散其更新反熵反熵传播模型：服务器传播模型：服务器P周期的随机选取一台服务器周期的随机选取一台服务器Q交换更新，方式包括：交换更新，方式包括： P只把自己的更新推入只把自己的更新推入Q：较差的选择：较差的选择 P只从只从Q拉出新的更新拉出新的更新 P和和Q相

28、互发送更新相互发送更新 可以证明：如果初始只有一台服务器具有传染性，无论采用哪种形式，可以证明：如果初始只有一台服务器具有传染性，无论采用哪种形式，更新最终将被传播到所有服务器上更新最终将被传播到所有服务器上 思想：思想： 如果服务器如果服务器P刚刚因为数据项刚刚因为数据项x而被更新，那么它联系任而被更新，那么它联系任意一个其他服务器意一个其他服务器Q，并试图将更新推入，并试图将更新推入Q。 如果如果Q已经被其他服务器更新了，已经被其他服务器更新了， P可能会失去继续扩散可能会失去继续扩散的兴趣，变成隔离的（这种可能性是的兴趣，变成隔离的（这种可能性是1/k） 快速传播更新的方法快速传播更新的

29、方法 但不能保证所有的服务器都被更新了但不能保证所有的服务器都被更新了 s=e-(k+1)(1-s) ,k=3时，时，s小于小于2% 可以将可以将gossiping和反熵结合和反熵结合一致性协议一致性协议 一致性协议描述特定的一致性模型的实现一致性协议描述特定的一致性模型的实现 基于主备份的协议基于主备份的协议：每个数据：每个数据x都有一个关联的主备都有一个关联的主备份，负责协调份，负责协调x的写操作，根据主备份的位置分为：的写操作，根据主备份的位置分为： 远程写协议远程写协议 本地写协议本地写协议 复制的写协议复制的写协议：写操作可以在多个副本上执行：写操作可以在多个副本上执行 主动复制主动复制 基于法定数目的协议基于法定数目的协议 基于主备份的远程写协议，所有读操作和写操作都被转发到基于主备份的远程写协议，所有读操作和写操作都被转发到一个固定的服务器