요약
- Consistent Hashing 알고리즘을 구현하는 자료구조.
- 노드들이 원형 이중 연결 리스트로 이어져 있고, 각 노드는 해시 공간
R = [0, 2^k - 1]위의 자신의 위치(hashValue)와 담당 리소스를 가진다. - 키 → 노드 매핑은 시계 방향 거리 함수로 결정된다.
본문
배경 알고리즘과 가상 노드 같은 개념적 논의는 Consistent Hashing 참고. 이 노트는 자료구조 표현과 핵심 연산에 집중한다.
자료구조 정의
- 각
Node는 다음을 가진다:hashValue: 해시 공간 위 자신의 위치resources: 자신이 담당하는 리소스 사전 (key → value)next,previous: 원형 이중 연결 리스트 포인터
- 해시 공간은
R = [0, 2^k - 1]. - 두 점 사이 거리는 시계 방향 거리로 정의:
a == b이면 0a < b이면b - a- 그 외 (링을 한 바퀴 돌아야 할 때)에는
2^k + b - a
- 즉 시계 방향으로 얼마나 가야 b에 도달하는지를 나타낸다.
핵심 연산
lookupNode(hashValue) — 키가 저장될 노드 찾기
head부터 시작해 시계 방향으로 이동하면서,distance(temp, hashValue)가distance(temp.next, hashValue)보다 큰 동안 계속 진행.- 거리가 더 이상 줄지 않는 시점의 다음 노드가 키 담당자.
addNode(hashValue) — 새 노드 삽입
- 링이 비어 있으면 자기 자신을
next/previous로 가리키게 함. - 그렇지 않으면
lookupNode로 삽입 위치를 찾아 이중 연결을 끊고 새 노드를 끼워 넣음.
moveResources(dest, orig, deleteTrue) — 노드 추가/제거 시 리소스 재배치
orig의 리소스 중dest까지의 거리가orig까지의 거리보다 짧은 것만 옮김.deleteTrue이면 모든 리소스를 옮김 (노드 제거 케이스).
Python 구현
class Node:
def __init__(self, hashValue):
self.hashValue = hashValue
self.resources = {}
self.next = None
self.previous = None
class HashRing:
def __init__(self, k):
self.head = None
self.k = k
self.min = 0
self.max = 2**k - 1
def legalRange(self, hashValue):
return self.min <= hashValue <= self.max
def distance(self, a, b):
if a == b:
return 0
elif a < b:
return b - a
return (2**self.k) + b - a
def lookupNode(self, hashValue):
if not self.legalRange(hashValue):
return None
temp = self.head
if temp is None:
return None
while self.distance(temp.hashValue, hashValue) > self.distance(temp.next.hashValue, hashValue):
temp = temp.next
if temp.hashValue == hashValue:
return temp
return temp.next
def moveResources(self, dest, orig, deleteTrue):
delete_list = []
for i, j in orig.resources.items():
if self.distance(i, dest.hashValue) < self.distance(i, orig.hashValue) or deleteTrue:
dest.resources[i] = j
delete_list.append(i)
for i in delete_list:
del orig.resources[i]
def addNode(self, hashValue):
if not self.legalRange(hashValue):
return
newNode = Node(hashValue)
if self.head is None:
newNode.next = newNode
newNode.previous = newNode
self.head = newNode
else:
temp = self.lookupNode(hashValue)
newNode.next = temp
newNode.previous = temp.previous
newNode.previous.next = newNode
newNode.next.previous = newNode
def addResources(self, hashValueResource):
if not self.legalRange(hashValueResource):
return
targetNode = self.lookupNode(hashValueResource)
if targetNode:
value = "Dummy resource value of " + str(hashValueResource)
targetNode.resources[hashValueResource] = value
else:
raise Exception("No hash value")