Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/14070
Type: Dissertação
Title: A demand-aware heuristic for value-space partitioning and repartitioning
Other Titles: Uma heurística para particionamento e reparticionamento de um espaço de valores
Author(s)/Inventor(s): Cabral, Wladimir Livolis de Alcantara
Advisor: Rezende, José Ferreira de
Co-advisor: Rocha, Antônio Augusto de Aragão
Abstract: Neste trabalho, apresentamos uma nova heurística para particionamento de um banco de dados NoSQL de chave-valor baseado em seu espaço de valores. Nossa heurística leva em consideração a distribuição de operações de busca e atualização no intuito de particionar o espaço de valores em regiões mutuamente exclusivas e exaustivas que são contatadas de maneira justa por tais operações. A distribuição de cada uma dessas operações pode mudar com o tempo e, por isso, fazemos uso de uma versão do algoritmo de Greenwald-Khanna (um algoritmo de data stream bem conhecido), baseado em janelas deslizantes, no intuito de sempre ter disponível um resumo para encontrar quantis (que são os pontos onde o espaço de valores é particionado) e, então, realizar reparticionamentos de modo que as regiões ainda sejam contatadas de maneira justa. Nós realizamos experimentos variando a fração de buscas e atualizações, bem como suas distribuições, com o objetivo de avaliar o desempenho de nossa heurística e também compará-la com outras soluções. Os resultados mostram que, conforme a fração de buscas e atualizações muda, bem como suas distribuições, as regiões ainda são contatadas de maneira justa, além de não impor um número demasiado de mensagens a serem enviadas para as máquinas associadas a essas regiões.
Abstract: 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.
Keywords: Key-Value store
Value-space partitioning
Horizontal scalability
Subject CNPq: CNPQ::ENGENHARIAS
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Production unit: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: May-2019
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
WladimirLivolisDeAlcantaraCabral.pdf3,02 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.