[끄적끄적] 효율적인 키 분배 및 리밸런싱 방식

최근 진행중인 프로젝트는 내부적으로 redis-stream을 사용하고 있는데요, redis-stream은 key하나에 스트림 하나가 들어가므로 stream을 하나만 사용하면 redis cluster를 사용할 수 없습니다. 따라서, 클라이언트에서 로드밸런싱을 구현해줘야 하는데요, 노드 하나당 레디스 하나가 매핑된다고 가정하면, 레디스 클러스터 노드가 추가되거나 삭제될때 각 요청을 어느 노드로 보낼지 식별해서 로드밸런싱을 해줘야 합니다.
생각이 여기까지 오니까 "키 재분배 방식을 어떻게 하면 효율적으로 할 수 있을까?" 에 대해서 궁금해졌고 공부한 내용을 정리하고자 글을 작성하기로 했습니다.

---

모듈러 연산

키 재분배를 위해서 사용할 수 있는 가장 쉬운 방법은 모듈러 연산 방식 입니다.
5개의 노드가 있고 키가 백만개가 있다면, 각 키를 모듈러 연산을 통해 나머지를 구하고 나머지 값에 따라 1~5번 노드로 키를 분배 하는 방식입니다.
 
이 방식은 직관적이고 빠르지만, 새로운 노드가 추가되거나 다운될때 리밸런싱이 과하게 발생할 수 있다는 단점이 있습니다.
예를들어, 아래와 같이 5개의 노드가 존재하고 25개의 키를 5로 모듈러 연산해서 고르게 분배했다고 가정해보겠습니다.
 

• 노드 1: 5, 10, 15, 20, 25
• 노드 2: 1, 6, 11, 16, 21
• 노드 3: 2, 7, 12, 17, 22
• 노드 4: 3, 8, 13, 18, 23
• 노드 5: 4, 9, 14, 19, 24

이때 만약, 노드 6이 추가되면 어떻게 될 까요? 
 

• 노드 1: 6, 12, 18, 24
• 노드 2: 1, 7, 13, 19, 25
• 노드 3: 2, 8, 14, 20
• 노드 4: 3, 9, 15, 21
• 노드 5: 4, 10, 16, 22
• 노드 6: 5, 11, 17, 23

25개의 키중 21개의 키가 재분배 된것을 볼 수 있습니다. 만약, 키가 굉장히 많다면 사용하기 적절한 방식은 아닐것 입니다.
 
그러나, 모듈러 연산으로도 키 재분배를 줄이면서 노드를 추가하거나 삭제하는 방법이 있는데요, 바로 항상 2배수만큼 만큼 노드의 수를 증가시키는 것 입니다. 이렇게 하면 항상 50%만큼의 키가 재분배 됩니다. (모듈러 연산을 할 값이 2배씩 증가하므로 당연히 절반은 원래대로 절반은 리밸런싱 대상이 됩니다.)
하지만 이 방식은 노드가 2배씩 늘어나므로 지속 가능한 방식은 아니에요.
 
이것 외에도, 각 키가 어디로 가야되는지 감시하는 노드를 추가적으로 운용하면서 리밸런싱을 최소화 하는 방식이 있습니다.

콘시스턴트 해싱

감시하는 노드를 추가적으로 운용하는 방법, 2의 배수만큼 노드를 증가시키는 방법등 모듈러 연산을 사용했을때 리밸런싱을 줄이는 방법을 알아 봤지만, 노드 수가 기하급수적으로 늘어난다는 단점과 추가적인 노드 운용이 필요하다는 단점이 있었습니다.
 
콘시스턴트 해싱 기법을 사용하면 이런 단점을 회피할 수 있는데요,
콘시스턴트 해싱을 사용하면, 해싱된 값을 자신과 가장 가까운 오른쪽 노드(방향은 크게 중요하지 않습니다. 왼쪽으로 구현해도 되요)에 적재하게 됩니다.
 
예를들어, 아래 사진에서 1번 왼쪽 3번 오른쪽에 있는 화살표는 1번 노드에 적재 되고, 1~2번 사이에 있는 화살표는 2번 노드, 2~3번 노드에 있는 화살표는 3번노드에 적재됩니다.

콘시스턴트 해싱

 
 
이때, 만약 3번 노드가 다운되면 2~3 사이에 있는 화살표만 1번으로 리밸런싱 해주면 되기 때문에 모든 키들에 대해서 리밸런싱 하지 않아도 된다는 장점이 있습니다. 
 
하지만, 이 방식은 모듈러 연산과 같이 키가 고르게 분배되지 않는다는 단점, 키가 재분배 되면서 특정 노드에 값이 몰리게 되고 연쇄적으로 다운되는 문제가 발생할 수 있습니다.
 
콘시스턴트 해싱에서는 이러한 문제를 해결하기 위해 가상노드라는 개념을 사용하는데요,
가상 노드를 사용하면, 위 와 같은 링에서 실제 노드로 연결되는 가상의 노드를 생성하고 자신과 가장 가까운 시계방향 노드에 적재를 하는 방식입니다.
 
예를들어, 노드의 갯수가 3개일때, 아래 그림과 같이 각 노드로 연결되는 가상의 노드를 Ring 위에 흩뿌려 둡니다.

consistent hasing - vnode

 
이렇게 설계하면 특정 노드가 다운되거나 생겼을때, 키가 다시 재분배 된다는 장점이 있습니다.