검색어 자동완성 시스템

가상 면접 사례로 배우는 대규모 시스템 설계 기초 "검색어 자동완성 시스템"을 요약한 내용입니다.

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

요구 사항

• 빠른 응답 속도
  • 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시되어야 한다.
  • 페이스북 검색어 자동완성 시스템에 관한 문서를 보면 시스템 응답속도는 100밀리초 이내여야 한다.
• 연관성
  • 자동완성이되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.
• 정렬
  • 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.
• 규모 확장상
  • 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 한다.
• 고가용성
  • 시스템의 일부에 장애가 발생하거나 느려지거나 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능 해야함

개략적 규모 추정

• 일간 능동 사용자(DAU)는 천만 명으로 가정
• 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정
  • 질의문은 평균적으로 4개 단어로 이루어진다고 가정
  • 각 단어는 평균적으로 다섯 글자로 구성된다고 가정
• 검색창에 글자를 입력할 때마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다.
  • 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다.
  • ex) dinner 입력하면 다음 6개의 요청이 순차적으로 백엔드에 전송된다.
    • search?q=d
    • search?q=di
    • search?q=din
    • search?q=dinn
    • search?q=dinne
    • search?q=dinner
• 대략 초당 24,000건의 질의(QPS)가 발생할 것이다.
  • 10,000,000 사용자 x 10질의/일 x 20자 / 24시간 / 3600초)
• 최대 QPS = QPS X 2 = 대략 48,000
• 질의 가운데 20% 정도는 신규 검색이라고 가정 할 것이다.
  • 대략 0.4GB 정도
  • 매일 0.4GB의 신규 데이터가 시스템에 추가 된다는 뜻

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

• 데이터 수집 서비스(Data Gathering Service)
  • 사용자가 입력한 질의를 실시간으로 수집하는 시스템
  • 데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지는 않음
• 질의 서비스(Query Service)
  • 주어진 질의에 다섯개의 인기 검색어를 정렬해 내놓은 서비스

데이터 수집 서비스

• 데이터 수집 서비스가 어떻게 동작하는지 간단한 예제를 통해 살펴보자 [그림 13-2]
• 질의 문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정
• 사용자가 검색하는 순서대로 상태를 바뀌어 나간다

질의 서비스

• [표 13-1]과 같은 빈도 테이블이 있는 상태라 가정
  • query: 질의 문을 저장하는 필드
  • frequency: 질의문이 사용된 빈도를 저장하는 필드
• 사용자가 “tw”를 검색장에 입력하면 아래의 “top 5”자동 완성 검색어가 표시되어야 한다. [그림 13-3]
• 가장 많이 사용된 5개 검색어는 SQL 질의문을 사용해 계산할 수 있다.
  • 데이터가 많아지면 데이터베이스가 병목이 될 수 있다

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