Publicação
Protocols for Database Replication with Delta-based CRDT
| datacite.subject.fos | Engenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informática | pt_PT |
| dc.contributor.advisor | Preguiça, Nuno | |
| dc.contributor.advisor | Ferreira, Carla | |
| dc.contributor.author | Santos, Ana Patrícia Lourenço dos | |
| dc.date.accessioned | 2024-05-13T14:13:39Z | |
| dc.date.available | 2024-05-13T14:13:39Z | |
| dc.date.issued | 2023-12 | |
| dc.description.abstract | The use of distributed systems is the norm nowadays for web applications and services. In order to provide high availability and fault tolerance, systems need to rely on replication. With geo-replication, replicas are placed in different locations, and clients spread across the world contact the closest replica, with an expected lower latency. Weak consistency models are often used with these settings, and clients’s updates are propagated asynchronously to other replicas. When adopting such consistency models, it is possible that concurrent updates are executed, so it becomes necessary to merge these concurrent updates. CRDTs have been proposed as a principled approach to address this problem. CRDTs are data types specifically designed to be replicated and will converge upon having received the same set of updates, without having to contact other replicas. State- based CRDTs synchronize replicas by exchanging the whole state, while operation-based CRDTs exchange individual operations. A third model, delta-based CRDTs, is an alterna- tive that mixes the two models, by sending the part of the state that was modified, which minimizes the data being transmitted in most situations. In this work we designed a delta-based version of PotionDB, a geo-replicated database that currently uses operation-based CRDTs. To this end, we had to modify the CRDT library and the way that the updates are processed. Additionally, as PotionDB supports transactions, we had to modify the algorithms in a way that it is still possible to provide the transactional causal consistency model supported by PotionDB. We have evaluated our prototype, with the results showing that the new version uses less network bandwidth, but the scalability of the solution is worse. | pt_PT |
| dc.description.abstract | O uso de sistemas distribuídos é a norma hoje em dia para aplicações e serviços web. Para garantir alta disponibilidade e tolerância a falhas, os sistemas dependem de mecanismos de replicação. Com a geo-replicação, as réplicas são posicionadas em diferentes localizações, para que clientes espalhados pelo mundo possam aceder à réplica mais próxima, com a qual é expectável uma menor latência. Modelos de consistência fraca são comummente usados para isto e as atualizações efetuadas pelos clientes são propagadas assincronamente para as outras réplicas. Ao adotar estes modelos de consistência, torna-se possível que operações de atualização sejam executadas concorrentemente, pelo que se torna necessário unir estas atualizações concorrentes. Os CRDTs foram propostos como uma solução para resolver este problema. Os CRDTs são tipos de dados criados especificamente para serem replicados e con- vergem para o mesmo estado se receberem as mesmas operações, sem a necessidade de contactar as outras réplicas. Os CRDTs baseados em estado sincronizam réplicas ao enviar o estado inteiro e os CRDTs baseados em operações enviam as operações individuais. Um terceiro modelo, os CRDTs baseados em deltas, são uma alternativa que combina dos dois, pois enviam a parte do estado que foi modificada, minimizando a quantidade de dados a serem transmitidos na maioria dos casos. Neste trabalho, criámos uma versão baseada em deltas para o PotionDB, que é uma base de dados geo-replicada que atualmente utiliza CRDTs baseados em operações. Para isto, foi necessário modificar a biblioteca de CRDTs e a forma como as operações de escrita são processadas. Adicionalmente, como o PotionDB suporta transações, foi necessário modificar os algoritmos de forma a que seja possível providenciar a consistência causal transacional suportada pelo PotionDB. Nós avaliamos o nosso protótipo e os resultados motram que a nova versão utiliza menos recursos da rede, mas a escalabilidade é pior. | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10362/167320 | |
| dc.language.iso | eng | pt_PT |
| dc.subject | Distributed Systems | pt_PT |
| dc.subject | Conflict Resolution | pt_PT |
| dc.subject | Delta-based CRDTs | pt_PT |
| dc.subject | Geo-Replication | pt_PT |
| dc.subject | Partial Replication | pt_PT |
| dc.subject | Transactional Causal Consistency Model | pt_PT |
| dc.title | Protocols for Database Replication with Delta-based CRDT | pt_PT |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | masterThesis | pt_PT |
| thesis.degree.name | MASTER IN COMPUTER SCIENCE AND ENGINEERING | pt_PT |