분산 해시 테이블 (DHT)의 간단한 기본 설명
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
누구든지 DHT의 작동 방식에 대한 설명을 할 수 있습니까?
너무 무거워뿐만 아니라 기본 만.
해결책
좋아, 그들은 근본적으로 매우 간단한 아이디어입니다. DHT는 사전과 유사한 인터페이스를 제공하지만 노드는 네트워크 전체에 분산됩니다. DHTS의 트릭은 특정 키를 저장하는 노드가 해당 키를 해싱하여 발견되므로 사실상 해시 테이블 버킷은 이제 네트워크의 독립 노드입니다.
이것은 많은 결함-장애와 신뢰성과 아마도 성능 이점을 제공하지만, 많은 두통을 겪습니다. 예를 들어, 노드가 실패 또는 다른 방법으로 네트워크를 떠날 때 어떻게됩니까? 그리고 노드가 결합 될 때 키를 어떻게 재분배하여 부하가 대략 균형을 이루도록합니까? 생각해보세요. 어떻게 키를 균등하게 배포합니까? 그리고 노드가 결합되면 모든 것을 다시 해치지 않습니까? (버킷 수를 늘리면 일반 해시 테이블 에서이 작업을 수행해야한다는 것을 기억하십시오).
이러한 문제 중 일부를 다루는 DHT는 N 노드의 논리적 링이며 각각 키 공간의 1/N을 책임집니다. 네트워크에 노드를 추가하면 두 개의 다른 노드 사이에 앉을 링의 장소를 찾아 형제 노드의 일부 키에 대해 책임을집니다. 이 접근법의 아름다움은 링의 다른 노드 중 어느 것도 영향을받지 않는다는 것입니다. 두 형제 노드 만 키를 재분배해야합니다.
예를 들어, 3 개의 노드 링에서 첫 번째 노드는 키 0-10, 두 번째 11-20 및 세 번째 21-30을 갖습니다. 네 번째 노드가 나오고 노드 3과 0 사이에 자체적으로 삽입되면 (링 안에 있음을 기억하십시오) 3의 키의 절반에 대한 책임이있을 수 있으므로 이제 26-30 및 노드 3을 다루고 있습니다. -25.
컨텐츠 기반 라우팅을 사용하여 키를 저장할 올바른 노드를 찾는 다른 오버레이 구조가 많이 있습니다. 링에서 키를 찾으려면 한 번에 하나의 노드 씩 반지를 검색해야합니다 (로컬 룩업 테이블을 유지하지 않는 한 수천 개의 노드에 문제가없는 경우). 증강 고리를 포함한 기타 구조는 O (log n) -hop 라우팅을 보증하고 더 많은 유지 보수 비용으로 O (1) -hop 라우팅에 대한 주장.
Wikipedia 페이지를 읽고 약간의 깊이로 알고 싶다면 이것을 확인하십시오. 코스 페이지 하버드에서는 꽤 포괄적 인 독서 목록이 있습니다.
다른 팁
DHT는 사용자와 동일한 유형의 인터페이스를 일반 해시 테이블 (키별로 값을 찾으십시오)을 제공하지만 데이터는 임의의 연결된 노드에 분산됩니다. Wikipedia는 내가 더 많이 쓰면 본질적으로 역류 할 것이라는 좋은 기본 소개를 가지고 있습니다.
일관된 해싱에 대한 통찰력을 가졌기 때문에 Henryr의 유용한 대답을 추가하고 싶습니다. 정상/순진한 해시 조회는 두 변수의 함수이며 그 중 하나는 버킷 수입니다. 일관된 해싱의 아름다움은 방정식에서 "N"의 수를 제거한다는 것입니다.
순진한 해싱에서 첫 번째 변수는 테이블에 저장 될 객체의 키입니다. Key를 "X"라고 부를 것입니다. 두 번째 변수는 버킷 수 "N"입니다. 따라서 객체가 저장된 버킷/기계를 결정하려면 hash (x) mod (n)을 계산해야합니다. 따라서 버킷 수를 변경하면 거의 모든 객체가 저장되는 주소도 변경합니다.
이것을 일관된 해싱과 비교하십시오. "r"을 해시 함수의 범위로 정의해 봅시다. R은 일정합니다. 일관된 해싱에서 객체의 주소는 해시 (x)/r에 있습니다. 우리의 조회는 더 이상 버킷 수의 함수가 아니기 때문에 버킷 수를 변경할 때 리핑이 줄어 듭니다.
체크 아웃 이 위키 백과 기사아니면 이거 파워 포인트 슬라이드
Amazon의 Dynamo를 확인하십시오. Circle 일관성 해싱을 기반으로 간단하지만 새로운 DHT 구현을 설명합니다.
