가상 면접 사례로 배우는 대규모 시스템 설계 기초 Study [13장] 검색어 자동완성 시스템

검색어 자동완성 시스템

• 검색창에 단어를 입력하다보면 입력중인 글자에 맞는 검색어가 자동으로 표기되는 것
• autocomplete, typeahead, search-as-you-type, incremental search

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

요구사항 정의

• 빠른 응답 속도 : 페이스북의 응답속도는 100밀리초 이내
• 연관성 : 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것
• 정렬 : 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬
• 규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있을 정도록 확장 가능
• 고가용성 : 일부 장애가 발생하거나 느려지거나 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능

개략적 규모 추정

• DAU는 천만 명으로 가정
• 평균적으로 한 사용자는 매일 10건의 검색 수행
• 질의할 때마다 평균적으로 20Byte 입력
  • 문자 인코딩 방법으로는 ASCII 사용 1문자=1Byte
  • 질의문은 평균적으로 4개의 단어 구성 각 단어는 평균 다섯 글자
  • 질의당 평균 4 * 5 = 20 Byte
• 검색창에 글자를 입력 백엔드에 요청을 보낸다 1회 검색당 20건의 요청이 백엔드로 전달
• 대략 초당 24,000건의 QPS 발생 (10,000,000 * 10 queries/day * 20 characters / 24시간 / 3600초)
• 최대 QPS = 24,000 * 2 = 48,000
• 질의 중 20% 신규 검색어
  • 10,000,000 * 10 queries/day * 20 byte per query * 20% = 0.4 GB 가 데이터베이스 저장

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

• 데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집. 데이터가 많은 경우 실시간 시스템은 바람직하지 않다.
• 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬

데이터 수집 서비스

• 질의문과 사용 빈도를 저장하는 빈도 테이블을 관리

질의 서비스

• query : 질의문을 저장하는 필드
• frequency : 질의문이 사용된 빈도를 저장하는 필드
• Top5 는 빈드 테이블에 기록된 수치를 사용해 계산
• 데이터 양이 적을 때는 나쁘지 않으나 데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있다.

1
2
3
4

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

3. 상세 설계

3.1 트라이(trie) 자료 구조

• 트라이는 문자열들을 간략하게 저장할 수 있는 자료 구조
• “retrieval” 이라는 단어에서 왔으며 문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조
  트라이 자료구조의 핵심

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

검색어 자동완성 구현

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

가장 많이 사용된 질의어 k 찾기

• 해당 접두어를 표현하는 노드를 찾음. 시간복잡도 O(p)

• 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드 찾기

  • 유효한 검색 문자열을 구성하는 노드가 유효 노드. 시간복잡도는 O(c)

• 유효 노드들을 정렬하여 가장 인기 있는 검색어 k를 찾음 시간복잡도 O(c log c)

  예제

  k=2 이고 사용자가 검색창에 “be"를 입력

  

  1. 접두어 노드 “be” 를 찾음
  2. 해당 노드부터 시작하는 하위 트리를 탐색하는 모든 유효 노드 찾기 : [beer:10], [best:35], [bet:29]
  3. 유효 노드를 정렬하여 두개만 골라낸다. [best:35], [bet:29]

• 이 알고리즘의 시간복잡도는 O(p) + O(c) + O(c log c)

• 이 알고리즘은 직관적이나 최악의 경우 k개 결과를 얻으려고 전체 트라이를 다 검색

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

접두어 최대 길이 제한

• 검색창에 긴 검색어를 입력하는 일은 없음 p값은 작은 정숫값이라 가정해도 안전하다.
• 시간복잡도는 O(p)에서 O(1) 로 바뀜

노드에 인기 검색어 캐시

• 각 노드에 k개의 인기 검색어를 저장해두면 전체 트라이 탐색을 방지
• 5~10 정도의 자동완성 제안을 표시하면 충분
• 각 노드에 질의를 저장할 공간이 많이 필요하나 응답속도가 아주 중요할 경우 우선순위 될 수 있다.
• 검색결과가 이미 캐시되어있으므로 시간복잡도도 O(1)로 변경

3.2 데이터 수집 서비스

• 매일 수천만 건의 질의가 입력될 때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려짐
• 일단 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것 -> 자주 갱신할 필요는 없음
• 용례에 따라 데이터 수집 서비스의 토대는 달라지지 않음
  • 분석 서비스나 로깅 서비스로부터 올 것이기 때문

데이터 분석 서비스 로그

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

로그 취합 서버

• 데이터 분석 서비스의 로그는 보통 그 양이 엄청나고 데이터 형식도 제각각. 잘 취합하여 제공해야함
• 데이터 취합 방식은 용례에 따라 다름
  • 실시간 애플리케이션의 경우(ex 트위터) : 데이터 취합주기를 보다 짧게 가져가야 한다.
  • 대부분의 경우 일주일에 한 번 정도 로그 취합

작업 서버

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

트라이 캐시

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

트라이 데이버테이스

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

3.3 질의 서비스

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

• 캐시비스는 캐시 서버의 메모리가 부족하거나 캐시 서버에 장애가 있어도 발생할 수 있음

최적화 방안

• AJAX 요청 : 웹 애플리케이션의 경우 AJAX 요청을 보내 자동완성된 검색어 목록을 가져옴. 새로고침 할 필요가 없다
• 브라우저 캐싱 : 대부분의 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않음. 브라우저 캐시를 통해 후속 질의 결과를 캐시에서 바로 가져간다.
  • 구글 검색엔진의 경우 제안된 검색어를 한 시간 동안 응답 헤더 cache-control에 저장한다
  • private는 해당 응답이 요청을 보낸 사용자의 캐시에만 보관
  • max-age=3600 : 3600초동안만 캐시 유지
• 데이터 샘플링 : 대규모 시스템의 경우 모든 질의 결과를 로깅해놓으면 CPU 자원과 저장공간을 엄청나게 소진. N개의 요청중 1개만 로깅

3.4 트라이 연산

트라이 생성

• 트라이 생성은 작업 서버가 담당하며 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터 이용

트라이 갱신

1. 매주 한번 갱신하는 방법 - 새로운 트라이를 만든 다음 기존 트라이를 대체
2. 트라이의 각 노드를 개별적으로 갱신하는 방법

• 성능이 좋지 않다.
• 모든 상위 노드(ancestor)도 갱신필요

검색어 삭제

• 혐오, 폭력, 성적 인 질의어는 자동완성 결과에 제거필요
• 트라이 캐시 앞에 필터 계층을 통해 부적절한 질의어가 반환하지 않도록 하는 것
• 필터 규칙에 따라 검색 결과를 자유롭게 변경
• 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행할 수 있음

3.5 저장소 규모 확장

• 영어만 지원할 경우 간단하게 첫 글자 기준으로 샤딩하는 방법을 생각
• 서버 갯수에 제한이 있고 데이터를 각 서버에 균등하게 배분하기 어렵다
• 검색어 대응 샤드관리자는 어떤 검색어가 어느 저장소 서버에 저장되는지 대한 정보를 관리

4. 마무리

• 다국어 지원이 가능하게 확장하려면
  • 트라이에 유니코드 데이터를 저장한다.
• 국가별로 인기 검색어 순위가 다르다면
  • 국가별로 다른 트라이를 사용하고 트라이를 CDN에 저장 응답속도를 높이는 방법도 생각
• 실시간으로 변하는 검색어 추이를 반영하려면 -> 현 설계안 대응 어려움. 대응이 어려운 이유
  • 작업 서버가 매주 한 번씩만 돌도록 설정. 시의 적절하게 트라이를 갱신할 수 없다.
  • 트라이를 구성하는데 많은 시간이 소요

실시간 검색어 자동완성 시스템 구축 아이디어

• 샤딩을 통해 작업 대상의 양을 줄임
• 순위 모델을 바꾸어 최근 검색어 보다 높은 가중치를 주도로 한다
• 데이터가 스트림 형태로 올 수 있다는 점
  • 모든 데이터를 동시에 사용할 수 없을 가능성을 고려
  • 데이터가 스트리밍 되는 것은 데이터가 지속적으로 생성됨을 의미한다
  • 아파치 하둡 맵리듀스, 아파치 스톰, 아파치 카프카 등