Kademlia는 XOR 거리를 기반으로 라우팅하여 어떤 피어든 몇 홉 만에 도달할 수 있게 했다

분산형 피어 투 피어 시스템에는 누가 파일을 보유하는지 조회할 인덱스가 없다. 네트워크를 플러딩하는 것은 너무 비싸고, 중앙 트래커는 취지를 무색하게 만든다.

2002년에 나온 Kademlia는 160비트 ID의 비트 단위 XOR을 거리로 정의한다. XOR은 자기 자신의 역이고 대칭이므로, 노드의 라우팅 테이블은 선행 비트가 몇 개나 다른지에 따라 다른 ID들을 나누고, 버킷당 대략 하나의 연락처를 보관한다.

피어를 찾기 위해 노드는 대상에 가장 가까운 알려진 노드에 질의하고, 각 응답은 더 가까운 노드를 가져오므로 탐색 거리는 매 라운드마다 절반으로 줄어든다 — 대략 log n 홉이다. 피어들이 응답하면서 학습하고 가십을 전파하기 때문에 이 시스템은 스스로 치유된다.

XOR을 거리라고 부르면, 각 피어는 누군가에게 가깝다

XOR 거리는 대칭이며, 노드는 각 비트 수준에서 어떤 연락처에 가깝다.

라우팅 테이블은 아주 작게 유지되면서도 도달 범위는 전역적이므로, 모든 노드를 아는 노드는 없다.

각 홉이 거리를 절반으로 줄여 디렉터리 없이 O(log n) 탐색을 가능하게 한다.

조회와 삽입이 노드들에게 피어들에 대해 가르쳐 주므로, 네트워크는 스스로 치유된다.

디렉터리가 없는 네트워크에서는 하나의 메트릭을 정하고 각 노드가 거리 버킷마다 연락처 하나를 유지하게 하라. 그러면 각 노드는 전역 목록 없이 가장 가까운 알려진 이웃을 통해 다른 어떤 노드에도 도달할 수 있다.

Kademlia는 BitTorrent의 DHT, 이더리움, 그리고 많은 파일 공유 네트워크의 조회 프로토콜이 되었다. 대규모 피어 투 피어 시스템에서 조정자 없이 라우팅하는 표준 답안이다.