[시스템 디자인] 5장. 안정 해시 설계

혀어어언·2025년 9월 16일
가상노드단순해시모듈러시스템디자인시스템설계안정해시설계

[북스터디] 시스템 디자인

목록 보기
7/14

5장. 안정 해시 설계

수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다
안정해시는 이를 달성하기 위해 보편적으로 사용하는 기술이다

1. 수평적 규모 확장이란?

  • 단일 서버 성능을 올리는 수직적 확장(Scale-up)과 달리, 서버를 여러 대로 나누어 부하를 분산하는 것
  • 균등하고 일관성 있는 데이터의 분산이 중요

2. 설계 관점에서의 서버 풀

2-1. 고정 서버 풀

  • 서버 수가 늘거나 줄지 않는 전제
  • 단순 해시(hash(key) % N)로도 충분
  • 균등 분포만 잘 맞추면 문제 없음

2-2. 변동 서버 풀

  • 현실 세계에서는 서버가 고정되지 않음:
    • 오토스케일링: 트래픽 스파이크 대응 위해 서버 증설/축소
    • 장애 대응: 서버가 죽으면 다른 서버로 재분배 필요
  • 이때 단순 모듈러 해시는 풀 사이즈가 바뀌면 전체 키 매핑이 바뀌는 문제 발생 → 재배치 비용이 매우 큼

3. 데이터 분산 방식

3-1. 단순 해시(Uniform / Modulo Hashing)

  • hash(key) % N (N = 서버 개수)로 분산
  • 키를 해시함수로 충분히 무작위로 섞은 후, 탐색이나 검색 없이 즉시 도달하는 인덱싱 모델
      long x = XxHash64.hash(keyBytes, seed); // 1. 해시 알고리즘 실행(섞기)
  int  i = Math.floorMod(x, N);           // 2. 범위 축소(인덱스 뽑기)
  Server s = servers[i];                  //    해당 인덱스의 서버 선택
  • 장점: 단순, 빠름, 균등 분배 가능
  • Naive 해시(hash(key) % N) 방식의 가장 큰 약점:
    • 서버 수 N이 바뀌면 전체 키 매핑이 바뀜.
    • 대규모 키 재배치발생 → 캐시 미스, 데이터 불일치 문제
  • 예: 서버 4대에서 5대로 확장 → 80% 이상의 키가 다른 서버로 이동

3-2. 안정 해시(Consistent Hashing)

4. 실무에서 고려할 점

4-1. 해시 함수 선택

  • 단순한 mod N 대신 어떤 해시 함수를 쓰느냐에 따라 분포 균등도가 달라짐
  • MD5, SHA-1 같은 암호학적 해시 vs MurmurHash, xxHash 같은 비암호학적 고속 해시
  • 분산 시스템에서는 충돌 최소화 + 속도 둘 다 중요

4-2. 가상 노드(Virtual Node, vnode)

  • 안정 해시만 쓰면 서버 개수가 적을 때 분포 불균형 발생
  • 각 서버를 여러 개의 가상 노드로 링에 배치하면 데이터 분포가 더 균등해짐

4-3. 서버 가중치(Weighted Consistent Hashing)

  • 모든 서버가 같은 스펙은 아님 → CPU, 메모리, 디스크, 네트워크 성능 차이 존재
  • 서버별 처리 능력에 따라 가중치 부여
  • 가상 노드 개수 ∝ 서버 성능 으로 균형 잡음

4-4. 데이터 이동 비용 (Resharding Overhead)

  • 서버 추가/삭제 시에도 일부 키는 이동해야 함
  • 데이터 이동 과정에서 캐시 미스 폭증, 백엔드(DB) 부하 급증 가능
  • 이를 줄이기 위해:
    • 백그라운드 점진적 마이그레이션
    • 더블 라이트(Double-write) 전략
    • 버전 기반 라우팅

4-5. 안정 해시와 CAP 정리

  • 분산 환경에서 노드 장애 → 데이터 재배치 → 일관성(Consistency) 문제 발생
  • Dynamo, Cassandra는 Eventual Consistency + 안정 해시 모델을 채택
  • RDBMS 스타일의 Strong Consistency를 원하면 안정 해시 적용 범위에 제약 생김

1) Eventual Consistency란?

  • 분산 시스템에서 모든 복제본(replica)이 즉시는 아니지만, 충분한 시간이 지나면 결국 동일한 상태로 수렴하는 일관성 모델
  • CAP 이론에서 Availability(가용성)과 Partition Tolerance(분할 내성)을 우선할 때 주로 채택
  • 강한 일관성(Strong Consistency)과 달리, 읽는 순간마다 최신 데이터를 보장하지 않는다
2) 동작 원리
  • 쓰기 요청이 들어오면 모든 노드에 동시에 적용되지 않고, 먼저 도착한 일부 노드에서 처리됨
  • 나머지 노드들은 비동기적 복제 / 동기화 프로세스를 통해 나중에 같은 데이터로 맞춰짐
  • 결국 어느 시점에는 모든 복제본이 같은 값을 가지게 됨
3) C.A.P
  • Consistency (일관성)
    → 모든 노드가 같은 시점에 동일한 데이터를 보여준다
  • Availability (가용성)
    → 모든 요청에 대해 항상 응답을 돌려줄 수 있다 (성공/실패 여부 무관)
  • Partition Tolerance (분할 내성)
    → 네트워크가 분리(Partition)돼도 시스템은 계속 동작할 수 있다

4-6. 안정 해시 대안 기법

1) Rendezvous Hashing (HRW, Highest Random Weight)

  • Consistent Hashing보다 간단하면서도 비슷한 재배치 성질
  • 구글 GFS, Ceph, 일부 CDN에서 사용
    • 장점: 균등 분포, 구현 단순, Consistent Hashing보다 데이터 이동량이 더 적을 수 있음

2) Jump Consistent Hashing

  • 구글이 제안, O(1) 시간 복잡도, 균등 분포 뛰어남
  • Kafka, FoundationDB 같은 대규모 분산 시스템에서 채택

5. 운영 단계에서 해시와 안정 해시의 문제들

5-1. 데이터 분포 균등성 (Uniformity)

  • 해시는 이상적으로 키를 균등하게 분배해야 함
  • 하지만 실제 운영에서는 Hotspot Key / Celebrity Problem이 발생:
    • 예: 특정 사용자 ID(연예인 계정), 특정 해시 범위에만 트래픽 집중
  • 안정 해시를 쓰더라도, 키 분포 자체가 편향되면 샤드 불균형은 피할 수 없음

해결 전략

  • Sharding Key 설계: 고카디널리티(high cardinality) 키 선택
  • Hash Salting: 키에 무작위성을 추가해 편향 완화
  • Virtual Nodes (가상 노드): 한 물리 노드가 여러 해시 구간 담당 → 균등화

5-2. 노드 추가/삭제 시 데이터 재배치 비용

  • 단순 해싱(Mod N) 방식:
    • 서버 수가 바뀌면, 전체 키의 대부분이 다른 서버로 이동 → 재배치 비용 큼
  • 안정 해시:
    • 노드 추가/삭제 시, 해당 구간 일부 키만 이동 → 비용 최소화
  • 그러나 재배치 자체는 여전히 비용:
    • TB 단위 데이터를 옮기는 데 수시간~수일
    • 그동안 읽기/쓰기 지연 발생

해결 전략

  • Rebalancing Window: 트래픽이 낮은 시간대에 점진적 재분배
  • Double Write: 재분배 기간 동안 두 노드에 동시에 기록해 일관성 유지
  • Lazy Migration: 요청 시점에 필요한 키만 새로운 노드로 점진적으로 옮김

5-3. 데이터 일관성 (Consistency)

  • 분산 해시 환경에서는, 노드 이동/장애 시 데이터 복제가 중요
  • 안정 해시의 기본 구조는 N개의 인접 노드에 복제(replica) → Dynamo, Cassandra.
  • 문제:
    • 네트워크 분할(Partition) → 일부 노드만 최신 데이터 보유
    • 복제본 간 충돌(conflict) 발생

해결 전략

  • Quorum 기반 읽기/쓰기: W+R > N 보장 (예: 3개의 복제 중 2개 이상 성공해야 ack)
  • Conflict Resolution: Last Write Wins, Vector Clock, CRDT 등
  • Eventual Consistency 허용 여부 결정: 애플리케이션 성격 따라 선택

5-4. 장애 복구와 트래픽 우회

  • 노드가 죽으면, 해당 구간 키 요청이 모두 장애로 이어짐

  • 안정 해시는 바로 인접 노드로 우회 가능하지만, 실제 운영은 더 복잡:

    • 캐시/DB 미스율 폭발
    • 특정 노드로 트래픽 집중(2차 장애)

    해결 전략

  • Replica 활용: 읽기는 다른 복제본에서 즉시 처리

  • Auto-Rebalancing 제어: 장애 시 자동 리밸런싱을 막고, 임시 우회 후 복구 단계에서 이동

  • Rate Limiting + Circuit Breaker: Failover 중 과부하 방지

5-5. 관측성과 모니터링

  • 운영 시 가장 큰 문제 중 하나는 샤드 불균형을 조기에 탐지하지 못하는 것
  • 해시 분포 문제는 지표로 드러남:
    • 샤드별 QPS, Latency, Storage Usage, Cache Hit Rate
  • 안정 해시라고 해서 자동으로 "균등"이 보장되는 건 아님 → 반드시 모니터링 필요

핵심 지표

  • 키 분포 균등도(Entropy)
  • 샤드별 Hotspot 비율
  • 재배치 중 지연 시간 증가율

5-6. 운영 환경에서의 설계 Trade-off

1) 서버 풀(Server Pool)의 고정 vs 변동

  • 고정 풀: 서버 수가 잘 변하지 않으면, 단순 해싱(Mod N)도 가능 → 운영 단순
  • 변동 풀: 클라우드 오토스케일링, 다중 데이터센터 환경이라면 → 안정 해시 필수

2) 데이터 분포

  • 분포가 완전히 랜덤이라면 이상적 → 하지만 실제 키는 특정 패턴(사용자 ID, 지역, 시간대)에 따라 편향
  • 해시 함수 선택, 키 설계가 중요

3) 안정 해시와 변형 기법

  • Virtual Nodes: 균등화 보완
  • Jump Hashing: O(1) 매핑, 대규모 클러스터 효율적
  • Rendezvous Hashing: 데이터 이동량 최소화
profile
혀어어언
이전 포스트

[시스템 디자인] 4장. 처리율 제한 장치의 설계

다음 포스트

[시스템 디자인] 6장. 키-값 저장소

0개의 댓글