랑데부 해싱

랑데부(Rendezvous) 또는 HRW (High Random Random Weight) 해싱 은 클라이언트가 가능한 n개의 선택지에서 k개의 선택에 대해 분산 합의를 달성할 수 있게 하는 알고리즘이다. 전형적인 예는 클라이언트가 개체들이 할당될 사이트들이 어떤 것인지 합의해야할 때이다.

일관된 해싱은 랑데부 해싱의 특수한 경우($k=1$)이다.

역사

랑데부 해시는 1996년 미시간 대학교에서 David Thaler와 Chinya Ravishankar가 발명했다. 일년 후 일관된 해싱은 문헌으로 나타났다. 랑데부 해싱의 첫번째 활용 중 하나는 인터넷의 멀티 캐스트 클라이언트가 분산된 방식으로 멀티 캐스트 랑데부 지점을 식별할 수 있게 하는 것이다. 분산 캐시 조정 및 라우팅을 위해 1998년 Microsoft의 CARP ( Cache Array Routing Protocol )에 의해 사용되었다. 일부 프로토콜 독립 멀티 캐스트 라우팅 프로토콜은 랑데부 해싱을 사용하여 랑데부 지점을 선택한다.

랑데부 해싱은 모바일 캐싱, 라우터 설계, 보안 키 설정,, 샤딩 및 분산 데이터베이스를 포함한 다양한 응용 프로그램에 적용되었다.

개요

알고리즘

랑데부 해싱은 분산 해시 테이블 문제를 해결한다.

객체 O가 주어졌을 때, 클라이언트들이 n개의 사이트들(서버 등)에서 O를 배치할 위치에 대해 어떻게 합의할 것인가? 각 클라이언트는 사이트를 독립적으로 선택하지만 모든 클라이언트는 동일한 사이트를 선택해야 한다. 교란 최소화 제약을 추가하고 제거된 사이트에만 매핑된 개체를 다른 사이트에 다시 할당해야 하는 경우 이는 쉽지 않다.

기본 아이디어는 각 사이트 _Sj에 각 객체 O _i에 대한 점수 (무게)를 부여하고 객체를 가장 높은 점수를 내는 사이트에 할당하는 것이다. 모든 클라이언트는 먼저 해시 함수 h()에 합의해야한다. 객체 O_i에 대해 사이트 S_j는 가중치 w_i,j = h (O_i , S_j )를 갖도록 정의된다. HRW는 가중치 w_{i, m} 이 가장 큰 사이트 S_m에 O_i를 할당한다. h()는 합의되어 있기 때문에 각 클라이언트가 독립적으로 가중치들을 계산하고 가장 큰 것을 선택할 수 있다. 목표가 분산된 k-합의라면 클라이언트는 k개의 해시 값이 가장 큰 사이트를 독립적으로 선택할 수 있다.

사이트 S가 추가되거나 제거되었을 때 S에 매핑 된 개체 만 다른 사이트로 다시 매핑되어도 위의 교란 최소화 제약을 충족시킨다. HRW 할당은 사이트 집합 S₁, S₂, ..., S_N에 대한 식별자와 할당될 객체에만 의존하기 때문에 클라이언트에 의해 독립적으로 계산될 수 있다.

HRW는 사이트마다 용량이 다를 때도 쉽게 수용한다. 사이트 S_k 가 다른 사이트의 용량의 두 배를 갖는 경우, 간단하게 S_k,1 및 S_k,2 와 같이 목록에서 S_k를 두 번 나타내면 된다. 다른 사이트보다 2배 많은 객체가 S_k에 매핑될 것이다.

속성

이것은 n 사이트를 해시 테이블에서 버킷으로 취급하고 객체 이름 O를 테이블로 해시하는 것으로 충분해 보일 수 있다. 그러나 사이트 중 하나라도 고장나거나 연결할 수 없는 경우, 해시 테이블 크기가 변경되어 모든 개체를 다시 매핑해야 된다. 이러한 대규모 교란은 이러한 직접 해싱이 작동하지 않게 만든다. 그러나 랑데부 해싱에서 클라이언트는 다음으로 큰 가중치를 생성하는 사이트를 선택하는 것으로 사이트 고장을 대처한다. 재매핑은 고장난 사이트에 매핑 된 개체에만 필요하며 교란은 최소화된다.

랑데부 해싱에는 다음과 같은 속성이 있다.

1. 낮은 오버헤드 : 사용된 해시 함수가 효율적이므로 클라이언트의 오버헤드가 매우 낮다.
2. 로드 밸런싱 : 해시 함수가 랜덤하므로, n개의 사이트 각각이 오브젝트 O를 할당 받을 확률이 균등하다. 따라서 사이트 전체의 하중이 균일하다.
   1. 사이트 용량 : 용량이 다른 사이트는 용량에 비례하여 사이트 목록에 표시 될 수 있다. 다른 사이트 용량의 두 배인 사이트는 목록에 두 번 표시되고 다른 모든 사이트는 한 번 표시된다.
3. 높은 적중률 : 모든 클라이언트가 동일한 사이트 S _O에 객체 O를 배치하는 것에 동의하기 때문에, S _O에 대한 O의 수정이나 이동 작업은 적중률의 측면에서 최대의 효율을 얻을 수 있다. 일부 교체 알고리즘에 의해 퇴거하지 않는 객체 O는 S _O에서 항상 발견 될 것이다.
4. 최소 교란 : 사이트가 고장나면 해당 사이트에 매핑된 개체만 다시 매핑하면 된다. 입증된 바와 같이 교란은 최소화된다.
5. 분산된 k -agreement : 클라이언트는 단순히 순서에서 최고의 k 사이트를 선택하여 k 개의 사이트에 분산 합의에 도달할 수 있다.

가중 변형

랑데부 해싱의 표준 구현에서는 모든 노드가 통계적으로 동일한 수의 키를 할당 받는다. 그러나 이것은 노드들이 그들이 할당 받은 키에 사용할 수 있는 용량이 다른 경우를 고려하지 않는다. 예를 들어, 한 노드가 다른 노드보다 두 배의 저장 용량을 가진 경우 알고리즘이 이를 고려하여 용량이 큰 노드가 다른 노드보다 두 배의 키를 할당받도록 하는 것이 좋을 수 있다.

간단한 접근법은 하나의 노드에 2배의 가상 공간을 할당하여 큰 노드일 경우 더 많은 키를 받게 하는 것이다. 하지만 이러한 전략은 크기 비율이 정수가 아닐 경우 제대로 동작하지 않는다. 예를 들어 42% 더 큰 용량을 지닌 노드가 있을 경우 많은 가상 노드를 추가해야하므로 성능이 크게 저하된다. 이러한 제약을 극복하기 위해 랑데부 해싱에 대한 몇가지 수정이 제안되었다.

제어된 복제

확장 가능한 해싱 또는 CRUSH에서의 제어된 복제는 RUSH의 확장이다. RUSH는 해시를 이용하여 키를 탐색할 수 있는 트리를 생성하는 것으로 랑데부 해싱을 개선한다.

스켈레톤 기반 변형

n이 매우 클 때 스켈레톤 기반 변형은 실행 시간을 크게 향상 시킬 수 있다. 이 방법은 가상 계층 구조(스켈레톤)을 만들고 각 계층에서 HRW을 적용하여 $O(logn)$의 실행 시간을 가능하게 한다.

구현

가중 랑데부 해시

가중 랑데부 해시를 구현하는 파이썬 코드 :

#!/usr/bin/env python
import mmh3
import math

def int_to_float(value: int) -> float:
    """Converts a uniformly random [[64-bit computing|64-bit]] integer to uniformly random floating point number on interval <math>[0, 1)</math>."""
    fifty_three_ones = (0xFFFFFFFFFFFFFFFF >> (64 - 53))
    fifty_three_zeros = float(1 << 53)
    return (value & fifty_three_ones) / fifty_three_zeros

class Node(object):
    """Class representing a node that is assigned keys as part of a weighted rendezvous hash."""
    def __init__(self, name: str, seed, weight) -> None:
        self.name, self.seed, self.weight = name, seed, weight

    def __str__(self):
        return "[" + self.name + " (" + str(self.seed) + ", " + str(self.weight) + ")]"

    def compute_weighted_score(self, key):
        hash_1, hash_2 = mmh3.hash64(str(key), 0xFFFFFFFF & self.seed)
        hash_f = int_to_float(hash_2)
        score = 1.0 / -math.log(hash_f)
        return self.weight * score

def determine_responsible_node(nodes, key):
    """Determines which node, of a set of nodes of various weights, is responsible for the provided key."""
    highest_score, champion = -1, None
    for node in nodes:
        score = node.compute_weighted_score(key)
        if score > highest_score:
            champion, highest_score = node, score
    return champion

WRH의 출력 예 :

[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.39)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import wrh
>>> node1 = wrh.Node("node1", 123, 100)
>>> node2 = wrh.Node("node2", 567, 200)
>>> node3 = wrh.Node("node3", 789, 300)
>>> str(wrh.determine_responsible_node([node1, node2, node3], 'foo'))
'[node3 (789, 300)]'
>>> str(wrh.determine_responsible_node([node1, node2, node3], 'bar'))
'[node3 (789, 300)]'
>>> str(wrh.determine_responsible_node([node1, node2, node3], 'hello'))
'[node2 (567, 200)]'