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

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

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

CLC Number:

TP393

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.

Figures/Tables 8

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 22

Related Articles 3

Metrics

Recommended 0

[1]	Junfeng TIAN, Qianyu YANG, Xiao Jitian. Distributed audit causal consistency model based on biased stability [J]. Journal on Communications, 2023, 44(3): 164-177.
[2]	Junfeng TIAN, Juntao ZHANG, Yanbiao WANG. Distributed storage causal consistency model with trusted constraint [J]. Journal on Communications, 2021, 42(6): 145-157.
[3]	Junfeng TIAN,Yanbiao WANG,Xinfeng HE,Juntao ZHANG,Wanhe YANG,Ya’nan PANG. Survey on the causal consistency of data [J]. Journal on Communications, 2020, 41(3): 154-167.