System Design Interview - 검색어 자동완성 시스템

들어가며

많은 포털 사이트, 웹 사이트 검색창에는 단어를 입력하면 입력중인 글자에 맞는 추천 검색어들이 표시된다. 이러한 기능을 자동완성 이라고 한다.

이 글은 특정 입력에 대한 검색어 자동 완성 기능을 다룬다.

1. 문제 이해 및 설계 범위

• 자동완될 검색어는 첫 부분으로 한정한다.
• 5개의 자동완성 검색어가 표시되어야 한다.
• 인기 순위를 기준으로 5개의 검색어를 표시한다.
• 맞춤법 검사나 자동수정은 지원하지 않는다
• 질의어는 영어지만, 다국어 지원을 생각하면 좋다.
• 질의는 영어 소문자로 구성된다.
• DAU는 천만명 기준이다.

요구사항 정리

1. 빠른 응답 속도 : 사용자가 검색어를 입력할 때마다 자동완성 검색어도 표시되어야 한다. (100ms 이내)
2. 연관성 : 사용자가 입력한 단어와 연관되어야 한다.
3. 정렬 : 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.
4. 규모 확장성 : 시스템은 많은 트래픽을 감당할 수 있도록 확장 가능해야 한다.
5. 고가용성 : 시스템의 문제가 생겨도 가용할 수 있어야 한다.

개략적 규모 추정

• DAU는 천 만명으로 가정
• 평균적으로 한 사용자는 매일 10건의 검색을 수행한다고 가정
• 질의할 때마다 평균적으로 20바이트의 데이터를 입력한다고 가정
  • ASCII를 사용한다고 가정하면, 1 문자 = 1 byte
• 평균적으로 1회 검색당 20건의 요청이 백엔드로 전달된다고 가정
• 대략 초당 24,000건의 QPS가 발생할 것이고 최대 QPS는 48,000건이 될 것이다.
  • 천만 사용자 x 10질의 / 일 x 20자 / 24시간 / 3600초
• 질의 가운데 20%는 신규 검색어라고 가정하면
  • 천만 사용자 x 10질의 / 일 x 20자 x 20%로 매일 0.4GB 의 신규 데이터가 시스템에 추가된다

2. 개략적 설계안

데이터 수집 서비스, 질의 서비스 두 부분으로 나뉜다.

데이터 수집 서비스

사용자가 입력한 질의를 실시간으로 수집하는 시스템이다.

질의문과 사용빈도를 저장하는 빈도 테이블을 두었다고 가정한다면, 사용자가 twitch, twitter, twitter, twillo 순서를 검색하면 아래와 같이 빈도 테이블이 바뀌어진다.

질의 서비스

주어진 질의에 k개의 인기 검색어를 정렬해 내놓는 서비스다.

질의서비스는 아래 표와 같이 query, frequency 필드를 가지고 있다.

• query : 질의문을 저장하는 필드
• frequency : 질의문이 사용된 빈도를 저장하는 필드

이 상태에서 사용자가 tw 를 입력한다면, 다음 SQL를 통해 twitter, twitch, twilight, twin peak, twitch prime 순으로 표시될 것이다.

가장 많이 사용된 5개 검색어는 아래의 SQL 질의문을 사용해 계산할 수 있다.

SELECT * FROM frequency_table
	WHERE query Like `prefix%`
		ORDER BY frequency DESC
			LIMIT 5;

데이터 양이 적을 때는 괜찮지만, 데이터가 아주 많아진다면 데이터베이스의 병목 현상이 발생할 수 있다.

3. 상세 설계

트라이 자료구조, 데이터 수집 서비스, 질의 서비스, 트라이 연산, 저장소 규모 확장을 통해 최적화 설계를 해보자.

트라이 자료구조

문자열들을 간략하게 저장할 수 있는 자료구조다. 문자열을 꺼내는 연산에 최적화되어 있다.

특징

• 트라이는 트리형태의 자료구조
• 루트 노드는 빈 문자열
• 각 노드는 문자 하나를 저장하며, 26개의 자식노드를 가질 수 있다.
• 각 트리 노드는 하나의 단어 또는 prefix string 을 나타낸다.

아래는 tree, try, true, toy, wish, win 이 저장된 트라이다.

이용 빈도에 따라 정렬된 값을 반환하기 위해서 노드에 빈도 정보를 같이 저장한다.

해당 트라이로 검색어 자동완성을 어떻게 구현할 수 있을까?

p : prefix의 길이 n : 트라이 노드 개수 c : 주어진 노드의 자식 개수

이 정보를 가지고 be 를 입력했을 때 자동완성의 시간복잡도와 알고리즘을 알아보자.

가장 많이 사용된 질의어 k 개는 다음과 같이 찾을 수 있다. (k = 3이라 가정)

• 해당 접두어를 표현하는 노드를 찾는다. O(p)

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

  • 유효 노드 : 사용자가 검색한 문자열을 구성하는 노드 ex) [bee: 20], [beer: 10], [best: 35], [bet: 29]

• 상위 k개 검색어를 정렬한다. O(clogc) (최소힙 사용시 O(clogk) 로 더 효과적) 결과 : [best:35], [bet:29], [bee: 20]

따라서 총 시간 복잡도는 O(p) + O(n) + O(clogc) 가 된다.

하지만 최악의 경우 전체 트라이를 다 검색해야 하는 일이 생길 수 있고, 여기서 더 최적화 할 수 있다.

1. 접두어 최대 길이 제한

p값을 작은 정숫값으로 제한한다면 O(p) 에서 O(작은 상숫값) = O(1) 이 될 것이다.

2. 노드에 인기 검색어 캐시

아래 그림과 같이 각 노드에 인기 질의어를 캐시 하면 공간 복잡도는 증가하겠지만 시간 복잡도를 O(1) 로 획기적으로 낮출 수 있다.

데이터 수집 서비스

지금까지의 설계안은 사용자가 검색창에 검색어를 입력할 때마다 실시간으로 데이터를 수정하고 있다. 이 방법에는 두 가지 문제가 있다.

문제 1. 매일 수천만 건의 질의가 입력되면 수천 만 번의 트라이 갱신이 발생할텐데, 서비스가 심각하게 느려질 것이다.

문제 2. 인기 검색어는 자주 바뀌지 않을 것이기 때문에 트라이 갱신을 자주 할 필요가 없을 것이다.

위 그림과 같이 개선안을 만들 수 있다. 차례로 살펴보자.

데이터 분석 서비스 로그 (Analytics Logs)

검색창에 입력된 질의에 관한 원본 데이터가 보관된다. 데이터가 추가만 되고 수정은 없으며, 로그 데이터에는 인덱스를 걸지 않는다.

로그 취합 서버 (Aggregators)

데이터 분석 서비스로부터 나오는 방대한 양의, 제각각인 데이터 형식 데이터를 잘 취합(aggregation)하여 해당 시스템이 쉽게 소비할 수 있도록 한다.

대부분의 경우 일주일에 한 번 정도로 로그를 취합하는데 트위터와 실시간 애플리케이션의 경우 취합 주기를 짧게 설정한다.

취합된 데이터 (Aggregated Data)

• time : 해당 주가 시작된 날짜 (취합)
• frequency : 해당 질의가 해당 주에 사용된 횟수의 합 (빈도)

작업 서버 (Workers)

주기적으로 비동기적 작업(job)을 실행하는 서버 집합이다.

작업서버는 트라이 자료구조 생성 및 트라이 데이터베이스에 저장하는 역할을 담당한다.

트라이 캐시

분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높인다.

매주 데이터베이스 스냅샷을 떠서 갱신한다.

트라이 데이터베이스

지속성 저장소다.

트라이 데이터베이스로 사용할 수 있는 선택지 2개

1. 문서 저장소

   • 새 트라이를 매주 만들 것이므로 주기적으로 트라이를 직렬화하여 데이터베이스에 저장한다.
   • MongoDB 같은 문서 저장소를 활용 가능하다.

2. 키-값 저장소

   • 해시 테이블 형태로 변환 가능하다.
   • 트라이에 보관된 모든 prefix를 해시 테이블 키로 변환하여 저장한다.
   • 각 트라이 노드에 보관된 모든 데이터를 해시 테이블 값으로 변환한다. (인기 검색어)

질의 서비스

방금 전 설계안의 비효율성을 개선한 새 설계안은 아래와 같다.

동작 과정

1. 검색 질의가 로드 밸런서로 전송된다.

2. 로드밸런서는 해당 질의를 API 서버로 전달한다.

3. API 서버는 트라이 캐시에서 데이터를 가져와 자동완성 검색어 제안 응답을 구성한다.

4. 데이터가 트라이 캐시에 없는 경우 트라이 데이터베이스에서 가져와 캐시에 채운다. (캐시 미스는 캐시 서버 메모리 부족 or 캐시 서버 장애가 때문에도 발생함)

질의 서비스는 매우 빨라야 하므로 다음과 같은 최적화 방안을 제안할 수 있다.

• AJAX 요청 : 요청을 보내고 받기 위해 페이지를 새로고침 할 필요 없다. (실시간 반영)

• 브라우저 캐싱 : 대부분의 애플리케이션의 경우 자동완성 검색어 제안 결과는 짧은 시간 안에 자주 바뀌지 않으므로 브라우저 캐시에 넣어두면 후속 질의어 결과는 해당 캐시에서 바로 가져갈 수 있다.
  • HTTP의 Cache-Control 헤더를 조절하여 자주 변하지 않는 데이터를 브라우저 캐시에 저장하면, 사용자에게 빠른 응답을 제공하고 서버 부하를 줄일 수 있다.
• 데이터 샘플링 : 모든 질의 결과를 로깅하도록 하면 CPU 자원과 저장공간을 많이 소진하므로, N개 요청 가운데 1개만 로깅한다.

트라이 연산

트라이 생성

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

트라이 갱신

• 매주 한 번 갱신하는 방법 (추천)
  • 새로운 트라이를 만든 다음 기존 트라이를 대체한다.
• 트라이의 각 노드를 개별적으로 갱신하는 방법 (트라이가 작을때 고려해볼만 하다)
  • 성능이 좋지 않다. (노드를 갱신할 때 모든 상위 노드도 갱신해야 하는데, 사우이 노드에도 인기 검색어같은 캐시 데이터가 보관되기 때문)

검색어 삭제

여러 위험한 질의어를 자동완성 결과에서 제거해야 한다. (욕설, 혐오성, 폭력성 등 관련)

트라이 캐시 앞에 필터 계층(Filter Layer) 을 두고 부적절한 질의어를 거를 수 있다.

데이터베이스에서 해당 검색어 물리적으로 삭제하는건 다음 업데이트 사이클에 비동기적으로 진행한다.

저장소 규모 확장

구현 조건은 영어만 지원하면 되므로 간단하게는 첫 글자 기준으로 샤딩하는 방법이 있다.

• Case 1) 검색어 보관에 두 대의 서버가 필요한 경우 a ~ m 으로 시작하는 검색어는 첫 번째 서버, 나머지 n ~ z 는 두 번째 서버에 저장한다.

• Case 2) 검색어 보관에 세 대의 서버가 필요한 경우 a ~ i 까지는 첫 번째 서버에, j ~ r까지는 두 번째 서버에, 나머지 s ~ z 는 세 번째 서버에 저장한다.

이 방식으로는 사용 가능한 서버 최대 26개다. 그 이상으로 서버수 늘리려면 샤딩을 계층적으로 해야 한다.

예시)

• Case 3) a 로 시작하는 검색어를 네 대의 서버에 나눠서 보관하는 경우 aa ~ ag, ah ~ an, ao ~ au, 나머지 av ~ az 로 4개의 서버에 나누어 보관하면 된다.

그럴싸해 보이지만 이는 데이터를 각 서버에 균등하게 배분할 수 없다.

a 로 시작하는 단어가 z 로 시작하는 단어보다 많다는 것을 생각해보면 알 수 있다. 각 알파벳으로 시작하는 단어의 개수가 비슷하지 않기 때문이다.

검색어 대응 샤드 관리자(shard map manager)

어떤 검색어가 어느 저장소 서버에 저장되는지에 대한 정보를 관리한다.

검색어 대응 샤드 관리자를 사용하면 이를 개선할 수 있다.

( s 로 시작하는 검색어 양 ) = ( w, x, y, z 로 시작하는 검색어 양 ) 이라면, s 에 대한 샤드 하나, w ~ z에 대한 샤드 하나 이렇게 두개만 두어도 충분하다.

추가 확장 개선점

• 다국어 지원 : 유니코드로 저장
• 국가별 인기 검색어 지원 : 국가별로 다른 트라이 사용하고 이를 CDN에 저장하여 응답속도 향상

실시간 검색어 자동완성 시스템 고급 구현

책에서 추가로 소개하는 실시간 검색 추이 반영을 위한 핵심 아이디어는 다음과 같다.

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

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

데이터가 스트림 형태로 올 수 있기 때문에 스트림 프로세싱에 적합한 시스템을 고려한다. (아파치 하둡 맵리듀스, 아파치 스파크 스트리밍, 아파치 스톰, 아파치 카프카 등이 이 그런 부류의 시스템이다.)

이 중 핵심은 데이터 스트림 처리 시스템이다.

Apache Kafka를 이용한 실시간 데이터 처리

Apache Kafka 는 실시간으로 기록 스트림을 게시, 구독, 저장 및 처리할 수 있는 분산형 데이터 스트리밍 플랫폼이다. 하루에 1조 4천억 건의 메시지를 처리하기 위해 LinkedIn이 개발한 내부 시스템으로 시작했다.

카프카는 대규모 실시간 데이터를 안정적으로 처리할 수 있다. 검색어 자동완성에서는 사용자가 입력하는 검색어를 실시간으로 수집하고 분석해야 하는데, 카프카가 이 용도에 딱 맞다.

Spark Streaming으로 실시간 분석

스파크 스트리밍은 데이터 스트림을 시간 단위로 잘게 쪼개어 마이크로 배치 형태로 처리하기 때문에 배치 처리와 유사한 방식이지만, 실시간으로 데이터를 처리할 수 있다는 점에서 차이가 있다.

결국 Kafka로 데이터를 받고 → Spark로 실시간 처리 → 다시 Kafka로 결과 전송하는 파이프라인을 만드는 것이다.

LinkedIn의 신경망 기반 접근법

LinkedIn에서는 단순한 키워드 매칭을 넘어, 사용자의 검색 의도를 파악하는 고도화된 기술을 사용한다. LinkedIn에서 발표된 ‘Efficient Neural Query Auto Completion’ 논문을 기반으로 FST(Finite State Transducer)와 MCG(Maximum Context Generation) 라는 두 가지 핵심 개념을 적용했다. 이 방식은 단순한 패턴 매칭을 넘어, 검색어의 문맥을 이해하여 더 정확한 추천을 제공한다.

FST와 MCG: 검색어 자동완성 원리

사용자가 “cheapest flights from seattle to” 라는 검색어를 입력했다고 가정해보자

1. FST(Finite State Transducer): 후보 단어 생성

FST는 과거의 방대한 검색 기록을 분석하여 구축된 결정론적 유한 오토마타이다. FST는 ‘seattle to’ 뒤에 자주 등장했던 패턴, 예를 들어 ‘new york’, ‘london’, ‘san francisco’와 같은 도시 이름을 후보로 생성하는 역할을 한다.

하지만 FST는 순수한 패턴 분석에 의존하기 때문에 검색어의 의미적 맥락을 완벽하게 이해하지는 못한다. 따라서 FST가 생성하는 후보 목록에는 ‘pizza’와 같이 문맥상 관련성이 떨어지는 단어도 포함될 수 있다!

2. MCG(Maximum Context Generation): 최적의 순위 결정

이때 MCG가 등장한다. MCG는 신경망(Neural Network) 기반의 모델로, FST가 제시한 후보 단어들 중에서 전체 검색어의 맥락(context) 을 고려해 가장 적합한 단어의 순위를 매기는 역할을 한다.

MCG는 ‘cheapest flights’라는 단어가 ‘여행’과 관련된 맥락임을 이해하고, ‘seattle to’ 뒤에 오는 단어가 ‘여행지’일 확률이 높다고 판단한다. 만약 FST가 ‘new york’, ‘pizza’와 같은 단어를 후보로 제시했다면, MCG는 ‘pizza’가 여행 맥락과 무관하다고 판단해 순위를 낮추고, ‘new york’과 같은 여행지 관련 단어를 상위에 배치하여 사용자에게 보여준다.

이처럼 FST가 후보 단어를 생성하고, MCG가 그 단어들의 순위를 최적화하는 이원화된 접근법을 통해, 단순한 트라이 구조보다 훨씬 똑똑하게 예측하는 것이다.

정확한 데이터 처리를 위한 Exactly-Once

실시간 시스템에서 가장 중요한 건 데이터 중복이나 손실 없이 정확히 한 번만 처리하는 것이다.

실시간 스트리밍 데이터 처리에서 한 번만 정확하게(exactly-once) 처리하는 것은 중복 데이터 처리와 데이터 손실을 방지하고 분석 결과가 왜곡되지 않도록 하는 데 중요하다. 이는 카프카에서 간단히 설정할 수 있음을 저번 글에서 소개했다.

마치며

검색창에 단 한 글자를 입력하는 단순한 행위 뒤에는, 빠른 응답 속도, 높은 가용성, 그리고 정확한 추천을 보장하기 위한 복잡하고 정교한 시스템 설계가 숨겨져 있었다.

트라이 자료구조부터 실시간 스트리밍 처리, 신경망 기반 예측까지 우리가 당연하게 여기는 검색어 자동완성은 대규모 시스템 설계의 핵심 개념들이 모두 집약된 놀라운 엔지니어링의 결과물이다.

---

References

• 웹 서비스 캐시 똑똑하게 다루기
• Apache-Kafka란?
• Google 자동 완성 예상 검색어의 작동 방식
• Efficient Neural Query Auto Completion