数据网格中复制式数据的一致性维护方法.ppt

Size: px

Start display at page:

Download "数据网格中复制式数据的一致性维护方法.ppt"

迈浈仲
4 years ago
Views:

1 数据网格中复制式数据的一致性维护方法杨江明复旦大学计算机与信息技术系上海市邯郸路 220 号

2 内容提要背景介绍相关工作系统构架一致性维护方法结论

3 内容提要背景介绍相关工作系统构架一致性维护方法结论

4 背景介绍为什么是网格环境? 网格是资源共享的趋势机遇与挑战用户对资源的需求对于参与的需求 Wikipedia, Open directory project, 对于交互的需求以各种论坛为代表的大量数据, 是以用户交互性的需求为前提的对于协同的需求是企业全球化与信息化的趋势

5 内容提要背景介绍相关工作系统构架一致性维护方法结论

6 相关工作网格环境下数据存储的研究如 edonkey emule Globus Data Grid EU Data Grid OceanStore 等等大都仅仅着眼于数据的动态性, 分布性和可获得性, 缺乏对网格数据实时修改的支持一致性维护方法的研究传统的一致性维护方法如 : 分布式锁轮寻等方法, 无法满足用户操作的实时响应无锁的一致性维护方法如 : 操作转换方法地址空间转换方法, 不支持同一站点内的并发操作

7 内容提要背景介绍相关工作系统构架一致性维护方法结论

8 系统构架通过在数据网格中维护多个数据副本用户可以选择其中任意一个进行访问修改用户的操作在其访问的数据副本上立即执行保证全部操作执行完成之后, 各个数据副本间的一致性

9 系统构架对数据副本的约束实时性 (Real-time), 用户可以选择任意的数据副本访问, 并且可以从这个数据副本立即得到返回结果独立性 (Independency), 如果一个数据副本崩溃, 不会影响其它的数据副本一致性 (Consistency), 对于修改操作, 用户只需要在一个数据副本上执行操作, 所有的数据副本会保持一致

10 内容提要背景介绍相关工作系统构架一致性维护方法结论

11 一致性维护方法我们采用无锁的一致性维护方法 : 基于地址空间转换的方法通过引入新的时间戳模型, 使其可以支持同一站点内的并发操作使用 XML 模型描述数据结构使用 XQuery 和 XUpdate 描述用户操作, Query 和 Update 间不存在并发冲突

12 因果关系和并发关系定义因果关系考虑两个操作 O a 和 O b, 分别来自用户 i 和 j 操作满足因果关系 O a O b, 当且仅当, 当 i=j, 操作 O a 的产生在操作 O b 之前当 i j, 操作 O a 在数据副本上的执行在收到操作 O b 之前存在一个操作 O x,o a O x 且 O x O b 并发关系考虑两个操作 O a 和 O b, 操作满足并发关系 O a O b, 当且仅当, 即没有 O a O b, 也没有 O b O a

13 关系时间戳和执行时间戳一个时间戳仍然时一个状态向量假设网格环境有 N 个数据副本, 每个数据副本有一个唯一的标识符 ID 不妨假设数据副本标识符为整数 0,1,...,N-1 则数据副本 i 的状态向量为 N 元向量, 其中第 j 维表示来自数据副本 j 的操作的执行个数例如一个 3 数据副本的时间戳向量, 可以表示为 <3,1,2> 为了便于理解, 本文仍然使用了基于向量的时间戳, 动态环境下的时间戳表示, 可参见论文 : Ning Gu, Qiwei Zhang, Jiangming Yang. DCH: An Approach to Improve The Scalability of Causality Capturing in Real-time Groupwares

14 关系时间戳和执行时间戳关系时间戳 : 关系时间戳各个维的初始值均为 0 当副本 i 收到一个新的操作 O, 则副本 i 的关系时间戳向量的第 i 维加 1, 得到的结果为操作 O 的关系时间戳当副本 i 执行了一个来自副本 j 的远程操作, 则关系时间戳的第 j 维加 1 执行时间戳 : 执行时间戳各个维的初始值均为 0 当副本 i 收到一个新的操作 O, 副本 i 当前的执行时间戳向量即为操作 O 的执行时间戳当副本 i 执行了一个本地操作, 则执行时间戳向量的第 i 维加 1 当副本 i 执行了一个来自副本 j 的远程操作, 则执行时间戳的第 j 维加 1 当一个操作在其源副本执行之后, 会附着着它的关系时间戳和执行时间戳一同广播到其它数据副本

15 操作的执行条件定义,( 新时间戳模型下远程操作的执行条件 ) 假设操作 O 是来自副本 a 的操作, 它的关系时间戳是 SV R O 在副本 b 上,b 的执行时间戳向量是 SV E b, 操作 O 在副本 b 上满足执行条件当且仅当 : SV R O [a]=sve b [a]+1 SV R O [i]<=sve b [i], 0 i N-1 且 i a

16 控制算法因为基于地址空间转换算法的回溯过程和执行过程是依照给定的时间戳来执行的, 当时间戳可以确定时, 算法的回溯过程和执行过程可以保持不变考虑一个来自数据副本 a 的远程操作, 它的关系时间戳为 SV R O, 它的执行时间戳为 SV E O, 文档可以表示为 XML Docb 文档的关系时间戳为 SV R b, 执行时间戳为 SV E b Procedure 控制算法 (XML Docb,O), 在 XML Docb 上执行操作 O 1: While( 操作 O 不满足基于 SV R O 的执行条件 ) 2: 等待下一个操作的执行 3: Retracing XML (XML Docb, SV E O ) 4: 调用 FLW(XML Docb, SV E O ), 获得执行集行 ES 5: 取消 Retracing XML 过程的影响 6: U(XML Docb, SV E O, ES) 7: 设置 SV E b [R] SVE b [R]+1 8: 设置 SV R b [R] SVR b [R]+1

17 正确性证明略基于地址空间转换算法的一致性证明, 参见 : Ning Gu, Jiangming Yang, Qiwei Zhang. Consistency maintenance based on the mark & retrace technique in groupware systems. In Proceedings of ACM GROUP Conference, Sanibel Island, USA, Nov 2005, 新的时间戳模型对于因果关系维护的证明, 参见 : Jiangming Yang, Qiwei Zhang, Ning Gu. A Consistency Maintenance Approach in Replicated Services. In Proceedings of 2006 IEEE international conference on computer and information technology, September 2006, Seoul, Korea. Accepted.

18 内容提要背景介绍相关工作系统构架一致性维护方法结论

19 结论本文第一次提出了数据网格中多副本数据的一致性维护方法, 允许用户自由地修改网格中的数据内容, 支持一个数据副本上的并发操作, 且可以满足网格环境下数据的 RIC 属性本文基于的标记回溯算法已经在 CoAutoCAD 系统上得到实现

主持人本刊特约记者春华郑兰英他们之间的信息是可以共享的互操作的这三个嘉宾王丹建设综合勘察研究设计院副院长条件真正实施起来并不容易因此现在我们的数字孙建中上海城市发展信息研究中心信城市还在起步阶段信息化没有止境数字城市建息技术部主任设同样没有止境随着技术不断发展

主持人本刊特约记者春华郑兰英他们之间的信息是可以共享的互操作的这三个嘉宾王丹建设综合勘察研究设计院副院长条件真正实施起来并不容易因此现在我们的数字孙建中上海城市发展信息研究中心信城市还在起步阶段信息化没有止境数字城市建息技术部主任设同样没有止境随着技术不断发展期间中外数字城市建设现状与成果推动相关数随着北京香港上海广州等大城市数字化建设字城市建设技术设备及产品在城市建设领域的应的启动许多省市已将数字城市作为实现区域信息用促进中外城市之间政府与企业之间在数化的切入点和突破口成功召开的首届及第二届数字城市领域的广泛合作培育数字城市产业字城市大会使得政府相关企业及公众对数字城市链共同推进中外信息化技术的发展与进步