Sincronização Eficiente de CRDTs em Escala Utilizando uma Solução Hierárquica de Publish–Subscribe
Abstract
This study presents VCube-Sync, a system that uses a virtual hypercube topology as the basis for replicating a Conflict-free Replicated Data Type (CRDT)-based data store. CRDTs can ensure consistency in a deterministic and conflict-free manner. At the same time, hypercubes have been previously used for message distribution due to their fault tolerance and logarithmic latency while enabling heuristics based on knowledge of the structured overlay. The protocol presented in this study is based on VCubePS leveraging synergies between pub-sub and replication systems. VCube-Sync was tested under different loads and network distributions using the Grid5000 testbed, and the results were compared with those of other replication protocols in recent research. The results of this study show that VCube-Sync provides good results in terms of latency, scalability, and bandwidth.
References
Akkoorath, D. D., Tomsic, A. Z., Bravo, M., Li, Z., Crain, T., Bieniusa, A., Preguiça, N., and Shapiro, M. (2016). Cure: Strong semantics meets high availability and low latency. In 36th IEEE Int'l Conf. Distributed Comp. Systems (ICDCS), pages 405-414.
Baquero, C., Almeida, P. S., and Shoker, A. (2017). Pure operation-based replicated data types. CoRR, abs/1710.04469. http://arxiv.org/abs/1710.04469.
Bauwens, J. and Boix, E. G. (2021). Improving the Reactivity of Pure OperationBased CRDTs. In Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data, pages 1-6, New York, NY, USA. ACM. https://dl.acm.org/doi/10.1145/3447865.3457968.
Brown, R., Cribbs, S., Meiklejohn, C., and Elliott, S. (2014). Riak dt map: A composable, convergent replicated dictionary. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency, PaPEC '14, New York, NY, USA. ACM. https://doi.org/10.1145/2596631.2596633.
de Araujo, J. P. (2019). A communication-efficient causal broadcast publish/subscribe system. Theses, Sorbonne Université.
de Araujo, J. P., Arantes, L., Duarte, E. P., Rodrigues, L. A., and Sens, P. (2019). Vcube-ps: A causal broadcast topic-based publish/subscribe system. Journal of Parallel and Distributed Computing, 125:18-30. [link].
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007). Dynamo: Amazon's highly available key-value store. Operating Systems Review (ACM), pages 205-220.
Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalable distributed diagnosis algorithm. pages 17-22. IEEE. http://ieeexplore.ieee.org/document/7016729/.
Fouto, P., Costa, P. A., Preguiça, N., and Leitão, J. (2022). Babel: A framework for developing performant and dependable distributed protocols. https://arxiv.org/abs/2205.02106.
Fouto, P., Leitao, J., and Preguica, N. (2018). Practical and fast causal consistent partial geo-replication. pages 1-10. IEEE. https://ieeexplore.ieee.org/document/8548067/.
Linde, A., Fouto, P., Leitão, J., Preguiça, N., Castiñeira, S., and Bieniusa, A. (2017). Legion: Enriching internet services with peer-to-peer interactions. pages 283-292.
McCord, C. (2022). Phoenix presence.
Meiklejohn, C. and Van Roy, P. (2015). Selective Hearing: An Approach to Distributed, Eventually Consistent Edge Computation. In 2015 IEEE 34th Symposium on Reliable Distributed Systems Workshop (SRDSW), volume 2016-Janua, pages 62-67. IEEE. https://ieeexplore.ieee.org/document/7371444/.
Meiklejohn, C. S. and Van Roy, P. (2017). Loquat: A framework for large-scale actor communication on edge networks. 2017 IEEE Int'l Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2017, pages 563-568.
Rodrigues, L. A., Duarte Júnior, E. P., de Araujo, J. P., Arantes, L., and Sens, P. (2018). Bundling Messages to Reduce the Cost of Tree-Based Broadcast Algorithms. In LADC 2018 8th Latin-American Symposium on Dependable Computing, Foz do Iguaçu, Brazil.
Saito, Y. and Shapiro, M. (2005). Optimistic replication. ACM Comput. Surv., 37(1):42-81. https://doi.org/10.1145/1057977.1057980.
Shapiro, M., Preguiça, N., Baquero, C., and Zawirski, M. (2011). Conflict-free replicated data types. In Défago, X., Petit, F., and Villain, V., editors, Stabilization, Safety, and Security of Distributed Systems, pages 386-400, Berlin, Heidelberg. Springer Berlin Heidelberg.
van der Linde, A., Fouto, P., Leitão, J. a., and Preguiça, N. (2020). The intrinsic cost of causal consistency. In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC '20, New York, NY, USA. Association for Computing Machinery.
Vieira, E. (2021). Eco sync tree: A causal and dynamic broadcast tree for edge-based replication. Master's thesis, NOVA University Lisbon.
Vogels, W. (2009). Eventually consistent. Commun. ACM, 52(1):40-44. https://doi.org/10.1145/1435417.1435432.
Younes, G., Shoker, A., Almeida, P. S., and Baquero, C. (2016). Integration challenges of pure operation-based crdts in redis. In First Workshop on Programming Models and Languages for Distributed Computing, PMLDC '16, New York, NY, USA. ACM. https://doi.org/10.1145/2957319.2957375.
Baquero, C., Almeida, P. S., and Shoker, A. (2017). Pure operation-based replicated data types. CoRR, abs/1710.04469. http://arxiv.org/abs/1710.04469.
Bauwens, J. and Boix, E. G. (2021). Improving the Reactivity of Pure OperationBased CRDTs. In Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data, pages 1-6, New York, NY, USA. ACM. https://dl.acm.org/doi/10.1145/3447865.3457968.
Brown, R., Cribbs, S., Meiklejohn, C., and Elliott, S. (2014). Riak dt map: A composable, convergent replicated dictionary. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency, PaPEC '14, New York, NY, USA. ACM. https://doi.org/10.1145/2596631.2596633.
de Araujo, J. P. (2019). A communication-efficient causal broadcast publish/subscribe system. Theses, Sorbonne Université.
de Araujo, J. P., Arantes, L., Duarte, E. P., Rodrigues, L. A., and Sens, P. (2019). Vcube-ps: A causal broadcast topic-based publish/subscribe system. Journal of Parallel and Distributed Computing, 125:18-30. [link].
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007). Dynamo: Amazon's highly available key-value store. Operating Systems Review (ACM), pages 205-220.
Duarte, E. P., Bona, L. C. E., and Ruoso, V. K. (2014). Vcube: A provably scalable distributed diagnosis algorithm. pages 17-22. IEEE. http://ieeexplore.ieee.org/document/7016729/.
Fouto, P., Costa, P. A., Preguiça, N., and Leitão, J. (2022). Babel: A framework for developing performant and dependable distributed protocols. https://arxiv.org/abs/2205.02106.
Fouto, P., Leitao, J., and Preguica, N. (2018). Practical and fast causal consistent partial geo-replication. pages 1-10. IEEE. https://ieeexplore.ieee.org/document/8548067/.
Linde, A., Fouto, P., Leitão, J., Preguiça, N., Castiñeira, S., and Bieniusa, A. (2017). Legion: Enriching internet services with peer-to-peer interactions. pages 283-292.
McCord, C. (2022). Phoenix presence.
Meiklejohn, C. and Van Roy, P. (2015). Selective Hearing: An Approach to Distributed, Eventually Consistent Edge Computation. In 2015 IEEE 34th Symposium on Reliable Distributed Systems Workshop (SRDSW), volume 2016-Janua, pages 62-67. IEEE. https://ieeexplore.ieee.org/document/7371444/.
Meiklejohn, C. S. and Van Roy, P. (2017). Loquat: A framework for large-scale actor communication on edge networks. 2017 IEEE Int'l Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2017, pages 563-568.
Rodrigues, L. A., Duarte Júnior, E. P., de Araujo, J. P., Arantes, L., and Sens, P. (2018). Bundling Messages to Reduce the Cost of Tree-Based Broadcast Algorithms. In LADC 2018 8th Latin-American Symposium on Dependable Computing, Foz do Iguaçu, Brazil.
Saito, Y. and Shapiro, M. (2005). Optimistic replication. ACM Comput. Surv., 37(1):42-81. https://doi.org/10.1145/1057977.1057980.
Shapiro, M., Preguiça, N., Baquero, C., and Zawirski, M. (2011). Conflict-free replicated data types. In Défago, X., Petit, F., and Villain, V., editors, Stabilization, Safety, and Security of Distributed Systems, pages 386-400, Berlin, Heidelberg. Springer Berlin Heidelberg.
van der Linde, A., Fouto, P., Leitão, J. a., and Preguiça, N. (2020). The intrinsic cost of causal consistency. In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC '20, New York, NY, USA. Association for Computing Machinery.
Vieira, E. (2021). Eco sync tree: A causal and dynamic broadcast tree for edge-based replication. Master's thesis, NOVA University Lisbon.
Vogels, W. (2009). Eventually consistent. Commun. ACM, 52(1):40-44. https://doi.org/10.1145/1435417.1435432.
Younes, G., Shoker, A., Almeida, P. S., and Baquero, C. (2016). Integration challenges of pure operation-based crdts in redis. In First Workshop on Programming Models and Languages for Distributed Computing, PMLDC '16, New York, NY, USA. ACM. https://doi.org/10.1145/2957319.2957375.
Published
2023-05-22
How to Cite
GALESKY, Leonardo de Freitas; RODRIGUES, Luiz Antonio.
Sincronização Eficiente de CRDTs em Escala Utilizando uma Solução Hierárquica de Publish–Subscribe. In: BRAZILIAN SYMPOSIUM ON COMPUTER NETWORKS AND DISTRIBUTED SYSTEMS (SBRC), 41. , 2023, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 463-475.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2023.484.