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

• 검색어 자동완성에 대해 이야기합니다.

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

• 5개의 자동 완성 검색어가 표시되어야 합니다.
• 5개를 고르는 기준은 질의 빈도에 따라 정해지는 검색어 인기 순위로 삽습니다.
• 맞춤법 검사나 자동수정은 지원하지 않습니다.
• 질의는 영어나, 다국어 지원을 생각해도 괜찮습니다.
• 모든 질의는 영어 소문자로 이루어진다고 가정합니다.
• 일간 능동 사용자(DAU) 기준으로 천만(10million) 명입니다.

요구사항

• 빠른 응답 속도: 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시되어야 합니다.
• 연관성: 자동완성되어 추력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 합니다.
• 정렬: 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어야 합니다.
• 규모 확장성: 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 합니다.
• 고가용성: 시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능해야 합니다.

개략적 규모 추정

• 일간 능동 사용자는 천만 명 가정
• 평균적으로 한 사용자는 매일 10건의 검색을 수행합니다.
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정합니다.
• 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보냅니다.
• 대략 초당 24,000건의 질의(QPS)가 발생할 것입니다. (10,000,000 * 10질의 / 일 x 20자 / 24시간 / 3600초)
• 최대 QPS = QPS * 2 = 대략 48,000

2단계 개략적 설계안 제시 및 동의 구하기

• 개략적 시스템은 두 부분으로 나뉩니다.
  • 데이터 수집 서비스(data gathering service): 사용자가 입력한 질의를 실시간으로 수집하는 시스템입니다.
  • 질의 서비스(query service): 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스입니다.

데이터 수집 서비스

• 질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정합니다.

질의 서비스

• 두 개의 필드가 있습니다.
  • query: 질의문을 저장하는 필드
  • frequency: 질의문이 사용된 빈도를 저장하는 필드

3단계 상세 설계

• 아래의 순서로 최적화를 논의합니다.
  • 트라이(trie) 자료구조
  • 데이터 수집 서비스
  • 질의 서비스
  • 규모 확장이 가능한 저장소
  • 트라이 연산

트라이 자료구조

• 트라이는 문자열들을 간략하게 저장할 수 있는 자료구조입니다.
• 아래의 형태를 가지고 있습니다.
  • p: 접두어(prefix)의 길이
  • n: 트라이 안에 있는 노드 개수
  • c: 주어진 노드의 자식 노드 개수
• 이 알고리즘의 시간 복잡도는 O(p) + O(c) + O(clogc) 입니다.
• 최악의 경우, 전체 트라이를 봐야할 수도 있습니다. 이를 해결할 방법은 다음과 같습니다.
  • 접두어의 최대 길이를 제한
  • 각 노드에 인기 검색어를 캐시합니다.

접두어 최대 길이 제한

• 검색창에 긴 검색어를 입력하는 일은 거의 없으며 p 값은 작다고 가정해도 안전합니다.

노드에 인기 검색어 캐시

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

위의 내용을 정리하면 각 단계의 시간 복잡도가 O(1) 이므로, 알고리즘의 복잡도도 O(1)로 바뀌어야합니다.

데이터 수집 서비스

• 매일 수천만 건의 질의가 입력될 것이나, 그때마다 트라이를 갱신하면 질의 서비스가 느려집니다.
• 트라이가 생성된 후에는 인기 검색어는 자주 바뀌지 않습니다.

질의 서비스

• 아래의 최적화 방법을 고려해봅니다.
  • AJAX 요청(request)
  • 브라우저 캐싱(browser caching)
  • 데이터 샘플링(data sampling)

트라이 연산

• 트라이 생성
  • 트라이 생성은 작업 서버가 담당합니다.
• 트라이 갱신
  • 매주 한번 갱신
  • 트라이의 각 노드를 개별하는 갱신(트라이가 작은 경우 고려해봄직합니다.)
• 검색어 삭제
  • 위험한 질의어는 자동 완성 결과에서 제거가 필요합니다.
  • 이 경우 필터 계층이 필요합니다.

저장소 규모 확장

• 트라이가 너무 큰 경우, 규모 확장성도 고려해봅니다.
  • 검색어에 따라 서버를 나눕니다.
  • 영어의 경우, 26개이나 더 늘릴려면 샤딩을 해야합니다.

4단계 마무리

• 다음을 추가적으로 질문이 올 수 있습니다.
  • 다국어 지원이 가능하려면? 트라이에 유니코드 데이터를 저장해야 합니다.
  • 국가별로 인기 검색어 순위가 다르다면? 국가별 다른 트라이 사용, CDN등을 통한 응답속도 향상도 고려해봅니다.
• 실시간 변하는 추이를 구현하려면?
  • 샤딩을 통하여 작업 대상 데이터의 양을 줄입니다.
  • 순위 모델을 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 합니다.
  • 데이터가 스트림 형태로 올 수 있습니다.