설계 범위

• 사용자가 입력하는 단어는 자동완성될 검색어의 첫 부분
• 자동완성 검색어 표시 갯수: 5개
• 질의 빈도에 따라 정해지는 검색어 인기순으로 5개 선정
• 맞춤법 검사나 자동수정 지원 X
• 질의는 영어이지만, 시간이 허락한다면 다국어 지원
• 모든 질의는 영어 소문자로 이루어진다고 가정
• 일간 DAU 천만명

요구사항

• 빠른 응답 속도
  • 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시
• 연관성
  • 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것
• 정렬
  • 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬
• 규모 확장성
• 고가용성

개략적 규모 측정

• 평균적으로 사용자는 매일 10건의 검색 수행
• 질의할 때마다 평균적으로 20바이트의 데이터 입력
  • ASCII 사용 가정 → 1문자 = 1바이트
  • 질의문은 평균적으로 4개 단어로 구성
• 검색창에 글자를 입력할 때마다, 백엔드에 요청
  • 평균적으로 1회 검색당 20건의 요청이 전달
• 대략 초당 24,000건의 질의(QPS) 발생
• 질의 가운데 20% 정도는 신규 검색어 → 매일 0.4GB의 신규 데이터 시스템에 추가

개략적 설계

크게 두 부분으로 나뉜다.

• 데이터 수집 서비스: 사용자가 입력한 질의 수집 → 인기 검색어를 위해
• 질의 서비스: 주어진 질의에 다섯 개의 인기 검색어를 정렬해 반환하는 서비스

데이터 수집 서비스

질의	빈도
twitch	1
twitter	2

위와 같이 사용자가 검색한 단어를 빈도수와 함께 ‘빈도 테이블’에 저장한다.

질의 서비스

빈도 테이블을 이용해 인기 top5 검색어를 계산한다.

만약, 사용자가 ‘tw’ 를 검색창에 입력한 상태라면, ‘tw’로 시작하는 단어 중, 인기 top5 검색어를 반환하면 된다.

SELECT * FROM frequency_table
WHERE query Like 'prefix%'
ORDER BY frequency DESC
LIMIT 5

하지만 이렇게 되면, 데이터가 많아지기 떄문에 DB에 병목 현상이 발생할 수 있다.

상세 설계

트라이 자료구조

위의 관계형 데이터베이스를 이용해, 가장 인기 TOP5 다섯 개 질의문을 골라내는 방안은 효율적이지 않아, 트라이 자료구조 를 이용해 구현해보려고 한다.

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

트라이 자료 구조 핵심

• 트리 형태 구조
• 루트 노드는 빈 문자열 저장
• 각 노드는 문자열 하나 저장, 26개(알파벳 개수)의 자식 노드를 가질 수 있다.
• 각 노드는 하나의 단어, 또는 접두어를 나타낸다.

위와 같이 문자와 빈도수를 노드 안에 저장해보자

• p: 접두어(prefix)의 길이
• n: 트라이 안의 노드 개수
• c: 주어진 노드의 자식 노드 개수

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

• 해당 접두어를 표현하는 노드 찾기 → O(p)
• 해당 노드의 하위 트리 탐색하여 유효 노드 찾기 → O(c) 유효한 검색 문자열을 구성한다면, 그 노드는 유효 노드이다.
  
• 유효 노드 빈도수를 기준으로 정렬 후, 가장 인기 있는 검색 k개 찾기 → O(clogc), 정렬 시간복잡도

따라서, 가장 많이 사용된 질의어 k개를 찾는 해당 알고리즘의 시간복잡도

O(p) + O(c) + O(clogc)

최악의 경우 트리 전체를 탐색해야 할 수도 있다.

이를 방지하기 위한 2가지 방안이 있다.

접두어 최대 길이 제한

사용자가 검색어를 엄청 길게 입력하는 일은 거의 없다. 따라서 접두어의 길이를 약 50으로 생각하고 제한을 둔다면,

해당 접두어를 표현하는 노드를 탐색할 때, O(p) → O(1)로 바뀔 수 있다.

노드에 인기 검색어 캐시

말 그대로, 노드마다 인기 검색어를 캐시해 두는 방법이다.

노드마다, 위처럼 인기 검색어를 저장해 두기 때문에 장단점은 존재한다.

• 인기 검색어만큼 사용하는 저장 공간이 증가
• 빠른 응답속도

살펴본 위 2가지 방안을 적용한다면,

1. 접두어 노드 탐색 시간 복잡도 O(1)
2. 최고 인기 검색어 5개를 찾는 질의 또한 시간 복잡도 O(1)

따라서, 가장 인기있는 k개의 검색어를 찾는 알고리즘 자체의 시간복잡도는 O(1)로 나타낼 수 있다.

데이터 수집 서비스

규모 확장이 쉬운 데이터 수집 서비스를 위해서라면, 데이터가 어디에서 오고, 어떻게 이용되는 지 알아야 한다.

예를 들어, 트위터 같은 실시간 애플리케이션이라면, 검색어를 항상 신선하게 유지해야 하고, 만약 구글과 같은 애플리케이션이라면, 그렇게까지 실시간일 필요는 없다.

지금까지 봤던 설계안은 2가지 문제점이 있는데, 이걸 개선해보자.

• 매일 수천만 건의 질의가 입력될 텐데, 질의가 입력될 때마다 트라이를 갱신한다면, 질의 서비스의 속도는 심각하게 느려질 것
• 인기 검색어는 자주 바뀌지 않을테니, 자주 갱신할 필요가 없다.

위를 반영하여 개선된 설계안

데이터 분석 로그

query	time
tree	2023-10-01 22:01:01
try	2023-10-01 22:01:05

위와 같이 검색창에 입력된 질의와 time 정보 데이터를 로그 데이터로 수집한다.

로그는 당연히 새로운 데이터가 추가될 뿐, 수정, 삭제 등의 기능이 제공되지 않는다. 또한 인덱스도 필요없다.

로그 취합 서버

위에서 살펴봤던 로그는 양이 엄청나고, 데이터 형식이 제각각일 경우가 많다.

따라서 로그 취합하는 서버를 두어, 아래와 같이 빈도수와 해당 날짜(일별)를 이용해 데이터를 취합한다.

query	time	frequency
tree	2023-10-01	12000
tree	2023-10-08	15000
toy	2023-10-01	850
toy	2023-10-09	6256

작업 서버

작업 서버는 비동기적 작업을 실행하는 서버 집합이다. 트라이 자료 구조를 만들어, 데이터베이스에 저장한다.

트라이 캐시

분산 캐시 시스템으로, 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 역할

매주, 트라이 데이터베이스의 스냅샷 갱신

트라이 데이터베이스

트라이 데이터베이스는 당연히 지속성 저장소이다.

관계형 데이터베이스는 아까 사용 안한다고 했으니, 어떤 선택지가 있을까?

1. 문서 저장소: 새 트라이를 매주 만들어, 직렬화하여 DB에 저장할 수 있다.

   ex) MongoDB

2. 키-값 저장소: 트라이에 보관된 모든 접두어를 key, 각 트라이 노드에 보관된 모든 데이터를 value로 저장

질의 서비스

한 번 개략적 설계안을 개선한 후, 질의 서비스가 어떻게 동작하는 지 살펴보자.

• 검색 질의가 로드밸런서로 전송
• 로드밸런서는 해당 질의를 API 서버로 전송
• API 서버는 트라이 캐시에서 데이터를 가져와, 해당 요청에 대한 자동완성 검색어 제안 응답 구성

질의 서비스는 번개와 같이 빨라야 하기 때문에, 또 다음과 같은 최적화 방안을 생각해보자

AJAX 요청

브라우저는 보통 AJAX 요청을 보내, 자동완성된 검색어 목록을 가져온다.

장점: 요청을 보내고 받기 위한, 페이지 새로고침 필요 X

브라우저 캐싱

자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않는다.

따라서, 제안했던 검색어 리스트를 브라우저 캐시에 넣어두면, 다음 질의의 결과를 바로 브라우저 캐시에서 가져올 수 있다.

ex) 구글은 제안된 검색어를 한 시간 동안 캐시해둔다.

데이터 샘플링

대규모 시스템일 경우, 모든 질의 결과를 로깅하도록 해놓으면, CPU 자원과 저장공간을 엄청나게 소진

N개 요청 중 1개만 로깅.

트라이 연산

트라이 갱신

1. 매주 한 번 갱신: 새로운 트라이 ↔ 기존 트라이 대체 방식
2. 트라이의 각 노드를 개별적으로 갱신: 트라이가 크다면 바람직하지 못한 구조

검색어 삭제

폭력성, 짙은 혐오성과 관련된 질의어는 트라이 구조에 저장은 하되, 추천 검색어로는 들어가면 안된다.

위와 같이 캐시에서 추천 검색어를 조회하기 전, 필터 계층을 두어 부적절한 질의어를 걸러내자.

데이터베이스에서 물리적으로 삭제하는 건, 매주 트라이 구조를 업데이트 할 때, 비동기적으로 진행하면 된다.

❓ 하지만, 왜 애초에 저장할 때 걸러내지 않고, 조회할 때 필터를 거치는 건지 궁금하니 추후에 찾아보도록 해야겠다.

저장소 규모 확장

자동완성된 검색어를 사용자에게 추천하는 기능은 끝냈다.

이제 트라이 구조가 한 서버에 넣기에 너무 방대하게 커질 경우를 대비해보자.

일단 영어만 지원해도 되기 때문에, 첫 글자를 기준으로 한 샤딩을 고려해보자

• 알파벳은 26개라는 걸 감안한다면, 최대 26개의 서버를 사용할 수 밖에 없다.
• c로 시작하는 단어와 z로 시작하는 단어의 개수 차이가 너무 크다. → 각 서버에 균등하게 데이터를 배분불가능

⇒ 이를 해결하기 위해 과거 질의 데이터를 분석해, 샤딩

검색어 대응 샤드 관리자

어느 저장소 서버에 어떤 검색어가 저장되는 지에 대한 정보를 관리하는 역할

s 로 시작하는 검색어의 양이 u, v, w, x, y, z 로 시작하는 검색어를 전부 합친 것과 비슷하다면, 각각 샤드 하나씩 두어도 충분하다.

고려해야할 점

다국어 지원이 가능하다면?

비영어권 국가의 언어 지원은 트라이에 유니코드 데이터를 저장

국가별로 인기 검색어 순위가 다르다면?

국가별로 다른 트라이 사용, 트라이를 CDN에 저장하여 응답속도를 높이는 방법도 고려해볼만 하다

실시간으로 변하는 검색어의 추이 반영을 하고 싶다면?

현 설계안은 실시간 검색어를 지원하기에 적합하지 않다.

• 작업 서버가 매주 한 번씩만 작동
• 트라이를 구성하는 데 너무 많은 시간 소요

만약 실시간 검색어를 지원하고 싶다면?

• 샤딩을 통하여 작업 대상 데이터 양 감소시키기
• 순위 모델을 바꾸어 최근 검색어에 보다 높은 가중치
• 데이터가 스트리밍 된다는 것 → 데이터가 지속적으로 생성
  • 스트림 프로세싱: 아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등이 필요