Kademlia

Kademlia는 분산 해시 테이블(DHT, Distributed Hash Table)을 기반으로 하는 피어 투 피어(P2P) 네트워크 프로토콜이다.

개요

Kademlia는 2002년 Petar Maymounkov과 David Mazières가 제안한 P2P 시스템 설계로, 중앙 서버 없이 자율적인 노드 간의 검색 및 데이터 저장을 가능하게 한다. 주로 파일 공유 시스템, 블록체인, IPFS, BitTorrent 등에서 사용된다. Kademlia의 주요 특징은 XOR 거리 기반 라우팅, k-버킷 기반 라우팅 테이블, 병렬 검색 등이다.

주요 구성 요소

노드 ID와 키 공간

각 노드와 데이터 키는 동일한 비트 길이(예: 160비트)의 식별자 공간을 가진다. 노드 간 거리 측정은 XOR 연산으로 계산되며, 이 값이 작을수록 두 노드는 더 가깝다고 판단된다.

라우팅 테이블 (k-버킷)

각 노드는 자신을 기준으로 거리 범위에 따라 k-버킷이라 불리는 여러 개의 버킷을 유지한다. 각 버킷은 해당 거리 범위에 속하는 최대 k개의 노드 정보를 저장하며, 오래된 노드를 우선 유지하는 방식으로 관리된다.

메시지 유형

Kademlia는 다음의 기본 RPC 메시지를 정의한다.

• PING: 노드 생존 여부 확인
• STORE: (키, 값) 쌍 저장 요청
• FIND_NODE: 주어진 ID에 가까운 노드 검색
• FIND_VALUE: 주어진 키의 값을 검색하거나, 없다면 관련 노드 반환

검색 및 저장

노드 탐색

• 1. 검색자는 타겟 ID에 가까운 α개의 노드에게 FIND_NODE 요청을 보낸다.
• 2. 응답 노드로부터 더 가까운 노드들을 받고, 이들을 대상으로 반복 요청한다.
• 3. 더 이상 가까운 노드가 없을 때 탐색 종료된다.

이 탐색 알고리즘의 평균 시간 복잡도는 O(log n)이다.

값 저장

데이터는 키를 기준으로 가장 가까운 k개의 노드에 저장된다. 복제와 캐싱을 통해 내구성과 접근성이 향상된다.

네트워크 참여

새 노드는 부트스트랩 노드를 통해 네트워크에 접속하며, 자기 자신의 ID로 self-lookup을 수행하여 라우팅 테이블을 채운다.

장점

• O(log n)의 빠른 탐색 속도
• 중앙 서버 없는 완전 분산 구조
• XOR 기반 거리 계산으로 간결한 구조
• 장애 허용력 및 자가 복구 메커니즘

한계

• XOR 거리와 실제 네트워크 지연 간 불일치
• Sybil 공격 등 보안 취약점 가능성
• 노드 ID 분포 불균형 시 부하 집중 가능성

응용

• IPFS
• BitTorrent
• Ethereum의 노드 검색 프로토콜
• libp2p 기반 DHT

개념 비교

다른 DHT들과 비교했을 때 Kademlia는 다음과 같은 차이점이 있다.

• XOR 거리 사용으로 대칭적 라우팅 가능
• α개의 노드에 병렬 요청을 통해 탐색 성능 향상
• 오래된 노드 우선 보존 정책을 통한 안정성 확보

같이 보기

• 분산 해시 테이블
• 피어 투 피어 네트워크
• XOR 메트릭
• Chord 프로토콜
• 블록체인 노드 탐색

참고 문헌

• Petar Maymounkov, David Mazières. Kademlia: A Peer-to-peer Information System Based on the XOR Metric. 2002.
• Carolina Monteiro et al. Enriching Kademlia by Partitioning. Protocol Labs Research. 2022.