검색어 자동완성 시스템
1. 요구사항 확인
설계에 앞서 다음 사항을 먼저 확인해야 함.
- 사용자 입력이 검색어의 첫 부분에 한정되는가, 중간 부분도 대응하는가
- 몇 개의 자동완성 검색어를 보여줄 것인가
- 자동완성 검색어를 고르는 기준은 무엇인가
- 맞춤법 검사와 자동 수정 기능을 제공하는가
- 어떤 언어를 지원하는가
- 대문자나 특수문자는 어떻게 처리하는가
- 얼마나 많은 사용자를 지원해야 하는가(DAU)
비기능 요구사항
-
빠른 응답 속도
- 페이스북의 검색어 자동완성 시스템 문서에 따르면 응답 속도가 100밀리초 이상이면 사용자가 불편을 느낌
-
연관성
- 출력되는 검색어는 사용자가 입력한 단어와 연관되어야 함
-
정렬
- 계산 결과는 인기도 등의 순위 모델에 따라 정렬되어 있어야 함
-
규모 확장성
- 많은 트래픽을 감당할 수 있도록 확장 가능해야 함
-
고가용성
- 시스템 일부에 장애가 발생하거나 느려지거나 예상치 못한 네트워크 문제가 생겨도 계속 사용 가능해야 함
2. 개략적 규모 추정
현재 데이터가 없으므로 몇 가지 가정을 세우고 시작함.
-
일간 능동 사용자(DAU): 1000만 명
-
한 사용자가 하루에 검색하는 횟수: 평균 10회
-
질의당 평균 입력 데이터 크기: 20바이트
- ASCII 문자 하나는 1바이트
- 질의문은 평균 4개 단어, 단어당 평균 5글자로 가정
-
신규 검색어 비율: 전체의 20%
백엔드 요청 수
검색어를 입력할 때 글자 하나마다 요청이 발생함.
"dinner" 입력
→ search?q=d
→ search?q=di
→ search?q=din
→ search?q=dinn
→ search?q=dinne
→ search?q=dinner따라서 검색 1회당 평균 20건의 요청이 백엔드로 전달됨.
QPS
QPS
= 1000만 × 10회 × 20건 ÷ 86,400초
≈ 24,000
최대 QPS
= 24,000 × 2
= 48,000신규 데이터 크기
하루 질의 데이터
= 1000만 × 10회 × 20바이트
= 2GB
신규 데이터
= 2GB × 20%
= 0.4GB / 일3. 개략적인 설계안
시스템은 크게 두 부분으로 나눌 수 있음.
-
데이터 수집 서비스
- 사용자가 입력한 질의를 실시간으로 수집하는 시스템
- 데이터가 많은 애플리케이션에서 실시간 수집은 바람직하지 않지만, 설계의 출발점으로 일단 둠
-
질의 서비스
- 주어진 질의에 대해 인기 검색어 k개를 정렬해 내놓는 서비스
빈도 테이블
질의문과 사용 빈도를 저장하는 빈도 테이블이 있다고 가정함.
데이터 수집 서비스는 사용자가 입력한 질의문을 저장하면서 사용 빈도를 늘림.
질의 서비스는 빈도가 높은 순으로 상위 k개의 검색어를 SQL 질의문으로 계산하여 보여줌.
사용하는 질의문은 다음과 같음.
SELECT * FROM frequency_table
WHERE query LIKE 'prefix%'
ORDER BY frequency DESC
LIMIT k데이터가 적을 때는 괜찮은 설계안이지만, 데이터가 많아지면 DB가 병목이 됨.
따라서 상세 설계안으로 넘어감.
4. 트라이 자료구조
관계형 DB로 가장 인기 있는 k개의 질의문을 골라내는 방식은 효율적이지 않음.
따라서 트라이 자료구조를 사용하여 응답 시간을 줄임.
트라이(trie)라는 이름은 retrieval의 가운데 부분에서 따온 것임.
구조
- 트리 형태의 자료구조임
- 루트 노드는 빈 문자열을 나타냄
- 각 노드는 글자 하나를 저장함
- 각 노드는 하나의 단어 또는 접두어 문자열을 나타냄
자식 노드의 개수는 지원하는 문자 집합에 따라 달라짐.
영문 소문자만 지원한다면 노드마다 최대 26개의 자식을 가질 수 있고, 한글이나 유니코드 전반을 지원한다면 훨씬 커짐.
따라서 요구사항에서 지원 언어를 먼저 확인해야 함.
빈도 테이블의 정보를 트라이 노드에 저장하면 다음과 같음.
5. 탐색 알고리즘과 시간 복잡도
기호는 다음과 같이 정의함.
p: 접두어의 길이n: 트라이 안에 있는 노드 개수c: 주어진 노드의 자식 노드 개수
단계별 복잡도
-
해당 접두어를 표현하는 노드를 찾음 →
O(p) -
그 노드부터 하위 트리를 탐색하여 모든 유효 노드를 찾음 →
O(c)- 유효 노드는 유효한 검색 문자열을 구성하는 노드를 말함
-
유효 노드를 정렬하여 가장 인기 있는 검색어 k개를 찾음 →
O(c log c)
전체 시간 복잡도는 다음과 같음.
O(p) + O(c) + O(c log c)
= O(p + c log c)최적화
최악의 경우 전체 트라이를 모두 검색해야 하는 상황이 생길 수 있음.
이를 해결하는 방법은 두 가지임.
-
접두어의 최대 길이 제한
- 사용자가 검색창에 긴 질의를 입력하는 일은 드묾
p를 상수로 만들 수 있으므로 1단계가O(1)이 됨
-
각 노드에 인기 검색어 캐시
- 노드마다 상위 k개를 미리 저장해 둠
- 2단계와 3단계를 건너뛸 수 있음
저장 공간이 많이 필요해지지만, 빠른 응답 속도가 더 중요하므로 이 기법들을 사용함.
두 기법을 함께 적용하면 접두어를 찾아 인기 검색어를 얻는 과정의 전체 시간 복잡도가 O(1)이 됨.
접두어 길이 제한 → O(p)를 상수로
노드별 top k 캐시 → 탐색과 정렬 제거
= O(1)여기서 O(1)은 접두어 길이가 상수로 제한된다는 전제 위에서 성립함.
6. 데이터 수집 서비스 상세 설계
앞선 설계안에서는 실시간으로 데이터를 갱신했으나, 매일 수천만 건의 질의가 발생하는 대형 서비스에서는 적합하지 않음.
트라이가 한 번 만들어지면 인기 검색어는 자주 바뀌지 않으므로 자주 갱신할 필요가 없음.
트라이를 만드는 데 쓰이는 데이터는 보통 데이터 분석 서비스나 로깅 서비스로부터 옴.
각 컴포넌트의 역할
-
데이터 분석 로그
- 입력된 질의에 관한 원본 데이터를 보관
-
로그 취합 서버
- 로그를 취합함
- 취합의 실시간성은 서비스 성격에 따라 중요도가 다르므로 확인이 필요함
-
작업 서버
- 주기적으로 비동기 작업을 실행하는 서버 집합
- 트라이 자료구조를 만들고 트라이 DB에 저장하는 역할
-
트라이 캐시
- 트라이 DB의 스냅샷을 주기적으로 떠서 연산 성능을 높임
-
트라이 DB
-
영속성 저장장치로는 두 가지 선택지가 있음.
-
문서 저장소
- 주기적으로 트라이를 직렬화하여 저장
-
키-값 저장소
- 트라이에 보관된 모든 접두어를 해시 테이블의 키로 변환
- 각 노드에 보관된 데이터를 해시 테이블의 값으로 변환
-
-
접두어 "din" → 키
["dinner", "dinosaur", ...] → 값7. 질의 서비스 상세 설계
질의 서비스는 다음 과정으로 이루어짐.
- 검색 질의가 로드밸런서로 전송됨
- 로드밸런서가 API 서버 중 하나로 질의를 보냄
- API 서버가 트라이 캐시에서 데이터를 가져옴
- 캐시 미스가 나면 DB에서 가져와 캐시를 채운 뒤 응답을 구성함
최적화 기법
-
AJAX 요청
- 페이지 전체를 새로 고치지 않고 필요한 데이터만 비동기로 주고받음
- 글자마다 요청이 발생하는 자동완성의 특성상 필수적임
-
브라우저 캐싱
- 자동완성 결과는 짧은 시간 안에 자주 바뀌지 않음
- 응답을 브라우저에 캐시해 두면 같은 접두어를 다시 입력할 때 서버 요청 자체가 발생하지 않음
-
데이터 샘플링
- 모든 질의를 기록하지 않고 일부만 골라 기록함
- 인기 검색어의 순위는 표본만으로도 충분히 파악할 수 있으므로 로그 양과 처리 비용을 크게 줄일 수 있음
8. 트라이 연산
트라이 생성
작업 서버가 담당하며, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용함.
트라이 갱신
두 가지 방법이 있음.
-
주기마다 전체 갱신
- 새로운 트라이를 만들어 기존 트라이를 대체함
-
각 노드를 개별적으로 갱신
- 트라이가 작을 때 고려할 만한 방법임
검색어 삭제
혐오 조장, 폭력성, 성적 불쾌감, 위험 단어 등은 연산 결과에서 제거해야 함.
캐시 앞에 필터 계층을 두고 부적절한 질의어를 걸러내는 방법이 좋음.
트라이 캐시
→ 필터 계층
→ API 서버필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있기 때문임.
9. 규모 확장이 가능한 저장소
트라이가 한 서버에 담기지 않을 만큼 커지면 샤딩이 필요함.
단순한 분할의 한계
첫 글자를 기준으로 나누는 방식은 데이터가 균등하게 분배되지 않음.
a로 시작하는 검색어 → 매우 많음
x, z로 시작하는 검색어 → 매우 적음검색어 대응 샤드 관리자
과거 질의 데이터의 분포를 분석하여, 각 샤드가 비슷한 양의 데이터를 담도록 구간을 나눔.
분포 분석 결과 s로 시작하는 검색어가 많다면
→ s 하나만으로 한 샤드를 구성
u, v, w, x, y, z는 각각 적다면
→ 묶어서 한 샤드로 구성이 매핑 정보, 즉 어떤 검색어가 어느 저장소 서버에 저장되는지를 관리하는 것이 검색어 대응 샤드 관리자임.
10. 최종 정리
검색어 자동완성 시스템의 전체 흐름은 다음과 같음.
수집
→ 데이터 분석 로그
→ 로그 취합 서버
→ 작업 서버
→ 트라이 DB
→ 트라이 캐시
질의
→ 로드밸런서
→ API 서버
→ 트라이 캐시(미스 시 DB)
→ 응답핵심은 다음과 같음.
- 100밀리초 이내 응답이 목표이므로 RDB 질의로는 부족하고 트라이가 필요함
- 접두어 길이 제한과 노드별 top k 캐시를 함께 써야
O(1)에 가까워짐 - 인기 검색어는 자주 바뀌지 않으므로 실시간 갱신 대신 주기적 배치로 처리함
- 부적절한 검색어는 필터 계층에서 걸러야 규칙 변경이 자유로움
- 샤딩은 첫 글자가 아니라 실제 질의 분포를 기준으로 나눠야 균등해짐
