高级操作系统一致性和复制精要.ppt

第7章 一致性和复制 主要内容 7.1 一致性与复制 7.2 以数据为中心的一致性模型 7.3 以客户为中心的一致性模型 7.4 复制管理 7.5 一致性协议 7.1 一致性与复制 复制的理由 提高可靠性：防止单点失败，数据校验 提高性能：并行性，可伸缩性 复制的代价 一致性维护：更新问题 例：Web页的Cache 支持伸缩性的复制技术 将数据的副本放置在处理它们的进程附近以减少访问时间，解决可伸缩性问题 复制策略 设进程P对数据d的访问N次/秒，d的更新M次/秒 当NM时，访问/更新比非常低，由于一致性维护带来更大代价，因此，不应复制 支持伸缩性的复制技术 一致性维护与可伸缩性问题 保证所有的副本都是相同的，--〉紧密一致性 当某个副本上执行更新操作时，需对所有副本进行全局同步 ，在大型系统上很难实施--〉可伸缩性问题 解决策略 松驰一致性，所有副本不一定保持完全相同，尽量减少立即的全局同步 7.2 以数据为中心的一致性模型 分布式数据仓(data store)模型 物理上，分布的和复制的 例如，分布式共享内存、数据库、文件 操作：每个进程可执行读操作，写操作 写操作在本地副本上进行，再传播给其他副本 一致性模型 数据相干性（coherency） 同一个数据在各个数据仓中的值保持一致 从单个数据的视角 一致性模型 多个进程与多个数据之间的操作，保持一致性 进程与数据仓之间的契约(contract) 如果进程遵守约定的规则，数据仓就能工作正常。 如果进程违反了这些规则，数据仓就不再保证操作的正确性 持续一致性模型 范围： 副本之间的数值偏差：已应用于给定副本但还没有应用于其他副本的更新数目 副本之间的新旧程度偏差：与副本最近一次更新有关 副本之间的更新操作顺序偏差：副本之间不同的更新顺序 持续一致性模型 一致性单元（conit）：受控的数据集 举例：conit（x,y） 一致性单元的粒度选择 粗粒度：任一个更新操作都导致更新传播 虚假共享问题 细粒度：当一个数据更新时，另一个数据无需更新 顺序一致性 记法规则： Wi(x)a:表示进程Pi把数值a写入数据项x Ri(x)b:表示进程Pi从数据项x读取数据后返回数值b 顺序一致性 规则：所有进程执行的结果，等同于它们的操作按某种顺序在数据仓上执行的结果。每个进程的操作都按照程序规定的顺序。 例：顺序一致性 顺序一致性 所有进程看到相同的内存访问操作次序 等价于数据库的可串行化（serializability） 操作粒度：命令 vs.事务 例：非顺序一致性 顺序一致性举例 例： 3个并行执行的进程 90种正确的执行顺序 因果一致性 因果关系(Causality)： P1写x,P2读x，则R2(x)与W1(x)具有潜在的因果关系。 P1写x,P2读x,然后写y，则W2(y)与W1(x)具有潜在的因果关系。 否则，操作之间的关系为并发(Concurrent)关系 例：P1写x,P2写z，则W1(x)与W2(z)不具有潜在因果关系。 定义： 对于具有潜在因果关系的写操作，所有进程看到的执行顺序应相同。 并发写操作在不同主机上被看到的顺序可以不同。 因果一致性 例：因果一致性 例：违反因果一致性 因果一致性 例：符合因果一致性 实现技术 操作依赖图 向量时钟(vector clock) 分组操作 同步变量：与一个数据区相关联 Synchronize(S) 同步所有的数据局部拷贝 导出： 导入： 规则： 对同步变量的访问必须满足顺序一致性。 在所有先前的写操作完成之前,不能访问同步变量 在所有先前的同步操作完成之前,不能访问（读/写）数据。 入口一致性（1） 同步变量 与某个共享数据项相关联 不是与数据区中的所有保护型数据关联 拥有者(owner)：最后一个获取（acquire）它的进程。 其他进程必须从当前所有者手中取得拥有权。 非互斥方式（non-exclusive）:可以读，但不能写 多个进程可以非互斥方式同时拥有一个同步变量 入口一致性（2） 规则： 在进程P获取同步变量S之前，有关的被保护的共享数据上的全部更新操作都必须完成； 在进程P以互斥模式访问同步变量S之前，不允许其他进程同时拥有S，即使在非互斥模式下； 在进程P以互斥模式获取同步变量S之后，任意其他进程都不能对S执行非互斥式访问，除非在S的拥有者P执行之后。 入口一致性（3） 例：入口项一致性 7.3 以客户为中心的一致性模型 分布式数据存储区 没有同时更新（无写-写冲突）或容易解决 大多数操作为读操作 例：Web网页（服务器，代理缓存） 最终一致性（eventual consistency） 如果很长时间不发生更新操作，则所有的副本将逐渐变为一致的。 最终一致性（1