일관된 해싱, 해시 링, 해시 슬롯

요즘 개발자를 위한 시스템 설계수업 - 길벗

 

 

지난 글에서 Memcached 아키텍처를 설명할 때 일관된 해싱을 언급했습니다.

일관된 해싱 알고리즘(Consistent Hashing) 을 사용하여 키를 특정 서버에 매핑합니다.

 

일관된해싱은 분산 시스템에서 데이터를 여러노드에 효율적으로 분배하면서 노드를 추가, 삭제할때

데이터의 위치를 다른 곳으로 옮겨야하는 과정이 최소화되도록하는 방식입니다.

 

 

 

 

기존방식(단순 해싱)의 문제점

노드가 3대 있다고 가정하겠습니다.

100개의 파드를 3개의 노드에 골고루 분배하기 위해 규칙을 설정합니다.

 

규칙: 파드 번호를 3으로 나눠서 남는 숫자에 해당하는 노드에 넣습니다. (예: 4%3=1 나머지가 1이므로 1번 노드에 배포)

# %는 모듈러 연산
데이터 번호 % 서버의 개수(N)

 

해당 규칙은 3개의 노드일 경우 잘 동작하지만, 노드를 1개 더 추가하여 4개가 된다면 문제가 발생합니다.

기존 3개의 노드에서 4개가 되었으므로 100개 파드 중 75개 파드를 꺼내 새로운 번호표에 맞춰 이동해주어야합니다.

따라서 분산시스템에서 노드 추가시 데이터 이동이 필요하고 해당 동작은 시스템에 부담이 될 수 있습니다.

 

 

어떤 시스템이 문제가 발생할 수 있을까요?

 

세션

로그인 세션 서버에 로드밸런싱을 했다면,

로그인 세션 서버 한대가 죽는다면, 인덱스 값이 변경되고 일부 요청은 기존과 다른 서버로 요청이 전달됩니다.

새 서버에는 세션 데이터가 없으므로 수많은 유저가 동시에 로그아웃되는 사출 현상이 발생합니다.

 

캐시

캐시 서버 하나가 죽으면, 인덱스 값이 변경되어 일부 요청은 다른 서버로 전달됩니다.

새롭게 도달한 캐시서버는 기존 캐싱 데이터가 없으므로, 데이터를 다시 로딩하게 됩니다.

모든 트래픽이 백엔드 DB로 고스란히 쏟아지며 데이터베이스가 다운되는 연쇄 장애로 이어질 수 있습니다.

 

 

 

 

해결책: 해시 링(Hash Ring)을 통한 일관된 해싱

각 데이터에서 시계 방향으로 가장 처음 도달하는 노드가 이 데이터와 연결될 노드입니다.

 

 

해당 문제해결을 위해 파드와 노드를 하나의 둥근 원(Ring) 모양에 트랙 위에 무작위 배포하는 아이디어가 나옵니다.

 

새로운 규칙:

데이터와 서버 모두 해시 함수를 거쳐 원 위 특정 위치에 점을 찍습니다.

각 파드(데이터)는 트랙을 따라 시계 방향으로 돌다가 가장 먼저 만나는 노드(서버)에 들어갑니다.

 

이를 통해 트랙 중간에 노드를 추가하면 링위에 새 노드 뒤에 있던 일부 파드만 이동하면 됩니다.

트랙 멀리떨어진 나머지 파드들은 그대로 둬도 큰 문제가 없습니다.

 

 

 

이 기법은 시스템에 노드를 추가 또는 제거할 때

전체 데이터를 다시 매핑하지 않고 일부 데이터만 이동하여 영향을 최소화하는 것이 목표입니다.

따라서 일관된 해싱은 콘텐츠 전송 네트워크(CDN), 분산 데이터베이스 등과 같은 노드의 추가, 제거가 빈번한 대규모 시스템에서 특히 유용합니다.

 

링 위에서 시계 방향으로 다음 노드를 빠르게 찾기 위해 파이썬에서는 bisect 모듈을 통한 이진 탐색(O(log N))을 주로 활용

 

https://bytebytego.com/guides/consistent-hashing/

System Design · Coding · Behavioral · Machine Learning Interviews

 

 

 

 

일관된 해싱의 단점: 도미노 현상과 가상 노드(vnode)

일관된 해싱의 단점 : 도미노 현상

기존 해시링에서 서버가 A,B,C 가 있을때 A 서버가 죽어버린다면 

모든 트래픽과 데이터가 B 서버로 전달됩니다.

이를 통해 B가 장애가 발생한다면 C에게 가고 모든 시스템이 연쇄적으로 다운되는 도미노 현상이 발생합니다.

 

 

 

가상노드 (vnode)

해당 현상을 막기 위한 기법으로 가상노드 (vnode)가 있습니다.

실제 노드(서버)는 3대 이지만 링 위에 수십개의 서버가 있는 것처럼 가상노드를 놔둡니다 (A1,A2,A3,B1,B2...)

 

A 서버가 다운되면 어떻게 될까요?

A의 분신들 (A1,A2,A3)가 죽으면서 A1 -> B1, A2 -> C1 등으로 데이터가 이동합니다.

이를 통해 죽은 서버의 데이터가 B가 아닌 남은 서버들에 골고루 분산됩니다.

 

https://docs.datastax.com/en/dse/6.9/architecture/database-architecture/virtual-nodes.html

 

vnode 개수가 많아질수록 수학적으로 완벽한 1/N 균등 분배에 가까워지지만,
그만큼 해시 링 자료구조가 비대해져 메모리 연산 비용과 노드 간 상태 동기화 오버헤드가 커집니다.

과거 Apache Cassandra는 기본값으로 256개를 썼으나,
최신 버전에서는 동기화 부하 최적화를 위해 16개 또는 128개를 권장값으로 하향 조정하는 추세입니다.

 

 

 

 

Memcached vs Redis

Memcached

Memcached 서버는 다른 노드가 몇개인지, 링이 어떻게 생긴지 모릅니다. 자신에게 들어온 데이터만 저장합니다.

이전 글에서 언급했듯이 일관된 해싱을 처리하는 주체는 클라이언트입니다.

이를 통해 서버는 메모리 작업에만 집중할 수 있습니다.

 

 

 

Redis Cluster

Redis 클러스터는 일관된 해싱이 사용하지 않습니다. 해시 링이 아닌 해시 슬롯을 사용합니다.

 

• 고정된 16,384개의 방: 레디스 클러스터는 전체 데이터 공간을 딱 16,384개의 쪼개진 슬롯(Slot)으로 고정해 둡니다.
• 규칙: 데이터를 저장할 때 무조건 CRC16(Key) % 16384 연산을 합니다. 나오는 결과값(0~16383 사이의 숫자)이 해당 데이터가 들어갈 '방 번호'가 됩니다.
• 노드별 슬롯 할당: 서버(물리 노드)가 3대(A, B, C) 있다면 이 16,384개의 슬롯을 나누어 가집니다.
  • 노드 A: 0 ~ 5,500번 슬롯 담당
  • 노드 B: 5,501 ~ 11,000번 슬롯 담당
  • 노드 C: 11,001 ~ 16,383번 슬롯 담당

 

노드가 추가, 삭제된다면

해시 링처럼 데이터가 시계 방향으로 자연스럽게 흘러가는 게 아니라,

슬롯 자체를 다른 노드로 강제 이사(마이그레이션/리샤딩) 시킵니다. (슬롯단위이동)

 

예를 들어 Node D가 추가되면,

기존 A, B, C 노드가 가진 슬롯 중 일부(예: 각각 1,000개씩)를 떼어다가 Node D로 옮깁니다.

이때 슬롯 안에 들어있던 데이터들도 함께 이동합니다.

 

 

 

 

 

 

구조의 이유

왜 레디스는 해시 링을 버리고 슬롯을 선택했을까요?

바로 데이터의 영속성(Persistence)과 정합성 때문입니다.

 

 

Memcached는 날아가도 상관없는 휘발성 데이터입니다.

노드가 죽어 해시 링 규칙에 따라 트래픽이 옆 노드로 스파이크되거나, 캐시 미스가 발생해도

백엔드 DB만 버틴다면 시스템에 치명적이지 않습니다.

 

Redis는 단순 캐시를 넘어 데이터베이스, 분산 락, 대기 열 큐 등 유실되면 안되는 핵심 데이터를 다룹니다.

해시 링 구조를 사용한다면 시스템 정합성이 깨질 수 있습니다.

따라서, Redis는 부하가 걸리거나 노드가 변경되어도 16384개의 슬롯 매핑 테이블을 클러스터 노드끼리 명확히 제어합니다.

 

 

 

 

 

 

 

 

참조글

https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/#performance

Redis cluster specification

 

https://binux.tistory.com/119

Consistent hashing (Hash ring)

https://bytebytego.com/guides/consistent-hashing/

System Design · Coding · Behavioral · Machine Learning Interviews

https://docs.datastax.com/en/dse/6.9/architecture/database-architecture/virtual-nodes.html

Virtual nodes | DataStax Enterprise | DataStax Docs

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