A demand-aware heuristic for value-space partitioning and repartitioning

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Cabral, Wladimir Livolis de Alcantara
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Universidade Federal do Rio de Janeiro
Brasil
Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Programa de Pós-Graduação em Engenharia de Sistemas e Computação
UFRJ
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/11422/14070
Resumo: In this work, we present a novel heuristic for partitioning a NoSQL key-value store based on its value-space. Our demand-aware heuristic takes into account the updates and search queries’ distribution in order to partition the value-space into mutually exclusive and exhaustive regions that are fairly contacted by these operations (updates and searches). The operations’ distributions might change with time and thus we make use of a sliding window based variation of the GreenwaldKhanna algorithm - a well-known data stream algorithm - in order to always have a summary available for finding quantile points (the value-space is partitioned at these points) and then to perform repartitioning so that regions are still fairly contacted. We also executed experiments varying the fraction of searches and updates, as well as their distributions, in order to evaluate the performance of our heuristic and compare it with other solutions. The results show that, as the fraction of searches and updates varies, as well as their distributions, regions are still contacted fairly and do not impose a higher number of messages to be sent to the machines associated to these regions.