대규모 시스템 설계 기초 - 13장 검색어 자동완성 시스템

구글 검색 또는 아마존 검색창에 단어를 치게 되면 검색어와 관련된 검색어를 자동으로 완성해서 보여주는 것을 찾아볼 수 있었을 것이다. 이런 기능은 많은 제품에서 중요하게 사용되는 기능이다.

 

여기서는 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템을 설계해 보도록 하겠다.

 

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

1. 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분이어야 하는지 중간 부분이어도 상관없는지 물어보기

EX) 첫 부분으로 한정한다.

 

2. 몇 개의 자동완성 검색어가 표시되어야 하는지 물어보기

EX) 5개

 

3. 자동완성 검색어 5개를 고르는 기준이 무엇인지 물어보기

EX) 질의 빈도에 따라 정해지는 검색어 인기 순위를 기준으로 

 

4. 맞춤법 검사 기능도 제공해야 하는지 물어보기

EX) 아니다. 맞춤법 검사나 자동수정은 지원하지 않는다.

 

5. 질의는 영어인지 물어보기

EX) 맞다. 시간이 남는다면 다국어 지원도 생각해도 좋다

 

6. 대문자나 특수 문자 처리도 해야하는지 물어보기

EX) 모든 질의는 영어 소문자로 이루어진다고 가정한다.

 

7. 얼마나 많은 사용자를 지원해야 하는가?

EX) DAU 기준으로 천만 명이다.

 

요구사항

• 빠른 응답 속도 : 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빠르게 표시되어야 한다. 페이스북의 경우 응답속도를 100 밀리초 이내라고 규정한다. 그렇지 않으면 시스템 이용이 불편해진다.
• 연관성 : 검색어는 사용자가 입력한 단어와 연관성이 있어야 한다.
• 정렬 : 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어야 한다.
• 규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 한다.
• 고가용성 : 시스템의 일부에 장애가 발생하거나 느려지거나, 예상치 못한 네트워크 문제가 발생해도 시스템은 계속 사용 가능해야 한다.

개략적 규모 추정

• DAU는 천만 명으로 가정
• 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정
• 질의 할 때 평균적으로 20바이트의 데이터를 입력한다고 가정
  • 문자 인코딩 방법은 ASCII를 사용한다고 가정하면 1문자 = 1바이트이다.
  • 질의문은 평균적으로 4개의 단어로 이뤄진다고 가정, 각 단어는 평균적으로 다섯 글자로 구성된다.
  • 따라서 질의당 평균 4 x 5 = 20 바이트이다.
• 검색창에 글자를 입력할 때마다 클라이언트는 백엔드 서버로 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다.  예를 들어 검색창에 dinner라고 입력하면 아래 처럼 순차적으로 6개의 요청이 생긴다.
  • search?q=d 
  • search?q=di
  • search?q=din
  • 등등.. 
• 대략 초당 24,000건의 질의 발생 = (10,000,000 x 10 질의 / 일 x 20자 / 24시간 / 3600초)
• 질의 가운데 20% 정도는 신규 검색어라고 가정.

 

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

개략적으로 보면 시스템은 크게 데이터 수집 서비스와 질의 서비스로 나눌 수 있다.

 

• 데이터 수집 서비스란 사용자가 입력한 질의를 실시간으로 수집하는 시스템이다.  질의한 단어와 횟수를 빈도 테이블에 저장
• 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 놓는 서비스

3단계 상세 설계

 

트라이 자료구조

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

 

트라이는 문자열을 찾기 위해 사용되는 자료구조 중 하나이다.

루트 노드는 빈문자열을 가지고 그 밑에 자식 노드에는 포함되는 단어의 첫글자, 그 다음에는 26가지 단어가 올 수 있다. 이런 식으로 단어가 형성되기까지의 가정을 트리 형태로 만들어놓은 자료구조이다.

 

p: 접두어의 길이

n: 트라이 안에 있는 노드 개수

c: 주어진 노드의 자식 노드 개수

 

가장 많이 사용된 질의 k개는 다음과 같은 과정으로 찾을 수 있다.

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