[가면대설] 13장. 검색어 자동완성 시스템

검색어 자동완성

💡검색어 자동완성

입력 중인 글자에 맞게 검색에가 자동으로 완성되어 표시되는 것

 

https://techblog.gccompany.co.kr/%EC%97%AC%ED%96%89-%EA%B2%80%EC%83%89%EC%9D%98-%ED%8E%B8%EB%A6%AC%ED%95%A8%EC%9D%84-%EB%8D%94%ED%95%98%EB%8B%A4-%ED%95%B4%EC%99%B8-%EC%9E%90%EB%8F%99%EC%99%84%EC%84%B1-%EA%B0%9C%EC%84%A0-75c4d146d43c

여행 검색의 편리함을 더하다 : 해외 자동완성 개선

 

 

요구사항 분석

🔑 요구사항

• 빠른 응답 속도 : 검색어를 입력할 때 자동완성 검색어도 빠른 시간 안에 표시 ex) 100밀리초
• 연관성 : 사용자가 입력한 단어와 연관성이 있어야됨 -> 연관 단어를 가져오는 알고리즘 필요
• 정렬 : 자동완성 검색어는 인기순으로 정렬되어야 함
• 규모 확장성 : 시스템은 많은 트래픽을 감당하도록 확장 가능해야 함.
• 고가용성 : 시스템의 일부가 장애가 발생하거나, 예상치 못한 네트워크 문제가 생겨도 시스템은 계속 사용 가능 해야함.

 

🔑 개략적 규모 추정

• 천만 사용자가 하루에 서비스를 활용
• 한 사용자는 매일 10건의 검색을 한다고 가정
• 질의할 때마다 평균 20바이트의 데이터를 입력한다고 가정
  • 평균적으로 한 질의에 4개의 단어, 한 단어에는 5개의 글자가 들어간다고 가정.
• 검색창에 검색 단어 한 개를 입력할 때마다 검색어 자동완성 백엔드에 요청을 보낸다.
  • 영어 기준 1회 검색 질의 당 20건의 백엔드 요청이 들어온다.

 

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

대략 20%, 약 0.4GB 정도가 새로운 데이터라고 가정한다.

 

 

개략적 설계안

개략적 설계에서는 데이터 수집 서비스와 질의 서비스, 크게 2개의 서비스로 구현한다.

 

📍 데이터 수집 서비스

- 사용자가 입력한 질의를 실시간으로 수집하는 시스템, 우선순위를 정하는 매커니즘은 아직 없음

 

 

📍 질의 서비스 (Query Service)

- 사용자가 입력한 단어에 맞춰 질의한 요청에 따라 자동완성 검색어를 반환하는 서비스

- 검색어가 관계형 데이터베이스에 저장돼 있다 가정하면, SQL 쿼리로 자동완성 검색어를 질의한다.

- 이때 DESC 명령어를 이용해 우선순위를 반영한다.

 

 

단점

- 데이터가 아주 많아지면 문제다.

- 관계형 데이터베이스는 I/O에 특화되어 있지 않기에 서버 성능이 저하된다.

 

 

개선점

- 많은 검색어를 대상으로 빠른 조회가 가능한 스토리지나 데이터베이스가 필요하다.

- 빠른 조회를 위한 캐시 서비스가 필요하다.

- 검색어의 우선순위를 대처할 수 있는 알고리즘이 필요하다.

 

 

상세 설계

데이터 수집 서비스, 질의 서비스라는 두 부분으로 구성된 설계안은 첫 출발로서는 좋으나, 실제 설계에서는 보충이 필요하다. 특히 우선순위에 대처할 수 있는 알고리즘이나 자료구조가 필요하다. 따라서 트라이(trie) 자료구조가 포함된다.

• 트라이 자료구조
• 데이터 수집 서비스
• 질의 서비스
• 규모 확장이 가능한 저장소
• 트라이 연산

 

1️⃣ 트라이 자료구조

앞의 데이터 수집 서비스에선 RDB를 사용했지만 I/O 성능 이슈로 적합하지 않았다. 따라서 트라이라는 문자열을 간략하게 저장할 수 있는 자료구조를 도입한다.

 

 

 

트라이 자료구조

 

 

• 트라이는 트리 형태 자료구조
• 트리의 루트 노드는 빈 문자열이다
• 각 노드는 글자 하나를 저장하며, 26개(영어 기준)의 자식 노드를 가질 수 있다
• 각 트리 노드는 하나의 단어, 접두어 문자열을 나타낸다.

트라이 자료구조로 우선순위도 표현할 수 있다. 노드에 저장하는 자료의 형태를 ["단어나 접두어(query) : 빈도(frequency)"]로 나타내면 된다.

💡트라이 구조 시간복잡도

 

1️⃣ 용어 정리

p : 접두어(prefix)의 길이

n : 트라이 안에 있는 노드 개수

c : 주어진 노드의 자식 노드 개수

 

2️⃣ 시간복잡도 계산

사용자가 질의할 때 가장 많이 사용된 자동완성 검색어 k개는 다음과 같이 찾는다.

 

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

- 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는다. O(c)

- 유효 노드를 정렬하여 가장 인기 있는 검색어 K개를 찾는다. O(clogc) -> 합병, 퀵 정렬

 

3️⃣ 시간복잡도 단축

k개의 자동완성 검색어를 얻기 위해 최악의 경우 모든 트라이 노드를 다 찾아야 할 수 있다.

다음과 같은 방법으로 시간복잡도를 단축할 수 있다.

 

🔑 접두어의 최대 길이 계산

검색어의 최대 길이를 제한해 노드의 생성을 막자. 어차피 사용자는 엄청 긴 검색어를 잘 검색하지 않는다.

트라이의 노드 생성을 막는다면 그만큼 검색어나 접두어를 찾는 시간이 줄어든다.

 

🔑 빠른 조회를 위한 트라이 캐시

노드 안에 해당 접두어로 이루어지면서 자주 탐색되는 검색어들을 노드 안의 캐시 형식으로 저장해 놓는다.

물론 캐시 미스를 해결하는 방법에는 오히려 더 많은 시간이 걸릴 수 있다.

 

2️⃣ 데이터 수집 서비스

앞의 설계안에서는 사용자가 한 글자 적을 때마다 자동완성 검색어 백엔드로 요청을 보냈다. 이는 다음과 같은 문제를 불러온다.

• 초당 24,000의 질의를 감당하기엔 RDB는 느리다. 서비스 속도 저하를 불러온다.
• RDB에 질의가 들어오면 그에 맞춰 우선순위가 매번 바뀐다. 실제로는 그렇게 처리할 필요가 없다. 

데이터 수집 서비스 설계를 하기 위해선 자동완성 검색어 데이터의 소스는 어디인지, 데이터의 변경 주기는 어떻게 되는지를 살펴야 한다. 데이터 소스를 알면 수집 인프라를 설계할 수 있고, 변경 주기를 알면 데이터 수집 방식을 선택할 수 있다.

이번 예시에서는 로그를 통해 수집한 데이터를 저장한다고 가정한다.

 

📍 데이터 파이프라인
데이터를 수집하고 데이터를 사용하는 서비스에 맞게 변환하고 저장하는 모든 과정을 일컫는다.

데이터 파이프라인을 구성하기 위해선 다음과 같은 고민을 한다.
- 데이터 수집 방식으로 배치, 스트리밍 형식을 고민
- 데이터 웨어하우스, 데이터 레이크, 데이터 마트
- 객체 스토리지, 문서 스토리지, NoSQL 데이터베이스, RDB...

 

📍데이터 분석 서비스 로그

다양한 데이터 소스에서 수집된 데이터들이 저장되는 형식이다. 새로운 데이터가 추가될 뿐 수정은 이루어지지 않는다. 인덱스를 따로 사용하지 않는다.

• 로그, JSON과 같은 반정형 데이터 저장 방식

 

📍로그 취합 서버

데이터 분석 서비스로부터 나오는 로그는 양이 엄청나고 데이터 형식도 제각각인 경우가 많다. 이 데이터를 잘 취합하여 시스템이 쉽게 소비할 수 있도록 해야한다.

서비스에 따라 데이터 취합 주기를 짧게(스트리밍)가져갈 수 있고 길게(배치) 형식으로 가져갈 수 있다.

• 빠른 I/O 처리를 위한 데이터 웨어하우스, 데이터 마트 사용
• 다양한 파일 형식의 저장을 위한 데이터 레이크 사용
• 배치 or 스트리밍 데이터 수집과 그에 따른 인프라 설계

 

📍작업 서버

작업 서버(worker)를 두어 비동기적으로 데이터를 취합하고 트라이 구조를 만드는 작업 진행

 

• 작업 서버 등 파이프라인 관리를 위한 워크플로 관리 도구 사용(Airflow)
• 비동기 처리를 위한 코디네이터(SQS, Kafka)
• 분산 스토리지와 분산 처리를 위한 툴(Hadoop, Spark)

 

📍트라이 캐시와 데이터베이스

트라이 캐시는 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지해 빠른 I/O 달성.

트라이 데이터베이스, 트라이 자료구조를 저장하는 형식으로 문서 저장소, 키-값 저장소를 고민할 수 있음.

 

• 데이터 형식에 맞는 스토리지 결정
• 인메모리 캐시(Redis)

 

 

3️⃣ 질의 서비스

개략적 설계안에서는 RDB 데이터베이스와 SQL 쿼리를 이용해 우선순위 검색어를 골라냈다. 이제 트라이 데이터베이스와 이를 이용한 API 서버를 통해 우선순위 자동완성 검색어를 검색한다.

 

1. 검색 질의가 로드 밸런서로 전송
2. 로드 밸런서가 자동으로 API 서버에게 요청 전송
3. API 서버는 트라이 캐시에 맞는 검색어가 있는지 확인하고 없으면 데이터베이스로 질의가 넘어감
4. 데이터베이스에서 데이터를 가져와 캐시에 채움

 

💡 빠른 질의 서비스를 위한 대책

• AJAX 요청 : 페이지를 새로고침하지 않고 질의를 보내는 방법
• 브라우저 캐싱 : 트라이 캐시의 부하를 막기 위해 사용자의 브라우저에 검색어를 캐시하는 방법
• 데이터 샘플링 : 데이터베이스에서 데이터를 가져올 때 적은 데이터만 가져오는 방법

 

 

4️⃣ 트라이 연산

📍트라이 생성

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

 

📍트라이 갱신

배치 형식인지 스트리밍 형식인지 결정할 수 있음. 책에서는 배치 형식이 효율적이라고 추천.

 

스트리밍 형식을 사용하기 위해선 각 노드를 개별적으로 갱신해야 하는데, 자식 노드를 갱신하면 어쩔 수 없이 부모 노드를 갱신하기 때문에 컴퓨팅 자원이 과도하게 사용될 수 있음.

 

📍데이터 삭제

질의 시스템 중 API 서버에서 트라이 데이터베이스로 질의가 넘어 갈때 미들웨어를 둬 질의에 대한 필터링이 가능함.

 

https://techblog.woowahan.com/15764/

고르곤졸라는 되지만 고르곤 졸라는 안 돼! 배달의민족에서 금칙어를 관리하는 방법 | 우아한형

 

 

 

5️⃣ 저장소 규모 확장

언어 별로 접두어에 따라 단어 수의 편차가 존재함. 단어 수에 따라 서버의 수를 다르게 배치할 수 있다.

접두어 별로 균등하게 서버를 배분하기에는 불가능하다는 것이 이 단락의 핵심이다.

 

책에서는 검색어 대응 샤드 관리자(map)을 추천한다. 이 관리자는 단어 수가 많은 서버로 질의가 들어오면 어느 서버로 질의해야 한는지 알려준다. 이를 통해 불필요한 데이터 조회를 막을 수 있다.

 

 

6️⃣ 추가로 생각할 점

• 다국어 지원을 하려면 어떻게 해야하는가? => 유니 코드 고려
• 국가별로 인기 검색어 순위가 다르다면? => 국가별 CDN 사용
• 실시간으로 변하는 검색어는 어떻게 반영하는가? => 데이터 수집 프로세스를 스트리밍 형식으로 사용, 인프라 설계
• 샤딩
• 검색 엔진
• 순위 모델
• 데이터의 스트리밍 수집 : Apache Hadoop MapReduce, Apache Spark, Apache Storm, Apache Kafka

 

 

AI

 

https://d2.naver.com/helloworld/4896087

 

https://blog.naver.com/naver_search/223826386209?trackingCode=rss

검색 랭킹 시스템의 지속적인 개선을 위한 A/B 테스트 안내