Dayoung

Dayoung

Be-Developer

© 2024

Dark Mode

[대규모 시스템 설계 기초] 13 검색어 자동 완성 시스템
May 8, 2022
  • design
  • architecture
  • study

검색어 자동 완성 시스템

문제 이해 및 설계 범위 확정

요구사항

  • 검색어의 첫부분을 보고 키워드 뒷부분을 완성.
  • 5개의 자동완성 검색어
  • 질의 빈도에 따라 정해지는 검색어 인기순
  • 영어가 기본, 다국어 지원
  • DAU 1000만명
  • 빠른 응답속도 100ms 이내
  • 연관성 : 검색어와 단어는 연관된 것이어야한다.
  • 규모확장성
  • 고가용성 : 일부 시스템장애, 네트웍문제가 생기더라도 계속 사용가능해야한다.

    개략적 규모 추정

  • 평균 한사용자는 매일 10건의 검색을 한다고 가정.
  • 질의할때 평균 20byte 입력한다고 가정.
    • 평균 질의문이 4단어로 이루어지고, 각 단어는 평균 다섯글자로 이루어진다. = 20byte
  • 글자입력시마다 요청이 발생된다.
  • 대략 QPS 24,000 (1000만 * 10 질의 * 20자/24시간/3600초)
  • 최대 QPS 48,000
  • 질의중 20%는 신규 검색어. = 매일 0.4GB 신규데이터가 추가될것.

    개략적 설계안 제시 및 동의 구하기

    데이터 수집 서비스

    : 사용자가 입력한 질의를 실시간 수집

  • 질의문과 검색 빈도를 저장하는 테이블로 구성됨.

    질의 서비스

    : 주어진 질의에 5개의 인기검색어를 정렬해 응답.

  • 데이터 수집 서비스의 빈도테이블에서 빈도로 인기순정렬후, 응답.

데이터가 많아지면 DB가 병목이 될 수 있다.

상세 설계

trie 자료구조

  • 트라이 = retrieval(검색, 되찾아옴) = 접두어 트리(prefix tree)
  • 트라이는 문자열들을 간략하게 저장할 수 있는 트리형태의 자료구조이다.
  • root는 빈 문자열
  • 각 노드는 글자 하나를 저장하며 26개의 자식노드를 가질 수 있다. (26개 = 알파벳 대소문자?)
  • 각 트리노드는 하나의 단어 또는 접두어 문자열을 나타낸다.
  • 시간 복잡도
    • $p$ 접두어 prefix 길이
    • $n$ 트라이안에 있는 노드 갯수
    • $c$ 주어진 노드의 자식 노드 갯수
    • 가장 많이 사용된 질의어 k개를 찾는 시간복잡도 = $O(p) + O(k) + O(clogc)$
      1. 접두어를 표현하는 노드 찾기 $O(p)$
      2. 해당노드부터 시작하는 하위 트리를 탐색하여 모든 유효노드 탐색 $O(k)$
      3. 유효노드를 정렬하여 가장 인기있는 검색어 k개 찾기. 시간복잡도는 $O(c)$
  • k개의 결과를 얻기위해 전체 트라이를 탐색해야할수도 있다.
    • 접두어 최대 길이 제한
      • $O(작은 상수) = O(1)$ 로 제한될것.
    • 각 노드에 인기 검색어 캐시
      • 각 노드에 질의어 저장공간이 많이 필요하게 될 수 있지만 가치있다.
      • $O(1)$
    • 둘다 적용했을때 속도 개선에 효율적.

      데이터 수집 서비스

  • 쿼리가 들어올때마다 트라이 데이터 수정하는 방식
    • 쿼리가 매우 느려질것
    • 트라이가 만들어지고나면 인기검색어는 자주 바뀌지 않을것이므로, 자주갱신은 불필요. (트위터같은 실시간성은 예외)
  • 데이터 분석 서비스 로그 : 원본데이터와 쿼리시각 저장
  • 로그 취합 서버 : 데이터 취합 주기(실시간성)은 서비스의 특성에 맞게 가자. 면접시 꼭 확인해야할 포인트.
  • 취합된 데이터 : 쿼리별 빈도와 기준 날짜
  • 작업 서버 : 트라이 자료구조를 만들고 DB에 저장
  • 트라이 캐시 : 분산 캐시 시스템, DB 스냅샷을 떠서 갱신한다
  • DB
    • document store : 트라이는 매주 생성되므로 serialize 하여 저장할수있으며, mongoDB가 좋다.
    • key-value store: 각 트라이 노드 데이터를 해시테이블 값으로 변환.

      질의 서비스

  • 속도 최적화 방안
    • AJAX : 요청을 보내고 받기위해 페이지 새로고침이 필요없다.
    • browser caching : 구글은 사용중
      • responseHeader.cache-control : max-age=3600(s)
    • 데이터 샘플링
      • 쿼리가 매우 많으므로, n개중 1개만 로깅.

        트라이 연산

  • 트라이 생성 : 로그나 DB로부터 취합된 데이터 사용.
  • 트라이 갱신
    • 매주 1번 갱신 : 기존 트라이를 대체한다.
    • 개별 실시간 갱신
      • 트라이가 작을때는 고려해볼수있다.
      • 트라이 노드 갱신시에 상위노드전체를 갱신해야한다. (캐시 업데이트)
  • 검색어 삭제
    • 트라이 캐시 앞에 필터 레이어를 두고 반환되지 않도록 한다.
    • DB에서 물리적으로 삭제하는건 다음 업데이트 사이클에서 비동기적으로 진행하면 된다.

      규모 확장이 가능한 저장소

  • 첫글자를 기준으로 샤딩 (영어만 지원하므로)
    • 최대 서버대수가 알파벳수(26자)만큼 제한된다.
    • 데이터를 균등하게 배분하기 불가능하다. (a로 시작하는 단어와 x로 시작하는 단어 개수)
  • 과거 질의 데이터 패턴을 분석하여 샤딩하는 방법
    • 샤드관리자가 따로있고, 검색어 빈도를 고려햐여 샤딩.

      마무리

      더 논의할 주제

  • 다국어 지원
    • 트라이에 유니코드로 저장.
  • 국가별 인기검색어 순위가 다르다면
    • 국가별로 다른 트라이를 사용하여 트라이를 CDN에 저장해볼수도있다.
  • 실시간 검색어 추이반영
    • 순위모델에서 최근검색어의 가중치를 높인다.
    • 트라이 업데이트주기는 어떻게?
    • 데이터가 스트림형태로 올 수 있다. (데이터가 지속적으로 생성됨)
      • apache hadoop mapreduce
      • apache spark streaming
      • apache storm

      • apache kafka

  • How we built prefixy
    • 캐시로 Redis, persistent로 mongo를 사용하는데, prefix tree가 key-value로 표현하기 좋은 구조이고, 두가지 db도 동일하기때문.
    • key(prefix) : value(List(keyword:frequency))
    • 책과 거의 동일, 더 자세히 나와있음.