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

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

• 요구 사항

  • 빠른 응답 속도

  • 연관성

  • 정렬

  • 규모 확장성

  • 고가용성

• 개략적 규모 추정

  • 일간 능동 사용자(DAU)는 천만 명으로 가정한다.

  • 평균적으로는 한 사용자는 매일 10건의 검색을 수행한다고 가정한다.

    • 문자 인코딩 방법으로는 ASCII를 사용한다고 가정할 것이므로, 1문자 = 1바이트이다.

    • 질의문은 평균적으로 4개 단어로 이루어진다고 가정할 것이며, 각 단어는 평균적으로 다섯 글자로 구성된다고 가정할 것이다.

    • 따라서 질의당 편균 4 x 5 = 20바이트이다.

  • 검색창에 글자를 입력할 떄마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보낸다. 따라서 1회 검색당 20건의 요청이 백엔드로 전달된다.

  • 대략 초당 24,000건의 QPS가 발생할 것이다. (=10,000,000 사용자 x 10질의/일 x 20자 / 24시간/ 3600초)

  • 최대 QPS = QPS x 2 = 대략 48,000

  • 질의 가운데 20% 정도는 신규 검색어라고 가정할 것이다. 따라서 대략 0.4GB 정도다.

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

• 개략적으로 시스템은 두 부분으로 나뉘다.

  • 데이터 수집 서비스

    • 빈도 테이블

      
  • 질의 서비스

    • 빈도 테이블

      

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

3단계 : 상세 설계

• 트라이(trie) 자료구조

  

  • 시간 복잡도 개선

    • 접두어의 최대 길이 제한

    • 각 노드 별 인기 검색어 캐시

      
• 데이터 수집 서비스

  

  트라이 데이터베이스로 사용할 수 있는 선택지로는 다음 두 가지가 있다.

  • 문서 저장소 : 새 트라이를 매주 만들 것이므로, 주기적으로 트라이를 직렬화하여 데이터베이스에 저장할 수 있다. MongoDB 같은 문서 저장소를 활용하면 이런 데이터를 편리하게 저장할 수 있다.

  • 키-값 저장소 : 트라이는 아래 로직을 적용하면 해시 테이블 형태로 변환 가능하다.

    • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환

    • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환

    
• 질의 서비스

  • 비효율성을 개선한 설계안

  
• 트라이 연산

  • 트라이 생성

    • 트라이 생성 작업은 서버가 담당하며, 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용한다.

  • 트라이 갱신

    • 매주 한 번 갱신

    • 트라이의 각 노드를 개별적으로 갱신

  • 검색어 삭제

    • 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 한다.

• 저장소 규모 확장

  

4단계 : 마무리

Ref : https://github.com/G33kzD3n/Catalogue/blob/master/System%20Design%20Interview%20An%20Insider%E2%80%99s%20Guide%20by%20Alex%20Xu%20(z-lib.org).pdf