[대규모 시스템 설계 기초] 검색어 자동완성 시스템

요구사항

기능 요구사항

시스템이 무엇을 해야 하는 지에 대한 요구사항

• 가장 많이 이용된(질의 빈도가 높은) 검색어 k개를 자동완성하여 출력함
• 사용자 입력 단어는 자동완성될 검색어의 첫 부분임
• 영어를 지원해야 함

비기능 요구사항

시스템이 어떻게 동작해야 하는지에 대한 요구사항

• 빠른 응답 속도
  • 사용자가 검색어를 입력하는 속도에 맞추어 자동완성 검색어도 빠르게 표기가 필요함
  • 페이스북 검색어 자동완성 시스템 기준 시스템 응답속도는 100ms 이내여야 함
• 연관성
  • 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관되어야 함
• 규모 확장성
  • 대규모 트래픽 발생 시 손쉽게 확장 가능해야 함
• 고가용성
  • 시스템 일부에 대해 장애가 발생해도 사용 가능해야 함

개략적 설계안

개략적 규모 추정

• 일간 능동 사용자(Daily Active Users)는 천만명이며, 평균적으로 단일 사용자는 매일 10건의 검색을 수행한다고 가정한다.
• 질의할 때마다 평균적으로 20바이트 데이터를 입력한다고 가정한다.
  • 기준) 질의문은 평균적으로 4개의 단어로 구성되며, 각 단어는 평균적으로 다섯 글자로 구성한다는 가정임 - 4 X 5 = 20
• 검색창에 글자를 입력할 때마다 검색어 자동완성 시스템에 요청을 보내므로, 평균적으로 1회 검색당 20건의 요청이 자동완성 시스템에 전달된다.
• 초당 질의 개수(QPS) = ( 10,000,000 사용자 X 10 X 20 ) / 24 / 60 / 60 = 23,148 (약 24,000 QPS)
• 최대 QPS는 평균의 2배정도로 가정한다. (약 48,000 QPS)
• 검색어 중 20%는 신규 검색어로 가정한다. 따라서, 대략 0.4GB 신규 데이터가 검색어 데이터 저장소에 추가됨
  • 0.4GB = 10,000,000 X 10 X 20 X 0.2 = 400,000,000 Byte

상세 설계

트라이(trie) 자료구조

가장 인기 있는 다섯 개의 질의문을 골라내기 위해서는 RDB를 사용하는 것은 효율적이지 않다. 

왜 RDB를 사용하는 것이 효율적이지 않을까?

 

RDB를 사용하여 가장 많이 사용된 5개 검색어는 아래 쿼리를 이용해 계산할 수 있다.

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

 위 쿼리의 경우 아래와 같은 문제점들이 있을 수 있다.

• LIKE 'prefix%' 연산의 비효율성
  • LIKE 연산은 RDB의 인덱스를 효율적으로 활용하기 어려움 (부분 인덱스 활용의 한계)
  • 인덱스의 첫 부분부터 일치하는 접두사를 찾아야 하므로 인덱스의 특정 범위가 인덱스 전체 스캔 또는 테이블 전체를 스캔해야 할 수도 있음. 따라서, 데이터 양이 많아질수록 스캔 범위가 넓어짐
• ORDER BY frequency DESC와 인덱스 전략의 충돌
  • query와 frequency 필드를 포함하는 다중 컬럼 인덱스를 생성한다고 가정했을 때, query를 기준으로 정렬 후 frequency 필드를 기준으로 정렬하면 정렬 이점을 제대로 살릴 수 없음
    • LIKE 쿼리는 query 필드의 접두사만 일치시키므로 인덱스가 query를 완전히 정렬할 수 없기 때문
• 빈번한 frequency 업데이트와 인덱스 유지보수 비용
  • frequency 필드는 사용자의 질의 빈도에 따라 지속적으로 업데이트되는 필드임
  • frequency 값이 변경될 때마다 해당 레코드의 인덱스 엔트리도 업데이트되어야 하며, 이는 인덱스 트리의 재구성(rebalancing)을 유발할 수 있고, 동시성 환경에서는 인덱스 조각화(fragmentation)을 야기할 수 있고, 이는 검색 속도 저하까지 일으킴
• 대용량 데이터 처리 및 확장성 한계
  • RDB는 수직 확장(scale-up)에는 유리하지만, 수평 확장(scale-out)에는 구조적인 제약이 있음
  • 대용량 데이터 처리를 위해 RDB를 샤딩할 수 있지만, 쿼리가 여러 샤드에 걸쳐 검색을 수행해야 할 수도 있으므로 복잡성이 증가하고 성능 저하가 있을 수 있음

Trie 자료구조 개념

트라이라는 이름은 retrieval에서 온 것으로 문자열을 꺼내는 연산에 초점을 맞추어 설계된 문자열들을 간략하게 저장할 수 있는 자료구조이다.

Trie Data Structure (geeksforgeeks)

• 노드(Node): 트라이의 각 노드는 단일 문자를 나타냄(예외적으로 루트 노드는 문자를 나타내지 않을 수 있음)
• 루트(Root): 트라이의 시작점으로, 보통 비어있는 문자열을 나타냄
• 경로(Path): 루트 노드에서 특정 노드까지의 경로는 하나의 문자열(단어 또는 접두사)을 나타냄
• 자식 노드(Child Node): 각 노드는 그 다음 문자를 나타내는 여러개의 자식 노드를 가질 수 있으며, 일반적으로 자식 노드는 해시맵(HashMap)이나 고정 크기 배열(예: 알파뱃 개수, 26개)로 저장됨
• 단어의 끝 표시(End of Word Marker): 특정 노드가 유효한 단어의 끝임을 나타내는 플래그

Trie 핵심 동작 - 삽입(O(n) Time & O(n) Space)

Insert Operation in Trie Data Structure (geeksforgeeks)

1. 루트 노드에서 시작: 삽입할 단어의 첫 문자에서 시작
2. 문자별 탐색: 현재 문자에 해당하는 자식 노드가 존재하는지 확인
   • 존재하면: 해당 자식 노드로 이동하여 다음 문자로 진행
   • 존재하지 않으면: 해당 문자에 대한 새로운 노드를 생성학, 현재 노드의 자식으로 추가한 후 새로운 노드로 이동해 다음 문자로 진행함
3. 단어의 끝 표시: 단어의 모든 문자를 처리한 후, 마지막 노드에 isEndOfWord 플래그를 true로 설정함

Trie 핵심 동작 - 검색(O(n) Time & O(1) Space)

Search Operation in Trie Data Structure (geeksforgeeks)

 

1. 루트 노드에서 시작: 검색할 단어의 첫 문자부터 시작
2. 문자별 탐색: 현재 문자에 해당하는 자식 노드가 존재하는지 확인
   • 존재하면: 해당 자식 노드로 이동하여 다음 문자로 진행
   • 존재하지 않으면: 해당 단어는 Trie에 존재하지 않으므로 false 반환
3. 단어의 끝 확인: 단어의 모든 문자를 처리한 후, 마지막으로 도달한 노드의 isEndOfWord 플래그가 true인지 확인
   • isEndOfWord == true: 단어 존재
   • isEndOfWord == false: 해당 접두사는 있지만 완전한 단어는 아님
   • 예) app와 apple로 검색을 했고, 트라이 자료구조에 apple만 저장된 상태라면 a - p - p(isEndOfWord = false) - l - e(isEndOfWord = true)로 되어 있을거라 app은 단어가 없다고 검색될 것이고, apple에만 단어가 있다고 반환될 것

Trie 핵심 동작 - 접두어 검색

1. 접두사 경로 찾기: 검색할 접두사의 모든 문자를 따라 트라이를 탐색함
   • 만약 접두사 중간에 노드가 없으면 해당 접두사로 시작하는 단어가 없으므로 빈 리스트 반환
2. 하위 트리 탐색: 접두사의 마지막 문자에 해당하는 노드에 도달하면, 해당 노드를 시작으로 해당 노드의 모든 하위 트리를 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 방식으로 탐색함
3. 유효 단어 수집: 탐색 중 isEndOfWord 플래그가 true인 노드를 만나면, 루트부터 해당 노드까지의 경로를 하나의 유효한 단어로 간주하고 결과 목록에 추가함

Trie의 장단점

• 장점
  • 빠른 접두사 검색: 검색어 길이 L에 대해 O(L) 시간에 검색이 가능함
  • 공간 효율성: 많은 단어들이 공통 접두사를 가질 때, 해당 접두사의 노드들을 공유함
• 단점
  • 메모리 사용량: 각 노드 후보가 될 수 있는 문자가 많으면 메모리가 많이 사용될 수 있음(유니코드가 많은 경우)
    • 보완) 해시맵을 사용하여 실제 존재하는 자식 노드만 저장하거나 Compressed Trie (Radix Tree), Ternary Search Tree (TST), Finite State Automata/Transducer 등을 사용해볼 수 있음
  • 빈도 기반 정렬 어려움: 순수 Trie는 빈도 정보를 내장하지 않음
    • 보완) 각 단어의 끝 노드에 빈도수를 저장하고 접두사 검색 후 반환된 단어들을 빈도 기준으로 다시 정렬해볼 수 있음
  • 동적 업데이트: 빈번한 삽입/삭제/업데이트 시 트리 구조 변경하는 과정에서 오버헤드가 발생할 수 있음

Trie를 실제 시스템에서 사용하는 방식

실제 검색어 자동완성 시스템에서는 순수한 Trie를 직접 구현하기보다는 Trie 개념을 활용해 최적화된 형태로 제공하는 라이브러리나 전문 검색 엔진을 사용하는 경우가 많음

• Elasticsearch의 completion suggester: 내부적으로 훨씬 효율적인 Trie의 변형(Finite State Transducer)을 사용하여 대용량 데이터에서도 매우 빠른 자동완성 기능 제공함. 이는 빈도 기반 랭킹도 지원함
  • 속도 최적화: FST는 메모리에 상주하여 접두사 매칭에 극도로 최적화되어 있어 밀리초 단위의 응답 속도를 기대할 수 있음
  • 색인 시점(Index-Time) 구축: Completion Suggester는 일반 검색 필드와 다르게, 문서가 색인될 때 미리 FST 구조를 메모리에 구축함. 따라서, 쿼리 시점에는 이미 완성된 자료구조를 탐색하기만 하면 됨
  • 다양한 입력 처리
    • input 배열: 하나의 제안어에 대해 여러 가지 입력을 제공해 다양한 사용자 입력 커버 가능
    • contexts: 특정 문맥(카테고리, 지역 등)에 따라 다른 제안을 할 수 있음
  • 퍼지(Fuzzy) 매칭: 오탈자를 허용하는 fuzzy 옵션을 통해 사용자가 틀려도 관련성 높은 제안 받을 수 있게 함
  • 부분 일치(Infix/Substring)는 기본적으로 지원하지 않음: Completion Suggester는 기본적으로 접두사 매칭에 특화되어 있으므로 중간 단어 일치(infix)나 부분 문자열(substring) 일치를 원한다면 search-as-you-type 필드 타입이나 edge_ngram 토크나이저를 일반 텍스트 필드와 조합하는 다른 전략 고려 필요
• Redis modules: 일부 Redis 모듈(예: RediSearch)도 Trie와 유사한 자료구조를 사용해 텍스트 검색 및 자동완성 기능을 제공함

접두어 최대 길이 제한

접두어가 길어질수록 검색하는데 오래 걸리기도 하고, 긴 검색어를 입력하는 경우는 적으므로, 접두어 최대 길이를 제한하는 것이 좋다.

• 담당하는 도메인마다 다르겠지만, 검색창에 들어올만한 검색어의 길이를 예측해서 해당 길이 정도까지로 제한할 수 있음

노드에 인기 검색어 캐시

앞서 Trie 핵심 동작 중 접두어 검색을 보면, 해당하는 접두어를 찾았다고 검색이 끝나지 않고 해당 접두어로 시작하는 모든 단어를 찾기 위해 노드를 순회해야 한다. 이 경우 속도가 느릴 수 있으므로, 각 노드에 k개의 인기 검색어를 함께 저장해두면 전체 트라이를 조회하지 않을 수 있다.

대신 인기 검색어를 캐싱할 경우, 저장한 공간이 많이 필요하게 된다는 단점이 있으므로 상황에 맞게 사용해야 한다.

 

검색어 삭제

간혹 위험한 질의어가 들어왔을 때는 해당 단어를 자동완성 시스템에서 활용하지 않도록 필터 계층을 두고 부적절한 단어가 반환되지 않도록 해야 한다.

데이터 수집 서비스 - 사용자가 입력한 질의를 수집하는 서비스

아래와 같은 사유로 인해 데이터 수집 서비스는 반드시 실시간 서비스인게 이득은 아니다.

• 하루에도 수천만건의 질의가 실시간으로 전송되기 때문에, 실시간으로 트라이를 갱신하면 질의 서비스가 느려짐
• 트라이가 만들어진 후 대세가 크게 바뀌지 않기 때문에 자주 갱신할 필요는 없음(서비스에 따라 다를 수 있음)

이에, 데이터 수집 서비스는 1일/7일 등 주기로 갱신하는 배치를 생성하여 트라이를 갱신할 수 있다.

• Analytics Logs(데이터 분석 서비스 로그): 검색창에 입력된 질의에 관한 원본 데이터가 보관된다. insert만 할 뿐 수정은 이루어지지 않는다.
  • AWS를 사용한다면 S3와 같은 저장소에 데이터를 밀어넣는 식으로 사용할 수 있음
• Aggregators(로그 취합 서버): 질의된 데이터의 양이 많기 때문에 로그를 취합하여 원하는 방식으로 소비할 수 있도록 하는게 좋다.
  • 실시간성의 중요성에 따라 서비스에 맞게 취합 주기를 다르게 가져가면 됨
• Workers(작업 서버): 취합된 데이터를 주기적으로 가져가서 트라이 자료구조를 만들고 DB에 저장하는 역할을 담당한다.
• Trie DB(트라이 데이터베이스): 트라이 데이터베이스는 질의 서비스에 이용하는 자동완성 서비스 데이터 저장소이다.
  • Elasticsearch를 사용하면, Trie의 변형을 담은 completion suggester를 사용해볼 수 있음
• Trie Cache(트라이 캐시): 트라이 캐시는 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지해 읽기 성능을 높이는 데 사용된다.

질의 서비스 - 주어진 질의와 연관된 다섯 개의 인기 검색어를 정렬하여 반환하는 서비스

질의 서비스는 일반적인 API처럼 특정 접두어로 시작하는 단어의 자동완성 데이터를 요청 받으면 DB(또는 캐시)를 조회하여 응답하는 형태로 구성하면 된다.

질의 서비스를 보다 더 빠르게 하는 방안

질의 서비스를 빠르게 제공하기 위해 클라이언트단 캐싱(Client-side Caching)을 해볼 수도 있다. 

클라이언트단 캐싱 방식 및 장/단점

• 사용자의 웹 브라우저(또는 모바일 앱)가 이전에 요청했던 자동완성 결과를 로컬 저장소(localStorage, indexedDB 또는 메모리 캐시)에 저장해두는 방식
• 장점
  • 빠른 응답 속도: 네트워크 지연과 서버 처리 오버헤드를 제거하므로 빠른 자동완성 경험 가능
  • 서버 부하 감소: 동일 요청에 대해 서버가 재처리할 필요가 없으므로, 백엔드 시스템 부하가 줄어듬
• 단점
  • 메모리/저장 공간: 클라이언트의 로컬 저장소 공간을 사용하여 너무 많은 데이터를 캐싱하면 클라이언트 성능에 영향을 줌
    • 캐시 크기 제한을 두거나 LRU 등의 캐시 정책이 필요함
  • 캐시 일관성, 데이터 신선도 문제: 데이터 수집 서비스가 00시 주기로 갱신된다고 했을 때, 캐시의 TTL을 1시간으로 설정하고 23시 59분에 조회한 사용자는 거의 한시간동안 오래된 데이터를 보게되기도 하고, 1분뒤 조회한 사용자와 상이한 자동완성 검색어를 보게 될 수 있음

참고 자료

• Gemini (2.5 Flash)
• How We Built Prefixy
• Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables
• trie data structure
• 책과 동일한 이미지 출처

더 알아보면 좋을 주제

• 다국어 지원 검색어 자동완성 시스템
  • Elasticsearch의 completion Suggester를 사용한다면, 한글에 대해 자동완성 서비스를 제공하기 위해서는 분석시(analyzer) 설정이 중요함
    • Nori Analyzer를 사용하거나 Nori Analyzer를 커스텀하여 플러그인으로 삽입하여 사용할 수 있음
      • Nori Analyzer는 Elasticsearch에서 공식적으로 제공하는 한글 형태소 분석기 플러그인이며, Nori는 한글의 형태소 분석을 통해 의미 있는 토큰(단어)을 추출함
• Trie DB로 사용할 데이터베이스의 규모 확장은 어떤식으로 할 수 있을까