Foundry
검색어 자동완성 설계
중급
핵심

요구사항과 요청 증폭

검색 한 번이 요청 스무 번을 만든다

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

항목
대상검색어 자동완성
검색하루 1억 건 (초당 1,157)
한 검색당 입력평균 20타
제안 개수상위 5개
응답 시간상위 1퍼센트가 100ms 이내
검색어 종류1억 종류
갱신하루 1회 반영이면 된다
순서많이 검색된 것부터

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

한 번의 검색이 입력 글자 수만큼의 자동완성 요청을 만든다 검색 요청 초당 1,157 자동완성 요청 초당 2만. 20배 한 글자마다 한 번씩 물어본다 요청 하나에 계산을 조금이라도 두면 20배로 곱해진다 읽기만 하고 아무것도 계산하지 않는 구조로 만든다 그리고 앞쪽 한두 글자는 제안이 무의미해서 안 물어도 된다

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

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

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

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

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

응답 시간결과
타이핑보다 빠르다글자마다 제안이 갱신된다
타이핑보다 느리다제안이 뒤늦게 깜빡이며 바뀐다

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

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

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

항목무엇을 허용하나
갱신이 하루 1회면 된다데이터를 통째로 다시 만들어 바꿀 수 있다
제안이 5개면 된다노드마다 다섯 개만 들고 있으면 된다

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

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

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

이번에 다루지 않는 것이유
트라이의 구조와 연산자료구조 문서에서 다룬다
검색 결과 자체를 찾는 것자동완성은 검색어를 제안할 뿐이다
개인별 검색 기록 기반 제안답이 사용자마다 달라지면 캐시가 무의미해진다
오타 교정 제안별도 문제다. 먼저 정확한 접두사를 다룬다

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

면접에서 이렇게 나옵니다

Q.검색이 하루 1억 건인데 자동완성 요청은 얼마나 됩니까

초당 약 2만입니다. 검색의 20배입니다.

초당 1,157 x 한 검색당 20타 = 초당 약 2만

자동완성은 글자마다 한 번씩 물어봅니다. 검색량이 아니라 입력량이 부하입니다.

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

흔한 실수: 검색량으로 용량을 산정하는 것. 20배를 놓치면 처음부터 스무 배 작은 시스템을 설계하게 됩니다. 그리고 앞쪽 한두 글자는 제안이 무의미해서 안 물어도 되는데, 그것을 클라이언트 규칙으로 정해 두면 요청을 실제로 줄일 수 있습니다.

Q.응답 100ms 라는 요구가 무엇을 금지합니까

접두사 아래의 단어를 모아 정렬하는 것을 금지합니다.

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

응답 시간결과
타이핑보다 빠르다글자마다 제안이 갱신된다
타이핑보다 느리다제안이 뒤늦게 깜빡이며 바뀐다

답을 만드는 데 쓸 시간이 거의 없다는 뜻입니다.

흔한 실수: 이것을 사용자 체감 목표로만 읽는 것. 이 숫자는 읽을 때 계산할 수 없다는 설계 제약입니다. 그래서 답을 미리 만들어 두는 것이 선택이 아니라 유일한 방법이 됩니다.

Q.요구사항의 어느 항목이 설계를 쉽게 만듭니까

갱신이 하루 1회면 된다는 것과 제안이 5개면 된다는 것입니다.

항목무엇을 허용하나
하루 1회 갱신데이터를 통째로 다시 만들어 바꿀 수 있다
제안 5개노드마다 다섯 개만 들고 있으면 된다

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

흔한 실수: 요구사항에서 제약만 찾고 여유를 찾지 않는 것. 무엇이 허용되는지를 먼저 확인하면 훨씬 단순한 설계가 가능한데, 그것을 놓치면 필요 없는 실시간 구조를 만들게 됩니다.

Q.개인별 검색 기록으로 제안을 다르게 하면 어떤 문제가 생기나요

캐시 적중률이 무너지고 초당 2만이 그대로 우리에게 옵니다.

이 시스템에서 가장 큰 자산은 답이 모든 사용자에게 같다는 것입니다. 같은 접두사에 같은 답을 주므로 한 번 만든 답을 모두에게 재사용할 수 있습니다.

개인화를 넣으면 답이 사용자마다 달라져 재사용이 사라집니다.

흔한 실수: 개인화를 품질 개선으로만 보는 것. 비용 구조를 바꾸는 결정입니다. 넣으려면 개인 신호를 소수의 집단 단위로 묶거나, 공통 답을 클라이언트에서 재정렬하는 식으로 재사용을 지켜야 합니다.

먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.

읽었으면 문제로 확인해보세요

검색어 자동완성 설계 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.