랑데부 해싱 문서 원본 보기

{{위키데이터 속성 추적}}
'''랑데부'''(Rendezvous) 또는 '''HRW (High Random Random Weight) 해싱'''<ref name=":0">{{웹 인용|url=http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf|제목=A Name-Based Mapping Scheme for Rendezvous|성=Thaler|이름=David|성2=Chinya Ravishankar|출판사=University of Michigan Technical Report CSE-TR-316-96|확인날짜=2013-09-15}}</ref><ref name=":1">{{저널 인용|제목=Using Name-Based Mapping Schemes to Increase Hit Rates|저널=IEEE/ACM Transactions on Networking|성=Thaler|이름=David|성2=Chinya Ravishankar|날짜=February 1998|권=6|호=1|쪽=1–14|doi=10.1109/90.663936}}</ref> 은 클라이언트가 가능한 ''n''개의 선택지에서 ''k''개의 선택에 대해 분산 합의를 달성할 수 있게 하는 알고리즘이다.  전형적인 예는 클라이언트가 개체들이 할당될 사이트들이 어떤 것인지 합의해야할 때이다.

[[일관된 해싱]]은 랑데부 해싱의 특수한 경우(<math>k = 1</math>)이다.

== 역사 ==
랑데부 해시는 1996년 [[미시간 대학교]]에서 David Thaler와 Chinya Ravishankar가 발명했다.<ref name=":0">{{웹 인용|url=http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf|제목=A Name-Based Mapping Scheme for Rendezvous|성=Thaler|이름=David|성2=Chinya Ravishankar|출판사=University of Michigan Technical Report CSE-TR-316-96|확인날짜=2013-09-15}}</ref> 일년 후 [[일관된 해싱]]은 문헌으로 나타났다. 랑데부 해싱의 첫번째 활용 중 하나는 인터넷의 [[멀티캐스트|멀티 캐스트]] 클라이언트가 분산된 방식으로 멀티 캐스트 랑데부 지점을 식별할 수 있게 하는 것이다.<ref>{{웹 인용|url=http://tools.ietf.org/html/draft-blazevic-dcm-mobility-01|제목=Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony|성=Blazevic|이름=Ljubica|웹사이트=IETF Draft|출판사=IETF|확인날짜=September 17, 2013}}</ref><ref>{{웹 인용|url=http://tools.ietf.org/html/rfc4601|제목=Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)|성=Fenner|이름=B.|웹사이트=IETF RFC|출판사=IETF|확인날짜=September 17, 2013}}</ref> 분산 캐시 조정 및 라우팅을 위해 1998년 Microsoft의 CARP ( Cache Array Routing Protocol )에 의해 사용되었다.<ref name="carp">{{웹 인용|url=http://tools.ietf.org/html/draft-vinod-carp-v1-03|제목=Cache Array Routing Protocol v1.0|성=Valloppillil|이름=Vinod|성2=Kenneth Ross|출판사=Internet Draft|확인날짜=September 15, 2013}}</ref><ref>{{웹 인용|url=http://oldsite.mcoecn.org/WhitePapers/Mscarp.pdf|제목=Cache Array Routing Protocol and Microsoft Proxy Server 2.0|출판사=Microsoft|보존url=https://web.archive.org/web/20140918115447/http://oldsite.mcoecn.org/WhitePapers/Mscarp.pdf|보존날짜=September 18, 2014|확인날짜=September 15, 2013}}</ref> 일부 [[멀티캐스트용 프로토콜|프로토콜 독립 멀티 캐스트]] 라우팅 프로토콜은 랑데부 해싱을 사용하여 랑데부 지점을 선택한다.

랑데부 해싱은 모바일 캐싱,<ref>{{저널 인용|제목=Supporting mobile device communications in the presence of broadcast servers|저널=International Journal of Sensor Networks|성=Mayank|이름=Anup|성2=Ravishankar|이름2=Chinya|url=http://www.cs.ucr.edu/~ravi/Papers/Jrnl/Mayank.pdf|날짜=2006|권=2|호=1/2|쪽=9–16|doi=10.1504/IJSNET.2007.012977}}</ref> 라우터 설계,<ref>{{저널 인용|제목=An efficient parallelized L7-filter design for multicore servers|저널=IEEE/ACM Transactions on Networking|성=Guo|이름=Danhua|성2=Bhuyan|이름2=Laxmi|날짜=October 2012|권=20|호=5|쪽=1426–1439|doi=10.1109/TNET.2011.2177858|성3=Liu|이름3=Bin}}</ref> 보안 키 설정,<ref name="foisting">{{저널 인용|제목=Key Foisting and Key Stealing Attacks in Sensor Networks'|저널=International Journal of Sensor Networks|성=Wang|이름=Peng|성2=Ravishankar|이름2=Chinya|url=http://www.cs.ucr.edu/~ravi/Papers/Jrnl/foisting.pdf|날짜=2015}}</ref>, [[샤드 (데이터베이스 아키텍처)|샤딩]] 및 [[분산 데이터베이스|분산 데이터베이스를]] 포함한 다양한 응용 프로그램에 적용되었다.<ref>{{저널 인용|제목=Distributed Architecture of Oracle Database In-memory|저널=Proceedings of the VLDB Endowment|성=Mukherjee|이름=Niloy|날짜=August 2015|권=8|호=12|쪽=1630–1641|doi=10.14778/2824032.2824061|저자표시=etal}}</ref>

== 개요 ==

=== 알고리즘 ===
랑데부 해싱은 [[분산 해시 테이블]] 문제를 해결한다.

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

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

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

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

=== 속성 ===
이것은 ''n'' 사이트를 [[해시 테이블]]에서 버킷으로 취급하고 객체 이름 ''O''를 테이블로 해시하는 것으로 충분해 보일 수 있다. 그러나 사이트 중 하나라도 고장나거나 연결할 수 없는 경우, 해시 테이블 크기가 변경되어 모든 개체를 다시 매핑해야 된다. 이러한 대규모 교란은 이러한 직접 해싱이 작동하지 않게 만든다. 그러나 랑데부 해싱에서 클라이언트는 다음으로 큰 가중치를 생성하는 사이트를 선택하는 것으로 사이트 고장을 대처한다. 재매핑은 고장난 사이트에 매핑 된 개체에만 필요하며 교란은 최소화된다.<ref name=":0">{{웹 인용|url=http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf|제목=A Name-Based Mapping Scheme for Rendezvous|성=Thaler|이름=David|성2=Chinya Ravishankar|출판사=University of Michigan Technical Report CSE-TR-316-96|확인날짜=2013-09-15}}</ref><ref name=":1">{{저널 인용|제목=Using Name-Based Mapping Schemes to Increase Hit Rates|저널=IEEE/ACM Transactions on Networking|성=Thaler|이름=David|성2=Chinya Ravishankar|날짜=February 1998|권=6|호=1|쪽=1–14|doi=10.1109/90.663936}}</ref>

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

# '''낮은 오버헤드''' : 사용된 해시 함수가 효율적이므로 클라이언트의 오버헤드가 매우 낮다.
# '''[[부하분산|로드 밸런싱]]''' : 해시 함수가 랜덤하므로, ''n''개의 사이트 각각이 오브젝트 ''O''를 할당 받을 확률이 균등하다. 따라서 사이트 전체의 하중이 균일하다.
## '''사이트 용량''' : 용량이 다른 사이트는 용량에 비례하여 사이트 목록에 표시 될 수 있다. 다른 사이트 용량의 두 배인 사이트는 목록에 두 번 표시되고 다른 모든 사이트는 한 번 표시된다.
# '''높은 적중률''' : 모든 클라이언트가 동일한 사이트 ''S <sub>O</sub>''에 객체 ''O''를 배치하는 것에 동의하기 때문에, ''S <sub>O</sub>''에 대한 ''O''의 수정이나 이동 작업은 적중률의 측면에서 최대의 효율을 얻을 수 있다. 일부 교체 알고리즘에 의해 퇴거하지 않는 객체 ''O''는 ''S <sub>O</sub>''에서 항상 발견 될 것이다.
# '''최소 교란 :''' 사이트가 고장나면 해당 사이트에 매핑된 개체만 다시 매핑하면 된다. 입증된 바와 같이 교란은 최소화된다.<ref name=":0">{{웹 인용|url=http://www.eecs.umich.edu/techreports/cse/96/CSE-TR-316-96.pdf|제목=A Name-Based Mapping Scheme for Rendezvous|성=Thaler|이름=David|성2=Chinya Ravishankar|출판사=University of Michigan Technical Report CSE-TR-316-96|확인날짜=2013-09-15}}</ref><ref name=":1">{{저널 인용|제목=Using Name-Based Mapping Schemes to Increase Hit Rates|저널=IEEE/ACM Transactions on Networking|성=Thaler|이름=David|성2=Chinya Ravishankar|날짜=February 1998|권=6|호=1|쪽=1–14|doi=10.1109/90.663936}}</ref>
# '''분산된 ''k'' -agreement :''' 클라이언트는 단순히 순서에서 최고의 ''k'' 사이트를 선택하여 ''k'' 개의 사이트에 분산 합의에 도달할 수 있다.<ref name="foisting">{{저널 인용|제목=Key Foisting and Key Stealing Attacks in Sensor Networks'|저널=International Journal of Sensor Networks|성=Wang|이름=Peng|성2=Ravishankar|이름2=Chinya|url=http://www.cs.ucr.edu/~ravi/Papers/Jrnl/foisting.pdf|날짜=2015}}</ref>

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

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

=== 캐시 목록 라우팅 프로토콜 ===
=== 제어된 복제 ===
확장 가능한 해싱 또는 CRUSH<ref name="crush">{{웹 인용|url=http://www.crss.ucsc.edu/media/papers/weil-sc06.pdf|title=CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data|author=Sage A. Weil|display-authors=etal|확인날짜=2019-12-31|보존url=https://web.archive.org/web/20190220002858/https://www.crss.ucsc.edu/media/papers/weil-sc06.pdf|보존날짜=2019-02-20|url-status=dead}}</ref>에서의 제어된 복제는 RUSH<ref name="rush">{{웹 인용 |url=http://www.ssrc.ucsc.edu/media/papers/honicky-ipdps04.pdf |title=Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution |author=R. J. Honicky, Ethan L. Miller |확인날짜=2019-12-31 |보존url=https://web.archive.org/web/20170226050158/http://www.ssrc.ucsc.edu/media/papers/honicky-ipdps04.pdf |보존날짜=2017-02-26 |url-status=dead }}</ref>의 확장이다. RUSH는 해시를 이용하여 키를 탐색할 수 있는 트리를 생성하는 것으로 랑데부 해싱을 개선한다.
=== 스켈레톤 기반 변형 ===
n이 매우 클 때 스켈레톤 기반 변형은 실행 시간을 크게 향상 시킬 수 있다.<ref name="CSE Technical Report UCR-CS 2001-05062">{{서적 인용|last1=Yao|first1=Zizhen|last2=Ravishankar|first2=Chinya|last3=Tripathi|first3=Satish|title=Hash-Based Virtual Hierarchies for Caching in Hybrid Content-Delivery Networks|date=May 13, 2001|publisher=CSE Department, University of California, Riverside|location=Riverside, CA|url=http://static.cs.ucr.edu/store/techreports/UCR-CS-2001-05062.pdf|accessdate=15 November 2015}}</ref><ref>{{저널 인용|last=Wang|first=Wei|author2=Chinya Ravishankar |title=Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-hoc Networks|journal=Mobile Networks and Applications|date=January 2009|volume=14|issue=5|pages=625–637|doi=10.1007/s11036-008-0144-3}}</ref><ref>{{인용| first = Anup| last = Mayank| first2 = Trivikram | last2 = Phatak| first3 = Chinya| last3 = Ravishankar| title = Decentralized Hash-Based Coordination of Distributed Multimedia Caches | series = Proc. 5th IEEE International Conference on Networking (ICN'06) | year = 2006| place = Mauritius| publisher = IEEE| url = http://www.cs.ucr.edu/~ravi/Papers/NWConf/ICN2006.pdf}}</ref> 이 방법은 가상 계층 구조(스켈레톤)을 만들고 각 계층에서 HRW을 적용하여 <math>O(log n)</math>의 실행 시간을 가능하게 한다.

== 구현 ==

=== 가중 랑데부 해시 ===
가중 랑데부 해시를 구현하는 파이썬 코드 :<ref name="wrh">{{웹 인용|url=http://www.snia.org/sites/default/files/SDC15_presentations/dist_sys/Jason_Resch_New_Consistent_Hashings_Rev.pdf|제목=New Hashing Algorithms for Data Storage|성=Jason Resch}}</ref> <syntaxhighlight lang="python">
#!/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
</syntaxhighlight> WRH의 출력 예 : <syntaxhighlight lang="pycon">
[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)]'
</syntaxhighlight>

== 각주 ==
{{각주}}

[[분류:해싱]]
[[분류:알고리즘]]