어째서 레디스에서 분산 해시에 %N을 쓸까?

분산 해시를 공부하면서 %N부터 가상 노드까지 차례로 다뤘습니다. 이렇게 순서대로 늘어놓으면, 마치 %N은 초보적인 출발점이고 가상 노드는 그 위의 고도화된 기법처럼 보이기 쉽습니다. 하지만 실제로는 그렇지 않습니다. 상황에 따라 %N을 일부러 선택하는 경우도 적지 않습니다. 이번에 다룰 레디스(Redis)가 바로 그런 사례입니다. 레디스는 어째서 해시 링이나 가상 노드를 두고 %N을 골랐을까요? 그리고 %N의 치명적인 약점인 재배치 문제는 또 어떻게 피해 갔을까요?

레디스가 %N으로 해시 분산을 할 수 있는 이유

해시값 % N으로 데이터를 분산하면, 가장 치명적인 약점은 바로 재배치 문제였습니다. 이 문제를 풀기 위해 우리는 자연스럽게 해시 링(안정 해시)이라는 아이디어를 떠올릴 수 있습니다. 하지만 레디스는 해시 링을 택하지 않았습니다. 그렇다면 레디스는 어떤 선택을 했을까요?
바로 해시값의 범위를 직접 정해 두는 방법입니다. 그렇다면 이 방법이 정말 재배치 문제에 효과적일까요? 작은 예로 따라가 보겠습니다.
설명을 위해, 값의 범위를 0부터 99까지, 즉 100칸으로 고정했다고 가정해 보겠습니다. 그러면 모든 키는 이 100칸 중 하나로 떨어집니다.

이제 어떤 데이터가 들어와도 결과값은 0~99 사이에서 정해집니다. 이 결과값을 슬롯(slot)이라고 부릅니다.
기존 %N 방식에서는 이 결과값이 곧 서버 번호였습니다. 하지만 고정 N 방식에서는 서버 개수와 무관하게 결과값이 늘 0~99일 뿐입니다.
즉, 이 번호만으로는 데이터가 어느 서버로 가야 하는지 알 수 없습니다. 새로운 문제가 생긴 것입니다.

이 문제를 해결하기 위해, 각 서버가 담당할 슬롯 범위를 지정합니다. 예를 들어 서버 1은 0~30번, 서버 2는 31~60번, 서버 3은 61~99번을 맡는 식입니다. 이렇게 "어느 슬롯을 어느 서버가 맡는지" 정리한 것이 바로 표(table)입니다.

그렇다면 레디스는 슬롯을 몇 개나 두었을까요? 바로 16384입니다. 네, 정확히 16384입니다. 왜 하필 16384일까요?

레디스 슬롯의 범위가 16384인 이유

여기에는 2가지 이유가 있습니다.

첫 번째 이유

첫 번째 이유는 16384가 2의 거듭제곱(2¹⁴)이기 때문입니다. 갑자기 거듭제곱이 나와 의아할 수 있습니다. 이유는 이렇습니다. 컴퓨터는 모든 수를 0과 1, 즉 2진수로 다룹니다. 그리고 나누는 수가 2의 거듭제곱이면, %(나머지) 연산을 훨씬 쉽고 빠르게 할 수 있습니다. 
2¹⁴은 너무 큰 수이기 때문에 이번에도 작은 수로 계산해보겠습니다. 바로 2³으로 진행하겠습니다.  그렇다면 어떤 데이터의 해시값이 45라고 해봅시다. 이 45를 2³(=8)으로 나누면 나머지는 몇일까요? 
45를 2진수로 표현하면 101101이 됩니다.

2³으로 나눴으니 뒤에서부터 3비트씩 끊어 봅니다. 앞 3비트(101)는 몫, 뒤 3비트(101)는 나머지입니다.
실제로 10진수로 계산해도 결과는 같습니다.레디스가 빠른 나머지 계산을 위해 2의 거듭제곱을 택한 것은 이해했습니다. 하지만 그 많은 거듭제곱 중에서 왜 하필 2¹⁴(16384)였을까요?

두 번째 이유

두 번째 이유는 이 크기가 2KB밖에 되지 않기 때문입니다. 그렇다면 무엇이 2KB일까요?
레디스 서버들은 서로 끊임없이 통신해야 합니다. 이때 각 서버가 "내가 어떤 슬롯을 맡고 있는지"를 슬롯마다 0과 1로 표시해 주고받는데, 이 0과 1의 목록을 비트맵이라고 부릅니다.
이번에도 작은 단위로 비트맵을 이해해봅시다. 설명을 위해 고정 N을 2³, 즉 8이라고 해봅시다. 서버 1이 1번 슬롯만 맡는다면, 다음과 같이 그릴 수 있습니다.

슬롯 하나는 1비트로 표시됩니다. 슬롯이 8개이니 8비트, 즉 1바이트입니다.
여기서 중요한 사실이 하나 있습니다. 데이터를 올바른 서버로 보내려면, 각 서버는 자기 것뿐 아니라 다른 서버들의 비트맵까지 알고 있어야 합니다. 즉, 서버끼리 비트맵을 서로 공유해야 한다는 뜻입니다.
그 이유는 레디스에 전체를 관리하는 중앙 서버가 없기 때문입니다. 관리자가 없으니, 각 서버가 스스로 전체 지도를 알아야 하고, 그러려면 서로에게 직접 알려주는 수밖에 없습니다.
다시 현실로 돌아오면, 레디스의 진짜 고정 N은 16384개입니다. 슬롯 하나당 1비트이니 16384비트이고, 이를 바이트로 바꾸면 16384 ÷ 8 = 2048바이트, 즉 정확히 2KB입니다. 
사실 여기까지 와도 "그래서 왜 하필 2KB냐"는 의문이 남을 수 있습니다. 레디스를 만든 antirez의 설명은 이렇습니다. 서버들이 이 비트맵을 수시로 주고받아야 하기 때문에, 2KB 정도면 충분히 가볍습니다. 만약 슬롯을 2¹⁶(65536)으로 늘렸다면 이 비트맵은 8KB가 되어, 자주 오가기엔 너무 무거워집니다.
그런데 한 가지 이상한 점이 있습니다. 어째서 2¹⁵(32768)이 아니라 2¹⁶(65536)과 비교했을까요? 이는 레디스가 쓰는 해시 함수 CRC16 때문입니다. CRC16은 16비트, 즉 2¹⁶(65536)가지 값을 만들어냅니다. 그래서 슬롯이 가질 수 있는 최대 범위가 65536이기 때문에 이 값을 비교 대상으로 삼은 것으로 추측하였습니다.

그래서 뭘 해시를 하는데?

지금까지 레디스가 어떻게 데이터를 나누는지 설명했습니다. 그런데 짚고 넘어갈 게 있습니다. 지금까지 "서버"라고 불렀지만, 사실 그것들은 인스턴스입니다.
레디스는 싱글 스레드로 동작합니다. 인스턴스 하나가 CPU 코어를 하나만 쓴다는 뜻이죠. 그런데 물리 서버에는 코어가 여러 개 있습니다. 그래서 코어를 놀리지 않으려면, 한 대의 머신에 레디스 인스턴스를 여러 개 띄웁니다.
그렇다면 지금까지 말한 "서버"는 무엇이었을까요? 바로 이 인스턴스들, 각각 독립적으로 동작하는 레디스 프로세스입니다. 물리 서버가 아니라 인스턴스 단위로 슬롯이 나뉘는 것이죠.
이 인스턴스들은 역할이 나뉩니다. 원본 데이터를 맡는 마스터와, 그 마스터를 그대로 복사해 두는 복제본(replica)입니다. 그리고 이렇게 인스턴스를 묶은 집합을 클러스터라고 부릅니다.
즉, 레디스는 키를 해시해 슬롯을 정하고, 그 슬롯을 각 마스터 인스턴스에 나눠 배정합니다.

마무리

지금까지 레디스가 데이터를 분산하는 방법을 살펴보았습니다. 레디스는 해시 링 대신 고정 N을 사용해 재배치 문제를 해결했습니다.
레디스가 해시 링이 아닌 %N을 택한 이유는 빠르고 가볍기 때문입니다. 해시 링은 어떤 서버가 어디에 올라가 있는지를 알아야 위치를 찾을 수 있지만, 슬롯 방식은 “누가 어느 슬롯을 맡았는지”를 2KB 비트맵 하나로 통째로 주고받을 수 있습니다. 어떻게 보면 해시 링이 더 정교한 기술처럼 보일 수도 있습니다. 하지만 레디스의 사례는 해시 링이 언제나 정답은 아니라는 것을 보여줍니다. 더욱이 %N을 쓰는 기술은 생각보다 많습니다. 예를 들어 카프카도 데이터를 분산할 때 %N을 사용합니다. %N뿐 아니라 해시 링과 가상 노드가 실제로 어떤 기술에 어떻게 쓰이는지 녹여보는 것도 재미있을 것 같네요.