Uma abordagem para o particionamento de dados na nuvem baseada em relações de afinidade em grafos

Abstract

Resumo: Os desafios atuais do gerenciamento de dados vêm sendo frequentemente associados ao termo Big Data. Este termo refere-se a um número crescente de aplicações caracterizadas pela produção de dados com alta variedade, grande volume, e que exigem velocidade em seu processamento. Ao mesmo tempo em que estes requisitos são identificados, o amadurecimento tecnológico associado à computação em nuvem alavancou uma mudança nos aspectos operacionais e econômicos da computação, sobretudo através de infraestruturas para o desenvolvimento de serviços escaláveis. A iniciativa do gerenciamento de dados sobre estas plataformas mostra-se adequada para tratar os desafios do Big Data através de um serviço de banco de dados em nuvem (Database as a Service). Uma forma de escalar aplicações que processam uma quantidade massiva de informações e através da fragmentação de grandes conjuntos de dados alocados sobre servidores de um sistema em nuvem. O principal problema associado a esta abordagem esta em particionar os dados de forma que consultas possam ser preferencialmente executadas de forma local para evitar o custo da troca de mensagens entre servidores. Em conjunto com este problema, a variedade de dados e o volume crescente associado as bases de dados em nuvem desafiam as soluções tradicionais para o particionamento de dados. Esta tese propõe um novo método para o particionamento de dados que tem como objetivo promover a escalabilidade de repositórios em nuvem. Para minimizar o custo da execução de consultas distribuídas, heurísticas sobre informações de carga de trabalho são utilizadas para identificar afinidades entre dados e estabelecer o agrupamento de itens fortemente relacionados em um mesmo servidor. O problema do particionamento e tratado pelos processos de fragmentação e alocação. O processo de fragmentação define unidades de armazenamento que contem itens de dados fortemente relacionados. Na fase seguinte, o processo de alocação utiliza o mesmo critério de agrupamento para co-alocar fragmentos nos servidores do repositório. A replicação é utilizada para maximizar a quantidade de dados relacionados em um mesmo servidor, porém, a quantidade de replicas gerada é controlada por todo o processo. A metodologia proposta esta focada em modelos em grafo estabelecidos pelos formatos RDF e XML, e que permitem representar uma variedade de outros modelos. A principal contribuição desta tese esta em definir o particionamento sobre uma visão sumarizada de um banco de dados similar a um esquema de banco de dados. Além de evitar a exaustão do processo de particionamento sobre grandes bases, esta solução permite reaplicar a estratégia obtida sobre novas porções de dados que estejam de acordo com o esquema e a carga de trabalho assumidos pelo processo. Esta metodologia se mostra adequada para acomodar o volume crescente de dados associado a repositórios em nuvem. Resultados experimentais mostram que a solução proposta é efetiva para melhorar o desempenho de consultas, se comparada a abordagens alternativas que tratam o mesmo problema.

Abstract: The new challenges in data management have been referred to as Big Data. This term is related to an increasing number of applications characterized by generating data with a variety of types, huge volume, and by requiring high velocity processing. At the same time, cloud computing technologies are transforming the operational and economic aspects of computing, mainly due to the introduction of infrastructures to deploy scalable services. Cloud platforms have been properly applied to support data management and address Big Data challenges through a database service in the cloud (DaaS - Database as a Service). One approach to scale applications that process massive amounts of information is to fragment huge datasets and allocate them across distributed data servers. In this context, the main problem is to apply a partitioning schema that maximizes local query processing and avoids the cost of message passing among servers. Besides this problem, data variety and the ever-increasing volume of cloud datastores pose new challenges to traditional partitioning approaches. This thesis provides a new partitioning approach to scale query processing on cloud datastores. In order to minimize the cost of distributed queries, we apply heuristics based on workload data to identify the affinity among data items and cluster the most correlated data in the same server. We tackle the data partitioning problem as a twofold problem. First, data fragmentation defines storage units with strongly correlated items. Further, data allocation aims to collocate fragments that share correlated items. Data replication is applied to cluster related data as much as possible. However, data redundancy is controlled throughout the process. We focus on graph models given by the RDF and XML formats in order to support data variety. Our main contribution is a partitioning strategy defined over a summarized view of the dataset given as a database schema. The result of the process consists of a set of partitioning templates, which can be used to partition an existing dataset, as well as maintain the partitioning process when new data that conform to the schema and the workload are inserted to the dataset. This approach is suitable to deal with the increasing volume of data related to cloud datastores. Experimental results show that the proposed solution is effective for improving the query performance in cloud datastores, compared to related approaches.