A Demand-Aware Heuristic for Value-Space Partitioning and Repartitioning

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.