Performance modeling, task scheduling and elastic scaling for distributed graph processing systems

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2021.O crescimento das bases de dados observado nos últimos anos, que deu origem ao termo BigData, trouxe inúmeros desafios e despertou o interesse dos pesquisadores por formas inovadoras de extrair informações de grandes bases de dados de maneira paralela e distribuída. Diversas ferramentas foram idealizadas e se mostraram bem sucedidas para essa tarefa, como o MapReduce da Google (e sua versão open source, o Hadoop). No entanto, logo ficou claro que estas ferramentas de propósito geral não eram adequadas para lidar com grandes bases de dados modeladas como grafos. Para lidar com grafos muito grandes, ferramentas e abstrações de programação específicas foram propostas, dentre as quais se destaca o Pregel, da Google. Pregel propõe uma abstração baseada no Bulk Synchronous Parallel (BSP), cuja popularidade resultou em diversas implementações de código aberto e ampla utilização na indústria e academia. Isso inclui tanto ferramentas para processamento em lote, como o originalmente proposto pelo Pregel, quanto ferramentas para processamento de fluxo contínuo de dados, chamadas stream processing baseadas em grafos. Estas ferramentas foram propostas para serem executadas em nuvens computacionais, onde os recursos precisam ser alocados de maneira eficiente. Este trabalho investiga modelos de desempenho que possam ser usados para estimar o tempo de execução de tarefas de processamento de grafos em diferentes configurações de ambientes de execução (em termos de número e tamanho das máquinas alocadas), de maneira a permitir a otimização e racionalização da escolha destas configurações. São considerados tanto os cenários de processamento em lote, em grafos estáticos previamente coletados, quanto cenários de stream processing, em que o grafo evolui continuamente durante a execução. Além disso, são consideradas diversos mecanismos de particionamento do grafo entre os computadores que compõem o ambiente de execução: desde o particionamento aleatório simples (conhecido como Hash) até modelos sofisticados que otimizam a distribuição do grafo de maneira a reduzir o overhead de comunicação, através de uma técnica baseada em micro-partições. Para tarefas de processamento em lote, é apresentado um modelo de desempenho baseado no GPS, uma implementação de código aberto do Pregel, cujas previsões tem uma precisão média próxima de 90% (comparada a 50% de ferramentas de aprendizado de máquina comumente usadas nessa tarefa). O modelo também é o primeiro da literatura capaz de lidar com particionadores sofisticados (usando a técnica de micro-partições), aplicando o particionamento de vértices do grafo. Para tarefas de stream processing, é apresentado um modelo de desempenho para o Spark GraphX. Esta ferramenta, também baseada no Pregel, realiza o particionamento de arestas, que foi estendido com um particionador que suporta a técnica de micro-partições. O modelo de desempenho é utilizado para guiar o escalonamento de tarefas, de modo que o sistema ajuste a configuração do ambiente de execução de acordo com a evolução do grafo que está sendo analisado. Com isso, torna-se possível realizar escalonamento horizontal e vertical, sem a necessidade de um reparticionamento completo do grafo, que seria necessário com particionadores sofisticados. O modelo de desempenho e o particionador foram aplicados a um grafo dinâmico extraído do Twitter com o objetivo de cumprir deadlines na atualização do grafo, tendo sido verificada uma precisão média próxima de 90% para as previsões realizadas pelo modelo de desempenho, bem como uma redução de até 30% no custo de alocação de máquinas em experimentos realizados no Amazon EC2.Abstract: The accelerated growth of databases observed in recent years, that started the BigData era, presented numerous challenges related to extracting useful information from massive datasets in a parallel and distributed fashion. Several tools and frameworks were proposed to tackle these challenges, with many widely successful examples, such as MapReduce from Google (and its open-source version Hadoop), Apache Spark, and others. However, it soon became clear that, although successful in many domains, general-purpose frameworks were not efficient to handle large datasets modeled as graphs. Efficiently extracting valuable data from massive graphs required domain-specific tools and programming abstractions. Over the years, many frameworks were proposed, among which Google's Pregel stands out. Pregel proposes an abstraction based on the Bulk Synchronous Parallel (BSP) programming model that simplifies the creation of graph algorithms and became widely popular both among researchers and the industry. Pregel's popularity resulted in many open-source implementations, including for batch applications (as Pregel was originally designed) and also for dynamic graph stream processing applications. Frameworks such as Pregel are designed to be executed in cloud computing environments, where the resources must be efficiently managed given the pay-as-you-go nature of such services. This thesis investigates performance models that can be used to estimate the execution time of graph processing tasks in different execution environments (considering the number and types of virtual machines allocated), to optimize and rationalize the choice of such configurations. We investigate the static graph processing scenario and also stream processing applications of dynamic graphs, in which the graph continuously evolves during the execution of the system. We also consider different mechanisms for partitioning a graph among distributed processing nodes, from the simple Hash partitioner (in which the graph components are randomly assigned to processing nodes) to sophisticated algorithms that aim to reduce communication overheads, employing a micro-partitioning technique. When considering batch processing of static graphs, this thesis presents a performance model based on GPS, an open-source implementation of the Pregel model, and a task scheduler that uses the performance model to schedule graph processing jobs in a cloud computing environment. Our model has an average precision of 90 (much higher than the 50 achieved by machine learning tools commonly used to perform such predictions). Our model is also the first in the literature capable of using sophisticated partitioners, by applying a micro-partitioning technique to partition the graph vertices, whereas the existing literature of performance modeling for static graphs is limited to the simple hash partitioner. For streaming applications of dynamic graphs, we present an elastic scaler for Spark GraphX, also using Pregel's abstractions. Our proposal includes a performance model for dynamic graphs and a novel edge-based graph partitioner, that employs the micro-partitioning technique and is capable of quickly re-partitioning a graph during reconfigurations. The performance model is used to guide the elastic scaling of the streaming graph execution environment, both vertically and horizontally, as the graph evolves over time aiming to satisfy user-defined timing restrictions and to optimize the cost of running the application on a cloud computing environment. The performance model and partitioner were tested in a dynamic graph extracted from Twitter and have shown an average precision of 90 for performance model predictions, and reductions of up to 30 in the cost of running the application on Amazon EC2 when compared to state-of-the-art alternatives