PopRing: a popularity-aware replica placement for reducing latency on distributed key-value stores

Distributed key-value stores (KVS) are a well-established approach for cloud data-intensive applications, but they were not designed to consider workloads with data access skew, mainly caused by popular data. In this work, we analyze the problem of replica placement on KVS for workloads with data access skew. We formally define our problem as a multi-objective optimization problem because not only load imbalance cost, but replica maintenance and reconfiguration costs affect system performance as well. To solve the replica placement problem, we present the PopRing replica placement component based on Genetic algorithms to find new replica placements efficiently. Next, we extend PopRing framework with a hyper-parameter optimization component based on Bayesian optimization in order to efficiently find the proper importance of load imbalance, replica maintenance, and reconfiguration objectives according to the system latency. To validate our PopRing engine in practice, we implemented a full prototype of PopRing to generate new replica placement schemes in the format of the distributed hash table (DHT) interface of the popular object store OpenStack-Swift. Then, in our lab environment, we deployed a distributed cluster of the OpenStack-Swift, a benchmark node and the PopRing prototype to run some experiments. From results evaluation, we verified that our solution was able to reduce system latency for different levels of data access skew without human intervention, i.e., PopRing auto-tuned its parameters to find a proper replica placement scheme to a given scenario.O armazenamento distribuído em chave-valor (KVS) é uma abordagem bem estabelecida para aplicações com uso intensivo de dados na nuvem. Contudo, este tipo armazenamento não foi projetado para considerar cargas de trabalho com acesso desbalanceado aos dados devido principalmente a dados populares. Na presente pesquisa, foi feita uma análise do problema de alocação de réplicas no KVS para cargas de trabalho com acesso desbalanceado aos dados. O problema é definido formalmente como um problema de otimização multiobjetivo, pois além do custo de desequilíbrio de carga, também existem os custos de manutenção e reconfiguração de réplicas, que afetam o desempenho do sistema. Para resolver o problema de alocação da réplica, nós propomos o componente de alocação de réplicas PopRing. Esse componente, baseado em algoritmos genéticos, busca de forma eficiente novas alocações de réplica. Em seguida, a estrutura PopRing foi estendida com um componente de otimização de hiper-parâmetros baseado em otimização bayesiana, de modo a encontrar com eficiência a importância adequada das funções objetivas de desbalanceamento de carga, manutenção de réplica e reconfiguração de acordo com a latência do sistema. Para validar o PopRing, foi implementado um protótipo completo a fim de gerar novos esquemas de alocação de réplica no formato da interface distributed hash table (DHT) de armazenamento de objetos OpenStack-Swift. Em seguida, em nosso ambiente de experimentação, foi configurado um cluster distribuído do OpenStack-Swift, um nó de referência do benchmark e o protótipo PopRing para executar alguns experimentos. A partir da avaliação dos resultados, verificou-se que a solução conseguiu reduzir a latência do sistema para diferentes níveis de desbalanceamento de acesso a dados sem intervenção humana, ou seja, ajustou seus parâmetros automaticamente para encontrar um esquema de alocação de réplica apropriado para um dado cenário