TIL

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

설계 범위 예시

• 빠른 응답 속도
  • 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨라야 함
  • 100밀리초 이내
• 연관성
  • 사용자가 입력한 단어와 연관된 것이어야 한다.
• 정렬
  • 시스템 계산 결과는 인기도 등 순위 모델에 의해 정렬
• 고가용성
  • 시스템 일버에 장애가 발생하거나 느려져도 시스템은 계속 사용 가능해야 한다.

개략적 규모 측정

• DAU 천만 명
• 평균 한 사용자는 매일 10건의 검색을 수행
• 질의할 때마다 평균 20바이트 데이터를 입력
  • ASCII 인코딩 방법 사용 (1문자 = 1바이트)
  • 잘의문은 평균 4개 단어로 이루어지고 평균 5글자라 가정
• 글자를 입력할 때마다 클라이언트는 백엔드에 요청
  • 평균 1회 검색당 20건 요청이 백엔드로 전달
  • ex) dinner라 검색한다면
    • search?q=d
    • search?q=di
    • …
    • search?q=dinne
    • search?q=dinner
• 약 초당 24,000건 질의(QPS) 발생, 최대 QPS = 48,000
• 쿼리 중 20% 정도는 신규 검색어

검색어 자동완성 시스템 개략적 설계안

• 개략적으로 시스템은 두 부분으로 나뉜다.
  • 데이터 수집 서비스 - 사용자가 입력한 질의를 실히간으로 수집
    • 데이터가 많은 애플리케이션에서 실시간 시스템은 바람직하지 않다.
    • 추후 상세 설계에서 현실적인 안에서 교체할 예정
  • 질의 서비스 - 질의에 대해 인기 검색어를 정렬해 내놓는 서비스

데이터 수집 서비스

• 질의문과 사용 빈도를 저장하는 ‘빈도 테이블’이 있다 가정
• 사용자가 검색어를 검색할 때마다 질의문과 빈도가 갱신되어진다.

query	frequency
twitch	1
twitter	2

질의 서비스

• 빈도 테이블이 어느정도 채워진 상황에서 사용자가 질의를 하게 되면 top 5 검색어가 조회되어야 한다.

• 아래 쿼리를 통해 빈도수 상위 5개를 조회할 수 있다.

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

• 데이터 양이 적을 때는 괜찮지만 데이터가 많아지면 병목이 발생할 수 있다.

검색어 자동완성 시스템 상세 설계

• 상세 설계에서 필요한 컴포넌트
  • 트라이(trie) 자료구조
  • 데이터 수집 서비스
  • 질의 서비스

트라이 자료구조

• 트라이: 문자열들을 간략하게 저장할 수 있는 자료구조
  • 트리 형태의 자료구조
  • 루트 노드는 빈 문자열
  • 각 노드는 글자(character) 하나를 저장
  • 각 노드는 26개의(해당 글자 다음에 등장할 수 있는 모든 글자 개수) 자식 노드를 가질 수 있음
  • 각 노드는 하나의 단어 또는 접두어 문자열(prefix string)을 나타냄
• ex) 가령 아래의 빈도 테이블은 그림과 같이 트리로 나타낼 수 있다.

query	freqeuncy
tree	10
try	29
true	35
toy	14
wish	25
win	50

트라이 자료구조를 활용한 구현

• 용어 정리
  • p: 접두어(prefix)의 길이
  • n: 트라이 안의 노드 개수
  • c: 주어진 노드의 자식 노드 개수
• 가장 많이 사용된 질의어 k개를 찾는 방법
  1. 해당 접두어를 표현하는 노드를 탐색 ,O(p)
  2. 해당 노드부터 하위 트리를 탐색하여 모든 유효 노드 탐색, O(c)
     1. 유효 노드란 유효한 검색 문자열을 구성하는 노드
  3. 요휴 노드들을 정렬하여 가장 인기있는 k개를 찾는다, O(c log c)
• 총 시간 복잡도 = O(p) + O(c) + O(c log c)
• 단 최약의 경우 k개를 얻기 위해 전체 트라이를 다 검색해야할 수도 있다.
  • 이를 해결하기 위한 두 가지 최적화 방법이 있다.

트라이 트리 탐색 최적화 1 - 접두어 최대 길이 제한

• 사용자가 긴 검색어를 입력하는 일은 거의 없다.
• 따라서 p값은 작은 정숫값(가령 50)이어도 충분
• 검색어 최대 길이를 제한하면 ‘접두어 노드를 찾는’ 시간 복잡도는 O(1)에 수렴할 수 있다.

트라이 트리 탐색 최적화 2 - 노드에 인기 검색어 캐시

• 각 노드에 k개 인기 검색어를 캐시해두면 전체 트라이 탐색을 방지할 수 있다.
• k는 보통 작은 값이기에 캐시 충분히 가능
• 단 저장 공간이 더 많이 필요하다는 단점도 있다.
  • 빠른 응답 속도가 중요할 때는 저장공간을 희생할만한 가치는 있다.
• 인기 검색어를 캐시해두면 접두어 노드를 찾는 순간 자식 노드를 탐색할 필요 없이 O(1) 시간에 정렬된 인기 검색어를 찾을 수 있다.

접두어 최대 길이를 제한하고, 노드에 인기 검색어를 캐시하면 전체 알고리즘 복잡도가 O(1)로 바뀌게 된다.

데이터 수집 서비스

• 실시간으로 데이터 수집하는 방법의 문제점
  • 매일 수천만 건 질의가 있을 때마다 트라이를 갱신하면 질의 서비스는 많이 느려질 것이다.
  • 트라이는 자주 갱신할 필요가 없다.
  • 일단 트라이가 만들어지고 나면 인기 검색어는 자주 바뀌지 않을 것

데이터 수집 서비스 컴포넌트

• 데이터 분석 서비스 로그
  • 질의에 관한 원본 데이터를 보관
  • 데이터가 추가될 뿐 수정을 이루어지지 않는다.
  • 로그 데이터에는 인덱스를 걸지 않는다.
  • query(질의), time(시간) 정보 등을 가지고 있다.
• 로그 취합 서버
  • 엄청난 양의 데이터 형식도 제각각인 로그를 잘 취합할 필요가 있다.
  • 서비스 성격에 따라 데이터 취합 빈도를 결정하면 된다.
  • 구글 검색 같은 성격이면 일주일 주기의 취합도 충분한 경우도 있다.
• 취합된 데이터
  • query(질의), time(해당 주가 시작된 날짜), frequency(해당 주에 사용된 횟수) 등 정보를 가진다.
• 작업 서버
  • 주기적으로 비동기 작업르 실행하는 서버
  • 트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당
• 트라이 캐시
  • 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 성능을 높인다.
  • 매주 트라이 데이터베이스의 스냅샷을 떠서 갱신
• 트라이 데이터베이스
  • 트라이 자료구조의 지속성 저장소
  • 저장소 선택지
    • 문서 저장소(document store): 주기적으로 새 트라이를 직렬화하여 저장할 수 있다. (ex. Mongo DB)
    • 키-값 저장소: 트라이의 모든 접두어를 해시 테이블 키로, 각 노드에 보관된 모든 데이터를 값으로 변환하여 사용할 수 있다.

질의 서비스

• 질의 서비스 설계안

  

  1. 검색 질의를 로드밸런서로 전송
  2. 로드밸런서는 해당 질의를 API 서버로 전송
  3. API 서버는 트라이 캐시에서 데이터를 가져와 요청에 대한 응답을 구성
  4. 데이터가 캐시에 없는 경우 데이터를 데이터베이스에서 가져와 캐시에 채움
     1. 캐시 미스는 캐시 서버 메모리가 부족하거나 캐시 서버 장애 시에도 발생할 수 있다.

• 질의 서비스 최적화 방안

  • AJAX 요청 - 요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없다.
  • 브라우저 캐싱 - 후속 질의의 결과를 캐시에서 바로 가져갈 수 있다.
  • 데이터 샘플링 - 대규모 시스템일 경우 모든 질의 결과를 로깅하면 CPU 자원과 메모리를 엄청 소모하게 되므로 N개 요청 중 1개만 로깅하도록 하는 것

트라이 연산

• 트라이 생성
  • 작업 서버가 담당
  • 데이터 분석 서비스의 로그나 DB로부터 취합된 데이터를 이용
• 트라이 갱신
  • 매주 한 번 갱신하는 방법 - 새 트라이를 만들고 기존 트라이를 대체
  • 트라이 각 노드를 개별적으로 갱신하는 방법
    • 성능이 좋지 않지만 트라이가 작을 땐 고려할 수도 있다.
    • 노드를 갱신할 땐 그 모든 상위 노드도 갱신해야 한다. (상위 노드에도 인기 검색어 질의 결과가 보관되기 때문)
• 트라이 삭제
  • 부적절한 검색어는 제거할 필요가 있다.
  • API 서버와 트라이 캐시 사이에 필터 계층을 추가해 부적절한 질의어를 반환하지 않도록 할 수 있다.
  • DB에 해당 검색어를 물리적으로 삭제하는 것은 다음 업데이트 시 비동기로 제공할 수 있다.

저장소 규모 확장

• 트라이 크기가 한 서버에 넣기에 너무 크다면 데이터베이스 샤딩을 생각해볼 수 있다.
• 영어의 경우에는 첫글자를 샤드 키로 사용할 수 있다.
  • a~z로 시작하는 단어들을 분류해 26대의 서버에 보관 가능
  • 26대 보다 더 늘리고 싶다면 두번째 글자까지 활용하여 한 알파벳당 여러대의 DB를 사용 가능
• 단 ‘c’로 시작하는 단어가 ‘x’로 시작하는 단어보다 많기에 데이터를 각 서버에 균등하게 배분할 수 없다.
  • 과거 질의 데이터 패턴을 분석하여 샤딩하는 방법이 있다.
  • ex) 만약 ‘s’에 대한 샤드 하나와 ‘u’부터 ‘z’까지의 샤드들의 양이 비슷하다면 ‘s’ 샤드 하나와 ‘u’~’z’ 샤드 하나를 두어도 충분할 것이다.

더 논의해볼만한 점

• 다국어 지원이 가능하도록 하려면?
  • 트라이에 유니코드 데이터를 저장해야 한다.
  • 유니코드: 고금을 막론하고 세상에 존재하는 모든 문자 체계를 지원하는 표준 인코딩 시스템
• 국가별 인기 검색어 순위가 다르다면?
  • 국가별로 다른 트라이를 사용하도록 하면 된다.
  • 트라이를 CDN에 저장하여 성능을 올릴 수도 있을 것
• 실시간으로 변하는 검색어 추이를 반영하려면?
  • 샤딩을 통해 작업 대상 데이터 양을 줄인다.
  • 순위 모델을 바꾸어 최슨 검색어에 높은 가중치를 두도록 한다.
  • 데이터가 스트림 형태로 올 수도 있다. (한 번에 모든 데이터를 동시에 사용 불가)
    • 아파치 카프카 등