분산 해시 테이블

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

분산 해시 테이블(DHT)은 초기 P2P 시스템의 한계를 극복하기 위해 개발된 기술로, 자율성, 탈중앙화, 장애 허용, 확장성을 특징으로 한다. DHT는 키 스페이스 분할과 오버레이 네트워크를 사용하여 데이터를 저장하고 검색하며, 일관성 해싱, 랑데부 해싱, 지역 보존 해싱 등의 구조를 활용한다. DHT는 비구조적 오버레이 네트워크와 달리 키에 의해 논리 공간상의 같은 위치를 탐색하는 분산 알고리즘을 사용하며, 보안, 라우팅 알고리즘, 다양한 구현 방식을 가진다. DHT는 비트토렌트, 파일 공유, 콘텐츠 배포, 분산 데이터 저장, 검열 저항 네트워크, 웹 검색 엔진 등 다양한 분야에서 활용된다.

더 읽어볼만한 페이지

분산 자료 구조 - I2P
I2P는 2003년 Freenet에서 분기된 익명 P2P 분산 통신 계층으로, IP 주소 노출을 방지하며 다양한 소프트웨어와 익명성 응용 프로그램을 지원하고, 기부금으로 운영되며 6~8주마다 릴리스를 진행한다.
분산 자료 구조 - 카뎀리아
카뎀리아는 분산 해시 테이블 기반 P2P 네트워크 프로토콜로, 고정 크기 라우팅 테이블과 XOR 거리 계산을 통해 효율적인 노드 검색 및 정보 접근성을 제공하며, I2P, 이더리움, 비트토렌트 등 다양한 분산 네트워크와 응용 프로그램에서 활용된다.
해시 자료 구조 - I2P
I2P는 2003년 Freenet에서 분기된 익명 P2P 분산 통신 계층으로, IP 주소 노출을 방지하며 다양한 소프트웨어와 익명성 응용 프로그램을 지원하고, 기부금으로 운영되며 6~8주마다 릴리스를 진행한다.
해시 자료 구조 - 토르 (네트워크)
토르(Tor)는 사용자의 익명성을 보장하고 온라인 활동을 보호하기 위해 개발된 네트워크로, 암호화된 통신을 여러 노드를 거쳐 전송하며 검열 우회, 언론의 자유를 위한 도구로 활용되지만 범죄에도 악용될 수 있다.
검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.

분산 해시 테이블
개요
분산 해시 테이블의 예시. 각 노드는 키 공간의 일부를 담당한다. 키는 먼저 책임 노드에 해시되고, 다음으로 해당 값에 매핑된다.
유형	분산 시스템
설계 목표	분산, 확장성, 내결함성
상세 정보
관련 주제	해시 테이블 피어 투 피어 분산 컴퓨팅 일관성 해싱

2. 역사

DHT 연구는 초기 P2P 시스템의 한계를 극복하기 위해 시작되었다. 냅스터와 같은 하이브리드 P2P 시스템은 중앙 서버를 사용하여 콘텐츠와 각 노드의 주소를 관리했다. 이 방식은 서버 관리에 많은 비용이 들고, 중앙 서버가 공격받거나 소송에 휘말릴 경우 시스템 전체가 취약해지는 단점이 있었다.^[3]

누텔라 같은 순수 P2P 시스템은 중앙 서버 없이 애드 혹 방식으로 노드들이 서로 접속했다. 그러나 사용자가 늘어날수록 네트워크 트래픽이 증가하고 콘텐츠를 찾기 어려워지는 문제가 발생했다. 초기 누텔라 클라이언트는 쿼리 플러딩 모델을 사용하여 검색 메시지를 네트워크의 모든 노드에 보내는 방식으로 작동했는데, 이는 단일 실패 지점은 피했지만 매우 비효율적이었다.^[4]

프리넷은 완전 분산형 시스템으로, 각 파일에 키를 할당하고 유사한 키를 가진 파일들을 비슷한 노드에 클러스터링하는 휴리스틱 키 기반 라우팅을 사용했다. 이 방식은 쿼리를 효율적으로 라우팅할 수 있었지만, 데이터 발견을 보장하지는 않았다.^[5]

DHT는 프리넷과 누텔라의 분산화, 냅스터의 효율성과 결과 보장을 모두 얻기 위해 보다 구조화된 키 기반 라우팅을 사용한다.^[6] 2001년에는 CAN,^[7] Chord,^[8] Pastry, Tapestry 등 네 가지 시스템이 DHT를 주요 연구 주제로 만들었다.

2002년에는 미국 국립 과학 재단에서 1200만달러를 지원받아 복원력 있는 인터넷 시스템을 위한 인프라(Iris) 프로젝트가 시작되었다.^[9] 이 프로젝트에는 실비아 라트나사미, 이온 스토이카, 하리 발라크리쉬난, 스콧 쉔커 등이 참여했다.^[10] DHT 기술은 학계뿐만 아니라 비트토렌트와 같은 응용 프로그램에도 채택되었다.^[11]

3. 속성

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

4. 구조

분산 해시 테이블(DHT)은 몇 가지 주요 구성 요소로 나뉜다.^[14]^[15]

추상 키 공간: DHT는 160비트 문자열 집합과 같은 추상적인 키 공간을 기반으로 한다.
키 영역 분할: 키 영역 분할은 참여하는 노드들에 걸쳐 키 영역의 소유권을 나눈다.
오버레이 네트워크: 노드들을 연결하고 이들이 키 공간에서 키의 소유자를 찾게 해준다. 애드혹성과 확장성을 모두 확보하는 탐색 기법으로, 컴퓨터 네트워크 상에 구축되기 때문에 오버레이 네트워크의 일종이라고 할 수 있다.

이러한 구성 요소가 갖춰지면, DHT를 이용한 저장 및 검색은 다음과 같이 이루어진다.

1. 키 공간이 160비트 문자열 집합이라고 가정한다.

2. 주어진 파일 이름() 및 데이터()가 있는 파일을 DHT에 인덱싱하려면, 의 SHA-1 해시를 생성하여 160비트 키 를 만든다.

3. 메시지 를 DHT에 참여하는 모든 노드로 전송한다.

4. 메시지는 키 공간 분할에 지정된 대로 키 를 담당하는 단일 노드에 도달할 때까지 오버레이 네트워크를 통해 노드에서 노드로 전달된다.

5. 해당 노드는 키와 데이터를 저장한다.

6. 다른 클라이언트는 을 다시 해싱하여 를 생성하고, 모든 DHT 노드에 메시지 를 보내 와 관련된 데이터를 찾도록 요청하여 파일의 내용을 검색할 수 있다.

7. 메시지는 다시 를 담당하는 노드로 오버레이를 통해 라우팅되며, 이 노드는 저장된 로 응답한다.

DHT는 서버 집합으로 구성되며, 주요 기능은 해시 테이블과 동일하다. 어떤 키(비트열)를 해시 함수 또는 어떠한 직선화 함수에 의해 논리적인 공간의 한 점에 투영하고, 투영된 점에 값을 연관시키는 것을 특징으로 한다. DHT는 높은 확장성을 가진다. 확장성은 DHT에 참여하는 노드 수 N에 대해, 어떤 노드에서 탐색을 시작하더라도 모든 노드에 O(N) 오더보다 좋은 오더(예: Chord 등 대표적인 알고리즘에서는 O(log(N)))의 통신으로 도달 가능한 것이 확률적으로 보장된다는 점에 기인한다.

DHT는 키에 대한 해시 함수 적용 방법, 해시 값을 투영하는 논리 공간 정의, 해시 값을 논리 공간에 투영하는 방법, 분할 정복을 위한 논리 공간 분할 방법, 노드의 공간 투영 방법, 노드로 구성하는 오버레이 네트워크 구성 방법(참가, 탈퇴, 경로 학습 등) 등의 차이에 따라 다양한 특징을 가진다.

4. 1. 키 공간 분할

분산 해시 테이블(DHT)의 기반은 추상적인 키 공간이다. '''키 공간 분할'''은 이 키 공간의 소유권을 참여하는 노드들에게 분배하는 것이다. 대부분의 DHT는 키를 노드에 매핑하기 위해 일관성 해싱 또는 랑데부 해싱의 변형을 사용한다.^[14]^[15]

키 공간 분할 및 오버레이 네트워크 구성 요소는 대부분의 DHT에 공통적이지만, 세부적인 설계는 다양하다.

일관성 해싱과 랑데부 해싱은 모두 노드를 추가하거나 제거할 때 인접 노드의 키만 변경하고 다른 노드에는 영향을 주지 않는 특징을 가진다. 이는 기존의 해시 테이블에서 버킷을 추가/제거할 때 거의 모든 키를 다시 매핑하는 것과 대조적이다. DHT에서 소유권 변경은 객체가 한 노드에서 다른 노드로 이동하는 대역폭 집약적인 작업이므로, 높은 이탈률(노드 도착 및 장애) 환경에서는 이러한 재구성을 최소화해야 한다.^[4]

애드혹성과 확장성을 모두 확보하는 탐색 기법은 컴퓨터 네트워크 상에 구축되므로 오버레이 네트워크의 일종이라고 할 수 있다. DHT는 주소와 콘텐츠의 해시값을 공간에 사상하고, 그 공간을 여러 피어(peer)로 분할 관리함으로써 특정 피어에 부하가 집중되지 않고 대규모 콘텐츠 탐색을 실현한다.

DHT는 높은 확장성을 가지는데, 이는 참여 노드 수 N에 대해 어떤 노드에서 탐색을 시작하더라도 모든 노드에 O(N)보다 좋은 O(log(N))의 통신으로 도달 가능한 것이 확률적으로 보장되기 때문이다. (Chord와 같은 대표적인 알고리즘) 이러한 확장성은 자율 분산적인 알고리즘에 따른 다수의 노드에 의한 해시 테이블 관리를 위한 논리 공간의 분할 정복을 통해 이루어진다.

키에 대한 해시 함수 적용 방법, 해시 값을 투영하는 논리 공간 정의, 분할 방법, 노드의 공간 투영 방법, 오버레이 네트워크 구성 방법 등의 차이에 따라 다양한 DHT가 존재한다.

4. 1. 1. 일관된 해싱

분산 해시 테이블은 키를 노드에 매핑하기 위해 주로 일관성 해싱 또는 랑데부 해싱의 변형을 사용한다. 이 알고리즘들은 분산 해시 테이블 문제를 해결하기 위해 독립적이면서도 동시에 고안되었다.^[3]

일관성 해싱은 키와 노드 식별자(ID)를 같은 해시 함수를 사용하여 해싱한다. 키와 노드는 해시값에 따라 정렬되며, 각 키는 해시 공간에서 가장 가까운 노드에 할당된다.^[5] 예를 들어, Chord DHT는 노드를 원 위의 점으로 취급하고, 키 공간을 원형으로 분할하여 각 노드에 할당한다.^[6]

이 방식은 노드가 추가되거나 제거될 때, 인접한 노드의 키만 재할당하면 되므로 시스템의 안정성을 높인다. 전통적인 해시 테이블에서 버킷(노드)이 추가/제거될 때 거의 모든 키를 다시 해싱해야 하는 것과 대조적이다.^[4] 높은 이탈률(노드 추가/제거) 환경에서 이러한 재구성을 최소화하는 것은 매우 중요하다.^[4]

4. 1. 2. 랑데부 해싱

랑데부 해싱은 최고 무작위 가중치(HRW) 해싱이라고도 하며, 모든 클라이언트가 동일한 해시 함수 $h()$(미리 선택됨)를 사용하여 키를 사용 가능한 ''n''개의 서버 중 하나와 연결한다.

각 클라이언트는 각 서버에 대해 하나씩 동일한 식별자 목록을 갖는다. 어떤 키 ''k''가 주어지면, 클라이언트는 ''n''개의 해시 가중치를 계산한다. 클라이언트는 해당 키에 대한 가장 높은 해시 가중치에 해당하는 서버에 해당 키를 연결한다. ID $S_x$를 가진 서버는 해시 가중치 $h(S_x, k_m)$이 해당 키에 대한 다른 노드의 해시 가중치보다 높은 모든 키 $k_m$을 소유한다.

일관성 해싱과 랑데부 해싱은 모두 하나의 노드를 제거하거나 추가할 경우 인접한 ID를 가진 노드가 소유한 키의 집합만 변경되고 다른 모든 노드에는 영향을 미치지 않는다는 필수적인 특징을 가지고 있다. 이는 하나의 버킷을 추가하거나 제거할 경우 거의 전체 키 공간이 재매핑되는 전통적인 해시 테이블과 대조된다. 소유권의 변경은 일반적으로 DHT에 저장된 객체가 한 노드에서 다른 노드로 이동하는 대역폭 집약적인 작업에 해당하므로, 이러한 재구성을 최소화하는 것은 높은 이탈률(노드 도착 및 장애)을 효율적으로 지원하는 데 필요하다.

4. 1. 3. 지역 보존 해싱

지역 보존 해싱은 유사한 키를 가진 객체를 인접한 노드에 할당하는 방식이다. 이는 범위 쿼리와 같이 특정 범위의 키를 검색하는 데 효율적이다. 그러나 일관성 해싱과 달리 키(및 부하)가 키 공간과 참여 노드에 균일하게 분산되지 않을 수 있다.

이러한 문제를 해결하기 위해 Self-Chord와 Oscar^[16] 같은 DHT 프로토콜이 개발되었다. Self-Chord는 객체 키를 노드 ID와 분리하고, 군집 지능을 기반으로 한 통계적 접근 방식으로 키를 정렬한다.^[17] 이를 통해 유사한 키를 가진 객체들이 이웃 노드에 저장되어 범위 쿼리를 포함한 검색을 로그 시간 안에 수행할 수 있다. Oscar는 무작위 보행 샘플링을 통해 탐색 가능한 스몰 월드 네트워크를 구축하여 로그 검색 시간을 보장한다.

4. 2. 오버레이 네트워크

분산 해시 테이블(DHT)의 구조는 추상 키 스페이스 기반의 '''키 영역 분할''' 계층과 '''오버레이 네트워크'''로 구성된다. 오버레이 네트워크는 노드들을 연결하여 키의 소유자를 찾도록 돕는다.^[14]^[15]

각 노드는 이웃 노드들과의 연결을 유지하며, 네트워크 토폴로지에 따라 이웃을 선택한다. 모든 DHT는 특정 키(k)에 대해, 해당 키를 소유하는 노드 ID를 가지거나, 키 공간에서 정의된 거리가 k에 더 가까운 ID를 가진 노드와의 연결을 가진다. 이를 통해 탐욕 알고리즘을 사용하여 메시지를 k의 소유자에게 쉽게 전달할 수 있다. 각 단계에서 k에 가장 가까운 ID를 가진 이웃에게 메시지를 전달하는 방식이다.

기본 라우팅 외에 토폴로지에서 중요한 제약은 홉의 갯수를 낮추는 것(처리 속도 향상)과 이웃 노드의 숫자를 낮추는 것(유지 비용 절감)이다. 짧은 경로는 높은 최대 차수를 요구한다.

DHT는 애드혹성과 확장성을 모두 확보하는 탐색(lookup) 기법으로, 컴퓨터 네트워크 상에 구축되기 때문에 오버레이 네트워크의 일종이라고 할 수 있다. 주소와 콘텐츠의 해시값을 공간에 사상하고, 그 공간을 여러 피어(peer)로 분할 관리함으로써 특정 피어에 부하가 집중되지 않고 대규모 콘텐츠 탐색을 실현한다.

4. 2. 1. 라우팅 알고리즘

분산 해시 테이블(DHT)은 특정 키에 대한 메시지를 해당 키를 담당하는 노드로 전달하기 위해 키 기반 라우팅 알고리즘을 사용한다. 일반적으로 사용되는 방식은 탐욕 알고리즘으로, 현재 노드에서 키에 가장 가까운 ID를 가진 이웃 노드에게 메시지를 전달하는 과정을 반복한다. 이러한 라우팅 방식은 키 기반 라우팅이라고도 불린다.^[18]

DHT 토폴로지에서 중요한 제약 조건은 홉 수를 최소화하여 빠른 처리를 가능하게 하고, 이웃 노드 수를 줄여 유지 비용을 낮추는 것이다. 일반적으로 짧은 경로는 높은 최대 차수(각 노드가 연결된 이웃 노드의 수)를 요구한다. 일반적인 선택은 n개의 노드에 대해 최대 차수와 라우트 길이를

O(\log n)

으로 하는 것이다.

그래프 차수	탐색 횟수	사용 기법	참고
$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)$		가장 많은 공간을 사용, 노드의 추가 또는 제거 후 많은 통신이 발생한다.

$O(\log n)$ 차수/경로 길이는 최적은 아니지만, 이웃 선택에 유연성을 제공하여 실제 네트워크의 지연 시간을 고려한 이웃 선택을 가능하게 한다. 일반적으로 DHT는 경로 길이와 네트워크 차수를 절충하는 탐색 가능한 작은 세상 네트워크 토폴로지를 구성한다.^[19]

최대 경로 길이는 네트워크의 지름(모든 최단 경로 중 최대 홉 수)과 관련이 있다. DHT는 차수/지름 트레이드 오프에 의해 제한되지만,^[20] 탐욕 알고리즘이 항상 최단 경로를 찾는 것은 아니므로 실제 경로 길이는 지름보다 클 수 있다.^[21]

5. 알고리즘

분산 해시 테이블(DHT)은 다양한 알고리즘을 기반으로 구현될 수 있다. DHT는 서버 집합으로 구성되며, 주요 기능은 해시 테이블과 동일하다. DHT는 어떤 키(비트열)를 해시 함수나 직선화 함수를 통해 논리적인 공간에 한 점으로 투영하고, 그 점에 값을 연결하는 특징을 갖는다. DHT는 높은 확장성을 가지는데, 이는 DHT에 참여하는 노드 수 N에 대해, 어떤 노드에서 탐색을 시작하더라도 모든 노드에 O(log(N))의 통신으로 도달 가능하다는 점에 기인한다(Chord 등 대표적인 알고리즘에서). 이러한 확장성은 자율 분산적인 알고리즘과 다수의 노드에 의한 해시 테이블 관리를 위한 논리 공간의 분할 정복을 통해 실현된다.

분산 해시 테이블 알고리즘은 키에 대한 해시 함수 적용 방법, 해시 값을 투영하는 논리 공간, 해시 값을 논리 공간에 투영하는 방법, 분할 정복을 위한 논리 공간 분할 방법, 노드의 공간 투영 방법, 오버레이 네트워크 구성 방법(참가, 탈퇴, 경로 학습 등)에 따라 다양한 특징을 가진다.

분산 해시 테이블 알고리즘을 특징짓는 가장 큰 요소는 키를 매핑하는 논리 공간과 각 노드가 유지하는 경로 테이블 관리 방법이다.

5. 1. 논리 공간에 따른 분류

DHT 알고리즘은 키를 매핑하는 논리 공간에 따라 분류할 수 있다.

Chord: 닫힌 수직선
CAN: N차원 토러스
Kademlia, P-Grid: 이진 트리
Pastry, Tapestry: 알고리즘
Koorde: De Bruijn 그래프

5. 2. 경로표 관리에 따른 분류

DHT 알고리즘은 경로표(라우팅 테이블)를 관리하는 방법에 따라 분류될 수 있다. DHT 네트워크에 노드가 참여하거나 탈퇴하면 각 노드가 담당하는 부분 공간이 변경되므로, 이에 따라 경로표를 재구성해야 한다. 경로표 관리 방법에 따라 다음과 같이 분류된다.

'''Chord''', '''Pastry''', '''Tapestry''' : 피어가 능동적으로 관리
'''Kademlia''' : 평소의 통신을 통해 관리

6. P2P 시스템과의 비교

DHT는 기존의 P2P 시스템과 비교하여 몇 가지 중요한 차이점을 가진다.

냅스터는 중앙 인덱스 서버를 사용하여 각 노드가 보유한 파일 목록을 관리하고 검색을 수행했다. 이러한 중앙 집중식 구조는 시스템을 공격과 소송에 취약하게 만들었다.^[3]

반면, 그누텔라는 쿼리 플러딩 모델을 사용하여 네트워크의 모든 머신에 메시지를 브로드캐스트하는 방식으로 검색을 수행했다. 이 방식은 단일 실패 지점은 피했지만, 냅스터보다 훨씬 비효율적이었다. 이후 그누텔라 클라이언트들은 효율성을 높이기 위해 동적 쿼리 모델로 전환했다.^[4]

프리넷은 완전 분산형이지만, 휴리스틱 키 기반 라우팅을 사용하여 유사한 키를 가진 파일이 유사한 노드 집합에 클러스터링되도록 하였다. 쿼리는 이러한 클러스터를 통해 라우팅되어 효율성을 높였지만, 데이터 발견을 보장하지는 않았다.^[5]

DHT는 이러한 P2P 시스템들의 장점을 결합하고 단점을 보완하기 위해 개발되었다.

6. 1. 비구조적 오버레이 네트워크

그누텔라와 같은 비구조적 오버레이 네트워크는 쿼리 플러딩 모델을 사용하는데, 이는 각 검색이 네트워크의 모든 머신으로 메시지를 브로드캐스트하는 결과를 낳는다.^[4] 이러한 방식은 단일 실패 지점은 피할 수 있지만, 냅스터보다 훨씬 비효율적이다.^[4] 기존의 그누텔라와 같은 순수 P2P 네트워크는 기본적으로 메시지 플러딩을 이용한 자원 탐색 시스템으로, 파일 공유 시스템처럼 네트워크상에 퍼져 있는 여러 복사본 중 하나의 위치만 알아내면 목적을 달성할 수 있는 경우가 대부분이다.

6. 2. 구조적 오버레이 네트워크

DHT는 구조화된 키 기반 라우팅을 사용하여 프리넷과 그누텔라의 분산화, 냅스터의 효율성과 보장된 결과를 모두 얻는다.^[6] DHT는 확장성을 확보하는 탐색(lookup) 기법으로, 컴퓨터 네트워크 상에 구축되기 때문에 오버레이 네트워크의 일종이라고 할 수 있다.

오버레이 네트워크는 DHT를 사용하는 "구조적 오버레이 네트워크"와 기존의 Gnutella와 같은 Pure P2P를 사용하는 "비구조적 오버레이 네트워크"(비구조화 오버레이 네트워크라고도 함)로 나뉜다.

7. 보안

분산 해시 테이블(DHT)은 분산화, 내결함성, 확장성 때문에 중앙 집중식 시스템보다 악의적인 공격에 더 강하다.^[4]

대규모의 악의적인 공격자에게 강한 분산 데이터 저장소를 위한 개방형 시스템이 가능하다.^[5]

비잔틴 장애 허용을 갖도록 신중하게 설계된 DHT 시스템은 현재 대부분의 DHT 설계에 영향을 미치는 시빌 공격으로 알려진 보안 취약점에 대응할 수 있다.^[6] Whanau는 시빌 공격에 대한 저항성을 갖도록 설계된 DHT이다.^[6]

Kademlia의 최초 저자 중 한 명인 페타르 메이문코프는 시스템 설계에 사회적 신뢰 관계를 통합하여 시빌 공격의 약점을 우회하는 방법을 제안했다.^[7] 새로운 시스템은 코드명 Tonika 또는 도메인 이름 5ttt로도 알려져 있으며 "전기 라우팅"이라고 하는 알고리즘 설계에 기반을 두고 있으며 수학자 조나단 켈너와 공동으로 작성되었다.^[7] 메이문코프는 현재 이 새로운 시스템의 포괄적인 구현 노력을 진행하고 있다.^[7] 그러나 시빌 공격에 대한 효과적인 방어 연구는 일반적으로 열린 문제로 간주되며, 매년 주요 보안 연구 컨퍼런스에서 다양한 잠재적 방어가 제안된다.^[8]

8. 구현

실제 DHT 구현에서 주목할 만한 차이점은 다음과 같다.

주소 공간: DHT의 매개변수이다. 여러 실제 DHT는 128비트 또는 160비트 키 공간을 사용한다.
해시 함수: 일부 실제 DHT는 SHA-1 이외의 해시 함수를 사용한다.
키의 종류: 실제 DHT의 키는 파일의 ''이름'' 해시가 아닌 파일의 ''내용'' 해시가 될 수 있다. 이는 파일 이름을 변경해도 사용자가 파일을 찾는 데 방해가 되지 않도록 내용 주소 지정 가능한 저장소를 제공한다.
데이터 게시: 일부 DHT는 서로 다른 유형의 객체를 게시할 수 있다. 예를 들어 키가 노드가 될 수 있고, 관련된 데이터는 이 노드에 연결하는 방법을 설명할 수 있다. 이를 통해 인스턴트 메신저 응용 프로그램 등에서 자주 사용되는 존재 정보 게시가 가능하게 한다.
중복성: 신뢰성을 향상시키기 위해 중복성을 추가할 수 있다. 키-값 쌍은 키에 해당하는 둘 이상의 노드에 저장될 수 있다.
고급 DHT: Kademlia와 같은 일부 고급 DHT는 먼저 DHT를 통해 반복적인 조회를 수행하여 적절한 노드 집합을 선택하고, 게시된 메시지를 해당 노드에만 전송하여 불필요한 트래픽을 줄인다.
메시지 묶음: 대부분의 시스템에서 메시지를 보내는 것은 로컬 해시 테이블 접근보다 훨씬 더 많은 비용이 들기 때문에, 특정 노드와 관련된 많은 메시지를 단일 배치로 묶는 것이 합리적이다.^[31]

DHT 프로토콜 및 구현체는 다음과 같다.

아파치 카산드라
배턴 오버레이
메인라인 DHT – 비트토렌트에서 사용되는 표준 DHT^[32]
콘텐츠 주소 지정 네트워크 (CAN)
코드
코르드
카데믈리아
페이스트리
P-Grid
리아크
스킬라DB
태피스트리
톰P2P
볼드모트

9. 활용

DHT는 다양한 분야에서 활용되고 있다.

DHT는 본래 프리넷, 그누텔라, 비트토렌트, 냅스터와 같은 P2P 시스템에서 인터넷에 분산된 자원을 활용하여 파일 공유 서비스를 제공하기 위해 연구되었다.^[3] 이러한 시스템들은 데이터를 찾는 방식에 따라 중앙 집중형, 쿼리 플러딩, 휴리스틱 키 기반 라우팅 등의 방식으로 나뉘는데, DHT는 초기 P2P 시스템들의 장점을 결합하여 분산화, 효율성, 결과 보장을 모두 제공한다.

2001년에는 CAN,^[7] Chord,^[8] Pastry, Tapestry의 네 가지 시스템이 DHT를 인기 있는 연구 주제로 만들었다. 2002년에는 미국 국립 과학 재단의 지원을 받아 실비아 라트나사미, 이온 스토이카 등이 참여한 Iris 프로젝트가 진행되었으며,^[9] 학계뿐만 아니라 비트토렌트, 코랄 콘텐츠 배포 네트워크, PlanetLab 프로젝트 등에도 DHT 기술이 채택되었다.^[11]

DHT는 오버레이 네트워크의 일종으로, 애드혹성과 확장성을 모두 확보하는 탐색 기법이다. 주소와 콘텐츠의 해시값을 공간에 사상하고, 그 공간을 여러 피어(peer)로 분할 관리함으로써 특정 피어에 부하가 집중되지 않고 대규모 콘텐츠 탐색을 실현한다. DHT는 기존의 그누텔라와 같은 Pure P2P 네트워크와는 달리, 분산 알고리즘을 사용하여 키에 대응하는 파일을 찾는다.

DHT 연구는 분산 객체 관리를 위한 DOLR(Decentralized Object Location and Routing) 방식과 분산 파일 시스템 연구에서 시작되었으며, 일관성 해싱도 DHT 연구의 원류로 언급된다.

9. 1. 파일 공유

비트토렌트나 eMule과 같은 P2P 파일 공유 시스템은 분산 해시 테이블(DHT)을 이용하여 파일을 검색하고 다운로드한다.^[3] DHT는 프리넷, 그누텔라, 비트토렌트, 냅스터와 같은 P2P 시스템에서 단일 애플리케이션을 제공하기 위해 인터넷에 분산된 리소스를 활용하는 데서 시작되었다.^[3] 특히 증가된 대역폭과 하드 디스크 용량을 활용하여 파일 공유 서비스를 제공했다.^[3]

초기 P2P 시스템인 냅스터는 중앙 인덱스 서버를 사용하여 각 노드가 보유한 파일 목록을 관리하고 검색을 수행했다.^[3] 그러나 이 방식은 중앙 서버가 공격과 소송에 취약하다는 단점이 있었다.^[3]

그누텔라와 같은 네트워크는 쿼리 플러딩 모델을 사용하여 검색 메시지를 네트워크의 모든 머신에 브로드캐스트했다.^[4] 이 방식은 단일 실패 지점은 없었지만, 냅스터보다 비효율적이었다.^[4]

프리넷은 완전 분산형이지만, 각 파일이 키와 연관되고 유사한 키를 가진 파일이 유사한 노드 집합에 클러스터링되는 휴리스틱 키 기반 라우팅을 사용한다.^[5] 그러나 프리넷은 데이터가 발견될 것이라고 보장하지 않는다.

DHT는 프리넷과 그누텔라의 분산화, 냅스터의 효율성과 보장된 결과를 모두 얻기 위해 보다 구조화된 키 기반 라우팅을 사용한다.^[6] DHT는 키워드 검색이 아닌 정확히 일치하는 검색만 지원하며, put하는 노드와 get하는 노드가 키에 의해 논리 공간상의 같은 위치를 탐색하기 위한 분산 알고리즘이며, 어떤 키에 대응하는 파일은 기껏해야 1종류이다.

9. 2. 콘텐츠 배포

분산 해시 테이블(DHT)은 다음과 같은 콘텐츠 배포에 사용된다.

BTDigg: 비트토렌트 DHT 검색 엔진
Codeen: 웹 캐싱
Freenet: 검열 저항 익명 네트워크
GNUnet: Freenet과 유사한 DHT 구현을 포함하는 분산 네트워크
I2P: 오픈 소스 익명 P2P 네트워크
I2P-Bote: 서버리스 보안 익명 이메일
IPFS: 콘텐츠 주소 지정이 가능한 P2P 하이퍼미디어 배포 프로토콜
JXTA: 오픈 소스 P2P 플랫폼
LBRY: Kademlia의 영향을 받은 DHT 시스템을 사용하는 블록체인 기반 콘텐츠 공유 프로토콜
Perfect Dark: 일본의 P2P 파일 공유 애플리케이션
Retroshare: 친구 간 네트워크^[33]
Jami: Kademlia와 유사한 DHT를 기반으로 하는 개인 정보 보호 음성, 영상 및 채팅 통신 플랫폼
Tox: 스카이프를 대체하기 위한 인스턴트 메시징 시스템
Twister: 마이크로블로깅 P2P 플랫폼
YaCy: 분산 웹 검색 엔진

9. 3. 분산 데이터 저장

DHT 연구는 부분적으로 프리넷, 그누텔라, 비트토렌트, 냅스터와 같은 피어 투 피어(P2P) 시스템에 의해 동기 부여되었는데, 이들은 인터넷에 분산된 자원을 활용하여 파일 공유 서비스를 제공했다.^[3]

이러한 시스템들은 피어(peer)에서 제공하는 데이터를 찾는 방식에서 차이를 보였다. 초기 P2P 시스템인 냅스터는 중앙 인덱스 서버를 사용했다. 각 노드는 참여 시 보유한 파일 목록을 서버로 전송하고, 서버는 검색을 수행하여 결과를 가진 노드로 쿼리를 보냈다. 이러한 중앙 집중식 구조는 시스템을 공격과 소송에 취약하게 만들었다.

그누텔라 등은 쿼리 플러딩 모델을 사용했다. 각 검색은 네트워크의 모든 머신으로 메시지를 브로드캐스트하여 단일 실패 지점은 피했지만 냅스터보다 비효율적이었다. 이후 그누텔라 클라이언트는 동적 쿼리 모델로 이동하여 효율성을 높였다.^[4]

프리넷은 완전 분산형이지만, 휴리스틱 키 기반 라우팅을 사용한다. 각 파일은 키와 연관되고, 유사한 키를 가진 파일은 유사한 노드 집합에 클러스터링된다. 쿼리는 많은 피어를 방문하지 않고도 해당 클러스터로 라우팅될 가능성이 높다.^[5] 그러나 데이터가 발견된다는 보장은 없다.

분산 해시 테이블은 프리넷과 그누텔라의 분산화, 냅스터의 효율성과 보장된 결과를 모두 얻기 위해 보다 구조화된 키 기반 라우팅을 사용한다. DHT는 키워드 검색이 아닌 정확히 일치하는 검색만 직접 지원한다. 하지만 프리넷의 라우팅 알고리즘은 근접 연산을 정의할 수 있는 모든 키 유형으로 일반화될 수 있다.^[6]

DHT는 분산 데이터베이스, 분산 파일 시스템 등에서 데이터를 분산 저장하고 관리하는 데 사용된다. 예를 들어, 스토리지 가상화에 사용되는 분산 파일 시스템인 GlusterFS와 콘텐츠 주소 지정이 가능한 P2P 하이퍼미디어 배포 프로토콜인 IPFS 등이 있다.

9. 4. 기타 응용

DHT는 다음과 같은 곳에 응용된다.

프리넷: 검열 저항 익명 네트워크^[3]
I2P: 오픈 소스 익명 P2P 네트워크
Jami: Kademlia와 유사한 DHT를 기반으로 하는 개인 정보 보호 음성, 영상 및 채팅 통신 플랫폼
YaCy: 분산 웹 검색 엔진

참조

_[1] 서적 Distributed Computing and Internet Technology: 9th International Conference, ICDCIT 2013, Bhubaneswar, India, February 5-8, 2013, Proceedings https://books.google[...] Springer 2013-01-11
_[2] 논문 Chord: A scalable peer-to-peer lookup service for internet applications http://pdos.csail.mi[...] 2018-09-18
_[3] 논문 A survey and comparison of peer-to-peer overlay network schemes http://www.cl.cam.ac[...] 2019-09-24
_[4] 논문 Analysis of the impact of dynamic querying models on client-server relationships 2009
_[5] 간행물 Searching in a Small World Chapters 1 & 2 https://freenetproje[...] 2012-01-10
_[6] 간행물 A Distributed Decentralized Information Storage and Retrieval System 2012-01-10
_[7] 논문 A scalable content-addressable network https://dl.acm.org/d[...] 2001-08-27
_[8] 웹사이트 Looking up data in P2P systems http://www.cs.berkel[...] Communications of the ACM 2016-05-19
_[9] 뉴스 New P2P network funded by US government https://www.newscien[...] 2002-10-01
_[10] 뉴스 MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project https://iris.pdos.cs[...] MIT 2002-09-25
_[11] 논문 Democratizing content publication with Coral https://www.scs.stan[...] 2024-05-01
_[12] 웹사이트 Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems https://www.irit.fr/[...] Proc. iiWas, 2010 2022-08-09
_[13] 웹사이트 A Survey of DHT Security Techniques http://www.globule.o[...] ACM Computing Surveys 43(2), January 2011. 2023-06-01
_[14] 웹사이트 Novel Architectures for P2P Applications: the Continuous-Discrete Approach http://www.wisdom.we[...] Proc. SPAA, 2003. 2019-12-09
_[15] 웹사이트 Dipsea: A Modular Distributed Hash Table http://www-db.stanfo[...] Ph. D. Thesis (Stanford University), August 2004. 2004-09-10
_[16] 논문 Structured overlay for heterogeneous environments http://infoscience.e[...] 2020-03-12
_[17] 논문 Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems http://porto.polito.[...] 2019-07-28
_[18] 간행물 Peer to Peer Overlay Networks: Structure, Routing and Maintenance Springer US 2009
_[19] 간행물 Designing peer-to-peer overlays a small-world perspective https://infoscience.[...] EPFL 2019-11-11
_[20] 간행물 The (Degree, Diameter) Problem for Graphs http://maite71.upc.e[...] Maite71.upc.es 2012-01-10
_[21] 웹사이트 "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks" http://citeseer.ist.[...] Proc. STOC, 2004. 2008-04-20
_[22] 웹사이트 Distributed k-ary System: Algorithms for Distributed Hash Tables http://www.sics.se/~[...] KTH-Royal Institute of Technology, 2006. 2007-05-22
_[23] 논문 Should we build Gnutella on a structured overlay? http://nms.lcs.mit.e[...] 2019-09-25
_[24] 논문 Enabling Dynamic Querying over Distributed Hash Tables 2010-12
_[25] 문서 "Towards a scalable and robust DHT"
_[26] 웹사이트 "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary" http://www.cypherpun[...] 2016-07-22
_[27] 문서 "Byzantine agreement for reputation management in DHT-based peer-to-peer networks"
_[28] 웹사이트 Whanau: A Sybil-proof Distributed Hash Table https://pdos.csail.m[...] 2022-01-25
_[29] 서적 Proceedings of the 1st Workshop on Social Network Systems Association for Computing Machinery 2008-04-01
_[30] 논문 Electric routing and concurrent flow cutting https://linkinghub.e[...] 2011-07-22
_[31] 서적 Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox https://www.springer[...] Springer International Publishing 2020-01-22
_[32] 웹사이트 Tribler wiki http://www.tribler.o[...] 2010-12-04
_[33] 웹사이트 Retroshare FAQ http://retroshare.so[...] 2013-07-17
_[34] 간행물 Distributed Hash Table Springer US 2009

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com