Tabelas Hash Distribuídas com Consultas de um Salto com Baixa Carga de Manutenção
Autores
|
4874 |
402,135
|
|
|
4875 |
402,135
|
Informações:
Publicações do PESC
Nesta tese estamos introduzindo uma inovadora Tabela Hash Distribuída (DHT), batizada de D1HT, que é capaz de resolver consultas com um salto e tem baixas demandas de rede, mesmo em ambientes com dinâmicas representativas de aplicações distribuídas populares. Para validar suas propriedades, introduzimos dois teoremas, implementamos o sistema proposto, e desenvolvemos a mais ampla avaliação experimental de DHTs já publicada, com até 4.000 pares e 2.000 nós físicos. Nosso conjunto de resultados nos permitiu provar teoricamente, experimentalmente e analiticamente as propriedades de correção, balanceamento de carga, custos e desempenho de D1HT, bem como sua superioridade frente a todas as outras DHTs de baixa latência, com reduções de custos de até uma ordem de magnitude para sistemas com dimensões e comportamentos representativos de aplicações reais e populares. De maneira a efetivamente validar a utilidade de nossa principal contribuição, introduzimos e desenvolvemos um sistema de arquivos distribuído fundamentado em D1HT, e conduzimos experimentos mostrando que este sistema pode prover desempenho até oito vezes superior ao alcançado por uma solução comercial de última geração. Deste modo, o nosso conjunto de resultados formais, analíticos e experimentais, nos permitiu concluir que, frente a contextos atuais e tendências futuras, D1HT já desponta como uma ferramenta útil e adequada para diversos ambientes, desde Centros de Computação de Alto Desempenho até aplicações de larga escala na Internet, devendo se tornar cada vez mais atraente para um espectro continuamente maior de aplicações. Disponibilizamos o código fonte de D1HT, facilitando seu uso e o desenvolvimento de novas pesquisas nesta área.
In this thesis we are introducing a new distributed hash table (DHT), called D1HT, which is able to solve lookups with one hop and low overhead even in systems with frequent node joins and leaves. In order to certify its properties, we introduced two theorems, implemented D1HT, and realized the largest DHT experimental comparison ever published, with up to 4,000 peers and 2,000 physical nodes in two radically distinct environments. Our set of results allowed us to prove formally, experimentally, and analytically the D1HT characteristics of correctness, load balancing, maintenance overheads and performance, as well as its superior properties in relation to other low latency DHTs, with D1HT's overhead reductions of up to one order of magnitude for systems which size and behavior are representative of popular applications. In order to demonstrate the utility of D1HT, we implemented a distributed file system on top of it, and carried out experiments showing that the resulting system could achieve performance up to eight times superior than that of a modern commercial solution. Our large set of formal, analytical, and experimental results allowed us to conclude that D1HT is already an useful tool for a wide range of computing environments, from High Performance Computing data centers to Internet large scale applications, and that future trends may make D1HT even more attractive for a larger range of applications. We have made the D1HT source code freely available, which may easy its use by other groups as well as to foster new research in this area.