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

검색어 자동완성 (autocomplete, typehead, search-as-you-type, incremental search)에 관한 이야기.

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

요구사항

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

개략적 규모 추정

• 일간 능동 사용자(DAU) 는 약 1000만명
• 평균적으로 한 사용자 당 매일 10건의 검색을 수행한다고 가정
• 질의할 때마다 평균적으로 20바이트 의 데이터를 입력
• 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 전송
• 대략 초당 24,000건의 질의(QPS)가 발생
• 최대 QPS = QPS * 2 = 약 48,000
• 질의 가운데 20% 정도는 신규검색어라고 가정. 따라서 매일 0.4GB 의 신규 데이터가 시스템에 추가된다는 의미

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

데이터 수집 서비스(data gathering service)
사용자가 입력한 질의를 실시간으로 수집하는 시스템
데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지 않지만 설계안을 만드는 출발점으로는 괜찮음

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

데이터 수집 서비스

질의문과 사용빈도를 저장하는 빈도 테이블(frequency table)이 있다고 가정
처음에 테이블은 비어있고, 사용자가 검색하면 순차적으로 빈도 수에 카운트를 넣음

질의 서비스

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

데이터 양이 적을 때에 나쁘지 않은 설계안. 데이터가 아주 많아지면 데이터베이스가 병목이 될 가능성이 있다.

3단계. 상세 설계

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

트라이 자료구조

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

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

이 알고리즘은 직관적이지만 최악의 경우 k개 결과를 얻으려고 전체 트라이를 다 검색해야 하는 일이 발생할 수도 있다.
해결 방법으로는 1. 접두어의 최대 길이를 제한과 2. 각 노드에 인기 검색어를 캐시 하는 방법이 있다.

접두어 최대 길이 제한

사용자가 검색창에 긴 검색어를 입력하는 일은 거의 드물기에 검색어의 최대 길이를 제한해도 된다.

노드에 인기 검색어 캐시

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

데이터 수집 서비스

타이핑 내용이 변경될 때마다 실시간으로 데이터를 수정하게 되면
1. 매일 수천만 건의 질의가 입력될 텐데 그 때마다 트라이를 갱신하면 질의 서비스는 심각하게 느려질 것
2. 일단 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것. 그래서 트라이는 그렇게 자주 갱신할 필요가 없음
의 이유로 비실용적이게 된다.

데이터 분석 서비스 로그

검색창에 입력된 질의에 관한 원본 데이터가 보관됨.
새로운 데이터가 추가될 뿐 수정은 이루어지지 않으며 로그 데이터에 인덱스를 걸지 않음.

로그 취합 서버

데이터 분석 서비스로 부터 나오는 로그는 양도 많고 데이터 형식이 제각각인 경우가 대부분
-- 따라서 이 데이터를 잘 취합(aggregation)하여 시스템이 쉽게 소비할 수 있게 해야 함

데이터 취합의 실시간성에 대한 체크가 중요

취합된 데이터

작업 서버

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

트라이 캐시

분산 캐시 시스템으로 트라이 데이터 메모리에 유지하여 읽기 연산 성능을 높이는 역할
매주 트라이 DB의 스냅샷을 떠서 갱신

트라이 데이터베이스

지속성 저장소
트라이 DB로 사용할 수 있는 선택지로는

1. 문서저장소(document store) : 주기적으로 트라이를 직렬화하여 데이터베이스에 저장 가능. 몽고디비(MongoDB) 같은 문서 저장소를 활용하면 데이터 편리하게 저장 가능
2. 키-값 저장소 : 1) 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환 2) 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

질의 서비스

1. 검색 질의가 로드밸런서로 전송
2. 로드밸런서는 해당 질의를 API 서버로 보냄
3. API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성함
4. 데이터가 트라이 캐시에 없는 경우, 데이터를 DB에서 가져와 캐시에 채움. 다음에 같은 접두어에 대한 질의가 오면 캐시에 보관된 데이터를 사용해 처리할 수 있게 하기 위해서.. 캐시 미스(CACHE MISS)는 캐시 서버의 메모리가 부족하거나 캐시 서버에 장애가 있어도 발생할 수 있음

생각해 볼 만한 최적화 방안

1. Ajax 요청(request) : 요청을 보내고 받기 위해 페이지를 새로고침 할 필요가 없다는 장점
2. 브라우저 캐싱(browser caching) : 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있음. 구글 검색 엔진이 이러한 캐시 매커니즘을 사용.
3. 데이터 샘플링(data sampling) : 대규모 시스템의 경우, 모든 질의 결과를 로깅 해 놓으면 CPU 자원과 저장공간을 다량 소진하게 됨. N개의 요청 가운데 1개만 로깅

트라이 연산

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

트라이 생성

작업 서버가 담당하며, 데이터 분석 서비스의 로그나 DB로부터 취합된 데이터를 이용

트라이 갱신

1. 매주 한 번 갱신하는 방법. 새로운 트라이를 만든 다음, 기존의 트라이를 대체
2. 트라이의 각 노드를 개별적으로 갱신하는 방법. 성능이 떨어져서 트라이가 작을 때 고려해볼만한 방안.

검색어 삭제

트라이 캐시 앞에 필터 계층(filter layer)을 두고 부적절한 질의어가 반환되지 않도록 하는 것.
필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다는 장점
DB에서 해당 검색어를 물리적으로 삭제하는 것은 다음 번 업데이트 사이클에 비동기적으로 진행하면 됨.

저장소 규모 확장

트라이의 크기가 한 서버에 넣기에 너무 큰 경우에 대응할 수 있도록..
간단하게 첫 글자를 기준으로 샤딩(SHARDING) 하는 방법을 생각해볼 수 있음

4. 마무리

아이디어

1. 샤딩을 통해 작업 대상의 데이터 양을 줄임
2. 순위모델(Ranking Model)을 바꾸어 최근 검색어에 보다 높은 가중치
3. 데이터가 스트림 형태로 올 수 있다는 점. 한번에 모든 데이터를 동시에 사용할 수 없을 가능성이 있다는 점을 고려 - 이에 대한 논의를 위해서는 특정한 도메인 지식이 필요