Consistent Hashing 도입으로 노드 확장 시 데이터 재배치 비용 75% 감소

Context

Modulo Hashing 방식의 서버 추가/삭제 시 발생하는 대규모 Cache Miss 및 데이터 이동 문제 분석. 노드 수 변동에 따라 거의 모든 키가 재매핑되는 구조적 한계로 인한 시스템 불안정성 해결 필요.

Technical Solution

• 0~2^32 범위의 원형 숫자선 상에 Node와 Key를 배치하는 Consistent Hashing Ring 설계
• bisect_right 함수를 활용한 시계 방향 탐색 기반의 최적 노드 매핑 로직 구현
• 불균형한 데이터 분산 해결을 위해 물리 노드당 다수의 Virtual Nodes를 배치하는 전략 채택
• Replication Factor 설정을 통해 키 위치부터 시계 방향으로 N개의 고유 노드에 데이터를 복제하는 가용성 구조 설계
• 서버 사양에 비례하여 Virtual Nodes 수를 조절하는 Weight 기반의 부하 분산 메커니즘 적용
• 해시 충돌 및 경계값 처리를 위한 Wraparound 로직을 통한 링 구조의 완결성 확보

Impact

• 노드 추가 시 Modulo Hashing(약 75% 이동) 대비 데이터 이동량을 25% 수준으로 최적화
• Virtual Nodes 150개 적용 시 각 노드별 데이터 점유율을 약 33.3% 수준으로 균등하게 분산