QUERY PROCESSING IN CLOUD DATABASES WITH PARTIAL REPLICATION

Abstract

Distributed databases are an essential component of large-scale applications where data is stored durably. Given the size of the systems, this type of applications is often presented with network partitions, which can cause considerable down time which impacts user experience and relevant economic losses to companies that resort to such solutions. Because of this, application developers are increasingly opting for highly-available low latency solutions that eschew strong consistency properties that require replica coordination and penalize performance especially when application and database instances are geo-replicated across multiple datacenters. In this type of applications it also becomes difficult to have data fully replicated in each site. Servers might not have enough physical resources to do so and it may become really expensive to do so. Partial replication solutions where every replica doesn’t have all data are an alternative that still is able provide fault-tolerance and low latency. PotionDB is a database that follows the partial replication model and this work extends it with the added support for queries. This contribution includes a description and study of internal structures used to get records that satisfy the queries’ condition along with a study of different algorithms used in query processing to get objects a database instance does not possess locally given the partial replication of the data.

Bases de dados distribuídas são o componente essencial de aplicações de larga escala onde os dados são guardados duravelmente. Dada a dimensão destes sistemas, este tipo de aplicações é frequentemente afetada por partições de rede que por sua vez podem resultar em um serviço ir abaixo por um tempo considerável que por sua vez prejudica a experiência do utilizador e pode resultar em perdas económicas consideráveis. Devido a isto, programadores têem cada vez mais adotado bases de dados que garantem maior disponibilidade e latência reduzida ao invés de outras opções de consistência forte que exigem coordenação entre réplicas e degradam o desempenho do sistema, especialmente quando os dados estão replicados em múltiplos centros de dados. Neste tipo de aplicações também se torna difícil ter os dados totalmente replicados em todas as réplicas. Os servidores podem não ter recursos físicos para que isso seja implementado e também se tornaria muito caro fazê-lo. A replicação parcial é uma alternativa a este esquema e é capaz de atingir tolerância a falhas e baixa latência. O PotionDB é uma base de dados que adota o modelo de replicação parcial dos dados. Este trabalho extende as funcionalidades originais do PotionDB nomeadamente o suporte para responder a perguntas. As contribuições deste trabalho incluem a descrição e estudo de estruturas internas utilizados para obter os registos da base de dados que satisfazem as condições das perguntas. Este trabalho também faz um estudo de algoritmos utilizados durante o processamento de perguntas que definem como ir buscar objetos que a instância da base de dados que recebe a pergunta do cliente não possui localmente dado o modelo de replicação parcial dos dados.