가정
- 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분으로 한정
- 5개의 자동완성 검색어가 표시
- 질의 빈도에 따라 정해지는 검색어 인기 순위로 선정
- 맞춤법 검사와 자동수정은 지원 안 함
- 영어를 기본으로 다국어 지원도 가능
- DAU는 10M
요구사항
- 빠른 응답 속도
- 페이스북 검색어 자동완성 시스템에 관한 문서를 보면 응답속도가 100ms 이하여야
- 연관성
- 사용자가 입력한 단어와 연관된 단어가 출력돼야
- 정렬
- 규모 확장성
- 많은 트래픽을 감당할 수 있도록 확장 가능해야
- 고가용성
- 시스템 일부에 장애가 발생하거나, 예상치 못한 네트워크 문제가 생겨도 계속 사용 가능해야
개략적 규모 추정
- DAU 10M, 한 사용자가 매일 10건의 검색을 수행한다고 가정
- 질의할 때 평균 20byte의 데이터를 입력한다고 가정
- ASCII 기준으로 1문자 = 1byte
- 평균 4단어, 한 단어를 5 글자로 가정
- 검색차에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보냄
- 1회 검색당 평균 20건의 요청이 백엔드로 전달
- 초당 24K의 QPS
- 질의의 20%는 신규 검색어로 가정
- 매일 0.4GB의 신규 데이터가 시스템에 추가
개략적인 설계
- 데이터 수집 서비스(data gathering service)
- 질의 서비스(query service)
- 주어진 질의에 다섯 개의 인기 검색어를 정렬해 제공
데이터 수집 서비스
- 질의문과 사용빈도를 저장하는 빈도 테이블(frequency table)이 있다고 가정
- 처음엔 비어 있음
- 새 검색어가 들어오면 (질의, 빈도) 쌍이 추가, 동일 검색어가 또 들어오면 빈도가 증가
질의 서비스
- RDB 기준으로 생각했을 때, 주어진 검색어에 대해
WHERE query LIKE 'prefix%'와 같은 형태를 생각해볼 수 있음
- 데이터가 많아지면 데이터베이스 병목이 될 수 있긴 함
폴링
- 클라이언트가 주기적으로 서버에 새 메시지가 있느냐고 물어봄
- 폴링 비용은 폴링을 자주할 수록 올라감
- 답해줄 메시지가 없는 경우, 서버 자원이 낭비
상세 설계
트라이(Trie) 자료구조
- RDB에서 인기 있는 5개의 질의를 골라내는 방안이 비효율적
- 트라이를 적용
- 트리 형태
- 루트 노드는 빈 문자열을 의미
- 각 노드는 글자 하나를 저장하며, 26개(알파벳 기준)의 자식 노드를 가질 수 있음
- 각 트리 노드는 하나의 단어 또는 접두어 문자열(prefix string)
- 검색어 빈도 정보도 각 트라이 노드에 같이 저장
- 접두어 길이를 $p$, 트라이 노드 개수를 $n$, 주어진 노드의 자식 노드 개수를 $c$라 할 때, 가장 많이 사용된 질의어 $k$개를 찾는 방법
- 해당 접두어를 표현하는 노드를 $O(p)$로 탐색
- 해당 노드부터 시작하는 하위 트리를 탐색해 모든 유효 노드를 찾음
- 유효한 검색 문자열을 구성하는 노드가 유효 노드
- $O(C)$
- 유효 노드를 정렬해 가장 인기 있는 검색어 $k$개를 찾음
- 최악의 경우 전체 트라이를 다 검색해야 할 수도 있음
- 접두어의 최대 길이를 제한
- 사용자가 검색창에 긴 검색어를 입력하는 일은 드물기에 $p$를 작은 정수로 가정해도 안전
- 이 경우, 접두어 노드를 찾는 단계가 $O(p)$ 에서 $O(1)$ 로 단축
- 각 노드에 인기 검색어를 캐시
- 자동완성 제안은 5 ~ 10개 정도면 충분하므로 $k$ 는 작은 값
- 각 노드에 질의어를 저장할 공간이 더 많이 필요하지만, 응답속도가 빨라짐
- 최고 인기 검색어를 찾는 질의의 시간 복잡도가 $O(1)$
데이터 수집 서비스
- 사용자가 검색창에 타이핑을 할 때마다 데이터가 실시간으로 수정되는 것은 비효율적
- 매일 수천만건의 질의에 대해 트라이를 갱신해야 하므로 질의 서비스가 심각하게 느려짐
- 트라이가 만들어지고 나면 인기 검색어가 자주 바뀌지 않을 것이므로 자주 갱신할 필요가 없음
- 실시간 애플리케이션이라면 제안되는 검색어를 최신 트렌드에 맞게 갱신해야 겠으나 구글 검색 같은 경우 그럴 필요는 없음
- 로깅 서비스(logging service)에서 착안
- 데이터 분석 서비스 로그
- 검색창에 입력된 질의에 관한 원본 데이터 보관
- 데이터가 추가될 뿐 수정이나 인덱스는 없음
- 로그 취합 서버
- 데이터 분석 서비스에서 나오는 데이터를 잘 취합(aggregation)해야 함
- 서비스의 종류에 따라 취합 주기를 다르게 가져감
- 취합된 데이터
- 로그 취합 서버에서 취합한 데이터가 작업 서버로 전달
- 작업 서버
- 주기적으로 비동기적 작업을 실행하는 서버 집합
- 트라이를 만들고 이를 DB에 저장하는 역할
- 트라이 캐시
- 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지해 읽기 성능을 높임
- 특정 주기로 스냅샷을 떠서 갱신
- 트라이 DB
- 지속성 저장소
- 선택 후보 DB
- 문서 저장소
- 새 트라이를 매주 만든다면, 주기적으로 트라이를 직렬화해 DB에 저장
- e.g. MongoDB
- 키-값 저장소
- 트라이를 다음 로직으로 해시 테이블로 변환
- 트라이에 보관된 모든 접두어를 해시 테이블 키로
- 노드에 보관된 모든 데이터를 해시 테이블 값으로
질의 서비스
- 동작 과정
- 검색 질의가 LB로 전송
- API 서버는 트라이 캐시에서 데이터를 가져와 자동완성 검색어 제안 응답 구성
- 캐시에 데이터가 없는 경우, DB에서 데이터를 가져와 캐시를 채움
- 캐시 미스는 캐시 서버의 메모리 부족, 캐시 서버 장애 등에서 발생 가능
- 최적화 방안
- AJAX 요청
- AJAX로 자동완성 검색어 목록을 가져올 경우, 요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없음
- 브라우저 캐싱(browser caching)
- 자동완성 검색어 제안 결과가 짧은 시간에 자주 바뀌지 않으므로, 제안된 검색어들을 브라우저 캐시에 넣어 활용할 수 있음
- 데이터 샘플링(data sampling)
- 데이터 샘플링 기법으로 N개의 요청 가운데 1개만 로깅해 CPU와 디스크 자원 절약
트라이 연산
- 트라이 생성
- 작업 서버가 담당하며, 데이터 분석 서비스의 로그나 DB에 취합된 데이터 이용
- 트라이 갱신
- 매주 한 번 갱신
- 트라이 각 노드를 개별 갱신
- 성능이 좋지 않으나, 트라이가 작을 때 고려해볼만 함
- 노드를 갱신할 때, 그 모든 상위 노드도 갱신해야 함
- 상위 노드에 인기 검색어 질의 결과가 보관되기 때문
- 검색어 삭제
- 문제가 될 수 있는 질의이럴 자동완성 결과에서 제거
- 트라이 캐시 앞에 필터(filter) 계층을 두고, 부적절한 질의어는 반환되지 않도록 제한
- 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다는 장점
- DB에서 해당 검색어를 삭제하는 것은 다음 업데이트 사이클에 비동기적으로 진행
저장소 규모 확장
- 간단하게 첫 글자를 기준으로 샤딩(sharding)할 수 있음
- 알파벳이 26자이므로, 서버를 26대 이상으로 늘리면 샤딩을 계층적으로 해야함
- aa ~ ag를 한 서버, ah ~ an을 한 서버...
- c로 시작하는 단어가 x로 시작하는 단어보다 많다는 것을 감안하면 균등하게 데이터가 배분되지 않음
- 과거 질의 데이터의 패턴을 분석해 샤딩
- 검색어 대응 샤드 관리자(shard map manager)는 어떤 검색어가 어떤 저장소 서버에 저장되는지 정보를 관리
- s로 시작하는 검색어의 양이 u ~ z로 시작하는 검색어를 전부 합친 것과 비슷하다면, s에 대한 샤드 하나와 u ~ z까지의 검색어를 위한 샤드 하나를 두어도 충분
추가로 고려할 부분
- 다국어 지원
- 국가별로 인기 검색어 순위가 다르면
- 국가별로 트라이를 구성하고, 트라이를 CDN에 저장해 응답속도를 높이는 방안
- 실시간으로 변화하는 검색어의 추이 반영
- 위 설계안으로는 부적합
- 작업 서버가 특정 주기로 동작해 적절하게 트라이를 갱신하지 못함
- 고려해볼 아이디어
- 샤딩을 통해 작업 대상 데이터 양을 줄임
- 순위 모델을 바꿔 최근 검색어에 높은 가중치
- 데이터가 스트림 형태로 올 수 있다는 점, 즉, 한 번에 모든 데이터를 동시에 사용할 수 없을 가능성을 고려
- 카프카 등 스트림 프로세싱에 적합한 시스템이 있어야 함