Skip to content

Latest commit

 

History

History
189 lines (147 loc) · 10.2 KB

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

File metadata and controls

189 lines (147 loc) · 10.2 KB
Raw

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

  • 검색어 자동 완성 (autocomplete, typeahead, search-as-you-type, incremental search)
  • 가장 많이 이용된 검색어 k개를 자동완성하여 출력하는 시스템 설계

image

1단계 - 문제 이해 및 설계 범위 확정

요구사항 구체화를 위한 질의응답 예 (p.224)
  • 사용자의 입력 단어 는 자동 완성 검색어와 어디에 매칭되어야? (첫부분인지 중간 부분일 수 도 있는지)
    • 첫 부분으로 한정
  • 자동 완성 검색어 는 몇개 (k)가 표시되어야?
    • k=5
  • 자동 완성 검색어 5개를 고르는 기준?
    • 질의 빈도에 따른 검색어 인기 순위에 따라
  • 맞춤법 검사 기능 제공 여부? (?)
    • NO. 맞춤범 검사 / 자동 수정 미지원
  • 질의 언어?
    • 영어만. 시간이 된다면 다국어 지원도.
  • 대문자나 특수문자 처리 필요성?
    • 모든 질의는 영어 소문자로만 이루어진다고 가정
  • 얼마나 많은 사용자를 지원해야?
    • 일간 능동 사용자 (DAU) 기준 천 만명
  • 요구사항
    • 빠른 응답 속도 : 페이스북 typeahead 문서 기준으로는 100ms 이내여야
    • 연관성 : 자동 완성되어 출력되는 검색어는 사용자의 입력단어와 연관 된 것이여야
    • 정렬 : 시스템 계산 결과는 순위 모델에 의해 정렬되어있어야 (ex. popularity)
    • 규모 확장성 : 많은 트래픽을 감당할 수 있도록
    • 고가용성 : 시스템의 일부에 장애나 속도 저하, 예상치못한 네트워크 문제가 생겨도 시스템은 계속 사용가능해야
      • 📌 대개 모든 시스템 설계에서 규모 확장성 & 고가용성은 필수
  • 개략적 규모 추정
    • 사용자 : 일간 능동 사용자 (DAU) 는 천만 명 (by 질의응답)
    • 평균 검색량 : 사용자 당 10건/day
    • 평균 입력 질의 데이터 크기 : 20bytes
      • ASCII 사용 시 1문자 = 1bytes
      • 질의문은 평균 4개 단어 & 각 단어는 5글자로 가정 => 4 * 5 * 1 bytes = 20 bytes
      • 글자 입력할 때마다 클라이언트는 백엔드에 요청 => 검색 당 평균 20회 요청
      • 🤔 면접관과 구체화 해야할 부분 vs 자체적 추정
    • QPS : 초당 24,000건 질의
    • max(QPS) : QPS * 2 = 약 4,8000
    • 신규 데이터 크기 : 매일 0.4GB 가 시스템에 추가
      • 질의 중 20%를 신규 검색어로 가정 => 10,000,000 * 10 질의 * 20자 * 20% = 0.4GB

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

  • 데이터 수집 서비스 (data gathering service)
  • 질의 서비스 (query service)

데이터 수집 서비스

  • 사용자가 입력한 질의를 실시간으로 수집하는 시스템 (데이터가 많은 경우 부적절)
  • 질의문 & 빈도 테이블 (frequency table)
    • query : 질의문 저장 필드
    • frequency : 질의문이 사용된 빈도 저장 필드

13-2

질의 서비스

  • 데이터량이 적은 경우 SQL 질의로 추출 가능 (데이터가 많아지면 DB 병목)

t-13-1

-- ex. 'tw' 입력 시 가장 많이 사용된 5개 검색어 ("top 5") 추출 쿼리
SELECT *
FROM frequency_table
ORDER BY frequency DESC
LIMIT 5;

3단계 - 상세 설계

데이터 수집 서비스 & 질의 서비스 기반의 개략적 설계안에서 => 컴포넌트를 골라 보다 상세히 설계 후 최적화

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

(1) 트라이 자료 구조

  • 트라이 (trie, prefix tree) 자료구조
    • 검색어 시스템의 핵심적 부분
    • 트라이 : 문자열을 간략하게 저장할 수 있는 자료 구조 (retrieval 에서 유래)
      • 문자열을 꺼내는 연산에 초점을 맞춤
      • 트리 형태 (루트 노트는 빈 문자열)
      • 각 노드는 character 하나를 저장. 해당 글자 다음에 등장할 수 있는 글자 수(a-z, 26개) 만큼 자식노드를 가질 수 있다
      • 각 트리노드는 하나의 단어 or 접두어 문자열을 나타냄

13-6

트라이 기반 검색어 자동완성 알고리즘

p: 접두어 (prefix) 의 길이 n: 트라이 안의 노드 개수 c: 주어진 노드의 자식 노드 개수

  • 가장 많이 사용된 (frequency) 질의어 k개 찾기 => O(p) + O(c) + O(clogc)
    • 해당 접두어를 표현하는 노드 찾기 : O(p)
    • 해당 노드 하위 트리 탐색을 통한 모든 유효 노드 찾기 : O(c)
    • 유효 노드 정렬하여 top k개 찾기 : O(clogc)
  • => 최악의 경우 k개를 찾기 위해 full scan 해야할 수 있다
  • 최적화 기법 적용 => O(c)
    • 1) 접두어의 최대 길이 제한
      • 검색어의 최대 길이를 제한할 수 있다면 O(p) => O(1)
    • 2) 각 노드에 인기 검색어 캐시
      • 각 노드에 k개 인기 검색어 캐싱하면 O(c) + O(clogc) => O(1)
      • 응답속도 ⬆, 저장 공간 ⬆

(2) 데이터 수집 서비스

  • 타이핑마다 실시간으로 데이터 수정 시
    • 질의 서비스 속도 저하
    • 트라이가 자주 갱신될 필요성 x
  • 데이터의 용례를 알아야 규모확장이 쉬움 (ex. 트위터? 구글 검색?)
  • 데이터 수집 서비스의 토대는 동일
    • 데이터 분석 서비스 (analytics), 로깅 서비스 (logging service) 로부터 수집한 데이터로 트라이 생성

13-9

a. 데이터 분석 서비스 로그 : 검색창에 입력된 질의의 원본 데이터 보관 (write only. index x) b. 로그 취합 서버 : 많은 양의 로그를 잘 취합 (aggreagtion) 하여 저장. 서비스 용례에 따라 취합 방식/주기는 달라질 수 있다 (데이터 취합의 실시간성) c. 취합된 데이터 : 취합 주기에 따라 저장. query, time (취합 날짜), frequency d. 작업 서버 : 트라이 자료구조를 만들어 트라이 DB에 저장. 작업 서버 (worker)는 주기적으로 비동기 잡을 실행하는 서버 집합 e. 트라이 캐시 : 분산 캐시 시스템 사용. 매 주기마다 트라이 데이터베이스의 스냅샷을 떠서 갱신 f. 트라이 데이터베이스 : 지속성 저장소 사용.

  • document store
    • 주기마다 새 트라이가 만들어지므로 (snapshot) 트라이를 직렬화하여 저장
    • ex. MongoDB
  • key-value store (해시 테이블) => 6장 참고
    • key : 트라이에 보관된 모든 접두어
    • value : 각 트라이 노드의 모든 데이터를 해시 테이블 값으로 변환

13-10

(3) 질의 서비스

13-11

  • 개략적 설계안의 비효율성을 개선한 새 설계안
  • 질의 서비스는 빨라야함 => 최적화 필요
    • AJAX request : 새로고침 없이 요청/응답
    • Browser Caching : 제안된 검색어를 브라우저 캐시에 저장 (구글 검색 엔진 - cache-conrol: private; max-age=3600;)
    • Data Sampling : 모든 질의 결과 저장 시 소진되는 리소스 절약. N개 요청 중 1개만 로깅

(4) 규모 확장이 가능한 저장소

  • 트라이 크기가 한 서버에 넣기에 큰 경우 대응
  • 글자 단위 샤딩
    • 영어 기준 첫 글자 기준으로 샤딩하는 방법 => 사용가능한 서버 26개로 제한
    • 두 번째 글자까지 추가해 더 계층적인 샤딩 => 데이터 균등 배분 불가능
  • 검색어 대응 샤드 관리자 (shard map manager) 사용
    • 과거 질의 데이터 패턴을 분석하여 샤딩
    • 어떤 검색어가 어느 저장소 서버에 저장되는지 관리 => 균등 분배 가능

13-15

(5) 트라이 연산

  • 트라이 생성 : 작업 서버가 특정 주기에 따라 비동기적으로. 데이터 분석 서비스 로그나 DB로부터 취합 데이터 사용.
  • 트라이 갱신 (2가지 방법)
    • 매주 한번 갱신. 새 트라이로 기존 트라이 대체 (snapshot)
    • 트라이의 각 노드를 개별적으로 갱신 => 성능 Bad (상위도 모두 갱신되어야)
  • 검색어 삭제 : 필터 계층 사용 + 물리적 삭제는 업데이트 사이클에 비동기적 처리

13-14

4단계 - 마무리

면접관이 추가로 던질 수 있는 질문들

  • Q. 다국어 지원할 수 있도록 확장하려면?
    • A. 비영어권 지원을 위해 unicode 데이터 저장 (유니코드는 "모든 문자 체계를 지원하는 표준 인코딩 시스템")
  • Q. 국가 별 인기 검색어 순위가 다르다면?
    • A. 국가별 다른 트라이 사용. + CDN 으로 응답속도 개선 고려
  • Q. 실시간 검색어 추이 반영하려면?
    • 현 설계안은 부적절함. (작업서버가 매주 돌고, 배치성으로 트라이 구성에 많은 시간 소요)
    • 샤딩을 통한 작업 대상 데이터량 줄이기?
    • 순위 모델 (ranking model) 을 최근 검색어에 높은 가중치 주도록 수정 (not just 빈도)
    • 데이터의 스트리밍 프로세싱 시스템 (ex. Apache Hadoop MapReduce, Spark Streaming, Storm, Kafka) 등 추가 고려