Hash Ring

Hash Ring 이란?

분산 시스템에서 데이터(키)를 여러 서버에 고르게 분산시키기 위한 방법이다.

🍩 원형 구조의 해시 공간 위에
키와 서버를 같은 방식으로 매핑해서
가장 가까운 서버에 데이터를 저장하는 구조

예시로 들어보자

노드 3개에 데이터를 분산 저장하는 상황이 있다. 제일 쉬우면서 분산 저장하는 법은 데이터의 특정 값을 이용해 해싱 결과 값을 구하고, 해당 값의 노드로 배치하는 법이다.

hash(data-key) % 3

이러한 예시에서 노드의 수가 세상이 끝날 때까지 변함이 없다는게 보장된다면 문제 없이 동작할 수 있다. 하지만 역시나 그럴 확률은 적다. 주변 환경에 따라, 유저의 수가 증감함에 따라, 회사/서비스의 상황에 따라 분산저장 노드의 개수는 변할 수 있고, 그렇게 상황에 따라 변하는 것이 효율적이다.

 

노드 수가 변경되면 생기는 문제

예를 들어 노드 수가 3개에서 5개로 바뀌었다고 가정해 보자
그럼 해시 함수도 다음과 같이 바뀐다

기존: hash(data-key) % 3 
변경: hash(data-key) % 5

문제는 여기서 발생한다.

• 변경된 해시 함수로는 기존 데이터를 저장한 노드를 다시 계산해도 찾을 수 없습니다.
• hash(data-key) % 3에서 Node 1로 배정되었던 데이터가, % 5로는 Node 1이 아닐 수 있기 때문입니다.
• 결국, 기존 데이터를 모두 새로운 노드 기준으로 재배치해야 하는 문제가 발생합니다.

이러한 재배치 비용은 데이터가 적고, 노드 변경이 드물다면 감당할 수 있습니다.
하지만 그런 상황은 예외에 가깝고, 대부분의 시스템은 다음과 같은 질문을 피해갈 수 없습니다:

• 데이터가 정말 적을까?
• 노드 변경이 자주 일어나지 않을까?

즉, 단순 해시 기반 분산 저장 방식은 현실적으로 실용성이 떨어지는 구조입니다.

 

이러한 문제를 위해 고안된 것이 Consistent hash이다. 여기서는 hash ring이라는 개념을 사용한다.

 

해시 함수를 통해 데이터를 분산 저장하는 방식

Consistent Hashing은 "해시 링(Hash Ring)"이라는 구조를 사용합니다. 이 구조를 이해하려면 먼저 해시 함수가 어떤 역할을 하는지 간단히 짚고 넘어가야 합니다.

해시 함수는 데이터를 일정한 범위의 값으로 매핑해줍니다.
예를 들어, 해시 함수의 출력 범위를 0부터 1 사이의 실수값이라고 가정해 봅시다.
즉, 어떤 데이터든 hash(data-key)를 계산하면 항상 0.0 이상 1.0 미만의 값이 나오게 됩니다.

Hash ring에서는 저장할 값의 hash 값과 가장 가까운 값을 가지는 Node에 해당 값을 저장하는 알고리즘이다. "가장 가까운 값"은 알고리즘마다 달라질 수 있다. 예를 들어, 정말 절대 값 차이를 의미할 수도 있고, hash 값 이상의 값들 중 제일 가까운 값을 가지는 Node 일수도 있다.

좀 감이 안올 수 있는데, 또 예시를 들어보자. 데이터를 저장할 Node는 hash 값 이사의 값들 중 제일 가까운 값을 가지는 Node라고 하자. 그러면 아래의 사진처럼 해당 범위에 오는 데이터들은 같은 색깔을 가지는 노드에 저장된다는 것을 의미한다.

 

저장할 값(DataA)을 hash 함수로 돌렸을 때, 결과가 0.28이 나왔다. 그러면 아래 그림처럼 Node2 근처에 위치할 수 있을 것이다.

DataA 의 hash 값(0.28)보다 이상인 값을 가지는 Node 중 제일 가까운 Node는 2이므로 DataA 는 Node 2에 저장된다.

이러한 알고리즘대로 이어진다면, 다음 그림처럼 데이터들이 저장될 수 있다.

맨 앞에서 살펴보았던 단순히 hash 값을 통해 분산 저장하는 것과 같이 consistent hash (hash ring)을 통해서도 분산 저장할 수 있게 된다. 그럼, 이 방법이라면 node의 수가 변할 때 전체 재배치를 막을 수 있을까?

어떠한 이유로 Node 3 가 사용불가, Out 되었다고 하자. 그럼 Node2에 저장되어 있는 값들은 어떻게 할까?

 

여기서 hash ring의 효과가 나타나는데, 알고리즘 상 hash 값의 이상 값을 가지는 가장 가까운 Node였으므로, Node 3에 저장되는 범위들은 자동으로 Node 1을 가리키게 된다. 즉, Node가 사라지는 상황에서 그 사라지는 특정 Node에 존재하는 데이터들만 재배치를 하면 된다는 것이다.

 

그럼 반대로 Node가 추가되는 상황을 생각해보자. Node 4(0.8) 이 추가되었다. 그럼 일반 hash를 사용할 때의 문제처럼 모든 데이터들이 재배치되어야할까? 그림을 보면 알 수 있듯, 아니다! 이번에도 마찬가지로 특정 데이터들만 재배치되면 된다. 여기서는 새로 추가되는 Node의 hash값 이하 범위들의 데이터들만 재배치 되면 된다.

 

위에서 살펴보았듯, hash ring을 통해 consistent hash를 구현할 수 있었다. 즉, 기존 hash 값만으로 분산 저장 노드를 계산하던 방식의 문제점을 해결해낼 수 있었다.

 

그럼 이제 생각해보아야 할 것이 hash ring 방식에는 단점, 문제점이 없는가? 이다.

모든 솔루션에는 단점이 있듯, hash ring에도 존재한다.

---

1. 데이터가 균등하게 분산되지 않을 수 있다

Consistent Hashing에서는 데이터가 해시 함수를 통해 무작위 위치에 배치됩니다.
하지만 이 무작위성 때문에 모든 노드에 균등하게 분포된다는 보장이 없습니다.

예시:

• Node 1에는 20,000개의 데이터가 몰리고,
• Node 2에는 1개의 데이터만 저장되는 극단적인 상황도 발생할 수 있습니다.

---

2. 노드 장애 발생 시 특정 노드로 부하가 집중될 수 있다

해시 링에서는 노드가 사라졌을 때, 해당 노드가 맡고 있던 데이터의 범위를 다음 노드가 자동으로 가져가게 됩니다.
하지만 이때도 문제는 발생합니다.

예시:

• Node 3이 사라졌다고 해봅시다.
• 그러면 원래 Node 3의 범위에 속해 있던 모든 데이터는 다음 노드인 Node 1로 넘어가게 됩니다.

즉, 수많은 데이터가 한 번에 Node 1로 몰리게 되고,
그 결과 Node 1은 심각한 부하 증가와 과부하 위험에 노출됩니다.

 

 

이 예시는 데이터가 적어서 그렇지, 노드마다 데이터가 수십만개, 수백만개 저장되어있다고 해보자. 그럼 Node 3의 데이터들은 Node 1에 재배치되면서 Node 1에 엄청난 부하가 일어나게 된다. 이에 따라 Node 1 자체도 위험해질 수 있다는 말이다.

운이 안좋으면 해당 부하로 인해 Node 1도 죽을 수 있다. 그러면 어떻게 되는가? Node 3, Node 1 범위의 데이터들이 재배치되면서 결국 홀로 남은 Node 2로 재배치될 것이다. 그럼 당연히도 Node 2의 부하가 올라가고, Node 2 마저도 죽을 수 있다. 이렇듯 연쇄작용을 통해 모든 Node 들이 죽을 수도 있는 상황이 일어나게 된다.

결국엔 hash ring을 그냥 사용하면 일반 hash 값을 통해 분산저장하는 상황보다 더 큰 문제를 일으킬 수 있는 단점이 있다는 것이다.

그럼 어떻게 이 문제를 해결해야 할까?

이 문제를 해결하기 위해 등장한 개념이 바로 Virtual Node (가상 노드)다.

• 하나의 실제 노드를 해시 링 위에 여러 개의 가상 노드(Virtual Node)로 분산 배치
• 노드 하나가 죽더라도, 해당 노드가 담당하던 여러 범위는 여러 다른 노드에 분산되기 때문에
  부하가 특정 노드에 몰리지 않음

아래 그림에서처럼 각 Node마다 vnode가 6개씩 존재하는 상황이다. 그럼 이 vnode를 무작위로 범위 내에 뿌려놓는다.

 

그리고 앞의 예처럼 데이터를 넣어보자. 기존에는 데이터의 hash 값 이상에 제일 가까운 node에 배치하는 것이었다면, 이번엔 hash 값 이상에 제일 가까운 vnode의 node에 배치하게 된다.

 

이렇게 되면 더 다양하고, 비정형화된 규칙으로 hash ring이 구성되게 된다. 이전처럼 Node가 사라질 때 부하가 커지는 지 확인해보자.

Node 3이 사라졌다고 가정해보자

이제 Node 3이 사라지게 되면 어떤 일이 벌어질까요?

기존 방식에서는 Node 3이 담당하던 0.6~1.0 범위 전체가 한꺼번에 Node 1로 몰렸습니다.
하지만 이제는 Node 3가 가지고 있던 여러 vnode의 위치마다 각기 다른 노드로 재배치됩니다.

당연하지만 vnode의 배치가 랜덤하게 될수록 부하가 몰리는 현상이 줄어들 수 있다. 랜덤하게 배치되었다면 데이터가 더 많아지고, vnode가 더 많아짐에 따라 거의 균등하게 재배치 되는 것을 확인할 수 있을 것이다.