[알고리즘] 일관된 해싱(Consistent Hasing), 그리고 분산 환경에서 메시지 라우팅을 위한 구조 고민

우리는 클러스터링 된 WebSocket 서버 환경에서 실시간 메시징 기능을 제공하고 있다. 클라이언트 수가 증가함에 따라 WebSocket 서버의 수평 확장이 자연스럽게 필요해졌고, 이에 따라 다음과 같은 메시지 라우팅 문제를 고민하게 되었다.

예를 들어,

• 사용자 A는 서버 1에 접속하고,
• 사용자 B는 서버 3에 접속해 있다고 하자.

이때 A가 B에게 메시지를 보내려면 B가 연결된 서버를 알아야 한다.
즉, 클러스터 환경에서는 "어느 서버에 누구(userId)가 붙어 있는지"에 대한 라우팅 정보 관리가 핵심이다.

이 문제를 해결하기 위한 대표적인 방법은 다음과 같다:

• Redis 등에 라우팅 테이블을 유지
• Gateway 서버에서 중앙 집중형 라우팅 처리
• Consistent Hashing 기반 라우팅

우리는 가능한 한 모든 영역에서 상태를 갖지 않으면서도 메시지가 정확히 라우팅 되기를 원했기에, Consistent Hashing 개념에 주목하게 되었다.

 

1. 기존 해싱 방식의 구조적 한계

전통적으로 분산 시스템에서는 아래와 같은 방식으로 노드를 분배한다:

hash(userId) % N   // N은 서버 수

 

예를 들어,
hash("user1234") % 3 = 1 → 1번 서버

하지만 서버 수가 변경되면 대부분의 키 매핑이 바뀌게 된다.
예: hash("user1234") % 4 = 3 → 3번 서버

이 방식의 문제점은 다음과 같다:

• 서버가 추가/제거되면 대부분의 클라이언트가 다른 서버로 매핑됨
• 캐시라면 캐시 미스 발생 → 성능 저하
• WebSocket이라면 사용자 연결 예측 실패 → 메시지 유실 가능

 

2. Consistent Hashing의 기본 개념

Consistent Hashing은 위 문제를 해결하기 위한 구조적 해법이다.

• 전체 해시 공간을 원형(링 구조)으로 가정한다 (예: 0 ~ 2³²)
• 서버와 키(예: userId) 모두 해시하여 이 원 위에 위치시킨다
• 각 키는 시계 방향으로 가장 가까운 서버에 할당된다

예를 들어:

요소 해시 각도 역할

https://en.wikipedia.org/wiki/Consistent_hashing

Server A	74°	서버 노드
Server B	139°	서버 노드
Server C	310°	서버 노드
BLOB	111°	Server B로 매핑됨

2.1. 서버 추가 시 변화

서버 D가 200°에 추가된다면?

• 기존 B~C 사이 키 중 일부만 D로 이동
• 나머지 매핑은 그대로 유지
• 즉, 서버가 추가되더라도 데이터 이동량이 최소화됨

이러한 특징은 확장성과 안정성 측면에서 매우 유리하다.

 

3. 실무 적용에 대한 현실적 고민

Consistent Hashing을 기반으로 메시지를 라우팅 하면,
동일한 사용자에게 가는 메시지는 항상 동일한 WebSocket 서버로 전송될 수 있다.

그러나 한 가지 중요한 전제가 필요하다:

"사용자가 항상 자신에게 할당된 서버에 접속해 있어야 한다."

즉, 클라이언트 접속 시에도 hash(userId)를 기준으로 "정해진 서버"로 유도되어야 한다. 이를 흔히 Sticky Routing 또는 Pre-Routing이라고 하며, L4/L7 로드 밸런서에서 일부 지원하긴 하지만 제약이 많다.

현실적으로는 사용자 접속이 랜덤 하게 이루어지는 경우가 많기 때문에,
Consistent Hashing만으로는 사용자 위치를 정확히 예측하기 어렵다.

 

4. 우리의 선택은?

이러한 현실적인 제약을 고려해, 우리는 다음과 같은 구조로 설계를 진행하고 있다:

• 클라이언트 접속 시 WebSocket 서버는 사용자 ID를 Redis에 등록
• A → B 메시지를 보낼 때 Redis에서 B의 현재 서버를 조회
• 메시지를 해당 서버로 Pub/Sub 또는 직접 전달

이 방식은 상태를 최소화하면서도 정확한 라우팅을 가능하게 한다.
추가적으로 Redis 자체를 클러스터링 하거나 TTL을 두어 장애 대응도 병행할 수 있다.

 

---

 

Consistent Hashing은 노드 변경 시에도 대부분의 매핑을 유지할 수 있는 매우 효율적인 알고리즘이다.
그러나 실무에서는 클라이언트 접속 방식, 네트워크 구조, 로드 밸런서의 특성 등 다양한 현실적인 제약을 함께 고려해야 한다.

• 사용자가 항상 정해진 서버로 접속할 수 있다면, Consistent Hashing은 강력한 해법이다.
• 그렇지 않다면, Redis 기반의 동적 라우팅 + Pub/Sub 구조가 더 유연하고 실용적이다.

아키텍처 설계에서 중요한 것은 특정 기술을 적용하는 것 자체가 아니라,
현재 시스템의 특성과 제약 조건에 맞는 적절한 방법을 선택하는 것이다.

Consistent Hashing은 그 자체로 멋있는 개념이지만,
우리의 서비스 환경에서는 Redis 기반 라우팅이 더 현실적이고 안정적인 해법이었다.

궁극적으로 기술은 "이론"보다 "현실"에서의 타협을 하는 것이 중요한 것 같다.

 

참고

https://en.wikipedia.org/wiki/Consistent_hashing

https://ko.wikipedia.org/wiki/%EC%9D%BC%EA%B4%80%EB%90%9C_%ED%95%B4%EC%8B%B1