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

Junfeng TIAN; Wanhe YANG; Ya’nan PANG; Juntao ZHANG

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

您当前的位置：

首页 >

文章列表页 >

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

Papers | 更新时间：2024-06-05

- Causal consistency model for distributed data store based on shared graph and partial replication strategy
- Journal on Communications Vol. 41, Issue 5, Pages: 48-58(2020)
- 作者机构：
  
  1. 河北大学网络空间安全与计算机学院，河北保定 071002
  2. 河北省高可信信息系统重点实验室，河北保定 071002
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(6180060654)
- DOI：10.11959/j.issn.1000-436x.2020079
  CLC： TP393
- Online First：2020-05，
  
  Published：25 May 2020
- 稿件说明：
移动端阅览
Junfeng TIAN, Wanhe YANG, Ya’nan PANG, et al. Causal consistency model for distributed data store based on shared graph and partial replication strategy[J]. Journal on Communications, 2020, 41(5): 48-58.
DOI：

Junfeng TIAN, Wanhe YANG, Ya’nan PANG, et al. Causal consistency model for distributed data store based on shared graph and partial replication strategy[J]. Journal on Communications, 2020, 41(5): 48-58. DOI： 10.11959/j.issn.1000-436x.2020079.

摘要

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

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.

关键词

Keywords

references

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 .

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 .

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 .

朱涛 , 郭进伟 , 周欢 , 等 . 分布式数据库中一致性与可用性的关系 [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 .

AHAMAD M , NEIGER G , BURNSI J E , et al . Causal memory:definitions,implementation,and programming [J ] . Distributed Computing , 1995 , 9 ( 1 ): 37 - 49 .

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 .

BAILIS P , VENKATARAMAN S , MICHAEL J , et al . Quantifying eventual consistency with PBS [J ] . The VLDB Journal , 2014 , 23 ( 2 ): 279 - 302 .

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 .

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.

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 .

DIDONA D , SPIROVSKA K , ZWAENEPOEL W . Okapi:causally consistent geo-replication made faster,cheaper and more available [J ] . arXiv Preprint,arXiv:1702.04263 , 2017

ROOHITAVAF M , DEMIRBAS M , KULKARNI S S . CausalSpartanX:causal consistency and non-blocking read-only transactions [J ] . arXiv Preprint,arXiv:1812.07123 , 2018

SPIROVSKA K , DIDONA D , ZWAENEPOEL W . PaRiS:causally consistent transactions with non-blocking reads and partial replication [J ] . arXiv Preprint,arXiv:1902.09327 , 2019

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 .

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 .

XIANG Z L , VAIDYA N H . Global stabilization for causally consistent partial replication [J ] . arXiv Preprint,arXiv:1803.05575 , 2018

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 .

刘佩 , 蒋梓逸 , 曹袖 . 一种基于分布式存储系统中多节点修复的节点选择算法 [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 .

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 .

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

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 .

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 .

Views

1482

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Distributed audit causal consistency model based on biased stability

Survey on the causal consistency of data

Distributed storage causal consistency model with trusted constraint

Related Author

Junfeng TIAN

Qianyu YANG

Xiao Jitian

Junfeng TIAN

Yanbiao WANG

Xinfeng HE

Juntao ZHANG

Wanhe YANG

Related Institution

School of Science, Edith Cowan University, Joondalup 7

AI问答

⁰