검색어 자동완성 설계 면접 퀴즈

검색어 자동완성을 설계합니다. 검색창에 글자를 넣는 동안 상위 5개를 보여주는 기능입니다.

검색량이 아니라 입력량이 부하다

검색은 하루 1억 건 (초당 1,157)입니다. 그 자체로는 부담이 아닙니다. 그런데 자동완성은 글자마다 한 번씩 물어봅니다. 한 검색에 평균 20타를 넣으면 요청이 20배가 됩니다.

초당 1,157 x 20 = 초당 약 2만

이 숫자가 첫 결론을 강제합니다. 요청 하나에 계산을 조금이라도 두면 20배로 곱해집니다. 그래서 자동완성 요청은 읽기만 하고 아무것도 계산하지 않는 것으로 만들어야 합니다.

100ms 는 사용자 체감이 아니라 설계 제약이다

응답이 100ms를 넘으면 사용자의 다음 타이핑이 먼저 도착합니다. 그러면 이전 답은 화면에 뜨지도 못하고 버려집니다.

즉 이 요구사항은 답을 만드는 데 쓸 시간이 거의 없다는 뜻입니다. 접두사 아래의 단어를 모아 정렬하는 것은 이 예산에 들어오지 않습니다.

무엇이 이 설계를 쉽게 만드나

요구사항에 우리를 도와주는 항목이 둘 있습니다.

이 두 줄이 없으면 이 시스템은 훨씬 어려워집니다. 실시간 갱신을 요구하면 통째로 바꾸는 방식을 쓸 수 없고, 제안을 100개 보여 달라고 하면 미리 저장하는 이득이 줄어듭니다.

접두사 검색 자체는 이미 다룬 문제다

문자열을 접두사로 찾는 자료구조는 트라이에서 다뤘습니다. 여기서는 그것을 서비스 규모로 운영하는 문제를 봅니다.

세 번째 항목이 중요합니다. 답이 모든 사용자에게 같다는 것이 이 시스템에서 가장 큰 자산입니다. 개인화를 넣는 순간 캐시 적중률이 무너지고 초당 2만이 그대로 우리에게 옵니다.

앞 절에서 읽을 때 계산할 시간이 없다는 것을 확인했습니다. 그러면 답을 어디에 어떤 형태로 두는지가 다음 문제입니다.

노드마다 답을 들고 있는다

접두사에 해당하는 노드를 찾는 것은 글자 수만큼 내려가면 되므로 값쌉니다. 문제는 그 아래에 있는 단어를 모아 정렬하는 것입니다. 인기 있는 짧은 접두사는 아래에 수만 건이 달려 있습니다.

그래서 노드마다 그 아래의 상위 5개를 미리 저장합니다. 읽기는 노드를 찾아 그 목록을 그대로 보내는 것으로 끝납니다.

읽기를 공짜로 만드는 값을 쓰기가 냅니다. 검색어 하나의 점수가 바뀌면 그 경로의 모든 조상 노드에서 순위가 바뀔 수 있습니다.

저장 크기를 계산한다

노드마다 목록을 두면 저장이 얼마나 되는지 봐야 합니다.

검색어 1억 종류, 평균 길이 10글자
공통 접두사를 공유하므로 노드 수는 검색어 수보다 적다
노드마다 5개 x (문자열 참조 + 점수)

여기서 중요한 판단이 하나 있습니다. 목록에 문자열을 그대로 담지 않습니다. 같은 단어가 조상 노드마다 반복되기 때문입니다. 열 글자 단어는 조상이 열 개라 열 번 저장됩니다.

식별자만 담고 문자열은 따로 두면 이 중복이 사라집니다. 대신 읽을 때 식별자를 문자열로 바꾸는 일이 생기는데, 그것은 다섯 개뿐이라 값쌉니다.

어느 노드까지 목록을 두나

모든 노드에 둘 필요는 없습니다.

긴 접두사는 아래에 달린 단어가 적어서 읽을 때 모아도 100ms 안에 끝납니다. 목록을 둘 이유가 없습니다.

이 판단이 저장을 크게 줄입니다. 노드 수는 접두사가 길어질수록 급격히 늘어나므로, 긴 쪽을 빼면 대부분이 빠집니다.

점수는 무엇으로 하나

목록의 순서를 정하는 값은 검색된 횟수입니다. 그런데 언제부터의 횟수인지를 정해야 합니다.

전체 기간의 횟수를 쓰면 오래전 유행이 계속 남는다
최근 기간만 쓰면 꾸준한 검색어가 밀린다

두 값을 섞습니다. 최근 며칠에 무게를 더 주고 그보다 오래된 것에는 적게 줍니다. 하루 1회 갱신이므로 이 계산을 그때 한 번만 하면 됩니다.

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

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

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

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

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

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

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

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

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

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

무엇으로 만드나

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

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

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

통째로 바꾸는 것의 대가

세 가지를 감수합니다.

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