Author(s): Rufino, José
Date: 2008
Persistent ID: http://hdl.handle.net/10198/982
Origin: Biblioteca Digital do IPB
Subject(s): Tabelas de Hash distribuídas; Particionamento; Localização distribuída; Operação conjunta; Balanceamento dinâmico; Avaliação de desempenho
As Estruturas de Dados Distribuídas (DDSs) constituem uma abordagem ao Armazenamento Distribuído adequada a aplicações com requisitos de elevada capacidade de armazenamento, escalabilidade e disponibilidade. Ao mesmo tempo, apresentando-se com interfaces simples e familiares, permitem encurtar o ciclo de desenvolvimento de aplicações. Num ambiente de cluster, caracterizado pela co-existência de grande variedade de aplicações e utilizadores com requisitos dinâmicos, e de gerações de equipamento com desempenhos diferenciados (tanto ao nível do poder de cálculo, como das comunicações e do armazenamento), a necessidade de operação conjunta e eficiente de múltiplas DDSs pelas aplicações constituiu um desafio científico e tecnológico que esta tese se propôs superar. Esta tese apresenta as propostas e os resultados alcançados durante o estudo e desenvolvimento dos modelos e da plataforma de suporte à arquitectura Domus para a co-operação de múltiplas Tabelas de Hash Distribuídas (DHTs) em clusters partilhados e heterogéneos. A plataforma contempla várias classes de atributos e operações sobre DHTs permitindo, entre outras possibilidades, a definição administrativa de limites à expansão/contracção, o recurso a diferentes tecnologias de armazenamento e a suspensão/retoma administrativa da operação. Numa outra vertente, para responder aos requisitos impostos pela execução simultânea de múltiplas e diferenciadas aplicações, foram formulados e desenvolvidos mecanismos de balanceamento dinâmico de carga que visam a optimização e rentabilização dos recursos computacionais, comunicacionais e de armazenamento disponíveis no cluster. Na base da abordagem estão modelos que dão uma resposta qualificada aos problemas do particionamento e da localização de entradas numa DHT. Em relação ao particionamento, são propostos modelos de distribuição para definição do número de entradas de cada nó de uma DHT, suportando variação dinâmica do número total de nós; os modelos asseguram uma distribuição óptima do número de entradas, nos quatro cenários que resultam da combinação de Hashing Estático ou Dinâmico, com Distribuição Homogénea ou Heterogénea; com Hashing Dinâmico, a qualidade da distribuição é parametrizável e, com Distribuição Homogénea, o esforço de re-distribuição é de ordem O(1) face ao total de nós da DHT. No que toca à localização, definiram-se algoritmos de encaminhamento acelerado para localização distribuída em topologias DeBruijn e Chord, que respondem à descontinuidade das partições das DHTs geradas pelos modelos de distribuição. Para o efeito, explorou-se a possível coexistência de múltiplas tabelas de encaminhamento em cada nó de uma DHT, para tentar aproximar o maior custo da localização sobre grafos completos (em que os vértices são entradas da DHT), ao custo de referência sobre grafos esparsos (em que os vértices são nós da DHT), tendo-se obtido valores de 70% a 90% do custo de referência.
Distributed Data Structures (DDSs) as an approach to Distributed Storage are adequate to applications that require high storage capacity, scalability and availability. At the same time, DDSs present simple and familiar interfaces that allow shorter development cycles. In a cluster environment, shared by multiple users and applications with dynamic requisites, and built on different hardware generations (with different computing, communication and storage power), the need to simultaneously and efficiently operate several DDSs by user applications presents the scientific and technological challenge embraced by this thesis. This thesis presents the proposals and the results achieved during the study of the models and development of the platform that supports the Domus architecture for the co-operation of multiple Distributed Hash Tables (DHTs) in shared and heterogeneous clusters. The platform supports several classes of attributes and operations on DHTs allowing, among other possibilities, the administrative definition of per DHT node boundaries and storage technologies, or the deactivation/reactivation of DHTs. In addition, Domus DHTs are managed by dynamic load balancing mechanisms which ensure certain service levels (like storage space or access performance) and optimize the utilization of cluster resources. The architecture builds on specific models for the partitioning and lookup of a DHT address space. The partitioning models ensure optimal distribution of the number of DHT buckets per node, for a dynamic number of DHT nodes, and support the different scenarios that arise from the combination of Static/Dynamic Hashing, with Homogeneous/Heterogeneous Distributions. The quality of the distribution is tuneable under Dynamic Hashing, and repartitioning involves O(1) nodes of the DHT under Homogeneous Distributions.
PRODEP III/5.3/N/199.006/00
