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

田俊峰; 杨万贺; 庞亚南; 张俊涛

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于共享图和部分复制策略的分布式存储因果一致性模型
- Causal consistency model for distributed data store based on shared graph and partial replication strategy
- 通信学报 2020年41卷第5期页码：48-58
- 作者机构：
  
  1. 河北大学网络空间安全与计算机学院，河北保定 071002
  2. 河北省高可信信息系统重点实验室，河北保定 071002
- 作者简介：
  
  [ "田俊峰（1965- ），男，河北保定人，博士，河北大学教授、博士生导师，主要研究方向为信息安全与分布式计算" ]
  [ "杨万贺（1996- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性" ]
  [ "庞亚南（1995- ），女，河北衡水人，河北大学硕士生，主要研究方向为信息安全、数据一致性" ]
  [ "张俊涛（1995- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性" ]
- 基金信息：
  
  国家自然科学基金资助项目(6180060654)
- DOI：10.11959/j.issn.1000-436x.2020079
  中图分类号： TP393
- 网络出版日期：2020-05，
  
  纸质出版日期：2020-05-25
- 稿件说明：
移动端阅览
田俊峰, 杨万贺, 庞亚南, 等. 基于共享图和部分复制策略的分布式存储因果一致性模型[J]. 通信学报, 2020,41(5):48-58.

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.
田俊峰, 杨万贺, 庞亚南, 等. 基于共享图和部分复制策略的分布式存储因果一致性模型[J]. 通信学报, 2020,41(5):48-58. DOI： 10.11959/j.issn.1000-436x.2020079.

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 .

浏览量

603

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于偏向稳定的分布式审计因果一致性模型

数据因果一致性研究综述

具有可信约束的分布式存储因果一致性模型