Rendezvous hashing

Highest Random Weight(HRW) hashing으로 부르기도 하는 랑데뷰(Rendezvous) 알고리즘은 1996년(2015-04-01T09:35:47 기준 거의 20년이나 된 알고리즘이다.)개발 됐다. 미시건(Michigan) 대학의 David Thaler과 Chinya Ravishankar이 개발 했다. 비슷한 시기에 개발된 MIT의 Consistent hash와는 (목적은 비슷하긴 하지만)상관이 없는 알고리즘이다.

이 알고리즘는 멀티캐스트 애플리케이션에 처음 구현됐다. 이후 1998년 마이크로소프트의 CARP(Cache Array Routing Protocol)의 구현에 사용된다. 모바일 캐쉬와 라우터 디자인, secure establishment등에 사용하고 있다.

라데뷰 해시로 풀려는 문제는 다음과 같다.

클라이언트의 집단이 있고, 이들은 객체 O에 접근하려고 한다. 객체들을 관리하는 여러 개의 사이트가 있을 때, 어느 사이트로 접근해야 할까 ? 각각의 클라이언트가 서로 독립적일 때, 각 클라이언트들은 객체를 가지고 있는 "같은 사이트"에 접근할 수 있어야 한다.

사이트의 집합을 {S1, S2, ..., Sn}으로 표현 하자. HRW는 해시 함수 h()를 이용해서, 각 사이트에 대해서 n 개의 hash weight를 구한다. "w1 = h(S1, O), w2 = h(S2,O), ..., Wn = h(Sn, O)". 각 클라이언트의 객체 O를 가진 사이트를 So라 할 때, 가장 높은 가중치 (highest weight) wo = max{W1, W2,...., Wn}를 가진 사이트가 So가 된다. 클라이언트들은 자신들이 가진 객체들에 대해서 해시 연산을 수행하고, 다른 클라이언트들에 독립적인 사이트 So를 선택할 수 있다.

해시 함수는 해시 테이블을 구성하는데, 사이트의 갯수 n에 의존적이다. 만약 사이트의 갯수가 변경되면, 모든 객체를 리맵해야 한다. 랑데뷰 해시의 경우 사이트가 실패하면, 다음으로 가중치가 높은 사이트를 선택한다. 따라서 실패한 사이트로 향하는 키만 새로 맵핑해주면 되며, 서비스의 중단을 최소화 할 수 있다. 랑데뷰 해싱은 아래와 같은 특징들을 가지고 있다.

• 낮은 오버헤드 : 해시 함수는 효율적이며 단순하다. 클라이언트의 오버헤드를 최소화 할 수 있다.
• 로드 밸런싱 : 해시 함수는 램덤하게 작동한다. 따라서 로드는 전체 사이트로 밸런싱 된다.
• 높은 적중률 : 모든 클라이언트에 대해서 객체 O는 사이트 So에 있다는 것을 보장한다.
• 중단 최소화 : 사이트가 실패 하더라도 리맵이 발생하지 않는다.
• Distributed k-agreement

컨시스턴트 해싱은 hashring에 사이트를 랜덤하게 배치한다. 해시링상의 포인트 Po에 배치된 객체는 링에서 시계방향으로 가장 가까운 사이트 So에 저장된다. 만약 사이트 Sk가 실패하면, 모든 객체들은 Sk+1에 맵핑된다. 이 경우 Sk의 객체가 Sk+1에 몰리게 되는데, 이는 서비스 전체에 나쁜 영향을 미칠 수 있다.

이 문제는 해시링상에 100에서 200개 정도의 가상의 복제(virtual replica)를 랜덤하게 배치하는 것으로 해결할 수 있다. 이들 복제는 랜덤하게 배치되므로, Sk다음에 오는 Sk+1은 특정 노드가 아닌, 1/N 확률로 배치가 된다. Sk가 실패할 경우 Sk+1로 트래픽이 가긴 하지만 모든 사이트로 분산되는 효과를 얻을 수 있다. 가상 복제를 관리에 들어가는 비용이 만만 찮다는 단점이 있다.

랑데뷰 해싱은 이런 문제에서 자유롭다. 해시 함수의 매개변수로 사이트와 객체를 모두 사용하고, 그 결과로 정렬된 사이트의 목록을 얻을 수 있기 때문이다. 가장 높은 가중치의 사이트가 실패하면, 다음 가중치를 선택하면 된다.

사이트 N개에 대해서 해시 함수 h()를 순차적으로 적용하면 된다. 어떤 해시 함수를 사용할 것인지가 중요요소다. 각각의 클라이언트들은 N 사이트에 대해서 해시 함수를 돌려야 하므로 시간복잡도는 O(n)이 되어야 할 것 같지만, 절약할 수 있다. 라고 한다. 그런데 어떻게 가능한지 모르겠다. http://en.wikipedia.org/wiki/Rendezvous_hashing 이 문서를 보고 있는데, 현재 분석 중...