Survey on the causal consistency of data

Junfeng TIAN; Yanbiao WANG; Xinfeng HE; Juntao ZHANG; Wanhe YANG; Ya’nan PANG

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

您当前的位置：

首页 >

文章列表页 >

Survey on the causal consistency of data

Comprehensive Review | 更新时间：2024-06-05

- Survey on the causal consistency of data
- Journal on Communications Vol. 41, Issue 3, Pages: 154-167(2020)
- 作者机构：
  
  1. 河北大学网络空间安全与计算机学院，河北保定 071002
  2. 河北省高可信信息系统重点实验室，河北保定 071002
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(6180060654)
- DOI：10.11959/j.issn.1000-436x.2020055
  CLC： TP309
- Online First：2020-03，
  
  Published：25 March 2020
- 稿件说明：
移动端阅览
Junfeng TIAN, Yanbiao WANG, Xinfeng HE, et al. Survey on the causal consistency of data[J]. Journal on Communications, 2020, 41(3): 154-167.
DOI：

Junfeng TIAN, Yanbiao WANG, Xinfeng HE, et al. Survey on the causal consistency of data[J]. Journal on Communications, 2020, 41(3): 154-167. DOI： 10.11959/j.issn.1000-436x.2020055.

摘要

数据因果一致性是分布式存储中保障数据一致性的重要方案之一，目前的因果一致性方案研究重点包括时钟方法的优化、协议的设计以及操作事务序列的优化等方面。实际上云环境除了时钟漂移、查询放大等情况之外，还存在木马、不可信第三方等不安全因素，以致于破坏因果一致性元数据、用户操作结果的一致性，甚至影响存储环境的可用性。从一致性存储性能提升和安全保障角度出发，结合区块链等共识机制，对比分析了时钟同步方法、数据复制策略、服务端协议的分析设计以及操作事务序列化等研究方向，总结讨论了它们的的原理、优势、局限性以及安全约束方面的不同效用，进而指出未来的发展趋势和后续研究方向，期望对该领域的研究起到参考和帮助作用。

Abstract

Causal consistency is one of the important projects to ensure data consistency in distributed storage.The current research focuses on causal consistency including optimization of clock method

design of the protocol and the optimization of operation transaction sequence.In the actual cloud environment

in addition to clock skew and query amplification

there are also insecure factors such as Trojans and untrusted third parties

which will destroy the causal consistency metadata stored by users

and the consistency of user’s operating results

even affect the availability of the storage environment.From the perspective of performance improvement and security in distributed storage

the clock synchronization

data replications

analysis and design of server protocol

related research progress of the serialization of operational affairs were introduced combined with consensus mechanisms such as blockchain.At the same time

their principlest

advantages

limitations

and different utilities in terms of security constraints were discussed

and then the future development trends and follow-up research directions were point out at last

which would provide a reference and help for the research in this field.

关键词

Keywords

references

崔勇 , 宋健 , 缪葱葱 , 等 . 移动云计算研究进展与趋势 [J ] . 计算机学报 , 2017 , 40 ( 2 ): 273 - 295 .

CUI Y , SONG J , MIAO C C , et al . Mobile cloud computing research progress and trends [J ] . Chinese Journal of Computers , 2017 , 40 ( 2 ): 273 - 295 .

SPIROVSKA K , DIDONA D , ZWAENEPOEL W . Optimistic causal consistency for geo-replicated key-value stores [C ] // International Conference on Distributed Computing Systems . Piscataway:IEEE Press , 2017 : 2626 - 2629 .

BREWER E A , . Towards robust distributed systems [C ] // The Nineteenth Annual ACM Symposium on Principles of Distributed Computing . New York:ACM Press , 2000 : 477 - 502 .

张玉清 , 王晓菲 , 刘雪峰 , 等 . 云计算环境安全综述 [J ] . 软件学报 , 2016 , 27 ( 6 ): 1328 - 1348 .

ZHANG Y Q , WANG X F , LIU X F , et al . Survey on cloud computing security [J ] . Journal of Software , 2016 , 27 ( 6 ): 1328 - 1348 .

AGUILERA M , TERRY B . The many faces of consistency [J ] . Bulletin of the IEEE Computer Society Technical Committee on Data Engineering , 2016 , 39 ( 1 ): 3 - 13 .

BALEGAS V , LI C , NAJAFZADEH M , et al . Geo-replication:fast if possible,consistent if necessary [J ] . IEEE Data Engineering Bulletin,Special Issue on Data Consistency across Research Communities , 2016 , 39 ( 1 ):12.

BAILIS P , GHODSI A . Eventual consistency today:limitations,extensions,and beyond [J ] . Communications of the Association for Computing Machinery , 2013 , 56 ( 5 ): 55 - 63 .

LI M H , HAN D , DAVID G , et al . MICA:a holistic approach to fast in-memory key-value storage [C ] // Usenix Conference on Networked Systems Design ＆ Implementation . Berkeley:USENIX Association , 2014 : 429 - 444 .

王意洁 , 许方亮 , 裴晓强 . 分布式存储中的纠删码容错技术研究 [J ] . 计算机学报 , 2017 , 40 ( 1 ): 273 - 295 .

WANG Y J , XU F L , PEI X Q . Research on code-based fault-tolerant technology for distributed storage [J ] . Chinese Journal of Computers , 2017 , 40 ( 1 ): 273 - 295 .

AJOUX P , BRONSON N , KUMAR S , et al . Challenges to adopting stronger consistency at scale [C ] // Usenix Conference on Hot Topics in Operating Systems . Berkeley:USENIX Association , 2015 : 1 - 13 .

DU J Q , IORGULESCU C , ROY A , et al . Gentlerain:cheap and scalable causal consistency with physical clocks [C ] // The ACM Symposium on Cloud Computing . New York:ACM Press , 2014 : 1 - 13 .

DU J Q , ELNIKETY S , ZWAENEPOEL W . Clock-SI:snapshot isolation for partitioned data stores using loosely synchronized clocks [C ] // 2013 IEEE 32nd International Symposium on Reliable Distributed Systems . Piscataway:IEEE Press , 2013 : 173 - 184 .

TOMSIC A , CRAIN T , SHAPIRO M . PhysiCS-NMSI:efficient consistent snapshots for scalable snapshot isolation [C ] // The 2nd Workshop on Principles and Practice of Consistency for Distributed Data . New York:ACM Press , 2016 : 1 - 4 .

DU J Q , SCIASCIA D , ELNIKETY S , et al . Clock-RSM:low-latency inter-datacenter state machine replication using loosely synchronized physical clocks [C ] // The 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks . Piscataway:IEEE Press , 2014 : 343 - 354 .

LYU Y X , ZHANG W . A relevant casual relation based timestamp order consistency control method in DVE systems [C ] // IEEE 3rd Information Technology and Mechatronics Engineering Conference . Piscataway:IEEE Press , 2017 : 27 - 31 .

LAMPORT L . Time,clocks,and the orderingof events in a distributed system [J ] . Communications of the Association for Computing Machinery , 1978 , 21 ( 7 ): 558 - 565 .

KULKARNI S , DEMIRBAS M , MADAPPA D , et al . Logical physical clocks [C ] // International Conference on Principles of Distributed Systems . Berlin:Springer , 2014 : 17 - 32 .

ROOHITAVAF M , KULKARNI S . GentleRain+:making gentlerainrobust on clock anomalies [J ] . arXiv Preprint,abs/1612.05205 , 2016

ROOHITAVAF M , DEMIRBAS M , KULKARNI S . CausalSpartan:causal consistency for distributed data stores using hybrid logical clocks [C ] // Reliable Distributed Systems . Piscataway:IEEE Press , 2017 : 184 - 193 .

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

LIU S , BENSON T , REITER M . Efficient and safe network updates with suffix causal consistency [C ] // European Conference on Computer Systems . New York:ACM Press , 2019 : 1 - 15 .

ROOHITAVAF M , AHN J S , KANG W , et al . Session guarantees with raft and hybrid logical clocks [C ] // International Conference on Distributed Computing Systems . Piscataway:IEEE Press , 2019 : 100 - 109 .

ALMEIDA S , LEITAO J,LUÍS E T.et al . ChainReaction:a causal+consistent datastore based on chain replication [C ] // European Conference on Computer Systems . New York:ACM Press , 2013 : 85 - 98 .

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 .

张倩 . 分布式存储系统中用户数据一致性分析及研究 [D ] . 西安:西安工业大学 , 2015 .

ZHANG Q . Analysis and research of user data consistency in distributed storage system [D ] . Xi’an:Xi’an Technological University , 2015 .

VALTER B , NAJAFZADEH B , DUARTE M , et al . Putting the consis tency back into eventual consistency [C ] // European Conference on Computer Systems . New York:ACM Press , 2015 : 1 - 16 .

刘鑫伟 . 基于 Ceph 分布式存储系统副本一致性研究 [D ] . 武汉:华中科技大学 , 2016 .

LIU X W . Research on replica consistency based on ceph distributed storage system [D ] . Wuhan:Huazhong University of Science and Technology , 2016 .

LI C , PORTO D , CLEMENT A , et al . Making geo-replicated systems fast as possible,consistent when necessary [C ] // The 10th USENIX conference on Operating Systems Design and Implementation . New York:ACM Press , 2012 : 265 - 278 .

BAILIS P , FEKETE A , GHODSI A , et al . The potential dangers of causal consistency and an explicit solution [C ] // Proceedings of the Third ACM Symposium on Cloud Computing . New York:ACM Press , 2012 : 1 - 7 .

SHEN M , KSHEMKALYANI A D , HSU T Y . Causal consistency for geo-replicated cloud storage under partial replication [C ] // The 2015 IEEE International Parallel and Distributed Processing Symposium Workshop . Los Alamitos:IEEE Computer Society , 2015 : 509 - 518 .

HSU T Y , KSHEMKALYANI A D . Performance of approximate causal consistency for partially replicated systems [C ] // International Workshop on Adaptive Resource Management ＆ Scheduling for Cloud Computing . New York:ACM Press , 2016 .

HSU T Y , KSHEMKALYANI A D . Value the recent past:approximate causal consistency for partially replicated systems [J ] . IEEE Transactions on Parallel and Distributed Systems , 2018 , 29 ( 1 ): 212 - 225 .

CRAIN T , SHAPIRO M . Designing a causally consistent protocol for geo-distributed partial replication [C ] // European Conference on Computer Systems . New York:ACM Press , 2015 : 1 - 4 .

FORSTER K , MAHAJAN R , WATTENHOFER R . Consistent updates in software defined networks:On dependencies,loop freedom,and blackholes [C ] // 2016 IFIP Networking Conference and Workshops . Piscataway:IEEE Press , 2016 : 1 - 9 .

BRAVO M , RODRIGUES L . Saturn:a distributed metadata service for causal consistency [C ] // European Conference on Computer Systems . New York:ACM Press , 2017 : 111 - 126 .

MONIZ H , LEITAO J , DIAS R J , et al . Blotter:low latency transactions for geo-replicated storage [C ] // The 26th International Conference.International World Wide Web Conferences Steering Committee . New York:ACM Press , 2017 : 263 - 272 .

LI Z M , ROY P , ROMANO P . Exploiting speculation in partially replicated transactional data stores [C ] // Proceedings of the 2017 Symposium on Cloud Computing . New York:ACM Press , 2017 :640.

XIANG Z , VAIDYA N H . Global stabilization for causally consistent partial replication [J ] . avXiv Preprint,abs/1803.05575 , 2018

GUNAWARDHANA C , BRAVO M , RODRIGUES L . Unobtrusive deferred update stabilization for efficient geo-replication [C ] // USENIX Annual Technical Conference . Berkeley:USENIX Association , 2017 : 83 - 95 .

FOUTO P , LEITAO J , PREGUICA N . Practical and fast causal consistent partial geo-replication [C ] // 17th International Symposium on Network Computing and Applications . Piscataway:IEEE Press , 2018 : 1 - 10 .

TARIQ M , SHANKARANARAYANAN P N , SANJAY R , et al . Karma:cost-effective geo-replicated cloud storage with dynamic en forcement of causal consistency [J ] . IEEE Transactions on Cloud Computing , 2018 ( 99 ):1.

XIANG Z L , VAIDYA N . Brief announcement:partially replicated causally consistent shared memory [C ] // Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing . New York:ACM Press , 2018 : 273 - 275 .

KALAVADIA B , BHATIA T , PADIYA T , et al . Adaptive partitioning using partial replication for sensor data [C ] // International Conference on Distributed Computing and Internet Technology.Berlin:Springer, . 2019 : 260 - 269 .

贺海武 , 延安 , 陈泽华 . 基于区块链的智能合约技术与应用综述 [J ] . 计算机研究与发展 , 2018 , 55 ( 11 ): 2452 - 2466 .

HE H W , YAN A , CHEN Z H . Survey of smart contract technology and application based on blockchain [J ] . Journal of Computer Research and Development , 2018 , 55 ( 11 ): 2452 - 2466 .

韩璇 , 袁勇 , 王飞跃 . 区块链安全问题:研究现状与展望 [J ] . 自动化学报 , 2019 , 45 ( 1 ): 206 - 225 .

HAN X , YUAN Y , WANG F Y . Security problems on blockchain:the state of the art and future trends [J ] . Acta Automatica Sinica , 2019 , 45 ( 1 ): 206 - 225 .

EYAL I , GENCER A E , SIRER E G , et al . BitcoinNG:a scalable blockchain protocol [C ] // The 13th USENIX Conference on Networked Systems Design and Implementation . Berkeley:USENIX Association , 2016 : 45 - 59 .

WANG Y H , CAI S B , LIN C L , et al . Study of blockchains’s consensus mechanism based on credit [J ] . IEEE Access , 2019 ( 7 ): 1024 - 1023 .

高政风 , 郑继来 , 汤舒扬 , 等 . 基于DAG的分布式账本共识机制研究 [J ] . 软件学报 , 2020 , 31 ( 4 ): 1 - 20 .

GAO Z F , ZHENG J L , TANG S Y , et al . State-of-the-art survey of consensus mechanisms on DAG-based distributed ledger [J ] . Journal of Software , 2020 , 31 ( 4 ): 1 - 20 .

LLOYD W , FREEDMAN M , KAMINSKY M , et al . Don’t settle for eventual:Scalable causal consistency for wide-area storage with cops [C ] // The Twenty-Third ACM Symposium on Operating Systems Principles . New York:ACM Press , 2011 : 401 - 416 .

DU J Q , ELNIKETY S , ROY A , et al . Orbe:scalable causal consistency using dependency matrices and physical clocks [C ] // The 4th Annual Symposium on Cloud Computing . New York:ACM Press , 2013 : 1 - 14 .

ZAWIRSKI M , PREGUICA N M , DUARTE S , et al . Write fast,read in the past:causal consistency for client-side applications [C ] // Proceedings of the 16th Annual Middleware Conference . New York:ACM Press , 2015 : 75 - 87 .

ROOHITAVAF M , KULKARNI S . Toward adaptive causal consistency for replicated data stores [J ] . avXiv Preprint,abs/1803.08609 , 2018

DZIUMA D , FATOUROU P , KANELLOU E . Consistency for transactional memory computing [M ] . Berlin : Springer International PublishingPress , 2015 .

VIOTTI P , VUKOLIC M . Consistency in non-transactional distributed storage systems [J ] . ACM Computing Surveys , 2016 , 49 ( 1 ): 1 - 34 .

ANDREA C , BERNARDI G , GOTSMAN A . A framework for transactional consistency models with atomicvisibility [C ] // The 26th International Conference on Concurrency Theory . Berlin:Springer , 2015 : 58 - 71 .

ZHANG I , SHARMA N K , SZEKERES A D , et al . Building consistent transactions with inconsistent replication [J ] . ACM Transactions ,

AKKOORATH D D , TOMSIC A Z , BRAVO M , et al . Cure:strong semantics meets high availability and low latency [C ] // 36th International Conference on Distributed Computing Systems . Piscataway:IEEE Press , 2016 : 405 - 414 .

BAILIS P , FEKETE A , GHODSI A , et al . Scalable atomic visibility with RAMP transactions [J ] . ACM Transactions on Database Systems , 2016 , 41 ( 3 ): 1 - 45 .

LU H , HODSDON C , NGO K , et al . The SNOW theorem and latency-optimal read-only transactions [C ] // Usenix Conference on Operating Systems Design ＆ Implementation . Berkeley:USENIX Association , 2016 : 133 - 150 .

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

DIDONA D , GUERRAOUI R , WANG J J , et al . Causal consistency and latency optimality:friend or foe? [C ] // Proceedings of the VLDB Endowment . New York:ACM Press , 2018 : 1618 - 1632 .

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

Views

2240

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Distributed audit causal consistency model based on biased stability

Distributed storage causal consistency model with trusted constraint

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

Classification auditting scheme for privacy protection of outsourced EHR based on distributed storage

Query recovery attacks against conjunctive keyword searchable encryption

Related Author

Junfeng TIAN

Qianyu YANG

Xiao Jitian

Junfeng TIAN

Wanhe YANG

Ya’nan PANG

Juntao ZHANG

ZHANG Xiaoxu

Related Institution

School of Science, Edith Cowan University, Joondalup 7

College of Cyber Science, Nankai University

Tianjin Key Laboratory of Network and Data Security Technology

School of Cyber Science and Engineering, Wuhan University

School of Computer Science, Nanjing University of Posts and Telecommunications

AI问答

⁰