요약
- Consistent Hashing을 구현하는 자료구조로, 노드 추가/삭제 시 최소한의 키만 재배치됨
- 가상 노드를 통해 키의 균등 분포 문제를 해결
본문
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf
분산 시스템에서 데이터와 리소스를 효율적으로 관리하기 위함
- 리소스와 노드가 범위 R이 아래와 같이 정의 되어 있음
- R = [0. 2^k -1].
- 각 리소스와 노드는 해시링 위에 그들의 해시로 정의 됨
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 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 self.legalRange(hashValue):
temp = self.head
if temp is None:
return None
else:
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: Node, orig: Node, 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 self.legalRange(hashValue):
newNode = Node(hashValue)
if self.head is None: # there is not any node in hash ring
newNode.next = newNode
newNode.previous = newNode
self.head = newNode
else: # add new node
temp = self.lookupNode(hashValue)
newNode.next = temp
newNode.previous = previous
newNode.previous.next = newNode
newNode.next.previous = newNode
def addResources(self. hashValueResource):
if self.legalRange(hashValueResource):
targetNode = self.lookupNode(hashValueResource)
if targetNode:
value = "Dummy resource value of " + str(hashValueResource)
targetNode.resources[hashValueResource] = value
else:
raise Exception("No hash value")
- 노드간의 거리는 시계 방향, 반시계 방향 중 가까운 거리로 정의됨
이 알고리즘은 MIT에서 처음 제안되었고 기본 절차는 아래와 같음
- 서버와 키를 균등 분포 해시 함수를 이용해 해시링에 배치함
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
이 방식의 구현은 2가지 문제가 존재
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는게 불가능
- 파티션: 서버사이의 해시 공간
- 키의 균등 분포를 달성하기가 어렵다는 점
가상노드(virtual node)
- 실제 노드 or 서버를 가리키는 노드
- 하나의 서버는 링위에 여러개의 가상 노드를 가질 수 있음
- 키 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버
- 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐