검색어 자동완성은 사용자가 검색창에 몇 글자만 입력해도 관련된 검색어 후보를 제안하는 기능이다. Google, Naver, YouTube, Amazon 같은 서비스에서 이미 표준처럼 제공되고 있으며 빠른 응답 속도(수 ms 단위)와 높은 정확성이 핵심이다.
예를 들어, 사용자가 삼성이라고 입력하면 삼성 갤럭시, 삼성 주가, 삼성 서비스센터 같은 추천어가 즉시 제시된다. 이 기능은 단순 편의성이 아니라 검색 품질과 사용자 체류 시간에 직접적으로 영향을 주기 때문에 대규모 트래픽을 고려한 아키텍처가 필요하다.
요구사항 정리
기능적 요구사항
- 사용자가 입력하는 prefix 기반으로 검색어 후보 제안
- 제안어는 인기 순위, 개인화(검색 기록, 지역, 시간대 등)를 반영
- 빠른 응답 (100ms 이내, ideally 10ms 수준)
- 잘못된 입력(오타)에 대한 대응 (Optional)
비기능적 요구사항
- 초당 수십만 QPS(검색창 자동완성은 입력할 때마다 호출됨 → 트래픽 폭발)
- 글로벌 서비스라면 지리적으로 분산된 데이터센터
- 실시간 업데이트 (신규 검색어/급상승 검색어 반영)
설계 포인트
데이터 수집
- Query Log: 사용자가 입력한 검색어와 빈도를 로그로 수집
- Batch 처리: Hadoop / Spark 같은 시스템으로 주기적 집계
- Stream 처리: Kafka + Flink/Samza 같은 실시간 스트리밍으로 급상승 검색어 반영
데이터 저장 구조
검색어 자동완성에서 가장 중요한 부분은 입력한 접두사(prefix)에 해당하는 후보를 얼마나 빠르게 찾아낼 수 있는가이다. 이를 위해 가장 많이 고려되는 자료구조는 Trie(트라이)와 B-Tree/정렬 배열이다.
Trie(트라이)는 문자열을 문자 단위로 분리해 트리 형태로 저장하는 방식이다. 삼성 갤럭시라는 검색어가 있다면 삼 → 성 → " " → 갤 → 럭 → 시 순서로 노드가 이어진다. 사용자가 삼까지만 입력해도 해당 노드 이하에 어떤 검색어들이 있는지 빠르게 찾을 수 있기 때문에 빠른 prefix 탐색이 가능하다. 다만, 전체 검색어를 저장하면 메모리 사용량이 기하급수적으로 커지므로 대규모 서비스에서는 메모리 최적화 기법(압축 트라이, Top-K 후보만 저장 등)을 반드시 병행해야 한다.
반면 B-Tree나 정렬 배열 기반 이진 탐색은 사전순으로 정렬된 검색어 리스트를 두고 특정 prefix의 시작과 끝을 binary search로 찾는 방식이다. 예를 들어 삼성으로 시작하는 검색어 범위를 찾으면 그 구간 내에서 Top-N을 바로 가져올 수 있다. 이 방식은 메모리 효율적이고 캐싱과 잘 결합되지만 문자열 비교 연산이 많아질 수 있다는 단점이 있다.
실제 대규모 서비스에서는 두 방식을 혼합하여 짧은 prefix(1~2글자)는 Trie로 빠르게 탐색하고 긴 prefix는 정렬 리스트/이진 탐색으로 처리하는 구조를 취하는 경우가 많다.
캐싱 전략
- Hot 키워드 캐싱: 상위 10만~100만 검색어는 메모리에 올려둠 (Redis/Memcached)
- 지역 캐싱: CDN 또는 지역 데이터센터에 인기 검색어 캐싱
- L1 캐시: 애플리케이션 서버 메모리
- L2 캐시: Redis/Memcached 클러스터
순위 산정
자동완성에서 단순히 후보 검색어를 보여주는 것만으로는 부족하다. 사용자가 가장 많이 선택할 법한 순서대로 정렬해 제시해야 검색 품질과 사용자 경험이 향상된다. 이를 위해 다양한 요소를 고려한 랭킹 알고리즘이 필요하다.
우선 기본적인 기준은 검색 빈도(frequency)다. 많이 검색된 검색어일수록 상단에 노출된다. 그러나 단순 빈도만 기준으로 하면 오래된 인기 검색어만 반복 노출될 수 있기 때문에 최근성(recency)을 가중치로 함께 고려한다. 예를 들어 최근 하루 동안 급격히 증가한 검색어는 일시적으로 높은 점수를 받아 상위에 노출된다.
또한 현대의 자동완성은 개인화(personalization)를 필수적으로 반영한다. 동일한 삼성이라는 입력이라도 어떤 사용자는 삼성 주가를 더 자주 클릭하고 또 다른 사용자는 삼성 서비스센터를 더 자주 찾는다. 이를 위해 사용자 프로필(검색 이력, 지역, 시간대, 기기 종류 등)을 반영한 개인화 랭킹을 적용한다.
최종적으로는 단일 기준이 아니라 가중치 기반의 종합 점수가 사용된다. 예를 들어 최종 점수 = α * frequency + β * recency + γ * personalization 형태의 모델을 만들고 각 서비스 정책과 데이터 특성에 맞게 α, β, γ 값을 조정한다. 최근에는 머신러닝 기반 랭킹 모델(LTR, Learning To Rank)을 도입해 더욱 정교하게 순위를 매기기도 한다.
시스템 아키텍처
사용자 입력 → API Gateway → Autocomplete Service
↙ ↘
Cache(Redis) Search Index(Trie/B-Tree)
↘
Offline/Realtime Processing
(Kafka + Hadoop/Spark + Flink)확장성 고려
- 샤딩: 알파벳/언어별로 샤딩 (예: 한국어 vs 영어 인덱스 분리)
- Replication: 읽기 트래픽 분산
- CQRS 패턴: 검색어 입력(쓰기)와 자동완성 조회(읽기)를 분리
- 실시간 업데이트: Kafka → Flink → Redis 갱신 파이프라인
📝 배운점
검색어 자동완성은 단순히 문자열 검색 문제가 아니라 실시간성, 대규모 트래픽, 개인화, 랭킹이 복합적으로 얽힌 문제였다. 특히 사용자가 한 글자 입력할 때마다 API가 호출되므로 일반 검색보다 훨씬 높은 QPS를 처리해야 하고 따라서 캐시 구조와 인덱싱 전략이 성능을 좌우한다. 또한 "급상승 검색어" 같은 최신성을 반영하기 위해 배치 처리 + 스트리밍 처리를 함께 쓰는 Lambda 아키텍처 패턴이 적합하다는 점도 흥미로웠다. 결국 검색어 자동완성 시스템은 데이터 구조(Trie/B-Tree)와 분산 캐싱 전략, 랭킹 알고리즘의 조합이 핵심이며 이는 검색 품질과 사용자 경험 모두에 직결된다는 것을 배웠다.
