复制.ppt

《复制.ppt》由会员分享，可在线阅读，更多相关《复制.ppt（54页珍藏版）》请在三一文库上搜索。

1、第6章 复制,第6章 复制,简介 系统模型 容错服务 高可用服务的实例研究：gossip体系结构、Bayou和Coda 小结,简介,复制的概念 在多个计算机中进行数据副本的维护。 复制的动机：增强服务 增强性能 - 浏览器对Web资源的缓存 - 数据在多个服务器之间地透明复制 提高可用性 - 服务器故障：1pn - 网络分区和断链操作：预先复制 增强容错能力 - 正确性：允许一定数量和类型的故障,简介,复制的基本要求 复制透明性 - 对客户屏蔽多个物理拷贝的存在 - 客户仅对一个逻辑对象进行操作 一致性 - 在不同应用中有不同强度的一致性需求 - 复制对象集合的操作必须满足应用需求,第6章 复

2、制,简介 系统模型 容错服务 高可用服务的实例研究：gossip体系结构、Bayou和Coda 小结,系统模型,基本模型,系统模型,基本模型组件 副本管理器 - 接收前端请求 - 对副本执行原子性操作 前端 - 接收客户请求 - 通过消息传递与多个副本管理器进行通信,系统模型,副本对象的操作 请求：前端将请求发送至一个或多个副本管理器 协调 - 保证执行的一致性 - 对不同请求进行排序（FIFO，因果，全序） 执行：包括临时请求的执行 协定：就提交请求的影响达成一致 响应：一个或多个副本管理器响应前端,第6章 复制,简介 系统模型 容错服务 高可用服务的实例研究：gossip体系结构、Bayo

3、u和Coda 小结,容错服务,复制是提高系统容错能力的有效手段之一 为用户提供一个单一的镜像 副本之间需要保持严格的一致性 副本之间的不一致性将导致容错能力失效 银行帐户示例,容错服务,1. 银行帐户x和y的两个副本管理器位于计算机A、B上 2. 客户在本地的副本管理器上读取和更新帐户,容错服务,由于B在把帐户x的更新传送至A前出现故障，所以产生了不一致现象,客户1: setBalanceB(x,1) Server B failed setBalanceA(y,2),客户2: getBalanceA(y)=2 getBalanceA(x)=0,容错服务,被动(主备份)复制 一个主副本管理器多个

4、次副本管理器 - 若主副本管理器出现故障，则某个备份副本管理器将提升为主副本管理器。 模型,容错服务,被动复制时的事件次序 请求 - 前端将请求发送给主副本管理器 协调 - 主副本管理器按接收次序对请求排序 执行 - 主副本管理器执行请求并存储响应,容错服务,被动复制时的事件次序(续) 协定 - 若请求为更新操作，则主副本管理器向每个备份副本管理器发送更新后的状态、响应和唯一标识符。 - 备份副本管理器返回确认。 响应 - 主副本管理器将响应发送给前端 - 前端将响应发送给客户,容错服务,主动复制 副本管理器地位对等，前端组播消息至副本管理器组 模型,容错服务,主动复制时的事件次序 请求 -

5、前端使用全序、可靠的组播原语将请求组播到副本管理器组 协调 - 组通信系统以同样的次序(全序)将请求传递到每个副本管理器 执行 - 每个副本管理器以相同的方式执行请求 响应 - 每个副本管理器将响应发送给前端 - 前端将响应发送给客户,第6章 复制,简介 系统模型 容错服务 高可用服务的实例研究：gossip体系结构、Bayou和Coda 小结,高可用服务的实例研究,高可用性和容错能力 容错能力 - 只要可能，所有正确的副本管理器都能够及时收到更新，并在将控制传递回客户以前达成一致。 高可用性 - 采用较弱程度的一致性，提高共享数据的可用性。 - 实例：gossip、Bayou和Coda,go

6、ssip体系结构,体系结构 前端可以选择任意副本管理器 提供两种基本操作：查询更新 副本管理器定期通过gossip消息来传递客户的更新,(2,2,3),gossip体系结构,体系结构(续) 系统的两个保证 - 随着时间的推移，每个用户总能获得一致服务 副本管理器提供的数据能反映迄今为止客户已经观测到的更新 - 副本之间松弛的一致性 所有副本管理器最终将收到所有更新 两个客户可能会观察到不同的副本 客户可能观察到过时数据,gossip体系结构,查询和更新操作流程 请求 - 前端将请求发送至副本管理器 查询：客户可能阻塞 更新：无阻塞 更新响应 - 副本管理器立即应答收到的更新请求 协调 - 收到

7、请求的副本管理器并不处理操作，直到它能根据所要求的次序约束处理请求为止。,gossip体系结构,查询和更新操作流程(续) 执行 - 副本管理器执行请求 查询响应 - 副本管理器对查询请求作出应答 协定 - 副本管理器通过交换gossip消息进行相互更新 gossip消息的交换是偶尔的 发现消息丢失后，才和特定的副本管理器交换消息,gossip体系结构,前端的版本时间戳 客户交换数据 -通过访问相同的gossip服务 - 相互直接通信,为了控制操作处理次序，每个前端维持了一个向量时间戳,gossip体系结构,前端的版本时间戳(续) 每个前端维护一个向量时间戳 - 每个副本管理器有一条对应的记录

8、- 更新或查询信息中包含时间戳 -合并操作返回的时间戳与前端时间戳 向量时间戳的作用 - 反映前端访问的最新数据值,gossip体系结构,副本管理器状态,gossip体系结构,副本管理器状态(续) 值 - 副本管理器维护的应用状态的值 值的时间戳 - 更新的向量时间戳 更新日志 - 记录更新操作 副本的时间戳 - 已经被副本服务器接收到的更新,gossip体系结构,副本管理器状态(续) 已执行操作表 - 记录已经执行的更新的唯一标识符，防止重复执行 时间戳表 - 确定何时一个更新已经应用于所有的副本管理器,gossip体系结构,查询操作 副本管理器收到查询 - q.prevalueTS 立即响

9、应 返回消息中的时间戳为valueTS - 否则 将消息保存到保留队列 如：q.pre(2,4,6),valueTS(2,5,5) 前端收到查询响应 - 合并时间戳：frontEndTS:=merge(frontEndTS,new)(2,5,6),gossip体系结构,按因果次序处理更新 前端发送更新请求：(u.op, u.prev, u.id) 副本管理器i接收请求 - 丢弃：操作已经处理过 - 否则，将更新记录日志 ts =u.prev, tsi=tsi+1 logRecord= - 副本管理器将ts返回给前端 frontEndTS=merge(frontEndTS, ts),gossip

10、体系结构,按因果次序处理更新(续) 更新请求u的稳定性条件 u.prevvalueTS 副本管理器的更新操作 - value := apply(value, r.u.op) - valueTS := merge(valueTS, r.ts) - executed := executedr.u.id,gossip体系结构,强制的和即时的更新操作 强制更新和即时更新需要特殊处理，强制更新是全序加因果序，保证更新的强制次序的基本方法是在相现象的时间戳后加入一个唯一的序号，并以这个序号的次序来处理它们。 gossip消息 副本管理器通过gossip消息来更新自身的状态。通过时间戳表里的记录来估计其它副

11、本管理器还没有收到哪些更新。 gossip消息m的格式：日志m.log和副本时间戳m.ts,gossip体系结构,收到gossip消息后执行的操作 日志合并 - 若r.ts replicsTS，则丢弃 - 将记录加入到日志，合并时间戳 replicaTS := merge(replicaTS, m.ts) 执行任何以前没有执行并已经稳定了的更新 - 根据向量时间戳的偏序“”对更新进行排序，并依次执行更新。 当知道更新已执行并没有重复执行的危险时，删除日志和已执行操作表中的记录 - 若tableTSic r.tsc，则丢弃r。,gossip体系结构,更新传播 gossip体系结构未规定具体的更新

12、传播策略 如何选择合适的gossip消息的发送频率？ - 分钟、小时或天？由具体应用需求决定 如何选择合适的合作者(副本管理器) - 随机策略 使用加权概率来选择更合适的合作者 - 确定策略 使用副本管理器状态的函数来选择合作者 - 拓扑策略 网格、环、树,gossip体系结构,目标：保证服务的高可用性 存在问题： 不适合接近实时的更新复制 可扩展性问题,Bayou系统和操作变换方法,Bayou系统简介 与gossisp体系结构和基于时间戳的反熵协议类似 提供的一致性保证弱于顺序一致性 能够进行冲突检测和冲突解决 - 操作变换：一个或多个相冲突的操作被取消或改变以解决冲突的过程。 - 例子 行

13、政主管和秘书同时预约 ，其中行政主管为离线更新行政主管上线后，Bayou系统检测到冲突，然后批准行政主管的预约而取消秘书的预约。,Bayou系统和操作变换方法,提交的更新和临时更新 临时的更新 更新首次应用于数据库时，被标记为临时的。 提交的更新 Bayou将临时的更新以规范次序放置，并添加提交标识。 数据库副本状态 提交的更新序列临时的更新序列 更新重排序 新更新到达或某个临时更新被修改为提交的更新,Bayou系统和操作变换方法,提交更新和临时更新示例,临时更新ti成为下一个提交更新， 并被插入到最新提交更新cN之后,Bayou系统和操作变换方法,依赖检查和合并过程 依赖检查 - 一个更新执

14、行时是否会产生冲突 - 例子：写写冲突、读写冲突检测 合并过程 - 改变将要执行的操作，避免冲突，并获得相似效果 - 无法合并系统报错 Bayou系统讨论 复制对于应用而言是不透明的 复杂度高,Coda文件系统,AFS的主要缺陷 只提供有限复制，规模受限，不适用于大规模共享的文件访问。 Coda目标 提供一个共享的文件存储。 Coda对AFS的扩展 采用文件卷复制技术提高吞吐率和容错性 在客户计算机上缓存文件副本断链处理,Coda文件系统,Coda体系结构 Venus/Vice进程 - Venus：前端和副本管理器的混合体 - Vice：副本管理器 卷存储组(VSG) 持有一个文件卷副本的服务

15、器集合 可用的卷存储组(AVSG) 打开一个文件的客户能访问的VSG的某个子集,Coda文件系统,Coda体系结构(续) 文件访问过程 - 当前AVSG中的任何一个服务器提供文件服务，并缓存在客户计算机上。 - 对每个副本管理器进行更新分布。 关闭文件 - 修改过的拷贝并行广播到AVSG中的所有服务器。,Coda文件系统,Coda体系结构(续) 断链操作 - AVSG为空时，客户缓存文件 - 手工干预解决冲突 设计原则 - 服务器上的拷贝比客户计算机缓存中的拷贝更可靠,Coda文件系统,复制策略 乐观策略 - 在网络分区和断链操作期间，仍然可以进行文件修改 实现 - Coda版本向量(CVV)

16、 作为时间戳附加在每个版本的文件上 CVV中的每个元素是一个估计值，表示服务器上文件修改次数的估计 目的提供足够的关于每个文件副本的更新历史，以检测出潜在的冲突，进行手工干预和自动更新。,Coda文件系统,复制策略(续) 例如：CVV=（2，2，1） - 文件在服务器1上收到2个更新 -文件在服务器2上收到2个更新 -文件在服务器3上收到1个更新 冲突检测 - 若一个站点的CVV大于或等于所有其它站点相应的CVV，则不存在冲突。自动更新 - 若对于两个CVV而言，v1v2与v2v1均不成立，则存在一个冲突。 手工干预,Coda文件系统,复制策略(续.) 文件关闭 - Venus进程发送更新消息

17、（包括CVV和文件的新内容）到AVSG - AVSG中的每个服务器更新文件，并返回确认。 - Venus计算新的CVV，增加相应服务器的修改记数，并分发新的CVV。,Coda文件系统,构建CVV示例一 文件F在三个服务器S1、S2和S3上有副本 - VSG = S1, S2, S3 - F被C1,C2修改 - 由于网络分区的原因C1: S1, S2； C2: S3,Coda文件系统,构建CVV示例一(续) 最初，F的CVV在3个服务器上是相同的，比如1, 1, 1 C1修改F，然后关闭 - S1和S2上的CVV更新为：2, 2, 1,Coda文件系统,构建CVV示例一(续.) 网络故障修复后

18、- S1和S2上的CVV为2, 2, 1，S3上的CVV为1, 1, 1 - S1或S2上的文件版本替代S3上的文件版本,Coda文件系统,构建CVV示例二 文件F在三个服务器S1、S2和S3上有副本 - VSG = S1, S2, S3 - F在同一时间被C1和C2修改 - C1: S1, S2； C2: S3,Coda文件系统,构建CVV示例二(续) 最初，F的CVV在3个服务器上是相同的，比如1, 1, 1 C1修改F，然后关闭 - S1和S2上的CVV更新为：2, 2, 1 同时，C2上的两个进程分别修改F，然后关闭 - S3上的CVV更新为：1, 1, 3,Coda文件系统,构建CVV示例二(续.) 网络故障修复后 - S1和S2上的CVV为2, 2, 1，S3上的CVV为1, 1, 3 - 存在冲突，需手工干预,小结,分布式系统的复制 增强性能、提高可用性和容错能力 组通信 组成员关系服务视图传递 视图同步的组通信 容错服务 主备份复制 主动复制,小结,高可用服务 gossip bayou coda,