안정 해시 설계 면접 퀴즈

안정 해시는 제품이 아니라 기법입니다. 그래서 어떤 상황에서 그 기법이 필요한지부터 고정합니다. 이 토픽은 아래 하나의 요구사항을 끝까지 풉니다.

기능 요구사항과 범위 밖

장애 감지를 범위 밖으로 둔 것이 중요합니다. "어느 서버가 죽었다" 는 주어진 입력으로 보고, 그 뒤에 담당을 어떻게 다시 정할지만 다룹니다. 감지까지 끌어오면 이야기가 흩어집니다.

왜 이동량이 첫 제약인가

캐시는 담당이 바뀌면 그 키를 새 서버에서 찾게 되고, 새 서버에는 값이 없습니다. 그러면 원본으로 갑니다.

평소: 조회 50만 x 미스 5퍼센트 = 원본 요청 2.5만
담당이 전부 바뀐 직후: 원본 요청 50만

20배입니다. 원본이 그 부하를 못 받으면 캐시를 채울 수도 없어서 회복이 더 늦어집니다. 그래서 이 설계에서 가장 먼저 재는 것은 처리량이 아니라 서버 한 대가 늘거나 빠질 때 담당이 바뀌는 키의 비율입니다.

구성 변경은 사건이 아니라 상시 조건이다

주당 3~4번 이라는 숫자가 이것을 말합니다. 서버 100대 규모에서 증설과 교체와 장애를 합치면 구성 변경은 늘 일어나는 일입니다.

한 번의 이사라면 새벽에 조용히 옮기고 끝낼 수 있습니다. 매주 일어나는 일이라면 이동 비용을 구조로 낮춰야 합니다. 운영 절차로 감당할 수 있는 종류가 아닙니다.

담당 계산은 요청 경로에 있다

조회 초당 50만 이므로 담당 서버를 찾는 계산이 초당 50만 번 실행됩니다. 예산 0.1ms 는 여기에 붙습니다.

그래서 담당은 물어보지 않고 계산으로 알아야 합니다. 이 제약이 뒤의 설계를 크게 좁힙니다.

캐시라서 다른 점

캐시는 값을 잃어도 됩니다. 담당이 바뀐 키의 값을 새 서버로 옮기지 않고 버려도 됩니다. 다시 채우면 되니까요.

같은 기법을 쓰지만 대가의 종류가 다릅니다. 이 요구사항은 캐시이므로 이동량이 곧 미스로 환산되고, 저장소라면 이동량이 곧 이관 작업량이 됩니다.

앞 단계에서 이동량이 첫 제약이고, 담당은 물어보지 않고 계산으로 알아야 한다고 정했습니다. 계산으로 담당을 정하는 가장 단순한 방법부터 봅니다.

서버 수로 나눈 나머지

담당 서버 번호 = 해시(키) % 서버 수

좋은 점이 많습니다. 계산이 연산 두 번이라 0.1ms 예산에 여유가 크고, 해시가 고르면 분포도 고르며, 구현이 한 줄이고 들고 있을 상태가 서버 수 하나뿐입니다.

서버 수가 바뀌면 규칙 자체가 바뀐다

문제는 나누는 수가 규칙의 일부라는 것입니다. 서버 수가 바뀌면 모든 키의 계산 결과가 함께 바뀝니다. 값이 조금 밀리는 것이 아니라 규칙 없이 재배열됩니다.

서버가 많아질수록 나빠집니다. 규모를 키우려고 서버를 늘리는데 늘릴수록 늘리기가 어려워지는 구조입니다.

요구사항과 대조하면 탈락한다

앞 단계에서 계산한 숫자를 그대로 씁니다. 담당이 99퍼센트 바뀌면 적중률이 거의 0으로 떨어지고 원본 요청이 20배가 됩니다. 적중률 95퍼센트 이상 유지라는 요구사항을 정면으로 어깁니다.

그리고 이 일이 주당 3~4번 일어납니다. 한 번이면 새벽에 감당할 수 있지만 매주라면 구조를 바꿔야 합니다.

그래도 이 방법이 맞는 경우

나머지 연산을 나쁜 방법으로 외우면 안 됩니다. 서버 수가 고정이거나, 담당이 바뀌어도 잃을 것이 없으면 이보다 단순하고 값싼 방법이 없습니다.

무엇을 담고 있는지가 판단을 가릅니다. 담당이 바뀔 때 잃는 것이 없다면 나머지 연산으로 충분합니다.

서버 수를 넉넉하게 잡아 두면 되지 않나

미리 1,000으로 나눠 두고 서버 100대가 각각 10개 조각을 맡는 방법이 있습니다. 조각 수는 고정이므로 나머지 규칙은 그대로이고, 서버가 늘면 조각의 담당만 옮깁니다.

이 방법은 실제로 쓰입니다. 다만 조각과 서버의 매핑 표를 누군가 관리하고 모두에게 알려야 하고, 처음 정한 조각 수가 상한이 됩니다. 조각 수를 늘리는 순간 다시 같은 문제로 돌아갑니다.

다음 단계에서 매핑 표 없이 같은 효과를 얻는 방법을 봅니다.

앞 단계에서 나머지 연산이 무너진 이유는 하나였습니다. 나누는 수가 규칙의 일부라서 서버 수가 바뀌면 모든 계산 결과가 함께 바뀌는 것입니다.

그러면 규칙에서 서버 수를 빼면 됩니다.

키와 서버를 같은 공간에 놓는다

해시 값의 범위를 끝과 시작이 이어진 하나의 원으로 봅니다. 키도 서버도 같은 해시 함수로 그 원 위의 한 점이 됩니다. 그리고 규칙은 이렇습니다.

키의 담당 = 그 키에서 시계 방향으로 처음 만나는 서버

이 규칙에 서버 수가 들어 있지 않습니다. 서버가 몇 대든 계산 방법이 같습니다.

서버가 늘 때 이동량

새 서버는 원 위의 한 점으로 들어옵니다. 그 지점 때문에 경계가 하나 생기고, 바로 앞 구간의 키들만 담당이 바뀝니다. 원래 그 키들을 맡던 다음 서버에서 새 서버로 넘어갑니다.

다른 경계는 건드리지 않는 것이 핵심입니다. 서버 100대 중 한 대를 더하면 새 서버가 가져가는 몫만 움직이므로 평균적으로 전체의 100분의 1입니다.

요구사항과 대조한다

앞에서 계산한 방식을 그대로 씁니다. 이동한 키가 1퍼센트면 그 키에 대한 조회만 미스가 되므로,

평소 미스: 조회 50만 x 5퍼센트 = 2.5만
추가 미스: 조회 50만 x 1퍼센트 = 0.5만
합계 3만. 평소의 1.2배

99퍼센트 이동일 때 20배였던 것이 1.2배가 됩니다. 적중률 95퍼센트 유지라는 요구사항 안에 들어옵니다.

서버가 빠질 때

그 서버의 점이 원에서 사라지고, 그 서버가 맡던 구간은 시계 방향 다음 서버로 합쳐집니다. 이동량은 그 서버가 갖고 있던 몫이므로 이번에도 전체의 100분의 1 수준입니다.

다만 그 몫이 한 서버에 전부 갑니다. 빠진 서버의 부하를 다음 한 대가 다 받는 것이라, 이미 바쁜 서버였다면 연달아 무너질 수 있습니다. 이 문제는 다음 단계에서 함께 해결됩니다.

무엇을 얻고 무엇을 잃었나

공짜가 아닙니다. 서버 목록과 위치를 모든 클라이언트가 들고 있어야 하고, 그 목록이 서로 다르면 같은 키가 다른 서버로 갑니다. 담당 계산도 나눗셈 하나보다는 무겁습니다. 이 두 대가는 뒤에서 각각 다룹니다.