Kademlia 편집하기

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

[[파일:Kademlia.png|800x800픽셀]]
==개요==
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.
==각주==
<references />
[[분류:네트워크]]