개요
구글 검색이나 아마존 웹 사이트 검색창에 단어를 입력하면 위 글미처럼 글자에 맞는 검색어가 자동으로 완성되어 표시된다. 이러한 검색어 자동완성 시스템을 설계해보자.
1단계 문제 이해 및 설계 범위 확정
설계에 앞서 질문을 통해 요구사항을 명확히 하자.
지원자: 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분이어야 하나요? 아니면 중간 부분이 될 수도 있습니까?
면접관: 첫 부분으로 한정하겠습니다.
지원자: 몇 개의 자동완성 검색어가 표시되어야 합니까?
면접관: 5개입니다.
지원자: 자동완성 검색어 5개를 고르는 기준은 무엇입니까?
면접관: 질의 빈도에 따라 정해지는 검색어 인기 순위를 기준으로 삼겠습니다.
지원자: 맞춤법 검사 기능도 제공해야 합니까?
면접관: 아뇨. 맞춤법 검사나 자동수정은 지원하지 않습니다.
지원자: 질의는 영어입니까?
면접관: 네. 하지만 시간이 허락한다면 다국어 지원을 생각해도 좋습니다.
지원자: 대문자나 특수 문자 처리도 해야 합니까?
면접관: 아뇨. 모든 질의는 영어 소문자로 이루어진다고 가정하겠습니다.
지원자: 얼마나 많은 사용자를 지원해야 합니까?
면접관: 일간 능동 사용자(DAU) 기준으로 천만(10million) 명입니다.
Plain Text
복사
위 대화를 통해 요구사항을 정리하면 다음과 같다.
•
빠른 응답 속도 : 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빠르게 표시되어야 한다. 페이스북 검색어 자동완성 시스템에 관한 문서에는 시스템 응답속도가 100ms 이내여야 한다고 나와있다.
•
연관성 : 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.
•
규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야한다.
•
고가용성 : 시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 발생해도 시스템은 계속 사용 가능해야 한다.
개략적 규모 추정
•
일간 능동 사용자(DAU)는 천만 명으로 가정
•
평균적으로 한 사용자가 매일 10건의 검색을 수행한다고 가정
•
질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정
◦
문자 인코딩 방법으로는 ASCII를 사용한다고 가정(1문자 = 1바이트)
◦
질의문은 평균적으로 다섯 글자로 구성된 4개의 단어로 이루어진다고 가정
◦
질의당 평균 4 x 5 = 20 바이트
•
검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보내기 때문에, 평균적으로 1회 검색당 20건의 요청이 발생
•
대략 초당 24,000건의 질의(QPS)가 발생할 것으로 예상
◦
10,000,000 사용자 x 10query/1일 x 20자 / 24시간 / 3600초
•
최대 QPS = QPS x 2 = 48,000
•
질의 중 20%는 신규 검색어로 가정
◦
10,000,000 사용자 x 10query/1일 x 20자 x 20% = 0.4GB
◦
매일 0.4GB의 신규 데이터가 시스템에 추가
2단계 개략적 설계안 제시 및 동의 구하기
검색어 자동완성 시스템은 개략적으로 두 부분으로 나뉜다.
•
데이터 수집 서비스(data gathering service) : 사용자가 입력한 질의를 실시간으로 수집하는 시스템
•
질의 서비스(query service) : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 반환하는 서비스
데이터 수집 서비스
위 그림은 질의문과 사용빈도를 저장하는 frequency table이 있는 상황에서 twitch, twitter, twitter, twilo를 순서대로 검색하면 상태 변화를 나타낸 것이다.
질의 서비스
•
query : 질의문을 저장하는 필드
•
frequency : 질의문이 사용된 빈도를 저장하는 필드
이런 테이블이 있다고 할 때, 사용자가 “tw”를 입력하면 아래의 이미지처럼 top5 자동완성 검색어가 표시되어야 한다.
이와 같은 결과는 다음 SQL 쿼리르 사용해 얻을 수 있다.
SELECT * FROM frequency_table
WHERE query LIKE 'prefix%'
ORDER BY frequency DESC
LIMIT 5
SQL
복사
이런 설계는 데이터가 적을 때는 나쁘지 않지만, 데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있다. 상세 설계안에서 이 문제를 해결할 방법을 찾아보자.
3단계 상세 설계
상세 설계에서는 다음의 컴포넌트를 상세히 설계하고 최적화 방안을 논의해보자.
•
트라이(trie) 자료구조
•
데이터 수집 서비스
•
질의 서비스
•
규모 확장이 가능한 저장소
•
트라이 연산
트라이 자료구조
관계형 데이터베이스를 통해 가장 인기 있는 질의문을 골라내는 방안은 효율적이지 않다. 이 문제는 트라이(trie, 접두어 트리)를 통해 해결할 수 있다.
트라이는 문자열들을 간략하게 저장할 수 있는 자료구조이다. retrieval이라는 단어에서 유래된 이름에서도 알 수 있듯, 문자열을 꺼내는 연산에 초점을 맞추어 설계된 자료구조이다. 트라이 자료구조의 핵심 아이디어는 다음과 같다.
•
트라이는 트리 형태의 자료구조이다.
•
트리의 루트 노드는 빈 문자열을 나타낸다.
•
각 노드는 글자(character) 하나를 저장하며, 해당 글자 다음에 등장할 수 있는 글자의 개수(여기에서는 26개)만큼 자식 노드를 가질 수 있다.
•
각 트리 노드는 하나의 단어 또는 접두어 문자열을 나타낸다.
위 그림은 ‘tree’, ‘try’, ‘true’, ‘joy’, ‘wish’, ‘win’이 보관된 상태의 트라이를 나타낸다. 여기서 굵은 선은 질의어를 나타낸다.
단어들의 사용빈도와 위와 같다고 하면,
트라이 트리에서는 이처럼 저장되어 있을 것이다.
용어를 몇 가지 정의하고 알고리즘을 살펴보자.
•
p : 접두어(prefix)의 길이
•
n : 트리 안에 있는 노드 개수
•
c : 주어진 노드의 자식 노드 개수
가장 많이 사용된 질의어 k개는 다음과 같이 찾을 수 있다.
•
해당 접두어를 표현하는 노드를 찾는다. - 시간 복잡도 O(p)
•
해당 노드부터 시작하는 하위 트리를 탑색하여 모든 유효한 검색 문자열을 구성하는 노드를 찾는다. - 시간 복잡도 O(c)
•
유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. - 시간 복잡도 O(c log c)
사용자가 ‘be’를 입력 했을 때 인기 검색어를 찾는 과정은 다음과 같다.
1.
접두어 노드 ‘be’ 찾기
2.
해당 노드부터 하위 트리를 탐색하여 모든 유효 노드 찾기
3.
유효 노드를 정렬하여 2개 골라내기
4.
결과 반환 [best:35], [bet:29]
이 알고리즘의 시간 복잡도는 위의 각 단계에서 소요된 시간의 합이므로, O(p) + O(c) + O(c log c)이다.
이 알고리즘은 직관적이지만 최악의 케이스에서 k개 결과를 얻기위해 전체 트라이를 다 검색하는 일이 발생할 수 있다. 이 문제를 해결할 방법은 다음 두 가지이다.
•
접두어의 최대 길이 제한
•
각 노드에 인기 검색어를 캐시
접두어 최대 길이 제한
사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다. 따라서 p값은 작언 정수라고 가정해도 안전하다. 검색어의 최대 길이를 제한할 수 있다면, 접두어 노드를 찾는 단계의 시간 복잡도를 O(p)에서 O(작은 상수값)=O(1)로 바뀔 것이다.
각 노드에 인기 검색어 캐시
각 노드에 k개의 인기 검색어를 저장해두면 전체 트라이를 검색하는 일을 방지할 수 있다. 5 ~ 10개 정도의 자동완성 제안을 표시하면 충분하기 때문에, k는 작은 값일 것이다.
각 노드에 캐시를 한다면, top5 검색어를 질의하는 시간 복잡도를 엄청나게 낮출 수 있다. 하지만 각 노드에 질의어를 저장할 공간이 많이 필요하게 된다는 단점도 있다. 빠른 응답 속도가 중요하다면, 이런 저장공간을 희생할만한 가치가 있을 수 있다.
이와 같이 트라이 구조를 개선하면, 각 노드에서 가장 인기 있는 검색어를 찾는 시간 복잡도를 O(1)로 낮출 수 있다.
데이터 수집 서비스
사용자가 검색창에 뭔가를 타이핑 할 때마다 실시간으로 데이터를 수정하면 다음 두 가지 문제로 그다지 실용적이지 않다.
•
매일 수천만 건의 질의가 입력될텐데, 그때마다 트라이를 갱식하면 질의 서비스가 심각하게 느려질 것이다.
•
트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것이니, 트라이를 그렇게 자주 갱신할 필요가 없다.
규모 확장이 쉬운 데이터 수집 서비스를 만들기 위해서는, 데이터가 어디서 오고 어떻게 이용되는지를 살펴봐야 한다. 트위터 같은 실시간 애플리케이션이라면 제안되는 검색어를 신선하게 유지할 필요가 있지만, 구글 검색 같은 경우에는 그렇게 자주 바꿔줄 필요는 없을 것이다.
위 그림의 컴포넌트들을 하나씩 살펴보자.
데이터 분석 서비스 로그
데이터 분석 서비스 로그에는 검색창에 입력된 질의에 대한 원본 데이터가 보관된다. 새로운 데이터를 추가될 뿐 수정은 이루어지지 않고, 로그 데이터는 인덱스를 걸지 않는다.
로그 취합 서버
데이터 분석 서비스에서 저장되는 로그는 양이 엄청나게 많고, 데이터 형식이 제각각인 경우가 많다. 따라서 이런 데이터를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있게 만들어야 한다.
트위터 같은 실시간성이 중요한 애플리케이션에서는 결과를 빨리 보여주는 것이 중요하므로, 데이터 취합 주기를 짧게 가져갈 필요가 있을 수 있다. 일반적인 경우라면 일주일에 한 번 정도로 로그를 취합해도 충분할 것이다.
취합된 데이터
매주 데이터를 취합하여 저장해둔다.
여기서 time은 해당 주가 시작한 날짜를 나타낸다.
작업 서버
작업 서버는 주기적으로 비동기 작업을 통해 트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당한다.
트라이 캐시
트라이 캐시는 분산 캐시 시스템으로, 트라이 데이터를 메모리에 유지하여 읽기 성능을 높인다. 매주 트라이 데이터베이스의 스냅샷을 떠서 갱신한다.
트라이 데이터베이스
지속성 저장소를 통해 트라이 데이터를 저장해 데이터베이스를 구축한다.
1.
문서 저장소(document storage) : 새 트라이를 매주 만들 것이기 때문에, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장할 수 있다. MongoDB 같은 문서 저장소를 활용해 편리하게 저장할 수 있다.
2.
키-값 저장소(key-value storage) : 트라이를 해시 테이블 형태로 변환하여 저장한다.
•
트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
•
각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환
질의 서비스
위 그림은 개선한 설계안을 통해 질의를 수행하는 과정이다.
1.
검색 질의가 로드밸런서로 전송
2.
로드밸런서가 해당 질의를 API로 전송
3.
API 서버가 트라이 캐시에서 데이터를 가져와 자동완성 검색어 제안 응답을 구성
4.
트라이 캐시에 데이터가 없는 경우, 데이터베이스에서 데이터를 가져와 캐시에 채움
추가적으로 다음과 같은 질의 서비스의 최적화 방안을 생각해볼 수 있다.
•
AJAX 요청 : 웹 애플리케이션의 경우 브라우저는 보통 AJAX 요청을 통해 자동완성된 검색어 목록을 받아온다. 이를 통해 요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없다는 것이다.
•
브라우저 캐싱 : 대부분 애플리케이션의 경우 자동완성 검색어 제안 결과는 자주 바뀌지 않는다. 따라서 그 결과를 브라우저 캐시에 넣어두어 최적화 할 수 있다. 구글 검색 엔진이 이런 캐시 메커니즘을 사용한다.(1시간 동안 유지되는 private 캐시로 저장)
•
데이터 샘플링 : 대규모 시스템은 모든 질의 결과를 로깅하도록 해놓으면 CPU와 저장공간을 엄청나게 소진하게 된다. N개의 요청 가운데 1번만 로깅하도록 데이터를 샘플링하는 것이 유용할 것이다.
트라이 연산
트라이 관련 연산이 어떻게 동작하는지 살펴보자.
트라이 생성
트라이 생성은 작업 서버가 담당하고, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용한다.
트라이 갱신
트라이를 갱신하는데는 두 가지 방법이 있다.
1.
전체 갱신 : 새로운 트라이를 만든 다음 기존 트라이를 대체한다.
2.
개별 갱신 : 트라이의 각 노드를 개별적으로 갱신하는 방법이다. 다만 트라이 노드를 갱신할 때 상위 노드도 같이 갱신하는데, 때문에 이 방식은 성능이 좋지 않고 트라이가 작을 때나 고려해볼만 하다.
검색어 삭제
혐오성이 짙거나, 폭력적이거나, 성적으로 노골적이거나 여러 가지로 위험한 질의어를 자동완성 결과에서 제거해야 한다. 이를 위한 좋은 방법은 트라이 캐시 앞에 필터 계층을 두고, 필터 규칙에 따라 부적절한 질의어가 반환되지 않도록 하는 것이다. 데이터를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행하면 된다.
저장소 규모 확장
트라이의 크기가 한 서버에 넣기에는 너무 큰 경우에도 대응할 수 있도록 규모 확장성 문제를 해결해볼 필요가 있다. 여기에서는 영어 소문자만 지원하기 때문에, 간단하게는 첫 글자를 기준으로 샤딩해보는 방법이 있을 것이다.
•
두 대의 서버에 나누어 저장한다면, ‘a’부터 ‘m’까지 글자로 시작하는 검색어는 첫 번째 서버에 넣고 나머지는 두 번째 서버에 저장한다.
•
세 대의 서버에 나누어 저장한다면, ‘a’부터 ‘i’까지 첫 번째 서버에, ‘j’부터 ‘r’까지를 두 번째 서버에, 나머지를 세 번째 서버에 저장한다.
위 방법의 경우 영어 알파벳이 26글자 밖에 없기 때문에, 26대를 넘어서 샤딩을 할 필요가 있다면 계층적으로 샤딩을 해야한다. 이 방법은 얼핏 생각하기에는 균등한 것처럼 보이지만, ‘c’로 시작하는 단어가 ‘x’로 시작하는 단어보다 많다는 것을 생각해보면 균등하게 배분하기가 불가능하다.
이 문제를 해결하기 위해 과거 질의 데이터 패턴을 분석해 샤딩하는 방법을 사용할 수 있다.
검색어 대응 샤드 관리자는 어떤 검색어가 어느 저장소 서버에 저장되는지를 관리하고, 그를 통해 샤드에 접근하는 방식이다. 이를 통해 각 샤드에 데이터를 균등하게 저장하도록 구성할 수 있다.
4단계 마무리
시간이 남는다면 몇 가지를 추가로 논의해볼 수 있다.
•
다국어 지원이 가능하도록 시스템을 확장하기
◦
트라이에 유니코드 데이터를 저장하여 해결
•
국가별로 인기 검색어 순위가 다른 경우
◦
국가별로 트라이를 분리하여 사용
◦
트라이를 CDN에 저장하여 응답 속도를 높이는 것도 가능
•
실시간으로 변하는 검색어 추이를 반영하고 싶다면
◦
현 설계는 작업 서버가 주마다 돌기 때문에 적절하게 트라이를 갱신하기 어려움
◦
설사 때맞춰 실행하더라도, 트라이를 구성하는데 시간이 많이 소요
◦
설계 범위를 벗어나기 때문에 논의하지 않을 것
◦
하지만 실시간 추이 구현을 위한 추가적인 아이디어들
▪
샤딩을 통해 작업 대상 데이터의 양을 줄이기
▪
순위 모델(ranking model)을 바꾸어 최근 검색어에 높은 가중치 부여하기
▪
데이터가 스트림 형태로 오게 되어, 한 번에 모든 데이터를 동시에 사용할 수 없을 가능성이 있다는 점을 고려