83%의 캐시 미스를 15%로 줄이는 Consistent Hashing 구현 전략

Context

서버 추가 시 Modulo 연산 방식의 해시 맵핑은 대다수 키의 위치를 변경함. 이로 인해 발생하는 대규모 Cache Miss가 데이터베이스에 부하를 주는 Thundering Herd 현상 유발. 노드 변경 시 데이터 이동을 최소화하는 구조적 설계 필요.

Technical Solution

• 0부터 2^32까지의 해시 링 구조를 도입하여 노드와 키를 동일 선상에 배치하는 설계
• 키 위치에서 시계 방향으로 가장 가까운 노드에 데이터를 할당하여 노드 추가 시 인접 구간만 재배치하는 방식
• 물리 노드당 다수의 Virtual Node를 배치하여 해시 링 상의 데이터 불균형 문제를 해결하는 전략
• 읽기 빈도가 높은 링 조회 특성을 고려하여 sync.RWMutex를 통한 잠금 세분화로 동시성 성능 최적화
• FNV-1a, MD5, CRC32 등 다양한 해시 함수를 인터페이스로 추상화하여 교체 가능한 구조 설계
• 이진 탐색(Binary Search) 기반의 O(log n) 조회 성능을 확보한 정렬 슬라이스 구현

Impact

• 노드 확장(5→6개) 시 키 재배치 비율: Modulo 방식 83.8%(83,803개) → Consistent Hashing 15.7%(15,723개)
• Virtual Node 수 증가에 따른 데이터 분포 표준편차: 1개(11,353) → 150개(2,824) → 500개(976)
• 최악 노드의 데이터 할당 비율: Virtual Node 1개일 때 공평 배분 대비 3.20배 → 500개일 때 1.17배로 개선

Key Takeaway

분산 시스템에서 상태를 가진 노드의 집합이 변동될 때, 전체 시스템의 재조정 비용을 최소화하기 위해 데이터 배치와 노드 위치를 논리적 링 구조로 추상화하는 설계 원칙이 중요함.