검색어 추천 기능 V2(Trie + RAM)

이전 버전은 기능적으론 만족스러웠지만, 성능 측면에서 아쉬움이 있었습니다. 따라서 버전 2는 성능 개선을 중점으로 진행했으며, 대규모 시스템 설계의 기초 서적에서 많은 도움을 받았습니다.
 
앞서 우리는 문자열 검색에 데이터베이스 쿼리를 활용했는데, LIKE 연산자의 동작 방식으로 인해 데이터베이스는 테이블의 모든 행을 검사해야 했습니다.

이 과정에서 시간 복잡도는 O(테이블의 행 수)이며, 각 행의 해당 컬럼에서 질의 문장을 매칭하는 과정이 추가되기 때문에 실제로는 O(테이블의 행 수 * 문장 길이)의 시간 복잡도가 발생하게 됩니다.
 
모든 행을 검사하는 것은 비효율적입니다. 예를 들어, 사용자가 입력한 검색어가 "A"일 경우, "A"로 시작하는 칼럼만 비교하면 되지, "C"나 "D"로 시작하는 컬럼과 매칭할 필요는 없습니다.
 
이를 개선하기 위해 트라이(Trie) 자료구조를 도입했습니다. 트라이의 특성상 사용자가 입력한 데이터만 트라이 데이터와 비교되므로 불필요한 비교를 피할 수 있습니다.

예를 들어, 사용자가 "app"이라는 접두사를 입력하면, 트라이 자료구조를 통해 해당 접두사를 가진 모든 단어("apple", "app", "application", "apply")를 검색하고, 불필요한 단어("apd", "cpple")는 검색에서 제외됩니다.
 
참고로, 문자열 검색에는 KMP 알고리즘도 있습니다. KMP는 특정 문자열 내에서 원하는 문자를 빠르게 찾을 수 있는 알고리즘이지만, 현재의 상황과는 맞지 않습니다.
 
따라서 검색 기능에는 트라이 자료구조가 효과적이며, 이를 구현하기 위해서는 트라이의 동작 방식을 이해하는 것이 중요합니다.

이 부분은 아래의 참고자료 블로그를 참조하면 좋을 것 같습니다. 참고로, 개발의 편의를 위해 트라이 노드를 아래와 같이 변경하였습니다.

public class Node {
	Map<Character, Node> child = new HashMap<>();
	String keyword = "";
	Long searchCount = 0L;
	boolean endOfWord = false;
}

 
결과적으로, 트라이를 사용한 버전 2에서는 92%의 성능 개선을 확인할 수 있었습니다. 버전 1에서는 17,500개의 데이터에 대해 응답 시간이 약 100ms가 소요되었지만, 버전 2에서는 응답 속도가 8ms로 단축되었습니다.

 
성능이 어떻게 다이나믹하게 개선되었는지 이해하기 위해서는 알고리즘을 빅오(Big-O) 표기법으로 분석해 보는 것이 유용합니다.

검색어 추천 알고리즘의 빅오 표기법은 O(P) + O(C) + O(C log C)로 표현할 수 있습니다.

즉 버전 2의 경우에는 검색어의 개수(P)와 부분 힙의 크기(C)가 검색 속도를 좌우하지만 버전 1의 경우에는 데이터의 크기가 검색속도를 좌우하기 때문입니다.

중요한 점은, 우리가 원하는 "AR + XX" 형태로 데이터가 추가되지 않으면, 성능이 항상 일정하게 유지된다는 것입니다. 이를 증명하듯, 데이터를 1,000,000개로 늘렸을 때도 "AR" 검색어의 질의 결과는 여전히 7ms로 나왔습니다.
 
이 알고리즘의 개선 포인트로 캐시 도입, 접두어 글자 개수 제한 등 다양한 방법이 있지만, 가장 치명적인 단점은 트라이 구조가 힙 메모리 영역에 할당되면서 데이터가 추가될 때 힙 메모리 부족 현상이 발생할 수 있다는 점입니다.
 
2024.08.09 - [개발] - 검색어 추천 서비스 개발기에서 우리가 계산한 QPS(초당 쿼리 수)는 114건이며, 이 중 20%가 신규 검색어라고 가정할 때, 매일 약 36.53MB의 데이터가 추가됩니다.

만약 힙 메모리가 2GB로 제한된다면, 56일 동안은 문제가 없지만 그 이후에는 OutOfMemory 에러가 발생하여 서버가 다운될 수 있으며, 이로 인해 저장된 검색어 데이터가 모두 소실될 위험이 있습니다.
 
따라서 버전 3에서는 메모리 구조를 개선하여 트라이 구조를 다른 저장소로 이동시키고, 검색어 추천 알고리즘의 기능을 어떻게 향상할 수 있을지 작성해 보겠습니다.
 
 
**추가적 **

트라이(Trie)

• 목적: 주로 문자열 검색 및 접두사 기반 검색을 효율적으로 수행하기 위해 사용됩니다.
• 구조: 트리는 노드와 간선으로 구성되며, 각 노드는 알파벳 문자와 같은 단일 문자를 나타냅니다. 문자열의 각 문자는 트라이의 노드를 따라가며, 문자열의 끝은 특별한 "종료" 노드로 표시됩니다.
• 사용 사례: 자동 완성, 사전 구현, 문자열 탐색, 접두사 일치 등.
• 장점: 트라이를 사용하면 문자열 검색 속도가 매우 빠릅니다. 접두사 검색의 경우 O(m) (m은 문자열의 길이) 시간복잡도를 가집니다.
• 단점: 메모리 사용량이 많습니다. 특히 데이터셋이 크거나 입력 문자열의 길이가 길면 메모리 사용량이 급격히 증가할 수 있습니다.

힙(Heap)

• 목적: 주로 우선순위 큐(Priority Queue) 구현 및 최댓값이나 최솟값을 빠르게 찾기 위해 사용됩니다.
• 구조: 힙은 이진 트리 형태의 자료구조로, 최대 힙(max-heap)과 최소 힙(min-heap)으로 구분됩니다. 최대 힙에서는 부모 노드가 자식 노드보다 항상 크거나 같으며, 최소 힙에서는 반대입니다.
• 사용 사례: 우선순위 큐 구현, 힙 정렬, 실시간 스케줄링 알고리즘, 네트워크 라우팅.
• 장점: 최댓값이나 최솟값을 O(1) 시간에 찾을 수 있으며, 삽입과 삭제 작업은 O(log n)의 시간복잡도를 가집니다.
• 단점: 트리의 형태를 유지해야 하므로, 삽입 및 삭제 작업에서 성능이 떨어질 수 있습니다. 또한, 힙은 특정 값 검색에 최적화되지 않았습니다

[트라이 자료구조 설명]
https://innovation123.tistory.com/116 

[JAVA/자료구조] 트라이(Trie) 개념, 직접 구현하기