요약
- 분산 시스템에서 노드 추가/제거 시 최소한의 키만 재배치하는 해싱 기법
- 서버 스케일링 시 대규모 캐시 미스를 방지하는 핵심 알고리즘
본문
- consistent hashing는 웹 캐시에서 주목을 받음
- 요구 사항
- 리소스와 노드 상의 매핑이 빠르고 쉬어야 함
- 다른 노드 사이의 리소스 부하가 비교적 균등 해야함
- 매핑은 자주 발생하는 도착과 출발에 대비해 유연해야한다.
- 리소스가 꺼질 것에 대해 대비가 되어 있어야한다는 뜻
전형적인 해시 문제
- 리소스가 추가 되거나, 제거 되었을 때 어떤식으로 부하를 재배치 할지 정하는 문제가 존재함
- classical hash table들은 새로운 해시 함수를 이용해 다른 범위로 재해싱한 후 새로운 테이블로 옮기는 방식으로 리사이징이 가능한데 이는 매우 비싼 operation이 를 Rehash 문제라고 함
- N개의 캐시 서버가 있고 N개의 서버에 부하를 균등하게 나누는 보편적인 방법은
- serverIndex = hash(key) % N(N은 서버 수)
- 이 방식은 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작함, 기존 서버가 삭제되면 문제가 생김
- 키 기준으로 해싱되어 있기 때문에 균등하게 배치 되지 않을 뿐더러, 클라이언트가 캐시가 저장되어 있지 않은 서버에 접근하기 때문에 대규모 캐시 미스 발생
- 이 상태에서 서버의수(N이 감소 하면)
해시 링 기본 절차
- 서버와 키를 균등 분포 해시 함수를 이용해 해시링에 배치함
- 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버
- 리소스와 노드가 범위 R = [0, 2^k - 1] 아래에 정의되어 있고, 각 리소스와 노드는 해시링 위에 그들의 해시로 정의됨
이 방식의 구현은 2가지 문제가 존재
- 서버가 추가되거나 삭제되는 상황을 감안하면 파티션 크기를 균등하게 유지하는게 불가능
- 파티션: 서버사이의 해시 공간
- 키의 균등 분포를 달성하기가 어렵다는 점
가상노드(virtual node)
- 실제 노드 or 서버를 가리키는 노드
- 하나의 서버는 링위에 여러개의 가상 노드를 가질 수 있음
- 키 위치로부터 시계 방향으로 링을 탐색하다 만나는 최초의 가상 노드가 해당 키가 저장될 서버
- 가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해짐
구현 코드 (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 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, 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 self.legalRange(hashValue):
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 = 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”)