한 대에 안 들어갈 때

앞 절에서 두 벌이 필요하다는 것을 봤습니다. 검색어 1억 종류에 노드마다 목록까지 두면 한 대에 들어가지 않을 수 있습니다. 나눠야 한다면 어떻게 나누는지가 이 절입니다.

첫 글자로 나누면 고르지 않다

가장 단순한 방법은 첫 글자로 나누는 것입니다. 그런데 검색어의 첫 글자는 고르게 퍼져 있지 않습니다. 흔한 글자로 시작하는 조각은 크고 드문 글자로 시작하는 조각은 거의 비어 있습니다.

조각 수를 늘려도 큰 조각이 쪼개지지 않습니다. 첫 글자가 같은 것은 언제나 같은 조각에 있기 때문입니다.

그래서 글자가 아니라 검색량으로 경계를 정합니다.

검색어를 사전 순으로 놓고 누적 검색량이 고르게 되도록 자른다
어느 조각도 한 대에 들어갈 만한 크기가 되게 한다

왜 해시로 나누지 않나

다른 시스템에서는 키를 해시해서 나누는 것이 기본입니다. 여기서는 그러면 안 됩니다.

해시로 나누면 접두사 하나를 물어볼 때 모든 조각에 물어봐야 합니다. 초당 2만 요청에 조각 수를 곱하면 그 자체로 무너집니다.

접두사 검색은 순서가 의미를 갖는 조회입니다. 그래서 순서를 보존하는 분할을 씁니다.

요청을 어느 조각으로 보내나

경계를 알면 앞 글자 몇 개만 보고 목적지를 정할 수 있습니다. 이 경계표는 작아서 요청을 받는 쪽이 들고 있어도 됩니다.

경계는 갱신할 때 다시 정합니다. 유행이 바뀌면 어느 조각이 뜨거워지는지도 바뀝니다. 통째로 다시 만드는 방식이라 경계를 바꾸는 것도 그때 함께 하면 되고, 따로 재배치할 일이 없습니다.

이것이 앞 절의 결정에서 따라오는 이득입니다. 제자리에서 고치는 구조라면 경계 변경이 데이터 이동을 뜻하지만, 새로 만드는 구조에서는 그냥 다르게 만드는 것입니다.

뜨거운 조각은 나누는 것으로 풀리지 않는다

짧고 인기 있는 접두사는 요청이 몰립니다. 그 접두사가 어느 조각에 있든 그 조각이 뜨거워집니다.

두 문제를 같은 수단으로 풀 수 없습니다. 크기는 나눠서 줄이고, 조회 쏠림은 같은 조각을 여러 대에 복사해 나눠 읽습니다. 트라이가 바뀌지 않는 것이므로 사본을 늘리는 데 조율이 필요하지 않습니다.