13장 검색어 자동완성 시스템

필요한 검색어 자동완성 시스템

요구사항

개략적 규모 추정

평균 1사람당 매일 10건 검색한다고 가정하고, 20바이트의 데이터를 입력한다고 가정한다.

검색어가 평균적으로 4개의 단어로 이루어진다고 가정하고, 각 단어는 5글자로 구성된다고 했을 때, 20바이트의 데이터를 입력한다고 한다.

검색창에 글자를 입력할 때마다 백엔드 api 호출한다면, 대략 초당 24,000건의 질의가 발생한다.

데이터 수집 서비스
- 사용자가 입력한 질의를 실시간으로 수집하는 시스템
- 데이터가 많은 애플리케이션에는 바람직하지 않지만 설계안의 출발점으로는 괜찮을 것이다.
질의 서비스
- 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스
- query, frequency db에서 frequency 순으로 정렬

데이터 양이 적을 때는 나쁘지 않지만, 데이터가 아주 많아지면 병목이 될 수 있다.

트라이 자료구조

트라이 자료구조를 사용했을 때의 시간 복잡도는 다음과 같다.

p: 접두어의 길이

n : 트라이 안에 있는 노드 개수

c : 주어진 노드의 자식 노드 개수

접두어 검색 : O(p)

모든 유효 노드 검색 : O(c)

유효 노드 중에서 가장 인기 있는 검색어 k 찾기 : O(clogc)

그러나, 최악의 경우에는 k개의 결과를 얻으려고 전체 트라이를 다 검색해야 하는 일이 생길 수 있다.

최적화 방안 생각하기

1. 접두어 최대 길이 제한

긴 검색어를 입력하는 일은 거의 없기 때문에 접두어의 최대 길이를 제한할 수 있다.

p값을 정수값(50)이라고 가정한다면, O(p) → O(1) 로 최적화할 수 있다.

2. 노드에 인기 검색어 캐시

각 노드의 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있다.

물론 저장공간을 희생해야 한다. ⇒ O(1)

데이터 수집 서비스

타이핑할 때 마다 데이터를 수정하면, 질의 서비스는 심각하게 느려질 것이다.

인기 검색어 순위는 그다지 자주 바뀌지 않으므로 자주 갱신할 필요가 없다.

데이터 분석 서비스 로그 : 검색창에 입력된 질의에 관한 원본 데이터가 보관된다. 새로운 데이터가 추가되기만 한다.
로그 취합 서버 : 데이터를 취합하여 시스템이 쉽게 소비할 수 있도록, 일주일 주기로 취합하도록 가정한다. (취합된 데이터는 query, time frequency 형태)
작업 서버 : 주기적으로 비동기적 작업을 실행하는 서버 집합, 트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 한다.
트라이 캐시 : 분산 캐시 시스템으로 메모리에 유지하여 읽기 연산 성능을 높이는 구실을 한다.
트라이 데이터베이스 : 지속성 저장소이다.
- 문서 저장소 : 새 트라이를 매주 만들고 주기적으로 트라이를 직렬화하여 데이터베이스 몽고디비에 저장한다.
- 키-값 저장소: 접두어를 해시 테이블 키로 변환하여 해시 테이블 형태로 변환가능하다.

질의 서비스

트라이 연산

트라이 생성 : 작업 서버 담당, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용한다.

트라이 갱신

검색어 삭제 : 혐오 표현이거나 할 경우 제거해야한다. 필터 계층을 두고 필터 규칙에 따라서 결과를 자유롭게 변경한다.

저장소 규모 확장 : 첫 글자를 기준으로 샤딩, a-m까지 첫 서버에 저장하고, 나머지는 두번째 서버에 저장하는 방식

그러면 최대 26개의 서버 사용 가능하지만, x로 시작하는 데이터는 a로 시작하는 데이터의 개수보다 현져하게 적으므로 데이터를 균등하게 배분하기는 불가능할 것이다.

데이터를 균등하게 배분하기 위해서는 검색어 대응 샤드 관리자를 두어, 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리하게 할 수 있다.

* 가상 면접을 통한 대규모 시스템 설계 13장을 읽고 정리한 내용입니다.