［독서기록］ 가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장

📖 제목 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초 : 5장
🙋‍♂️ 저자 : 알렉스 쉬
5장에서는 안정 해시 설계에 대해 다루고 있다. 안정해시란 서버가 추가되거나 제거되더라도, 가능한 한 많은 키가 이동하지 않도록(다시 분산할 필요가 없도록) 도와주는 알고리즘이다. 이 개념을 이해하기 위해 우선 실제 서비스에서 키-값이 어떻게 쓰이는 지 몇 가지 사례를 생각해 본 후 안정 해시 설계에 대해서도 정리해보자.

📌실제 시스템에서 키-값은 어떻게 쓰일까?

1. 세션 저장소

   1 2	key: "session:abc123" value: "{userId: 42, 로그인 시간: 2025-04-14}"

   로그인 한 유저의 정보를 서버가 저장하기 위해 사용하는 세션 저장소에서 키-값이 사용된다.

2. 캐시 서버

   1 2	key: "user:42:cart" value: "[상품1, 상품2, 상품3]"

   데이터베이스 접근을 줄이기 위해, 자주 조회되는 값을 Redis나 Memcached같은 캐시에 저장해서 사용하기도 한다.

3. 프로필 사진, 아바타 URL 등 메타데이터

   1 2	key: "user:42:profile-img" value: "https://cdn.example.com/avatar/42.jpg"

   빠르게 URL을 불러오기 위해 메타 데이터들을 키로 저장해 둘 수도 있다.

👉 왜 하나의 서버에 다 저장하지 않을까?
서버 하나가 너무 커지면 용량이나 성능에 문제가 생길 수도 있고, 이 서버에 문제가 생기면 전체 서비스가 멈추게 된다. 그래서 보통 대규모 서비스에서는 여러 대의 서버에 데이터를 나눠서 저장하는 것이다.
이 때 어떤 데이터를 어떤 서버에 저장할 지 결정하는 게 해시 함수고, 서버 수가 늘거나 줄 때 마다 데이터 재배치 부담을 줄일 수 있도록 도와주는 게 안정 해시 알고리즘 이다.

📌 안정 해시가 필요한 이유를 알아보자

먼저 일반적인 해시 분산의 문제점을 알아야 안정 해시의 필요성을 느낄 수 있다.
N개의 캐시 서버가 있다고 할 때, 이 서버들에 부하를 균등하게 나누기 위해서는 이런 공식의 해시 함수를 사용할 수 있다.

1	int serverIndex = hash(key) % 3; // 서버 개수 3개

그런데 여기에서 서버가 한 대 더 추가되어 4대가 되면?

1	int serverIndex = hash(key) % 4;

계산해보면 대부분의 키들이 다른 서버로 이동하게 된다.
즉, 기존의 해시 분산 방식은 서버 수가 바뀌면 거의 모든 키를 다시 분산해야 한다. 이게 바로 스케일 아웃이 어려운 이유다.

📌안정 해시에 대해 알아보자

안정 해시는 어떤 방법으로 부하를 균등하게 나눠줄까?
안정 해시는 평균적으로 k/n개의 키만 재배치하는 해시 기술이다. K는 키의 개수, N은 슬롯의 개수를 의미한다.

안정 해시는 원형 해시 링으로 이해 할 수 있는데, 우선 일렬의 해시 공간이 있다고 가정해보자. 이 공간을 선이라고 생각하고 양쪽 끝을 구부리면 위 이미지와 같이 원형이 된다.
그런 다음, 키들이 이 링 위의 어딘가에 배치된다. 각 키는 시계 방향으로 가장 가까운 서버에게 할당된다.

이 이미지처럼, 키1은 서버1에 할당되고, 키2는 서버1과 더 가깝지만 시계 방향으로 가장 가까운 서버에게 할당되므로 서버2에 할당된다.

그럼 서버 한대가 추가되거나 삭제될 경우에는 어떻게 동작할까?
서버5가 위 그림처럼 추가되었다면, 키2는 서버2가 아니라 서버5에 할당되도록 변경될 것이고, 다른 키들은 모두 그대로 유지된다.
서버3이 삭제된다면, 키3은 서버1에게로 재할당 되고 다른 키들은 모두 그대로 유지된다.

이 안정 해시의 기본 구현법은 상당히 좋아 보이지만 두 가지 문제가 있다.

1. 서버가 추가/삭제 되는 경우 파티션의 크기를 균등하게 유지하기가 어렵다.
2. 키의 균등 분포를 달성하기 어렵다.

이를 해결하기 위해 제안된 기법이 가상 노드(Virtual Node) 또는 복제(Replica) 기법이다.

📌가상 노드 기법이란?

서버마다 여러 개의 가상 노드를 만들어서 해시 링 위에 흩뿌려두는 기법이다. 이렇게 하면 링 위 여기저기에 서버1-1, 서버1-2, 서버1-3 같은 서버1의 가상 노드들이 할당되고 서버의 부하가 좀 더 균등하게 분산된다.
다만 가상 노드가 많아질수록 가상 노드 데이터를 저장할 공간이 더 많이 필요해지므로, 몇 개의 가상 노드를 사용할 것인지를 잘 고려해야 한다.

📌안정 해시의 이점 정리하기

• 서버가 추가되거나 삭제될 때 재배치 되는 키의 수가 최소화 된다.
• 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장성을 달성하기 쉽다.
• 핫스팟 키 문제를 줄인다. 특정 샤드에 대한 접근이 지나치게 빈번하면 과부하 문제가 생길 수 있다.

📌안정 해시를 사용하는 대표적인 예

• 아마존 다이나모 데이터베이스(DynamoDB)
• Apach Cassandra 클러스터의 데이터 파티셔닝
• Discord
• Akamai CDN
• Meglev 네트워크 부하 분산기