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

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.

Graphical abstract

Keywords

periodic replication / consistency maintenance / synchronization cost / synchronization strategy

Chenhao Zhang received the BS degree in Internet of Things engineering from China University of Petroleum, China in 2019. He is currently pursuing a PhD degree in computer science at Beihang University, China. His main research interests include distributed file systems, storage system, and high performance computing

Liang Wang received the BEng and MSc degrees in electronics engineering from Harbin Institute of Technology, China in 2011 and 2013, respectively, and the PhD degree in computer science and engineering from The University of Hong Kong, China in 2017. He is currently an assistant professor with the School of Computer Science and Engineering, Beihang University, China. He was a postdoctoral research fellow in the Institute of Microelectronics, Tsinghua University, China during 2017 and 2020. His research interests include power-efficient and reliability-aware design for network-on-chip and many-core system

Limin Xiao received the BS in computer science from Tsinghua University, China in 1993, the MS and PhD degree in computer science from the Institute of Computing, Chinese Academy of Sciences, China in 1996 and 1998, respectively. He is a professor of the School of Computer Science and Engineering, Beihang University, China. He is a senior membership of China Computer Federation. His main research areas are computer architecture, computer system software, high performance computing, virtualization and cloud computing

Shixuan Jiang received his BS degree in computer science and technology from Beihang University, China in 2020. He is currently pursuing a Master degree in computer science at Beihang University, China. His research interests include distributed file system, storage system

Meng Han received the BS degrees in Computer Science from the Beijing University of Posts and Telecommunications, China in 2019. He is currently working toward the PhD degree in Computer Architecture with the School of Computer Science and Engineering, Beihang University, China. His research interests include computer architecture and deep learning accelerator

Jinquan Wang received the BS in software engineering form Hunan University, China in 2021. He is currently pursuing a PhD degree in computer architecture at Beihang University, China. His main research interests include hybrid storage systems, distributed storage systems and scheduling system

Bing Wei received the BS in electrical engineering and MS degrees in computer science from Capital Normal University, China in 2012 and 2015, respectively, He is currently pursuing a PhD degree in computer science at Beihang University, China. His main research interests include file systems, high performance computing, software engineering, and clusters

Guangjun Qin received the MS degree in computer application technology in Zhengzhou University, China in 2006 and the PhD degree in computer architecture from Beihang University, China in 2015. From 2015 to 2017, he was a postdoctoral fellow at Beihang University, China. Since 2017, he has been a lecturer of the Smart City College, Beijing Union University, China. His main research areas are computer architecture, information security, bigdata analysis

References

[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] Corbett J C, Dean J, Epstein M, Fikes A, Frost C, Furman J J, Ghemawat S, Gubarev A, Heiser C, Hochschild P, Hsieh W, Kanthak S, Kogan E, Li H, Lloyd A, Melnik S, Mwaura D, Nagle D, Quinlan S, Rao R, Rolig L, Saito Y, Szymaniak M, Taylor C, Wang R, Woodford D . Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems, 2013, 31( 3): 8

[3] Khelaifa A, Benharzallah S, Kahloul L, Euler R, Laouid A, Bounceur A . A comparative analysis of adaptive consistency approaches in cloud storage. Journal of Parallel and Distributed Computing, 2019, 129: 36–49

[4] Tziritas N, Khan S U, Loukopoulos T, Lalis S, Xu C Z, Li K, Zomaya A Y . Online inter-datacenter service migrations. IEEE Transactions on Cloud Computing, 2020, 8( 4): 1054–1068

[5] Hong C Y, Kandula S, Mahajan R, Zhang M, Gill V, Nanduri M, Wattenhofer R. Achieving high utilization with software-driven WAN. In: Proceedings of ACM SIGCOMM 2013 Conference on SIGCOMM. 2013, 15–26

[6] Kandula S, Menache I, Schwartz R, Babbula S R. 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] Bailis P, Venkataraman S, Franklin M J, Hellerstein J M, Stoica I . Quantifying eventual consistency with PBS. Communications of the ACM, 2014, 57( 8): 93–102

[9] Kraska T, Hentschel M, Alonso G, Kossmann D . 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] Sharov A, Shraer A, Merchant A, Stokely M . Take me to your leader!: online optimization of distributed storage configurations. Proceedings of the VLDB Endowment, 2015, 8( 12): 1490–1501

[16] Shen H . IRM: integrated file replication and consistency maintenance in P2P systems. IEEE Transactions on Parallel and Distributed Systems, 2010, 21( 1): 100–113

[17] Bright L, Gal A, Raschid L . 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] Xu W, Wu W, Wu H, Cao J, Lin X . CACC: a cooperative approachto cache consistency in WMNs. IEEE Transactions on Computers, 2014, 63( 4): 860–873

[20] Bhide M, Deolasee P, Katkar A, Panchbudhe A, Ramamritham K, Shenoy P . 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] Yao X, Wang C L . Probabilistic consistency guarantee in partial quorum-based data store. IEEE Transactions on Parallel and Distributed Systems, 2020, 31( 8): 1815–1827

[23] Zhong J, Yates R D, Soljanin E. Minimizing content staleness in dynamo-style replicated storage systems. In: Proceedings of 2018 IEEE Conference on Computer Communications Workshops. 2018, 361–366

[24] Behrouzi-Far A, Soljanin E, Yates R D. Data freshness in leader-based replicated storage. In: Proceedings of 2020 IEEE International Symposium on Information Theory. 2020, 1806–1811

[25] Boyer E B, Broomfield M C, Perrotti T A. GlusterFS one storage server to rule them all. Los Alamos: Los Alamos National Laboratory, 2012

[26] Palankar M R, Iamnitchi A, Ripeanu M, Garfinkel S. 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] Carra D, Neglia G, Michiardi P . Elastic provisioning of cloud caches: a cost-aware TTL approach. IEEE/ACM Transactions on Networking, 2020, 28( 3): 1283–1296

[30] Feldmann A, Caceres R, Douglis F, Glass G, Rabinovich M. 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] Cate V. 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] Lu H, Veeraraghavan K, Ajoux P, Hunt J, Song Y J, Tobagus W, Kumar S, Lloyd W. Existential consistency: measuring and understanding consistency at facebook. In: Proceedings of the 25th Symposium on Operating Systems Principles. 2015, 295–310

[34] Huang C, Cahill M, Fekete A, Röhm U. 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] Rahman M R, Tseng L, Nguyen S, Gupta I, Vaidya N . Characterizing and adapting the consistency-latency tradeoff in distributed key-value stores. ACM Transactions on Autonomous and Adaptive Systems, 2017, 11( 4): 20

[36] Bermbach D, Tai S. Benchmarking eventual consistency: lessons learned from long-term experimental studies. In: Proceedings of 2014 IEEE International Conference on Cloud Engineering. 2014, 47–56

[37] Alabdulkarim Y, Almaymoni M, Ghandeharizadeh S . 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] Feng B, Wu C, Li J. MLC: an efficient multi-level log compression method for cloud backup systems. In: Proceedings of 2016 IEEE Trustcom/BigDataSE/ISPA. 2016, 1358–1365

[40] Wei J, Zhang G, Wang Y, Liu Z, Zhu Z, Chen J, Sun T, Zhou Q. 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] Bailis P, Venkataraman S, Franklin M J, Hellerstein J M, Stoica I . Probabilistically bounded staleness for practical partial quorums. Proceedings of the VLDB Endowment, 2012, 5( 8): 776–787

[42] Golab L, Johnson T, Shkapenyuk V . Scalable scheduling of updates in streaming data warehouses. IEEE Transactions on Knowledge and Data Engineering, 2012, 24( 6): 1092–1105

[43] Kaul S, Yates R, Gruteser M. Real-time status: how often should one update? In: Proceedings of 2012 Proceedings IEEE INFOCOM. 2012, 2731–2735

[44] Zhong J, Yates R D, Soljanin E. Two freshness metrics for local cache refresh. In: Proceedings of 2018 IEEE International Symposium on Information Theory. 2018, 1924–1928

[45] Cho J, Garcia-Molina H . 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] Zhou S, Mu S. 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] Eddelbuettel D. 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

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62272026 and 62104014), the fund of the State Key Laboratory of Software Development Environment (No. SKLSDE-2022ZX-07) and the Iluvatar CoreX semiconductor Co., Ltd.

RIGHTS & PERMISSIONS

2024 Higher Education Press