검색어 자동완성 시스템 설계 (가상 면접 사례로 배우는 대규모 시스템 설계)

검색창에 단어를 입력하다 보면 입력중인 글자에 맞는 검색어가 자동으로 완성되어 표시되는 것을 볼 수 있다. 이런 기능은 보통 검색어 자동완성이라 부른다. 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템을 설계해 보도록 하자.

가정된 상황

- 사용자가 입력하는 단어는 자동완성될 검색어의 첫부분인 것으로
- 자동완성 검색어가 표시되는 갯수는 5개
- 질의 빈도에 따라 인기순으로 정렬
- 맞춤법 검사나 자동수정 지원X
- 질의는 영어를 기본으로하고, 시간이 허락한다면 다국어도 반영
- 모든 질의는 소문자로 이루어진다고 가정
- 일간 능동 사용자 기준으로 1000만명으로 가정

- 빠른 응답속도, 연관성, 정렬, 규모확장성, 고가용성 고려해야함.

- 일간 능동 사용자(DAU)는 천만영으로 가정하고있다.
- 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정하자.
- 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정하자.

• 문자 인코딩 방법으로 ASCII를 사용한다고 가정할 것으로, 1문자 = 1바이트이다.
• 질문은 평균적으로 4개 단어로 이루어진다고 가정할 것이며, 가 ㄱ단어는 평균적으로 다섯 글자로 구성된다고 가정하자
• 따라서 질의당 평균 4x5=20 바이트다.
  검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다. 예를들어 dinner를 입력하면 d, di, din, dinn, dinne, dinner 6번의 호출 발생

그렇다면 초당 24,000건의 질의(QPS)가 발생한다. (10,000,000명 x 10질의 x 20자 / 24시간 x 3600초)

최대 QPS = QPS x 2 = 대략 48,000
질의 가운데 20%정도는 신규 검색이라고 가정. 매일 0.4GB의 신규 데이터가 시스템에 추가됨.
(=10,000,000 x 10 x 20 x 20%)

개략적인 설계안

데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집하는 시스템
질의 서비스 : 주어진 질의에 5개의 인기 검색어 정렬 및 반환

데이터 수집 서비스

빈도 테이블이 있다고 가정.

query	freuqency
twitter	35
twitch	29
twilight	25
twin peak	21
twitch prime	18
twitter search	14
twillo	10
twin peak sf	8

이 상태에서 사용자가 "tw"를 검색창에 입력하면 5개의 자동완성 검색어가 표시되어야한다.

해당 검색어는 `SELECT * FROM frequency_table

WHERE query Like 'prefix%' ORDER BY frequency DESC LIMIT 5 를 통해 계산할 수 있다. 하지만 데이터가 아주 많아지면 데이터베이스가 병목될 수 있다.

인덱스를 써도 "정렬 + 자르기(LIMIT)"는 메모리와 CPU에 부담을 주기 때문

상세 설계

트라이 자료구조

개략적 설계안에서는 관계형 데이터베이스를 저장소로 사용했지만, TOP5의 질의를 골라내는 방법은 효율적이지 못하다. 이 문제는 트라이를 사용해 해결 할 예정이다.

트라이란?
문자열 검색에 특화된 트리 기반 자료구조로, 특히 접두어(prefix) 검색에 매우 효율적이다. 자동완성, 사전(dictionary), 문자열 검색 등에서 자주 사용된다.

(root)
├── b
│   ├── be
│   │   ├── bee: 20
│   │   │   └── beer: 10
│   │   ├── bes
│   │   │   └── best: 35
│   │   └── bet: 29
│   └── bu
│       └── buy: 14
└── w
    └── wi
        ├── wis
        │   └── wish: 25
        └── win: 50

루트는 빈 문자열을 나타냄

각 트리는 하나의 단어, 또는 접두어 문자열을 나타낸다.

검색어 자동 완성되는 과정은 다음과 같다.
1.접두어 노드 "be"를 찾는다.
2.해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다.
3.유효 노드를 정렬하여 k갯수만큼 데이터를 골라낸다.
4.k가2라고할때 best, bet이 출력된다.

해당 알고리즘은 최악의 경우 k개의 결과를 위해 트리 전체를 다 검색해야하는 일이 생길 수 있다.
이는 아래 두가지 방법으로 해결할 수 있다.

접두어의 최대 길이 제한

사용자가 긴 검색어를 입력하는 일은 거의 없다. 따라서 작은값으로 가정해도 안전하다.(가령 50정도) 검색어의 최대 길이를 제한할 수 있다면 접두어 노드를 찾는 단계의 시간 복잡도는 O(1)로 줄어들 수 있다.

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

각 노드에서 k개의 인기 검색어를 저장해두면 전체 트라이를 검색하는 일을 방지할 수 있다. 하지만 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다는 단점도 있다. 빠른 응답 속도가 중요할 때는 희생할 가치가 있다는점.

데이터 수집 서비스

사용자가 검색창에 뭔가 타이핑을 할 때마다 실시간으로 데이터를 수정하는 방법은 실용적이지 못하다.

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

[데이터 분석 서비스 로그]
            │
            ▼
    [로그 취합 서버]
            │
            ▼
     [취합된 데이터]
            │
            ▼
       [작업 서버]
            │
            ▼ (매주 갱신)
   [트라이 데이터베이스]
            │
            ▼ (매주 스냅샷)
       [트라이 캐시]

데이터 분석 서비스를 두고 사용자 질의에대해 데이터를 취합한다. 작업 서버는 취합된 데이터를 토대로 트라이 데이터베이스를 갱신하고 캐싱한다.

트라이 데이터베이스 저장소로는 문서 저장소(mongoDB 같은)와 키-값 저장소 두가지 선택지가 있다.

저장 규모의 확장

트라이의 크기가 너무 큰 경우에는 저장소의 확장이 필요하다.
영어만 지원하면 된다는 가정을 기반으로, 첫 글자를 기준으로 샤딩하는 방법을 생각해볼 수 있다.

해당 방법은 알파벳기준 26개까지밖에 샤딩을 할 수 없으므로, 더 필요하다면 계층을 두고 해하는 방벙이 있다. 예를들어 검색어 대응 샤드 관리자를 두고, 어떤 샤드에 어떤 데이터가있는지 관리하는 방법이다.