검색어 자동완성 시스템 (대시설기)

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

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

• 입력 단어는 자동완성될 검색어의 첫 부분
• 5개의 자동완성 검색어 표시
• 인기순
• 맞춤법 x, 자동 수정 x
• 모든 질의는 영어 소문자
• DAU 기준으로 천만명

요구사항

• 빠른 응답 속도 - 시스템 응답속도는 100ms
• 연관성
• 정렬 - 인기순
• 규모 확장성 - 많은 트래픽
• 고가용성 - 페일오버

개략적 규모 추정

• DAU 천만명
• 한 사용자는 매일 10건의 검색
• 질의할 때마다 평균 20바이트 데이터 입력
• 검색창에 금자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다.
• 초당 24,000건의 질의(QPS)가 발생할 것
• 최대 QPS = QPS * 2 = 48,000
• 질의 가운데 20% 정도는 신규 검색어라고 가정 → 매일 0.4GB의 신규 데이터가 시스템에 추가

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

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

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

데이터 수집 서비스

질의문과 시용빈도를 저장하는 빈도 테이블이 있다고 가정

질의 서비스

빈도 테이블은 두 개의 필드가 있다.

• query
• frequency

가장 많이 사용된 5개 검색어는 SQL 질의문으로 계산할 수 있다.

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

3단계 상세 설계

최적화 방안 논의

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

트라이 자료구조

관계형 데이터베이스는 효율적이지 않다. → 트라이를 사용해 해결

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

핵심 아이디어

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

기본 트라이 자료구조는 노트에 문자들을 저장한다. 빈도까지 저장할 필요가 있다.

용어 정리

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

가장 많이 사용된 질의어 k개 찾는 방법

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

해당 알고리즘은 직관적이지만 최악의 경우에는 k개 결과를 얻으려고 전체 트라이를 다 검색해야 하는 일이 생길 수 있다.

해결 방법 2가지

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

접두어 최대 길이 제한

사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다. 접두어 노드를 찾는 단계의 시간복잡도는 O(p) 에서 O(1)로 바뀔 것이다.

노드에 인기 검색어 캐시

각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있다.각 노드에 공간이 많이 필요하지만 빠른 응답속도가 아주 중요할 때는 희생할 만한 가치가 있다.

데이터 수집 서비스

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

실용적이지 못한 이유 2가지

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

데이터 분석 서비스의 수정된 설계안

데이터 분석 서비스 로그 → 로그 취합 서버 → 취합된 데이터 → 작업 서버 → (매주 갱신) 트라이 데이터베이스 → (매주 데이터베이스의 상태를 스냅샷) 트라이 캐시

트라이 데이터베이스

2가지 선택지

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

질의 서비스 최적화 방안

• AJAX 요청: 페이지를 새로고침 할 필요가 없다.
• 브라우저 캐싱: 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져갈 수 있다.
• 데이터 샘플링: 요청이 많을 때 N개 요청 중 1개만 로깅하도록 하는 것

트라이 연산

1. 매주 한 번 갱신하는 방법
2. 트라이의 각 노드를 개별적으로 갱신하는 방법 → 성능이 좋지 않다.

검색어 삭제

혐오성이 짙거나, 폭력적인 위험한 질의어를 제거한다. 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 한다.

저장소 규모 확장

첫 글자 기준으로 샤딩하는 방법 → 샤드 관리자가 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리한다.