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

가장 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템을 설계한다.

 

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

요구사항

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

개략적 규모 추정

• 일간 능동 사용자(DAU)는 천만 명으로 가정한다.
• 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정한다.
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정한다.
  • 문자 인코딩 방법은 ASCII를 사용한다고 가정 → 1문자 = 1바이트
  • 질의문은 평균적으로 4개 단어로 입력한다고 가정하며 각 단어는 평균 다섯 글자로 구성된다고 가정
  • 따라서 질의당 평균 4 * 5 = 20 바이트다.
• 검색창에 글자를 입력할 때 마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다. 예를 들어 dinner라고 입력한다면 6개의 요청이 순차적으로 백엔드에 전송된다. 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초)
• 최대 QPS = QPS * 2 = 대략 48,000
• 질의 가운데 20% 정도는 신규 검색어라고 가정할 것이다. 따라서 대략 0.4GB정도다. (= 10,000,000 사용자 * 10 질의 / 일 * 20자 * 20%) 매일 0.4GB의 신규 데이터가 시스템에 추가된다는 뜻이다.

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

개략적으로 보면 시스템은 두 부분으로 나뉜다.

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

데이터 수집 서비스

데이터 수집 서비스가 는 다음과 같이 동작한다.

질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정하겠다. 처음에는 이 테이블은 비어 있는데, 사용자가 ‘twitich’, ‘twitter’, ‘twit-ter’, ‘twillo’를 순서대로 입력하면 그 상태가 다음과 같이 바뀌어 나가게 된다.

질의 서비스

아래의 사진과 같이 빈도 테이블이 있는 상태일 때 두 개의 필드는 다음과 같다.

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

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

“top 5”는 빈도 테이블의 frequency를 사용해 계산한다고 가정한다.

가장 많이 검색된 5개 검색어는 아래 SQL을 통해 계산할 수 있다.

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

데이터 양이 적다면 나쁘지 않은 설계안이지만 데이터가 아주 많아지면 데이터베이스가 병목될 수 있다.

 

3단계. 상세 설계

데이터 수집 서비스와 질의 서비스의 두 부분으로 구성된 개략적 설계안보다 상세히 설계하고 최적화 방안을 논의한다.

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

트라이 자료구조

개략적 설계안에서는 관계형 데이터베이스를 저장소로 사용했었다. 하지만 이 방법은 효율적이지 않으며 트라이(trie, 접투어 트리)

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

트라이 자료구조의 핵심 아이디어를 살펴보면 다음과 같다.

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

다음 그림은 질의어 tree, try, true, toy, wish, win 가 보관된 트라이이다.

검색어 입력 빈도에 따라 트라이 노드에 저장하게 되면 다음과 같은 상태가 된다.

해당 트라이로 검색어 자동완성을 구현해본다면

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

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

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

k=2이고 사용자가 검색창에 ‘be’을 입력했다고 하면 다음과 같이 동작할 것 이다.

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

이 알고리즘의 시간복잡도는 위의 단계에 소요된 총 합으로 O(p)+O(c)+O(clogc)이다.

이 알고리즘은 직관적 이지만 최악의 경우에는 전체 트라이를 다 검색해야하는 문제가 있을 수 있으므로 다음과 같은 해결 방법이 있다.

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

접두어 최대 길이 제한

사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없기 때문에 p값은 작은 정수값이라고 가정해도 안전하다.

시간복잡도는 O(p)에서 O(작은 상숫값) = O(1)로 바뀔 것이다.

노드에 인기 검색어 캐시

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

각 노드에 질의어를 저장할 공간이 많이 필요하게 된다는 단점은 있으나 빠른 응답속도가 중요할 때에는 이정도 저장공간을 희생할 만한 가치가 있다.

다음은 개선된 트라이 구조다.

앞의 두 가지 최적화 기법을 적용하면 시간 복잡도는 다음과 같이 바뀐다.

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

 

데이터 수집 서비스

지금까지의 설계안은 사용자가 검색창에 뭔가 타이핑을 할 때마다 실시간으로 데이터를 수정했다.

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

트위터 같은 실시간 어플리케이션이라면 제안되는 검색어를 항상 신선하게 유지할 필요가 있지만, 구글 검색 같은 애플리케이션이라면 자주 바꿔줄 이유가 없다.

다음은 수정된 데이터 분석 서비스의 설계안이다.

데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 검색어에 입력된 질의에 관한 원본 데이터가 보관되며 새로운 데이터가 추가될 뿐 수정은 이루어지지 않는다. 또한, 로그 데이터에는 인덱스를 걸지 않는다.

로그 취합 서버

로그 데이터를 잘 취합하여 시스템이 쉽게 소비할 수 있도록 해야한다.

데이터 취합 방식은 서비스 용례에 따라 달라진다.

트위터와 같은 실시간 어플리케이션의 경우 결과를 빨리 보여주는 것이 중요 → 데이터 취합 주기를 짧게 가져간다.

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

 

취합된 데이터

작업 서버

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

트라이 캐시

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

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

트라이 데이터베이스

트라이 데이터베이스는 지속성 저장소이며 다음 두가지로 사용할 수 있다.

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

질의 서비스

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

질의 서비스는 빠르게 동작해야 하므로 아래와 같은 최적화 방안을 생각할 수 있다.

• AJAX 요청 : 요청을 보내고 받기 위해 페이지를 새로고침 할 필요가 없다.
• 브라우저 캐싱 : 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있다.
• 데이터 샘플링 : 모든 질의 결과를 로깅하도록 하면 CPU 자원과 저장공간을 많이 소진하게 된다. 데이터 샘플링 기법은 N개 요청 가운데 1개만 로깅하도록 하는 것이다.

트라이 연산

트라이는 검색어 자동완성 시스템의 핵심 컴포넌트이다.

트라이 생성

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

트라이 갱신

트라이를 갱신하는데에는 두 가지 방법이 있다.

1. 매주 한 번 갱신하는 방법 : 새로운 트라이를 만든 다음, 기존 트라이를 대체한다.
2. 트라이의 각 노드를 개별적으로 갱신하는 방법 : 성능이 좋지않지만 트라이가 작을 때는 고려해볼만 하다. 트라이 노드를 갱신할 때는 그 모든 상위 노드도 갱신해야 하는데, 상위 노드에도 인기 검색어 질의 결과가 보관되기 때문이다.

검색어 삭제

혐오성이 짙거나, 폭력적이거나, 여러 가지로 위험한 질의어를 자동완성 결과에서 제거해야한다.

트라이 캐시 앞에 필터 계층을 두면 부적절한 질의어가 반환되지 않도록 할 수 있으며 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다.

저장소 규모 확장

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

영어만 지원하면 되기 때문에, 간단하게는 첫 글자를 기준으로 샤딩 하는 방법을 생각해 볼 수 있다.

• 두 대의 서버가 필요한 경우 : ‘a’부터 ‘m’까지로 시작하는 검색어는 첫 번째 서버에, 나머지는 두 번째 서버에 저장한다.
• 세 대의 서버가 필요한 경우‘ : a’부터 ‘i’까지는 첫 번째 서버에, ‘j’부터 ‘r’까지는 두 번째 서버에, 나머지는 세 번째 서버에 저장한다.

이 방법을 쓰는 경우에는 알파벳은 26자가 있기 때문에 사용 가능한 서버는 최대 26개로 제한된다.

이 이상으로 서버 대수를 늘리려면 샤딩을 계층적으로 해야 한다.

첫 번째 글자는 첫 번째 레벨의 샤딩에 쓰고, 두 번째 레벨의 샤딩에 쓰는 것이다.

‘a’로 시작하는 검색어를 네 대 서버에 나눠서 보관한다면

• 첫 번째 서버 → ‘aa’부터 ‘ag’까지
• 두 번째 서버 → ‘ah’부터 ‘an’까지
• 세 번째 서버 → ‘ao’부터 ‘au’까지
• 네 번째 서버 → 나머지

이 방법은 얼핏 보면 문제가 없어 보이지만 ‘c’로 시작하는 단어가 ‘x’로 시작하는 단어보다 많다는 것을 감안하면 좋은 방법이 아니다.

이 문제를 해결하기 위해는 과거 질의 데이터의 패턴을 분석해서 사딩하는 다음과 같은 방법을 제안한다.

‘검색어 대응 샤드 관리자'는 어떤 검색어가 어느 저장소 서버에 저장되는지를 관리한다.

예를 들어 ‘s’로 시작하는 검색어의 양이 ‘u’, ‘v’, ‘w’, ‘x’, ‘y’, ‘z’로 시작하는 검색어를 전부 합친 것과 비슷하다면 ’s’에 대한 샤드 하나와 ‘u’~’z’까지의 검색어를 위한 샤드 하나를 두어도 충분할 것 이다.

4단계. 마무리

• 다국어 지원이 가능하도록 시스템을 확장하려면? → 트라이에 유니코드 데이터를 저장한다.
• 국가별로 인기 검색어 순위가 다르다면? → 국가별로 다른 트라이를 사용하면 된다.
• 실시간으로 변하는 검색의 추이를 반영하려면? → 현 설계안은 그런 검색어를 지원하기에 적합하지 않다. 그 이유는 다음과 같다.
  • 작업 서버가 매주 한 번씩만 돌도록 되어 있어서 시의 적절하게 트라이를 갱신할 수 없다.
  • 때 맞춰서 서버가 실행되도, 트라이를 구성하는데 많은 시간이 소요된다.

실시간 검색어 자동 완성 시스템 구축하는데 도움 될만한 몇가지 아이디어

• 샤딩을 통하여 작업 대상 데이터의 양을 줄인다.
• 순위 모델을 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 한다.
• 한 번에 데이터를 동시에 사용할 수 없을 가능성이 있다는 점을 고려해야한다.