Epidemic store for massive scale systems

Abstract

Considering the state-of-the-art systems for data management, it is observable that they exhibit two main frailties when deployed in a large scale system. On one hand, coordination protocols used in traditional relational database management systems do not perform well when the system grows beyond tens of nodes. On the other hand, data management approaches that relax consistency guarantees, thus avoiding coordination, struggle with high levels of system churn. In this dissertation, we present a completely decentralized, coordinationfree, scalable and robust data store. Our design is aimed at environments with several thousands of nodes and high levels of churn. O↵ering the current ubiquitous key-value data structures and programming interfaces, we describe how to overcome challenges raised by the need to distribute data - essential for load balancing, to replicate data - the crux of fault tolerance, and to route requests - key to performability. Alongside the design of our data store, we make several contributions in the context of distributed systems slicing. We propose a novel slicing protocol that overcomes state-of-the-art limitations. Additionally, we propose a novel epidemic algorithm for scalable and decentralized organization of system nodes into groups. This algorithm is used as an alternative to slicing at the core of our system. It organizes nodes into groups of parameterizable size without the need to have nodes knowing the system size. The contributions made on slicing protocols and the proposed group construction protocol are independent from the design of the data store. They are generic and can also be used as building blocks for other applications.

Ao considerar o estado da arte no que diz respeito a gestão de dados, é possível observar que as soluções existentes exibem duas grandes fragilidades quando instaladas em sistemas de grande escala. Por um lado, os protocolos de coordenação utilizados nas bases de dados relacionais tradicionais não são capazes de gerir, de forma eficaz, mais de uma dezena de nós. Por outro lado, abordagens que relaxam a coerência dos dados evitando assim protocolos de coordenação, escalam melhor mas não conseguem lidar com elevados níveis de dinamismo. Nomeadamente, constante entrada e saída de nós do sistema. Nesta dissertação apresentamos um sistema de armazenamento de dados completamente descentralizado, que não recorre a protocolos de coordenação, que é escalável e robusto. O desenho do nosso sistema visa ambientes com vários milhares de nós e elevados níveis de dinamismo. Oferecendo uma interface chave-valor, descrevemos como superar os desafios de distribuição de dados - essencial para balanceamento de carga, de replicação de dados - que permite tolerância a falhas e de direccionamento de pedidos - chave para o desempenho. Além do desenho do nosso sistema de armazenamento fazemos várias contribuições no âmbito do fatiamento de sistemas distribuídos. Propomos um novo protocolo de fatiamento que resolve várias limitações das abordagens existentes. Adicionalmente, propomos um novo algoritmo epidémico para organizar um sistema em grupos de nós de forma descentralizada e escalável. Este algoritmo é utilizado como alternativa a protocolos de fatiamento no mecanismo interno do nosso sistema. Organiza os nós em grupos de tamanho parametrizável sem que os nós precisem de saber o tamanho do sistema. As contribuições feitas em algoritmos de fatiamento e o novo algoritmo de construção de grupos são independentes do sistema de armazenamento de dados. So genéricos e podem ser utilizados como componentes de outras aplicações.