문제 이해 및 설계범위 확정개략적 규모 추정개략적 설계안 제시 및 동의 구하기데이터 수집 서비스질의 서비스상세 설계트라이 자료구조가장 많이 사용된 질의어 k개 찾는 방법접두어 최대 길이 제한노드에 인기 검색어 캐시데이터 수집 서비스데이터 분석 서비스 로그로그 취합 서버취합된 데이터작업 서버트라이 캐시트라이 데이터베이스질의 서비스최적화 방안트라이 연산트라이 생성트라이 갱신검색어 삭제저장소 규모 확장마무리
구글 검색 또는 아마존 웹 사이트 검색창에 단어를 입력하다 보면 입력 중인 글자에 맞는 검색어가 자동완성되어 표시되는 것을 볼 수 있다. 이 기능을 보통
검색어 자동완성이라 부른다.이번 장에서는 이와 관련하여 가장 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템을 설계하자
문제 이해 및 설계범위 확정
요구사항
- 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분으로 한정
- 자동완성 검색어 표시 갯수 : 5개
- 5개를 고르는 기준 → 검색어 인기 순위
- 맞춤법 검사, 자동 수정은 지원 x
- 검색은 영어로. 시간이 허락한다면 다국어 지원
- 모든 검색은 영어 소문자로 이뤄진다고 가정
- DAU(일간 능동 사용자) 기준으로 천만(10million)명의 사용자 지원해야 함
- 빠른 응답속도 : 검색어 입력시, 자동완성 검색어도 충분히 빨리 표시되어야 함 (시스템 응답속도 100밀리초 이내)
- 연관성 : 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관되어야 함
- 정렬 : 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어 있어야 함
- 규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 함
- 고가용성 : 시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용가능해야 함
개략적 규모 추정
- 일간 능동 사용자(DAU)는 천만 명
- 평균적으로 한 사용자는 매일 10건의 검색을 수행
- 질의할 때마다 평균적으로 20바이트의 데이터를 입력
- 문자 인코딩 ASCII 사용, 1문자 = 1바이트
- 질의문은 평균적으로 4개 단어로 이루어지고 각 단어는 평균적으로 다섯 글자로 구성
- 따라서 질의당 4개 단어 * 5바이트 = 20바이트
- 천만 DAU → 10,000,000사용자 * 10질의 / 일 * 20자 / 24시간 / 3600 = 24000 QPS
- 최대 QPS = QPS * 2 = 대략 48,000
- 질의 가운데 20% 정도는 신규 검색, 대략 0.4 GB 정도. 매일 0.4GB의 신규 데이터(검색어)가 시스템에 추가
개략적 설계안 제시 및 동의 구하기
개략적으로 시스템은 두 부분으로 나뉜다.
- 데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집하는 시스템.
- 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스
데이터 수집 서비스
질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정하면, 단어를 검색할때마다 빈도수가 +1 씩 증가하게 됨
질의 | 빈도 |
twitch | 1 |
twitter | 2 |
질의 서비스
위와 같은 빈도 테이블이 있을 때, 가장 많이 사용된 5개 검색어는 간단히 sql 로 조회가 가능함
데이터 양이 적을 때는 나쁘지 않은 설계안이지만, 데이터가 아주 많아지면 데이터베이스가 병목이 될 수 있음
상세 설계
트라이 자료구조
RDB를 이용해 다섯 개 질의문을 골라내는 방안은 데이터가 많아지면 효율적이지 않음
이 문제를 트라이(trie, 접두어 트리 prefix tree 라고도 함)를 사용해 해결
트라이는 문자열들을 간략하게 저장할 수 있는 자료구조로 retrieval 에서 따온 이름
트라이 자료 구조의 핵심
- 트라이는 트리 형태의 자료구조
- 이 트리의 루트 노드는 빈 문자열
- 각 노드는 글자 하나를 저장하며, 26개의 자식 노드 가질 수 있음
- 각 트리 노드는 하나의 단어, 또는 접두어 문자열 을 나타냄
이용 빈도에 따라 정렬된 결과를 찾기 위해 노드에 빈도 정보까지 저장할 필요가 있음
p: 접두어(prefix)의 길이
n: 트라이 안에 있는 노드 개수
c: 주어진 노드의 자식 노드 개수
가장 많이 사용된 질의어 k개 찾는 방법
- 해당 접두어를 표현하는 노드를 찾는다. 시간 복잡도는 O(p)
- 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드(=유효한 검색 문자열을 구성하는 노드)를 찾는다. O(c)
- 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개 찾기. 시간복잡도 O(clogc)
위 알고리즘은 직관적이지만 최악의 경우에는 k개를 찾기 위해 전체 트라이를 다 검색해야 하는 일이 생길 수 있음. 이 문제를 해결하기 위해 다음 두 가지 방법이 있다
- 접두어의 최대 길이를 제한
- 각 노드에 인기 검색어를 캐시
접두어 최대 길이 제한
사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없다. 따라서 p 값은 작은 정숫값(가령 50)이라고 가정해도 안전함
노드에 인기 검색어 캐시
각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이 검색할 필요 없음
각 노드에 인기 질의어를 캐시하면 top5 검색어 질의하는 시간 복잡도를 엄청 낮출 수 있지만, 각 노드에 질의어를 저장할 공간이 필요하게 된다는 단점도 있음. 그러나 빠른 응답속도가 아주 중요할 때는 이 정도 저장공간을 희생할 만한 가치가 있다.
위의 2가지 방법을 적용하면 시간 복잡도가 O(1)로 줄어들게 됨
- 접두어 노드 찾는것 : O(p) ~= O(1)
- 최고 인기 검색어 찾는 질의 시간 복잡도 : O(1)
데이터 수집 서비스
기본 설계안에서는 검색창에서 타이핑을 할 때마다 실시간으로 데이터를 수정했지만, 이 방법은 두 가지 문제로 크게 실용적이지 않음
- 매일 수천만 건의 질의 입력되는데, 그때마다 갱신하면 질의 서비스가 심각하게 느려질 것
- 일단 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것임. 트라이를 자주 갱신할 필요가 없음
규모 확장이 쉬운 데이터 수집 서비스를 만들려면 데이터가 어디서 오고 어떻게 이용되는지를 살펴야 한다.
트위터 같은 실시간 애플리케이션이라면 제안되는 검색어를 항상 신선하게 유지할 필요가 있지만, 구글 검색 같은 애플리케이션이라면 그렇게 자주 바꿔줄 이유는 없다.
사용방식이 달라지더라도 데이터 수집 서비스의 토대, 트라이를 만드는데 쓰이는 데이터는 보통 데이터 분석 서비스(analytics)나 로깅 서비스(logging service)로 부터 온다
데이터 분석 서비스 로그
- 검색창에 입력된 질의에 관한 원본 데이터가 보관
- 새로운 데이터가 추가만 되고 수정은 이루어지지 않음
로그 취합 서버
데이터 분석 서비스로부터 나오는 로그는 보통 양이 엄청나고 데이터 형식도 제각각이기에 이 데이터를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있도록 해야 함
데이터 취합 방식은 서비스의 용례에 따라 달라진다. 트위터와 같은 실시간 애플리케이션의 경우, 데이터 취합 주기를 보다 짧게 가져감. 대부분의 경우에는 일주일에 한 번정도로 로그를 취합해도 충분할 것
데이터 취합의 실시간성이 얼마나 중요한지 확인하는 것이 중요함
취합된 데이터
query | time | frequency |
tree | 2019-10-01 | 12000 |
tree | 2019-10-08 | 15000 |
tre | 2019-10-15 | 9000 |
toy | 2019-10-01 | 8500 |
toy | 2019-10-08 | 6256 |
toy | 2019-10-15 | 8866 |
- time : 해당 주가 시작한 날짜
- frequency : 해당 질의가 해당 주에 사용된 횟수의 합
작업 서버
주기적으로 비동기적 작업(job)을 실행하는 서버 집합. 트라이 자료구조를 만들고 트라이 DB에 저장하는 역할
트라이 캐시
트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실
트라이 데이터베이스
지속성 저장소. 트라이 db의 선택지는 다음과 같음
- 문서 저장소 : 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 DB에 저장할 수 있음. 몽고 db 같은 문서 저장소를 활용하면 이런 데이터를 편리하게 저장할 수 있음
- 키-값 저장소 : 트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능
- 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환
- 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환
질의 서비스
개략적 설계안에서 살펴본 질의 서비스는 데이터베이스를 활용하여 최고 인기 검색어 다섯개를 골라냈는데, 위 설계안은 비효율성을 개선한 새 설계안임
- 검색 질의가 로드밸런서로 전송
- 로드밸런서는 해당 질의를 api 서버로 보냄
- api 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성
- 데이터가 캐시에 없으면 DB에서 조회.
최적화 방안
- AJAX 요청 : 요청 보내기 위해 페이지 새로고침할 필요 없음
- 브라우저 캐싱 : 대부분 애플리케이션에서 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌진 않음. 그래서 브라우저 캐시에 넣어두기. 구글 검색 엔진이 이런 캐시 메커니즘을 사용함
HTTP Response header에 Cache-control 헤더를 보면
private, max-age=3600 이라 오고, 이는 요청을 보낸 사용자의 캐시에만 보관하며, 3600초 동안 유효하다는 의미임- 데이터 샘플링 : 대규모 시스템의 경우 모든 질의결과를 로깅하면 cpu 자원과 저장공간 엄청나게 소모하게 됨. 데이터 샘플링 기법은 그럴 때 유용함. 즉 N개 요청 가운데 1개만 로깅하도록 하는 것
트라이 연산
트라이 생성
트라이 생성은 작업 서버가 담당하며, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용함
트라이 갱신
트라이 갱신의 두가지 방법
- 매주 한번 갱신하는 방법. 새로운 트라이를 만든 다음에 기존 트라이를 대체
- 트라이의 각 노드를 개별적으로 갱신하는 방법(성능이 좋지 않음)
- 트라이가 작을때는 고려해봄직한 방안
- 트라이 노드를 갱신할 때는 모든 상위노드도 갱신해야 하는데, 상위 노드에도 인기 검색어 질의 결과가 저장되기 때문임
검색어 삭제
위험한 질의어를 자동완성 결과에서 제거해야 함. 이를 위한 좋은 방법은 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 하는 것임
필터 계층을 두면 필터 규칙에 따라 검색 결과를 자유롭게 변경할 수 있다는 장점이 있다.
데이터베이스에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비동기적으로 진행하면 됨
저장소 규모 확장
트라이의 크기가 한 서버에 넣기엔 너무 큰 경우에도 대응할 수 있도록 규모 확장성의 문제를 해결해보기
간단하게는 첫 글자를 기준으로 샤딩하는 방법을 생각해볼 수 있음
- 검색어를 보관하기 위해 두 대 서버가 필요하다면 ‘a’부터 ‘m’ 까지 글자로 시작하는 검색어는 첫 번째 서버에 저장, 나머지는 두 번째 서버에 저장
- 위와 같은 방식으로 하면 최대 사용가능한 서버의 대수는 26대
- 더 많은 서버 대수를 사용하기 위해서는 계층적으로 데이터를 샤딩할 수 있음(’aa’ 부터 ‘ag’ 까지는 첫번째 서버, ‘ah’ 부터 ‘an’ 가지는 두 번째 서버 …)
그러나 이와 같이하면 데이터가 각 서버에 균등하지 않을 수 있기에, 과거 질의 데이터의 패턴을 분석하여 샤딩하는 방법을 이용할 수 있다.
마무리
예상 질문 리스트
- 다국어 지원이 가능하도록 시스템을 확장하려면 어떻게 해야 할까?
⇒ 비영어권 국가에서 사용하는 언어를 지원하려면 트라이에 유니코드 데이터를 저장해야 함. 유니코드는 고금을 막론하고 세상에 존재하는 모든 문자 체계를 지원하는 표준 인코딩 시스템임
- 국가별로 인기 검색어 순위가 다르다면 어떻게 해야 하나?
⇒ 다른 트라이를 사용하도록 하면 됨. 트라이를 CDN에 저장하여 응답속도를 높이는 방법도 생각해 볼 수 있음
- 실시간으로 변하는 검색어의 추이를 반영하려면 어떻게 해야 하나
⇒ 새로운 뉴스 이벤트가 생긴다든가 하는 이유로 특정 검색어의 인기가 갑자기 높아질 수 있음. 현 설계안은 그런 검색어를 지원하기에 적합하지 않음(매주 한번씩만 갱신하기에)
- 실시간 검색어 자동완성 시스템을 구축하는 것은 복잡한 문제임. 도움될 만한 몇가지 아이디어는
- 샤딩을 통하여 작업 대상 데이터의 양을 줄인다.
- 순위 모델을 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 한다
- 데이터가 스트림 형태로 올 수 있다는 점, 즉 한번에 모든 데이터를 동시에 사용할 수 없을 가능성이 있다는 점을 고려해야 함. 데이터가 스트리밍 ↔ 지속적으로 생성된다는 의미
- 아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등이 그런 부류의 시스템임