검색어 자동완성 시스템
요구 사항
•
빠른 응답 속도 : 100ms 이하
•
연관성
•
정렬 : 인기도 같은 순위 모델에 따라 정렬
•
규모 확장성, 고가용성
규모 추청
Given
•
DAU = 10,000,000명
•
사용자당 일일 검색량 = 10 검색
•
질의
◦
검색 한 번 당 평균 데이터량 = 20B
◦
문자 인코딩 방식 = ASCII(1문자 = 1B)
◦
한 단어 = 5글자, 한 번 검색 = 4단어 = 20바이트
•
글자 입력마다 요청 전송 = 검색당 20회 질의
•
질의 중 20%는 신규 검색어
Derived
•
초당 질의수(QPS) = 10,000,000명 x 10 검색 x 20 글자 / 1 하루
= 2 \times 10^{9} \div (24 \times 3600) \approx 초당 24,000 질의
= 2 \times 10^{9} \div (24 \times 3600) \approx 초당 24,000 질의
•
최대 QPS = QPS x 2 = 48,000
•
신규 검색 바이트 = 24,000 QPS x 20% = 4.8KB/sec \approx 0.4GB/day
개략적인 설계안
•
데이터 수집 서비스 : 사용자의 입력을 수집해 빈도 테이블을 갱신한다.
•
질의 서비스 : 빈도 테이블을 살펴 자동완성 검색어를 반환한다.
SELECT * FROM frequency_table
WHERE query LIKE `prefix%`
ORDER BY frequency DESC LIMIT 5상세 설계
트라이 자료구조
RDBMS 대신 trie(prefix tree)를 사용하여 검색 속도를 향상시킬 것이다.
정의
•
p : 접두어의 길이 (즉, tree의 depth)
•
n : 노드 개수
•
c : 주어진 노드의 자식 노드 수
자동완성 검색어 추출
•
해당 접두어로 트리를 따라간다. O(p)
•
하위 트리를 탐색해 유효 노드(검색 문자열)를 찾는다. O(c)
•
유효 노드를 정렬해 인기 있는 검색어 k개를 찾는다. O(c \cdot \log{c})
한계 극복
k개의 결과를 얻기 위해 트리 전체를 탐색해야 할 수도 있기 때문에
•
접두어의 최대 길이를 제한하고
•
인기 검색어를 캐싱한다.
◦
적절한 노드에 하위 트리의 인기 검색어를 캐싱할 수 있다.
◦
공간이 많이 필요하지만 응답속도는 매우 빠르다.
데이터 수집 서비스
질의마다 매번 트라이를 갱신하기에는 비용이 많이 든다. 이 방법보다는 질의를 로그로 남기고 로그를 주기적으로 분석해 트라이를 갱신하는 방법이 효과적이다.
•
데이터 분석 서비스 로그 : 질의마다 (질의, 시간) 데이터를 로그로 저장한다.
•
로그 취합 서버 : 로그를 주기적으로 취합한다. 10분에서 일주일까지 비즈니스에 따라 상이하다.
•
취합 데이터 : 로그를 일주일마다 취합해 (질의, 주차, 빈도) 테이블을 만든다.
•
트라이 캐시 : 분단 캐시 시스템으로 매주 trie DB의 스냅샷을 떠 갱신한다.
•
트라이 데이터베이스
◦
Document : MongoDB 같이 트라이를 직렬화해 저장
◦
Key-Value : Redis 같이 해시 테이블 형태로 변환해 저장
질의 최적화 방안
•
AJAX req : 페이지를 새로고침하고 필요한 데이터만 벡엔드에서 가져온다.
•
브라우저 캐싱 : 자동완성 검색어 제안은 실시간으로 바뀌지 않기 때문에 브라우저에 캐싱한다.
◦
cache-control: private, max-age=3600
◦
private : 공용 캐시에 저장해서는 안된다.
◦
max-age : 최대 저장 시간, 단위는 초이다.
•
데이터 샘플링 : N 개의 요청 중 1개만 로깅해 전체 용량을 줄인다.
트라이 연산
트라이 갱신
•
매주 한 번 갱신, 새로운 트라이를 만들어 기존의 것을 대체한다.
•
노드를 개별적으로 갱신, 느리다.
검색어 삭제
•
필터 레이어를 둔다.
저장소 규모 확장
•
샤딩할 수 있다. (a~m과 j~r)은 다른 서버에 저장