Kademlia DHT: 분산 네트워크에서 효율적인 검색 알고리즘
분산 해시 테이블을 활용한 P2P 네트워크에서의 효율적인 노드 및 데이터 검색 방법
DHT(Distributed Hash Table)란?
분산 해시 테이블은 여러 노드에 걸쳐 키-값 쌍을 분산 저장하는 시스템이다. 중앙 서버 없이도 네트워크 내의 모든 노드가 협력하여 데이터를 저장하고 검색할 수 있게 해준다.
전통적인 중앙집중식 vs DHT
- 중앙집중식: 모든 요청이 중앙 서버를 거쳐야 함
- DHT: 각 노드가 일부 데이터를 담당하며, 분산된 방식으로 검색
Kademlia DHT의 핵심 원리
통합된 식별자 공간
Kademlia에서 가장 중요한 개념은 노드와 데이터를 동일한 식별자 공간에서 취급한다는 것이다.
노드 A: 10101100
파일 X: 10110010
노드 B: 11101010
모든 것이 동일한 길이의 해시값(일반적으로 160비트 또는 256비트)으로 표현되어, 노드를 찾는 방법과 데이터를 찾는 방법이 완전히 동일해진다.
XOR 거리 메트릭
두 식별자 간의 "거리"는 XOR 연산으로 계산한다:
노드 A: 10101100
파일 X: 10110010
XOR 거리: 00011110
XOR 결과값이 작을수록 더 가까운 것으로 간주한다. 이 메트릭은 다음과 같은 수학적 특성을 만족한다:
- 대칭성: d(a,b) = d(b,a)
- 비음성: d(a,b) ≥ 0, d(a,a) = 0
- 삼각부등식: d(a,c) ≤ d(a,b) + d(b,c)
XOR 거리와 트리 구조의 관계
Kademlia 네트워크는 추상적으로 이진 트리로 볼 수 있다:
Root
/ \
0 1
/ \ / \
00 01 10 11
/|\ /|\ /|\ /|\
...
핵심: XOR 거리가 작을수록 트리에서 더 가까운 위치에 있다.
노드 A: 10101100
파일 X: 10110010
XOR : 00011110
위 예시에서 처음 3비트(101)가 동일하므로, 트리에서 3레벨까지는 같은 경로를 따른다. 4번째 비트에서 처음 갈라지므로(A는 0, X는 1), 이들은 트리의 4번째 레벨에서 분리된다. XOR 결과에서 첫 번째 1이 나타나는 위치가 바로 이 분리 지점을 나타낸다.
K-Bucket 라우팅 테이블
거리 기반 버킷 구조
각 노드는 거리별로 분류된 버킷들을 유지한다:
버킷 0: XOR 거리가 [2^0, 2^1) = [1, 2) 범위인 노드들
버킷 1: XOR 거리가 [2^1, 2^2) = [2, 4) 범위인 노드들
버킷 2: XOR 거리가 [2^2, 2^3) = [4, 8) 범위인 노드들
...
버킷 i: XOR 거리가 [2^i, 2^(i+1)) 범위인 노드들
버킷 인덱스 결정: 노드 간 XOR 거리를 계산한 후, 첫 번째 1이 나타나는 비트 위치가 버킷 인덱스가 된다.
XOR 거리: 00011110
첫 번째 1의 위치: 4번째 비트 → 버킷 3에 저장
설계 원리
가까운 노드 우선: 가까운 거리일수록 더 많은 노드 정보를 보관한다. 이는 검색 시 가까운 노드들을 우선적으로 질의하기 때문이다.
점진적 검색과의 일치: 멀리서 시작해서 점점 가까이 좁혀나가는 검색 방식과 라우팅 테이블 구조가 일치한다.
내결함성: 각 거리 범위에서 여러 선택지를 두어 일부 노드가 실패해도 대체할 수 있다.
버킷 관리
버킷 크기 제한: 각 버킷은 k개(보통 20개)의 노드만 저장한다.
LRU 교체 정책: 버킷이 가득 찰 때 가장 오래된 노드에게 ping을 보내서:
- 응답하면 새 노드를 대기 리스트에 추가
- 응답하지 않으면 제거하고 새 노드를 추가
자동 정리: 주기적으로 죽은 노드들을 제거하여 라우팅 테이블을 최신 상태로 유지한다.
반복적 검색 알고리즘
기본 검색 과정
Kademlia의 검색은 **반복적 접근(iterative approach)**을 사용한다:
- 초기화: 자신의 라우팅 테이블에서 목표에 가장 가까운 k개 노드 선택
- 병렬 질의: 선택된 노드들에게 동시에
FIND_NODE메시지 전송 - 응답 수집: 각 노드로부터 더 가까운 노드 목록을 응답받음
- 재정렬: 받은 모든 노드들을 목표와의 거리순으로 정렬
- 수렴 확인: 새로운 후보 노드들 중 가장 가까운 k개 선택
- 반복: 이전 반복보다 더 가까운 노드들이 발견되면 계속, 아니면 종료