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

가상 면접 사례로 배우는 대규모 시스템 설계 기초 – System Design Interview

여기서 설계하는 검색 시스템은 당근마켓 과 같은 경우에 적합할 것이라는 생각이 들었다.
잘못 입력했을 경우에 대한 교정이 없고, 단어 위주로 검색을 하게 되는 시스템에 유용할 거라는 생각이 들어서였다.

검색어 자동완성과는 또 다른 이야기이긴 하지만
당근마켓은 검색엔진으로 엘라스틱서치를 사용하고 있다고 한다.
아래 글이 생각나서 링크로 걸어둔다.
당근마켓 검색 엔진, 쿠버네티스로 쉽게 운영하기

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

질문 예시

- 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분이어야 하나요? 아니면 중간 부분이 될 수도 있습니까?
- 몇 개의 자동완성 검색어가 표시되어야 합니까?
- 자동완성 검색어를 고르는 기준은 무엇입니까?
- 맞춤법 검사 기능도 제공해야 합니까?
- 질의는 영어입니까?
- 대문자나 특수 문자 처리도 해야합니까?
- 얼마나 많은 사용자를 지원해야 합니까?

요구사항 정리

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

개략적 규모 추정

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

  - 문자 인코딩 방법으로는 ASCII를 사용한다고 가정할 것이므로, 1문자 = 1바이트이다.
- 질의문은 평균적으로 4개 단어로 이루어진다고 가정할 것이며, 각 단어는 평균적으로 다섯 글자로 구성된다고 가정할 것이다.
- 따라서 질의당 평균 4x5 = 20 바이트이다.

- 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다. 

예를 들어 dinner를 검색한다고 하면
d -> di -> din -> dinn -> dinne -> dinner
이렇게 요청을 보내게 된다.

- 대략 초당 24,000건의 질의(QPS)가 발생할 것이다 ( = 10,000,000 사용자 x 10 질의/일 x 20 자 / 24시간 / 3600 초 )

- 최대 QPS = QPS X 2 = 대략 48,000

- 질의 가운데 20% 정도는 신규 검색어라고 가정한다. 따라서 대략 0.4GB 정도다 ( = 10,000,000 사용자 x 10 질의/일 x 20 자 * 20% ). 매일 0.4GB의 신규 데이터가 시스템에 추가된다.

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

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

데이터 수집 서비스(data gathering service): 사용자가 입력한 질의를 실시간으로 수집하는 시스템이다. 데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지 않지만 설계안을 만드는 출발점으로는 괜찮을 것이다. 상세 설계안을 준비할 때 보다 현실적인 안으로 교체한다.

질의 서비스(query service): 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스이다.

데이터 수집 서비스

질의문과 사용빈도를 저장하는 빈도 테이블(frequency table)을 이용한다.

예시는 다음과 같다.

질의 서비스

데이터 수집 서비스에서 생성된 빈도 테이블을 이용하여 top 5 를 계산하여 전달한다.

아래는 질의문 예시이다.

데이터 양이 적을 때는 나쁘지 않은 설계안이다. 하지만 데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있다. 상세 설계에서 이 문제를 해결해 나가보자.

3단계 상세 설계

컴포넌트를 보다 상세히 설계하고 최적화해보자.

- 트라이(trie) 자료구조
- 데이터 수집 서비스
- 질의 서비스

에 대해 알아보고 고민해 볼 것이다.

트라이(trie) 자료구조

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

라고 하였을 때

검색어 자동완성을 위한 데이터를 탐색하는데 걸리는 시간 복잡도는 다음과 같다.

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

- 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유호 노드를 찾는다. 유효한 검색 문자열을 구성하는 노드가 유효 노드다. 시간 복잡도는 O(c) 이다.

- 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clogc)이다.

정리해보면 O(p) + O(c) + O(clogc) 이다.

일반적으로 이야기 하는 트라이 자료구조의 시간복잡도는 다음과 같았다.
생성 시간 복잡도는 O(M x L), 탐색 시간 복잡도는 O(L)
여기서 M은 총 문자열의 수, L은 가장 긴 문자열 이다.

하지만 우리가 하고자 하는 것은
하나만 찾는게 아니라 sort를 해서 인기있는 검색어 k개를 찾아내야 한다.
따라서 sort의 시간 복잡도가 추가가 된다.
sort의 경우 O(nlogn)의 형태를 가진다.

예시를 들면 다음과 같다.

다음과 같은 트라이 에서 검색창에 'be' 를 입력했다고 하자. 이때 2개의 인기 검색어만 추려낸다.

1. 접두어 노드 ‘be’를 찾는다.
2. 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. (beer, best, bet)
3. 유효 노드를 정렬하여 2개만 골라낸다. (best, bet)

데이터 수집 서비스

개략적 설계안 에서는 사용자가 검색창에 타이핑을 할 때마다 실시간으로 데이터를 수정했다. 이 방법은 다음 두 가지 이유로 그다지 실용적이지 못하다.

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

트위터 같은 실시간 애플리케이션이라면 제안되는 검색어를 항상 신선하게 유지해야 하겠지만, 구글 검색 같은 애플리케이션이라면 그렇게 자주 바꿔줄 이유는 없을 것이다.

수정된 설계안은 다음과 같다.

데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 검색창에 입력된 질의에 관한 원본 데이터가 저장된다. 새로운 데이터가 추가될 뿐 수정 작업은 이루어지지 않으며 로그 데이터에 인덱스도 걸지 않아도 된다.

다음은 로그 파일의 예시이다.

로그 취합 서버

데이터 분석 서비스로부터 나오는 로그는 보통 그 양이 엄청나고 데이터 형식도 제각각인 경우가 많다. 따라서 이 데이터를 잘 취합(aggregation) 하여 우리 시스템이 쉽게 소비할 수 있도록 해야 한다.

시스템에 따라 취합의 실시간성이 얼마나 중요한지 확인하고 넘어가는 것이 좋다.

본 설계안에서는 일주일 주기로 취합한다고 가정한다.

취합된 데이터

취합한 데이터의 예시는 다음과 같다.

time 필드는 해당 주가 시작된 날짜를 나타내며 frequency 필드는 해당 주에 사용된 횟수의 합이다.

작업서버

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

트라이 캐시

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

트라이 데이터베이스

다음과 같은 선택지를 선택할 수 있다.

- 문서 저장소

주기적으로 트라이를 직렬화하여 데이터베이스에 저장한다.
몽고디비 같은 문서 저장소를 활용하면 이런 데이터를 편리하게 저장할 수 있다.

- 키-값 저장소

트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능하다.
- 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
- 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

질의 서비스

1. 검색 질의가 로드밸런서로 전송된다.
2. 로드밸런서는 해당 질의를 API 서버로 보낸다.
3. API서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성한다.
4. 데이터가 트라이 캐시에 없는 경우 데이터를 데이터베이스에서 가져와 캐시에 채운다. (캐시 미스는 캐시 서버의 메모리가 부족하거나 캐시 서버에 장애가 있어도 발생할 수 있다.)

질의 서비스는 빨라야 한다. 따라서 다음과 같이 최적화를 고려해보면 좋을 것이다.

- AJAX 요청

- 브라우저 캐싱

자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않는다. 따라서 제안된 검색들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있다.

본 설계안에서는 cache control : private 를 이용하여 사용자 캐시에만 보관하도록 하고, max-age를 통해 캐싱 시간을 설정한다.

cache control 에 대한 부분은 아래 링크 참고
https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Cache-Control

- 데이터 샘플링 (data sampling)

모든 질의 결과를 로깅하도록 해놓을 필요는 없다. 이는 CPU 자원과 저장공간을 엄청나게 소진하게 한다. N개의 요청 중 하나만 로깅되도록 한다.

트라이 연산

트라이 생성

작업 서버가 담당한다. 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용한다.

트라이 갱신

두 가지 방법이 있다.

1. 주기에 따른 갱신
새로운 트라이를 만든 다음 기존 트라이를 대체

2.  트라이의 각 노드를 개별적으로 갱신
트라이가 작을 경우에는 고려해볼만한 방안이다.

검색어 삭제

혐오성이 짙거나, 폭력적이거나, 성적으로 노골적이거나, 기타 여러가지로 위험한 질의어를 자동완성 결과에서 제거해야 한다. 이를 위해 좋은 방법은 크라이 캐시 앞에 필터 계층(filter-layer)을 두고 부적절한 질의어가 반환되지 않도록 하는 것이다.

필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다는 장점이 있다. 데이터 베이스에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행하면 된다.

저장소 규모 확장

영어만 지원하는 것을 가정하였기 때문에 간단하게는 규칙에 따라 샤딩하는 방법을 생각해 볼 수 있다. (처음에는 첫 번째 글자를 기준으로, 또 그 이후에 추가적인 샤딩이 필요하다면 두 번째 글자를 기준으로 … ) 얼핏 생각하면 그럴싸해 보일 수도 있지만 균등하게 샤딩할 수 없다. (‘c’ 로 시작하는 단어가 ‘x’로 시작하는 단어보다 많다.)

따라서 별도의 샤드 관리자를 두어 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리한다.

이를 통해 균등하게 관리 될 수 있도록 한다.

4단계 마무리 

추가적으로 다루면 좋은 것들

다국어 지원이 가능하도록 확장하려면 어떻게 해야할까요?

유니코드로 데이터 저장

국가별로 인기 검색어 순위를 따로 관리하려면 어떻게 해야할까요?

국가별로 다른 트라이를 사용하도록 구성

트라이를 CDN에 저장하여 응답속도를 높이는 방법도 고려해볼 수 있음. 

실시간으로 검색 추이를 반영하려면 어떻게 해야할까요?

이 글에서 다룬 설계는 이에 적합하지 않다.

실시간 검색 추이 반영에 도움 될만한 키워드는 다음과 같다.
- 샤딩을 통하여 작업 대상 데이터의 양을 줄인다.
- 순위 모델(ranking model)을 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 한다.
- 데이터가 스트림 형태로 올 수 있기 때문에 스트림 프로세싱에 적합한 시스템을 고려한다.
(아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등이 이 그런 부류의 시스템이다.)

스터디 중에는 그래프 데이터베이스를 쓰면 어떻겠냐는 의견도 있었음.

fin.