통째로 다시 만들어 바꾼다

앞 절에서 노드마다 목록을 두기로 했습니다. 그러면 검색어의 인기가 바뀔 때 그 목록을 어떻게 고치는지가 문제입니다.

한 노드씩 고치면 답이 뒤섞인다

검색어 하나의 점수가 바뀌면 그 경로의 조상 노드에서 순위가 바뀔 수 있습니다. 조상이 열 개면 열 곳을 고쳐야 합니다.

고치는 도중에 읽으면 어떤 노드는 새 순위이고 어떤 노드는 옛 순위입니다. 그러면 글자를 하나 더 넣었을 때 제안이 이상하게 바뀝니다. 짧은 접두사에서는 있던 단어가 긴 접두사에서는 없는 식입니다.

그래서 고치지 않고 새로 만들어 통째로 바꿉니다.

새 트라이를 옆에서 만든다
완성되면 가리키는 곳을 바꾼다
읽는 쪽은 그 순간까지 옛 것을 온전하게 읽는다

바뀌지 않는 것으로 만들면 잠금이 필요 없다

한 번 만든 트라이를 고치지 않기로 하면, 읽는 쪽과 쓰는 쪽이 같은 것을 만지지 않습니다. 잠금도 조율도 필요하지 않습니다.

초당 2만 요청이 들어오는 경로에서 잠금을 없애는 것은 큰 이득입니다. 그리고 교체가 실패하면 옛 것이 그대로 쓰이므로, 실패가 곧 안전한 상태입니다.

되돌리기도 값쌉니다. 새 것이 이상하면 가리키는 곳을 옛 것으로 돌리면 됩니다. 데이터를 되돌리는 것이 아니라 가리키는 곳만 바꿉니다.

무엇으로 만드나

트라이를 만드는 재료는 검색 기록을 모은 집계입니다.

이 과정은 자동완성 요청 경로와 완전히 분리돼 있습니다. 하루 한 번 돌고, 느려도 사용자에게 영향이 없습니다. 읽기 경로와 만드는 경로를 나누는 것이 이 아키타입의 골격입니다.

집계 대상은 자동완성 요청이 아니라 실제로 검색된 것입니다. 자동완성 요청을 세면 타이핑 중간 상태가 다 섞여서, 아무도 검색하지 않은 조각이 인기 검색어가 됩니다.

통째로 바꾸는 것의 대가

세 가지를 감수합니다.

두 번째가 실제로 걸리는 지점입니다. 교체하는 순간에는 옛 트라이와 새 트라이가 동시에 존재합니다. 한 대에 두 벌이 들어가지 않으면 만드는 곳과 쓰는 곳을 나눠야 합니다.