数据因果一致性研究综述

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

通信学报 ›› 2020, Vol. 41 ›› Issue (3): 154-167.doi: 10.11959/j.issn.1000-436x.2020055

数据因果一致性研究综述

田俊峰^1,²,王彦骉^1,²,何欣枫^1,²,张俊涛^1,²,杨万贺^1,²,庞亚南^1,²

¹ 河北大学网络空间安全与计算机学院，河北保定 071002
² 河北省高可信信息系统重点实验室，河北保定 071002

修回日期:2020-02-29 出版日期:2020-03-25 发布日期:2020-03-31
作者简介:田俊峰（1965- ），男，河北保定人，博士，河北大学教授、博士生导师，主要研究方向为信息安全与分布式计算|王彦骉（1994- ），男，河北邢台人，河北大学硕士生，主要研究方向为信息安全与数据一致性|何欣枫（1976- ），男，河北保定人，河北大学副教授，主要研究方向为云计算、可信计算|张俊涛（1995- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性|杨万贺（1996- ），男，河北保定人，河北大学硕士生，主要研究方向为信息安全、数据一致性|庞亚南（1995- ），女，河北衡水人，河北大学硕士生，主要研究方向为信息安全、数据一致性
基金资助:
国家自然科学基金资助项目(6180060654)

Survey on the causal consistency of data

Junfeng TIAN^1,²,Yanbiao WANG^1,²,Xinfeng HE^1,²,Juntao ZHANG^1,²,Wanhe YANG^1,²,Ya’nan PANG^1,²

¹ School of Cyber Security and Computer,Hebei University,Baoding 071002,China
² Key Laboratory on High Trusted Information System in Hebei Province,Baoding 071002,China

Revised:2020-02-29 Online:2020-03-25 Published:2020-03-31
Supported by:
The National Natural Science Foundation of China(6180060654)

摘要/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

中图分类号:

TP309

田俊峰,王彦骉,何欣枫,张俊涛,杨万贺,庞亚南. 数据因果一致性研究综述[J]. 通信学报, 2020, 41(3): 154-167.

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.

图/表 3

参考文献 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

数据因果一致性研究综述

Survey on the causal consistency of data

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 62

相关文章 15

Metrics

推荐阅读 0

[1]	田俊峰, 杨乾宇, Jitian Xiao. 基于偏向稳定的分布式审计因果一致性模型[J]. 通信学报, 2023, 44(3): 164-177.
[2]	哈冠雄, 贾巧雯, 陈杭, 贾春福. 无第三方服务器的基于数据流行度的加密去重方案[J]. 通信学报, 2022, 43(8): 17-29.
[3]	刘光军, 郭网媚, 熊金波, 刘西蒙, 董长宇. 适用于再生编码分布式存储的轻量型隐私保护审计方案[J]. 通信学报, 2021, 42(7): 220-230.
[4]	田俊峰, 张俊涛, 王彦骉. 具有可信约束的分布式存储因果一致性模型[J]. 通信学报, 2021, 42(6): 145-157.
[5]	冯涛, 孔繁琪, 柳春岩, 马蓉, Maher Albettar. 基于区块链的双重可验证云存储方案[J]. 通信学报, 2021, 42(12): 192-201.
[6]	贾春福, 哈冠雄, 武少强, 陈杭, 李瑞琪. 加密去重场景下基于AONT和NTRU的密钥更新方案[J]. 通信学报, 2021, 42(10): 67-80.
[7]	田俊峰,杨万贺,庞亚南,张俊涛. 基于共享图和部分复制策略的分布式存储因果一致性模型[J]. 通信学报, 2020, 41(5): 48-58.
[8]	柯文龙,王勇,叶苗,陈俊奇. Ceph云存储网络中一种业务优先级区分的多播流调度方法[J]. 通信学报, 2020, 41(11): 40-51.
[9]	孙磊,赵志远,王建华,朱智强. 云存储环境下支持属性撤销的属性基加密方案[J]. 通信学报, 2019, 40(5): 47-56.
[10]	张襄松,李晨,刘振华. 抗密钥泄露的支持密态数据去重的完整性审计方案[J]. 通信学报, 2019, 40(4): 95-106.
[11]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[12]	田俊峰,柴梦佳,齐鎏岭. 基于公有验证和私有验证的数据持有性验证方案[J]. 通信学报, 2019, 40(3): 48-59.
[13]	杜瑞忠,石朋亮,何欣枫. 基于覆写验证的云数据确定性删除方案[J]. 通信学报, 2019, 40(1): 130-140.
[14]	严新成,陈越,贾洪勇,陈彦如,张馨月. 支持高效密文密钥同步演化的安全数据共享方案[J]. 通信学报, 2018, 39(5): 123-133.
[15]	陈越,王龙江,严新成,张馨月. 基于再生码的拟态数据存储方案[J]. 通信学报, 2018, 39(4): 21-34.