랑데부 해시

Rendezvous or Highest Random Weight(HRW; 랑데부 $또는$ 최대 랜덤 가중치 $)$ 해시는^[1]^[2] 클라이언트가 가능한n개의 $옵션$ 세트 중 $k개의$ 옵션세트에 분산 합의를 달성할 수 있는 알고리즘입니다.일반적인 어플리케이션은 클라이언트가 어떤 사이트(또는 프록시)에 오브젝트가 할당되어 있는지에 대해 동의해야 하는 경우입니다.

랑데부 해시는 일관된 해싱보다 훨씬 간단하고 일반적이며, 이는 랑데부 해싱의 특수한 경우( $k=1$ $=$ 1 { $display style k=$ 1 $k=1$ 의 경우)가 됩니다.

역사

랑데부 해시는 1996년 ^[1]미시간 대학의 데이비드 탈러와 친야 라비샨카에 의해 발명되었다.일관된 해시는 1년 후에 문헌에 나타났다.

Rendezvous Hashing은 단순하고 일반적이기 때문에 현재 실제 ^[3]^[4]^[5]어플리케이션에서는 일관된 해시보다 선호되고 있습니다.랑데부 해시는 모바일캐싱,^[6] 라우터 설계,^[7] 시큐어 키 확립,^[8] 샤딩 및 분산 데이터베이스 ^[9]등 많은 애플리케이션에서 매우 초기에 사용되었습니다.Github 로드 밸런서는 Rendezvous Hashing을 ^[10]사용합니다.

랑데부 해시의 첫 번째 응용 프로그램 중 하나는 인터넷상의 멀티캐스트클라이언트(MBONE 등의 컨텍스트)가 분산된 ^[11]^[12]방법으로 멀티캐스트 랑데부포인트를 식별할 수 있도록 하는 것이었습니다.1998년 마이크로소프트의 CARP(Cache Array Routing Protocol)에 의해 분산 캐시 조정 및 ^[13]^[14]라우팅에 사용되었습니다.일부 프로토콜 독립 멀티캐스트 라우팅 프로토콜은 랑데부 ^[1]해시를 사용하여 랑데부 포인트를 선택합니다.

개요

알고리즘.

랑데부 해시는 분산 해시 테이블의 문제를 해결합니다. $오브젝트$ O $(\displaystyle$ O $O$ 가 $n$ 주어졌을 때 클라이언트 집합이n개의 $사이트$ (서버 $,$ 예를 들어)에서 O $(\displaystyle$ O $O$ 를 배치하기 위해 어떻게 합의할 수 있습니까? 각 클라이언트는 독립적으로 사이트를 선택하지만 결국 모든 클라이언트가 동일한 사이트를 선택해야 합니다.최소한의 중단 제약 조건을 추가하고 제거된 사이트에 매핑된 개체만 다른 사이트에 재할당해야 하는 경우 이 작업은 중요하지 않습니다.

기본 개념은 각 $S_{j}$ $(\$ 에 $S_j$ $O_{i}$ $(\$ 에 대한 점수(무게)를 부여하고 객체를 가장 높은 점수 사이트에 할당하는 것입니다.모든 클라이언트는 먼저 $h(\cdot )$ h $h(\cdot )$ $h(\cdot )$ $){displaystyle$ h $(\cdot$ 에 동의합니다. 객체 $(\$ ${i})$ 의 경우 $S_{j}$ $S_{j}$ j(\ $displaystyle S_$ ${j$ })의 $w_{i,j}=h(O_{i},S_{j})$ 는 i $w_{i,j}=h(O_{i},S_{j})$ $w_{i,j}=h(O_{i},S_{j})$ $=$ )로 $S_j$ 정의됩니다. $S_{m}$ $(\$ 의 $S_m$ $w_{i,m}$ $w_{i,m}$ $(\$ 이 $w_{i,m}$ 가장 큽니다. $h(\cdot )$ ( $h(\cdot )$ ) { $displaystyle$ h ( \ $cdot$ ) } agreed $h(\cdot )$ agreed agreed agreed agreed 、 1 $w_{i,1},w_{i,2}\dots w_{i,n}$ 、 $w_{i,1},w_{i,2}\dots w_{i,n}$ i 、 $w_{i,1},w_{i,2}\dots w_{i,n}$ $w_{i,1},w_{i,2}\dots w_{i,n}$ $w_{i,1},w_{i,2}\dots w_{i,n}$ i , $w_{i,1},w_{i,2}\dots w_{i,n}$ \ $displaystyle w$ _ { $i$ , $1$ } \ $dots$ w $_$ ${ i$ , $n$ } \ dots w _ { i , n } $w_{i,1},w_{i,2}\dots w_{i,n}$ can $w_{i,1},w_{i,2}\dots w_{i,n}$ can i i i i i i i i i i i i i i i i the $w_{i,1},w_{i,2}\dots w_{i,n}$ the the the the the the the the the 、 1 、 $w_{i,1},w_{i,2}\dots w_{i,n}$ 、 wi , wi , wi , wi , 2 ... wi ,목표가 k $\display$ k-agreement로 $k$ $k$ 되면 클라이언트는 독립적으로 k $\display style$ k의 $k$ 값이 가장 큰 사이트를 선택할 수 있습니다.

$사이트$ S $({displaystyle$ S})를 $S$ 추가 또는 삭제하면 S $({displaystyle$ S})에 $S$ 매핑된 오브젝트만 다른 사이트로 재매핑되므로 위의 최소한의 중단 제약이 충족됩니다.HRW 할당은 $S_{1},S_{2}\dots S_{n}$ $S_{1},S_{2}\dots S_{n}$ $S_{1},S_{2}\dots S_{n}$ ... $(\$ S_ ${1}, S_{2}\dots$ S_ ${n})$ 및 $S_{1},S_{2}\dots S_{n}$ 할당되는 오브젝트의 ID에만 의존하기 때문에 모든 클라이언트에서 독립적으로 계산할 수 있습니다.

HRW는 사이트 간에 다양한 용량에 쉽게 대응할 수 있습니다. $S_{k}$ $(\$ 의 $S_k$ 용량이 다른 사이트보다 2배 클 경우, $S_{k,1},S_{k,2}$ 에서 $S_{k}$ $S_{k,1},S_{k,2}$ $displaystyle$ ${k,1$ }, $S_{k,$ 2 $S_{k,1},S_{k,2}$ 의 $S_k$ 2배는 단순히 $S_{k}$ $S_{k,1},S_{k,2}$ $displaystyle$ $S_{$ k,1}, S_ ${k$ ,2}})로 $S_{k,1},S_{k,2}$ 됩니다.

특성.

먼저 n개의 사이트를 해시 테이블의 버킷으로 처리하고 개체 이름 O를 이 테이블로 해시하는 것으로 충분해 보일 수 있습니다.그러나 사이트에 장애가 발생하거나 연결할 수 없는 경우 해시 테이블 크기가 변경되어 모든 개체를 다시 매핑해야 합니다.이러한 대규모 혼란으로 인해 이러한 직접적인 해시는 작동하지 않습니다.단, 랑데부해시에서는 클라이언트는 다음으로 가중치가 큰 사이트를 선택하여 사이트 장애를 처리합니다.재매핑은 장애가 발생한 사이트에 현재 매핑된 개체에 대해서만 필요하며 중단은 ^[1]^[2]최소화됩니다.

랑데부 해싱에는 다음 속성이 있습니다.

낮은 오버헤드:사용되는 해시 함수는 효율적이기 때문에 클라이언트의 오버헤드는 매우 낮습니다.
로드 밸런싱:해시 함수는 랜덤화되기 때문에 각 n개의 사이트가 오브젝트 O를 수신할 가능성이 동일합니다.로드는 사이트 전체에서 균일합니다.
1. 사이트 용량:용량이 다른 사이트는 용량에 비례하여 여러 개로 사이트 목록에 표시할 수 있습니다.다른 사이트보다 용량이 두 배 큰 사이트는 목록에 두 번 표시되고 다른 사이트는 한 번 표시됩니다.
높은 적중률:오브젝트 O를 같은 사이트S에_O 배치하는 것에 대해 모든 클라이언트가 동의하기 때문에 O를 S에_O 페치 또는 배치하는 것은 히트 레이트의 관점에서 최대의 효용성이 됩니다.오브젝트 O는 S에서 어떤_O 치환 알고리즘에 의해 제거되지 않는 한 항상 검출됩니다.
운영 중단 최소화:사이트에 장애가 발생하면 해당 사이트에 매핑된 개체만 다시 매핑하면 됩니다.에서 ^[1]^[2]증명되었듯이, 혼란은 가능한 최소한의 수준입니다.
분산 k-agreement : 클라이언트는 ^[8]발주처 상위 k개 사이트를 선택하는 것만으로 k개 사이트에 대한 분산 합의를 도출할 수 있습니다.

일관된 해싱과의 비교

일관된 해시는 사이트를 토큰이라고 하는 단위 원의 점에 균일하고 랜덤하게 매핑함으로써 작동합니다.또한 개체는 단위 원에 매핑되고 개체 위치에서 시계 방향으로 이동하는 첫 번째 토큰인 사이트에 배치됩니다.사이트가 제거되면 해당 사이트가 소유한 개체가 사이트로 전송되어 시계 방향으로 이동하는 다음 토큰을 소유합니다.각 사이트가 다수의 토큰(100~200 등)에 매핑되어 있는 경우, 나머지 사이트 간에 비교적 균일한 방법으로 오브젝트를 재할당합니다.

예를 들어 사이트 ID의 200가지 변형을 해시함으로써 사이트가 원의 포인트에 랜덤하게 매핑되는 경우 오브젝트를 할당하려면 각 사이트에 대해 200개의 해시 값을 저장하거나 재계산해야 합니다.단, 특정 사이트와 관련된 토큰은 미리 계산되어 정렬된 목록에 저장될 수 있으며, 오브젝트에 대한 해시함수의 단일 응용 프로그램 및 할당을 계산하기 위한 바이너리 검색이 필요합니다.그러나 사이트당 다수의 토큰을 사용하더라도 일관된 해시의 기본 버전은 사이트에 할당된 각 개체가 사이트에 토큰이 있는 수만큼만 배포되기 때문에 사이트 간에 개체의 균형을 균일하게 유지하지 못할 수 있습니다.

유닛 서클에 토큰을 배포하기 위해 보다 복잡한 로직을 사용하는 일관된 해시의 변형(Amazon의 Dynamo 등)은 기본적인 일관성 있는 해싱보다 뛰어난 로드 밸런싱을 제공하며, 새로운 사이트 추가에 따른 오버헤드를 줄이고 메타데이터 오버헤드를 줄이고 기타 ^[15]이점을 제공합니다.

이와는 대조적으로 Rendezvous Hashing(HRW; 랑데부해시)은 개념적으로나 실제로는 훨씬 단순합니다.또한 균일한 해시 함수를 지정하면 모든 사이트에 객체를 균일하게 분산시킵니다.일관된 해싱과 달리 HRW에서는 토큰의 사전 계산이나 저장이 필요하지 않습니다. $O_{i}$ $Oi(O$ , $)$ 는 $O_{i}$ $n$ $n개$ 의 $h(O_{i},S_{j})$ h $(O$ $)$ 를 $n$ 계산하여 n개의\ $displaystyle$ $n사이트$ $S_{1},S_{2}\dots S_{n}$ $S_{1},S_{2}\dots S_{n}$ ${1}\dots$ S_ $S_{1},S_{2}\dots S_{n}$ ${n$ $}$ 중 $n$ 에 배치됩니다. $해시$ 값이 가장 높은 S_ ${k}$ 입니다 $S_k$ .새로운 $S_{n+1}$ $S_{n+1}$ $S_{n+1}$ $({$ 이 $S_{{n+1}}$ 추가되면 새로운 오브젝트 배치 또는 요구는 n $n+1$ + $({display$ n $+1})$ 해시 $n+1$ 값을 $n+1$ 하고 이 중 가장 큰 해시 값을 선택합니다. $S_{k}$ 내의 객체( $Sk$ \displaystyle $S_{k})$ 가 $S_k$ 이 새로운 $S_{n+1}$ $S_{n+1}$ $S_{n+1}$ 1(\ $displaystyle S_{n+1$ 에 매핑되어 있는 경우 새로 가져오고 $S_{n+1}$ $S_{n+1}$ $(\$ 로 캐시됩니다.이후 모든 클라이언트는 이 사이트에서 취득하게 되며, $S_{k}$ 으로 Sk $(\$ })의 $S_{k}$ 오래된 캐시 복사본은 로컬 캐시 관리 알고리즘으로 대체됩니다. $(\$ 가 $S_k$ 오프라인으로 $S_{k}$ 되면 오브젝트는 $n-1$ n-1 $(\displaystyle n-1)$ $n-1$ 에 $n-1$ 균일하게 재매핑됩니다.

스켈레톤 사용 등 HRW 알고리즘의 변형(아래 참조)을 사용하면 배치의 글로벌 균일성이 저하되지만 오브젝트 위치의 O $)\displaystyle$ O( $n)$ $O(n)$ 을 $O(n)$ O $displaystyle$ O $(\log$ n $)$ 로 단축할 수 있습니다.단 $,$ n\ $displaystyle$ n이 크지 $n$ 않은 경우에는 $기본$ HRW의 O $)\displaystyle$ O $(n)$ 배치 비용이 문제가 $O(n)$ $O(n)$ 않습니다.HRW는 각 사이트 및 관련 메타데이터에 대해 여러 토큰을 올바르게 처리할 때 발생하는 모든 오버헤드와 복잡성을 완전히 방지합니다.

또한 랑데부 해시는 $분산$ k\ $display$ k-agreement와 $k$ 같은 다른 중요한 문제에 대한 간단한 해결책을 제공한다는 큰 장점이 있습니다.

일관된 해시는 랑데부해시의 특수한 경우입니다.

랑데부 해시는 일관된 해싱보다 간단하고 일반적입니다.2자리 해시 함수를 적절히 선택하면 일관된 해시가 HRW의 특수한 경우임을 알 수 있습니다.사이트 $식별자$ S(\ $displaystyle$ S $)$ 에서 $S$ 일관된 해시의 가장 간단한 버전은 토큰 위치 목록을 계산합니다(예: $t_{s}=h_{c}(S)$ $t_{s}=h_{c}(S)$ $=$ $t_{s}=h_{c}(S)$ c ( $t_{s}=h_{c}(S)$ ) { $displaystyle t_{s$ } = $h_{c}$ ）。 $h_{c}$ 서 $t_{s}=h_{c}(S)$ $h_{c}$ c { $displaystyle h_{c$ } ）。2자리 $h(S,O)$ h ( $h(S,O)$ , $h(S,O)$ O $h(S,O)$ ) { $displaystyle$ h ( $S$ , ${\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}$ O ) - ${\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}$ ${\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}$ } { $displaystyle$ { $frac$ { $1$ } { \ $min$ _ { S } ( $h$ { $c （$ O ) - $h_{c}(O)-t_{s}$ $_$ { s ${\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}$ } }}로 $h(S,O)$ ${\frac {1}{\min _{S}(h_{c}(O)-t_{s})}}$ 정의합니다. $h_{c}(O)-t_{s}$ 서 h $h_{c}(O)-t_{s}$ ( $h_{c}(O)-t_{s}$ O $h_{c}(O)-t_{s}$ ) - $t _ s$ { c ) $}($ $t_{s}$ $)$ ~ $t({$ s}) ( $h_{c}(O)-t_{s}$ ( $h_{c}(O)-t_{s}$ ) - $h_{c}(O)-t_{s}$ s \ $displaystyle h_{c$ }( $O)$ - $t_{$ s $h_{c}(O)-t_{s}$ })의 최소값이 0이 $h_{c}(O)-t_{s}$ 이 값을 일정한 범위의 고유한 정수로 변환하는 데 문제가 없습니다.)이렇게 하면 일관된 해시에 의해 생성된 할당이 정확하게 복제됩니다.

단, HRW는 삭제된 사이트의 개체를 무제한의 다른 사이트로 재할당할 가능성이 있기 때문에 HRW를 일관된 해시(사이트당 토큰 수가 제한된다고 가정)로 줄일 수 없습니다.

가중치 변동

랑데부 해시의 표준 실장에서는, 모든 노드가 키의 정적으로 같은 비율을 수신합니다.단, 노드가 할당된 키를 처리하거나 유지하는 용량이 다른 경우에는 이 동작이 바람직하지 않습니다.예를 들어, 한 노드의 스토리지 용량이 다른 노드의 두 배일 경우 알고리즘이 이를 고려하여 더 강력한 노드가 다른 노드의 두 배씩의 키를 수신할 수 있도록 하는 것이 좋습니다.

이 경우를 처리하기 위한 간단한 메커니즘은 이 노드에 2개의 가상 위치를 할당하여 더 큰 노드의 가상 위치 중 하나가 가장 높은 해시를 가질 경우 해당 노드가 키를 수신하도록 하는 것입니다.그러나 상대 가중치가 정수 배수가 아닌 경우에는 이 전략이 작동하지 않습니다.예를 들어, 한 노드의 스토리지 용량이 42% 더 많으면 다양한 비율로 많은 가상 노드를 추가해야 하므로 성능이 크게 저하됩니다.이 제한을 극복하기 위해 랑데부해시에 대한 몇 가지 수정이 제안되었습니다.

캐시 어레이 라우팅 프로토콜

Cache Array Routing Protocol(CARP)은 1998년 IETF 초안입니다.각 노드의 해시 점수에 곱하여 노드의 가중치를 ^[13]달리하기 위해 임의의 수준의 정밀도를 산출할 수 있습니다.단, 이 접근법의 한 가지 단점은 노드의 중량이 변경되거나 노드가 추가 또는 삭제될 때 모든 부하 계수를 재계산하여 상대적으로 확장해야 한다는 것입니다.부하계수가 서로 상대적으로 변화하면 가중치는 변경되지 않았지만 시스템 내의 다른 노드에 대해 부하계수가 변화한 노드 간에 키의 이동이 트리거됩니다.이로 인해 ^[16]키가 과도하게 이동하게 됩니다.

레플리케이션 관리

스케일러블 해싱 또는^[17] CRUSH에 의한 제어 레플리케이션은 RUSH에 대한^[18] 확장입니다.이 확장에서는 RUSH에 대해 최종적으로 어떤 노드가 특정 키에 대해 책임을 지는지를 검출하기 위해 의사랜덤 함수(해시)를 사용하는 트리를 구축함으로써 랑데부해시를 개선합니다.노드 추가에는 완벽한 안정성을 제공하지만 노드 제거 또는 재무게 부여 시 트리 높이에 비례하여 키의 과도한 이동이 완전히 안정되지는 않습니다.

CRUSH 알고리즘은 CEPH 데이터 스토리지 시스템에서 데이터 개체를 ^[19]저장하는 노드에 매핑하는 데 사용됩니다.

스켈레톤 기반의 바리안트

HRW 실장에 사용되는 스켈레톤.

$(\displaystyle$ n)이 $n$ 매우 큰 경우 스켈레톤 기반 변형으로 실행 ^[20]^[21]^[22]시간을 향상시킬 수 있습니다.이 방법에서는 가상 계층 구조('스켈튼'이라고 불린다)를 작성하고 계층 내림차순 시 각 레벨에 HRW를 적용하여 O $)\displaystyle$ O $(\log$ n $)}$ 의 $O(\log n)$ 실행시간을 $O(\log n)$ 합니다.이 방법에서는 먼저 $일정$ m({ $displaystyle$ m $})$ 을 $m$ $n$ 선택하고n개의 $사이트$ 를 $c=\lceil n/m\rceil$ $c=\lceil n/m\rceil$ $c=\lceil n/m\rceil$ / $c=\lceil n/m\rceil$ ${\$ { $displaystyle$ c = \ $lceil$ n / $m$ \ $rceil$ } $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ C $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ { $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ 、 $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ } , $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ { $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ + $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ 、 $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ + 1 $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ S + $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ } $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ $S_{1}, S_{2}\dots S_{m}\right\, C_{2}=\left\{S_{m+1}, S_{m+2}\dots S_{2m}\right\dots }$ 다음으로 $C_{1}=\left\{S_{1},S_{2}\dots S_{m}\right\},C_{2}=\left\{S_{m+1},S_{m+2}\dots S_{2m}\right\}\dots$ 상수 ${$ $style$ $fdisplay}\$ display 클러스터에 $f$ $c$ $c$ 하여 가상 계층을 구축합니다 $.$ .

첨부된 다이어그램에서 클러스터 크기는 $m=4$ $m=4$ $({displaystyle$ m $=4$ 스켈레톤 $f=3$ 은 f $f=3$ ({ $displaystyle$ f $=3$ 입니다. 편의상 108개 사이트(실제 노드)를 가정하면 3계층 가상 계층을 얻을 수 있습니다.f $f=3$ $displaystyle$ f $=3)$ 이므로 각 가상 노드는 8진수로 자연스러운 번호를 가집니다.따라서 최하층의 27개의 가상 노드에는 8진수로 $,$ $002$ $000,001,002,...,221,222$ $222(물론$ 각 레벨에서 팬아웃을 변경할 수 있습니다.이 경우 각 노드는 대응하는 혼합 기수 번호로 식별됩니다).

108개의 모든 실제 노드에 HRW를 적용하는 것이 아니라 우선 하위 계층 27개의 가상 노드에 HRW를 적용하여 1개를 선택할 수 있습니다.그런 다음 클러스터 내의 4개의 실제 노드에 HRW를 적용하여 대상 사이트를 선택합니다.해시는 108개가 아니라 27 $+4=31개$ 만 $27+4=31$ 합니다 $27+4=31$ .이 방법을 계층에서 한 단계 높은 곳부터 적용할 경우, 우승 사이트에 도달하려면 9 $9+3+4=16$ + $9+3+4=16$ + $9+3+4=16$ $9+3+4=16$ $9+3+4=16$ ${\displaystyle$ 9 + $3$ + 4 $9+3+4=16$ = $16$ }개의 $9+3+4=16$ $9+3+4=16$ 필요합니다.이 그림은 스켈레톤 루트부터 시작하여 가상 $(2)_{3}$ 2 $)$ $({displaystyle ($ 2 $)_{$ 3 $(2)_{3}$ $(20)_{3}$ ( $(20)_{3}$ ({ $displaystyle$ $(20)_{3$ $(200)_{3}$ $(200)_{3}$ ( $)$ 3({ $displaystyle$ (200) $_{$ 3 $(200)_{3}$ 을 차례로 선택하여 최종적으로 사이트 74에 도달하는 방법을 나타내고 있습니다.

루트뿐만 아니라 가상 계층의 모든 수준에서 시작할 수 있습니다.하위 계층에서 시작하면 더 많은 해시가 필요하지만 장애 발생 시 부하 분산이 개선될 수 있습니다.또한 가상 노드 이름은 단순히 $base-f\displaystyle$ f $($ 또는 혼합 기수) 표현 접두사이기 때문에 가상 계층을 저장할 필요는 없지만 필요에 따라 생성할 수 있습니다.필요에 따라서, 숫자로부터 적절히 정렬된 문자열을 간단하게 작성할 수 있습니다.이 예에서는 $0,1,2$ 0 $,$ , $0,1,2$ 1), $20,21,22$ $20,21,22$ $22($ 2 $),$ $, 201$ $202(계층$ 3) $200,201,202$ 를 사용하고 있습니다. $h=O(\log c)=O(\log n)$ $\displaystyle$ m $}$ 과 $m$ f $\displaystyle$ f $}$ 는 $f$ 모두 상수이므로 $T$ $\$ $displaystyle$ $T$ 는 $T$ 높이h $=$ ( $log$ c ) $h=O(\log c)=O(\log n)$ O ( $log$ n $)$ 입니다.f {\ $displaystyle$ f $}$ 는 $f$ $f$ 이므로 각 레벨에서 수행되는 작업은 $O(1)$ ( $)$ {{ $displaystyle$ O(1 $O(1)$

특정 오브젝트에 대해 이 메서드는 각 클러스터를 선택하고n개의 $사이트$ 를 $n$ 동일한 확률로 선택하는 것이 명확합니다 $.$ 최종 선택한 사이트를 사용할 수 없는 경우 동일한 클러스터 내의 다른 사이트를 일반적인 방법으로 선택할 수 있습니다.또는 스켈레톤 내의 1개 이상의 계층으로 올라가 해당 계층의 형제 가상 노드 중에서 대체 노드를 선택한 후 위와 같이 계층을 다시 실제 노드로 내립니다.

$m(\displaystyle$ m $)$ $m$ 은 $m$ 예상되는 고장률 및 원하는 부하 밸런싱 정도 등의 요인에 따라 선택할 수 있습니다. $(\displaystyle$ m $)$ 값이 $m$ 클수록 검색 오버헤드가 높아지지만 장애 발생 시 부하 스큐가 줄어듭니다.

$m=m$ $m=m$ { $displaystyle$ m $=m}$ 의 $m=m$ 선택은 비규칙적인 랑데부 해시와 동일합니다.실제로 $h(\cdot )$ h ${\$ )(\ $displaystyle$ h $(\cdot)$ 는 $h(\cdot)$ 매우 저렴하기 $m=n$ 에 n $(\displaystyle$ m $=n$ )이 $n$ 매우 높지 $않으면$ m $(\displaystyle$ m=n $)$ 이 $m=n$ 상당히 잘 작동합니다.

기타 변종

2005년에 Christian Schindelhauer와 Gunnar Schomaker는 노드의 무게가 변화하거나 노드가 추가 또는 ^[23]제거될 때 부하 계수의 상대적 배율이 필요하지 않은 방식으로 해시 점수를 재가중화하는 로그 방법을 설명했다.이를 통해 최소 개수의 키만 새 노드에 재매핑하면 되므로 노드의 가중치 부여 시 완벽한 정밀도와 완벽한 안정성이라는 이중적인 이점을 얻을 수 있었습니다.

유사한 로그 기반 해싱 전략을 사용하여 Cleversafe의 데이터 스토리지 시스템(현 IBM Cloud Object Storage)^[16]의 스토리지 노드에 데이터를 할당합니다.

실행

$h(\cdot )$ h ( $h(\cdot )$ $){$ $displaystyle$ h $(\cdot$ )}를 $h(\cdot)$ 선택하면 구현이 간단합니다(HRW 메서드에 관한 원작업에서는 해시함수가 ^[1]^[2]권장됩니다).각 클라이언트는 $n$ 의\ $displaystyle$ n개의 $n$ 각 사이트에 대해 해시 값을 계산한 후 가장 큰 사이트를 선택하면 됩니다. $O(n)$ 알고리즘은 O $O(n)$ ( $O(n)$ n ) $O(n)$ { $displaystyle$ O ( $n$ ) }회 $O(n)$ $O(n)$ 됩니다.해시함수가 효율적일 경우 O $O(n)$ ( $O(n)$ $)\displaystyle$ O ( $n$ ) $O(n)$ 은 $O(n)$ n $\displaystyle$ n이 $n$ 매우 크지 않으면 $n$ 가 되지 않습니다.

가중 랑데부 해시

가중 랑데부 ^[16]해시를 구현하는 Python 코드:

수입품 mmh3 수입품 수학 부터 데이터 클래스 수입품 데이터 클래스 부터 타자 치기 수입품 목록.   방어하다 hash_to_unit_syslog(s: 스트레이트) -> 흘러가다:     "유닛 인터벌(0, 1)에 문자열을 해시합니다."     돌아가다 (mmh3.해시128(s) + 1) / 2**128   @dataclass 학급 노드:     가중 랑데부해시의 일부로서 키가 할당되어 있는 노드를 나타내는 클래스."""     이름.: 스트레이트     체중: 흘러가다      방어하다 계산_가중_점수(자신, 열쇠: 스트레이트):         스코어 = hash_to_unit_syslog(f"{자신.이름.}:{열쇠}")         log_score = 1.0 / -수학.로그.(스코어)         돌아가다 자신.체중 * log_score   방어하다 determine_responsible_node(노드: 목록.[노드], 열쇠: 스트레이트):     "다양한 가중치를 가진 노드 집합 중 어느 노드가 제공된 키를 담당하는지 결정합니다."""     돌아가다 맥스.(         노드, 열쇠=람다 노드: 노드.계산_가중_점수(열쇠), 체납=없음.)

WRH 출력 예:

>>>수입품 wrh >>>노드 1 = wrh.노드("node1", 100) >>>노드2 = wrh.노드("node2", 200) >>>노드 3 = wrh.노드("node3", 300) >>>스트레이트(wrh.determine_responsible_node([노드 1, 노드2, 노드 3], '푸')) "노드(이름='node1', 무게=100)" >>>스트레이트(wrh.determine_responsible_node([노드 1, 노드2, 노드 3], '바')) "노드(이름='node2', 무게=300)" >>>스트레이트(wrh.determine_responsible_node([노드 1, 노드2, 노드 3], '안녕하세요')) "노드(이름='node2', 무게=300)" >>>부터 수집품 수입품 계산대 >>>책임 있는 = [wrh.determine_responsible_node( ...    노드, f「키:{열쇠}").이름. 위해서 열쇠 에서 범위(45_000)] >>>인쇄물(계산대(책임 있는)) 카운터({'My Node 9'): 8896, 'My Node 8': 8068, 'My Node 7': 7008, 'My Node 6': 5974, 'My Node 5': 5100, 'My Node 4': 4023, 'My Node 3': 3006, 'My Node 2: 1958, My Node 1'

레퍼런스

^ ^a ^b ^c ^d ^e ^f Thaler, David; Chinya Ravishankar. "A Name-Based Mapping Scheme for Rendezvous" (PDF). University of Michigan Technical Report CSE-TR-316-96. Retrieved 2013-09-15.
^ ^a ^b ^c ^d Thaler, David; Chinya Ravishankar (February 1998). "Using Name-Based Mapping Schemes to Increase Hit Rates". IEEE/ACM Transactions on Networking. 6 (1): 1–14. CiteSeerX 10.1.1.416.8943. doi:10.1109/90.663936.
^ "Rendezvous Hashing Explained - Randorithms". randorithms.com. Retrieved 2021-03-29.
^ "Rendezvous hashing: my baseline "consistent" distribution method - Paul Khuong: some Lisp". pvk.ca. Retrieved 2021-03-29.
^ Aniruddha (2020-01-08). "Rendezvous Hashing". Medium. Retrieved 2021-03-29.
^ Mayank, Anup; Ravishankar, Chinya (2006). "Supporting mobile device communications in the presence of broadcast servers" (PDF). International Journal of Sensor Networks. 2 (1/2): 9–16. doi:10.1504/IJSNET.2007.012977.
^ Guo, Danhua; Bhuyan, Laxmi; Liu, Bin (October 2012). "An efficient parallelized L7-filter design for multicore servers". IEEE/ACM Transactions on Networking. 20 (5): 1426–1439. doi:10.1109/TNET.2011.2177858.
^ ^a ^b Wang, Peng; Ravishankar, Chinya (2015). "Key Foisting and Key Stealing Attacks in Sensor Networks'" (PDF). International Journal of Sensor Networks.
^ Mukherjee, Niloy; et al. (August 2015). "Distributed Architecture of Oracle Database In-memory". Proceedings of the VLDB Endowment. 8 (12): 1630–1641. doi:10.14778/2824032.2824061.
^ GitHub Engineering. "Introducing the GitHub Load Balancer". GitHub Blog. Retrieved 1 February 2022.
^ Blazevic, Ljubica. "Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony". IETF Draft. IETF. Retrieved September 17, 2013.
^ Fenner, B. "Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)". IETF RFC. IETF. Retrieved September 17, 2013.
^ ^a ^b Valloppillil, Vinod; Kenneth Ross. "Cache Array Routing Protocol v1.0". Internet Draft. Retrieved September 15, 2013.
^ "Cache Array Routing Protocol and Microsoft Proxy Server 2.0" (PDF). Microsoft. Archived from the original (PDF) on September 18, 2014. Retrieved September 15, 2013.
^ DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, W. (2007). "Dynamo: Amazon's Highly Available Key-Value Store" (PDF). Proceedings of the 21st ACM Symposium on Operating Systems Principles. doi:10.1145/1323293.1294281. Retrieved 2018-06-07.
^ ^a ^b ^c Jason Resch. "New Hashing Algorithms for Data Storage" (PDF).
^ Sage A. Weil; et al. "CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data" (PDF). Archived from the original (PDF) on February 20, 2019.
^ R. J. Honicky, Ethan L. Miller. "Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution" (PDF).
^ Ceph. "Crush Maps".
^ Yao, Zizhen; Ravishankar, Chinya; Tripathi, Satish (May 13, 2001). Hash-Based Virtual Hierarchies for Caching in Hybrid Content-Delivery Networks (PDF). Riverside, CA: CSE Department, University of California, Riverside. Retrieved 15 November 2015.
^ Wang, Wei; Chinya Ravishankar (January 2009). "Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-hoc Networks". Mobile Networks and Applications. 14 (5): 625–637. doi:10.1007/s11036-008-0144-3.
^ Mayank, Anup; Phatak, Trivikram; Ravishankar, Chinya (2006), Decentralized Hash-Based Coordination of Distributed Multimedia Caches (PDF), Proc. 5th IEEE International Conference on Networking (ICN'06), Mauritius: IEEE
^ Christian Schindelhauer, Gunnar Schomaker (2005). "Weighted Distributed Hash Tables": 218. CiteSeerX 10.1.1.414.9353. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

외부 링크

Rendezvous Hashing: 일관된 해싱의 대체 수단

[:0-1] ^ ^a ^b ^c ^d ^e ^f Thaler, David; Chinya Ravishankar. "A Name-Based Mapping Scheme for Rendezvous" (PDF). University of Michigan Technical Report CSE-TR-316-96. Retrieved 2013-09-15.

[:1-2] Thaler, David; Chinya Ravishankar (February 1998). "Using Name-Based Mapping Schemes to Increase Hit Rates". IEEE/ACM Transactions on Networking. 6 (1): 1–14. CiteSeerX 10.1.1.416.8943. doi:10.1109/90.663936.

[3] "Rendezvous Hashing Explained - Randorithms". randorithms.com. Retrieved 2021-03-29.

[4] "Rendezvous hashing: my baseline "consistent" distribution method - Paul Khuong: some Lisp". pvk.ca. Retrieved 2021-03-29.

[5] Aniruddha (2020-01-08). "Rendezvous Hashing". Medium. Retrieved 2021-03-29.

[6] Mayank, Anup; Ravishankar, Chinya (2006). "Supporting mobile device communications in the presence of broadcast servers" (PDF). International Journal of Sensor Networks. 2 (1/2): 9–16. doi:10.1504/IJSNET.2007.012977.

[7] Guo, Danhua; Bhuyan, Laxmi; Liu, Bin (October 2012). "An efficient parallelized L7-filter design for multicore servers". IEEE/ACM Transactions on Networking. 20 (5): 1426–1439. doi:10.1109/TNET.2011.2177858.

[foisting-8] Wang, Peng; Ravishankar, Chinya (2015). "Key Foisting and Key Stealing Attacks in Sensor Networks'" (PDF). International Journal of Sensor Networks.

[9] Mukherjee, Niloy; et al. (August 2015). "Distributed Architecture of Oracle Database In-memory". Proceedings of the VLDB Endowment. 8 (12): 1630–1641. doi:10.14778/2824032.2824061.

[10] GitHub Engineering. "Introducing the GitHub Load Balancer". GitHub Blog. Retrieved 1 February 2022.

[11] Blazevic, Ljubica. "Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony". IETF Draft. IETF. Retrieved September 17, 2013.

[12] Fenner, B. "Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)". IETF RFC. IETF. Retrieved September 17, 2013.

[carp-13] Valloppillil, Vinod; Kenneth Ross. "Cache Array Routing Protocol v1.0". Internet Draft. Retrieved September 15, 2013.

[14] "Cache Array Routing Protocol and Microsoft Proxy Server 2.0" (PDF). Microsoft. Archived from the original (PDF) on September 18, 2014. Retrieved September 15, 2013.

[Amazon2007-15] DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A.; Sivasubramanian, S.; Vosshall, P.; Vogels, W. (2007). "Dynamo: Amazon's Highly Available Key-Value Store" (PDF). Proceedings of the 21st ACM Symposium on Operating Systems Principles. doi:10.1145/1323293.1294281. Retrieved 2018-06-07.

[wrh-16] Jason Resch. "New Hashing Algorithms for Data Storage" (PDF).

[crush-17] Sage A. Weil; et al. "CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data" (PDF). Archived from the original (PDF) on February 20, 2019.

[rush-18] R. J. Honicky, Ethan L. Miller. "Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution" (PDF).

[19] Ceph. "Crush Maps".

[CSE_Technical_Report_UCR-CS_2001-05062-20] Yao, Zizhen; Ravishankar, Chinya; Tripathi, Satish (May 13, 2001). Hash-Based Virtual Hierarchies for Caching in Hybrid Content-Delivery Networks (PDF). Riverside, CA: CSE Department, University of California, Riverside. Retrieved 15 November 2015.

[21] Wang, Wei; Chinya Ravishankar (January 2009). "Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-hoc Networks". Mobile Networks and Applications. 14 (5): 625–637. doi:10.1007/s11036-008-0144-3.

[22] Mayank, Anup; Phatak, Trivikram; Ravishankar, Chinya (2006), Decentralized Hash-Based Coordination of Distributed Multimedia Caches (PDF), Proc. 5th IEEE International Conference on Networking (ICN'06), Mauritius: IEEE

[23] Christian Schindelhauer, Gunnar Schomaker (2005). "Weighted Distributed Hash Tables": 218. CiteSeerX 10.1.1.414.9353. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Search