랑데부 해싱

3. 알고리즘

랑데부 해싱 알고리즘의 기본 아이디어는 각 사이트에 객체에 대한 점수(가중치)를 부여하고, 가장 높은 점수를 내는 사이트에 객체를 할당하는 것이다. 모든 클라이언트는 해시 함수 ''h()''에 대해 합의해야 한다.

객체 ''O_i''에 대해 사이트 ''S_j''는 가중치 ''w_i,j = h(O_i, S_j)''를 갖는다. 이 가중치가 가장 큰 사이트에 ''O_i''를 할당한다. 예를 들어, ''k=1''인 경우, 객체 $O\_i$는 $n$개의 사이트 $S\_1,\; S\_2\; \backslash dots\; S\_n$ 중 $n$개의 해시 값 $h(O\_i,\; S\_j)$을 계산하여 가장 높은 해시 값을 생성하는 사이트 $S\_k$에 배치된다.

사이트가 추가되거나 제거될 경우, 해당 사이트에 매핑된 개체만 다시 매핑된다. 새 사이트 $S\_\{n+1\}$이 추가되면, 새로운 객체 배치 또는 요청은 $n+1$개의 해시 값을 계산하고 이 중 가장 큰 값을 선택한다. 만약 $S\_k$에 이미 있는 객체가 이 새로운 사이트 $S\_\{n+1\}$에 매핑되면 새롭게 가져와 $S\_\{n+1\}$에 캐싱된다.

사이트 간 용량이 다른 경우에도 랑데부 해싱은 쉽게 적용할 수 있다. 예를 들어, 특정 사이트의 용량이 다른 사이트의 두 배라면 해당 사이트를 목록에 두 번 나타내는 방식으로 처리할 수 있다.

분산된 ''k''-합의가 필요한 경우, 클라이언트는 ''k''개의 해시 값이 가장 큰 사이트를 독립적으로 선택하면 된다.

기본 HRW의 $O(n)$ 배치 비용은 문제가 되지 않을 수 있지만, HRW 알고리즘의 변형을 통해 객체 위치를 찾는 시간 복잡도를 $O(\backslash log\; n)$으로 줄일 수도 있다.

3. 1. 속성

• '''낮은 오버헤드''': 사용된 해시 함수가 효율적이므로 클라이언트의 오버헤드가 매우 낮다.
• '''부하 분산''': 해시 함수가 무작위화되므로, 각 ''n''개 사이트가 객체 ''O''를 수신할 가능성이 동일하다. 부하는 사이트 전체에 균일하게 분산된다.
• '''사이트 용량''': 서로 다른 용량을 가진 사이트는 용량에 비례하는 다중성으로 사이트 목록에 표시될 수 있다. 다른 사이트의 두 배 용량을 가진 사이트는 목록에 두 번 표시되는 반면, 다른 모든 사이트는 한 번 표시된다.
• '''높은 적중률''': 모든 클라이언트가 객체 ''O''를 동일한 사이트 ''S_O''에 배치하는 데 동의하므로 ''S_O''에 대한 각 가져오기 또는 배치 작업은 적중률 측면에서 최대 유틸리티를 제공한다. 객체 ''O''는 ''S_O''에서 일부 교체 알고리즘에 의해 제거되지 않는 한 항상 발견된다.
• '''최소 교란''': 사이트가 고장나면 해당 사이트에 매핑된 개체만 다시 매핑하면 된다. 교란은 최소화된다.^[45][46]
• '''분산된 ''k''-agreement''': 클라이언트는 단순히 순서에서 최고의 ''k'' 사이트를 선택하여 ''k'' 개의 사이트에 분산 합의에 도달할 수 있다.^[47]

4. 가중 변형

표준 랑데부 해싱은 모든 노드가 동일한 수의 키를 할당받는 것을 가정하지만, 실제로는 노드마다 용량이 다를 수 있다. 예를 들어, 한 노드가 다른 노드보다 저장 용량이 두 배 크다면, 알고리즘이 이를 고려하여 용량이 큰 노드에 더 많은 키를 할당하는 것이 효율적일 수 있다.

이러한 문제를 해결하기 위해, 용량이 큰 노드에 더 많은 키를 할당하기 위한 다양한 변형들이 제안되었다. 간단한 접근 방식은 큰 노드에 여러 개의 가상 위치를 할당하여 더 많은 키를 받도록 하는 것이다. 하지만 이 방식은 노드 간 용량 비율이 정수가 아닐 경우 성능 저하를 유발할 수 있다. 예를 들어, 한 노드가 다른 노드보다 42% 더 큰 용량을 가진 경우, 많은 가상 노드를 추가해야 하므로 성능이 크게 떨어진다. 이러한 제약을 극복하기 위해 여러 수정 방법이 제안되었다.^[21]

4. 1. 캐시 목록 라우팅 프로토콜 (CARP)

4. 2. 제어된 복제 (CRUSH)

4. 3. 스켈레톤 기반 변형

5. 일관된 해싱과의 비교

랑데부 해싱은 일관 해싱에 비해 단순성, 낮은 오버헤드, 일반성 면에서 뚜렷한 장점을 지닌다.^[3][4][5] 랑데부 해싱은 토큰을 미리 계산하거나 저장할 필요가 없다는 점에서 일관된 해싱과 차별화된다.

일관된 해싱은 특정 조건을 만족하는 해시 함수를 사용하면 랑데부 해싱의 특수한 경우로 볼 수 있다. 그러나 랑데부 해싱은 사이트당 토큰 수가 제한된 경우 일관된 해싱으로 환원될 수 없다. 이는 랑데부 해싱이 제거된 사이트의 객체를 무제한의 다른 사이트로 재할당할 수 있기 때문이다.

랑데부 해싱은 분산 k-합의와 같은 문제에 대한 간단한 솔루션을 제공한다는 장점도 있다.

6. 구현

가중 랑데부 해시(Weighted Rendezvous Hash, WRH)를 구현하는 파이썬 코드는 다음과 같다.^[53]

```python

#!/usr/bin/env python

import mmh3

import math

def int_to_float(value: int) -> float:

"""균일하게 임의의 64비트 정수를 [0, 1) 구간의 균일하게 임의의 부동 소수점 숫자로 변환한다."""

fifty_three_ones = (0xFFFFFFFFFFFFFFFF >> (64 - 53))

fifty_three_zeros = float(1 << 53)

return (value & fifty_three_ones) / fifty_three_zeros

class Node(object):

"""가중 랑데부 해시의 일부로 키가 할당된 노드를 나타내는 클래스이다."""

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):

"""제공된 키를 담당하는 다양한 가중치의 노드 집합 중 노드를 결정한다."""

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의 출력 예는 다음과 같다.

```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)]'

```

해시 함수 $h(\backslash cdot)$가 선택되면 구현은 간단하다. 각 클라이언트는 $n$개의 각 사이트에 대한 해시 값을 계산한 다음 가장 큰 값을 선택하면 된다. 이 알고리즘은 $O(n)$ 시간에 실행된다. 해시 함수가 효율적이라면 $n$이 매우 크지 않은 한 $O(n)$의 실행 시간은 문제가 되지 않는다.^[1][2]

다음은 가중 랑데부 해싱을 파이썬으로 구현한 또 다른 코드이다.^[27]

```python

import mmh3

import math

from dataclasses import dataclass

from typing import List

def hash_to_unit_interval(s: str) -> float:

"""문자열을 단위 구간 (0, 1]으로 해싱한다."""

return (mmh3.hash128(s) + 1) / 2**128

@dataclass

class Node:

"""가중 랑데부 해싱의 일부로 키가 할당된 노드를 나타내는 클래스이다."""

name: str

weight: float

def compute_weighted_score(self, key: str):

score = hash_to_unit_interval(f"{self.name}: {key}")

log_score = 1.0 / -math.log(score)

return self.weight * log_score

def determine_responsible_node(nodes: list[Node], key: str):

"""제공된 키를 담당하는 다양한 가중치의 노드 집합 중 노드를 결정한다."""

return max(

nodes, key=lambda node: node.compute_weighted_score(key), default=None)

```

WRH의 출력 예시는 다음과 같다.

```pycon

>>> import wrh

>>> node1 = wrh.Node("node1", 100)

>>> node2 = wrh.Node("node2", 200)

>>> node3 = wrh.Node("node3", 300)

>>> str(wrh.determine_responsible_node([node1, node2, node3], "foo"))

"Node(name='node1', weight=100)"

>>> str(wrh.determine_responsible_node([node1, node2, node3], "bar"))

"Node(name='node2', weight=300)"

>>> str(wrh.determine_responsible_node([node1, node2, node3], "hello"))

"Node(name='node2', weight=300)"

>>> nodes = [node1, node2, node3]

>>> from collections import Counter

>>> responsible_nodes = [wrh.determine_responsible_node(

... nodes, f"key: {key}").name for key in range(45_000)]

>>> print(Counter(responsible_nodes))

Counter({'node3': 22487, 'node2': 15020, 'node1': 7493})

참조

<sub>[1]</sub> 웹사이트 A Name-Based Mapping Scheme for Rendezvous http://www.eecs.umic[...] University of Michigan Technical Report CSE-TR-316-96 2013-09-15
<sub>[2]</sub> 논문 Using Name-Based Mapping Schemes to Increase Hit Rates 1998-02
<sub>[3]</sub> 웹사이트 Rendezvous Hashing Explained - Randorithms https://randorithms.[...] 2021-03-29
<sub>[4]</sub> 웹사이트 Rendezvous hashing: my baseline "consistent" distribution method - Paul Khuong: some Lisp https://pvk.ca/Blog/[...] 2021-03-29
<sub>[5]</sub> 웹사이트 Rendezvous Hashing https://medium.com/i[...] 2021-03-29
<sub>[6]</sub> 논문 Supporting mobile device communications in the presence of broadcast servers http://www.cs.ucr.ed[...] 2006
<sub>[7]</sub> 논문 An efficient parallelized L7-filter design for multicore servers 2012-10
<sub>[8]</sub> 논문 Key Foisting and Key Stealing Attacks in Sensor Networks' http://www.cs.ucr.ed[...] 2015
<sub>[9]</sub> 논문 Distributed Architecture of Oracle Database In-memory 2015-08
<sub>[10]</sub> 웹사이트 Introducing the GitHub Load Balancer https://github.blog/[...] 2022-02-01
<sub>[11]</sub> 간행물 Apache Ignite https://en.wikipedia[...] 2022-12-09
<sub>[12]</sub> 웹사이트 Tahoe-LAFS https://tahoe-lafs.o[...] 2023-01-02
<sub>[13]</sub> 논문 Scale and performance in the CoBlitz large-file distribution service 2006
<sub>[14]</sub> 웹사이트 Router Process · Apache Druid https://druid.apache[...] 2023-01-02
<sub>[15]</sub> 웹사이트 IBM Cloud Object Storage System, Version 3.14.11, Storage Pool Expansion Guide https://www.ibm.com/[...] 2023-01-02
<sub>[16]</sub> 웹사이트 Arvados {{!}} Keep clients https://doc.arvados.[...] 2023-01-02
<sub>[17]</sub> 웹사이트 Horizontally scaling Kafka consumers with rendezvous hashing https://www.tinybird[...] 2023-02-15
<sub>[18]</sub> 웹사이트 Rendezvous Hashing https://medium.com/i[...] 2022-12-09
<sub>[19]</sub> 논문 Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony http://tools.ietf.or[...] IETF 2013-09-17
<sub>[20]</sub> 논문 Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised) http://tools.ietf.or[...] IETF 2013-09-17
<sub>[21]</sub> 웹사이트 Cache Array Routing Protocol v1.0 http://tools.ietf.or[...] Internet Draft 2013-09-15
<sub>[22]</sub> 웹사이트 Cache Array Routing Protocol and Microsoft Proxy Server 2.0 http://oldsite.mcoec[...] Microsoft 2013-09-15
<sub>[23]</sub> 서적 Hash-Based Virtual Hierarchies for Caching in Hybrid Content-Delivery Networks http://static.cs.ucr[...] CSE Department, University of California, Riverside 2015-11-15
<sub>[24]</sub> 논문 Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-hoc Networks 2009-01
<sub>[25]</sub> 간행물 Decentralized Hash-Based Coordination of Distributed Multimedia Caches http://www.cs.ucr.ed[...] IEEE
<sub>[26]</sub> 논문 Dynamo http://www.allthings[...] 2018-06-07
<sub>[27]</sub> 웹사이트 New Hashing Algorithms for Data Storage http://www.snia.org/[...]
<sub>[28]</sub> 웹사이트 CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data http://www.crss.ucsc[...]
<sub>[29]</sub> 웹사이트 Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution http://www.ssrc.ucsc[...]
<sub>[30]</sub> 웹사이트 Crush Maps http://docs.ceph.com[...]
<sub>[31]</sub> 논문 Weighted Distributed Hash Tables
<sub>[32]</sub> 웹인용 A Name-Based Mapping Scheme for Rendezvous http://www.eecs.umic[...] University of Michigan Technical Report CSE-TR-316-96 2013-09-15
<sub>[33]</sub> 논문 Using Name-Based Mapping Schemes to Increase Hit Rates
<sub>[34]</sub> 웹인용 A Name-Based Mapping Scheme for Rendezvous http://www.eecs.umic[...] University of Michigan Technical Report CSE-TR-316-96 2013-09-15
<sub>[35]</sub> 웹인용 Distributed Core Multicast (DCM): a routing protocol for many small groups with application to mobile IP telephony http://tools.ietf.or[...] IETF 2013-09-17
<sub>[36]</sub> 웹인용 Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised) http://tools.ietf.or[...] IETF 2013-09-17
<sub>[37]</sub> 웹인용 Cache Array Routing Protocol v1.0 http://tools.ietf.or[...] Internet Draft 2013-09-15
<sub>[38]</sub> 웹인용 Cache Array Routing Protocol and Microsoft Proxy Server 2.0 http://oldsite.mcoec[...] Microsoft 2013-09-15
<sub>[39]</sub> 논문 Supporting mobile device communications in the presence of broadcast servers http://www.cs.ucr.ed[...] 2006
<sub>[40]</sub> 논문 An efficient parallelized L7-filter design for multicore servers 2012-10
<sub>[41]</sub> 논문 Key Foisting and Key Stealing Attacks in Sensor Networks' http://www.cs.ucr.ed[...] 2015
<sub>[42]</sub> 논문 Distributed Architecture of Oracle Database In-memory 2015-08
<sub>[43]</sub> 웹인용 A Name-Based Mapping Scheme for Rendezvous http://www.eecs.umic[...] University of Michigan Technical Report CSE-TR-316-96 2013-09-15
<sub>[44]</sub> 논문 Using Name-Based Mapping Schemes to Increase Hit Rates 1998-02
<sub>[45]</sub> 웹인용 A Name-Based Mapping Scheme for Rendezvous http://www.eecs.umic[...] University of Michigan Technical Report CSE-TR-316-96 2013-09-15
<sub>[46]</sub> 논문 Using Name-Based Mapping Schemes to Increase Hit Rates 1998-02
<sub>[47]</sub> 논문 Key Foisting and Key Stealing Attacks in Sensor Networks' http://www.cs.ucr.ed[...] 2015
<sub>[48]</sub> 웹인용 CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data https://web.archive.[...] 2019-12-31
<sub>[49]</sub> 웹인용 Replication Under Scalable Hashing: A Family of Algorithms for Scalable Decentralized Data Distribution https://web.archive.[...] 2019-12-31
<sub>[50]</sub> 서적 Hash-Based Virtual Hierarchies for Caching in Hybrid Content-Delivery Networks http://static.cs.ucr[...] CSE Department, University of California, Riverside 2001-05-13
<sub>[51]</sub> 논문 Hash-Based Virtual Hierarchies for Scalable Location Service in Mobile Ad-hoc Networks 2009-01
<sub>[52]</sub> 간행물 Decentralized Hash-Based Coordination of Distributed Multimedia Caches http://www.cs.ucr.ed[...] IEEE
<sub>[53]</sub> 웹인용 New Hashing Algorithms for Data Storage http://www.snia.org/[...]