[네트워크] Ch3.2 DHT(Distributed Hash Table)

 

본 글은 학교 네트워크 수업을 들으며, "Computer Networking: A Top-Down Approach 8ed(컴퓨터 네트워킹: 하향식 접근 제8판)"을 기반으로 공부한 내용을 정리한 글입니다.

 

Ch3.2 DHT(Distributed Hash Table)

DHT는, 가장 단순한 형태의 P2P 구현임.

현재 널리 사용되는 P2P 기술들은 DHT를 변형한 것.

Simple Database

- `(key, value) pair`을 가진 단순한 데이터베이스를 먼저 생각해보자.

- 유저는 key를 가지고 DB를 쿼리하고, DB는 대응되는 value를 return함.

ex. `(cuffyluv, 123-45-6789)` // (name, social number)

Distributed Database on P2P

- P2P에서는 분산된 데이터베이스가 사용됨.

- 이 때, key에는 `검색용으로 쓰일 content 이름`, value에는 `peer 정보(IP address, port number, ...)`가 들어감.

- peer 정보란, 해당 content를 가지고 있는 peer의 IP address 따위를 말함.

- `(content name, peer Information)` 꼴인 것.

Hash Function

- 우리가 쓰는 key는 가변 길이의 content name이 들어가니까, 관리가 복잡해진다.

- 그러니, key를 `고정 길이의 수(=hash value)`로 표현해보자.

ex. `cuffyluv -> 12312543`, `XiaomingLiu -> 56435432`

- hash function에 대한 자세한 내용은 자료구조 시간에 공부한 걸 참고하자. 

 

Hash function's uniformity

- hash function은 기본적으로 output range가 비슷한 확률을 가지도록 설계해야함. (이건 당연)

- 만약 `hash table의 bucket 개수 >> hash function에 들어올 input 개수`이면, hash table이 충돌할 가능성은 0에 수렴함.

=> 따라서, 우리의 hash function은 동일한 key를 가지지 않는다고 간주할 수 있음.

DHT

- 각각의 peer들은 적은 수의 타 peer들에 대해서만 알고 있음.

- peer들은 key를 가지고 query를 할 수 있고, 그러면 DB는 대응되는 value를 return해줌.

- 위의 예시를 보면, peer 12는 오직 peer 1과 13에 대해서만 알고 있음. 이 때 peer 13을 peer 12에 대한 `immediate successor`, peer 1을 peer 12에 대한 `immediate predecessor` 이라고 부름.

Assign key-value pairs to peers

- 각각의 peer들은 그들 고유의 unique한 ID를 가지고 있음.

- ID는 랜덤하게 생성되는데, 이는 key를 만드는 데 쓰이는 비트 수와 같은 비트 수를 가짐.

- 이렇게 되면, ID에 쓰이는 bits = m이라 할 때, `0, 1, ..., 2^m -1 -> infinity` 이므로, 사실상 ID는 중복되지 않는다고 간주할 수 있다.

 

- 이 때, `(key, value) pair`을, ID값이 해당 key와 가장 가까운 peer에다가 할당해 줌.

- 해당 key의 immediate successor에게 할당해준다고 생각하면 됨.

 

간단한 예시)

- ID가 6 bits로 이루어져 있을 때, 가능한 ID는 0부터 63 까지임.

- 8개의 peer ID를 이제 무작위로 뽑았더니 위와 같았다고 하자.

- 그럼 key = 45인 어떤 content는, ID = 48인 peer에게 저장하면 된다.

- 이제, 각각의 peer들은 오직 자신의 immediate successor에 대해서만 알고 있다고 가정해보자.

- 즉, peer 1은 자신의 다음 peer의 ID가 12라는 것(또는, 자신의 다음 peer는 peer 12라는 것)만 알고 있다.

- 그리고, peer 1이 key = 45인 file을 가지고 있는 상황이라고 해보자.

 

- 이 때, `(45, 1), 즉 'peer 1이 key = 45인 file을 가지고 있다는 정보'`는 어디에 저장되어야 할까?

=> key 45의 immediate successor인 peer 48에 저장된다.

- 이 때, peer 13이 그 파일을 원하는 상황이라고 해보자. 그러면 peer 13은 그 파일이 key 45에 대응된다는 걸 당연히 알고 있다.

- 이제 peer 13은 `key 45인 (key, value) pair`이 어느 peer에 있는지 순차적으로 query한다.

- 이 message에는 peer 13의 IP address가 있기에, peer 48의 차례에서 (45, 1)이 peer 13한테로 바로 return되고,

- peer 13은 이제 peer 1에게 해당 파일이 있다는 걸 알게 됐다.

- 따라서 해당 파일을 peer 1에게 달라고 요청을 보내고,

- peer 1이 해당 파일을 peer 13에게 전송하면서 파일을 받게 된다.

- 이제, peer 13 또한 해당 파일을 가지게 되었다. 그러면 이 사실을 다른 peer들도 알 수 있게끔 해야하지 않겠나?

- 그렇기에, `(45, 13) 즉 나 peer 13도 key 45인 파일을 가지고 있다는 정보`를, peer 48에게 보내 저장시킨다. 

- 이는 peer 13이 이전 과정에서 이미 peer 48을 알고 있기 때문에 한 번에 전송이 가능하다.

- 이 때, peer 25가 나도 그 파일 가지고 싶다고 한다.

- 그러면 peer 25는 key 45를 쿼리할 것이다.

- 그러면 peer 48에서 `(45, 1)과 (45, 13)`이 return될 것이고,

- 이제 peer 25는 peer 1과 13에게 해당 파일을 달라고 요청할 것이다.

- 그럼 이제 peer 1과 peer 13이 자기가 가진 파일의 절반의 piece씩을 peer 25에게 전송하고,

- 따라서 peer 25는 이전 사례에 비해 절반의 시간만으로 해당 파일을 받을 수 있게 된다.

- 그리고 이제 peer 25가 '나도 key 45인 파일 가지고 있어!' 라고 알려주기 위해, 

- (45, 25)를 peer 48에게 보내 저장시킨다.

- 이제 다른 peer들이 해당 파일을 요청하게 되더라도, 첫 사례의 1/3 시간만으로 해당 파일을 받을 수 있게 된다.

 

- 그래서 peer가 늘어나면 여러 곳에서 request 하니까 소요 시간이 약간 늘어나긴 하지만, 기본적으로 하나의 peer가 해당 파일을 download하는 데 걸리는 시간 자체는 줄어들 수 있다.