검색어 자동완성 시스템 아키텍처!- 트라이구조에 대해서

안녕하세요!! 트윅히입니다.

 

가상 면접 사례로 배우는 대규모 시스템 설계 기초 책을 보면서 후기를 작성하다가

부분 부분 정리하고 좀 더 함께 정리해두면 좋을 것 같은 부분이 있더라구요

그래서 준비해보았습니다.!! 2탄

 

그리고 검색어 자동완성 시스템 같은 경우에는 평상시에도 어떻게 구현되어 있는지

굉장히 궁금해 했던 부분이에요!

직업병이 있다보니 모든 서비스를 볼 때 마다 어떤식으로 구현했는지

어떻게 작동되고 있는지 혼자 생각해볼 때가 많은데 ㅋㅋㅋㅋ

검색어도 그 중 하나였습니다. ㅎㅎㅎ 그래서 더 좀 흥미롭게 책도 읽을 수 있었어요

 

---

요구사항

책에서 배경으로 깔았던 요구 사항은 다음과 같다.

- 빠른 응답 속소 100 밀리초 이내

- 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.

- 시스템의 계산 결과는 인기도등의 순위 모델에 의해 정렬되어 있어야 한다.

- 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야한다.

- 시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능해야한다.

 

---

이 책에서 저자도 말하지만

rdb로는 한계가 있을 것이라고 말한다. (이에 무척 동감.. 나도 혼자 rdb로 구현하는 상상을 해봤는데 아닌 것 같았음)

 

책에서도 더 다양한 요구사항을 다루지 못했고 엄청 딥하게 들어가진 않은 것 같다..

 

트라이 자료 구조를 사용하는 것이 이 설계의 시작점이다!

트리 자료구조와 트라이 자료구조에 대해서 알아보쟈!!

 

---

트리 자료구조? 트라이 자료구조??

한 줄 요약

Tree는 개념(범용), Trie는 문자열 검색에 특화된 Tree다.

 

1️⃣ 트리(Tree) 자료구조

뭐냐면

• 계층 구조를 표현하는 가장 일반적인 자료구조
• 부모–자식 관계
• 각 노드는 아무 값이나 가질 수 있음

특징

• 루트 1개
• 사이클 없음
• 자식 수 제한 없음 (일반 트리)
• 깊이, 높이, 서브트리 같은 개념 존재

예시

 

회사 / 개발팀 기획팀 / 백엔드

대표적인 트리들

• Binary Tree
• BST
• AVL / Red-Black Tree
• Heap

👉 용도가 굉장히 넓음

 

2️⃣ 트라이(Trie) 자료구조

뭐냐면

• 문자열 집합을 저장하고 검색하기 위한 트리
• 보통 prefix(접두사) 기반 탐색

특징 (여기가 핵심)

• 노드 하나가 문자 1개를 의미
• 루트는 보통 빈 문자열
• 경로(path) 자체가 문자열
• 깊이 = 문자열 길이
• 검색 시간: O(문자열 길이)

예시 (apple, app 저장)

 

(root) | a | p | p* / \ l (end) | e*

* = 단어 끝 표시

핵심 차이 정리

구분TreeTrie

개념	범용 자료구조	문자열 전용 트리
저장 단위	임의의 값	문자
구조 의미	노드 자체가 의미	경로가 의미
탐색 기준	값 비교	문자 순서
주 용도	계층, 정렬, 탐색	자동완성, 사전
시간 복잡도	구조에 따라 다름	O(L)

 

언제 Trie를 쓰면 좋을까?

• 🔍 자동완성
• 🔎 검색어 추천
• 📖 사전
• 🚫 금칙어 필터
• 🌐 URL 라우팅

👉 “문자열 검색이 핵심”이면 거의 Trie

---

 

기본적인 구조는 트라이 자료구조를 사용 + 캐시 전략적 사용

이렇게 나아가야 할 것이다.

 

그런데 보통은 우리가 검색어 빈도를 계산할 때 10년전에 100만번 검색이 되었는데 그 후로 한번도 검색이 안된 키워드랑

오늘만 10만번 검색이 된 키워드가 있다고 해보자

 

그럼 당연히 10년전 키워드보다 오늘 10만번 검색이 된 키워드가 위에 와야 이치에 맞는 것처럼 보이지 않을까?

 

이런 부분을 위해서는 순위모델을 바꾸어야 할 것이다.

 

1. 지수 감쇠 (Exponential Decay)

가장 많이 쓰는 방식

**시간에 따른 가중치 변화**

시간 경과 | 가중치 (λ=0.01)
--------------------------------
1시간    | 99%
24시간   | 78.7%
7일      | 8.7%
30일     | 0.74%
1년      | 0.00000001%
10년     | 거의 0

 

2. 반감기 모델 (Half-Life Decay)

"N일 후 점수가 절반이 되게" 설정

**직관적인 이해**

경과 시간 | 점수 (반감기 7일)
--------------------------------
0일      | 100%
7일      | 50%
14일     | 25%
21일     | 12.5%
30일     | 7.8%

 

3. 구간별 가중치 (Tiered Weights)

4. 복합 모델

5. 실시간 트렌드 반영

 

....등등이 있을 수 있겠다.

 

사실 실제 서비스에 적용이 되려면 더 여러 부분을 살펴봐야겠지만..

- 트라이가 너무 커서 한 서버로 부족하여 샤딩을 해야하는 경우.. 어떤식으로 샤딩?

- 위에서 언급한 순위 모델

- 실제로 어떤 방식을 사용할지 rdb + redis vs mongo db 등등

 

 

다음에 좀 더 세부적인 내용으로 돌아오겠습니다..!!!

 

안녕~~~~