대규모 시스템 설계 기초 - 13장

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

 

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

면접관과 대화를 통해 도출한 요구사항:

• 검색어 첫부분만 자동완성 지원
• 5개의 추천어를 보여줘야 함
• 검색 빈도가 높은 인기 검색어 순으로 추천
• 맞춤법 검사와 자동 수정 기능은 불필요
• 질의는 영어로
• 모든 질의는 영어 소문자로 이루어짐
• DAU는 천만명

추가 사항:

• 빠른 응답 속도: 100ms 이하의 빠른 응답 속도
• 연관성: 사용자 입력과 연관된 검색어가 자동완성되어야 함
• 정렬: 인기도 등의 순위 모델로 정렬되어야 함
• 규모 확장성: 많은 트래픽 감당 가능하도록 확장 가능해야 함
• 고가용성: 시스템 일부에 장애가 발생해도 시스템이 계속 사용 가능해야 함

개략적 규모 추정:

• DAU는 천만명으로 가정
• 한 사용자는 매일 10건의 검색을 수행한다고 가정
• 질의 마다 평균 20바이트의 데이터를 입력한다고 가정
  • ASCII 방식으로는 1문자 = 1 바이트
  • 질의문은 평균 4개 단어로 이뤄진다고 가정
  • 각 단어는 평균 5글자로 이뤄진다고 가정
  • 즉, 질의당 평균 4*5 = 20 바이트
• 검색창에 글자 입력할 때마다 클라이언트가 검색어 자동완성 백엔드에 요청을 보냄
  즉, 평균 1회 검색당 20건의 요청이 벡엔드에 전달됨
• 대략 초당 24,000건의 질의(QPS)가 발생 (= (천만 사용자 * 10질의일 * 20자) / 24시간 / 36000초)
• 질의 중 20%는 신규 검색어
  즉, 0.4GB의 신규 데이터가 시스템에 추가됨

 

 

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

 

데이터 수집 서비스:

• 사용자의 질의를 수집하고 빈도수를 누적
• 예시: 질의문과 사용빈도를 저장하는 빈도 테이블을 가정, 사용자 검색에 따라 상태가 아래와 같이 변화함
  
  

질의 서비스:

• 주어진 질의에 다섯 개의 인기 검색어를 정렬해서 보여줌
• 두개의 필드를 가정:
  • query: 질의문을 저장
  • frequency: 질의문이 사용된 빈도를 저장

 

• 사용자가 "tw"를 입력한 경우 자동 완성 예시

• SQL 쿼리로 가장 많이 사용된 5개 검색어 계산 가능

 

3단계: 상세 설계

2단계의 방법은 데이터가 아주 많아지는 경우 DB에서 병목이 발생할 수 있음
컴포넌트를 상세히 설계하고 최적화 방법 논의 필요

 

트라이 자료구조:

• 관계형DB는 인기 질의 5개를 골라내는 데 비효율적이므로 트라이 자료구조 필요
• 트라이:
  • 문자열 검색에 특화된 트리 형태의 자료구조
  • 루트 노드는 빈 문자열을 나타냄
  • 각 노드는 문자 하나를 저장하고, 최대 26개의 자식 노드를 가짐
  • 각 노드는 하나의 단어 또는 접두어 문자열을 나타냄

• 각 노드에 빈도 정보를 저장하는 경우

 

 

• 용어 정리:
  • p: 접두어(prefix)의 길이
  • n: 트라이 안에 있는 노드 개수
  • c: 주어진 노드의 자식 노드 개수
• 트라이로 가장 많이 사용된 질의어 k개 찾는 방법:
  • 해당 접두어를 표현하는 노드를 찾음 (시간 복잡도 O(p))
  • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾음 (시간 복잡도 O(c))
  • 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾음 (O(clogc))
• 예제: k=2 이고 사용자가 'be'를 입력한 경우
  1. 접두어 노드 'be' 탐색
  2. 해당 노드부터 하위 트리 탐색하여 모든 유효 노트 찾음
     [beer: 10], [best: 35], [bet: 29]가 유효 노드
  3. 유효 노드를 정렬하여 2개만 골라냄
     [best: 35], [bet: 29]가 인기 검색어

• 알고리즘의 시간 복잡도:
  • O(p) + O(c) + O(clogc) = O(p + clogc)
• 최악의 경우에는 전체 트리를 다 탐색할 수 있으므로, 아래와 같이 해결
  1. 접두어의 최대 길이를 제한
  2. 각 노드에 인기 검색어를 캐시
• 접두어 최대 길이 제한
  • 현실적으로 사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없음
  • p 값을 작은 정수 값(e.g. 50)으로 가정할 수 있음
  • 접두어 노드를 찾는 시간 복잡도 O(p) = O(작은 상수) = O(1)
• 노드에 인기 검색어 캐시
  • 각 노드에 인기 검색어 k개를 캐시해두면 전체 트라이 검색을 방지할 수 있음
  • 5~10개 정도의 자동완성을 표시하면 충분하기 때문에 k는 작은 상수
  • 공간이 많이 필요하지만, 빠른 성능이 중요하다면 가치 있음
  • 예시: 각 노드에 인기 있는 검색어 5가지를 캐싱하게 하는 경우
    • 시간 복잡도:
      • 접두어 노드 찾는 시간 O(1)
      • 인기 검색어 5개 찾는 시간 O(1)
      • 전체 시간 복잡도 O(1)
   

 

데이터 수집 서비스:

• 사용자가 타이핑을 할 때마다 실시간으로 데이터를 수정하는 방식은 실용적이지 않음
  
  • 매일 입력되는 수천만 건의 질의 마다 트라이를 갱신하면 서비스가 심각하게 느려질 것
  • 트라이가 일단 만들어진 후에는 인기 검색어가 자주 바뀌지 않을 것이므로 자주 갱신할 필요 없음
• 수정된 설계안:

• 데이터 분석 서비스 로그
  • 검색창에 입력된 질의의 원본 데이터가 보관됨
  • 추가는 발생하지만 수정은 발생하지 않음
  • 인덱싱 되지 않음

• 로그 취합 서버
  • 분석 로그는 크기가 매우 크고, 시스템이 바로 처리하기에는 데이터 형식이 제각각이므로 잘 취합해야 함
  • 용례에 따라 집계 주기 조정:
    • 실시간 검색이 중요한 트위터: 짧은 간격으로 집계
    • 일반적인 검색 시스템: 주 1회 집계도 충분
• 취합된 데이터
  • 예시:
    • time: 해당 주가 시작한 날짜
    • frequency: 해당 질의가 해당 주에 사용된 횟수의 합

• 작업 서버 :
  • 정기적으로 비동기 작업을 수행하는 서버 집합
  • 집계 데이터를 사용하여 트라이 구조를 생성하고, 이를 트라이 DB에 저장
• 트라이 캐시:
  • 분산 캐시 시스템
  • 트라이 데이터를 메모리 상에 유지해, 빠른 검색 응답을 제공
  • 일반적으로 DB의 주간 스냅샷을 기반으로 데이터를 갱신
• 트라이 데이터베이스:
  
  • 두 가지 저장 방식
    • 문서 저장소
      • 주기적으로 새 트라이를 생성하여 직렬화(저장 가능한 방식으로 변환) 후 저장
      • e.g. MongoDB문서 저장소
    • 키-값 저장소
      • 트라이의 모든 노드를 해시 테이블 키로 변환
      • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

 

질의 서비스:

• 개략적 설계안에서 살펴본 DB를 사용한 질의 서비스를 개선한 설계안:
  1. 검색 질의가 로드밸런서로 전송됨
  2. 로드밸런서는 해당 질의를 API 서버로 전송
  3. API 서버는 트라이 캐시에서 데이터를 가져와 자동완성 검색에 제안을 구성
  4. 데이터가 트라이 캐시에 없는 경우에는 데이터를 데이터베이스에서 가져와 캐시에 채움
     (다음에 같은 접두어 질의에 캐시 미스 발생하지 않고 대응하기 위함)

• 더 빠른 질의 서비스를 위한 최적화 방안:
  • AJAX 요청:
    • 웹 애플리케이션에서는, 보통 브라우저가 AJAX 요청을 통해 자동완성 결과를 가져오는 방식 사용
    • 장점: 요청/응답을 주고받더라도 웹 페이지 전체를 새로 고치지 않음
  • 브라우저 캐싱:
    • 대체로 자동완성 추천어는 짧은 시간 동안 자주 변하지 않으므로, 브라우저에 캐싱할 수 있음
  • 데이터 샘플링:
    • 모든 검색 요청을 로그로 남기는 대신, 1/N만 로깅

 

트라이 연산:

• 트라이 생성:
  • 작업 서버가 담당
  • 데이터는 분석 로그나 DB 취합된 데이터를 사용
• 트라이 갱신:
  • 두 가지 방법:
    • 매주 한 번 갱신:
      • 새로운 트라이를 생성하고 기존 트라이를 대체
    • 각 노드를 개별적으로 갱신:
      • 트라이가 작을 때는 고려해볼만 하지만, 성능이 나쁨(느림)
      • 특정 노드를 갱신할 때는 그 노드의 모든 조상 노드까지도 함께 갱신해야 함

• 검색어 삭제
  • 혐오성이 짙거나, 폭력적이거나, 성적이거나, 위험한 질의어 등은 제거해야 함
  • 트라이 앞에 필터 계층을 두어, 부적절한 추천이 사용자에게 표시되지 않도록 함
  • 다음 트라이 업데이트 시 비동기적으로 DB에서도 물리적으로 삭제

 

저장소 규모 확장

• 트라이가 너무 커져서 한 서버에 저장 불가하다면, 샤딩을 통해 확장 가능
• e.g. 첫 글자 기준 샤딩:
  • 두 대일 경우:
    • 서버 1에는 'a'~'m'로 시작하는 쿼리 저장
    • 서버 2에는 'n'~'z'로 시작하는 쿼리 저장
  • 세 대일 경우:
    • 서버 1에 'a~'i'로 시작하는 쿼리 저장
    • 서버 2에 'j'~'r'로 시작하는 쿼리 저장
    • 서버 3에 's'~'z'로 시작하는 쿼리 저장
  • 이 방식은 최대 26개의 서버까지 분할 가능
    --> 샤딩을 첫n개 글자에 따라 계층적으로 하면 더 많은 서버 분할 가능
• 데이터를 균등하게 분배하는 샤딩:
  • 과거 질의 데이터 패턴을 분석하여 샤딩
  • 검색어 대응 샤딩 관리자가 어느 검색어가 어느 저장소 서버에 저장되는지 관리
  • e.g. 's'로 시작하는 검색어 양과 'u'~'z'로 시작하는 검색어 양이 같다면,
    • 서버 1에 's'로 시작하는 쿼리 저장
    • 서버 2에 'u'~'z'로 시작하는 쿼리 저장

 

 

4단계: 마무리

추가 논의 사항:

• 다국어 지원 확장: 트라이에 유니코드 데이터를 저장
• 국가별 인기 순위가 다른 경우: 국가별로 다른 트라이를 사용
• 실시간 검색 추이 반영:
  • 현 설계안에는 부적합한 이유:
    • 작업 서버가 매주 한 번만 갱신
    • 실시간으로 트라이를 구성하는 데는 너무 많은 시간이 소요됨
  • 개선방향:
    • 샤딩을 통해 작업 대상 데이터 양을 줄임
    • 순위 모델을 변경하여 최근 검색어에 높은 가중치를 주게 함
    • 데이터가 스트리밍되는 경우를 고려한 특별한 시스템 필요
      (아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등)