Logical clocks for could databases

Abstract

Cloud computing environments, particularly cloud databases, are rapidly increasing in importance, acceptance and usage in major (web) applications, that need the partition-tolerance and availability for scalability purposes, thus sacrificing the consistency side (CAP theorem). With this approach, use of paradigms such as Eventual Consistency became more widespread. In these environments, a large number of users access data stored in highly available storage systems. To provide good performance to geographically disperse users and allow operation even in the presence of failures or network partitions, these systems often rely on optimistic replication solutions that guarantee only eventual consistency. In this scenario, it is important to be able to accurately and e ciently identify updates executed concurrently. In this dissertation we review, and expose problems with current approaches to causality tracking in optimistic replication: these either lose information about causality or do not scale, as they require replicas to maintain information that grows linearly with the number of clients or updates. Then, we propose Dotted Version Vectors (DVV), a novel mechanism for dealing with data versioning in eventual consistent systems, that allows both accurate causality tracking and scalability both in the number of clients and servers, while limiting vector size to replication degree. We conclude with the challenges faced when implementing DVV in Riak (a distributed key-value store), the evaluation of its behavior and performance, and discuss the advantages and disadvantages of it.

Ambientes de computação na nuvem, em especial sistemas de base de dados na nuvem, estão rapidamente a aumentar em importância, aceitação e utilização entre as grandes aplicações (web), que precisam de alta disponibilidade e tolerância a partições por razões de escalabilidade, para isso sacrificando o lado da coerência (teorema de CAP). Com esta abordagem, o uso de paradigmas como a Coerência Inevitável tornou-se generalizado. Nestes sistemas, um grande número de utilizadores têm acesso aos dados presentes em sistemas de dados de alta disponibilidade. Para fornecer bom desempenho para utilizadores geograficamente dispersos e permitir a realização de operações mesmo em presença de partições ou falhas de nós, estes sistemas usam técnicas de replicação optimista que garantem apenas uma coerência inevitável. Nestes cenários, é importante que a identificação de escritas concorrentes de dados, seja o mais exata e eficiente possível. Nesta dissertação, revemos os problemas com as abordagens atuais para o registo da causalidade na replicação optimista: estes ou perdem informação sobre a causalidade ou não escalam, já que obrigam as réplicas a manter informação que cresce linearmente com o número de clientes ou escritas. Propomos então, os Dotted Version Vectors (DVV), um novo mecanismo para lidar com o versionamento de dados em ambientes com coerência inevitável, que permite tanto um registo exato e correto da causalidade, bem como escalabilidade em relação ao número de clientes e número de servidores, limitando o seu tamanho ao factor de replicação. Concluímos com os desafios surgidos na implementação dos DVV no Riak (uma base de dados distribuída de chave/valor), a sua avaliação de comportamento e de desempenho, acabando com uma análise das vantagens e desvantagens da mesma.