Minimizing the cost of periodically replicated systems via model and quantitative analysis

doi:10.1007/s11704-023-2625-8

Frontiers of Computer Science

2024, Vol. 18

Issue (5): 185206 https://doi.org/10.1007/s11704-023-2625-8

本期目录

Minimizing the cost of periodically replicated systems via model and quantitative analysis

Chenhao ZHANG^1,², Liang WANG^1,²(

), Limin XIAO^1,²(

), Shixuan JIANG^1,², Meng HAN^1,², Jinquan WANG^1,², Bing WEI³, Guangjun QIN⁴

¹. State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
². School of Computer Science and Engineering, Beihang University, Beijing 100191, China
³. School of Cyberspace Security, Hainan University, Haikou 570228, China
⁴. Smart City College, Beijing Union University, Beijing 100101, China

全文: PDF(11214 KB) HTML

Abstract：

Geographically replicating objects across multiple data centers improves the performance and reliability of cloud storage systems. Maintaining consistent replicas comes with high synchronization costs, as it faces more expensive WAN transport prices and increased latency. Periodic replication is the widely used technique to reduce the synchronization costs. Periodic replication strategies in existing cloud storage systems are too static to handle traffic changes, which indicates that they are inflexible in the face of unforeseen loads, resulting in additional synchronization cost. We propose quantitative analysis models to quantify consistency and synchronization cost for periodically replicated systems, and derive the optimal synchronization period to achieve the best tradeoff between consistency and synchronization cost. Based on this, we propose a dynamic periodic synchronization method, Sync-Opt, which allows systems to set the optimal synchronization period according to the variable load in clouds to minimize the synchronization cost. Simulation results demonstrate the effectiveness of our models. Compared with the policies widely used in modern cloud storage systems, the Sync-Opt strategy significantly reduces the synchronization cost.

Key words： periodic replication consistency maintenance synchronization cost synchronization strategy

收稿日期: 2022-10-14 出版日期: 2023-07-10

Corresponding Author(s): Liang WANG,Limin XIAO

引用本文:

. [J]. Frontiers of Computer Science, 2024, 18(5): 185206.
Chenhao ZHANG, Liang WANG, Limin XIAO, Shixuan JIANG, Meng HAN, Jinquan WANG, Bing WEI, Guangjun QIN. Minimizing the cost of periodically replicated systems via model and quantitative analysis. Front. Comput. Sci., 2024, 18(5): 185206.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-023-2625-8
https://academic.hep.com.cn/fcs/CN/Y2024/V18/I5/185206

Fig.1

Parameters	Description
$n$	The number of follower nodes
i	The ordinal number of follower nodes
$λ$	Update rate of the data item
y	The ordinal number of data items
$θ$	Synchronization period between the leader and followers
$j$	Synchronization period number between the leader and followers
$P$	The time the leader starts transferring data each time
$R$	The write latency from the leader to followers
$W$	The time at which the leader node received the update request
$A$	The time the follower receives synchronization data each time
$Γ a$	Staleness cost
$Γ t$	Communication cost
$Γ s$	Storage cost
$S$	The staleness cost per unit time
$C$	The storage cost of storing one data item per unit time
$D 1$	The communication cost each time
$D 2$	The cost of transporting one data item by the network each time
$T$	Total synchronization time

Tab.1

Fig.2

Fig.3

Tab.2

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

1	Calder B, Wang J, Ogus A, Nilakantan N, Skjolsvold A, McKelvie S, Xu Y, Srivastav S, Wu J, Simitci H, Haridas J, Uddaraju C, Khatri H, Edwards A, Bedekar V, Mainali S, Abbasi R, Agarwal A, ul Haq M F, ul Haq M I, Bhardwaj D, Dayanand S, Adusumilli A, McNett M, Sankaran S, Manivannan K, Rigas L. Windows azure storage: a highly available cloud storage service with strong consistency. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. 2011, 143–157
2	J C, Corbett J, Dean M, Epstein A, Fikes C, Frost J J, Furman S, Ghemawat A, Gubarev C, Heiser P, Hochschild W, Hsieh S, Kanthak E, Kogan H, Li A, Lloyd S, Melnik D, Mwaura D, Nagle S, Quinlan R, Rao L, Rolig Y, Saito M, Szymaniak C, Taylor R, Wang D Woodford . Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems, 2013, 31( 3): 8
3	A, Khelaifa S, Benharzallah L, Kahloul R, Euler A, Laouid A Bounceur . A comparative analysis of adaptive consistency approaches in cloud storage. Journal of Parallel and Distributed Computing, 2019, 129: 36–49
4	N, Tziritas S U, Khan T, Loukopoulos S, Lalis C Z, Xu K, Li A Y Zomaya . Online inter-datacenter service migrations. IEEE Transactions on Cloud Computing, 2020, 8( 4): 1054–1068
5	C Y, Hong S, Kandula R, Mahajan M, Zhang V, Gill M, Nanduri R Wattenhofer . Achieving high utilization with software-driven WAN. In: Proceedings of ACM SIGCOMM 2013 Conference on SIGCOMM. 2013, 15–26
6	S, Kandula I, Menache R, Schwartz S R Babbula . Calendaring for wide area networks. In: Proceedings of 2014 ACM conference on SIGCOMM. 2014, 515–526
7	Chihoub H E, Ibrahim S, Antoniu G, Pérez M S. Consistency in the cloud: when money does matter! In: Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing. 2013, 352–359
8	P, Bailis S, Venkataraman M J, Franklin J M, Hellerstein I Stoica . Quantifying eventual consistency with PBS. Communications of the ACM, 2014, 57( 8): 93–102
9	T, Kraska M, Hentschel G, Alonso D Kossmann . Consistency rationing in the cloud: pay only when it matters. Proceedings of the VLDB Endowment, 2009, 2( 1): 253–264
10	Huang C, Cahill M, Fekete A, Rohm U. Deciding when to trade data freshness for performance in mongoDB-as-a-service. In: Proceedings of the 36th IEEE International Conference on Data Engineering. 2020, 1934–1937
11	Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler. The hadoop distributed file system. In: Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies (MSST), 2010, 1-10
12	Piernas J, Nieplocha J, Felix E J. Evaluation of active storage strategies for the lustre parallel file system. In: Proceedings of 2007 ACM/IEEE conference on Supercomputing. 2007, 1-10
13	Meteor Development Group. Meteor. See meteor.com website, 2023
14	Terry D B, Prabhakaran V, Kotla R, Balakrishnan M, Aguilera M K, Abu-Libdeh H. Consistency-based service level agreements for cloud storage. In: Proceedings of the 24th ACM Symposium on Operating Systems Principles. 2013, 309–324
15	A, Sharov A, Shraer A, Merchant M Stokely . Take me to your leader!: online optimization of distributed storage configurations. Proceedings of the VLDB Endowment, 2015, 8( 12): 1490–1501
16	H Shen . IRM: integrated file replication and consistency maintenance in P2P systems. IEEE Transactions on Parallel and Distributed Systems, 2010, 21( 1): 100–113
17	L, Bright A, Gal L Raschid . Adaptive pull-based policies for wide area data delivery. ACM Transactions on Database Systems, 2006, 31( 2): 631–671
18	Gao W, Cao G, Srivatsa M, Iyengar A. Distributed maintenance of cache freshness in opportunistic mobile networks. In: Proceedings of the 32nd IEEE International Conference on Distributed Computing Systems. 2012, 132–141
19	W, Xu W, Wu H, Wu J, Cao X Lin . CACC: a cooperative approachto cache consistency in WMNs. IEEE Transactions on Computers, 2014, 63( 4): 860–873
20	M, Bhide P, Deolasee A, Katkar A, Panchbudhe K, Ramamritham P Shenoy . Adaptive push-pull: disseminating dynamic web data. IEEE Transactions on Computers, 2002, 51( 6): 652–668
21	Wang X, Yang S, Wang S, Niu X, Xu J. An application-based adaptive replica consistency for cloud storage. In: Proceedings of the 9th International Conference on Grid and Cloud Computing. 2010, 13–17
22	X, Yao C L Wang . Probabilistic consistency guarantee in partial quorum-based data store. IEEE Transactions on Parallel and Distributed Systems, 2020, 31( 8): 1815–1827
23	J, Zhong R D, Yates E Soljanin . Minimizing content staleness in dynamo-style replicated storage systems. In: Proceedings of 2018 IEEE Conference on Computer Communications Workshops. 2018, 361–366
24	A, Behrouzi-Far E, Soljanin R D Yates . Data freshness in leader-based replicated storage. In: Proceedings of 2020 IEEE International Symposium on Information Theory. 2020, 1806–1811
25	E B, Boyer M C, Broomfield T A Perrotti . GlusterFS one storage server to rule them all. Los Alamos: Los Alamos National Laboratory, 2012
26	M R, Palankar A, Iamnitchi M, Ripeanu S Garfinkel . Amazon S3 for science grids: a viable solution? In: Proceedings of 2008 International Workshop on Data-Aware Distributed Computing. 2008, 55–64
27	Zach Hill, Jie Li, Ming Mao, Arkaitz Ruiz-Alvarez, and Marty Humphrey. Early observations on the performance of windows azure. In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. 2010, 367–376
28	Houssem-Eddine Chihoub, Shadi Ibrahim, Gabriel Antoniu, María Pérez. Consistency in the Cloud: When Money Does Matter!. Research Report, Inria, 2012
29	D, Carra G, Neglia P Michiardi . Elastic provisioning of cloud caches: a cost-aware TTL approach. IEEE/ACM Transactions on Networking, 2020, 28( 3): 1283–1296
30	A, Feldmann R, Caceres F, Douglis G, Glass M Rabinovich . Performance of web proxy caching in heterogeneous bandwidth environments. In: Proceedings of IEEE INFOCOM '99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now. 1999, 107–116
31	V Cate . Alex-a global filesystem. In: Proceedings of 1992 USENIX File System Workshop. 1992, 1–12
32	Wada H, Fekete A D, Zhao L, Lee K, Liu A. Data consistency properties and the trade-offs in commercial cloud storage: the consumers’ perspective. In: Proceedings of the 5th Biennial Conference on Innovative Data Systems Research. 2011, 134–143
33	H, Lu K, Veeraraghavan P, Ajoux J, Hunt Y J, Song W, Tobagus S, Kumar W Lloyd . Existential consistency: measuring and understanding consistency at facebook. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 295–310
34	C, Huang M, Cahill A, Fekete U Röhm . Data consistency properties of document store as a service (DSaaS): using MongoDB atlas as an example. In: Proceedings of the 10th Technology Conference on Performance Evaluation and Benchmarking. 2019, 126–139
35	M R, Rahman L, Tseng S, Nguyen I, Gupta N Vaidya . Characterizing and adapting the consistency-latency tradeoff in distributed key-value stores. ACM Transactions on Autonomous and Adaptive Systems, 2017, 11( 4): 20
36	D, Bermbach S Tai . Benchmarking eventual consistency: lessons learned from long-term experimental studies. In: Proceedings of 2014 IEEE International Conference on Cloud Engineering. 2014, 47–56
37	Y, Alabdulkarim M, Almaymoni S Ghandeharizadeh . Polygraph: a plug-n-play framework to quantify application anomalies. IEEE Transactions on Knowledge and Data Engineering, 2021, 33( 3): 1140–1155
38	Golab W, Rahman M R, Auyoung A, Keeton K, Gupta I. Client-centric benchmarking of eventual consistency for cloud storage systems. In: Proceedings of the 34th IEEE International Conference on Distributed Computing Systems. 2014, 493–502
39	B, Feng C, Wu J Li . MLC: an efficient multi-level log compression method for cloud backup systems. In: Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA. 2016, 1358–1365
40	J, Wei G, Zhang Y, Wang Z, Liu Z, Zhu J, Chen T, Sun Q Zhou . On the feasibility of parser-based log compression in large-scale cloud systems. In: Proceedings of the 19th USENIX Conference on File and Storage Technologies. 2021, 249–262
41	P, Bailis S, Venkataraman M J, Franklin J M, Hellerstein I Stoica . Probabilistically bounded staleness for practical partial quorums. Proceedings of the VLDB Endowment, 2012, 5( 8): 776–787
42	L, Golab T, Johnson V Shkapenyuk . Scalable scheduling of updates in streaming data warehouses. IEEE Transactions on Knowledge and Data Engineering, 2012, 24( 6): 1092–1105
43	S, Kaul R, Yates M Gruteser . Real-time status: how often should one update? In: Proceedings of 2012 Proceedings IEEE INFOCOM. 2012, 2731–2735
44	J, Zhong R D, Yates E Soljanin . Two freshness metrics for local cache refresh. In: Proceedings of 2018 IEEE International Symposium on Information Theory. 2018, 1924–1928
45	J, Cho H Garcia-Molina . Synchronizing a database to improve freshness. ACM SIGMOD Record, 2000, 29( 2): 117–128
46	Pitchumani R, Frank S, Miller E L. Realistic request arrival generation in storage benchmarks. In: Proceedings of the 31st Symposium on Mass Storage Systems and Technologies. 2015, 1–10
47	S, Zhou S Mu . Fault-tolerant replication with pull-based consensus in mongoDB. In: Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation. 2021, 687–703
48	Tobbicke R. Distributed file systems: focus on Andrew file system/distributed file service (AFS/DFS). In: Proceedings of the 30th IEEE Symposium on Mass Storage Systems. Toward Distributed Storage and Data Management Systems. 1994, 23–26
49	D Eddelbuettel . A brief introduction to redis. 2022, arXiv preprint arXiv: 2203.06559
50	Michael Stonebraker. Sql databases v. nosql databases. Communications of the ACM, 2010, 53(4):10–11
51	Aliyun. Aliyun server esc price, 2023. Price/product\#/ecs/detail/vm, accessed: 2023-5-27
52	Aliyun. Aliyun server OSS price, 2023. Price/detail/oss, accessed: 2023-5-27
53	MongoDB. MongoDB, 2023. Docs/manual/core/replica-set-sync/, accessed: 2023-5-27
54	Windows Azure. Azure cache for redis, 2023. Microsoft.com/zh-cn/pricing/, accessed: 2023-5-27

[1]

FCS-22625-OF-CZ_suppl_1

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed