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

https://product.kyobobook.co.kr/detail/S000001033116

가상 면접 사례로 배우는 대규모 시스템 설계 기초 | 알렉스 쉬 - 교보문고

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

 

검색어 자동완성 기능은 대부분의 서비스에서 제공하고 있는 기능이다. 하지만 이 시스템의 설계안에 대해 한번도 고민해지 않아서 주제를 보면서 더욱 흥미롭게 느껴졌다.

 

요구사항

- 사용자가 입력한 단어는 자동완성될 검색어의 첫 부분이다.

- 5개의 자동완성 검색어가 표시된다.

- 질의 빈도에 따른 검색어 인기 순위를 기준으로 보여준다.

- 맞춤법 검사나 자동수정은 지원하지 않는다.

- 질의는 영어이다. 하지만 다국어 지원을 생각해도 좋다.

- 대문자나 특수문자는 고려하지 않는다.

- DAU는 1000만명이다.

 

요구사항 분석

- 빠른 응답 속도 : 시스템 응답속도는 100밀리초 이내여야 한다.(페이스북의 검색어 자동완성 시스템 문서 참조)

- 연관성 : 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관되어야 한다.

- 정렬 : 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.

- 규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야한다.

- 고가용성 : 시스템의 일부에 장애가 발생하거나, 느려지거나, 네트워크 문제가 생겨도 시스템은 계속 사용가능해야 한다. 

 

규모 추정

- DAU : 1000만명

- 한 사용자는 매일 10건의 검색 수행

- 질의할 때마다 평균적으로 20Byte 데이터 입력

- 1회 검색당 20건의 요청이 백엔드로 전송(글자를 입력할 때마다 클라이언트는 백엔드에 요청을 보냄)

- 초당 24000건의 질의가 발생(10,000,000사용자 * 10질의 * 20자 / 24시간/ 3600초)

 

개략적인 설계안

자동완성 시스템은 두 부분으로 나뉜다.

- 데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집하는 시스템(실시간은 부적절 하지만 차후 보안하자)

- 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스

 

데이터 수집 서비스

데이터 수집 서비스는 각각의 검색어가 몇번의 질의를 받았는지 기록해 두는 시스템이다. 만약 사용자가 twitch, twitter, twitter, twillo를 순서대로 검색하면, 다음과 같이 테이블에 데이터가 변경되어간다.

 

1. twitch : 1

 

2. twitch : 1

    twitter : 1

 

3. twitch : 1

    twitter : 2

 

4. twitch : 1

    twitter : 2

    twillo : 1

 

질의 서비스

앞서 기록한 데이터 수집 서비스에서 저장한 데이터에 SQL Query를 사용해 가장 많이 사용된 5개의 검색어를 계산할 수 있다.

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

데이터 양이 적다면 나쁘지 않은 설계안이다. 하지만 데이터가 많아지면 데이터베이스가 병목이 될 수 있다. 이제 이 문제를 해결할 방법을 앞으로 알아본다.

 

상세 설계

앞선 개략적 설계안을 개선하기 위해 트라이 자료구조, 데이터 수집 서비스, 질의 서비스 순으로 살펴보자.

 

트라이 자료구조

트라이 자료구조에 대한 상세한 설명은 이미 잘 알려져 있고, 좋은 자료도 많기 때문에 생략하겠다. 하지만 트라이 자료구조의 한계를 잠깐 언급하고 이어서 한계를 극복하는 방식에 대해 이야기 하겠다.

트라이 자료구조는 탐색을 위해 O(p) + O(c) + O(clogc) 이다. 이때 p는 접두어의 길이, n은 트라이 안에 있는 노드 개수, c는 주어진 노드의 자식 노드 개수이다. 이 알고리즘은 직관적이지만 최악의 경우에는 k개의 결과를 얻으려고 전체 트라이를 다 검색해야 하는 일이 생길 수 있다. 이 문제를 해결하기 위해 접두어 최대 길이 제한, 노드에 인기 검색어 캐시 하는 방식으로 최적화를 진행한다.

 

- 접두어 최대 길이 제한

앞서 접두어의 길이 p는 시간 복잡도에 영향을 끼친다. 여기서 접두어의 길이를 상수, 예컨데 50으로 제한 한다면 O(p)는 O(1)으로 변경된다.

 

- 노드에 인기 검색어 캐시

각 노드에서 인기있는 검색어 5개를 저장해 두면 시간 복잡도를 엄청나게 낮출 수 있다. 물론 저장 공간을 많이 희생하게 된다는 단점이 있지만, 빠른 응답속도가 아주 중요할 때는 희생할 만한 가치가 있다. 

 

앞선 두가지의 최적화를 진행하면 접두어 노드를 찾는 시간 복잡도는 O(1)이 되고, 최고 인기 검색어 5개를 찾는 질의의 시간 복잡도도 O(1)이 된다. 즉, 전체 알고리즘의 복잡도도 O(1)이 된다.

 

데이터 수집 서비스

최초의 설계안은 요청이 들어올 때 마다 실시간을 데이터를 수정했다. 하지만 이 방식은 매일 수천만 건의 질의가 입력되는 요구사항에서는 심각하게 느려질 것이다. 또한 트라이가 만들어지고 나면 인기 검색어는 자주 변경되지 않기 때문에 비효율 적이다. 

이 문제들을 해결하기 위해 개선된 설계안은 다음과 같다. 아래에서 개선된 설계안의 각 컴포넌트에 대한 설명을 이어서 한다. 

- 데이터 분석 서비스 로그

데이터 분석 서비스 로그에는 사용자가 입력한 질의를 저장한다. 수정이나 삭제는 이루어지지 않으며, 로그 데이터에는 인덱스를 걸지 않는다.

Query	Time
tree	2023-01-01 22:01:02
try	2023-01-01 22:01:03
test	2023-01-01 22:01:06

- 로그 취합 서버

데이터 분석 서비스에서 적재된 로그는 일정한 주기로 검색 횟수를 취합한다. 이때 트위터와 같이 데이터의 신선도가 중요한 서비스는 자주 취합해 주고, 구글과 같은 서비스는 더 긴 주기를 가져도 좋을 것이다.

 

- 취합된 데이터

time 필드는 해당 주가 시작된 날짜를 나타낸다.

query	time	frequency
tree	2023-01-01	12000
tree	2023-01-08	15000
tree	2023-01-15	9000
toy	2023-01-01	8500
toy	2023-01-08	6256
toy	2023-01-15	8866

 

- 작업 서버

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

 

- 트라이 캐시

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

 

- 트라이 데이터베이스

Document Store와 Key-Value Store를 통해 지속성 저장소를 구현할 수 있는데, 이 책에선 키-값 저장소를 사용한다.

 

질의 서비스

개략적 설계안에서는 DB를 활용하여 인기 검색어 5개를 골라냈다. 개선된 설계안은 기존 설계안의 비효율성을 개선한 설계안이다.

 

트라이 연산

트라이는 자동완성 시스템의 핵심 컴포넌트이다. 이제 트라이 관련 연산들이 어떻게 이루어 지는지 보자.

- 트라이 생성

트라이 생성은 작업 서버가 담당하며, 취합된 데이터를 활용한다.

 

- 트라이 갱신

트라이 갱신은 매주 새로운 트라이를 만든 후에 대체하는 방법과 각각의 노드를 개별적으로 갱신하는 방법이 있다. 작가는 매주 새로운 트라이를 만드는 방법을 사용했는데, 이는 성능이 좋지 않기 때문이다.

 

- 검색어 삭제

몇몇 단어는 혐오성이 짙거나, 폭력적이거나, 성적으로 노골적인 듯 문제가 되는 검색어를 자동완성 결과에서 제거해야 한다. 이를 위해 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 하는 것을 추가할 수 있다.

 

저장소 규모 확장

영어만 지원하지 때문에 첫 글자를 기준으로 샤딩할 수 있다. 영어는 26글자니까 추가로 샤딩하기 위해서 두 번째 글자까지 샤딩할 수 있다. 하지만 모든 글자가 해당 글자로 시작되는 단어를 동일하게 가지고 있는 것은 아니다. 이를 위해서 과거 질의 데이터의 패턴을 분석해서 샤잉하는 방법을 사용한다.