A Kademlia é uma tabela hash distribuída (DHT) para redes de computadores ponto a ponto descentralizadas projetada por Petar Maymounkov e David Mazières em 2002. Ela especifica a estrutura da rede e a troca de informações através de consultas de nós. Os nós Kademlia comunicam-se entre si usando UDP. Uma rede virtual ou rede sobreposta é formada pelos nós participantes. Cada nó é identificado por um número ou ID de nó. O ID de nó serve não apenas como identificação, mas o algoritmo Kademlia usa o ID de nó para localizar valores (geralmente hashes de arquivos ou palavras-chave).
Para procurar o valor associado a uma determinada chave, o algoritmo explora a rede em várias etapas. Cada etapa encontrará nós que estão mais próximos da chave até que o nó contatado retorne o valor ou não sejam encontrados nós mais próximos. Isso é muito eficiente: como muitas outras s, a Kademlia contata apenas nós durante a busca de um total de nós no sistema.
Outras vantagens são encontradas particularmente na estrutura descentralizada, que aumenta a resistência contra um ataque de negação de serviço. Mesmo se todo um conjunto de nós for inundado, isso terá efeito limitado na disponibilidade da rede, uma vez que a rede se recuperará "tricotando" a rede em torno desses "buracos".
A implementação da I2P da Kademlia é modificada para mitigar as vulnerabilidades da Kademlia, como ataques Sybil.
Segundo Petar Maymounkov, o nome Kademlia deriva de um pico montanhoso na Bulgária e de uma palavra turca que significa "homem de sorte".
Detalhes do sistema Redes ponto a ponto são feitas de nós, por design. Os protocolos que esses nós usam para se comunicar e localizar informações tornaram-se mais eficientes ao longo do tempo. As redes de compartilhamento de arquivos ponto a ponto de primeira geração, como o Napster, dependiam de um banco de dados central para coordenar as pesquisas na rede. Redes ponto a ponto de segunda geração, como a Gnutella, usavam inundação (flooding) para localizar arquivos, pesquisando em cada nó da rede. Redes ponto a ponto de terceira geração, como o BitTorrent, usam tabelas hash distribuídas para procurar arquivos na rede. Tabelas hash distribuídas armazenam localizações de recursos em toda a rede.
A Kademlia usa um cálculo de "distância" entre dois nós. Esta distância é calculada como o ou exclusivo (XOR) dos dois IDs de nó, tomando o resultado como um número inteiro sem sinal. Chaves e IDs de nó têm o mesmo formato e comprimento, portanto, a distância pode ser calculada entre eles exatamente da mesma maneira. O ID de nó é tipicamente um grande número aleatório que é escolhido com o objetivo de ser único para um nó específico (veja UUID). Pode acontecer, e acontece, que nós geograficamente distantes – da Alemanha e da Austrália, por exemplo – possam ser "vizinhos" se tiverem escolhido IDs de nó aleatórios semelhantes.
O XOR foi escolhido porque atua como uma função de distância entre todos os IDs de nó. Especificamente: a distância entre um nó e ele mesmo é zero é simétrica: as "distâncias" calculadas de A para B e de B para A são as mesmas segue a desigualdade triangular: dados A, B e C sendo vértices (pontos) de um triângulo, então a distância de A até B é menor do que (ou igual a) a soma da distância de A até C e da distância de C até B.
Essas três condições são suficientes para garantir que o XOR capture todas as características essenciais e importantes de uma função de distância "real", sendo ao mesmo tempo barato e simples de calcular.
Cada iteração de busca na Kademlia aproxima-se um bit do alvo. Um algoritmo de busca Kademlia básico tem complexidade de , o que significa que para uma rede com nós, levará no máximo etapas para encontrar esse nó.
Tabelas de roteamento de tamanho fixo
Tabelas de roteamento de tamanho fixo foram apresentadas na versão prévia do artigo original e são usadas na versão posterior apenas para algumas provas matemáticas. Uma implementação real da Kademlia não possui uma tabela de roteamento de tamanho fixo, mas sim uma de tamanho dinâmico.
As tabelas de roteamento Kademlia consistem em uma lista para cada bit do ID do nó (por exemplo, se um ID de nó consiste em 128 bits, um nó manterá 128 dessas listas.). Cada entrada em uma lista contém os dados necessários para localizar outro nó. Os dados em cada entrada da lista são tipicamente o endereço IP, porta e ID de nó de outro nó. Cada lista corresponde a uma distância específica do nó. Nós que podem ir para a n-ésima lista devem ter um n-ésimo bit diferente do ID do nó; os primeiros n-1 bits do ID candidato devem corresponder aos do ID do nó. Isso significa que é muito fácil preencher a primeira lista, pois 1/2 dos nós na rede são candidatos distantes. A próxima lista pode usar apenas 1/4 dos nós na rede (um bit mais próximo que a primeira), etc.
Com um ID de 128 bits, cada nó na rede classificará outros nós em uma das 128 distâncias diferentes, uma distância específica por bit.
À medida que os nós são encontrados na rede, eles são adicionados às listas. Isso inclui operações de armazenamento e recuperação e até mesmo ajudar outros nós a encontrar uma chave. Todo nó encontrado será considerado para inclusão nas listas. Portanto, o conhecimento que um nó tem da rede é muito dinâmico. Isso mantém a rede constantemente atualizada e adiciona resiliência a falhas ou ataques.
Na literatura da Kademlia, as listas são referidas como k-buckets (baldes-k). k é um número definido para todo o sistema, como 20. Cada k-bucket é uma lista contendo até k entradas dentro; ou seja, para uma rede com k=20, cada nó terá listas contendo até 20 nós para um determinado bit (uma determinada distância de si mesmo).
Como os possíveis nós para cada k-bucket diminuem rapidamente (porque haverá muito poucos nós que estão tão próximos), os k-buckets de bits inferiores mapearão totalmente todos os nós nessa seção da rede. Como a quantidade de IDs possíveis é muito maior do que qualquer população de nós jamais poderá ser, alguns dos k-buckets correspondentes a distâncias muito curtas permanecerão vazios.
thumb|420px|Partição de rede para o nó 110
Considere a rede simples à direita. O tamanho da rede é 2^3 ou oito chaves e nós no máximo. Existem sete nós participando; os pequenos círculos na parte inferior. O nó em consideração é o nó seis (binário 110) em preto. Existem três k-buckets para cada nó nesta rede. Os nós zero, um e dois (binário 000, 001 e 010) são candidatos para o k-bucket mais distante. O nó três (binário 011, não mostrado) não está participando da rede. No k-bucket do meio, os nós quatro e cinco (binário 100 e 101) são colocados. Finalmente, o terceiro k-bucket pode conter apenas o nó sete (binário 111). Cada um dos três k-buckets está fechado em um círculo cinza. Se o tamanho do k-bucket fosse dois, então o 2-bucket mais distante poderia conter apenas dois dos três nós. Por exemplo, se o nó seis tem o nó um e dois no 2-bucket mais distante, ele teria que solicitar uma busca de ID de nó a esses nós para encontrar a localização (endereço ip) do nó zero. Cada nó conhece bem sua vizinhança e tem contato com alguns nós distantes que podem ajudar a localizar outros nós distantes.
Sabe-se que os nós que estiveram conectados por um longo tempo em uma rede provavelmente permanecerão conectados por um longo tempo no futuro.Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. Technical Report UW-CSE-01-06-02, University of Washington, Department of Computer Science and Engineering, July 2001.Daniel Stutzbach and Reza Rejaie. Understanding Churn in Peer-to-Peer Networks Section 5.5 Uptime Predictability, Internet Measurement Conference, Rio de Janeiro, October, 2006. Devido a essa distribuição estatística, a Kademlia seleciona nós conectados há muito tempo para permanecerem armazenados nos k-buckets. Isso aumenta o número de nós válidos conhecidos em algum momento no futuro e fornece uma rede mais estável.
Quando um k-bucket está cheio e um novo nó é descoberto para esse k-bucket, o nó visto menos recentemente no k-bucket recebe um PING. Se o nó for encontrado ainda vivo, o novo nó é colocado em uma lista secundária, um cache de substituição. O cache de substituição é usado apenas se um nó no k-bucket parar de responder. Em outras palavras: novos nós são usados apenas quando os nós mais antigos desaparecem.
Mensagens de protocolo A Kademlia possui quatro mensagens. PING — Usada para verificar se um nó ainda está vivo. STORE — Armazena um par (chave, valor) em um nó. FIND_NODE — O destinatário da solicitação retornará os k nós em seus próprios buckets que são os mais próximos da chave solicitada. FIND_VALUE — O mesmo que FIND_NODE, mas se o destinatário da solicitação tiver a chave solicitada em seu armazenamento, ele retornará o valor correspondente.
Cada mensagem RPC inclui um valor aleatório do iniciador. Isso garante que, quando a resposta for recebida, ela corresponda à solicitação enviada anteriormente (veja magic cookie).
Localizando nós As buscas de nós podem prosseguir de forma assíncrona. A quantidade de buscas simultâneas é denotada por α e é tipicamente três. Um nó inicia uma solicitação FIND_NODE consultando os α nós em seus próprios k-buckets que são os mais próximos da chave desejada. Quando esses nós destinatários recebem a solicitação, eles olham em seus k-buckets e retornam os k nós mais próximos da chave desejada que eles conhecem. O solicitante atualizará uma lista de resultados com os resultados (IDs de nó) que recebe, mantendo os k melhores (os k nós que estão mais próximos da chave pesquisada) que respondem às consultas. Então, o solicitante selecionará esses k melhores resultados e emitirá a solicitação para eles, e iterará esse processo repetidamente. Como cada nó tem um conhecimento melhor de seus próprios arredores do que qualquer outro nó, os resultados recebidos serão outros nós que estão cada vez mais próximos da chave pesquisada. As iterações continuam até que não sejam retornados nós que sejam mais próximos do que os melhores resultados anteriores. Quando as iterações param, os melhores k nós na lista de resultados são aqueles em toda a rede que estão mais próximos da chave desejada.
A informação do nó pode ser aumentada com tempos de ida e volta, ou RTT. Esta informação será usada para escolher um tempo limite (time-out) específico para cada nó consultado. Quando uma consulta atinge o tempo limite, outra consulta pode ser iniciada, nunca ultrapassando α consultas ao mesmo tempo.
Localizando recursos A informação é localizada mapeando-a para uma chave. Um hash é tipicamente usado para o mapa. Os nós armazenadores terão informações devido a uma mensagem STORE anterior. A localização de um valor segue o mesmo procedimento que a localização dos nós mais próximos de uma chave, exceto que a busca termina quando um nó tem o valor solicitado em seu armazenamento e retorna esse valor.
Os valores são armazenados em vários nós (k deles) para permitir que os nós entrem e saiam e ainda tenham o valor disponível em algum nó. Periodicamente, um nó que armazena um valor explorará a rede para encontrar os k nós que estão próximos do valor da chave e replicará o valor neles. Isso compensa os nós desaparecidos.
Além disso, para valores populares que podem ter muitas solicitações, a carga nos nós armazenadores é diminuída fazendo com que um recuperador armazene esse valor em algum nó próximo, mas fora dos k mais próximos. Esse novo armazenamento é chamado de cache. Desta forma, o valor é armazenado cada vez mais longe da chave, dependendo da quantidade de solicitações. Isso permite que buscas populares encontrem um armazenador mais rapidamente. Como o valor é retornado de nós mais distantes da chave, isso alivia possíveis "pontos quentes" (hot spots). Os nós de cache descartarão o valor após um certo tempo, dependendo de sua distância da chave.