ch13 검색어 자동완성 시스템
검색어 자동완성 시스템
가장 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템을 설계 해보자.
1단계 문제 이해 및 설계 범위 확정
면접관 과의 대화에서 요구사항을 분명히 할 것들
- 사용자가 입력하는 단어의 자동완성될 검색어의 첫 부분? 중간 부분?
- 몇 개의 자동 완성 검색어가 표시되어야하는가
- 자동완성 검색어 5개를 고르는 기준은?
- 맞춤법 검사 기능 유무
- 질의는 영어인지
- 대문자나 특수 문자 처리도 해야하는지?
- 얼마나 많은 사용자를 지원해야 하는지?
요구사항
- 빠른 응답 속도 : 100밀리초 이내
- 연관성 : 사용자가 입력한 단어와 연관된것
- 정렬 : 인기도 등의 순위 모델에 의해 정렬
- 규모 확장성 : 많은 트래픽을 감당할 수 있도록
- 고가용성 : 장애가 발생하거나 , 느려지거나, 네트워크 문제가 생겨도 계속 사용가능하게
개략적 규모 추정
- 일간 능동 사용자(DAU) : 천만명
- 평균 사용자 매일 10건의 검색 수행한다고 가정
- 질의할 때마다 평균 20바이트의 데이터를 입력한다고 가정
- 문자 인코딩 방법으로 ASCII 를 사용한다고 가정, 1문자 = 1바이트
- 질의문은 평균적으로 4개 단어로 이루어진다고 가정, 각 단어는 평균적으로 다섯 글자로 구성된다고 가정
- 질의당 평균 4 X 5 = 20 바이트
- 검색창에 글자를 입력할때마다 클라이언트가 백엔드에게 요청을 보냄, 평균 1회 검색당 20건의 요청
- 초당 24,000건의 질의(QPS)가 발생 ( = 10,000,000 사용자 X 10질의/일 X 20자 / 24시간 / 3600초)
- 최대 QPS = QPS X 2 = 대략 48,000
- 질의 가운데 20% 정도 신규검색어라 가정, 대략 0.4GB
- 매일 0.4GB 의 신규 데이터가 시스템에 추가
2단계 개략적 설계안 제시 및 동의 구하기
- 데이터 수집 서비스
- 질의 서비스
데이터 수집 서비스
사용자가 입력한 질의를 실시간으로 수집하는 시스템
질의 서비스(Query Service)
주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스
query: 질의문을 저장하는 필드 frequency : 질의문이 사용된 빈도를 저장하는 필드
가장 많이 사용된 5개 검색어 top 5에 대한 쿼리
문제
데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있다.
3단계 상세 설계
아래 컴포넌트를 골라 상세히 설계 후 최적화 방안을 세워볼 것
- 트라이(trie) 자료 구조
- 데이터 수집 서비스
- 질의 서비스
- 규모 확장이 가능한 저장소
- 트라이 연산
트라이 자료구조
트라이(접두어 트리 / prefix tree): 문자열들을 간략하게 저장할 수 있는 자료구조
- 트리형태의 자료구조
- 루트 노드는 빈 문자열을 나타냄
- 각 노드는 글자(character) 하나를 저장, 26개(해당 글자 다음에 등장할 수 있는 모든 글자개수)의 자식노드를 가질 수 있음
- 각 트리 노드는 하나의 단어 or 접두어 문자열을 나타냄
tree, try, true, toy, wish, win 와 같은 질의러를 보관한 트라이
이용 빈도에 따라 /정렬된 결과를 보여주기 위해 빈도 정보까지 포함하여 저장할 필요가 있다
노드에 빈도 정보, 질의어를 같이 저장할 수 있다.
이 트라이로 검색어 자동완성은 어떻게 구현할 수 있을까?
용어 정리
- p : 접두어(prefix) 의 길이
- n : 트라이 안에 있는 노드 개수
- c : 주어진 노드의 자식 노드 개수
가장 많이 사용된 질의어 k개를 찾는 방법
- 해당 접두어를 표현하는 노드 찾기, 시간복잡도 O(접두어의 길이만큼)
- 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾기
- 유효 노드 : 유효한 검색 문자열을 구성하는 노드 , 시간 복잡도는 O(주어진 노드의 자식 노드 개수)
- 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(주어진 노드의 자식 노드 개수 x log주어진노드의 자식노드개수)
가장 많이 사용된 질의어 2개를 찾는 상황에서 사용자가 'be'을 입력했다고 할때,
- 접두어 노드 'be'을 찾기
- 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드 찾기
- 유효 노드를 정렬하여 2개 골라내기
총 시간 복잡도 O(접두어 길이만큼) + O(주어진 노드의 자식 노드 개수) + O(주어진 노드의 자식 노드 개수 x log주어진노드의 자식노드 개수)
다 더한다
문제
최악의 경우, k개 결과를 찾기위해 전체 트라이를 다 검색해야 하는 일이 생길 수 있다.
해결
- 접두어 최대 길이 제한
- 각 노드에 인기 검색어 캐시
접두어 최대 길이 제한
- 사용자가 긴 검색어를 입력하는 일은 거의 없다.
- p값은 작은 정숫값이라고 가정해도 안전하다(50?)
- 검색어 최대 길이를 제한할 수 있다면
- 접두어 노드 찾는 단계에서 시간 복잡도는 O(1)로 바뀔것이다.
노드에 인기 검색어 캐시
k개의 인기 검색어를 저장해두면 전체 트라이를 검색하는 일은 방지할 수 있다.
5~10개 정도의 자동완성 제안을 표시하면 충분하기에, k는 작은 값이다.
다섯 개 질의를 캐시한다고 가정할때,
각 노드에 인기 검색어 5개를 저장하도록 하였다.
top 5 검색어를 질의하는 시간 복잡도를 많이 줄일 수 있음
장점
빠른 응답속도가 중요할때 좋음
단점
각 노드에 질의어를 저장할 공간이 많이 필요하게 됨
저장공간을 희생하며 속도를 올리자!
두 가지 최적화 기법을 적용하여 시간 복잡도가 어떻게 달라질까
- 접두어 노드를 찾는 시간 복잡도 O(1)로 바뀜
- 최고 인기 검색어 5개를 찾는 질의의 시간 복잡도도 O(1)로 바뀜
- 검색 결과가 이미 캐시되어 있어서
=> 최고 인기 검색어 k개를 찾는 전체 알고리즘 복잡도는 O(1)
데이터 수집 서비스
사용자가 검색창에 타이핑할 때마다 실시간으로 데이터를 수정하였다.
문제
- 매일 수천만 건의 질의가 입력되는데 그때마다 트라이를 갱신하면 질의 서비스는 느려질 것이다.
- 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것이다. 따라서 트라이는 그렇게 자주 갱신할 필요가 없다.
고민점
규모확장이 쉬운 서비스를 만들기 위해서는 데이터가 어디서 오고 어떻게 이용되는지 파악 검색어를 항상 신선하게 유지해야 하는지 ex) 트위터는 그러한데, 구글은 자주 바꿀 이유는 없을 것
데이터수집서비스의 토대는 바뀌지 않을 것
데이터 분석 서비스 로그
검색창에 입력된 질의에 관한 원본이 보관됨 새로운 데이터가 추가될 뿐 수정은 이루어지지 않음 로그 데이터에는 인덱스를 걸지 않는다.
로그 취합 서버
로그 양이 엄청나고 데이터 형식도 제각각인 경우가 많음 따라서 데이터를 잘 취합하여 시스템이 쉽게 소비할 수 있도록 해야함
데이터 취합 방식
실시간 애플리케이션에 경우 결과를 빨리 보여주는 것이 중요하므로
데이터 취합 주기를 보다 짧게 가져갈 필요가 있음
대부분은 일주일에 한 번 정도 로그를 취합해도 충분
초점둬야할 것
데이터 취합의 실시간성이 얼마나 중요한지 확인
취합된 데이터
매주 취합한 데이터
time : 해당 주가 시작한 날짜 frequency : 해당 질의가 해당 주에 사용된 횟수의 합
작업 서버(worker)
주기적으로 비동기적 작업(job)을 실행하는 서버 집합
트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할
트라이 캐시
분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실을 함
매주 트라이 데이터베이스의 스냅샷을 떠서 갱신
트라이 데이터베이스
지속성 저장소
사용할 수 있는 선택지
- 문서 저장소
- 새 트라이를 매주 만듬
- 주기적으로 트라이 직렬화하여 데이터베이스에 저장
- 몽고디비
- 키-값 저장소
- 트라이를 해시 테이블 형태로 변환 가능
- 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
- 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환
<키, 값> 쌍으로 변환
질의 서비스
- 검색 질의가 로드밸런서로 전송
- 로드밸런서는 질의를 API서버로 전송
- API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성
- 데이터가 트라이 캐시에 없는 경우, 데이터를 데이터베이스에서 가져와 캐시에 채움
- 접두어에 대한 질의가 오면 캐시에 보관된 데이터를 사용해 처리
- 캐시 미스는 캐시 서버의 메모리가 부족하거나, 캐시서버 장애가 있어도 발생할 수 있다
질의 서비스는 빨라야한다.
최적화 방안
- AJAX 요청 : 웹 애플리케이션의 경우 브라우저는 보통 AJAX 요청을 보내어 자동완성된 검색어 목록을 가져옴
- 장점 : 요청을 보내고 받기 위해 페이지를 새로고침할 필요 X
- 브라우저 캐싱 : 제안된 검색어들을 브라우저 캐시에 넣어두고 후속 질의 결과를 바로 보여주기
- 자동완성 검색어 제안 결과를 짧은 시간 안에 자주 바뀌지 않음
- 구글검색엔진이 사용
- 응답헤더에 cache-control
- private : 해당 응답이 요청을 보낸 사용자의 캐시만 보관 가능, 공용 캐시에 저장x
- max-age = 3600 : 3600초만 유효함
- 데이터 샘플링
- 대규모 시스템의 경우 모든 질의 결과를 로깅해놓으면 cpu자원, 저장공간을 엄청 소진함
- 데이터 샘플링 기법 : N개 요청 가운데 1개만 로깅하도록
- 대규모 시스템의 경우 모든 질의 결과를 로깅해놓으면 cpu자원, 저장공간을 엄청 소진함
트라이 연산
트라이 생성
작업 서버가 담당, 데이터 분석 서비스 로그, 데이터베이스로부터 취합된 데이터를 이용
트라이 갱신
갱신에는 2가지 방법이 있다.
- 매주 한번 갱신하는 방법
- 새로운 트라이를 만든 다음에 기존 트라이를 대체
- 트라이의 각 노드를 개별적으로 갱신하는 방법
- 본 설계안에서는 채택하지 않음 -> 성능이 좋지 않아서
- 트라이가 작을때는 고려해볼만한 방안
- 트라이 노드를 갱신할 떄는 그 모든 상위 노드도 갱신해야함
- 상위 노드에도 인기 검색어 질의 결과가 보관되기 때문
Ex)
검색어 'beer'의 이용 빈도를 10에서 30으로 갱신해야 한다고 할때, 해당 노드에 기록된 'beer' 이용 빈도는 30으로 바뀜 상위 노드들에 기록된 이용 빈도 수치도 전부 30으로 갱신될 것이다.
검색어 삭제
트라이 캐시앞에 필터계층을 두고 부적절한 질의어를 반환되지 않도록 한다.
장점
필터 규칙에 따라 검색 결과가 자유롭게 변경할 수 있음
해당 검색어를 물리적으로 삭제
다음번 업데이트 사이클에 비동기적으로 진행
저장소 규모 확장
트라이 크기가 한 서버에 넣기엔 너무 큰 경우에도 대응할 수 있도록 규모확장성을 어떻게 해결하면 좋을까?
요구사항에는 영어만 지원하면 되기 때문에, 첫 글자를 기준으로 샤딩 하는 방법을 생각해볼 수 있다.
-
검색어를 보관하기 위해 두 대 서버가 필요하다면 'a' 부터 'm'까지 글자로 시작하는 검색어는 첫 번째 서버에 저장하고, 나머지는 두 번째 서버에 저장
-
세 대 서버가 필요하다면 'a' 부터 'i' 까지는 첫 번째 서버에, 'j' 부터 'r' 까지는 두 번째 서버에, 나머지는 세 번째 서버에 저장
알파벳에 맞춰서 사용가능한 서버는 최대 26대로 제한
이상으로 서버 대수를 늘리기 위해서는
샤딩을 계층적으로 진행해야함
검색어 첫번째 글자는 첫 번째 레벨의 샤딩에 쓰고 두 번째 글자는 두 번째 레벨의 샤딩에 쓰기 ex) 'a' 로 시작하는 검색어를 네 대 서버에 나눠 보관한다고 할때, 'aa' ~ 'ag' 첫번째서버 'ah' ~ 'an' 두번째서버 'ao' ~ 'au' 세번째서버 나머지는 네번째 서버에 보관
문제
'c' 로 시작하는 단어가 'x'로 시작하는 단어보다 많음
데이터를 각 서버에 균등하게 배분하기 불가능
해결
과거 질의 데이터의 패턴을 분석하여 샤딩하도록
- 어느 샤드에 있는지?
- 샤드에서 데이터 추출
shard map manager : 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리
ex) 's' 로 시작하는 검색어의 양이 'u','v','w','x','y','z' 로 시작하는 검색어를 전부 합친것과 비슷하다면,
's'에 대한 샤드 하나와 'u' ~ 'z' 까지의 샤드 하나를 두어도 충분할 것이다.
4단계 마무리
면접 예상 질문
- 다국어 지원이 가능하도록 시스템을 확장하려면 어떻게 해야 할까요?
비영어권 국가에서 사용하는 언어를 지원하려면 트라이에 유니코드(unicode) 데이터를 저장해야 한다.
유니코드 : an encoding standard covers all the characters for all the writing systems of the world, modern and ancient => 세상에 모든 문자 체계를 지원하는 표준 인코딩 시스템
- 국가별로 인기 검색어 순위가 다르다면 어떻게 해야 하나요?
국가별로 다른 트라이를 사용하도록 하면 된다. 트라이를 CDN에 저장하여 응답속도를 높이는 방법도 생각해볼 수 있다.
- 실시간으로 변하는 검색어의 추이를 반영하려면 어떻게 해야 하나요?
새로운 뉴스 이벤트가 생긴다든가 하는 이유로 특정 검새어의 인기가 갑자기 높아질 수 있다. 현재 설계안은 그런 검색어를 지원하기에 적합하지 않음
- 작업 서버가 매주 한번씩만 돌도록 되어 있어서 적절하게 트라이를 갱신할 수 없음
- 때맞춰 서버가 실행된다 해도, 트라이를 구성하는 데 너무 많은 시간이 소요됨
=> 실시간 검색어 자동완성 시스템을 구축하는 것은 복잡한 문제로 이 책에서 다룰 수 있는 범위를 넘어섬
도움될 만한 아이디어
- 샤딩을 통해 작업대상 데이터양을 줄이기
- 순위 모델(ranking model)를 바꾸어 최근 검색어에 높은 가중치를 주도록
- 데이터가 스트림 형태로 올수있음, 한번에 모든 데이터를 동시에 사용할 수 없을 가능성이 있는점을 고려해야함
- 데이터가 스트리밍 된다 => 데이터가 지속적으로 생성된다.
- 특별한 종류의 시스템이 필요
- 아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등,
- 특정한 도메인 지식이 필요
다음 챕터