13. 검색어 자동 완성 시스템
- 검색어 자동 완성: 웹사이트 검색창에 단어 입력 시 입력 중인 글자에 맞는 검색어가 자동으로 완성되어 표시되는 기능
- autocomplete, typeahead, search-as-you-type, incremental search
- 가장 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템 설계
1단계. 문제 이해 및 설계 범위 확정
1.질문을 통한 요구사항 확인
- 입력 단어는 자동완성될 검색어의 첫 부분으로 한정
- 5 개의 자동 완성 검색어 표시
- 자동완성 검색어 5개를 고르는 기준: 질의 빈도에 따라 정해지는 검색어 인기 순위를 기준
- 맞춤법 검사나 자동수정기능은 지원 X
- 질의는 영어. 여유가 있는 경우 다국어 지원 고려
- 모든 질의는 여어 소문자로 이루어지며, 대문자나 특수 문자는 처리하지 않음
2. 요구사항
2-1. 빠른 응답 속도
- 사용자가 검색어를 입력함에따라 자동 완성 검색어도 빠르게 표시되어야 함
- 페이스북 검색어 자동 완성 시스템에 관한 문서: 시스템 응답 속도는 100ms 이내여야 함
2-2. 연관성
- 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 함
2-3. 정렬
- 시스템 계산 결과는 인기도 등의 순위 모델(ranking model)에 의해 정렬되어 있어야 함
2-4. 규모 확장성
- 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 함
2-5. 고가용성
- 시스템은 계속 사용 가능해야 함
2. 개략적 규모 추정
- 일간 능동 사용자(DAU): 천만 명 가정
- 사용자당 일간 검색 수행 횟수: 10건
- 질의 데이터: 평균적으로 20바이트의 데이터 입력 가정
- 문자 인코딩 방법으로는 아스키 사용 가정(1문자=1바이트)
- 질의문은 평균적으로 4개 단어로 이루어진다고 가정, 각 단어는 평균적으로 다섯 글자로 구성된다고 가정
- 질의당 평균 4 단어 * 5글자 = 20바이트
2단계. 개략적 설계안 제시 및 동의 구하기
1. 개략적인 시스템 분류
1-1. 데이터 수집 서비스(data gathering service)
- 사용자가 입력한 질의를 실시간으로 수집하는 시스템
1-2. 질의 서비스(query service)
- 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스
3단계. 상세 설계
1. 트라이(trie) 자료 구조
1-1. 트라이
- 탐색 트리의 일종으로
- 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않음
- 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의
트라이 자료 구조의 핵심 아이디어
(root)
└─ t
└─ r
│ └─ e ← tre
│
└─ o ← to- 트리 형태의 자료구조
- 루트 노드는 빈 문자열을 나타냄
- 각 노드는 글자(character) 하나를 저장, 최대 26개의 자식 노드를 가질 수 있음
트라이로 검색어 자동 완성 구현
- 가장 많이 사용된 질의어 K 찾기
- 해당 접두어를 표현하는 노드를 찾는다. 시간 복잡도는 O(p)
- 하위 트리를 탐색하여 모든 유효 노드를 찾는다.
- 유효한 검색 문자열을 구성하는 노드가 유효 노드. 시간 복잡도는 O(c)
- 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clog c)
- 알고리즘의 시간 복잡도
= 각 단계에 소요된 시간
= O(p) + O(c) + O(clog c)
최적화 방안
- 접두어의 최대 길이 제한(
O(p)에서 p 값 감소) - 각 노드에 인기 검색어를 캐시
- 각 노드에 k 개의 인기 검색어 저장 시, 전체 트라이 검색 방지
- 각 단계의 시간 복잡도가 O(1)로 변경 > 최고 인기 검색어 k개를 찾는 전체 알고리즘의 복잡도도 O(1)로 변경
2. 데이터 수집 서비스
2-1. 종전 방법의 문제점: 사용자 타이핑 시 실시간 데이터 수정
- 실시간 트라이 갱신 시 질의 서비스의 속도가 심각하게 느려질 것
- 인기 검색어는 그다지 자주 바뀌지 않기 때문에 트라이를 자주 갱신할 필요가 없음
flowchart LR
A[데이터 분석 서비스 로그]--> B[로그 취합 서버] -->C[취합된 데이터]
C--> D[작업 서버] --매주 갱신--> E[트라이 데이터 베이스] --매주 DB 상태 스냅샷-->F[트라이 케시]2-2. 새로운 방식
1) 데이터 분석 서비스 로그
| query | time |
|---|---|
| tree | 2025-11-17 22:01:01 |
| try | 2025-11-17 22:01:05 |
| try | 2025-11-17 22:01:08 |
| toy | 2025-11-17 22:02:01 |
2) 로그 취합 서버
- 데이터 취합 실시간성의 중요성에 따른 분류
- 실시간 앱: 데이터 취합 주기를 짧게 가져갈 필요가 있을 수 있음
- 대부분: 일주일에 한번 정도 로그 취합
3) 취합된 데이터
-
time 필드: 해당 주의 시작 날짜
-
frequency 필드: 해당 질의가 해당 주에 사용된 횟수의 합
query time frequency tree 2025-11-03 12000 tree 2025-11-10 15000 tree 2025-11-17 9000 toy 2025-11-03 8500 toy 2025-11-17 6256
4) 작업 서버
- 주기적으로 비동기적 작업을 실행하는 서버 집합
- 트라이 자료구조를 만들고 트라이 DB에 저장하는 역할 담당
5) 트라이 캐시
- 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실
- 매주 트라이 DB의 스냅샷을 떠서 갱신
6) 트라이 DB
- 지속성 저장소
- 트라이 DB의 형태
- 문서 저장소(document store): 주기적으로 트라이를 직렬화하여 DB에 저장
- 키-값 저장소: 해시 테이블 형태로 변환
3. 질의 서비스
3-1. 비효율성을 개선한 설계안
flowchart LR
A[사용자 단말] --> B[로드 밸런서] -->C[API 서버] --> D[트라이캐시] -->E[트라이 DB]- query가 로드밸런서로 전송됨
- 로드밸런서는 query를 API 서버로 전송
- API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동 ㅗ안성 검색어 제안 응답 구성
- 데이터가 트라이 캐시에 없는 경우 데이터를 DB에서 가져와 캐시에 채움
3-2. 질의 서비스 최적화 방안
AJAX 요청
브라우저 캐싱
- 대부분의 앱에서 자동 완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않음
- 따라서 제안된 검색어들을 브라우저 캐시에 넣어두어 후속 질의 결과는 캐시에서 바로 가져갈 수 있게 함
데이터 샘플링
- N개 요청 가운데 1개만 로깅
4. 트라이 연산
4-1. 트라이 생성
- 데이터 분석 서비스의 로그나, DB로부터 취합된 데이터를 이용하여, 작업 서버가 담당
4-2. 트라이 갱신 방법
- 매주 한 번 갱신. 새로운 트라이를 만든 후 기존 트라이를 대체
- 트라이의 각 노드를 개별적으로 갱신
- 일반적으로 성능이 좋지 않지만, 트라이를 작을 때는 고려해볼만 함
4-3. 검색어 삭제
- 트라이 캐시 앞에 필터 계층(filter layer)을 두고 부적절한 질의어가 반환되지 않도록 함
5. 규모 확장이 가능한 저장소
- 첫 글자를 기준으로 샤딩
- 서버를 26대 이상으로 늘리려면 계층적 샤딩 적용
- 데이터의 균등 분배가 불가능함
- 과거 질의 데이터의 패턴을 분석하여 샤딩
- 검색어 대응 샤드 관리자(shard map manager): 어떤 검색어가 어느 저장소 서버에 저장되는 지에 대한 정보 관리
4단계. 마무리
다국어 지원이 가능하도록 시스템 확장
- 트라이에 유니코드 데이터 저장
국가별로 인기 검색어 순위가 다른 경우
- 국가별로 다른 트라이 사용
- 트라이를 CDN에 저장하여 응답 속도를 높일 수 있음
실시간 검색어 자동완성 시스템 구축 시 고려할 점
- 샤딩을 통한 작업 대상 데이터 양 줄이기
- 순위 모델을 변경하여 최근 검색어에 높은 가중치 주기
- 데이터가 스트림 형태로 올 수 있다는 점을 고려(스트림 프로세싱에 필요한 시스템)
- 아파치 하둡 맵리듀스
- 아파치 스파크 스트리밍
- 아파치 스톰
- 아파치 카프카 등
