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

 

웹 사이트 검색 창에 단어를 입력하다 보면 입력중인 글자에 맞는 검색어가 자동을 완성된다.

이런 기능을 보통 검색어 자동완성이라고 부른다.

1단계 설계 범위 확정

요구사항

• 빠른 응답 속도: 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시되어야 한다.
• 연관성: 자동완성 되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.
• 정렬: 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.
• 규모 확장성: 시스템은 많은 트랙픽을 감당할 수 있도록 확장 가능해야 한다.
• 고가용성: 시스템의 일부 장애가 발생해도 시스템은 계속 사용 가능해야한다.

 

개략적 규모측정

• 일간 능동 사용자(DAU)는 천 만명으로 가정
• 평균적으로 한 사용자는 매일 10건의 검색을 수행
• 질의할 떄마다 평균적으로 20바이트 데이터를 입력한다고 가정
  • 문자 인코딩 방법으로 ASCII를 사용하면, 1문자 = 1바이트 이다.
  • 질의문은 평균적으로 4개 단어로 이루어진다. 각 단어는 평균적으로 다섯 글자로 구성
  • 따라서, 질의마다 평균 4 * 5 = 20바이트 이다.
• 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다.
  • 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 사용자 * 10 질의 / 일 * 20자 / 24 시간 / 3600초)
• 질의 가운데 20% 정도는 신규 검색어라고 가정, 0.4GB (10,000,000 사용자 * 10 질의 / 일 * 20자  * 20%) 정도
  • 매일 0.4GB의 신규 데이터가 시스템에 추가된다.

 

2단계 개략적 설계

시스템은 두 부분으로 나누어 진다.

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

 

데이터 수집 서비스

질의문과 사용빈도를 정하는 빈도 테이블이 있다고 가정

 

예를 들어, 사용자가 'twitch', 'twitter', 'twitter', 'twillo'를 순서대로 검색하면 아래와 같이 바뀌어진다.

 

 

 

질의 서비스

빈도 테이블이 있다고 가정

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

빈도 테이블

 

 

예를 들어, 사용자가 tw를 검색창에 입력하면 아래와 같이 빈도 테이블의 top5가 자동완성 검색어가 표시되어야 한다.

 

5개 검색어

 

5개 검색어를 찾는 SQL 질의문

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

 

 

3단계 상세 설계

몇 개의 컴포넌트를 골라서 상세하게 설계하고 최적화 방안을 논의 한다.

 

• 트라이(trie) 자료구조
• 데이터 수집 서비스
• 질의 서비스
• 규모 확장이 가능한 저장소
• 트라이 연산

 

트라이 자료구조

개략적 설계안에서는 관계형 데이터베이스 저장소를 사용했지만, 효율적이지 않다.

 

트라이 자료구조를 사용해서 이러한 부분을 해결한다.

 

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

• 트라이는 트리 형태의 자료 구조
• 트리의 루트 노드(root)는 빈 문자열을 나타낸다.
• 각 노드는 글자 하나를 저장하며, 26개의 자식노드를 가질 수 있다.
• 각 트리 노드는 하나의 단어, 또는 접두어 문자열(prefix string)을 나타낸다.

트라이 자료구조 예시

 

트라이 자료구조 + 빈도 정보는 아래 이미지와 같다.

트라이 자료구조 + 빈도 정보

 

몇 가지 용어 정리를 한다.

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

 

가장 많이 사용된 질의어 k개는 다음과 같이 찾는다.

• 해당 접두어를 표현하는 노드를 찾는다. 시간 복잡도는 O(p)
• 해당 노드로부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. 시간 복잡도 O(c)
• 유효 노드들을 정렬하여 가장 인기 있는 검색어 k를 찾는다. O(clogc)

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

=> O(p) + O(c) + O(clogc)

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

 

이 문제를 해결하는 방법으로 두 가지가 있다.

 

1. 접두어의 최대 길이를 제한
2. 각 노드에 인기 검색어를 캐시

 

접두어 최대 길이 제한
사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다.

 

따라서 p값은 정수값(50)이라고 가정해도 안전하다.

 

만약, 검색어의 최대 길이를 제한할 수 있다면 "접두어 노드를 찾는" 단계의 시간 복잡도는 O(p)에서 O=O(1)로 바뀔 것이다.

 

 

노드에 인기 검색어 캐시

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

top5 검색어를 질의하는 시간 복잡도를 낮출 수 있지만, 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다.

응답 속도를 위해 저장공간을  희생할 만한 가치는 있따.

 

개선된 트라이 구조

 

 

 

 

두 가지 최적화 기법을 적용하면

• 접두어 노드를 찾는 시간 복잡도는 O(1)로 바뀐다.
• 최고 인기 검색어 5개를 찾는 질의 시간 복잡도도 O(1)로 바뀐다. 검색 결과가 이미 캐시되어 있어서다.

 

즉, 각 단계의 시간 복잡도가 O(1)로 바뀐 덕분에, 최고 인기 검색어 k개를 찾는 전체 알고리즘의 복잡도도 O(1)로 바뀐다.

 

데이터 수집 서비스

• 질의가 입력될 때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려진다.
• 트라이가 만들어지고 나면 인기 검색어는 자주 바뀌지 않는다. 자주 갱신할 필요가 없다.

데이터 분석 서비스의 수정된 설계안

 

 

데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 검색창에 입력된 질의에 관한 원본 테이터가 보관된다.

새로운 데이터가 추가될 뿐 수정은 이루어지지 않으며 로그 데이터에는 인덱스를 걸지 않는다.

 

 

로그 취합 서버

데이터 분석 서비스로부터 나오는 로그 데이터를 취합하여 시스템이 쉽게 소비할 수 있도록 해야한다.

 

트위터와 같은 실시간 애플리케이션의 경우, 결과를 빠르게 보여주기 위해 취합 주기를 짧게 가진다.

대부분의 경우 일주에 한 번 정도 로그를 취합해도 충분하다.

 

취합 데이터

아래 이미지는 매주 취합한 데이터의 사례.

• time 필드는 해당 주가 시작한 날짜
• frequency 필드는 해당 질의가 해당 주에 사용된 횟수의 합

 

작업 서버

주기적으로 비동기적 작업을 실행하는 서버 집합

트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당

 

트라이 캐시

분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기  연산 성능을 높이는 구실

매주 트라이 데이터베이스의 스냅샷을 떠서 갱신

 

트라이 데이터베이스

트라이 데이터베이스로 사용할 수 있는 선택지는 아래와 같이 두 가지이다.

 

1. 문서 저장소
   • 트라이를 매주 만드는 것으로, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장
   • 몽고디비 같은 문서 저장소를 활용하면 편리하게 저장
2. 키-값 저장소
   • 아래 로직을 적용하면 해시 테이블 형태로 변환 가능
     • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
     • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

해시 테이블

 

질의 서비스

앞선 개략적 설계안의 비효율성을 개선한 새 설계안

 

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

개선한 새 설계안

 

질의 서비스는 빨라야 한다. 아래 방안으로 최적화 생각해 보기

• AJAX 요청: AJAX 요청을 보내서 자동완성된 검색어 목록을 가져온다. 페이지를 새로고침할 필요가 없다는 장점
• 브라우저 캐싱: 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않는다. 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져올 수 있다.
  => 구글 검색 엔진은 cache-control 헤더 값에 private 을 넣어 한 시간 동안 캐시한다.
  => private은 응답의 요청을 보낸 사용자의 캐시에만 보관할 수 있다.
• 데이터 샘플링: 대규모 시스템의 경우, 모든 질의 결과를 로깅하면 CPU 자원과 저장공간을 소진하게 된다. N개 요청 가운데 1개만 로깅하도록 하는 것.

 

트라이 연산

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

 

트라이 생성

작업 서버가 담당하며, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용.

 

트라이 갱신

트라이를 갱신하는 두 가지 방법

1. 매주 한 번 갱신하는 방법:
   • 새로운 트라이를 만든 다음에 기존 트라이를 대체
2. 트라이의 각 노드를 개별적으로 갱신하는 방법
   
   • 성능이 좋지않다
   • 트라이 노드를 갱신할 때 모든 상위 노드도 갱신해야 한다.

 

검색어 삭제

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

트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 처리한다.

 

필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있는 장점이 있다.

데이터베이스에서 부적절한 검색어를 물리적으로 상제하는 것은 다음 번 업데이트에 비동기적으로 진행

 

 

저장소 규모 확장

트라이의 크기가 한 서버에 넣기에 너무 큰 경우에도 대응할 수 있도록 규모 확장성을 해결하자.

 

아래는 첫 글자를 기준으로 샤딩하는 예시 방법
=> 최대 26 대(영어 알파벳 개수) 서버

• 두 대 서버가 필요
  • a부터 m까지 글자로 시작하는 검색어는 첫 번째 서버
  • 나머지는 두 번째 서버
• 세 대 서버가 필요
  • a부터 i까지는 첫 번째 서버
  • j부터 r까지는 두 번째 서버
  • 나머지는 세 번째 서버

 

4단계 마무리

• 다국어 지원
  • 트라이에 유니코드 데이터를 저장
• 국가별 인기 검색어 순위
  • 국가별로 다른 트라이를 사용
  • 트라이를 CDN에 저장하여 응답속도를 고려
• 실시간으로 변하는 검색어의 추이 반영
  => 현재 구조로는 불가능함.
  • 도움이 될 수 있는 몇 가지 아이디어 고려 
    1. 샤딩을 통하여 작업 대상 데이터의 양을 줄인다.
    2. 순위 모델를 바꾸어 최근 검색어에 보다 높은 가중치를 준다.
    3. 데이터가 스트림 형태로 온다.
       => 아파치 스파크 스트리밍, 아파치 카프카, 아파치 스톰 등의 시스템을 고려