基于共享图和部分复制策略的分布式存储因果一致性模型

doi:10.11959/j.issn.1000-436x.2020079

通信学报 ›› 2020, Vol. 41 ›› Issue (5): 48-58.doi: 10.11959/j.issn.1000-436x.2020079

基于共享图和部分复制策略的分布式存储因果一致性模型

田俊峰^1,²,杨万贺^1,²(),庞亚南^1,²,张俊涛^1,²

¹ 河北大学网络空间安全与计算机学院，河北保定 071002
² 河北省高可信信息系统重点实验室，河北保定 071002

修回日期:2020-03-24 出版日期:2020-05-25 发布日期:2020-05-30
作者简介:田俊峰（1965- ），男，河北保定人，博士，河北大学教授、博士生导师，主要研究方向为信息安全与分布式计算|杨万贺（1996- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性|庞亚南（1995- ），女，河北衡水人，河北大学硕士生，主要研究方向为信息安全、数据一致性|张俊涛（1995- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性
基金资助:
国家自然科学基金资助项目(6180060654)

Causal consistency model for distributed data store based on shared graph and partial replication strategy

Junfeng TIAN^1,²,Wanhe YANG^1,²(),Ya’nan PANG^1,²,Juntao ZHANG^1,²

¹ School of Cyber Security and Computer,Hebei University,Baoding 071002,China
² Key Laboratory on High Trusted Information System in Hebei Province,Baoding 071002,China

Revised:2020-03-24 Online:2020-05-25 Published:2020-05-30
Supported by:
The National Natural Science Foundation of China(6180060654)

摘要/Abstract

摘要：

针对目前因果一致性模型中存在的元数据传播开销大、操作时延、远程更新可见时延高等问题，提出了基于共享图和部分复制策略的分布式存储因果一致性模型。该模型以共享图拓扑结构为基础，每个数据中心存放完整数据集的子集，同时，提出了共享稳定向量与混合逻辑时钟相结合的全局稳定策略，在保证因果关系的前提下，实现数据中心间的数据一致性。理论分析和仿真实验结果表明，与现有模型相比，所提模型在降低操作时延的同时，可有效地权衡远程更新可见性能和元数据开销。

关键词: 数据一致性, 因果一致性, 共享图, 部分复制策略, 全局稳定策略

Abstract:

In order to solve the problem of metadata propagation overhead,operation delay and remote update visibility latency in the current causal consistency model,a causal consistency model for distributed data stores based on the shared graph and partial replication strategy was proposed.This model was based on the topology of the shared graph,and each data center stored an arbitrary subset of the data.At the same time,the global stabilization strategy combining shared stable vector and hybrid logical clocks was proposed to provide data consistency guarantees on the premise of ensuring causality.The theoretical analysis and experimental results show that the proposed model can effectively balance the remote update visibility and the metadata overhead compared with the existing models while reducing the operation delay.

Key words: data consistency, causal consistency, shared graph, partial replication strategy, global stabilization strategy

中图分类号:

TP393

田俊峰,杨万贺,庞亚南,张俊涛. 基于共享图和部分复制策略的分布式存储因果一致性模型[J]. 通信学报, 2020, 41(5): 48-58.

Junfeng TIAN,Wanhe YANG,Ya’nan PANG,Juntao ZHANG. Causal consistency model for distributed data store based on shared graph and partial replication strategy[J]. Journal on Communications, 2020, 41(5): 48-58.

图/表 8

图1

图2

图3

图4

表1

图5

图6

图7

参考文献 22

[1]	DU J Q , ELNIKETY S , ROY A ,et al. Orbe:scalable causal consistency using dependency matrices and physical clocks[C]// Proceedings of the 4th Annual Symposium on Cloud Computing. New York:ACM Press, 2013: 11-14.
[2]	AKKOORATH D D , TOMSIC A Z , BRAVO M ,et al. Cure:strong semantics meets high availability and low latency[C]// 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2016: 405-414.
[3]	MARCOS K , AGUILER A , TERR Y . The many faces of consistency[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2016,39(1): 3-13.
[4]	朱涛, 郭进伟, 周欢 ,等. 分布式数据库中一致性与可用性的关系[J]. 软件学报, 2018,29(1): 131-149.
	ZHU T , GUO J W , ZHOU H ,et al. Consistency and availability in distributed database systems[J]. Journal of Software, 2018,29(1): 131-149.
[5]	AHAMAD M , NEIGER G , BURNSI J E ,et al. Causal memory:definitions,implementation,and programming[J]. Distributed Computing, 1995,9(1): 37-49.
[6]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . Optimistic causal consistency for geo-replicated key-value stores[C]// 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2017: 2626-2629.
[7]	BAILIS P , VENKATARAMAN S , MICHAEL J ,et al. Quantifying eventual consistency with PBS[J]. The VLDB Journal, 2014,23(2): 279-302.
[8]	AGRAWAL D , ABBADI A E , SALEM K . A Taxonomy of partitioned replicated cloud-based database systems[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2015,38(1): 4-9.
[9]	TOMSIC A Z , CRAIN T , SHAPIRO M . PhysiCS-NMSI:efficient consistent snapshots for scalable snapshot isolation[C]// Proceedings of the Workshop on the Principles and Practice of Consistency for Distributed Data.[S.n.:s.l]. 2016:21.
[10]	DU J Q , IORGULESCU C , ROY A ,et al. Gentlerain:cheap an scalable causal consistency with physical clocks[C]// Proceedings of the ACM Symposium on Cloud Computing. New York:ACM Press, 2014: 1-13.
[11]	DIDONA D , SPIROVSKA K , ZWAENEPOEL W . Okapi:causally consistent geo-replication made faster,cheaper and more available[J]. arXiv Preprint,arXiv:1702.04263, 2017
[12]	ROOHITAVAF M , DEMIRBAS M , KULKARNI S S . CausalSpartanX:causal consistency and non-blocking read-only transactions[J]. arXiv Preprint,arXiv:1812.07123, 2018
[13]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . PaRiS:causally consistent transactions with non-blocking reads and partial replication[J]. arXiv Preprint,arXiv:1902.09327, 2019
[14]	GUNAWARDHANA C , BRAVO M , RODRIGUES L E . Unobtrusive deferred update stabilization for efficient geo-replication[C]// USENIX Annual Technical Conference. Berkeley:USENIX Association, 2017: 83-95.
[15]	BRAVO M , RODRIGUES L , ROY P V . Saturn:a distributed metadata service for causal consistency[C]// European Conference on Computer Systems. New York:ACM Press, 2017: 111-126.
[16]	XIANG Z L , VAIDYA N H . Global stabilization for causally consistent partial replication[J]. arXiv Preprint,arXiv:1803.05575, 2018
[17]	ALMEIDA S , LEITAO J , RODRIGUES L E . ChainReaction:a causal+consistent datastore based on chain replication[C]// European Conference on Computer Systems. New York:ACM Press, 2013: 85-98.
[18]	刘佩, 蒋梓逸, 曹袖 . 一种基于分布式存储系统中多节点修复的节点选择算法[J]. 计算机研究与发展, 2018,55(7): 1557-1568.
	LIU P , JIANG Z Y , CAO X . Node selection algorithm during multi-nodes repair progress in distributed storage system[J]. Journal of Computer Research and Development, 2018,55(7): 1557-1568.
[19]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . Wren:nonblocking reads in a partitioned transactional causally consistent data store[C]// The 48th International Conference on Dependable Systems and Networks. Piscataway:IEEE Press, 2018: 1-12.
[20]	ROOHITAVAF M , AHN J S , KANG W H ,et al. Session guarantees with raft and hybrid logical clocks[J]. arXiv Preprint,arXiv:1808.05698, 2018
[21]	ROOHITAVAF M , DEMIRBAS M , KULKARNI S S . CausalSpartan:causal consistency for distributed data stores using hybrid logical clocks[C]// IEEE International Symposium on Reliable Distributed Systems. Piscataway:IEEE Press, 2017: 184-193.
[22]	DIDONA D , GUERRAOUI R , WANG J J ,et al. Causal consistency and latency optimality:friend or foe?[J]. Proceedings of the VLDB Endowment, 2018,11(11): 1618-1632.

模型	时钟	复制策略	向量	操作时延
文献[10]	物理时钟	完全复制策略	全局稳定时间戳(1)	高
文献[11]	混合逻辑时钟	完全复制策略	通用稳定向量(m)	较低
文献[16]	物理时钟	部分复制策略	全局稳定时间戳(1)	较高
CCSGPR	混合逻辑时钟	部分复制策略	共享稳定向量(2)	低

基于共享图和部分复制策略的分布式存储因果一致性模型

Causal consistency model for distributed data store based on shared graph and partial replication strategy

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 3

Metrics

推荐阅读 0

[1]	田俊峰, 杨乾宇, Jitian Xiao. 基于偏向稳定的分布式审计因果一致性模型[J]. 通信学报, 2023, 44(3): 164-177.
[2]	田俊峰, 张俊涛, 王彦骉. 具有可信约束的分布式存储因果一致性模型[J]. 通信学报, 2021, 42(6): 145-157.
[3]	田俊峰,王彦骉,何欣枫,张俊涛,杨万贺,庞亚南. 数据因果一致性研究综述[J]. 通信学报, 2020, 41(3): 154-167.