에듀테크 프로젝트 대시보드
일관된 해싱 (Consistent Hashing)
여러 대의 서버에 데이터를 나눠 저장할 때 가장 단순한 방법은 server = hash(key) % N 이다.
하지만 서버가 한 대 늘거나 줄면 N 이 바뀌면서 거의 모든 키가 다른 서버로 이동한다(캐시 전체 무효화).
일관된 해싱은 키와 서버를 같은 해시 링 위에 올려놓고, 각 키를 "시계 방향으로 만나는 첫 서버"에 맡긴다.
서버가 바뀌어도 영향받는 키는 평균 1/N 뿐이다.
현재 키 0개 · 서버 0대 상태에서 서버를 한 대 더 추가하면 몇 개의 키가 다른 서버로 옮겨가야 하는지 비교한다.
왜 차이가 날까? 모듈러 방식은 나눗셈의 나머지가 N 에 의존하므로 N 이 바뀌면 거의 모든 매핑이 깨진다. 일관된 해싱에서 새 서버는 링의 한 구간만 넘겨받으므로, 그 구간에 있던 키만 이동한다.
# 링은 정렬된 (해시값 → 서버) 목록. 가상 노드로 각 서버를 여러 번 배치한다. def build_ring(servers, vnodes=100): ring = [] for s in servers: for i in range(vnodes): ring.append( (hash(f"{s}#{i}"), s) ) return sorted(ring) def lookup(ring, key): h = hash(key) for (pos, server) in ring: # 실제로는 이진 탐색 O(log M) if pos >= h: return server return ring[0][1] # 링을 한 바퀴 돌아 처음으로
O(log M) (M = 총 vnode 수).ketama).