Distributed Hash Tables (DHTs)

Um componente crítico de muitas aplicações P2P e outras aplicações distribuídas é um índice (ou seja, um banco de dados simples), que suporta operações de busca e atualização. Quando esse banco de dados é distribuído, os pares podem realizar caching de conteúdo e roteamento sofisticado de consultas entre si. Como a indexação e busca de informações são um componente crítico nesses sistemas, cobriremos uma técnica popular de indexação e busca, Distributed Hash Tables (DHTs).

Consideremos assim a construção de um banco de dados simples distribuído em um grande número (possivelmente milhões) de pares que suportam indexação e solicitação simples. As informações armazenadas em nosso banco de dados consistirão de duplas (chave, valor). Por exemplo, as chaves podem ser números de seguridade social e os valores podem ser nomes humanos correspondentes; nesse caso, um exemplo de dupla chave-valor é (156-45-7081, Johnny Wu). Ou as duplas podem ser nomes de conteúdo (ex.: nomes de filmes, álbuns e software), e os valores podem ser endereços IP onde o conteúdo está armazenado; nesse caso, um exemplo de par chave-valor é (Led Zeppelin IV, 203.17.123.38). Pares consultam nossos bancos de dados fornecendo a chave: caso haja duplas (chave, valor) em seus bancos de dados que correspondam à chave, o banco de dados retorna as duplas correspondentes ao par solicitante. Portanto, por exemplo, caso o banco de dados armazene números de seguridade social e seus nomes humanos correspondentes, um par pode consultar um número de seguridade social específico e o banco de dados retornará o nome do humano que possui aquele número de seguridade social. Pares também devem ser capazes de inserir duplas (chave, valor) em nosso banco de dados.

A construção desse banco de dados é direta com uma arquitetura cliente-servidor na qual todos os pares (chave, valor) são armazenados em um servidor central. Essa abordagem centralizada também foi considerada em antigos sistemas P2P como o Napster. Mas o problema é significativamente mais desafiador e interessante em um sistema distribuído que consiste de milhões de pares conectados sem autoridade central. Em um sistema P2P, queremos distribuir as duplas (chave, valor) entre todos os pares, de forma que cada par tenha apenas um pequeno subconjunto da totalidade dos pares (chave, valor). Uma abordagem inocente para a construção desse banco de dados P2P é (1) espalhar aleatoriamente as duplas (chave, valor) entre os pares e (2) fazer com que cada par tenha uma lista dos endereços de IP de todos os pares participantes. Dessa forma, o par solicitante pode enviar uma solicitação a todos os outros pares, e os pares que tenham duplas (chave, valor) que correspondam à chave podem responder com as duplas correspondentes. Essa abordagem é completamente não escalável, logicamente, visto que cada par precisaria rastrear todos os outros pares (possivelmente milhões) e, pior, enviar cada solicitação a todos os pares.

Agora descreveremos uma abordagem elegante para um projeto de banco de dados P2P. Para isso, primeiro designaremos um identificador a cada par, em que cada identificador é um número inteiro na faixa [0, 2n – 1] de algum n fixo. Observe que cada identificador pode ser expresso por uma representação com n-bits. Vamos também exigir que cada chave seja um número inteiro na mesma faixa. O leitor astuto pode ter observado que as chaves de exemplo descritas anteriormente não são (números de seguridade social e nomes de conteúdo) números inteiros. Para criar números inteiros a partir dessas chaves, precisaremos usar uma função hash que mapeie cada chave (por exemplo, número de seguridade social) em um número inteiro na faixa [0, 2n – 1]. Uma função de hash é uma função de muitos-para-um para a qual duas entradas diferentes podem ter a mesma saída (mesmo número inteiro), mas a probabilidade de terem a mesma saída é extremamente pequena (leitores não familiarizados com funções de hash podem querer consultar o Capítulo 7, que discute detalhadamente funções de hash). A função de hash é considerada publicamente disponível a todos os pares no sistema. Portanto, quando nos referimos à “chave”, nos referimos ao hash da chave original. Portanto, por exemplo, caso a chave original seja “Led Zeppelin IV”, a chave será o número inteiro que corresponda ao hash de “Led Zeppelin IV”. Além disso, como estamos usando hashes de chaves, em vez das próprias chaves, nos referiremos ao banco de dados distribuído como Distributed Hash Table (DHT).

Consideraremos agora o problema de armazenar as duplas (chave, valor) no DHT. A questão central aqui é definir uma regra para designar chaves a pares. Considerando que cada par tenha um identificador de número inteiro e cada chave também seja um número inteiro na mesma faixa, uma abordagem natural é designar cada dupla (chave, valor) ao par cujo identificador está mais próximo da chave. Para implementar esse esquema, precisaremos definir o que significa ‘mais próximo’, o que admite muitas convenções. Por conveniência, definiremos que o par mais próximo é o sucessor imediato da chave. Para visualizarmos, observaremos um exemplo específico. Suponha que n = 4, portanto, todos os identificadores de par e chave estarão na faixa de [0, 15]. Suponha ainda que haja oito pares no sistema com identificadores 1, 3, 4, 5, 8, 10, 12 e 15. Finalmente, suponha que queiramos armazenar o par chave-valor (11, Johnny Wu) em um dos oito pares. Mas em qual? Usando nossa convenção de mais próximo, como o par 12 é o sucessor imediato da chave 11, armazenaremos, portanto, a dupla (11, Johnny Wu) no par 12 [para concluir nossa definição de mais próximo, caso a chave seja exatamente igual a um dos identificadores do par, armazenaremos o par (chave-valor) em um par correspondente; e caso a chave seja maior do que todos os identificadores de par, usaremos uma convenção módulo-2n , que armazena o par (chave-valor) no par com o menor identificador].

Suponha agora que um par, Alice, queira inserir uma dupla (chave-valor) no DHT. Conceitualmente, é um processo objetivo: ela primeiro determina o par cujo identificador é o mais próximo da chave; então ela envia uma mensagem a esse par, instruindo-o a armazenar a dupla (chave, valor). Mas como Alice determina o par mais próximo da chave? Se Alice rastreasse todos os pares no sistema (IDs de par e endereços IP correspondentes), ela poderia determinar localmente o par mais próximo. Mas essa abordagem requer que cada par rastreie todos os outros pares no DHT — o que é completamente impraticável para um sistema de grande escala com milhões de pares.  

ATIVIDADE DE FIXAÇÃO