138
A
답변
188
좋아, 그들은 기본적으로 매우 간단한 아이디어입니다. DHT는 사전과 같은 인터페이스를 제공하지만 노드는 네트워크를 통해 배포됩니다. DHT의 트릭은 특정 키를 저장하는 노드가 해당 키를 해싱하여 발견된다는 사실입니다. 따라서 해시 테이블 버킷은 이제 네트워크에서 독립적 인 노드입니다.
이렇게하면 많은 내결함성과 안정성을 제공하고 성능상의 이점을 얻을 수 있지만 많은 골칫거리가됩니다. 예를 들어, 노드가 실패하거나 다른 이유로 네트워크를 떠날 경우 어떻게됩니까? 그리고로드가 대략 균형을 이룰 수 있도록 노드가 조인 될 때 어떻게 키를 재배포합니까? 생각 해보니 어쨌든 키를 어떻게 균등하게 분배합니까? 그리고 노드가 조인 할 때, 모든 것을 다시 숨기지 않으려면 어떻게해야합니까? 버킷 수를 늘리면 일반 해시 테이블에서이 작업을 수행해야합니다.
이러한 문제 중 일부를 해결하는 DHT의 예로는 n 노드의 논리적 링이 있는데, 각각 n 키 스트립의 1/n에 대한 책임을집니다. 일단 노드를 네트워크에 추가하면 두 개의 다른 노드 사이에 링의 위치가 나타나며 형제 노드의 일부 키에 대한 책임이 있습니다. 이 방법의 장점은 링의 다른 노드가 영향을받지 않는다는 것입니다. 두 형제 노드 만 키를 재배포해야합니다.
예를 들어 3 노드 링에서 첫 번째 노드는 0-10 키이고 두 번째 노드는 11-20 키이고 다른 세 번째 노드는 세 번째 21-30 키입니다. 네 번째 노드가오고 노드 3과 노드 0 사이에 자신을 삽입하면 (즉, 링에 있음을 기억하십시오), 3의 키 스페이스의 절반을 담당 할 수 있으므로 이제는 26-30을 다루고 노드 3은 21을 처리합니다 -25.
콘텐츠 기반 라우팅을 사용하여 키를 저장할 올바른 노드를 찾는 많은 다른 오버레이 구조가 있습니다. 링에서 키를 찾는 것은 O (n) -hop 라우팅 인 한 번에 한 노드 씩 라운드를 검색해야합니다 (로컬 조회 테이블을 유지하지 않으면 수천 개의 노드가있는 DHT에서 문제가 있음). 증강 된 링을 포함하는 다른 구조는 O (log n) 홉 라우팅을 보장하고, 일부는 O (1) 홉 라우팅에 추가 유지 보수를 요하는 비용으로 청구합니다.
위키 피 디아 페이지를 읽고, 조금 깊이 알고 싶다면 Harvard의 coursepage에서 꽤 독서 목록을 확인하십시오.
9
DHT는 일반 해시 테이블 (키 값을 조회)과 동일한 유형의 인터페이스를 제공하지만 데이터는 연결된 임의의 수의 노드에 분산됩니다. 위키 백과는 내가 쓰는 경우 나는 기본적으로 역류 될 수있는 좋은 기본적인 소개를 가지고 더 -
2
체크 아웃 this Wikipedia article 또는이 powerpoint slide
-2
아마존의 디나모 (Dynamo)를 살펴보면, 원형 일관성 해시를 기반으로하는 단순하면서도 새로운 DHT 구현을 설명합니다.
6
저는 일관된 해싱에 대한 통찰력이 있었기 때문에 HenryR의 유용한 답변에 추가하고 싶습니다. 정상/순진 해시 검색은 두 변수의 함수이며, 그 중 하나는 버킷의 개수입니다. 일관된 해시의 장점은 방정식에서 버킷 개수를 제거한다는 것입니다.
순진 해싱에서 첫 번째 변수는 테이블에 저장할 개체의 키입니다. 우리는 "x"키를 부를 것입니다.두 번째 변수는 양동이의 수 "n"입니다. 따라서 객체가 저장된 버킷/머신을 확인하려면 hash (x) mod (n)을 계산해야합니다. 따라서 버킷 수를 변경하면 거의 모든 개체가 저장되는 주소도 변경됩니다.
일관된 해싱과 비교하십시오. "R"을 해시 함수의 범위로 정의합시다. R은 단지 일정한 것입니다. 일관된 해싱에서 객체의 주소는 hash (x)/R에 있습니다. 조회가 더 이상 버킷 수의 함수가 아니므로 버킷 수를 변경하면 다시 매핑이 줄어 듭니다.
+1 좋은 답변입니다. 세 번째 단락 ("이 문제 중 일부를 다루는 DHT 중 하나는 n 노드의 논리적 링입니다")이 의미하는 바는 Consistent Hashing입니다. 페이스 북이 만든 분산 데이터베이스 인 Apache Cassandra에서 사용 된 정말 흥미로운 주제입니다. 종이에 연결하십시오 (읽을 가치가 있습니다) : http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf – santiagobasulto
이해하기 쉬운 링 기반 조회 프로토콜은 Chord입니다 : http : //pdos.csail.mit.edu/papers/chord:sigcomm01/ – ThomasWeiss
키 - 값이 노드에 저장되는 방법을 자세히 설명해 주시겠습니까? 해시 테이블이나 DB의 형태일까요? –