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

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

Abstract

Abstract:

In the distributed storage, causal consistency is favored due to the best trade-off between ease of programming and performance.To address the problem of vector-dependent tracking loss of throughput in existing causal consistency results, a distributed audit causal consistency model based on biased stability was proposed.Combined vector timestamps were used instead of full vector timestamps in query operations to reduce system management and communication overhead.Meanwhile, the causal auditing was introduced with the help of distributed associative arrays, and data dependency was refined by partitioned cooperative auditing to reduce the number of false dependency entries.Theoretical analysis and simulation results show that proposed model improves throughput by 48.26% and reduces update response latency by 16.25%.

Key words: data consistency, causal consistency, distributed storage, bias stability, causal audit

CLC Number:

TN92

Junfeng TIAN, Qianyu YANG, Xiao Jitian. Distributed audit causal consistency model based on biased stability[J]. Journal on Communications, 2023, 44(3): 164-177.

Figures/Tables 14

符号	定义
N	分区数
M	每个分区副本数
$p_{n}^{m}$	第m个副本的第n个分区
$D D S_{c}$	客户端c的分布式依赖向量集
$S R V_{n}^{m}$	$p_{n}^{m}$ 的稳定远程向量
$S R V_{c}$	客户端c的稳定远程向量
${Clock}_{n}^{m}$	$p_{n}^{m}$ 的物理时钟
$S V V_{n}^{m}$	$p_{n}^{m}$ 的稳定版本向量
sr	源副本
dt	时间戳
dds	分布式依赖集
ds	依赖集
$B S V$	偏向稳定向量
D-mst	偏向时间戳

References 26

[1]	ALDIN H N S , DELDARI H , MOATTAR M H ,et al. Strict timed causal consistency as a hybrid consistency model in the cloud environment[J]. Future Generation Computer Systems, 2020,105(C): 259-274.
[2]	MOHAMED B S , AHMED B , CONSTANTIN E . Robustness against transactional causal consistency[J]. Logical Methods in Computer Science, 2021,17(1): 3-56.
[3]	AHAMAD M , NEIGER G , BURNS J E ,et al. Causal memory:definitions,implementation,and programming[J]. Distributed Computing, 1995,9(1): 37-49.
[4]	CADAMBE V , LYU S H . CausalEC:a causally consistent data storage algorithm based on cross-object erasure coding[J]. arXiv Preprint,arXiv:2102.13310, 2021
[5]	CAMILLERI C , VELLA J G , NEZVAL V . ThespisTRX causallyconsistent read transactions[J]. International Journal of Information Technology and Web Engineering, 2020,15(1): 1-16.
[6]	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: 1-14.
[7]	DIEGO D , RACHID G , WANG J J ,et al. Causal consistency and latency optimality:friend or foe?[J]. Proceedings of the VLDB Endowment, 2018,11(11): 1618-1632.
[8]	XIANG Z L , VAIDYA N H . Global stabilization for causally consistent partial replication[C]// Proceedings of the 21st International Conference on Distributed Computing and Networking. New York:ACM Press, 2020: 1-30.
[9]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . Optimistic causal consistency for geo-replicated key-value stores[C]// Proceedings of 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2017: 2626-2629.
[10]	LAMPORT L . Time,clocks,and the ordering of events in a distributed system[J]. Communications of the ACM, 1978,21(7): 558-565.
[11]	DU J Q , IORGULESCU C , ROY A ,et al. GentleRain:cheap and scalable causal consistency with physical clocks[C]// Proceedings of the ACM Symposium on Cloud Computing. New York:ACM Press, 2014: 1-13.
[12]	KULKARNI S S , DEMIRBAS M , MADAPPA D ,et al. Logical physical clocks[C]// International Conference on Principles of Distributed Systems. Berlin:Springer, 2014: 17-32.
[13]	ROOHITAVAF M , DEMIRBAS M , KULKARNI S . CausalSpartan:causal consistency for distributed data stores using hybrid logical clocks[C]// Proceedings of 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS). Piscataway:IEEE Press, 2017: 184-193.
[14]	GUNAWARDHANA C , BRAVO M , RODRIGUES L . Unobtrusive deferred update stabilization for efficient geo-replication[C]// Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference. New York:ACM Press, 2017: 83-95.
[15]	DZIUMA D , FATOUROU P , KANELLOU E . Consistency for transactional memory computing[C]// Transactional Memory.Foundations,Algorithms,Tools,and Applications. Berlin:Springer, 2015: 3-31.
[16]	ZHANG I , SHARMA N K , SZEKERES A ,et al. Building consistent transactions with inconsistent replication[C]// Proceedings of the 25th Symposium on Operating Systems Principles. New York:ACM Press, 2015: 263-278.
[17]	AKKOORATH D D , TOMSIC A Z , BRAVO M ,et al. Cure:strong semantics meets high availability and low latency[C]// Proceedings of 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2016: 405-414.
[18]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . Wren:nonblocking reads in a partitioned transactional causally consistent data store[C]// Proceedings of 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). Piscataway:IEEE Press, 2018: 1-12.
[19]	SPIROVSKA K , DIDONA D , ZWAENEPOEL W . PaRis:causally consistent transactions with non-blocking reads and partial replication[C]// Proceedings of 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2019: 304-316.
[20]	ROOHITAVAF M , DEMIRBAS M , KULKARNI S . CausalSpartanX:causal consistency and non-blocking read-only transactions[J]. arXiv Preprint,arXiv:1812.07123, 2018.
[21]	KAKWANI D , NASRE R . Orion:time estimated causally consistent key-value store[C]// Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data. New York:ACM Press, 2020:6.
[22]	LAMPORT . How to make a multiprocessor computer that correctly executes multiprocess programs[J]. IEEE Transactions on Computers, 1979,C-28(9): 690-691.
[23]	XIANG Z L , VAIDYA N H . Partially replicated causally consistent shared memory:lower bounds and an algorithm[C]// Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. New York:ACM Press, 2019: 425-434.
[24]	XIANG Z L , VAIDYA N H . 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.
[25]	ROOHITAVAF M , KULKARNI S . DKVF:a framework for rapid prototyping and evaluating distributed key-value stores[C]// Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering. New York:ACM Press, 2018: 912-915.
[26]	马文龙, 朱妤晴, 蒋德钧 ,等. Key-value 型 NoSQL 本地存储系统研究[J]. 计算机学报, 2018,41(8): 1722-1751.
	MA W L , ZHU Y Q , JIANG D J ,et al. A survey on local key-value store of NoSQL system[J]. Chinese Journal of Computers, 2018,41(8): 1722-1751.

Metrics

Recommended 0

No Suggested Reading articles found!

模型	一致性	死锁	时钟方法	时间戳	时延	依赖元数据
GentleRain	因果一致性	×	物理	标量	大	1
CausalSpartan	因果一致性	×	混合逻辑	矢量	较小	M
Cure	事务因果一致性	√	混合逻辑	矢量	较小	M
Wren	事务因果一致性	×	混合逻辑	标量	较大	2
PaRis	因果一致性	×	混合逻辑	标量	大	2
CausalSpartanX	因果一致性	×	混合逻辑	矢量	较小	M
Orion	因果一致性	×	混合逻辑	矢量	较小	M

数据中心位置	RTT/ms
保定	0.187
北京	15.308
上海	34.689
新加坡	83.936

Distributed audit causal consistency model based on biased stability

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 26

Related Articles 4

Metrics

Recommended 0

[1]	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.
[2]	Junfeng TIAN, Juntao ZHANG, Yanbiao WANG. Distributed storage causal consistency model with trusted constraint [J]. Journal on Communications, 2021, 42(6): 145-157.
[3]	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.
[4]	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.