앞 절에서 읽을 때 계산할 시간이 없다는 것을 확인했습니다. 그러면 답을 어디에 어떤 형태로 두는지가 다음 문제입니다.
노드마다 답을 들고 있는다
접두사에 해당하는 노드를 찾는 것은 글자 수만큼 내려가면 되므로 값쌉니다. 문제는 그 아래에 있는 단어를 모아 정렬하는 것입니다. 인기 있는 짧은 접두사는 아래에 수만 건이 달려 있습니다.
그래서 노드마다 그 아래의 상위 5개를 미리 저장합니다. 읽기는 노드를 찾아 그 목록을 그대로 보내는 것으로 끝납니다.
| 방식 | 읽기 | 쓰기 |
|---|---|---|
| 읽을 때 모으기 | 아래 단어 수에 비례 | 값싸다 |
| 미리 저장 | 노드 찾기만 | 조상 노드를 다 손봐야 한다 |
읽기를 공짜로 만드는 값을 쓰기가 냅니다. 검색어 하나의 점수가 바뀌면 그 경로의 모든 조상 노드에서 순위가 바뀔 수 있습니다.
저장 크기를 계산한다
노드마다 목록을 두면 저장이 얼마나 되는지 봐야 합니다.
검색어 1억 종류, 평균 길이 10글자
공통 접두사를 공유하므로 노드 수는 검색어 수보다 적다
노드마다 5개 x (문자열 참조 + 점수)
여기서 중요한 판단이 하나 있습니다. 목록에 문자열을 그대로 담지 않습니다. 같은 단어가 조상 노드마다 반복되기 때문입니다. 열 글자 단어는 조상이 열 개라 열 번 저장됩니다.
식별자만 담고 문자열은 따로 두면 이 중복이 사라집니다. 대신 읽을 때 식별자를 문자열로 바꾸는 일이 생기는데, 그것은 다섯 개뿐이라 값쌉니다.
어느 노드까지 목록을 두나
모든 노드에 둘 필요는 없습니다.
| 노드 | 목록을 두나 |
|---|---|
| 1에서 6글자 접두사 | 둔다. 요청의 대부분이 여기다 |
| 아주 긴 접두사 | 두지 않는다. 그 아래에 단어가 몇 개뿐이다 |
긴 접두사는 아래에 달린 단어가 적어서 읽을 때 모아도 100ms 안에 끝납니다. 목록을 둘 이유가 없습니다.
이 판단이 저장을 크게 줄입니다. 노드 수는 접두사가 길어질수록 급격히 늘어나므로, 긴 쪽을 빼면 대부분이 빠집니다.
점수는 무엇으로 하나
목록의 순서를 정하는 값은 검색된 횟수입니다. 그런데 언제부터의 횟수인지를 정해야 합니다.
전체 기간의 횟수를 쓰면 오래전 유행이 계속 남는다
최근 기간만 쓰면 꾸준한 검색어가 밀린다
두 값을 섞습니다. 최근 며칠에 무게를 더 주고 그보다 오래된 것에는 적게 줍니다. 하루 1회 갱신이므로 이 계산을 그때 한 번만 하면 됩니다.