06-复制范例.ppt

gossip体系结构 按因果次序处理更新(续) 更新请求u的稳定性条件 　　u.prev≤valueTS 即所有由发起更新的前端观察到的更新已经执行了，指副本服务器？ 如果更新提交时这个条件不满足，它将在闲聊消息到达时重新检查。 副本管理器的更新操作 　 - value := apply(value, r.u.op) - valueTS := merge(valueTS, r.ts) - executed := executed∪{r.u.id} gossip体系结构 强制的和即时的更新操作 强制更新和即时更新需要特殊处理，强制更新是全序加因果序，保证更新的强制次序的基本方法是在与更新相关的时间戳后加入一个唯一的序号，并以这个序号的次序来处理它们。 gossip消息 副本管理器通过gossip消息来更新自身的状态。通过时间戳表里的记录来估计其它副本管理器还没有收到哪些更新。 gossip消息m的格式：日志m.log和副本时间戳m.ts gossip体系结构 收到gossip消息后执行的操作 日志合并- replicsTS表示接收者的副本时间戳 　 - 若r.ts ≤replicsTS，则丢弃 　 - 否则，将m.log中记录r加入到接收者的日志，合并时间戳 　　replicaTS := merge(replicaTS, m.ts) 执行任何以前没有执行并已经稳定了的更新 　 - 根据向量时间戳的偏序“≤”对更新进行排序，并依次执行更新。 如果闲聊消息由副本管理器j发送且tableTS是这个副本管理器的副本时间戳表，则副本管理器设置： tableTS[j]：= m.ts 当知道更新已执行并没有重复执行的危险时，删除日志和已执行操作表中的记录。如果c是创建这个记录的副本管理器，要求所有的副本管理器i: 　 - 若tableTS[i][c] ≥ r.ts[c]，则丢弃日志中的记录r。 gossip体系结构 更新传播 gossip体系结构未规定具体的更新传播策略 如何选择合适的gossip消息的发送频率？ 　 - 分钟、小时或天？——由具体应用需求决定 如何选择合适的合作者(副本管理器) 　 - 随机策略 　　　使用加权概率来选择更合适的合作者 - 确定策略 　　　使用副本管理器状态的函数来选择合作者 - 拓扑策略 　　　网格、环、树 gossip体系结构 目标：保证服务的高可用性 存在问题： 不适合接近实时的更新复制 可扩展性问题 Bayou系统和操作变换方法 Bayou系统简介 与gossisp体系结构和基于时间戳的反熵协议类似 （反熵这是热力学中的一个术语，这个词的意思简而言之就是说投入的多但释放出来的能量少，也就是“费力不讨好”的现象在物理学中表现的一种形式。 ） 提供的一致性保证弱于顺序一致性 能够进行冲突检测和冲突解决 - 操作变换：一个或多个相冲突的操作被取消或改变以解决冲突的过程。 　 - 例子 　　　行政主管和秘书同时预约 ，其中行政主管为离线更新——行政主管上线后，Bayou系统检测到冲突，然后批准行政主管的预约而取消秘书的预约。 Bayou系统和操作变换方法 提交的更新和临时更新 临时的更新 　　更新首次应用于数据库时，被标记为临时的。 提交的更新 　　Bayou将临时的更新以规范次序放置，并添加提交标识。 数据库副本状态 　　提交的更新序列＋临时的更新序列 更新重排序 新更新到达或某个临时更新被修改为提交的更新 Bayou系统和操作变换方法 提交更新和临时更新示例 t2 t1 t0 cN c2 c1 c0 Ti+1 ti .... .... 已提交 临时 临时更新ti成为下一个提交更新， 并被插入到必威体育精装版提交更新cN之后 Bayou系统和操作变换方法 依赖检查和合并过程 依赖检查 　 - 一个更新执行时是否会产生冲突 　 - 例子：写－写冲突、读－写冲突检测 合并过程 　 - 改变将要执行的操作，避免冲突，并获得相似效果 　 - 无法合并→系统报错 Bayou系统讨论 复制对于应用而言是不透明的 复杂度高 Coda文件系统 AFS(Andrew文件系统)的主要缺陷 　　　只提供有限复制，规模受限，不适用于大规模共享的文件访问。 Coda目标 　　　提供一个共享的文件存储。 Coda对AFS的扩展 采用文件卷复制技术——提高吞吐率和容错性 在客户计算机上缓存文件副本——断链处理 Coda文件系统 Coda体系结构 Venus/Vice进程 　 - Venus：前端和副本管理器的混合体 　 - Vice：副本管理器 卷存储组(VSG) 持有一个文件卷副本的服务器集合