분산 해시 테이블

DHT의 개념도

분산 해시 테이블(distributed hash table, 줄여서 DHT)은 해시 테이블과 유사한 룩업 서비스를 제공하는 분산 시스템이다.(키-값 쌍이 DHT에 저장되며 특정 노드는 효율적으로 주어진 키와 관련된 값을 검색할 수 있다)

어떤 항목을 찾아갈 때 해시 테이블을 이용하는데, 중앙 시스템이 아닌 각 노드들이 이름을 값으로 맵핑하는 기능을 하는 방식이다. 부하가 집중되지 않고 분산된다는 큰 장점이 있어, 극단적으로 큰 규모의 노드들도 관리할 수 있다.

DHT는 순수 P2P라도 네트워크의 부하를 억제할 수 있으며 네트워크 상의 콘텐츠를 빠르고 정확히 검색할 수 있는 것이 가능하다. 종래의 순수 P2P에서 채용되었던 방식에서는 수십만 노드 정도가 한계였으나, DHT의 사용으로 수십억개의 노드를 검색범위로 할 수 있게 되었다. 그러나 DHT는 실제 구현이 어렵다. 특히 완전한 일치검색만이 가능하여, 와일드 카드 등을 활용한 복잡한 검색을 하지 못하는 단점이 있다.

DHT를 활용한 대표적인 시스템으로 비트토렌트(DHT를 확장하여 사용), eDonkey 등이 있다.

종류

본 기술은 P2P 네트워크에 특히 많이 사용되는데, P2P 네트워크는 냅스터 같은 하이브리드 P2P와 누텔라 같은 순수 P2P로 나뉜다.

하이브리드형은 콘텐츠와 콘텐츠가 배치되는 각 노드의 주소를 중앙의 서버가 목록화하여 관리함으로써 검색 기능을 제공한다. 그러나 중앙의 서버가 개별 노드와 콘텐츠를 관리하게 되므로 서버 관리에 많은 비용이 들어간다.

순수형은 중앙 서버가 없고 개별 노드가 애드 혹 방식으로 서로 접속하는 형태를 취한다. 이 형태는 사용자가 늘어남에 따라 네트워크의 데이터 유동량(트래픽)이 늘어나고, 네트워크 상의 콘텐츠를 찾기가 어려워진다는 단점이 있다.

속성

분산 해시 테이블은 특질상 다음 속성들이 두드러진다.

• 자율성과 탈중앙화 : 노드들은 어떠한 중앙 조정 없이 집합적으로 시스템을 형성한다.
• 장애 허용 : 시스템은 노드들이 지속적으로 추가, 제거, 고장나더라도 신뢰할 수 있어야한다.
• 확장성 : 시스템은 수천 또는 수백만 개의 노드에서도 효율적으로 작동해야한다.

이러한 목표를 달성하는 데 사용되는 핵심 기술은 각 노드가 소수의 노드와 조율이 필요하게 만들어 구성원이 바뀔 때마다 제한된 양의 작업만 필요하게 만드는 것이다.

일부 분산 해시 테이블은 악의적인 참가자로부터 보안을 유지하고 참가자가 익명을 유지하도록 하지만 이는 일반적인 경우가 아니다.

결론적으로 분산 해시 테이블은 반드시 부하분산, 데이터 무결성, 성능과 같은 전통적인 분산 시스템의 문제를 처리해야한다.

구조

분산 해시 테이블의 구조는 몇개의 주요 구성 요소로 나뉠 수 있다. 추상 키 스페이스를 기반으로 한다. 키 영역 분할 계층은 참여하는 노드들에 걸쳐 키 영역의 소유권을 나눈다. 오버레이 네트워크는 노드들을 연결하고 이들이 키 스페이스에서 키의 소유자를 찾게 해준다.

키 스페이스 분할

대부분의 분산 해시 테이블은 키를 노드에 매핑하기 위해 일관된 해싱 또는 랑데부 해싱의 변형을 사용한다.

일관된 해싱

 일관된 해싱 문서에 이 부분의 추가 정보가 있습니다.

랑데부 해싱

 랑데부 해싱 문서에 이 부분의 추가 정보가 있습니다.

지역 보존 해싱

 지역 보존 해싱 문서에 이 부분의 추가 정보가 있습니다.

오버레이 네트워크

각 노드들은 이웃 노드들과의 연결을 유지하고 오버레이 네트워크를 통한 연결도 함께 유지한다. 노드들은 네트워크 토폴로지에 따라 이웃 노드를 선택한다.

모든 분산 해시 테이블은 가장 기초적인 속성을 공유한다. 어떤 키 k에 대해 각 노드들은 k를 소유하는 노드 아이디를 가지거나 키 스페이스에서 정의된 거리가 k에 더 가까운 아이디를 가진 노드에 대한 연결을 가진다. 이는 다음과 같은 탐욕 알고리즘을 이용하여 메시지를 k의 소유자에게 전달하기 쉽게 만들어준다. 각 단계에서 k에 가장 가까운 아이디를 가진 이웃에게 전달한다. 이러한 스타일을 키 기반 라우팅이라 한다.

기초적인 라우팅을 넘어, 토폴로지에서 두가지 중요한 제약은 홉의 갯수를 낮추는 것(처리 속도를 빠르게 하는 것)과 이웃 노드의 숫자를 낮추는 것(유지 비용을 낮추는 것)이다. 당연하게도 짧은 경로는 높은 최대 차수를 요구한다. m개의 노드에 대해 최대 차수와 라우트 길이에 대한 일반적인 선택들은 다음과 같다.

그래프 차수	탐색 횟수	사용 기법	참고
$O(1)$	$O(n)$		가장 느린 조회
$O(\log n)$	$O(\log n)$	Chord Kademlia Pastry Tapestry	가장 일반적이나, 최적은 아니다. Chord는 가장 기초적인 버전이며, Kademlia가 가장 인기 있는 최적화된 변형으로 보인다.
$O(\log n)$	$O(\log n/\log(\log n))$	Koorde	구현하기에는 더 복잡할 수 있으나, 조회 속도가 좀 더 빠를 수 있다.
$O({\sqrt {n}})$	$O(1)$		가장 많은 공간을 사용, 노드의 추가 또는 제거 후 많은 통신이 발생한다.