앞 단계에서 링 항목이 15,000개가 됐습니다. 이제 조회마다 그 안에서 담당을 찾아야 합니다. 예산은 0.1ms 이고 이 계산은 초당 50만 번 실행됩니다.
정렬해 두고 반씩 좁힌다
링을 펼쳐 위치 순으로 정렬한 목록으로 둡니다. 그러면 "이 키의 해시 값보다 크거나 같은 첫 지점" 을 반씩 좁혀 찾을 수 있습니다.
15,000개를 반씩 좁히면 14단계
비교 14번이면 0.1ms 예산 안에 넉넉하다
담당을 찾는 일이 목록을 처음부터 훑는 것이 되면 15,000번 비교가 되고, 초당 50만 조회면 초당 75억 번의 비교가 됩니다. 정렬 상태를 유지하는 것이 이 설계의 전제입니다.
감싸기를 빼먹지 않는다
링의 양 끝은 같은 점입니다. 해시 값이 마지막 지점보다 큰 키는 시계 방향으로 돌아 처음 지점을 만납니다.
이 처리를 빼먹으면 그 구간의 키에서 담당을 못 찾습니다. 구현에서 가장 흔한 실수이고, 평소에는 드러나지 않다가 키의 일부에서만 실패하므로 원인을 찾기 어렵습니다.
어디서 계산하나
계산 자체는 값싸지만 링을 누가 들고 있느냐가 갈립니다.
| 위치 | 왕복 | 대가 |
|---|---|---|
| 클라이언트가 계산 | 없다 | 모든 클라이언트가 링을 들고 있어야 한다 |
| 앞단 프록시가 계산 | 한 번 늘어난다 | 링은 한 곳만 갱신하면 된다 |
| 아무 서버에 보내고 넘기기 | 내부에서 한 번 | 구현이 단순하다. 절반이 두 번 이동한다 |
예산 0.1ms 는 왕복을 허용하지 않으므로 이 요구사항에서는 클라이언트가 계산합니다. 그 대가로 링을 모두에게 나눠 주는 일이 생기고, 다음 단계가 그 이야기입니다.
해시 함수는 빠른 것을 고른다
이 해시는 보안용이 아니라 분배용입니다. 초당 50만 번 실행되므로 속도가 중요하고, 필요한 성질은 값이 고르게 흩어지는 것뿐입니다.
| 성질 | 필요한가 |
|---|---|
| 고른 분포 | 필요하다. 편차가 곧 부하 편차다 |
| 빠른 계산 | 필요하다. 요청 경로에 있다 |
| 역산이 어려움 | 필요 없다. 비밀을 지키는 용도가 아니다 |
암호용 해시는 역산을 어렵게 만드는 값을 치르므로 느립니다. 그 값을 여기서는 낼 이유가 없습니다.
키와 서버 위치에 같은 함수를 써야 합니다. 다른 함수를 쓰면 두 값이 같은 공간에 놓이지 않아 담당 규칙 자체가 성립하지 않습니다.