이 기사의 주요 연구는 세분화 알고리즘 코드입니다.
일관된 해싱 알고리즘은 1997 년 MIT에 의해 제안되었습니다 (0 참조). 디자인 목표는 인터넷에서 핫팟 문제를 해결하는 것이 었으며 원래 의도는 잉어와 매우 유사했습니다. 일관된 해싱은 Carp에서 사용하는 간단한 해싱 알고리즘으로 인해 발생하는 문제를 수정하여 DHT가 P2P 환경에 진정으로 적용될 수 있도록합니다.
일관된 해싱은 해싱 알고리즘이 동적으로 변화하는 캐시 환경에서 충족 해야하는 4 가지 적응 조건을 제안합니다.
균형은 해시의 결과가 모든 캐시에 가능한 한 모든 캐시에 분산되어 모든 캐시 공간을 활용할 수 있음을 의미합니다. 많은 해시 알고리즘 이이 조건을 충족 할 수 있습니다.
Monotonity는 일부 컨텐츠가 해싱을 통해 해당 캐시로 발송 된 경우에 새로운 캐시가 시스템에 추가 된 경우를 나타냅니다. 해시의 결과는 원래 할당 된 컨텐츠를 이전 캐시 컬렉션의 다른 버퍼에 매핑하지 않고도 새 캐시에 매핑 할 수 있도록해야합니다.
간단한 해싱 알고리즘은 종종 가장 간단한 선형 해시와 같은 단일성 요구 사항을 충족시킬 수 없습니다.
X → AX + B 모드 (P)
위의 공식에서 P는 모든 캐시의 크기를 나타냅니다. 캐시 크기가 (P1에서 P2로) 변경되면 모든 원래 해시 결과가 변경되므로 단조 요구 사항을 충족시키지 못하는 것은 어렵지 않습니다.
해시 결과의 변경은 캐시 공간이 변경되면 시스템에서 모든 매핑 관계를 업데이트해야 함을 의미합니다. P2P 시스템에서 캐시 변경은 피어가 결합하거나 시스템을 종료하는 것과 같습니다. 이 상황은 P2P 시스템에서 자주 발생하며, 이로 인해 엄청난 컴퓨팅 및 전송 부하가 제공됩니다. 단일성은 해시 알고리즘 이이 상황을 피할 수 있어야합니다.
분산 환경에서는 터미널이 모든 캐시를 볼 수는 없지만 일부 캐시 만 볼 수 있습니다. 터미널이 해싱 프로세스를 통해 컨텐츠를 캐시에 매핑하려는 경우, 다른 터미널로 보이는 캐시 범위가 다를 수 있으므로 해싱의 결과는 일관되지 않습니다. 최종 결과는 동일한 컨텐츠가 다른 단자에 의해 다른 캐시 영역에 매핑된다는 것입니다. 이 상황은 동일한 컨텐츠가 다른 버퍼에 저장되어 시스템 저장 효율을 줄이기 때문에 분명히 피해야합니다. 분산의 정의는 위의 상황의 심각성입니다. 좋은 해싱 알고리즘은 불일치, 즉 분산을 최소화하기 위해 불일치를 피할 수 있어야합니다.
부하 문제는 실제로 다른 관점에서 분산화 문제를보고 있습니다. 다른 터미널은 동일한 컨텐츠를 다른 버퍼에 매핑 할 수 있으므로 특정 버퍼의 경우 다른 사용자가 다른 컨텐츠에 매핑 될 수도 있습니다. 분산과 마찬가지로이 상황을 피해야하므로 우수한 해싱 알고리즘은 버퍼로드를 최소화 할 수 있어야합니다.
표면적으로, 일관된 해싱은 분산 버퍼링 문제를 목표로하고 있지만, 버퍼링을 P2P 시스템의 피어로 생각하고 다양한 공유 리소스 (데이터, 파일, 미디어 스트림 등)로 매핑 된 컨텐츠를 생각하면 실제로 동일한 문제를 설명하고 있음을 알 수 있습니다.
일관된 해싱 알고리즘에서 각 노드 (P2P 시스템의 피어에 해당)에는 무작위로 할당 된 ID가 있습니다. 콘텐츠를 노드에 매핑 할 때는 컨텐츠의 키워드와 노드 ID를 사용하여 일관된 해시 조작을 수행하고 키 값을 얻습니다. 일관된 해싱은 키 값과 노드 ID가 동일한 값 범위에 있어야합니다. 가장 간단한 키 값과 ID는 0000에서 9999의 정수 세트와 같은 1 차원 일 수 있습니다.
키 값을 기반으로 컨텐츠를 저장할 때 컨텐츠는 ID가 키 값에 가장 가까운 ID를 사용하여 노드에 저장됩니다. 예를 들어, 키 값이 1001 인 경우 시스템에 IDS 1000, 1010, 1100이있는 노드가 있으며 컨텐츠는 1000 개의 노드에 매핑됩니다.
쿼리에 필요한 경로를 만들려면 일관성 해시는 각 노드가 업 링크 노드의 위치 정보 (IP 주소)를 저장해야합니다 (ID 값은 자체 노드 중에서 가장 작은 것보다 크다) 및 다운 링크 노드 (ID 값은 자체 노드 중 가장 큰 값보다 작음). 노드가 컨텐츠를 찾아야하는 경우 컨텐츠의 주요 값을 기반으로 업 링크 또는 다운 링크 노드에 쿼리 요청을 시작하기로 결정할 수 있습니다. 쿼리 요청을 수신하는 노드가 요청 된 대상이 있음을 발견하면 쿼리 요청을 시작하는 노드에 확인을 직접 반환 할 수 있습니다. 자체 범위에 속하지 않는 경우 요청을 업 링크/다운 링크 노드로 전달할 수 있습니다.
위에서 언급 한 라우팅 정보를 유지하려면 노드가 시스템에 결합/종료 할 때 인접한 노드는 라우팅 정보를 적시에 업데이트해야합니다. 이를 위해서는 노드가 직접 연결된 다운 링크 노드 위치 정보를 저장할뿐만 아니라 특정 깊이 (N-HOP)에서 간접 다운 링크 노드 정보를 알고 있으며 노드 목록을 동적으로 유지해야합니다. 노드가 시스템을 종료하면 업 링크 노드가 가장 가까운 다운 링크 노드에 직접 연결하려고합니다. 연결이 성공하면 새 다운 링크 노드에서 다운 링크 노드 목록을 얻고 자체 노드 목록을 업데이트합니다. 마찬가지로, 새 노드가 시스템에 추가되면 먼저 자체 ID에 따라 다운 링크 노드를 찾아 다운 링크 노드 목록을 얻은 다음 업 링크 노드에 다운 링크 노드 목록을 수정하여 라우팅 관계를 복원하도록 요청하십시오.
논의하다
일관된 해시는 기본적으로 P2P 환경에서 가장 중요한 문제를 해결합니다. 동적 네트워크 토폴로지에서 스토리지 및 라우팅을 배포하는 방법. 각 노드는 소수의 인접 노드의 정보 만 유지하면되며, 노드가 시스템에 결합/종료하면 소수의 관련 노드만이 토폴로지의 유지 관리에 참여합니다. 이 모든 것이 일관된 해시를 최초의 실제 DHT 알고리즘으로 만듭니다.
그러나 일관된 해싱의 라우팅 알고리즘에는 여전히 단점이 있습니다. 쿼리 프로세스 중에 쿼리 메시지는 O (N) 단계 (O (N)가 N과의 비례 관계를 나타내고 N은 쿼리 노드에 도달하기 전에 시스템의 총 노드 수를 나타냅니다). 시스템이 매우 클 경우 노드 수가 백만을 초과 할 수 있으며 이러한 쿼리 효율성이 사용의 요구를 충족시키기가 어렵다고 상상하기는 어렵지 않습니다. 다른 관점에서, 사용자가 긴 지연을 견딜 수 있더라도 쿼리 프로세스 중에 생성 된 많은 양의 메시지는 네트워크에 불필요한로드를 가져옵니다.
패키지 herotrix; import java.util.collection; import java.util.sortedMap; import java.util.treemap; public classectenthash <t> {// HASH 알고리즘 비공개 최종 해시 uncfunction 해당 해시 unction; // 가상 노드 번호 비공개 최종 int Number -OfRepler; t> (); public consistenthash (Hashfunction hashfunction, int numberofreplicas, collection <t> 노드) {this.hashfunction = hashfunction; this.numberofreplicas = numberofreplicas; for (t node : nodes) {add (node);}} public void add (t node) {for (int i = 0; i <numberofreplicas; i ++) {circle.put (hashfunction.hash (node.tostring ()+i), node)} public void remove (t node) {int i = 0; i ++) {circle.remove (hashfunction.hash (node.toString ()+i));}} // 키 알고리즘 public t public t get (object key) {if (circle.isempty ()) {hash 값 int hash = hashfunction.hash (key); // if (! circle.containskey (hash)) {SortedMap <integer, t> tailmap = circle.tailmap (hash); hash = tailmap.isempty ()? Circle.firstkey () : tailmap.firstkey ();} return circle.get (hash);}}위의 것은 Java Language Serwest Hash 알고리즘 학습 노트 (코드 예제)에 대한이 기사의 전체 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!