Efficient synchronization of state-based CRDTs

Abstract

Data consistency often needs to be sacrificed in order to ensure high-availability in large scale distributed systems. Conflict-free Replicated Data Types relax consistency by always allowing query and update operations at the local replica without remote synchronization. Consistency is then re-established by a background mechanism that synchronizes the replicas in the system. In state-based CRDTs replicas synchronize by periodically sending their local state to other replicas and by merging the received remote states with the local state. This synchronization can become very costly and unacceptable as the local state grows. Delta-state-based CRDTs solve this problem by producing smaller messages to be propagated. However, it requires each replica to store additional metadata with the messages not seen by its direct neighbors in the system. This metadata may not be available after a network partition, since a replica can be forced to garbage-collect it (due to storage/memory limitations), or when the set of direct neighbors of a replica changes (due to dynamic memberships). In this dissertation we further improve the synchronization of state-based CRDTs, by introducing the concept of Join Decomposition of a state-based CRDT and explaining how it can be used to reduce the synchronization cost of this variant of CRDTs. We validate our proposal experimentally on Google Cloud Platform by comparing the state-based synchronization algorithm against the classic and improved versions of the delta-state-based algorithm. The results of this comparison show that our proposed techniques can greatly reduce state transmission, even under normal operation when the network is stable.

Frequentemente a consistência dos dados é sacrificada para garantir alta-disponibilidade em sistemas distribuídos de grande escala. Conflict-free Replicated Data Types relaxam a consistência permitindo operações de query e update na réplica local sem sincronização remota. Nos state-based CRDTs as réplicas sincronizam periodicamente enviando o seu estado local para as outras réplicas e combinando os estados remotos recebidos com o estado local. Esta sincronização pode tornar-se muito custosa e inaceitável à medida que o estado local cresce. Delta-state-based CRDTs resolvem este problema produzindo mensagens mais pequenas para serem propagadas. No entanto, requer guardar metadados adicionais com as mensagens que ainda não foram vistas pelos vizinhos diretos no sistema. Estes metadados podem não estar disponíveis depois de uma partição na rede, visto que a réplica pode ser forçada a apagá-los (devido a limitações de armazenamento/memória), ou quando o conjunto dos vizinhos diretos da réplica muda (devido a vistas dinâmicas). Nesta dissertação melhoramos ainda mais a sincronização de state-based CRDTs, introduzindo o conceito de Join Decomposition de um state-based CRDT e explicando como é que pode ser usado para reduzir o custo de sincronização desta variante de CRDTs. Validamos a nossa proposta experimentalmente na Google Cloud Platform comparando o algoritmo de sincronização de state-based CRDTs com a clássica e melhoradas versões do algoritmo dos delta-state-based. Os resultados desta comparação mostram que as técnicas propostas podem reduzir muito a transmissão de dados, mesmos em operação normal quando a rede está estável.