RADIOELECTRONIC AND COMPUTER SYSTEMS

Distributed replicated databases play a crucial role in modern computer systems enabling scalable, fault-tolerant, and high-performance data management. However, achieving these qualities requires resolving a number of trade-offs between various properties during system design and operation. This paper reviews trade-offs in distributed replicated databases and provides a survey of recent research papers studying distributed data storage. The paper first discusses a compromise between consistency and latency that appears in distributed replicated data storages and directly follows from CAP and PACELC theorems. Consistency refers to the guarantee that all clients in a distributed system observe the same data at the same time. To ensure strong consistency, distributed systems typically employ coordination mechanisms and synchronization protocols that involve communication and agreement among distributed replicas. These mechanisms introduce additional overhead and latency and can dramatically increase the time taken to complete operations when replicas are globally distributed across the Internet. In addition, we study trade-offs between other system properties including availability, durability, cost, energy consumption, read and write latency, etc. In this paper we also provide a comprehensive review and classification of recent research works in distributed replicated databases. Reviewed papers showcase several major areas of research, ranging from performance evaluation and comparison of various NoSQL databases to suggest new strategies for data replication and putting forward new consistency models. In particular, we observed a shift towards exploring hybrid consistency models of causal consistency and eventual consistency with causal ordering due to their ability to strike a balance between operations ordering guarantees and high performance. Researchers have also proposed various consistency control algorithms and consensus quorum protocols to coordinate distributed replicas. Insights from this review can empower practitioners to make informed decisions in designing and managing distributed data storage systems as well as help identify existing gaps in the body of knowledge and suggest further research directions.

distributed databases; Big Data, NoSQL; replication; consistency; latency; throughput; availability; trade-offs; CAP; PACELC; review

Ormandjieva, O., Omidbakhsh, M. & Trudel, S. Measuring the 3V's of Big Data: A Rigorous Approach. Int. Workshop on Software Measurement (IWSM) and Conference on Software Process and Product Measurement (IWSM-MENSURA), 2020. Available at: www.iwsm-mensura.org/wp-content/uploads/2020/10/paper5.pdf (accessed Jan. 17, 2023).

Brewer, E. Towards Robust Distributed Systems. ACM Symposium on Principles of Distributed Computing, 2000. DOI: 10.1145/343477.343502.

Gilbert, S. & Lynch, N. Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 2002, vol. 33, no. 2, pp. 51-59. DOI: 10.1145/564585.564601

Abadi, D. Consistency Tradeoffs in Modern Distributed Database System Design. IEEE Computer, 2012, vol. 45, no. 2, pp. 37-42. DOI: 10.1109/MC.2012.33

Gorbenko, A. & Romanovsky, A. Time-outing Internet Services. IEEE Security & Privacy, 2013, vol. 11, no. 2, pp. 68-71. DOI: 10.1109/MSP.2013.43

Gorbenko, A., Romanovsky, A. & Tarasyuk, O. Fault tolerant internet computing: Benchmarking and modelling trade-offs between availability, latency and consistency. J. Netw. Comput. Appl., 2019, vol. 146, p. 102412. DOI: 10.1016/j.jnca.2019.102412.

Alagappan, R., Ganesan, A., Patel, Y., Pillai, T. S., Arpaci-Dusseau A. C. & Arpaci-Dusseau, R. H. Correlated Crash Vulnerabilities. USENIX Symposium on Operating Systems Design and Implementation, 2016. Available at: www.usenix.org/system/files/conference/osdi16/osdi16-alagappan.pdf (accessed Jan. 17, 2023).

Abbas, Q., Shafiq, H., Ahmad, I. & Tharanidharan, S. Concurrency control in distributed database system. Int. Conf. on Computer Communication and Informatics (ICCCI), 2016, pp. 1–4. DOI: 10.1109/ICCCI.2016.7479987.

S. Kalid, S., Syed, A., Mohammad, A. & Halgamuge M. N. Big-data NoSQL databases: A comparison and analysis of Big-Table, DynamoDB, and Cassandra. IEEE 2nd Int. Conf. on Big Data Analysis (ICBDA), 2017, pp. 89–93. DOI: 10.1109/ICBDA.2017.8078782.

Anusha, K., Rajesh, N., Kavitha, M. & Ravinder, N. Comparative Study of MongoDB vs Cassandra in big data analytics. 5th Int. Conf. on Computing Methodologies and Communication (ICCMC), 2021, pp. 1831–1835. DOI: 10.1109/ICCMC51019.2021.9418441.

Sandhu, A. K., Big Data with Cloud Computing: Discussions and Challenges. Big Data Mining and Analytics, 2022, vol. 5, iss. 1, pp. 32-40. DOI: 10.26599/BDMA.2021.9020016

Pramukantoro, E. S., Kartikasari, D. P. & Siregar, R. A. Performance Evaluation of MongoDB, Cassandra, and HBase for Heterogenous IoT Data Storage. Int. Conf. on Applied Information Technology and Innovation (ICAITI), 2019, pp. 203-206. DOI:10.1109/ICAITI48442.2019.8982159

Iurian, C.-M., Ivanciu, I.-A. & Dobrota, V. Couchbase Server in Microsoft Azure Cloud: A Docker Container Approach. International Symposium on Electronics and Telecommunications (ISETC), 2020, pp. 1–4. DOI: 10.1109/ISETC50328.2020.9301052.

Araujo, J. M. A., de Moura, A. C. E., da Silva, S. L. B., Holanda, M., Ribeiro, E. de O. & da Silva, G. L. Comparative Performance Analysis of NoSQL Cassandra and MongoDB Databases. 16th Iberian Conference on Information Systems and Technologies (CISTI), 2021, pp. 1–6. DOI: 10.23919/CISTI52073.2021.9476319.

Misaki, M., Tsuda, T., Inoue, S., Sato, S., Kayahara, A. & Imai, S.-I. Distributed Database and Application Architecture for Big Data Solutions. IEEE Trans. Semicond. Manuf., 2017, vol. 30, no. 4, pp. 328–332. DOI: 10.1109/TSM.2017.2750183.

Naik, N. Comprehending Concurrency and Consistency in Distributed Systems. IEEE International Symposium on Systems Engineering (ISSE), 2021, pp. 1–6. DOI: 10.1109/ISSE51541.2021.9582518.

Gomes, B., Borba, E., Tavares, E. & Junior, M. N. de O. Performability Model for Assessing NoSQL DBMS Consistency. IEEE International Systems Conference (SysCon), 2019, pp. 1–6. DOI: 10.1109/SYSCON.2019.8836757.

Gorbenko, A., Karpenko, A. & Tarasyuk, O., Analysis of Trade-offs in Fault-Tolerant Distributed Computing and Replicated Databases. IEEE 11th Int. Conf. on Dependable Systems, Services and Technologies (DESSERT), 2020, pp. 1–6. DOI: 10.1109/DESSERT50317.2020.9125078.

Ductor S. & Guessoum, Z. A coordination mechanism to replicate large-scale multi-agent systems. Int. Conf. on Software Engineering for Adaptive and Self-Managing Systems, 2018, pp. 130–136. DOI: 10.1145/3194133.3194154.

Gilbert S. & Lynch, N. Perspectives on the CAP Theorem. Computer, 2012, vol. 45, no. 2, pp. 30–36.vDOI: 10.1109/MC.2011.389.

Muñoz-Escoí, F. D., de Juan-Marín, R., García-Escrivá, J.-R., González de Mendívil, J. R. & Bernabéu-Aubán, J. M. CAP Theorem: Revision of Its Related Consistency Models. Comput. J., 2019, vol. 62, no. 6, pp. 943–960. DOI: 10.1093/comjnl/bxy142.

Xhafa, F., Naranjo, V., Barolli, L. & Takizawa, M. On Streaming Consistency of Big Data Stream Processing in Heterogenous Clutsers. 18th Int. Conf. on Network-Based Information Systems, 2015, pp. 476–482. DOI: 10.1109/NBiS.2015.122.

Huang, X., Wang, J., Yu, P. S., Bai, J. & Zhang, J. An experimental study on tuning the consistency of NoSQL systems: An Experimental Study on Tuning the Consistency of NoSQL Systems. Concurr. Comput. Pract. Exp., 2017, vol. 29, no. 12, article no. e4129. DOI: 10.1002/cpe.4129.

Tomforde S. & Gruhl, C. Fairness, Performance, and Robustness: Is There a CAP Theorem for Self-adaptive and Self-organising Systems? IEEE Int. Conf. on Autonomic Computing and Self-Organizing Systems Companion (ACSOS-C), 2020, pp. 54–59. DOI: 10.1109/ACSOS-C51401.2020.00029.

Gorbenko, A. & Tarasyuk, O. Exploring Timeout as a Performance and Availability Factor of Distributed Replicated Database Systems. Radioelectron. Comput. Syst., 2020, no. 4, pp. 98–105. DOI: 10.32620/reks.2020.4.09.

Kumar, S. P., Lefebvre, S., Chiky, R. & Soudan, E. G. Evaluating consistency on the fly using YCSB. International Workshop on Computational Intelligence for Multimedia Understanding (IWCIM), 2014, pp. 1–6. DOI: 10.1109/IWCIM.2014.7008801.

Vyas, K. & Jat, P. M. Study of Consistency and Performance Trade-Off in Cassandra. Computer Science & Technology, 2022, vol. 12, no. 19, pp. 61-77. DOI: 10.5121/csit.2022.121907.

Kim, B. H., Oh, S. & Lie, D. Consistency Oracles: Towards an Interactive and Flexible Consistency Model Specification. 16th Workshop on Hot Topics in Operating Systems, 2017, pp. 82–87. DOI: 10.1145/3102980.3102994.

Hutchison, B., Kepner, J., Gadepally, V. & Howe, B. From NoSQL Accumulo to NewSQL Graphulo: Design and utility of graph algorithms inside a BigTable database. IEEE High Performance Extreme Computing Conference (HPEC), 2016, pp. 1–9. DOI: 10.1109/HPEC.2016.7761577.

Cao, C., Wang, W., Zhang, Y. & Ma, X. Leveraging Column Family to Improve Multidimensional Query Performance in HBase. IEEE 10th Int. Conf. on Cloud Computing (CLOUD), 2017, pp. 106–113. DOI: 10.1109/CLOUD.2017.22.

Sun, B., Zhang, G. & Gao, S. Data Management across Geographically Distributed Autonomous Systems: Architecture, Implementation, and Performance Evaluation. IEEE Int. Conf. on High Performance Computing and Communications; (HPCC), 2019, pp. 2284–2292. DOI: 10.1109/HPCC/SmartCity/DSS.2019.00317.

Ductor, S. & Guessoum, Z. A coordination mechanism to replicate large-scale multi-agent systems. 13th Int. Conf. on Software Engineering for Adaptive and Self-Managing Systems, 2018, pp. 130–136. DOI: 10.1145/3194133.3194154.

Zhao X. & Haller, P. Replicated data types that unify eventual consistency and observable atomic consistency. J. Log. Algebr. Methods Program., 2020, vol. 114, article no. 100561. DOI: 10.1016/j.jlamp.2020.100561.

Fetai, I., Stiemer, A. & Schuldt, H. QuAD: A quorum protocol for adaptive data management in the cloud. IEEE Int. Conf. on Big Data (Big Data), 2017, pp. 405–414. DOI: 10.1109/BigData.2017.8257952.

Pankowski, T. Consistency and Availability of Data in Replicated NoSQL Databases. 10th Int. Conf. on Evaluation of Novel Approaches to Software Engineering, 2015, pp. 102–109. DOI: 10.5220/0005368101020109.

Gu, S., Wang, Y., Wang, Y., Zhang, Q. & Qin, X. Grouping-Based Consistency Protocol Design for End-Edge-Cloud Hierarchical Storage System. IEEE Access, 2020, vol. 8, pp. 8959–8973, DOI: 10.1109/ACCESS.2020.2964626.

Hsu, T.-Y., Kshemkalyani, A. D. & Shen, M. Causal consistency algorithms for partially replicated and fully replicated systems. Future Gener. Comput. Syst., 2018, vol. 86, pp. 1118–1133. DOI: 10.1016/j.future.2017.04.044.

Fouto, P., Leitao, J. & Preguica, N. Practical and Fast Causal Consistent Partial Geo-Replication. IEEE 17th International Symposium on Network Computing and Applications (NCA), 2018, pp. 1–10. DOI: 10.1109/NCA.2018.8548067.

Maneas, S., Chondros, N., Diamantopoulos, P., Patsonakis, C. & Roussopoulos, M. On achieving interactive consistency in real-world distributed systems. J. Parallel Distrib. Comput., 2021, vol. 147, pp. 220–235. DOI: 10.1016/j.jpdc.2020.09.010.

Bannour, B., Souihi, S. & Mellouk, A. Adaptive State Consistency for Distributed ONOS Controllers. IEEE Global Communications Conference (GLOBECOM), 2018, pp. 1–7. DOI: 10.1109/GLOCOM.2018.8647168.

Sakic, E., Sardis, F., Guck, J. W. & Kellerer, W. Towards adaptive state consistency in distributed SDN control plane. IEEE Int. Conf. on Communications (ICC), 2017, pp. 1–7. DOI: 10.1109/ICC.2017.7997164.

de Souza, R. H., Flores, P. A., Dantas, M. A. R. & Siqueira, F. Architectural recovering model for Distributed Databases: A reliability, availability and serviceability approach. IEEE Symposium on Computers and Communication (ISCC), 2016, pp. 575–580. DOI: 10.1109/ISCC.2016.7543799.

Tian, I. & Pang, Y. Adjoin: A causal consistency model based on the adjacency list in a distributed system. Concurr. Comput. Pract. Exp., 2020, vol. 32, no. 22. DOI: 10.1002/cpe.5835.

Nejati Sharif Aldin, B., Deldari, H., Moattar, M. H. & Razavi Ghods, M. Strict Timed Causal Consistency as a Hybrid Consistency Model in the Cloud Environment. Future Gener. Comput. Syst., 2019, vol. 105, pp. 259–274. DOI: 10.1016/j.future.2019.11.038.

Khalfi, B., de Runz, C., Faiz, S. & Akdag, H. A New Methodology for Storing Consistent Fuzzy Geospatial Data in Big Data Environment. IEEE Trans. Big Data, 2021, vol. 7, no. 2, pp. 468–482. DOI: 10.1109/TBDATA.2017.2725904.

Abbaszadeh, M. Weak Consistency Model in Distributed Systems Using Hierarchical Colored Petri Net. J. Comput., 2018 pp. 236–243. DOI: 10.17706/jcp.13.2.236-243.

Lima, D., Miranda, H. & Taiani, F. Simulation of partial replication in Distributed Transactional Memory. Wireless Days, Porto, Portugal, 2017, pp. 54–59. DOI: 10.1109/WD.2017.7918115.

Georgiou, M. A., Paphitis, A., Sirivianos, M. & Herodotou, H. Hihooi: A Database Replication Middleware for Scaling Transactional Databases Consistently. IEEE Trans. Knowl. Data Eng., 2022, vol. 34, no. 2, pp. 691–707. DOI: 10.1109/TKDE.2020.2987560.

Georgiou, M. A., Panayiotou, M., Odysseos, L., Paphitis, A., Sirivianos, M. & Herodotou, H. Attaining Workload Scalability and Strong Consistency for Replicated Databases with Hihooi. Int. Conf. on Management of Data, 2021, pp. 2721–2725. DOI: 10.1145/3448016.3452746.

Guo, I., Li, C. & Luo, Y. Fast replica recovery and adaptive consistency preservation for edge cloud system. Soft Comput., 2020, vol. 24, no. 19, pp. 14943–14964. DOI: 10.1007/s00500-020-04847-2.

Mansouri, N., Mohammad Hasani Zade, B. & Javidi, M. M. A multi-objective optimized replication using fuzzy based self-defense algorithm for cloud computing. J. Netw. Comput. Appl., 2020, vol. 171, article no. 102811. DOI: 10.1016/j.jnca.2020.102811.

Liu, I., Peng, J., Wang, J., Liu, W., Huang, Z. & Pan, J. Scalable and Adaptive Data Replica Placement for Geo-Distributed Cloud Storages. IEEE Trans. Parallel Distrib. Syst., 2020, vol. 31, no. 7, pp. 1575–1587. DOI: 10.1109/TPDS.2020.2968321.

Sun, S., Wang, X. & Zuo, F. RPCC: A Replica Placement Method to Alleviate the Replica Consistency under Dynamic Cloud. Int. Conf.s on Internet of Things (iThings), 2020, pp. 729–734. DOI: 10.1109/iThings-GreenCom-CPSCom-SmartData-Cybermatics50389.2020.00126.

Nwe, T., Yee, T. T., Htoon, E. C. & Nakamura, J., A Consistent Replica Selection Approach for Distributed Key-Value Storage System. Int. Conf. on Advanced Information Technologies (ICAIT), 2019, pp. 114–119. DOI: 10.1109/AITC.2019.8921008.

Gomes, V. B. F., Kleppmann, M., Mulligan, D. P. & Beresford, A. R. Verifying Strong Eventual Consistency in Distributed Systems. Proc. ACM Program. Lang., 2017, vol. 1, no. OOPSLA, pp. 1–28. DOI: 10.1145/3133933.

Dai, T., He, J., Gu, X. & Lu, S. Understanding Real-World Timeout Problems in Cloud Server Systems, IEEE Int. Conf. on Cloud Engineering (IC2E), 2018, pp. 1-11. DOI: 10.1109/IC2E.2018.00022.