DHT; Distributed Hash Table (분산 해시 테이블) 의 개념 (Chord)

0. DHT란?

 

DHT (Distributed Hash Table)은 파일을 공유하는 방법 중 하나이다.

앞서 살펴본 P2P모델의 Gnutella는 중앙 서버가 없지만 속도가 느리다는 단점이 있고, Napster는 중앙 서버가 있어 속도는 빠르지만 중앙 서버의 부담이 크다는 단점이 있었다. DHT는 위의 약점들을 보완할 수 있는 방식으로, Gnutella와 유사하다고 볼 수 있지만, 해시 테이블을 사용해 더 효율적으로 처리한다는 특징이 있다.

자세한 원리를 살펴보자.

 

 

 

1. 해시테이블

 

DHT의 핵심은 해시테이블이다. 해시 함수는 Key와 Value로 구성되어 있고, 해시함수에 Key값을 넣으면 테이블의 index가 나오는 형태이다.

해시 테이블에서 index의 값은 범위가 지정되어 있는 경우가 많은데, 주로 [0, 2^n - 1] 의 범위가 사용된다.

 

우리가 오늘 살펴볼 DHT에서는 Key는 파일명, Value는 파일의 위치를 담고 있다.

 

 

 

2. DHT의 동작 방식

 

DHT에서는 다음과 같은 전제 조건을 가지고 서비스가 제공된다.

 

1) DHT에 참가하는 모든 호스트들의 IP주소를 해시함수에 넣고 돌리면 index 값이 나온다. 이를 index1 이라 하자.

2) 공유할 파일을 해시함수에 넣고 돌리면 index 값이 나온다. 이를 index2 라 하자.

3) index1과 index2값이 같으면, index2에 해당하는 파일의 위치를 index1에 해당하는 호스트가 가지고 있는다.

4) 만약 index2에 해당하는 index1이 없으면, index2 보다 크면서 가장 가까이 있는 index1이 index2에 해당하는 파일의 위치를 가지고 있는다.

5) 각 호스트들은 자신과 인접한 호스트의 IP 주소를 알고 있다.

 

 

말로만 해서는 이해가 안될것이므로 아래의 예시를 살펴보자.

 

 

우선 위의 그림에서 노드의 개수를 보면 알 수 있듯이, 해시 테이블의 index 범위는 [0,7]이다.

그림의 위쪽에 호스트가 총 4개가 있고, 아래쪽에 공유할 파일도 총 4개가 있다.

각각의 호스트들은 파일을 하나씩 들고 있다. 예를 들어 Host1은 'hello.txt'파일을 가지고 있고, Host4는 'practice.pptx' 파일을 가지고 있다.

 

 

이제 앞서 살펴보았던 index1를 구해야 한다. index1은 각 호스트의 IP주소에 해시함수를 적용해 구할 수 있다.

아래 그림처럼 각각의 호스트들이 index를 할당받았다고 가정해보자.

그렇다면 이제 각각의 호스트들은 자신과 인접한 호스트의 IP주소를 알고 있다.

 

 

 

이제 index2를 구해보자. index2는 파일을 해시함수에 적용해 구할 수 있다.

 

 

위의 그림에서 해시함수를 통해 index2를 구했다. 'hello.txt'의 해시함수 결과는 4 이므로 4번 index를 가진 Host3이 'hello.txt'의 위치를 알고 있으면 된다.

'run.avi'의 해시함수 결과는 6인데, 6번 index를 가진 호스트는 없다. 따라서 6번보다 크면서 가장 가까운 7번 index를 가진 Host4가 'run.avi'의 위치를 알고 있으면 된다.

'flower.jpg'의 해시함수 결과는 1인데, 1번 index를 가진 호스트는 없다. 따라서 1번보다 크면서 가장 가까운 2번 index를 가진 Host1이 'flower.jpg'의 위치를 알고 있으면 된다.

 

 

드디어 모든 준비는 끝났다.

 

 

만약 Host1이 'practice.pptx'를 다운받고 싶어한다고 해보자. 우선 해당 파일을 가지고 있는 호스트를 찾아야 할 것이다. Host1은 자신의 다음 호스트인 index 4번의 Host3에게 물어본다.

Host3은 'hello.txt'의 위치만 알고있으므로 자신의 다음 호스트인 index 5번의 Host2에게 물어본다.

Host2는 'practice.pptx'의 위치를 알고 있으므로 질문을 한 Host1에게 파일의 위치를 알려주게 된다.

 

이 과정을 그림으로 나타내면 아래와 같다.

 

 

위와 같은 방법을 통해 호스트끼리 파일을 주고받을 수 있게 된다.

 

 

 

3. 추가적인 정보

 

앞서 DHT의 동작 원리에 대해 살펴보았다. DHT를 이용하면 특정 서버에 부하가 걸리지 않고 잘 분산되어 파일을 공유할 수 있다.

 

하지만, 계속해서 다음 호스트에게 물어봐야 하므로 시간이 오래걸린다는 단점이 있다.

이러한 단점을 개선하기 위해 Shortcut 즉 지름길을 뚫어놓거나 각 호스트마다 finger table을 만들어 관리하기도 한다.

finger table는 더 넓은 범위의 노드들을 어떤 호스트가 담당하고 있는지 쉽게 파악할 수 있도록 해준다.

 

 

오늘 배운 내용을 정리해보면,

 

1. DHT는 해시 테이블을 기본으로 만들어진 파일 공유 서비스이다.

 

2. 해시 함수의 Key에는 파일 이름이, Value에는 파일의 위치가 담겨있다.

 

3. 각 호스트들과 파일들은 해시 함수를 통해 index를 부여받고, 이를 통해 어느 파일이 어느 호스트가 가지고 있는지 알게 된다.

 

4. 더 좋은 성능을 위해 Shortcut이나 finger table을 관리하기도 한다.

 

위 내용은 공부하며 작성한 것으로, 오류가 있을 수 있습니다.