데이터 재분배를 K/N으로 최소화하는 Consistent Hashing 기반 확장 가능 설계

Context

표준 Hashing 방식의 모듈러 연산 기반 서버 매핑은 클러스터 크기 변경 시 대부분의 키 위치가 변하는 Rehash Storm 발생 가능성 상존. 서버 추가 및 제거 시 발생하는 대규모 데이터 이동으로 인한 시스템 가용성 저하와 캐시 미스 급증이 주요 병목 지점임.

Technical Solution

• 해시 공간을 원형 Ring 구조로 설계하여 서버와 키를 동일한 가상 공간에 배치하는 구조 채택
• 특정 키에 대해 시계 방향으로 가장 가까운 서버에 매핑하는 Determinism 메커니즘 적용
• Virtual Nodes(VNodes) 도입을 통해 물리적 서버 한 대당 여러 가상 지점을 할당함으로써 데이터 불균형(Skew) 해결
• 서버 제거 시 해당 서버가 담당하던 키만 인접 서버로 이전하는 최소 단위 재분배 로직 구현
• 서버 추가 시 Ring 상의 특정 구간만 재할당하여 전체 시스템 영향도를 최소화하는 Elasticity 확보

Impact

• 서버 변경 시 재분배 대상 키를 전체의 약 1/N 수준으로 최소화
• Lookup Time $O(\log(N \times V))$ 및 Space Complexity $O(N \times V)$ 수준의 효율적 자원 관리 달성

Key Takeaway

정적 클러스터에서는 단순 Hashing이 효율적이나, 동적 확장성이 필수적인 분산 시스템에서는 데이터 이동 비용을 최소화하는 Consistent Hashing이 필수적임. 특히 VNodes를 통한 부하 분산 최적화가 실무 설계의 핵심임.