티스토리 뷰

Development

Consistent hashing (Hash ring)

KimDoubleB 2022. 1. 6. 22:17
반응형

Consistent hashing은 Hashing을 일관되게 유지하는 방법이다.

이게 뭐다 라고 설명하기 보단, 먼저 상황을 예시로 들어보자.

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

수식으로 나타낸다면 hash(data-key) % 3 으로 데이터가 저장되는 노드 번호를 구할 수 있을 것이다.

 

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

 

그럼 노드의 수가 5개로 변했다고 하자. 그럼 노드 번호를 구하는 수식은 hash(data-key) % 5 로 변하게 된다. 수식이 변한 이후로 들어오는 데이터들은 저장되고, 저장된 값을 찾아가는데 문제는 없을 건데, 문제는 기존에 저장된 데이터들은 어떻게 되는가? 이다.

 

기존에 Node 1에 저장되었던 데이터를 찾아야 한다. 노드의 수가 바뀐 지금 hash(data-key) % 5 을 통해서 노드 번호인 1이 나올지는 보장되지 않는다. 즉, 기존의 데이터가 들어간 위치를 찾을 수 없게 된다. 그러므로 기존에 저장되어있던 모든 데이터들은 새로운 수식을 통한 노드 재배치를 수행하여야 한다.

 

이러한 작업이 엄청 적은 데이터이고, 잦지 않다면 뭐... 감당할 수도 있다고 생각한다. 근데 이걸 어떻게 아는가? 데이터가 적을지, 잦지 않을지... 노드의 수란 유동적인 것인데 말이다. 이러한 문제로 단순한 hashing을 이용해 분산 저장하는 방법은 실용적이지 않다.

 

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

hash 함수를 통해 유한한 값의 범위로 결과가 나온다고 하자. 예를 들어 0~1 말이다. 그러면, 이 유한한 범위를 노드의 수로 나눠보자. 간단하게 하자면 Node1 (0), Node2 (0.3), Node3 (0.6)로 나눌 수 있을 것이다.

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. 데이터를 균등하게 저장하지 못한다.

  • Hash 값 특성상 데이터의 결과값이 랜덤하게 나온다. 뭐, 이건 이전의 hash만 사용했을 때도 발생할 수 있는 문제점이기도 하다. 아무튼, 그렇기에 데이터가 완전히 노드마다 균등하게 저장되지 못한다.
  • 정말 운이 안좋게도 불균등이 크다면 Node 1에는 20000개의 데이터가, Node 2에는 1개의 데이터가 저장될 수도 있다. 하지만 보통 데이터가 엄청나게 많아지면 어느정도 균등하게 저장된다 (뇌피셜).
  •  

2. Node가 죽는/없어지는 상황에서 특정 Node에 모든 데이터가 쏠려 부하가 올라갈 수 있다.

  • 말그대로 특정 Node가 죽는/없어지는 상황이 오면 해당 Node의 범위에 들어가있던 데이터들은 재배치를 하게 된다. 그 재배치를 통해 새로운 Node를 구하게 되는데 단순한 hash ring에서는 그 범위의 데이터들은 모두 같은 Node를 향해 재배치되게 된다.
  • 앞선 예시를 들어보자. Node 3 이 사라짐에 따라 Node 3 에 저장되던 범위의 데이터들은 재배치되게 된다. 당연히도 해당 범위의 데이터들은 모두 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 값을 통해 분산저장하는 상황보다 더 큰 문제를 일으킬 수 있는 단점이 있다는 것이다. 그럼 이 문제를 해결해야하는데, 어떻게 해야할까?

 

그래서 hash ring에서는 위 같이 Node 수 변화에 따른 부하 증가를 막기 위해 vnode(virtual node)를 사용한다.

  • vnode라고 해서 엄청 거창한 것은 아니다. 그냥 Node들을 나타내는 가상의 Node를 의미하는 것이다. 이렇게 말하니 더 이해하기 어려운 것 같다.... 바로 예제로 들어보자.
  • 아래 그림에서처럼 각 Node마다 vnode가 6개씩 존재하는 상황이다. 그럼 이 vnode를 무작위로 범위 내에 뿌려놓는다.

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

 

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

  • Node 3 이 사라진다고 해보자. vnode를 사용하지 않았더라면 Node 1 에 모든 부하가 쏠렸을 것이다. 하지만 vnode를 사용하게 됨으로써 DataC 는 Node 2 로, DataD 는 Node 1 로 재배치되게 된다. 즉, 기존과 달리 더 다양하고 부하가 몰리지 않게 끔 재배치 되게 된다.
  • 당연하지만 vnode의 배치가 랜덤하게 될수록 부하가 몰리는 현상이 줄어들 수 있다. 랜덤하게 배치되었다면 데이터가 더 많아지고, vnode가 더 많아짐에 따라 거의 균등하게 재배치 되는 것을 확인할 수 있을 것이다.

 

 

여기까지가 Consistent hashing (hash ring)에 대한 설명이었다.

  • 위키에서는 언어별 구현체를 설명하고 있다.
  • Java의 경우, 인접한 Node를 계산할 수 있는 TreeMap 컬렉션을 사용해 구현할 수 있다. TreeMap 에서는 higher, lower 종류의 메서드를 지원하고 있다.
  • 하지만 TreeMap 의 경우, thread-safe 하지 않기 때문에 production 코드에서 사용할 떄는 조심해야만 한다. 만약 thread-safe 함을 보장해야 한다면 ConcurrentSkipListMap 를 사용하는 것을 고려해야 한다.
320x100
반응형
댓글
반응형
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함