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

대규모 시스템 설계 기초 13장을 요약한 내용입니다.

검색어 자동 완성

autocomplete
typehead
search-as-you-type
incremental search

많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템 설계

1단계: 문제 이해 및 설계 범위 확정

사용자 입력 단어는 자동완성될 검색어의 첫 부분
5개의 자동완성 검색이 표시
5개는 질의 빈도에 따러 정해지는 검색어 인기 순위 기준
맞춤법 검사나 자동수정은 미지원
질의는 영어 + 다국어
모든 질의는 영어 소문자
일간 능동 사융자(DAU) 천만(10million)

요구사항

빠른 응답 속도

페이스북 검색어 자동완성 시스템에 관한 문서를 보면 시스템 응답속도는 100밀리초 이내여야 한다. 그렇지 않으면 시스템이 불편해진다.

연관성

자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.

정렬

시스템의 계산 결과는 인기도, 등의 순위 모델에 의해 정렬

규모 확장성

시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 한다.

고가용성

시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능해야 한다.

개략적 규모 추정

일간 능동 사용자(DAU)는 천만 명으로 가정
평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정
질의할 떄마다 평균적으로 20바이트의 데이터를 입력한다고 가정
- 문자 인코딩 방법으로 ASCII를 사용 (1문자=1byte)
- 질의문은 평균적으로 4개 단어로 이루어진다.(각 단어는 평균적으로 다섯 글자)
- 질의당 평균 4x5=20 byte
검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다.
- 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달
- 검색창에 dinner라고 입력 시 예시
  search?q=d search?q=di search?q=din search?q=dinn search?q=dinne search?q=dinner
대략 초당 24,000건의 질의(QPS) 발생 (=10,000,000사용자 x 10질의/일 x 20자/24시간/3600초)
최대 QPS = QPS x 2 = 대략 48,000
질의 가운데 20% 정도는 신규 검색어라고 가정
- 대략 0.4GB (=10,000,000사용자 x 10질의/일 x 20자 x 20%)

2단계: 개략적 설계안

개략적으로 시스템은 두 부분으로 나뉜다.

데이터 수집 서비스

사용자가 입력한 질의를 실시간으로 수집하는 시스템
실시간은 데이터가 많은 애플리케이션에 바람직하지 않지만 설계안의 출발점으로 적합

질의 서비스

주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스

데이터 수집 서비스

질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정해 보자.

질의 서비스

query: 질의문을 저장하는 필드
frequency: 질의문이 사용된 빈도를 저장하는 필드

"top 5"는 빈도 테이블에 기록된 수치를 사용해 계산한다고 가정

데이터 양이 적을 때는 SQL 질의문을 사용해 계산할 수 있지만, 데이터가 많아지면 DB 병목이 될 수 있다.

SELECT *
FROM frequency_table
WHERE query Like 'prefix%'
ORDER BY frequency DESC
LIMIT 5

3단계: 상세 설계

트라이 자료구조

관계형 데이터베이스를 이용해 가장 인기 있는 질의문을 골라내는 방안은 효율적이지 않다.

이 문제를 트라이(trie, 접두어 트리, prefix tree)를 사용해 해결할 수 있다.

트라이는 문자열들을 간략하게 저장할 수 있는 자료구조이다.

retrieval. 문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조

트라이 자료구조의 핵심 아이디어

트라이는 트리 형태의 자료구조
루트 노드는 빈 문자열
각 노드는 글자 하나를 저장하며, 26개(다음에 등잘할 수 있는 모든 글자 개수)의 자식 노드를 가질 수 있음
각 트리 노드는 하나의 단어, 또는 접두어 문자열을 나타냄

기본 트라이 자료구조는 노드에 문자들을 저장

이용 빈도에 따라 정렬된 결과를 내놓기 위해 노드에 빈드 정보까지 저장

검색어 자동완성 구현하기

알고리즘에 사용되는 용어

p: 접두어
n: 트라이 안에 있는 노드 개수
c: 주어진 노드의 자식 노드 개수

가장 많이 사용된 k개를 찾는 방법

해당 접두어를 표현하는 노드 찾기. O(p)
해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드 찾기. O(c)
- 유효한 검색 문자열을 구성하는 노드가 유효 노드
유효 노드들을 정렬하여 가장 인기 있는 검색어 k개 찾기. O(clogc)

k=2, 검색창에 'be' 입력했을 경우 알고리즘 동작

(1) 접두어 노드 'be' 찾기
(2) 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드 찾기
- 'beer', 'best', 'bet'
(3) 유효 노드를 정렬하여 2개만 골라내기

이 알고리즘의 시간 복잡도는 각 단계에 소요된 시간의 합이다.

O(p) + O(c) + O(clogc)
최악의 경우에는 k개의 결과를 얻기 위해 전체 트라이를 다 검색해야 하는 일이 생길 수 있다.
이 문제의 해결 방법으로 두 가지가 존재한다.
- 접두어의 최대 길이 제한
- 각 노드에 인기 검색어를 캐시

접두어의 최대 길이 제한

사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다.

p값은 작은 정숫값이라고 가정해도 안전하다.
검색어의 최대 길이를 제한할 수 있다면 접두어 노드 찾는 단계에서 시간 복잡도를 O(p) 에서 O(1)로 바뀔 것이다.

각 노드에 인기 검색어를 캐시

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

각 노드에 인기 질의어를 캐시하면 'top 5' 검색어 질의 시간 복잡도를 상당히 낮출 수 있다.
단, 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다.
빠른 응답속도가 중요할 경우 이 정도의 저장공간을 희생할 만한 가치가 있다.

각 노드에 가장 인기 있는 검색어 다섯 가지를 저장한 예시이다.

두 가지의 최적화 기법(접두어의 최대 길이 제한, 각 노드에 인기 검색어를 캐시)을 적용하여 시간 복잡도를 낮출 수 있었다.

접두어 노드를 찾는 시간 복잡도는 O(1)
최고 인기 검색어 5개를 찾는 일의의 시간 복잡도는 O(1)

데이터 수집 서비스

사용자의 타이밍마다 실시간으로 데이터를 수정하는 방법은 실용적이지 않다.

매일 수천만 건의 질의가 입력되는데 그때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려질 것.
트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것이니 자주 갱신할 필요가 없다.

트위터 같은 실시간 애플리케이션이라면 제안되는 검색어를 항상 신선하게 유지할 필요가 있겠지만, 구글 검색 같은 애플리케이션이라면 자주 바꿔줄 필요는 없다.

트라이를 만드는 데 쓰는 데이터는 보통 데이터 분석 서비스나 로깅 서비스로부터 올 것이므로 용례가 달라지더라도 데이터 수집 서비스의 토대는 바뀌지 않을 것이다.

데이터 분석 서비스 로그

검색창에 입력된 질의에 관한 원본 데이터가 보관
새로운 데이터가 추가될 뿐 수정은 이루어지지 않고, 로그 데이터에는 인덱스를 걸지 않음

로그 취합 서버

방대하고 형식이 제각각인 데이터를 잘 취합하여 시스템이 잘 소비할 수 있도록 해야 한다.
취합 방식은 실시간으로 결과를 빠르게 보여줘야 한다면 데이터 취합 주기를 짧게 가져갈 필요가 있다.
하지만, 대부분은 일주일에 한 번 정도로 로그를 취합해도 충분하다.

취합된 데이터

매주 취합한 데이터의 사례
time: 해당 주가 시간한 날짜
frequency: 해당 질의가 해당 주에 사용된 횟수의 합

작업 서버

주기적으로 비동기 작업을 실행하는 서버 집합
트라이 자료구조를 만들고 트라이 DB에 저장하는 역할을 담당

트라이 캐시

분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실
매주 트라이 DB의 스냅샷을 떠서 갱신

트라이 데이터베이스

지속성 저장소
트라이 DB로 사용할 수 있는 선택지
- 문서 저장소:
  - 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 DB에 저장
  - MongoDB 같은 문서 저장소 활용
- 키-값 저장소:
  - 트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능
  - 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
  - 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

트라이를 해시 테이블로 대응시키는 예시

각 트라이 노드는 하나의 <키, 값> 쌍으로 변환

질의 서비스

비효율적인 부분을 개선한 설계안

(1) 검색 질의가 로드밸런서로 전송
(2) 로드밸런서는 해당 질의를 API 서버로 전송
(3) API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성
(4) 데이터가 트래이 캐시에 없는 경우 데이터를 DB에서 가져와 캐시에 채움

질의 서비스는 빨라야 하므로 추가적인 최적화 방안을 생각해볼 수 있다. AJAX 요청(request)

웹 애플리케이션의 경우 보통 AJAX 요청으로 자동완성 검색어 목록을 가져온다.
요청을 보내고 받기 위해 페이지를 새로고침 할 필요가 없는 장점이 있다.

브라우저 캐싱(browser caching)

대부분 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않는다.
제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있다.
구글 검색 엔진의 캐시 메커니즘

데이터 샘플링(data sampling)

모든 질의 결과를 로깅하도록 하면 CPU 자원과 저장공간을 엄청나게 소진하게 된다.
데이터 샘플링 기법은 위 상황에 유용하다. (N개의 요청 가운데 1개만 로깅하는 방식)

트라이 연산

검색어 자동완성 시스템의 핵심 컴포넌트이다.

트라이 생성

생성은 작업 서버가 담당

데이터 분석 서비스의 로그나 DB로부터 취합된 데이터를 이용

트라이 갱신

트라이 갱신에는 두 가지 방법이 존재

(1) 매주 한 번 갱신하는 방법

새로운 트라이를 만든 후 기존 트라이를 대체

(2) 트라이의 각 노드를 개별적으로 갱신하는 방법

트라이 노드 갱신 시 그 모든 상위 노드도 갱신되어야 한다.
트라이가 작을 경우 고려해볼 수 있지만, 성능이 좋지 않다.

검색어 삭제

여러 가지로 위험한 질의어를 자동완성 결과에서 제거해야 한다.

트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 할 수 있다.
필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다.
DB에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행

규모 확장이 가능한 저장소

영어만 지원하면 되므로 간단하게 첫 글자 기준으로 샤딩하는 방법을 적용

검색어 보관을 위해

두 대의 서버가 필요할 경우
- 'a'부터 'm'까지 글자로 시작하는 검색어는 첫 번째 서버에 저장하고, 나머지는 두 번째 서버에 저장
세 대의 서버가 필요할 경우
- 'a'부터 'i'까지는 첫 번째 서버에, 'j'부터 'r'까지는 두 번째 서버에, 나머지는 세 번째 서버에 저장

이 방법을 사용하는 경우에는 사용 가능한 서버는 최대 26개로 제한(영어 알파벳 개수)

이 이상으로 서버 대수를 늘리려면 샤딩을 계층적으로 해야 한다.
'a'로 시작하는 검색어를 네 대의 서버에 나눠서 보관하고 싶다면, ‘aa’~~’ag’, ‘ah’~~’an’, ‘ao’~’au’, 나머지로 보관
’c’로 시작하는 단어가 ‘x’로 시작하는 단어보다 많다는 것을 감안하면 데이터를 각 서버에 균등하게 배분하기 불가능

위 문제 해결을 위해 과거 질의 데이터의 패턴을 분석하여 샤딩하는 방법을 제안