요구사항

기능적 요구사항

사용자가 입력하는 단어는 검색어의 첫 부분으로 한정
5개의 자동완성 검색어가 표시
질의는 영어로만 지원
Spelling 체크 X
시스템의 계산 결과는 순위 모델에 의해 정렬

비기능적 요구사항

시스템 응답속도는 100밀리초 이내
규모 확장성: 초당 24000 건의 질의(QPS) 발생

시스템 구조

자료 구조

나이브한 아키텍처는 아래와 같음

query frequency

ramen	23
radiation	2

간단하게 질의문을 저장하는 query 필드와 빈도를 저장하는 frequency 필드를 저장하는 DB 테이블을 만들어서 SELECT * from frequency_table WHERE query LIKE 'ra%' ORDER BY frequeny DESC LIMIT 5 이렇게 질의할 수도 있겠지만 데이터가 많아지면 데이터베이스가 병목이 될 수 있음

따라서 정보를 저장하는 자료구조는 트라이(TRIE) 를 이용함

트라이는 트리 형태의 자료구조
트리의 루트 노드는 빈 문자열
각 노드는 글자 하나를 저장하며, 해당 글자 다음에 등장할 수 있는 모든 글자의 개수인 26개의 자식 노드를 가질 수 있음
각 트리 노드는 하나의 단어, 또는 prefix string 을 나타냄

p: prefix의 길이

n : 트라이 안에 있는 노드 갯수

c : 주어진 노드의 자식 노드 갯수

시간복잡도는 1. 해당 prefix 를 표현하는 노드를 찾음(O(p)) + 2. 해당 노드에서 시작하는 하위 트리 탐색하여 모든 유효 노드를 찾음(O(c) )+ 3.유효 노드를 정렬하여 가장 인기있는 검색어 k 개를 찾음(O(clogc) )

이 경우, 접두어를 최대 길이를 제한(O(p) → O(작은 상수값) ) 하거나 노드에 인기 검색어를 캐시하게 되면 시간 복잡도가 O(1) 가 바뀔 수 있게 됨. 즉 각 노드는 자식 노드 외에 해당 접두어에 대한 Top-K 정보를 저장하여 전체 트리를 탐색하지 않고도 빠르게 결과를 반환할 수 있도록 함

시스템 아키텍처

검색어 자동 완성 시스템의 서비스는 크게 2개로 나뉨

질의 서비스: 주어진 질의에 다섯 개의 인기 검색어를 정렬해서 리턴하는 서비스
데이터 수집 서비스: 사용자가 입력한 질의를 준실시간으로 수집하고 Trie 에 반영하는 서비스

Request Flow

Trie 를 단일 서버에 저장하면 한계가 있으므로 여러 노드에 분산 저장함.

Zookeeper 는 Trie 샤드의 메타데이터 관리 및 조정의 역할을 수행함(=shard map manager). 접두어 범위를 나누고 어떤 노드가 어떤 범위를 담당하는지 기록. 각 노드는 prefix 기반으로 어떤 샤드에 요청해야 하는 지를 판단할 수 있음 (=service discovery 역할)

분산 캐시를 이용하여 각 결과를 캐시해 두거나 브라우저단에서 일정 시간동안 캐싱을 해서(e.g. cache-control 헤더) 후속 질의의 결과는 캐시에서 가져올 수 있도록 한다

요청 플로우는 다음과 같음

사용자가 접두어 입력 (e.g. "ba")
Load Balancer가 임의의 서버(N1)에 요청 전달
N1은 캐시 확인 → 없으면 Zookeeper에서 어떤 노드(T2 등)가 담당하는지 확인
T2에 질의 → 자동완성 후보 받아서 캐시에 저장 + 사용자에게 응답

Data Collection Flow

데이터소스(사용자 검색 기록, 클릭한 링크 제목 .. etc)들에서 Phrase 와 Weight 쌍 수집(최근 검색 횟수, 클릭률, 검색 후 체류시간 .. etc)
(Phrase, Weight) 쌍들은 Log Streaming System (e.g. Kafka) 에서 실시간으로 스트리밍됨
실시간으로 스트리밍 되는 데이터를 기반으로 Aggregator 가 데이터를 수신하여 같은 phrase 는 계속 합쳐지게 함. 일정 주기마다 해당 phrase 에 대한 weight 를 누적해서 DB 에 저장하게 됨
집계한 데이터를 시간 단위로 NoSQL DB (e.g. cassnadra) 에 저장함.

[phrase]     [timestamp]     [sum_weight]
 "bat"       2025-06-08 10     35  
 "bat"       2025-06-08 11     18  
 "bag"       2025-06-08 11     12

이렇게 저장하면

최신 검색어에 더 높은 가중치를 둘 수 있음
오래된 phrase 는 weight 를 낮게 계산하거나 삭제하는 등의 처리를 할 수 있음

Cassandra 를 사용한 이유?:

Cassandra 는 쓰기 성능 중심 아키텍처임. LSM 트리 기반이라 디스크에 순차적으로 빠르게 기록 가능, Aggregator 가 수많은 phrase + timestamp + weight 데이터를 빠르게 기록 가능
복합 키 (Parititon Key + Clustering Columns) 조합으로 정렬된 데이터를 저장할 수 있음: phrase + timestamp 조합으로 primary key 생성하면 phrase 별로 시간 순으로 weight 를 저장하고 효율적으로 조회가 가능함
수평 확장성: 노드 추가만으로 자동 샤딩 + 리밸런싱 가능

5. 특정 시간마다 Applier 가 DB 에서 데이터를 꺼내 Trie 를 새로 구성하고 각 Trie 노드에 top-K 단어를 삽입하고, Trie 를 여러 복제 노드에 반영함

→ 추가적으로 분산 캐시에 주기적으로 트라이 데이터베이스의 스냅샷을 떠서 읽기 연산 성능을 높일 수 있다

최적화 전략

CDN 사용: 자주 요청되는 prefix 결과를 사용자 근처의 CDN 에 캐싱해두기
Prefetch 전략: ba 입력 시, bat, ball, bag 결과까지 미리 보내서 빠르게 대응한다