DHT(Distributed Hash Table)
✍️DHT란?
- 파일을 공유하는 방법 중 하나이다.
P2P모델은 중앙서버가 없지만 속도가 느리다는 단점이 있고, client-server architecture은 중앙서버가 있지만, 서버 부담이 크다는 단점이 있다.
위 두 모델의 단점을 보완할 수 있는 방식으로 해시 테이블을 사용해 처리한다.
✍️DHT의 동작 방식
DHT는 hash table이므로, <key,value> 형태를 띈다.
key: file명(original key)를 hash함수에 돌려서 나온 key 값을 hash table에 저장한다.
value: 해당 파일이 있던 peer의 위치를 저장한다.
기본적인 동작 원리는:
여러 노드의 peer들이 존재한다. 각 peer들은 자신의 uniq id(어떤수임)를 가지고 있다.
어떤 peer가 file을 가지고 있다면, 그파일을 해쉬함수로 돌려서 나온 key 값(어떤수)과 가장 가깝고 큰 수의 id를 가진 peer에게 hash table을 제공한다.
다음에 다른 peer에서 해당 file을 찾고 싶다면, 다시 파일을 해쉬함수에 넣어 key 값을 구하면, 그 key 값과 가장 가깝고 큰 peer에게 가서 file의 위치를 물어본다.
그러면, 해당 peer는 해쉬 테이블을 return 해주고, 해쉬 테이블 value값이 파일이 있는 peer의 위치이다.
1. storing <key,value> pair
- peer 1이 file "mmcn.mp4"를 가지고 있다.
- "mmcn.mp4"를 hash 함수에 넣어서 key 값을 얻는다.
- 키 값은 28이고, 해당 파일을 가지고 있는 peer는 1이다.
- 따라서, 해쉬 테이블에 (28,1)로 저장이 되고
- key값인 28과 가장 가까운 peer id인 32로 가서 그 해쉬 테이블 값을 준다.
2. searching and get file
- peer 13이 "mmcn.mp4"를 찾는다.
- "mmcn.mp4"를 해쉬 함수에 넣어서 key 값으로 28을 얻었다.
- key 값인 28과 가장 가깝고 큰 peer 32로 가서 hash table 값을 얻어온다.
- peer 32에서 peer 13으로 (28,1)을 return 해준다.
- peer 13은 (28,1)을 보고 peer 1에 파일을 요청한다.
- peer 1이 13에게 파일을 전송해준다.
3. updating(key,value)
- peer 13이 "mmcn.mp4"를 받았다.
- peer 13은 자신이 파일을 받았다는 사실을 peer 32에게 알려준다.
- peer 32는 자신의 DHT에 <28,13>을 저장한다.
4. searching and get file
- peer 25가 "mmcn.mp4"파일을 원한다.
- "mmcn.mp4"를 해쉬함수에 돌리면 key값 28이 나온다.
- 28과 가깝고 큰 32peer로 간다.
- 아까 32peer에 저장한 <28,13>,<28,1>을 return 값으로 peer 25에게 준다.
- peer 25에서 peer13,1에게 파일을 요청한다.
Circular DHT
✍️peer 들이 ID 순서대로 원형태로 이루어져 있다.
✍️각 peer는 바로 전과 후의 DHT를 갖게 되는 구조다. 또한, 몇몇 shortcut(지름길)도 알게 된다.
✍️12 peer는 어떤 파일을 찾을때, 한쪽 방향으로 바로 뒤 peer(successor)에게 물어보게 되고, 일부는 지름길도 사용한다.
✍️ peer는 갑자기 사라질 수도 있고 생성될 수도 있다.
갑자기 사라진다면 앞뒤로 peer를 연결해주면된다.
✍️peer 5가 갑자기 사라졌을때, peer 5를 제외하고 나머지 peer를 앞뒤로 연결했다.
✍️만약에, peer가 새로 들어온다면 어떻게 들어올까?
peer 6이 peer 15에 대한 정보만 있다고 가정하자.
1. 새로운 peer가 추가될때, 먼저 네트워크에 속한 한 피어에게 자신이 추가되고 싶다고 알려야 한다.(JOIN 요청).
2. 원형 구조에서는 peer가 ID순으로 정렬 되어야 하기 때문에, 요청을 받은 15피어는 다른 피어에게 추가 요청을 한다.(forwarding)
3. 6피어가 위치할 피어에게 도달 했을때, 5피어가 6피어에게 5와 8 사이에 위치할 수 있다고 메세지를 보낸다(JOIN ACK).
4. 6피어가 자리로 들어간다.
5. 주변 피어들도 앞뒤 정보를 갱신하게 된다.
