13장

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

• 사용자가 입력하는 단어는 검색어의 첫 부분

• 5개의 자동완성 검색어가 표시되어야 함

• 검색어 인기 순위를 기준으로 5개가 선정됨

• 맞춤법 검사 기능이나 자동수정은 지원하지 않음

• 질의는 영어

• 대문자나 특수문자 처리는 없음 (소문자만 사용)

• DAU 기준 천만명

요구사항

• 빠른 응답 속도

• 연관성

• 정렬

• 규모 확장성

• 고가용성

개략적 규모 추정

• 일간 능동 사용자 천만명

• 한 사용자는 매일 10건의 검색을 수행한다고 가정

• 평균적으로 20바이트의 메시지를 검색 (1문자 1바이트)

• 1회 검색당 20건의 요청이 백엔드로 전달됨

• 초당 24000건의 QPS

• 최대 QPS = QPS * 2 = 대략 48000

• 질의 가운데 20% 정도는 신규 검색어 - 매일 0.4GB의 신규 데이터가 시스템에 추가됨

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

• 데이터 수집 서비스

  • 사용자가 입력한 질의를 실시간으로 수집

• 질의 서비스

  • 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓음

데이터 수집 서비스

• 빈도 테이블이 있다고 가정

질의 서비스

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

3단계 상세 설계

• 트라이 자료 구조

  • 해당 접두어를 표현하는 노드를 찾는다. 시간 복잡도는 O(p) (p: 접두어의 길이)

  • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효노드를 찾는다. 시간 복잡도는 O(c) - 주어진 노드의 자식 노드 개수)

  • 유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾는다. 시간 복잡도는 O(clogc)

  • 최악의 경우 k개의 결과를 얻기 위해 전체 트라이를 다 검색해야 함

    • 접두어 최대 길이 제한

    • 각 노드에 인기 검색어를 캐시

  • 각 단계의 시간 복잡도가 O(1)ㅇ로 바뀌어서 알고리즘의 복잡도도 O(1)으로 바뀐다.

• 데이터 수집 서비스

  • 매번 수천만 건의 질의가 입력될텐데 그때마다 트라이가 갱신되면 질의 서비스가 심각하게 느려질 것이다.

  • 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지않을 것이다. 그러니 트라이는 그렇게 자주 갱신할 필요가 없다.

  • → 로그 취합 서버를 이용해서 트라이 데이터베이스를 매주 갱신하고, 매주 데이터 베이스를 스냅샷하여 트라이 캐시로 사용한다.

• 질의 서비스

  • 검색 질의 - 로드 밸런서 - API 서버 - 트라이 캐시 - 트라이 데이터베이스

  • AJAX 요청 - 새로고침 할 필요 없어짐

  • 브라우저 캐싱 - 제안된 검색어를 브라우저 캐시에 넣어둠. (구글은 제안된 검색어를 한 시간 동안 캐시해 둔다.)

  • 데이터 샘플링 N개 요청 가운데 1개만 로깅하도록 한다.

• 규모 확장이 가능한 저장소

  • 첫 글자를 기준으로 샤딩한다 - 균등하게 분배되지 않음

  • 검색어 대응 샤드 관리자를 둔다. (과거 질의 데이터의 패턴을 분석하여 샤딩함)

    • 라이브로 업데이트할 수 있는건가? 아니면 샤딩할때마다 리셋하는건가?

      • d,e가 붙어 있었음 → d랑 e가 분리가 됨 → 옮기는 동안에는 d,e쪽 보고 있다가 샤딩한 후 샤딩된 d,e를 보도록 함

• 트라이 연산

  • 트라이 갱신

    • 매주 한 번 갱신

    • 각 노드를 개별적으로 갱신 - 성능이 좋지 않음

  • 검색어 삭제

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

4단계 마무리

• 다국어 지원

  • 유니코드 데이터를 저장해야함

• 국가별로 다른 인기 검색어 순위

  • 국가별로 다른 트라이 사용

• 실시간으로 변하는 검색어의 추이 반영

  • 지금 구조로는 안됨

  • 샤딩을 통해 대상 데이터의 양을 줄인다

  • 순위 모델을 바꾸어 최근 검색어에 보다 높은 가중치를 주도록 한다

  • 스트림 프로세싱을 위해 맵리듀스, 스파크 스트리킹, 카프카 등이 필요하다.