Sincronização Eficiente de CRDTs em Escala Utilizando uma Solução Hierárquica de Publish–Subscribe
Resumo
Este estudo apresenta o VCube-Sync, um sistema que utiliza de uma topologia de hipercubos virtuais como base para replicação de um data-store baseado em Tipos de Dados Replicados e Livres de Conflitos - CRDT (Conflictfree Replicated Data Types). Os CRDTs podem garantir a consistência de forma determinística e livre de conflitos. Ao mesmo tempo, hipercubos já foram empregados anteriormente como rede de sobreposição estruturada para a distribuição de mensagens devido à tolerância a falhas e latência logarítmica, permitindo ainda o desenvolvimento de heurísticas de otimização baseadas no conhecimento da configuração da sobreposição. O protocolo de replicação apresentado neste estudo foi baseado no VCube-PS explorando sinergias entre sistemas publicação-subscrição e de replicação. O protocolo foi testado sob várias distribuições de carga e rede usando o testbed Grid5000, e os resultados foram comparados com os de outros protocolos de replicação de pesquisas recentes. Os resultados deste estudo mostram que o VCube-Sync fornece bons resultados em termos de latência, escalabilidade e uso de rede.
Referências
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.
Publicado
22/05/2023
Como Citar
GALESKY, Leonardo de Freitas; RODRIGUES, Luiz Antonio.
Sincronização Eficiente de CRDTs em Escala Utilizando uma Solução Hierárquica de Publish–Subscribe. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (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.