앞 단계에서 나머지 연산이 무너진 이유는 하나였습니다. 나누는 수가 규칙의 일부라서 서버 수가 바뀌면 모든 계산 결과가 함께 바뀌는 것입니다.
그러면 규칙에서 서버 수를 빼면 됩니다.
키와 서버를 같은 공간에 놓는다
해시 값의 범위를 끝과 시작이 이어진 하나의 원으로 봅니다. 키도 서버도 같은 해시 함수로 그 원 위의 한 점이 됩니다. 그리고 규칙은 이렇습니다.
키의 담당 = 그 키에서 시계 방향으로 처음 만나는 서버
이 규칙에 서버 수가 들어 있지 않습니다. 서버가 몇 대든 계산 방법이 같습니다.
서버가 늘 때 이동량
새 서버는 원 위의 한 점으로 들어옵니다. 그 지점 때문에 경계가 하나 생기고, 바로 앞 구간의 키들만 담당이 바뀝니다. 원래 그 키들을 맡던 다음 서버에서 새 서버로 넘어갑니다.
| 상황 | 담당이 바뀌는 키 |
|---|---|
| 나머지 연산에서 한 대 추가 | 약 99퍼센트 |
| 링에서 한 대 추가 | 약 1퍼센트 |
다른 경계는 건드리지 않는 것이 핵심입니다. 서버 100대 중 한 대를 더하면 새 서버가 가져가는 몫만 움직이므로 평균적으로 전체의 100분의 1입니다.
요구사항과 대조한다
앞에서 계산한 방식을 그대로 씁니다. 이동한 키가 1퍼센트면 그 키에 대한 조회만 미스가 되므로,
평소 미스: 조회 50만 x 5퍼센트 = 2.5만
추가 미스: 조회 50만 x 1퍼센트 = 0.5만
합계 3만. 평소의 1.2배
99퍼센트 이동일 때 20배였던 것이 1.2배가 됩니다. 적중률 95퍼센트 유지라는 요구사항 안에 들어옵니다.
서버가 빠질 때
그 서버의 점이 원에서 사라지고, 그 서버가 맡던 구간은 시계 방향 다음 서버로 합쳐집니다. 이동량은 그 서버가 갖고 있던 몫이므로 이번에도 전체의 100분의 1 수준입니다.
다만 그 몫이 한 서버에 전부 갑니다. 빠진 서버의 부하를 다음 한 대가 다 받는 것이라, 이미 바쁜 서버였다면 연달아 무너질 수 있습니다. 이 문제는 다음 단계에서 함께 해결됩니다.
무엇을 얻고 무엇을 잃었나
| 항목 | 나머지 연산 | 링 |
|---|---|---|
| 담당 계산 | 연산 두 번 | 정렬된 목록에서 찾기 |
| 들고 있을 상태 | 서버 수 하나 | 서버 목록과 각자의 위치 |
| 한 대 추가 시 이동 | 약 99퍼센트 | 약 1퍼센트 |
공짜가 아닙니다. 서버 목록과 위치를 모든 클라이언트가 들고 있어야 하고, 그 목록이 서로 다르면 같은 키가 다른 서버로 갑니다. 담당 계산도 나눗셈 하나보다는 무겁습니다. 이 두 대가는 뒤에서 각각 다룹니다.