[System Design Interview] 13장 검색어 자동완성 시스템

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

요구사항

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

계략적 규모 추정

• 일간 능동 사용자는 천만 명으로 가정한다.
• 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 사정한다.
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정한다.
  • 문자 인코딩 방법으로는 ASCII를 사용한다고 가정할 것이므로, 1문자 = 1바이트이다.
  • 질의문은 평균적으로 4개 단어로 이루어진다고 가정할 것이며, 각 단어는 평균적으로 다섯 글자로 구성된다고 가정할 것이다.
  • 따라서 질의당 평균 4 * 5 = 20바이트이다.
• 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자도완성 백엔드에 요청을 보낸다. 따라서 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다.
• 대략 초당 24,000건의 질의가 발생할 것이다(= 10,000,000사용자 * 10질의/일 * 20자/24시간/3600초)
• 최대 QPS = QPS * 2 = 대략 48,000
• 질의 가운데 20% 정도는 신규 검색어라고 가정할 것이다. 따라서 대략 0,4GB의 신규 데이터가 시스템에 추가된다(=10,000,000사용자 * 10질의일 * 20자 * 20%)

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

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

데이터 수집 서비스

• 데이터 수집 서비스 동작과정을 살펴보자.
• 질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정한다. figure 13-2
• 처음에 이 테이블은 비어 있는데, 사용자가 'twitch','twitter','twitter','twillo'를 순서대로 검색하면 그 상태가 아래와 같이 바뀌어 나가게 된다.

질의 서비스

• figure 13-1은 빈도 테이블 예시이다. 이 테이블은 아래 두 개의 필드가 있다.
  • query : 질의문을 저장하는 필드다.
  • frequency : 질의문이 사용된 빈도를 저장하는 필드다.

• 이 상태에서 사용자가 "tw"를 검색창에 입력하면 아래의 "top 5" 자동완성 검색어가 표시되어야 한다.(figure 13-3)

• 가장 많이 사용된 5개 검색어는 아래의 SQL 질의문을 사용해 계산할 수 있다.

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

3단계 상세 설계

• 이번에는 컴포넌트를 몇 개 골라 보다 상세히 설계하고 다음 순서로 최적화 방안을 논의할 것이다.
  • 트라이 자료구조
  • 데이터 수집 서비스
  • 질의 서비스
  • 규모 확장이 가능한 저장소
  • 트라이 연산

트라이 자료구조

• 관계형 데이터베이스를 이용해 가장 인기 있는 다섯 개 질의문을 골라내는 방법은 데이터베이스 병목 현상을 일으킨다. 이 문제를 트라이를 사용해 해결할 것이다.
• 트라이는 문자열들을 간략하게 저장할 수 있는 자료구조다.
• 트라이 자료구조의 핵심 아이디어를 살펴보면 다음과 같다.
  • 트라이는 트리 형태의 자료구조다.
  • 이 트리의 루트 노드는 빈 문자열을 나타낸다.
  • 각 노드는 글자 하나를 저장하며, 26개의 자식 노드를 가질 수 있다.
  • 각 트리 노드는 하나의 단어, 또는 접두어 문자열을 나타낸다.
• figure 13-5는 질의어 'tree','try','true','toy','wish','win'이 보관된 트라이다.

• 기본 트라이 자료구조는 노드에 문자들을 저장한다.
• 이용 빈도에 따라 정렬된 결과를 내놓기 위해서는 노드에 빈도 정보까지 저장할 필요가 있다.
• 가령 아래와 같은 빈도 테이블이 있다고 하자.

• 이 빈도 정보를 트라이 노드에 저장하게 되면 figure 13-6과 같은 상태가 될 것이다.

• 아래 세가지 용어를 정의한다.
  • p : 접두어의 길이
  • n : 트라이 안에 있는 노드 개수
  • c : 주어진 노드의 자식 노드 개수
• 가장 많이 사용된 질의어 k개의 다음과 같이 찾을 수 있다.
  • 해당 접두어를 표현하는 노드를 찾는다. 시간 복작도는 O(p)이다.
  • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. 유효한 검색 문자열을 구성하는 노드가 유효 노드다. 시간 복잡도는 O(n)이다.
  • 유효 노드들을 정렬하여 가장 일기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clogc)이다.

• 이 알고리즘의 총 시간 복잡도는 O(p) + O(c) + O(clogc)이다.
• 이 알고리즘은 직관적이지만 최악의 경우에는 k개의 결과를 얻으려고 전체 트라이를 다 거색해야 하는 일이 생길 수 있다.
• 이 문제를 해결할 방법으로는 다음의 두 가지가 있다.
  • 접두어의 최대 길이를 제한
  • 각 노드에 인기 검색어를 캐시

접두어 최대 길이 제한

• 검색어의 최대 길이를 제한할 수 있다면 "접두어 노드를 찾는" 단계의 시간 복잡도는 O(p)에서 O(1)로 바뀔 것이다.

노드에 인기 검색어 캐시

• 각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있다.
• 5~10개 정도의 자동완성 제안을 표시하면 충분하므로, k는 작은 값이다.
• figure 13-8은 개선된 트라이 구조다. 각 노드에 가장 인기 있는 검색어 다섯 가지를 저장하도록 했다.

• 앞의 두 가지 최적화 기법을 적용하면 시간 복잡도가 어떻게 달라지는지 알아보면 다음과 같다.
  1. 접두어 노드를 찾는 시간 복잡도는 O(1)이다.
  2. 최고 인기 검색어 5개를 찾는 질의의 시간 복잡도는 O(1)로 바뀐다.
• 각 단계의 시간 복잡도가 O(1)로 바뀐 덕분에 최고 인기 검색어 k개를 찾는 전체 알고리즘의 복잡도도 O(1)로 바뀌게 된다.

데이터 수집 서비스

• 지금까지 살펴본 설계안은 사용자가 검색창에 타이핑을 할 때마다 실시간으로 데이터를 수정했다. 이 방법은 다음 두 가지 문제로 실용적이지 못하다.
  • 매일 수천만 건의 질의가 입력될 텐데 그때마다 트라이를 갱신하면 질의 서비스를 심각하게 느려질 것이다.
  • 일단 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것이다. 그러니 트라이는 자주 갱신할 필요가 없다.
• figure 13-9는 데이터 분석 서비스의 수정된 설계안이다.

데이터 분석 서비스 로그

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

로그 취합 서버

• 데이터 분석 서비스로부터 나오는 로그는 보통 그 양이 엄청나고 데이터 형식도 제각각인 경우가 많다.
• 따라서 이 데이터를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있도록 해야 한다.
• 데이터 취합 방식은 우리 서비스의 용례에 따라 달라질 수 있다.
• 따라서 면접장에서 데이터 취합의 실시간성이 얼마나 중요한지 확인하는 것은 중요하다.
• 본 설계안의 경우 일주일 주기로 취합하면 충분하다고 가정할 것이다.

취합된 데이터

• figure 13-4는 매주 취합한 데이터의 사례다.

작업 서버

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

트라이 캐시

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

트라이 데이터베이스

• 트라이 데이터베이스는 지속성 저장소다.
• 트라이 데이터베이스로 사용할 수 있는 선택지로는 다음의 두 가지가 있다.
  1. 문서 저장소 : 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장할 수 있다. 몽고디비 같은 문서 저장소를 활용하면 이런 데이터를 편리하게 저장할 수 있다.
  2. 키-값 저장소 : 트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능하다.
     1. 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
     2. 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

질의 서비스

• 질의 서비스는 데이터베이스를 활용하여 최고 인기 검색어 다섯 개를 골라낸다.

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

• 질의 서비스 성능 향상을 위해 아래와 같은 최적화 방안들이 있다.
  • AJAX 요청
  • 브라우저 캐싱
  • 데이터 샘플링

트라이 연산

트라이 생성

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

트라이 갱신

• 트라이를 갱신하는 데는 두 가지 방법이 있다.
  1. 매주 한 번 갱신하는 방법 : 새로운 트라이를 만든 다음에 기존 트라이를 대체한다.
  2. 트라이의 각 노드를 개별적으로 갱신하는 방법 : 본 설계안에서는 이 방법을 채택하지 않았는데, 성능이 좋지 않아서다. 하지만 트라이가 작을때는 고려해볼 만 하다.

트라이 삭제

• 혐오성이 짙거나, 폭력적이거나, 성적으로 노골적이거나, 여러 가지로 위험한 질의어를 자동완성 결과에서 제거해야 한다.
• 이를 위한 좋은 방법은 figure 13-14와 같이 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 하는 것이다.
• 데이터베이스에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비돌기적으로 진행하면 된다.

저장소 규모 확장

• 영어만 지원하면 되기 때문에 간단하게는 첫 글자를 기준으로 샤딩하는 방법을 생각해 볼 수 있다.
  • 검색어를 보관하기 위해 두 대 서버가 필요하다면 'a'부터 'm'까지 글자로 시작하는 검색어는 첫 번째 서버에 저장하고, 나머지는 두 번째 서버에 저장한다.
  • 세 대 서버가 필요하다면 'a'부터 'i'까지는 첫 번째 서버에, 'i'부터 'r'까지는 두 번째 서버에, 나머지는 세 번째 서버에 저장한다.
• 이 방법을 쓰는 경우 사용 가능한 서버는 최대 26대로 제한되는데, 영어 알파벳에는 26자 밖에 없기 때문이다.
• 이 이상으로 서버 대수를 늘리려면 샤딩을 계층적으로 해야 한다.
• 본 설계안은 figure 13-15와 같이 과거 질의 데이터의 패턴을 분석하여 샤딩하는 방법을 사용한다.

• 검색어 대응 샤드 관리자는 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리한다.
• 예를 들어 's'로 시작하는 검색어의 양이 'u','v','w','x','y','z'로 시작하는 검색어를 정부 합친 것과 비슷하다면, 's'에 대한 샤드 하나와 나머지 검색어를 위한 샤드 하나를 두어도 충분할 것이다.