基于执行历史图的副本一致性检测算法
分布式存储系统数据副本一致性即同一数据项在不同物理节点上的差异程度.提出了执行历史图(execution history graph,EHG)的概念,并设计出基于EHG的一致性检测算法.对于长度为n、最大并行度为p的执行历史,算法可以在O(n lg n+np)的时间内正确度量出执行历史的安全一致性和普通一致性,远快于已有的时间复杂度为O(n2)的基于有向无环图(directed acyclic graph,DAG)的检测算法.本算法通过分析执行历史中操作之间的并行与顺序关系,构造出执行历史图,并在执行历史图的基础上模拟执行历史运行时数据项的值的变化情况,从而找出所有违反安全和普通一致性的读操作.在Cassandra系统上通过和DAG算法的对比,验证了EHG算法的正确性与高效性,并分析出了算法执行时间和并行度、执行历史长度的关系,以及并行度对执行历史一致性程度的影响.
分布式存储系统 一致性检测 执行历史图
白渐 王建民 黄向东 王欣
清华大学软件学院 北京 100084
国内会议
太原
中文
40-47
2014-09-19（万方平台首次上网日期，不代表论文的发表时间）