분산 해시 테이블(DHT)의 핵심, Kademlia란?

블록체인, P2P 파일 공유, 분산 스토리지 시스템 등을 살펴보면 공통적으로 등장하는 단어가 있습니다. 바로 Kademlia입니다. Kademlia는 **분산 해시 테이블(DHT)**의 구현 방식 중 하나로, 분산 네트워크에서 노드와 데이터를 효율적으로 찾을 수 있게 해주는 프로토콜입니다.

이 글에서는 Kademlia의 핵심 개념과 동작 방식, 그리고 왜 이것이 그렇게 중요한지를 알아보겠습니다.

---

Kademlia란?

Kademlia는 2002년에 개발된 P2P 네트워크에서의 효율적인 노드 탐색 및 데이터 조회를 위한 알고리즘입니다. 이 알고리즘은 분산 네트워크에서 데이터를 저장하고 검색할 수 있게 해주며, BitTorrent, IPFS, Ethereum과 같은 여러 프로젝트에서 핵심 기술로 사용됩니다.

---

기본 개념

1. 노드와 키는 모두 160비트 ID를 가짐

• 각 노드는 해시를 통해 생성된 고유한 ID를 갖습니다.
• 데이터(예: 파일이나 트랜잭션) 역시 해시값을 통해 ID를 가짐.

2. XOR 거리

• Kademlia는 노드 ID 간의 거리를 XOR 연산으로 정의합니다.
• 두 ID를 XOR한 결과의 값이 작을수록 두 노드는 논리적으로 더 가깝습니다.
• 예시:
   
  ID A: 10110010
  ID B: 10010010
  XOR: 00100000 → 거리: 32

3. k-buckets

• 각 노드는 다른 노드들을 ID 거리 기준으로 그룹화하여 k-buckets에 저장합니다.
• 가까운 노드는 자주, 먼 노드는 적당히 유지하며 네트워크 부하를 줄이고 안정성을 유지합니다.

---

노드 탐색: 어떻게 작동할까?

1. 검색 시작
   • 찾고자 하는 ID에 대해 XOR 거리 기준으로 가장 가까운 노드들을 찾습니다.
2. 병렬 질의
   • 가장 가까운 노드 α개(보통 3~5개)에게 요청을 보내, 더 가까운 노드를 알고 있는지 묻습니다.
3. 반복
   • 응답으로 받은 더 가까운 노드들에게 다시 요청을 보내며 점점 가까워집니다.
4. 종료
   • 더 이상 가까운 노드를 찾을 수 없을 때까지 반복합니다.

이 과정을 통해 로그(N) 단계의 빠른 탐색이 가능해집니다.

---

Kademlia의 장점

• 비동기 처리: 네트워크 응답이 느려도 다른 노드에 동시에 질의 가능.
• 안정성: 일부 노드가 사라져도 전체 네트워크에는 큰 영향 없음.
• 효율성: 로그 스케일로 탐색 가능 → 대규모 네트워크에 적합.
• 자체 치유(Self-healing): 네트워크 변화에 유연하게 적응.

---

사용 사례

• BitTorrent (DHT 모드): 파일 피어 찾기.
• IPFS: 컨텐츠 주소 기반 저장소에서 컨텐츠 위치 찾기.
• Ethereum (pre-merge): 노드 간의 P2P 메시징.

---

마무리

Kademlia는 단순한 아이디어로 강력한 분산 네트워크를 가능하게 하는 핵심 기술입니다. 블록체인이나 P2P 시스템에 관심이 있다면 반드시 이해하고 넘어가야 할 알고리즘 중 하나입니다.

---

참고자료

• Kademlia 논문: "Kademlia: A Peer-to-peer Information System Based on the XOR Metric"
• IPFS Docs: https://docs.ipfs.tech/
• Ethereum DevP2P: https://github.com/ethereum/devp2p

---