[keyword] 13장 - 검색어 자동완성 시스템

[ngwoon]

주제

'13장 - 검색어 자동완성 시스템'을 읽고 내용을 요약하거나,
중요✨ 하다고 생각하는 키워드 및 관련 설명을 코멘트로 달아주세요

연관 챕터

40

@caffeine-library/readers-system-design-interview

[ngwoon]

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

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

요구사항

• 빠른 응답 속도

  사용자가 입력한 쿼리와 관련된 인기연관검색어 K개를 제공해야 한다.

  페이스북 검색어 자동완성 시스템에 관한 문서에 따르면, 시스템 응답속도는 100ms 이내여야 한다.

• 연관성

  사용자가 입력한 쿼리와 연관된 검색어를 제공해야 한다.

• 정렬

  연관검색어들을 제공할 때, 인기도 등의 순위 모델 (ranking model) 에 의해 정렬되어야 한다.

• 규모 확장성

  많은 트래픽을 감당할 수 있도록 extensibility를 갖춰야 한다.

• 고가용성

  시스템 일부에 장애가 발생하거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 서비스를 제공할 수 있어야 한다.

개략적 규모 추정

• DAU는 천만 명

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

• 질의할 때 마다 평균적으로 20바이트를 입력한다.

  • 문자 인코딩 방식은 ASCII를 사용할 것으로 가정. 즉, 1문자 = 1바이트
  • 질의문은 평균적으로 4개의 단어로 이루어지고, 각 단어는 5문자로 이루어진다고 가정한다.

• 검색창에 글자를 입력할 때 마다 백엔드에 요청을 보낸다.

  만약 “dinner” 를 입력한다면, d, di, din, dinn, dinne, dinner 여섯 번의 요청이 전송된다.

• 지금까지의 조건을 바탕으로 QPS를 계산해보면, 24000 QPS가 된다.

• 최대 QPS는 48000으로 가정한다.

• 질의 가운데 20%를 신규 검색어라고 가정한다. 즉, 신규 검색어는 약 0.4GB 정도이다.

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

검색어 자동완성 시스템은 크게 두 파트로 나눌 수 있다.

• 데이터 수집 서비스

  사용자가 입력한 질의를 실시간으로 수집하는 서비스

  질의문 - 빈도 쌍을 저장하는 “빈도 테이블” 을 관리하는 방식을 생각해 볼 수 있다.

• 질의 서비스

  사용자가 질의를 입력하면, 연관된 k개의 검색어를 제공하는 서비스

  빈도 테이블에서 빈도가 높은 k개의 검색어를 뽑아내는 SQL를 생각해 볼 수 있다.

3. 상세 설계

RDB 대신 Trie

검색어 자동완성 서비스에는 RDB에 검색어를 저장하는 것보다 더 잘 어울리는 Trie 자료구조가 있다.

Trie 자료구조의 핵심은 아래와 같다.

• 각 노드는 글자 하나를 저장하며, 최대 26개의 자식 노드를 가질 수 있다.
• leaf노드는 검색어 하나를 의미하며, 그 외 노드는 접두사를 의미한다.

검색어 - 빈도 쌍은 Trie 자료구조의 leaf노드에 저장된다.

이 기본적인 Trie를 사용하면, 최악의 경우 전체 Trie를 전부 조회해야할 수도 있다.

이를 보완하기 위해 책에서 두 가지 방법을 제시한다.

접두어의 최대 길이 제한

사용자가 긴 검색어를 입력하는 경우는 거의 없다.

따라서 접두어의 최대 길이를 제한해두면, 접두어 노드를 찾는 과정이 O(1)에 가까워진다.

각 노드에 검색어-빈도 쌍 캐시

접두어 노드를 찾은 뒤, 그와 연관된 검색어들을 찾는 과정 또한 시간이 오래 걸릴 수 있다.

접두어 노드에 검색어 - 빈도 쌍을 k개 캐시해둔다면, 따로 검색어 노드를 찾을 필요가 없게된다.

(단, 저장공간이 더 많이 필요하다.)

데이터 수집 서비스

사용자가 질의를 던질 때마다 Trie를 업데이트한다면 서버 부하가 엄청날 것이다.

따라서 사용자의 질의를 수집해서, 적절하게 조합한 다음, 적절한 주기로 Trie를 갱신할 수 있는 “데이터 수집 서비스” 가 필요하다.

• 데이터 분석 서비스 로그

  검색어 - 타임스탬프 쌍들이 저장되어있는 로그 파일이다.

• 로그 취합 서버

  데이터 분석 서비스 로그를 받아서, 검색어 - 빈도 쌍을 만든다.

• 취합된 데이터

  검색어 - 빈도 쌍의 집합이다.

• 작업 서버

  취합된 데이터를 주기적으로 Trie에 반영하는 서버이다.

  주기는 애플리케이션의 성격에 따라 달라진다.

  (실시간 반영이 중요할수록 주기가 짧아진다.)

• Trie 데이터베이스

  Trie 자료구조가 저장되는 곳이다.

  • 문서 저장소 (document store)

    Trie 자료구조를 직렬화하여 저장하는 방식

    MongoDB가 대표적인 예시이다.

  • 키-값 저장소

    노드의 접두어(혹은 검색어) 를 key로, 빈도 혹은 캐시된 값들을 value로 저장하는 방식

• Trie 캐시

  Trie 데이터베이스가 갱신되면, 그 스냅샷을 따서 캐시에 보관하면 사용자에게 더 나은 응답 속도를 제공할 수 있다.

질의 서비스

질의 서비스는 아래와 같은 흐름으로 사용자에게 검색어 k개를 제공한다.

검색어 제공은 굉장히 빠르게 제공되어야 한다. 서버 latency를 줄이기 위한 몇 가지 방법이 있다.

• ajax 요청

• 브라우저 캐싱

  관련 검색어는 짧은 시간에 변하는 경우가 드물다. 따라서 브라우저 측에 캐싱해두고 일정 시간동안 사용하게 하는 방법이 효율적이다.

• 데이터 샘플링

  모든 질의 결과를 로깅하면 서버에 부하가 크기 때문에, N개 요청 중 하나만 로깅하는 방법

[hyunrrr]

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

요구사항

• 빠른 응답속도
• 연관성: 자동완성되어 출력되는 검색어는 사용자가 입력한 단어와 연관성이 있어야 함
• 정렬: 인기도등의 순위모델에 의해 정렬되어 있어야 함
• 규모 확장성: 시스템은 많은 트래픽을 감당할 수 있도록 확장가능해야 함
• 고가용성: 시스템의 일부에 문제가 생겨도 항상 사용 가능해야 함

개략적 규모추정

• 일간 능동 사용자(DAU)는 천만 명으로 가정
• 평균 1인당 하루 10건의 검색을 한다 가정
• 한번의 질의에 20바이트의 데이터를 입력한다 가정
• 즉, 1회 검색당 20건의 요청이 자동완서 백엔드에 전송됨
• 대략 초당 24000건의 질의가 발생
• 최대 QPS는 24000*2 = 48000
• 질의 가운데 20%는 신규 검색어라 가정, 매일 0.4GB의 신규데이터가 추가됨

개략적 설계안

• 데이터 수집 서비스(실시간)
• 질의 서비스(관계형 데이터베이스 사용)

상세 설계(개략적 설계 개선안)

트라이 자료구조(관계형 데이터베이스 대신 사용)

접두어 길이: p, 트라이 안에 있는 노드 개수: n, 주어진 노드의 자식 노드 개수: c일때 접두어를 표현하는 노드를 찾음: O(p) 접두어표현 노드부터 하위의 모든 유효 노드를 찾음: O(c) 유효 노드를 정렬: O(clogc) 한 번의 질의 시간복잡도: O(p) + O(c) + O(clogc)

두 가지 방법으로 시간복잡도를 최적화 할 수 있음

1. 접두어의 최대 길이를 제한 -> p에 제한을 두면 p=최대 길이 상수, O(p) -> O(상수) -> O(1)이 된다.
2. 각 노드에 인기 검색어를 캐시 -> 캐시에 저장된 내용을 사용하면 됨, O(1) 최적화된 시간복잡도: O(1)

데이터 수집 서비스

실시간으로 데이터를 갱신하면 두 가지 문제가 있다.

1. 매일 수천만 건 발생하는 질의로 트라이를 실시간 갱신하면 서비스는 심각하게 느려짐
2. 인기 검색어는 자주 바뀌지 않음, 굳이 트라이를 자주 갱신할 필요가 없음

• 데이터 분석 서비스 로그(검색한 원본 질의 데이터 보관)
• 로그 취합 서버(방대하고 형식이 제각각인 로그를 취합, 실시간 어플리케이션이 아니면 일주일에 한번 취합해도 충분)
• 취합한 데이터(질의, 시간(취합주기단위), 빈도수)
• 작업 서버(트라이 자료구조를 만들고 트라이 데이터베이스에 저장하는 역할을 담당)
• 트라이 캐시(데이터를 메모리에 유지해 읽기 연산 성능을 높힘, 주에 한번 스냅샷을 떠 갱신)
• 트라이 데이터베이스(트라이 데이터를 저장)

질의 서비스

1. 검색 질의가 로드밸런서로 전송
2. 로드밸런서는 해당 질의를 api서버로 전송
3. api서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성해야 함
4. 데이터가 캐시에 없으면 데이터베이스에서 가져와 캐시를 채움

트라이 연산

• 트라이 생성(작업 서버가 담당)
• 트라이 갱신(매주 한번 갱신)
• 검색어 삭제(api서버와 트라이 캐시 사이에 필터를 둬 부적절한 단어 삭제)

저장소 규모 확장

• 영어단어만 지원하는 경우 각 알파벳별 검색어 양에 따라 적절히 샤딩한다.(여러 컴퓨터에 나눠담음)
• 검색어가 1. 어느 샤드에 있는지 조회하고, 2. 해당샤드에서 데이터를 추출한다.
• 시스템에 맞게 적절한 방법을 이용하면 됨

[binchoo]

이번 시스템에서 성능 향상을 도모하는 기법 중, 두 가지가 반복적으로 사용됨을 느꼈습니다.

첫째는, 탐색 공간의 일부를 배제하는 것입니다. 모집단을 모두 살피지 않고, 통계적으로 유효한 샘플 집단만 가지고도 기능 요구사항을 적당히 만족할 수 있으며, 품질도 확보할 수 있습니다.

둘째는, 캐싱을 이용하는 것입니다. 사용자의 요청을 받아서 부랴부랴 작업을 수행하는 방식을 지양합니다. 대신, 과거 작업이 도출하고 메모리로 저장했던 값을 읽어 반환합니다.

탐색 공간을 제한하기

• 트라이 노드가 될 수 있는 단어의 길이를 50자 이내로 함 길이가 50자 이상인 단어는 검색어로서 매력적이지 않은데도 트라이 자료 깊이만 늘릴 뿐입니다. 유효한 단어 길이를 제한하니 탐색 공간의 성장을 제한할 수 있고, 접두사 검색 시간을 O(50) 이내로 끝낼 수 있게 되었습니다.

• 데이터 수집 서비스는 모집단의 쿼리 로그가 아닌 표본 집단의 쿼리 로그를 사용함. 검색어 서비스는, 책이 가정하길 24,000 QPS를 다루는 인기있는 서비스입니다. 이 모집단이 생산하는 로그를 다루겠다고 한다면, 통계적 지식이 모자란 사람입니다.

  

캐싱하기

• 자식 노드들을 줄 세운 리스트를 부모 트라이 노드에서 캐싱함. 원래는 사용자의 키보드 입력에 반응하여 접두사 노드의 자손 노드들을 우선순위에 따라 줄 세우는 작업을 했습니다. 실시간 반영 데이터가 필요한 게 아니기 때문에 이 연산은 반복해서 할 이유가 없습니다.

  "요청에 의해 작업을 하지 않는다"랑 같은 맥락에서, 이 시스템은 데이터 분석 서비스를 따로 두고 1주일마다 비동기적으로 트라이 자료구조를 갱신하는 방식을 택했습니다.

• 쿼리 요청에 대해 HTTP 응답을 내려주면서 cache-control 정책을 활용하여 1시간 동안 브라우저에 결과물을 저장함. 검색어 자동완성 목록 자료는 실시간성을 배제하고 있으므로 괜찮은 접근 방식입니다. 브라우저와 API 서버간의 통신을 줄일 수 있게 되었습니다.

• API 서버가 트라이를 캐시 레이어에서 참조하도록 함. API서버 - 캐시 레이어 - 문서DB(몽고DB) 순으로 배치함으로써 API 서버와 DB 사이의 통신을 줄일 수 있게 되었습니다.

  

---

성능 향상에 대한 품질 요구사항에 대응할 때는, 탐색 공간의 배제 & 캐싱 두 기법을 기억해둔다면 좋을 것 같습니다 . 동일한 접근 방식이 알고리즘 문제를 구현할 때도 필요하다고 느꼈습니다.