가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 정리 13장 검색어 자동 완성 시스템

가상 면접 사례로 배우는 대규모 시스템 설계 기초

13장 검색어 자동 완성 시스템

개략적으로는 시스템은 두 부분으로 나뉜다.

• 데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집하는 시스템이다. 데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지 않지만 설계안을 만드는 출발점으로는 괜찮을 것이다.
• 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스이다.

  설계

최적화 방안을 논의한다.

• 트라이 자료구조
• 데이터 수집 서비스
• 질의 서비스
• 규모 확장이 가능한 저장소
• 트라이 연산

  트라이 자료구조

관계형 데이터베이스를 이용해 질의문을 골라내는 방안은 효율적이지 않다. 이 문제는 Trie 접두어 트리라고도 하는 트라이를 사용해 해결할 것이다.

트라이 자료구조는 트리형태의 자료 구조로 루트 노드는 빈 문자열을 나타낸다. 각 노드는 글자 하나를 저장하며 26개의 자식 노드를 가질 수 있다.

각 트리 노드는 하나의 단어 또는 접두어 문자열을 나타낸다.

tree, try, true, toy, wish, win 이 보관된 트라이이다.

p : 접두어의 길이

n : 트라이 안에 노드 개수

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

• 접두어를 표현하는 노드를 찾는 시간 복잡도는 O(p)
• 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는 복잡도는 O(c)

• 유효 노드들을 정렬하여 가장 인기있는 검색어 k개를 찾는 복잡도는 O(clogc) 트라이를 갱신하는 방법은 두가지가 있다.

• 매주 한번 갱신하는 방법

• 트라이의 각 노드를 개별적으로 갱신하는 방법 검색어 삭제

• 혐오성, 폭력성, 성적이 노골적이거나 위협요소는 제거해야한다.