DHT의 작동 방식에 대해 설명해 주시겠습니까?
너무 무겁지 않고 기본 만 있습니다.
답변
좋아, 그것들은 기본적으로 아주 간단한 아이디어입니다. DHT는 사전과 유사한 인터페이스를 제공하지만 노드는 네트워크를 통해 분산됩니다. DHT의 비법은 특정 키를 저장하는 노드가 해당 키를 해싱하여 발견되므로 해시 테이블 버킷은 이제 네트워크의 독립 노드입니다.
이것은 많은 내결함성과 신뢰성, 그리고 아마도 성능상의 이점을 제공하지만 많은 두통을 유발합니다. 예를 들어, 노드가 실패하거나 다른 방식으로 네트워크를 떠나면 어떻게됩니까? 그리고 노드가 조인 될 때 키가 어떻게 재분배되어로드가 대략 균형을 잡게됩니까? 어쨌든 어떻게 키를 균등하게 분배합니까? 그리고 노드가 참여할 때 모든 것을 다시 해시하지 않으려면 어떻게해야합니까? 버킷 수를 늘리려면 일반 해시 테이블에서이 작업을 수행해야합니다.
이러한 문제 중 일부를 해결하는 DHT의 한 예는 n 개의 노드의 논리적 링으로, 각각 키 공간의 1 / n을 담당합니다. 네트워크에 노드를 추가하면 링에서 두 개의 다른 노드 사이에 놓일 위치를 찾고 동위 노드의 일부 키를 담당합니다. 이 접근법의 장점은 링의 다른 노드가 영향을받지 않는다는 것입니다. 두 형제 노드 만 키를 재배포해야합니다.
예를 들어, 세 개의 노드 링에서 첫 번째 노드에는 키 0-10, 두 번째 11-20 및 세 번째 21-30이 있습니다. 네 번째 노드가 와서 노드 3과 0 사이에 자신을 삽입하면 (반지됩니다), 3의 키 공간의 절반을 책임질 수 있으므로 이제 26-30을 처리하고 노드 3은 21을 처리합니다 -25.
콘텐츠 기반 라우팅을 사용하여 키를 저장할 올바른 노드를 찾는 다른 많은 오버레이 구조가 있습니다. 링에서 키를 찾으려면 O (n)-홉 라우팅 인 수천 개의 노드 DHT에 문제가있는 로컬 조회 테이블을 유지하지 않는 한 한 번에 한 노드 씩 링을 검색해야합니다. 증강 링을 포함한 다른 구조는 O (log n)-홉 라우팅을 보장하고 일부는 유지 보수 비용이 많이 드는 O (1)-홉 라우팅을 주장합니다.
위키 백과 페이지를 읽고, 조금 더 깊이 알고 싶다면 하버드 (Harvard) 의이 코스 페이지 를 확인 하십시오.
답변
DHT는 일반 해시 테이블과 동일한 유형의 인터페이스를 사용자에게 제공하지만 (키별로 값 조회) 데이터는 임의의 수의 연결된 노드에 분산됩니다. Wikipedia에는 더 많은 글을 쓰면 본질적으로 역류 할 수있는 좋은 기본 소개가 있습니다.
http://en.wikipedia.org/wiki/Distributed_hash_table
답변
일관된 해싱에 대한 통찰력을 얻었으므로 HenryR의 유용한 답변을 추가하고 싶습니다. 정상 / 순시 해시 조회는 두 변수의 함수이며, 그 중 하나는 버킷 수입니다. 일관된 해싱의 장점은 방정식에서 버킷 수 “n”을 제거한다는 것입니다.
순진 해싱에서 첫 번째 변수는 테이블에 저장 될 객체의 키입니다. 우리는 키를 “x”라고 부릅니다. 두 번째 변수는 버킷 수 “n”입니다. 따라서 객체가 저장된 버킷 / 시스템을 결정하려면 hash (x) mod (n)을 계산해야합니다. 따라서 버킷 수를 변경하면 거의 모든 객체가 저장되는 주소도 변경됩니다.
이것을 일관된 해싱과 비교하십시오. “R”을 해시 함수의 범위로 정의 해 봅시다. R은 상수입니다. 일관된 해싱에서 객체의 주소는 hash (x) / R에 있습니다. 조회는 더 이상 버킷 수의 기능이 아니므로 버킷 수를 변경할 때 다시 매핑이 줄어 듭니다.
