문제

분산된 환경에서는 해시 키를 많이 사용한다.

• 분산 캐시(예: Redis): 서비스에 캐시 서버가 여러 대 있을 때, 어떤 서버에 데이터를 저장할지 결정해야 함.
• 데이터베이스 샤딩 (Sharding): 데이터베이스가 너무 커서 여러 DB 인스턴스로 나누고 싶을 때.
  분산환경에서 일반적으로 사용하는 해시 방식(hash(key) % N)에는 치명적인 문제가 하나 있다. 서버 개수가 바뀌면(추가되거나 삭제되면) 거의 모든 키의 매핑이 바뀐다는 것이다.

예를 들어

hash(key) % 3   → 서버 A, B, C 중 하나

이 상태에서 서버 D를 추가하면

hash(key) % 4

가 되어 기존 키의 75%가 다른 서버로 이동해야 한다.
이건 캐시 서버나 샤딩 구조에서는 재앙이다.

→ 안정 해시는 이런 “리밸런싱 문제”를 최소화하기 위해 등장했다.

안정 해시

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

해시 공간과 해시 링

안정 해시의 핵심 아이디어

안정 해시는 “서버와 키를 같은 해시 공간에 매핑”해서 서버 추가/삭제 시 재분배되는 키의 양을 최소화한다.

개념 요약
1. 0 ~ 2³² (혹은 큰 해시 공간)을 원형 링(Circle)으로 만든다.
2. 서버(Node)를 해시 함수로 링 위에 위치시킨다.
예: hash("ServerA") = 12345
3. 키(Key)도 같은 해시 함수를 사용해 링 위에 위치시킨다.
예: hash("User123") = 20000
4. 키는 자신보다 ‘시계 방향’으로 가장 가까운 서버에 할당된다.

즉, 링 위에서 “바로 다음 서버”가 담당하는 것이다.

서버 추가/삭제 시 변화

서버 추가

• 새 서버를 링 위의 특정 지점에 추가하면,
  그 서버가 위치한 구간의 일부 키만 재할당된다.
• 나머지 키는 그대로 유지됨.

서버 제거

• 제거된 서버가 담당하던 구간의 키들만
  “다음 서버”로 이동.

즉, 전체 키의 1/N 정도만 이동하면 된다. (N = 서버 개수)

하지만 이 접근법에는 두 가지 문제가 존재한다.
1. 파티션의 크기를 균등하게 유지하지 못한다. (파티션: 인접한 서버 사이의 해시 공간)
2. 키의 균등 분포를 달성하기 어렵다.
이 두 가지 문제를 보완하기 위한 기법이 가상 노드 또는 복제라 불리는 기법이다.

가상 노드

작동 원리

• 각 서버를 해시 링에 여러 번 등록한다.

Server A → hash("A#1"), hash("A#2"), hash("A#3") …
Server B → hash("B#1"), hash("B#2"), hash("B#3") …

• 키를 매핑할 때는 링 전체를 보고 가장 가까운 노드를 찾는다.
• 이렇게 하면 부하가 자연스럽게 분산된다.
• 보통 서버당 수백 개의 vnode를 두면 충분히 균등한 분포가 나온다고한다.

번외

해시 키를 사용하는 대표적인 상황들

1. 분산 캐시 (예: Redis, Memcached)

서비스에 캐시 서버가 여러 대 있을 때, 어떤 서버에 데이터를 저장할지 결정해야 함.

cache_server = hash("user:1234") % 4  # 총 4개의 Redis 노드

설명:

• "user:1234"가 해시 키
• 이 키를 해시해서 특정 Redis 노드에 매핑
• 나중에 같은 키로 조회하면 동일한 노드로 가서 데이터를 찾을 수 있음

정리: 캐시 일관성을 유지하고, 노드 간 데이터를 균등하게 분배하기 위해 해시 키 사용.

2. 데이터베이스 샤딩 (Sharding)

데이터베이스가 너무 커서 여러 DB 인스턴스로 나누고 싶을 때.

int shard = hash(userId) % 8; // 8개의 샤드(DB)

설명:

• userId가 샤드 키(Shard Key)
• 샤드키를 해시해서 실제 해시 키로 바꿔 어떤 샤드(DB)에 저장할지 결정.
• 해시를 쓰면 userId가 순차적이어도 데이터가 균등하게 분산됨.

정리: 해시 키는 “데이터가 저장될 샤드(서버)를 결정”하는 데 사용됨.

로드 밸런싱 (Load Balancing)

API 서버가 여러 대일 때, 같은 사용자 요청은 항상 같은 서버로 보내고 싶을 때.

server_index = hash(user_session_id) % 5
→ 5개의 웹 서버 중 하나 선택

설명:

• user_session_id를 해시 키로 사용.
• 같은 세션의 요청은 항상 같은 서버로 가게 되어, 세션 일관성이 유지.
  정리: 해시 키로 요청을 특정 서버에 고정시켜서 세션 유실을 방지.