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

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

빠른 응답 속도문자 입력에 대한 자동완성 단어 노출은 100ms 이내여야 한다연관성입력한 단어와, 자동완성 단어는 연관 된 단어여야 한다정렬자동완성 단어 선정 계산 결과는 인기도 등의 순위 모델에 의해 정렬 되어야 한다규모 확장성시스템이 많은 트래픽을 감당할 수 있도록 확장이 가능해야 한다고가용성시스템의 일부에 장애가 발생하거나, 느려지거나, 예상치못한 네트워크 문제가 발생해도 시스템 사용은 계속 가능해야 한다개략적 규모 추정일간 능동 이용자 DAU 는 1000만 명으로 가정평균적으로 한 사용자는 하루 10건의 검색을 수행평균적으로 20 byte 규모의 데이터를 입력글자가 입력 될 떄마다.

폴더 구조와 폴더명

검색어 작업 같은 작은 작업 였지만 리액트 특성상 컴포넌트로 하나하나 나누어서 작업 진행하기 때문에 폴더 구조와 폴더명이 중요한것을 알게되었습니다. Pages에는 뭐가 들어가야하는지 다른 사람들이 보시면 폴더와 파일명을 봤을때 그 로직이 조금은 어떤것일꺼다. 이런것은 알아야할수있게 정하는게 중요합니다. 자기가 나중에 봤을때를 위해서도 그렇고 확장가능성을 생각해봤을때도 필요한 부분입니다. 이때는 기능에 더 중점을 주는 느낌이 강했다면 다음에는 이렇게 사소하다고 생각되는 부분이지만 큰 역할을 하는 부분을 알아차릴수있었습니다.

데이터 수집 서비스

지금까지 살펴본 설계안은 사용자가 검색창에 타이핑을 할 때마다. 실시간으로 데이터를 수정했다. 이 방법은 다음 두 가지 문제로 실용적이지 못합니다.

매일 수천만 건의 질의가 입력될 텐데 그때마다. 트라이를 갱신하면 질의 서비스를 심각하게 느려질 것입니다. 처음 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌지 않을 것입니다. 그러니 트라이는 자주 갱신할 필요가 없습니다.. figure 139는 데이터 평가 서비스의 수정된 설계안입니다.

트라이 삭제

혐오성이 짙거나, 폭력적이거나, 성적으로 노골적이거나, 각양각색으로 무모한 질의어를 자동완성 결과에서 제거해야 합니다. 이를 위한 좋은 방법은 figure 1314와 같이 트라이 캐시 앞에 필터 계층을 두고 부적절한 질의어가 반환되지 않도록 하는 것입니다. 데이터베이스에서 해당 검색어를 물리적으로 삭제하는 것은 다음번 업데이트 사이클에 비돌기적으로 진행하면 됩니다.

트라이tri 자료구조

접두어prefix의 길이n 트라이 안에 있는 노드 개수c 주어진 노드의 자식 노드 개수 라고 하였을 때 검색어 자동완성을 위한 데이터를 탐색하는데 걸리는 시간 복잡도는 다음과 같다. 해당 접두어를 발언하는 노드를 찾습니다. 시간 복잡도는 Op입니다. 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유호 노드를 찾습니다. 합법인 검색 문자열을 구성하는 노드가 유효 노드다. 시간 복잡도는 Oc 입니다.

유효 노드들을 정렬하여 가장 인기 있는 검색어 k개를 찾습니다. 시간 복잡도는 O(clogc)입니다. 정리해보시면 Op Oc Oclogc 입니다. 일반적으로 이야기 하는 트라이 자료구조의 시간복잡도는 다음과 같았습니다.

질의 서비스

질의 서비스는 데이터베이스를 활용하여 최고 인기 검색어 다섯 개를 골라낸다. 검색 질의가 로드벨런서로 전송됩니다. 로드밸런서는 해당 질의를 API 서버로 보낸다. API 서버는 트라이 캐시에서 데이터를 가져와 해당 요청에 대한 자동완성 검색어 제안 응답을 구성합니다. 데이터가 트라이 캐시에 없는 경우 데이터를 데이터베이스에서 가져와 캐시에 채운다. 질의 서비스 성능 향상을 위해 아래와 같은 최적화 방안들이 있습니다.

노드에 인기 검색어 캐시

각 노드에 k개의 인기 검색어를 저장해 두면 전체 트라이를 검색하는 일을 방지할 수 있어요. 510개 정도의 자동완성 제안을 표시하면 충분하므로, k는 작은 값입니다. figure 138은 개선된 트라이 구조다. 각 노드에 가장 인기 있는 검색어 다섯 가지를 저장하도록 했다. 앞의 두 가지 최적화 기법을 적용하면 시간 복잡도가 어떠한 방안으로 달라지는지 알아보시면 다음과 같다.

접두어 노드를 찾는 시간 복잡도는 O1입니다.

최고 인기 검색어 5개를 찾는 질의의 시간 복잡도는 O1로 바뀐다. 각 단계의 시간 복잡도가 O(1)로 바뀐 덕분에 최고 인기 검색어 k개를 찾는 전체 알고리즘의 복잡도도 O(1)로 바뀌게 됩니다.

추가적인 아이디어

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

순위 모델ranking model 정책을 바꾸어, 최근 검색 된 검색어에 보다.

자주 묻는 질문