안정 해시(intro.)

패스워드는 어째서 암호화를 사용하지 않고 해시를 사용하는 걸까?

생각보다 많은 곳에서 해시를 사용합니다. 그중 하나가 패스워드이고, 이는 위 포스트에서 확인할 수 있습니다. 해시의 핵심 성질은 크게 두 가지입니다. 하나는 데이터의 지문을 만드는 것이고(패스워드가 여기에 해당합니다), 다른 하나는 키로 위치를 계산하는 것입니다. 해시 함수를 통과시키면 정수 값이 나오는데(흔히 16진수로 표기합니다), 이 값을 이용해 데이터를 어느 서버에 저장할지 계산할 수 있습니다.

해시가 어떤 값을 뱉는지 보기 위해 익숙한 SHA-256으로 예를 들어보겠습니다. (실제 분산 환경에서는 속도가 중요해 MurmurHash 같은 더 빠른 해시를 쓰지만, 값의 생김새를 보는 데는 무엇이든 상관없습니다.) "1234"를 SHA-256으로 변환해보겠습니다.

03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4

여기까지 보면, 이 긴 값으로 어떻게 위치를 계산한다는 건지 의아할 수 있습니다. 이 값은 길어 보이지만 16진수로 적힌 하나의 큰 정수입니다. 보기 편하게 10진수로 바꿔보겠습니다. 

1661548902539077689835780616605042428580731493960493799641588268547596371700

(두 숫자는 형태만 다를뿐 같은 값을 뜻합니다.)

다만 이 숫자는 너무 길어서 눈에 잘 들어오지 않습니다. 그래서 앞으로는 설명을 위해 1, 2, 3, 4 같은 짧은 숫자로 바꿔서 예를 들겠습니다. 실제로는 위와 같은 큰 정수가 쓰인다는 점만 기억하면 됩니다.

hash(key) % N

분산 환경에서는 서버를 여러 대 둡니다. 그래서 데이터를 각 서버에 균등하게 나눠 저장해야 합니다. 가장 간단한 방법은 hash(key)를 서버 개수로 나눈 나머지를 구하는 것입니다. 예를 들어 서버가 3대라면 나머지는 항상 0, 1, 2 중 하나가 나오고, 그 값을 서버 번호로 씁니다.

예를 들어 데이터 10, 21, 32가 있고 서버가 3대라고 해봅시다.

이렇게 세 데이터가 서로 다른 서버에 고르게 나뉩니다. 평상시에는 완벽합니다. 데이터는 추가되거나 삭제돼도 서버 개수가 3으로 그대로이기 때문에 % 3 계산이 변하지 않고, 따라서 큰 문제가 없습니다. 하지만 서버가 증설되거나 고장 나면 이야기가 달라집니다. 나누는 기준(서버 개수)이 바뀌기 때문입니다.

첫 번째 서버가 죽었습니다. 이제 서버는 3대가 아니라 2대입니다. 즉, 더 이상 % 3으로 계산하면 안 된다는 뜻입니다. 이제부터는 % 2로 계산해야 합니다. 

기존에 10번 데이터는 두 번째 서버가 담당했지만, 이제는 첫 번째 서버가 담당하게 되었습니다.
하지만 여기에는 함정이 있습니다. 서버가 3대일 때의 "첫 번째 서버"와, 한 대가 고장 난 뒤의 "첫 번째 서버"는 같은 번호일 뿐 실제로는 다른 서버일 수 있습니다. 번호는 그대로여도 데이터가 실제 다른 기계로 옮겨가는 것입니다. 결국, 번호만 봐서는 데이터가 실제로 어느 서버에서 어느 서버로 옮겨갔는지 알기 어렵습니다.

그런데 여기서 번호를 다시 매기는 문제가 생깁니다. 첫 번째 서버가 고장 났으니 남은 것은 두 번째, 세 번째 서버입니다. 하지만 % 2를 하면 나머지는 0과 1만 나오므로, 이 두 값을 남은 서버에 다시 이어 붙여야 합니다. 결국 서버 하나가 빠지면 번호 체계 전체가 밀리게 됩니다.

1번이 0번이고 2번이 1번

그렇다면 이게 왜 문제가 될까요? 단순히 번호가 밀리기 때문만은 아닙니다.

번호가 밀리면 % N의 계산 결과가 바뀌고, 그러면 거의 모든 데이터의 목적지가 달라집니다. 데이터가 있어야 할 서버에 없게 되는 것이죠. 그러면 데이터를 못 찾는 경우가 생깁니다. 만약 캐시라면, 이 요청들이 전부 원본 DB로 몰려 부하가 폭증할 수 있습니다.
그러니까 "밀림"은 시작일 뿐입니다. 진짜 문제는 대부분의 데이터가 재배치되면서 데이터를 못 찾고, 그 여파가 DB로 번진다는 것입니다. 이것이 가장 큰 대목입니다.

안정 해시

안정 해시는 링 해시라고도 불리며, 이것으로 앞의 문제를 해결할 수 있는지 살펴보겠습니다.

링 해시라 불리는 이유는 이렇습니다. 데이터와 서버를 모두 해시해서 하나의 원(링) 위에 올려놓습니다. 그리고 각 데이터는 링을 따라 시계방향으로 돌다가 처음 만나는 서버가 담당하게 됩니다.

앞과 같은 예시로 10번, 21번, 32번 데이터를 링 위에 올려놓겠습니다. 그리고 서버 3대도 함께 링 위에 올립니다. 다만 서버를 0, 1, 2처럼 나란히 붙여 놓으면 데이터가 한쪽으로 몰릴 수 있습니다. 그래서 이 예시에서는 서버를 링 여기저기에 흩어 놓겠습니다. (실제로는 서버의 위치도 서버 이름을 해시해서 정해지며, 그 결과 링 전체에 퍼지게 됩니다.)

서버는 그대로 0,1,2로 썼습니다.

각 데이터는 시계방향으로 돌다가 처음 만나는 서버가 담당합니다.

% N 방식에서 문제가 됐던 것은, 서버가 증설되거나 고장 나면 나누는 기준이 바뀌면서 대부분의 데이터가 다른 서버로 재배치된다는 점이었습니다. 안정 해시에서는 이를 얼마나 해결이 되었는지 확인해봅시다.

% N에서는 거의 모든 데이터가 재배치됐지만, 안정 해시에서는 영향받은 일부 데이터만 재배치됩니다. 이로써 데이터가 쓸데없이 대거 이동하는 문제는 해결했습니다.

% N의 가장 큰 장점은 데이터가 고르게 나뉜다는 점입니다. 하지만 안정 해시는 이 고름을 제어할 수단이 없습니다. 서버 위치가 해시 값으로 정해지다 보니, 링 위에 고르게 놓인다는 보장이 없기 때문입니다.

예를 들어 정수로는 1234보다 1235가 크지만, 해시를 통과시키면 이야기가 달라집니다. 1235의 해시 값이 1234보다 앞설 수도, 한참 뒤일 수도 있습니다. 입력의 크기와 해시 위치는 아무 상관이 없는 것이죠. 

데이터를 아주 많이 뿌려 보면, 서버들의 담당량이 얼마나 차이 나는지가 뚜렷하게 드러납니다. 다음과 같은 결과를 확인할 수 있습니다.

S1: 42% S2: 14% S3 44%

어떻게 보면 형평성에 어긋납니다. 서버마다 담당하는 데이터가 이렇게 차이나면 어떤 문제가 생길까요?

담당량이 많은 서버 하나가 먼저 한계에 부딪히기 때문입니다.

서버 세 대의 성능이 모두 같더라도, 한 대에 데이터가 몰리면 그 서버만 과부하로 힘들어집니다. 나머지 두 대는 여유로운데도 말이죠. 문제는, 시스템 전체의 한계가 가장 여유로운 서버가 아니라 가장 힘든 서버에 의해 정해진다는 점입니다.

짐꾼 세 명이 있다고 해봅시다. 힘은 모두 같은데 한 명에게만 짐을 몰아주면, 그 사람이 쓰러지는 순간 팀 전체가 멈춥니다. 나머지 둘이 아무리 팔팔해도 소용없죠.

결국 서버를 세 대나 뒀는데도, 한쪽은 과부하로 위험하고 한쪽은 놀게 됩니다. 실질적으로는 세 대의 성능을 다 쓰지 못하는 셈이죠.

가상 노드

이를 해결하기 위한 전략이 가상 노드입니다.

가상 노드는 서버 하나를 링 위 여러 위치에 흩어 놓는 것입니다. 서버 S1을 S1#1, S1#2, S1#3 … 처럼 여러 개의 분신으로 만들어 링 곳곳에 뿌리는 것이죠. 그것도 아주 많이요.

여기서 주의할 점은, 실제 서버가 여러 대로 늘어나는 게 아니라는 것입니다. 물리 서버는 그대로 한 대이고, 링 위에 "이 위치도 S1 담당"이라는 표시만 여러 개 찍는 것입니다. S1#1이든 S1#2든 결국 같은 서버 S1을 가리킵니다.

S1: 35% S2: 31% S3: 34%

링이 어떻게 보면 지저분해 보일 수 있습니다. 하지만 이렇게 하면 각 서버가 데이터를 훨씬 고르게 나눠 맡게 됩니다.

점 하나하나는 여전히 들쭉날쭉하지만, 한 서버의 분신을 여러 개 뿌리면 그 담당량의 총합이 서로 상쇄되어 평균에 가까워지기 때문입니다. 동전을 여러 번 던질수록 앞면 비율이 50%에 가까워지는 것과 같습니다.

하지만 100% 고르게 나뉘는 것은 아니라는 점을 명심해야 합니다. 분신을 많이 뿌릴수록 쏠림이 줄어드는 것은 사실이지만, 그만큼 관리해야 할 비용도 만만치 않습니다.

그렇다면 이 관리 비용은 어디서 오는 걸까요?

흔히 "분신이 많아서 관리가 어렵다"고 생각하기 쉽습니다. 하지만 그렇지 않습니다. 분신 100개를 지우는 일은 링에서 표시 몇 개를 지우는 것뿐이라, 컴퓨터에게는 아주 가벼운 작업입니다.

진짜 문제는 다른 곳에 있습니다. 바로 모든 서버가 링 정보를 각자 복사해서 들고 있어야 한다는 점입니다.

요청은 어느 서버로든 들어올 수 있고, 요청을 받은 서버는 "이 데이터가 어느 서버 담당인지"를 혼자 계산해야 합니다. 계산하려면 링(지도)이 필요하죠. 그래서 모든 서버가 링을 한 벌씩 복사해 들고 있습니다. 서버가 3,000대라면 링도 3,000벌인 셈입니다.

문제는 서버가 하나 추가되거나 고장 날 때입니다. 그 사실을 3,000대 모두에게 알리고, 각자의 링을 똑같이 고쳐야 합니다. 그런데 이 소식이 퍼지는 찰나에 어떤 서버는 이미 갱신했고 어떤 서버는 아직 모른다면, 두 서버가 같은 데이터를 서로 다른 곳으로 보내게 됩니다. 데이터를 찾지 못하는 것이죠.

즉, 관리가 어려운 이유는 "분신이 많아서"가 아니라, 여러 서버가 같은 링을 나눠 들고 있어서 그것을 항상 똑같이 맞춰야 하기 때문입니다.

마무리

% N부터 가상 노드까지 살펴보았습니다. 각 방식이 어떤 문제를 안고 있었고, 그다음 방식이 무엇을 해결하려 했는지 짚어보았습니다. 그 과정에서 본래의 장점이 사라지는 경우도 확인했습니다. 안정 해시로 넘어오며 재배치 리스크는 줄었지만, 완전히 없애지는 못했습니다. 여전히 일부 데이터는 재배치되기 때문입니다.

만약 제가 해시로 분산을 설계한다면, 안정 해시를 택할 것 같습니다. % N은 재배치가 너무 빈번하고, 가상 노드는 수많은 분신에 대한 링을 계속 맞춰야 해서 관리 비용이 만만치 않기 때문입니다.

물론 기본 안정 해시에는 데이터가 한쪽으로 몰릴 수 있다는 약점이 분명히 있습니다. 특히 서버 대수가 적을수록 그 쏠림은 두드러집니다. 그럼에도 저라면 가상 노드까지 가지 않고 기본 안정 해시 선에서 멈출 것 같습니다. 쏠림이라는 약점을 감수하더라도, 링을 계속 동기화해야 하는 복잡성을 떠안는 것보다는 단순한 구조를 유지하는 편이 낫다고 보기 때문입니다.

결국, 완벽한 방식은 없었습니다. 각 단계는 앞의 문제를 해결하면서 새로운 대가를 만들어냈고, 남은 것은 그중 어떤 대가를 감수할지 고르는 일이었습니다.