Type-Ahead Search Design타입어헤드 검색 설계

기능:
- 입력 접두사 기준 상위 5개 추천
- 지연시간: 100ms 이하
- 자동완성 결과: 검색 빈도 기반 정렬

규모:
- DAU 1억, 1인 평균 10회 검색, 각 검색 5번 키 입력
- QPS: 1억 × 10 × 5 / 86400 ≈ 58,000 QPS
- 피크: 약 3배 → 174,000 QPS

트라이: 접두사 공유 트리
"be", "bee", "beer", "best" 저장:

      b
      |
      e ← "be" (freq:100)
     / \
    e   s ← "bes"
    |   |
  "bee" t ← "best" (freq:300)
(freq:50)
    |
    r ← "beer" (freq:80)

접두사 "be" 입력 → 서브트리 탐색 → 상위 k개 반환

1. 노드에 top-k 캐싱:
   각 노드가 서브트리의 상위 5개 미리 저장
   조회: O(접두사 길이), 갱신 시 조상 노드 모두 업데이트

2. 접두사 해시맵:
   Map<prefix, top5_list>
   조회: O(1), 저장 공간 큼

트라이 vs 해시맵:
  트라이: 공간 효율, 접두사 공유
  해시맵: 조회 O(1), 저장 공간 큼

실시간 집계:
  [User Query] → [Kafka] → [Stream Aggregator]
                                → [Redis (접두사별 카운터)]

주기적 업데이트 (매주):
  [Hadoop/Spark 배치] → [새 트라이 빌드] → [트라이 DB 교체]
  → 약간 지연되지만 정확한 랭킹

[Browser Cache (1분)] → [CDN] → [API Server Cache (1시간)]
                                      → [Trie Store (Redis)]

전체 쿼리의 80~90%는 상위 인기 검색어
→ 캐시 히트율 매우 높음

지역화: 한국어/영어/일본어 별도 트라이