BT9G LABS / DHT 심층 분석 #02

Kademlia 해설: XOR 거리, 라우팅, BitTorrent DHT가 확장되는 이유

XOR distance, 반복 lookup, 병렬성, k-bucket이 Kademlia형 DHT를 어떻게 확장 가능하게 만드는지 설명합니다.

BT9G Labs게시일 2026-09-163 분 읽기

BT9G Labs / DHT Deep Dive #02. 전체 네트워크를 알지 못해도 소수의 contact만으로 목표 키에 도달하는 Kademlia의 핵심을 살펴봅니다.

Kademlia 해설: XOR 거리, 라우팅, BitTorrent DHT가 확장되는 이유

빠른 요약

주제: Kademlia 해설: XOR 거리, 라우팅, BitTorrent DHT가 확장되는 이유
핵심 키워드: Kademlia, XOR distance, DHT routing, k-bucket, iterative lookup
대상 독자: 백엔드 엔지니어, 프로토콜 연구자, 검색 엔지니어, BitTorrent 구현자
목표: DHT와 BitTorrent의 동작 원리를 실제 크롤러, 인덱싱, 검색 아키텍처 설계에 활용할 수 있을 정도로 정확하게 설명합니다.

시스템 뷰

Node IDXOR Metrick-bucketsParallel QueriesTarget

Node ID → XOR Metric; XOR Metric → k-buckets; k-buckets → Parallel Queries; Parallel Queries → Target

왜 XOR 거리가 중요한가

Kademlia는 Node ID와 목표 키를 같은 논리 공간에 놓고 XOR 결과를 거리로 사용합니다. 이 값은 결정적이고 대칭적이며 정렬하기 쉬워서, node가 전체 네트워크를 몰라도 목표에 더 가까운 contact를 선택할 수 있습니다.

이 거리는 지리나 RTT와는 무관합니다. 같은 데이터센터의 두 서버가 ID 공간에서 멀 수 있고, 서로 다른 대륙의 node가 가까울 수도 있습니다.

Lookup이 수렴하는 이유

클라이언트는 routing table에서 목표에 가까운 여러 node를 골라 병렬 질의합니다. 응답으로 더 가까운 node를 얻으면 후보 집합에 추가하고, 아직 질의하지 않은 가장 가까운 node를 다시 선택합니다. 반복할수록 XOR 거리가 줄어들며 결과를 얻거나 더 가까워질 수 없는 상태에 도달합니다.

이 구조 덕분에 각 node는 네트워크 전체 목록 없이도 적은 수의 좋은 contact만 유지하면 됩니다.

k-bucket과 크롤러 설계

Routing table은 XOR 거리 구간별 k-bucket으로 나뉩니다. churn이 큰 P2P 환경에서는 오래 응답해 온 안정적인 node가 단지 새로 관측된 주소보다 가치가 높을 수 있습니다.

Crawler는 routing knowledge, timeout, 병렬도, 중복 질의를 관리해야 하며, RTT 같은 보조 지표를 사용하더라도 Kademlia의 기본적인 '논리적으로 더 가까운 node를 따라간다'는 원칙을 깨지 않아야 합니다.

구현 스케치

def xor_distance(a: bytes, b: bytes) -> int:
    return int.from_bytes(a, 'big') ^ int.from_bytes(b, 'big')

contacts.sort(key=lambda n: xor_distance(n.node_id, target))
closest = contacts[:8]

BT9G Labs 엔지니어링 노트

BT9G 같은 인덱싱 시스템에서는 이벤트 수 자체보다 콘텐츠 식별자, 수명이 짧은 네트워크 관측값, 수집 상태, 검색용 문서를 분리하는 것이 중요합니다. DHT나 Peer에서 얻은 필드에는 출처와 타임스탬프를 남기고, discovery, 연결, handshake, 확장 지원, Metadata 수집, 검증, 저장, 검색 반영을 단계별로 측정해야 실제 병목을 찾을 수 있습니다.

흔한 오해

XOR 거리를 네트워크 지연이나 물리 거리로 해석하는 것.
각 node가 전체 DHT node를 저장해야 한다고 생각하는 것.
routing table 크기만 키우고 contact 품질을 무시하는 것.
병렬 lookup과 timeout의 영향을 무시하는 것.

참고 자료

다음 글: BitTorrent DHT는 Peer를 어떻게 찾을까? Bootstrap부터 get_peers, announce_peer까지 →

이 글은 공개 BitTorrent 프로토콜의 동작을 엔지니어링 및 연구 목적으로 설명하며, 관측된 모든 Swarm이 사용 가능하거나 유효하거나 재배포 허가를 받았음을 의미하지 않습니다.