数据因果一致性研究综述

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

Abstract

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.

Key words: data consistency, causal consistency, distributed storage, hybrid logical clock, cloud storage

CLC Number:

TP309

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.

Figures/Tables 3

References 62

[4]	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.
[5]	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.
[6]	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.
[7]	BAILIS P , GHODSI A . Eventual consistency today:limitations,extensions,and beyond[J]. Communications of the Association for Computing Machinery, 2013,56(5): 55-63.
[8]	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.
[9]	王意洁, 许方亮, 裴晓强 . 分布式存储中的纠删码容错技术研究[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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	KULKARNI S , DEMIRBAS M , MADAPPA D ,et al. Logical physical clocks[C]// International Conference on Principles of Distributed Systems. Berlin:Springer, 2014: 17-32.
[18]	ROOHITAVAF M , KULKARNI S . GentleRain+:making gentlerainrobust on clock anomalies[J]. arXiv Preprint,abs/1612.05205, 2016
[19]	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.
[20]	DIDONA D , SPIROVSKA K , ZWAENEPOEL W . Okapi:causally consistent geo-replication made faster,cheaper and more available[J]. arXiv Preprint,abs/1702.04263, 2017
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	张倩 . 分布式存储系统中用户数据一致性分析及研究[D]. 西安:西安工业大学, 2015.
	ZHANG Q . Analysis and research of user data consistency in distributed storage system[D]. Xi’an:Xi’an Technological University, 2015.
[26]	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.
[27]	刘鑫伟 . 基于 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.
[28]	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.
[1]	崔勇, 宋健, 缪葱葱 ,等. 移动云计算研究进展与趋势[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.
[29]	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.
[30]	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.
[2]	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.
[3]	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.
[31]	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.
[32]	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.
[33]	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.
[34]	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.
[35]	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.
[36]	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.
[37]	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.
[38]	XIANG Z , VAIDYA N H . Global stabilization for causally consistent partial replication[J]. avXiv Preprint,abs/1803.05575, 2018
[39]	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.
[40]	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.
[41]	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.
[42]	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.
[43]	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.
[44]	贺海武, 延安, 陈泽华 . 基于区块链的智能合约技术与应用综述[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.
[45]	韩璇, 袁勇, 王飞跃 . 区块链安全问题:研究现状与展望[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.
[46]	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.
[47]	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.
[48]	高政风, 郑继来, 汤舒扬 ,等. 基于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.
[49]	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.
[50]	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.
[51]	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.
[52]	ROOHITAVAF M , KULKARNI S . Toward adaptive causal consistency for replicated data stores[J]. avXiv Preprint,abs/1803.08609, 2018
[53]	DZIUMA D , FATOUROU P , KANELLOU E . Consistency for transactional memory computing[M]. Berlin: Springer International PublishingPress, 2015.
[54]	VIOTTI P , VUKOLIC M . Consistency in non-transactional distributed storage systems[J]. ACM Computing Surveys, 2016,49(1): 1-34.
[55]	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.
[56]	ZHANG I , SHARMA N K , SZEKERES A D ,et al. Building consistent transactions with inconsistent replication[J]. ACM Transactions,
[57]	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.
[58]	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.
[59]	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.
[60]	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.
[61]	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.
[4]	张玉清, 王晓菲, 刘雪峰 ,等. 云计算环境安全综述[J]. 软件学报, 2016,27(6): 1328-1348.
[62]	ROOHITAVAF M , DEMIRBAS M , KULKARNI S . CausalSpartanX:causal consistency and non-blocking read-only transactions[J]. avXiv Preprint,abs/1812.07123, 2018

Metrics

Recommended 0

No Suggested Reading articles found!

Survey on the causal consistency of data

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 62

Related Articles 15

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]	Guanxiong HA, Qiaowen JIA, Hang CHEN, Chunfu JIA. Data popularity-based encrypted deduplication scheme without third-party servers [J]. Journal on Communications, 2022, 43(8): 17-29.
[3]	Guangjun LIU, Wangmei GUO, Jinbo XIONG, Ximeng LIU, Changyu DONG. Lightweight privacy protection data auditing scheme for regenerating-coding-based distributed storage [J]. Journal on Communications, 2021, 42(7): 220-230.
[4]	Junfeng TIAN, Juntao ZHANG, Yanbiao WANG. Distributed storage causal consistency model with trusted constraint [J]. Journal on Communications, 2021, 42(6): 145-157.
[5]	Tao FENG, Fanqi KONG, Chunyan LIU, Rong MA, Albettar Maher. Dual verifiable cloud storage scheme based on blockchain [J]. Journal on Communications, 2021, 42(12): 192-201.
[6]	Chunfu JIA, Guanxiong HA, Shaoqiang WU, Hang CHEN, Ruiqi LI. AONT-and-NTRU-based rekeying scheme for encrypted deduplication [J]. Journal on Communications, 2021, 42(10): 67-80.
[7]	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]	Wenlong KE,Yong WANG,Miao YE,Junqi CHEN. Priority differentiated multicast flow scheduling method in Ceph cloud storage network [J]. Journal on Communications, 2020, 41(11): 40-51.
[9]	Lei SUN,Zhiyuan ZHAO,Jianhua WANG,Zhiqiang ZHU. Attribute-based encryption scheme supporting attribute revocation in cloud storage environment [J]. Journal on Communications, 2019, 40(5): 47-56.
[10]	Xiangsong ZHANG,Chen LI,Zhenhua LIU. Key-exposure resilient integrity auditing scheme with encrypted data deduplication [J]. Journal on Communications, 2019, 40(4): 95-106.
[11]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[12]	Junfeng TIAN,Mengjia CHAI,Liuling QI. Provable data possession scheme based on public verification and private verification [J]. Journal on Communications, 2019, 40(3): 48-59.
[13]	Ruizhong DU,Pengliang SHI,Xinfeng HE. Cloud data assured deletion scheme based on overwrite verification [J]. Journal on Communications, 2019, 40(1): 130-140.
[14]	Xincheng YAN,Yue CHEN,Hongyong JIA,Yanru CHEN,Xinyue ZHANG. Secure data sharing scheme supporting efficient synchronous evolution for ciphertext and key [J]. Journal on Communications, 2018, 39(5): 123-133.
[15]	Yue CHEN,Longjiang WANG,Xincheng YAN,Xinyue ZHANG. Mimic storage scheme based on regenerated code [J]. Journal on Communications, 2018, 39(4): 21-34.