A carregar...
Publicação
Protocols for Database Replication with Delta-based CRDT
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 3.49 MB | Adobe PDF |
Orientador(es)
Resumo(s)
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.
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.
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.
Descrição
Palavras-chave
Distributed Systems Conflict Resolution Delta-based CRDTs Geo-Replication Partial Replication Transactional Causal Consistency Model