가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 13장 ) 검색어 자동완성 시스템

 

 

 

 

검색어 자동완성 시스템 

• 자동완성 (autocomplete, typeahead, search-as-you-type, incremental search) 
  • 입력중인 글자에 맞는 검색어가 자동으로 완성되어 표시 

 

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

• 자동완성 될 검색어의 범위 
  • ex) 첫글자, 중간부분 등 
• 표시되는 자동완성 검색어의 갯수 
• 자동완성 검색어를 고르는 기준 
• 맞춤법 검사 기능 제공 여부 
• 질의어의 종류 
  • ex) 영어, 한국어 
• 대문자나 특수문자의 처리 여부 
• 사용자 수 
• 예시 요구사항 
  • 100밀리초 이내의 빠른 응답 속도 
  • 자동완성되어 출력되는 검색어와 사용자가 입력한 단어의 연관성 
  • 인기도 등 순위모델에 의한 정렬
  • 트래픽을 감당할 수 있도록 확장 가능해야 함 
  • 시스템 장애가 발생하더라도 지속 사용가능한 고가용성 
• 개략적 규모 측정 
  • DAU = 천만명 
  • 한 사용자가 매일 수행하는 검색의 수 = 10건
  • 질의시 사용되는 데이터의 양 = 20바이트 
  • 질의문 평균 단어의 수 = 4개, 각 단어의 평균 글자 수 = 다섯글자 
  • 질의당 평균 크기 = 4x5 = 20바이트 
  • 검색창에 글자를 입력할 때 마다 클라이언트는 검색어 자동완성 백엔드에 요청을 보내므로, 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달 됨 
  • 초당 질의(QPS) = 10000000사용자 x 10질의 / 일 x 20자/24시간/3600초 = 24000건
  • 최대 QPS = QPS x 2 = 대략 48000
  • 신규 검색어의 수 = 질의의 20% 
    • 매일 신규로 등록되는 데이터의 양 = 10000000사용자 x 10질의 / 일 x 20자 x 20% = 0.4G 

 

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

• 데이터 수집 서비스 (data gathering service)
  • 사용자가 입력한 질의를 실시간으로 수집하는 시스템
    • 데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지 않지만, 설계안을 만드는 출발점으로는 괜찮음 
  • 빈도테이블 (frequency table) 
    • 질의문과 사용빈도를 저장하는 테이블 
    • query 
      • 질의문을 저장하는 필드 
    • frequency 
      • 질의문이 사용된 빈도를 저장하는 필드 
    • 가장 많이 사용되는 검색어는 frequency를 사용한 SQL 쿼리 문으로 계산가능 
      • 단, 데이터가 많아지면 데이터베이스가 병목이 될 수 있음 
• 질의 서비스 (query service) 
  • 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스 

 

 

3단계 상세 설계 

• 트라이(trie) 자료구조 
  • 데이터 베이스 양이 많아지면 병목이 될 수 있었던 점을 트라이 자료구조 최적화를 통해 응답시간을 줄일 수 있음 
  • trie = retrieval = 문자열을 꺼내는 연산에 초점을 맞추어 설계뙨 자료구조 
    • 트라이는 트리 형태의 자료구조 
    • 루트노드는 빈 문자열을 나타냄 
    • 각 노드는 글자 하나를 저장하며 26개 (해당 글자 다음에 등장할 수 있는 모든 글자의 개수)의 자식 노드를 가질 수 있음 
    • 각 트리 노드는 하나의 단어, 또는 접두어 문자열을 나타냄 
    • 용어 
      • p : 접두어 (prefix)의 길이 
      • n : 트라이 안에 있는 노드 개수 
      • c : 주어진 노드의 자식 노드 개수 
    • 가장 많이 사용된 질의어 k개를 찾는 과정 
      • 해당 접두어를 표현하는 노드를 찾음 
        • 시간복잡도 = O(k) 
      • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾음 
      • 유효한 검색 문자열을 구성하는 노드가 유효 노드 
        • 시간 복잡도 = O(c) 
      • 유효 노드를 정렬하여 가장 인기 있는 검색어 k개를 찾음 
        • 시간복잡도 = O(clogc) 
      • => 총 시간 복잡도 = O(p) + O(c) + O(clogc) 
      • 최악의 경우 k개 결과를 얻기 위해 전체 트라이를 모두 검색해야 할 수 있음 
      • 해결방안 
        • 1) 접두어의 최대 길이를 제한
          • 사용자가 검색창에 긴 검색어를 입력하는 일은 거의 없기 때문에 작은 정숫값으로 가정해도 안전 
        • 2) 각 노드에 인기 검색어를 캐시 
          • 각 노드에 인기 질의어를 캐시하면 검색어를 질의하는 시간 복잡도를 낮출 수 있음 
          • 단, 노드에 질의어를 저장할 공간이 많이 필요하게 됨 
            • 빠른 응답 속도가 중요할 때는 저장공간을 포기하더라도 좋은 선택지가 될 수 있음 
        • 두가지의 방안 적용 결과
          • 접두어 노드를 찾는 시간 복잡도는 O(1)로 바뀜 
          • 최고 인기 검색어 5개를 찾는 질의의 시간 복잡도도 O(1)로 바뀜 
            • 검색 결과가 이미 캐시 되어 있기 때문 
          • k개의 단어를 찾는 전체 알고리즘의 복잡도도 O(1)로 바뀜 
• 데이터 수집 서비스 
  • 매일 수천만건의 질의가 입력될 때마다 트라이를 갱신하면 질의 서비스는 느려짐 
  • 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것 
    • 자주 갱신할 필요가 없음 
    • 트라이를 만드는데 쓰는 데이터는 보통 데이터 분석 서비스나 로깅 서비스로부터 오기 때문에 자주 바꿔줄 이유가 없음 
  • 구성 요소
    • 데이터 분석 서비스 로그 
      • 질의에 관한 원본 데이터 보관 
      • 새로운 데이터가 추가될 뿐 수정은 이루어지지 않음 
      • 로그 데이터에는 인덱스를 걸지 않음
    • 로그 취합 서버 
      • 로그 데이터를 잘 취합하여 우리 시스템이 쉽게 소비할 수 있도록 해야함 
        • 일주일에 한번 정도로 로그를 취합해도 충분 
        • 면접 장에서 데이터 취합의 실시간성이 얼마나 중요한지 확인하는게 중요 
      • 취합된 데이터 예시 
        • query, time, frequency의 컬럼 등으로 구성 
    • 작업 서버 
      • 주기적으로 비동기적 작업을 실행하는 서버 집합 
    • 트라이 캐시 
      • 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실을 함 
      • 매주 트라이 데이터 베이스의 스냅샷을 떠 갱신 
    • 트라이 데이터베이스 
      • 지속성 저장소 
      • 선택지 
        • 문서 저장소 
          • 주기적으로 트라이를 직렬화하여 데이터베이스에 저장 
          • 몽고디비 같은 문서 저장소를 활용하면 데이터를 편리하게 저장할 수 있음 
        • 키-값 저장소 
          • 해시 테이블 형태로 변환 가능 
            • 트라이에 보관된 모든 접두어를 해시 테이블 키로 변환 
            • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환 
            • ex) b: (be:15, bee:20, beer:10, best:35)
• 질의 서비스 
  • 플로우
    • 1) 검색 질의가 로드밸런서로 전송
    • 2) 로드밸런서는 해당 질의를 API 서버로 전달 
    • 3) API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성 
    • 4) 데이터가 트라이 캐시에 없는 경우 데이터를 데이터베이스에서 가져와서 캐시에 채움 
      • 같은 접두어에 대한 질의가 오면 캐시에 보관된 데이터를 사용해 처리 가능 
      • 캐시 미스는 캐시 서버의 메모리가 부족하거나 캐시 서버에 장애가 있어도 발생 가능 
  • 질의 서비스 속도 개선 방안 
    • AJAX 요청 
      • 요청을 보내고 받기 위해 페이지를 새로고침할 필요가 없음 
    • 브라우저 캐싱 
      • 검색어 제안 결과가 쉽게 바뀌지 않기 때문에 제안된 검색어들을 브라우저 캐시에 넣어두면 후속 질의의 결과는 해당 캐시에서 바로 가져감
      • ex) 구글 검색 엔진 
        • cache-control 의 private : 사용자의 캐시에만 보관하고 공용 캐시에 저장되어서는 안된다는 뜻 
    • 데이터 샘플링 
      • 모든 질의 결과를 로깅하도록 하면 CPU 자원과 저장공간을 엄청나게 소진하기 때문에 데이터 샘플링 기법은 그럴때 유용 
      • N 개 요청 가운데 1개만 로깅 
• 트라이 연산 
  • 트라이 생성 
    • 작업 서버가 담당
    • 데이터 분석 서비스의 로그나 데이터베이스로부터 취합된 데이터를 이용 
  • 트라이 갱신 
    • 1) 매주 한번 갱신하는 방법 
      • 새로운 트라이를 만들고 기존 트라이를 대체 
    • 2) 트라이의 각 노드를 개별적으로 갱신하는 방법
      • 성능이 좋지 않음 
        • 트라이를 갱신할 때는 인기 검색어 질의 결과가 상위노드에도 저장되기 때문에 그 모든 상위 노드가 갱신되어야 하기 때문 
      • 트라이가 작을 때는 고려해볼 수 있음 
  • 검색어 삭제 
    • 혐오성이 짙거나, 폭력적이거나 성적으로 노골적이거나 여러가지로 위험한 질의어를 자동완성 결과에서 제거해야 함 
    • 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 해야함 
    • 물리적으로 삭제하는 방안은 다음번 업데이트 사이클에 비동기적으로 진행할 수 있음 
• 규모 확장이 가능한 저장소
  
  • 1) 단순하게 첫 글자를 기준으로 샤딩
    • 글자수에 따라 최대 샤딩 가능 서버가 제한됨 
  • 2) 계층적 샤딩 
    • 첫번째 글자는 첫번째 레벨의 샤딩, 두번째 글자는 두번째 레벨의 샤딩 등 
    • 단, 글자별로 보관 데이터가 다르기 때문에 데이터를 각 서버에 균등하게 배분 불가능 
  • 3) 과거 질의 데이터 패턴을 분석하여 샤딩하는 방법 
    • 검색어 대응 샤드 관리자가 어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리하고 검색어 양에 따른 샤드 배분 

 

 

4단계 마무리 

• 다국적 지원 
  • 트라이에 유니코드 데이터를 저장해야 함 
    • 유니코드는 세상에 존재하는 모든 문자 체계를 지원하는 표준 인코딩 시스템 
• 국가별 인기 검색어 순위 관리 
  • 국가별로 트라이를 사용 
  • 트라이를 CDN에 저장하여 응답 속도 개선 가능 
• 실시간으로 변하는 검색어 추이 반영 
  • 샤딩을 통해 작업 대상 데이터의 양을 줄임 
  • 순위 모델을 바꾸어 최근 검색어보다 높은 가중치를 줌
  • 데이터가 스트림 형태로 올 수 있어 한번에 모든 데이터를 동시에 사용할 수 없을 가능성이 있다는 점을 고려해야 함 
    • 데이터가 지속적으로 생성된다는 뜻 
    • 스트림 프로세싱에는 특별한 종류의 시스템이 필요 
    • ex) 아파치 하둡 맬리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등