📌 대규모 시스템 설계 기초
13장 : 검색어 자동 완성 시스템
- 검색어를 입력하고 있을 때, 자동으로 완성되는 검색어 만들기
- 검색어 자동완성(autocomplete, typeahead, search-as-you-type, incremental search)
- 예제) 검색창에 단어를 입력했을 때 자동완성 되는 검색어들
1단계 문제 이해 및 설계 범위 확정
- 요구사항 파악하기
- 자동완성 검색어는 첫 부분인지, 중간 부분인지
- 몇 개의 검색어를 표시
- 검색어를 고르는 기준 : 인기순, 최신순
- 맞춤법 검사 기능을 제공
- 다국어 지원
- 대문자, 소문자, 특수 문자 처리 여부
- 사용자의 수는?
- 요구사항 정리하기
- 빠른 응답 속도
- 검색어의 연관성
- 정렬 : 계산 결과는 인기도 등의 순위 모델을 사용해야 한다.
- 규모 확장성 : 트래픽을 감당할 수 있도록 확장 가능해야 한다.
- 고가용성 : 일부에 장애가 발생하더도, 시스템은 계속 실행되어야 한다.
- 개략적 규모 추정
- 일간 사용자 천 만명 가정
- 한 사용자는 평균적으로 일일 10건 검색
- 평균적으로 20바이트의 데이터를 입력한다고 가정
- 문자 인코딩 방법은 ASCII를 사용하면 1문자 = 1바이트
- 평균적으로 질의문은 4개의 단어로 이루어져 있다.
- 각 단어는 평균적으로 다섯 글자로 구성
- 결과 = 질의당 평균 4 X 5 = 20 바이트
- 검색 창에 글자를 입력하면, 클라이언트는 백엔드에 요청을 보낸다.
- 평균적으로 1회 검색당 20건의 요청이 백엔드에 전달
- 계산 = 1000만 사용자 X 10 질의 / 일 X 20자 / 24시간 / 3600초)
- 초당 24000건의 QPS
- 질의 중에 20%가 신규 검색어라면, 1000만 사용자 X 10질의 / 일 X 20자 X 20%
- 0.4GB의 신규 데이터가 시스템에 추가된다.
2단계 개략적 설계안 제시 및 동의 구하기
- 데이터 수집 서비스(data gathering service)
- 질의 서비스(query service)
데이터 수집 서비스
- 사용자가 입력한 질의를 실시간으로 수집하는 서비스
- 데이터가 많은 애플리케이션에서는 어려운 작업
- 질의문과 사용빈도를 저장하는 빈도 테이블(frequency table)이 있다고 가정
질의 서비스
- 주어진 질의에 다섯 개의 인기 검색어를 정렬하는 서비스
- 주어진 빈도 테이블
- query : 질의문을 저장하는 필드
- frequency : 질의문이 사용된 빈도를 저장하는 필드
- 사용자가 "tw" 를 검색하게 되면, 아래와 같이 자동 완성 검색표가 완성 되어야 한다.
검색어 : tw
twitter
twitch
twilight
twin peak
twitch peak
SELECT * FROM frequency_table
WHERE query Like `prefix%`
ORDER BY frequency DESC
LIMIT 5
- 하지만 위와 같이 설계한다면, 데이터가 많아질 때 데이터베이스의 병목 현상이 일어날 수 있다.
3단계 상세 설계
- 트라이(trie) 자료구조
- 데이터 수집 서비스
- 질의 서비스
- 규모 확장이 가능한 저장소
- 트라이 연산
트라이 자료구조
- 관게형 데이터베이스를 사용할 때 가장 인기 있는 다섯 개의 질의문을 골라내는 방법은 효율적 X
- 트라이 자료구조로 해결
- 트라이
- 문자열들을 간략하게 저장할 수 있는 자료구조
- 트리 형태의 자료구조
- 루트 노드는 빈 문자열
- 각 노드는 하나의 문자만 저장한다.
- tree, try, true, toy, wish, win 질의어를 트라이에 보관할 때
- 빈도를 따라 정렬해야 하기 때문에, 빈도 정보를 저장할 빈도 테이블
- 질의어 찾는 방법
- p(접두어 길이), n(트라이 노드 개수), c(주어진 노드의 자식 노드 개수)
- 해당 접두어를 표현하는 노드를 찾기 -> O(p)
- 해당 노드부터 시작하는 하위 트리를 탐색해서, 모든 유효 노드를 찾는다. -> O(c)
- 유효 노드를 정렬해서 가장 인기 있는 k개를 찾는다. -> O(clogc)
- 예시 : k = 2, 질의어 'be'
- 접두어 노드 'be' 찾기
- 해당 노드의 하위 트리들을 탐색해서 모든 유효 노드를 찾는다.
- 유효 노드를 정렬해서 2개만 고른다.
- 최악의 경우에는 전체 트라이를 검색해야 하는 문제 발생
- 해결 방법
- 접두어 최대 길이 제한 두기
- 각 노드에 인기 검색어를 캐시
데이터 수집 서비스
- 계속 대용량의 데이터를 트라이에 갱신하면 성능 저하
- 인기 검색어는 자주 바뀌지 않을 것이기 때문에 자주 갱신할 필요가 없다.
- ex. 트위터는 검색어를 자주 갱신해주어야 하지만, 구글 같은 경우 자주 바꿔줄 필요 X
- 데이터 분석 서비스 로그 : 검색창에 입력된 질의에 대한 원본 데이터
- 로그 취합 서버 : 제각각인 데이터 형식들을 잘 집계(aggregation) 해서 쉽게 소비할 수 있도록 한다.
- 트위터 같이 결과를 빨리 보여줘야 하면 데이터 취합 주기를 짧게, 대부분의 경우 일주일에 한 번 정도 로그를 취합해도 된다.
- 취합된 데이터 : time, frequency 필드를 통해 해당 쿼리에 대한 시작한 날짜, 해당 주에 사용된 횟수의 합을 저장한다.
- 작업 서버 : 주기적으로 비동기적 작업을 실행하는 서버 집합
- 트라이 자료구조를 만들고, 트라이 데이터베이스에 저장하는 역할
- 트라이 캐시 : 분사 산 캐시 시스템으로, 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높인다. 매주 갱신하도록 한다.
- 트라이 데이터베이스 : 지속성 저장소. 문서 저장소 or 키 값 저장소 형태로 사용
- 문서 저장소(document store)
- 새 트라이를 매주 만들어야 해서, 주기적으로 트라이를 직렬화하여 DB에 저장
- MongoDB 같은 문서 저장소 활용
- 키 값 저장소
- 해시 테이블 형태로 변환
- 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
- 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환
질의 서비스
- 검색 질의가 로드 밸런서로 전송
- 로브 댈런서가 해당 질의를 API 서버에 전송
- API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답 구성
- 데이터가 트라이 캐시에 없는 경우의 데이터는 데이터베이스에서 가져와서 캐시에 채운다.
트라이 연산
- 트라이 생성 : 작업 서버 담당. 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용
- 트라이 갱신
- 매주 한 번 갱신해서 기존 트라이를 대신 하는 방법
- 각 노드를 개별적으로 갱신하는 방법 -> 트라이가 적을 때만 좋다.
- 트라이 노드를 갱신할 때 그 위의 상위 노드도 갱신해야 하기 때문
- 검색어 삭제
- 폭력적인 질의어는 자동완성에서 제거한다.
- 트라이 캐시 앞에 필터 계층(Filter layer)을 두고 부적절한 질의어가 반환되지 않도록 한다.
- 검색어를 물리적으로 삭제하는 것은 다음 업데이트에 비동기적으로 진행
저장소 규모 확장
- 서비스 크기가 확장될 때 규모를 확장할 수 있도록 해결한다.
- 첫 글자 기준으로 샤딩(sharding) 해보기
- 영어는 26개의 알파벳으로 이루어져 있다.
- 서버 2개인 경우, a부터 m까지 첫 번째 서버, 나머지 두 번째 서버
- 서버 3개인 경우, a부터 i까지 첫 번째 서버, ...
- 다른 방법으로는 샤딩을 계측적으로
- 첫 번째 샤딩에 첫 번째 글자
- 두 번째 샤딩에 두 번째 글자
- 하지만 데이터가 균등하지 않게 분배되는 문제가 생길 수 있따.
- ex. c로 시작하는 단어가 x로 시작하는 단어보다 많은 경우
- 검색어 대응 샤드 관리자(shard map manager)로 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리한다.
4단계 마무리
- 다국어 지원을 하려면?
- 트라이에 유니코드(Unicode) 데이터를 저장해야 한다.
- 유니코드 : 모든 문자 체계를 지원하는 표준 인코딩 시스템
- 국가별로 인기 검색어 순위가 다르면?
- 국가별로 다른 트라이를 사용
- 트라이를 CDN에 저장해서 응답속도 개선
- 실시간으로 변하는 검색어 추이를 반영하려면?
- 스트림 프로세싱에 필요한 시스템
- 하둡 맵리듀스, 스파크, 카프카 등이 필요하다.