개략적인 검색어 자동완성 시스템에 대한 이야기

가상 면접 사례로 배우는 대규모 시스템 설계 13장을 참고한 글입니다.

매일 사용하지만 설계해 본 적 없는 기능에 대히여

 

 

1) 범위 설정하기

• 검색 자동완성의 기준은 무엇인가? (가장 많이 이용된? 가장 최근에 검색된?)
• 몇 개의 자동완성 단어가 표시되어야 하는지?
• 다국어 지원이 가능한가?
• DAU는?
• 규모에 따른 QPS 계산하기(일간이용자*요청수*최대글자/일/24시간/3600초)

 

2) 설계안

데이터 수집 서비스

사용자가 입력한 질의를 실시간으로 수집하는 시스템이다. 데이터가 많은 애플리케이션에 실시간 시스템은 바람직하지 않지만 설계안을 만드는 출발점으론 괜찮다.

 

질의문과 사용빈도를 저장하는 빈도 테이블이 있다고 가정한다. 처음엔 테이블이 비어있지만 사용자가 검색하면 상태가 바뀌어 나간다.

 

 

질의 서비스

빈도테이블에서 빈도가 높은 순으로 자동완성 검색어가 표시되어야 한다. SQL로 표시하면

 

SELECT * FROM frequency_table 

WHERE query LIKE 'prefix%'

LIMIT N;

 

당연히 데이터가 많아지면 병목구간이 된다.

 

 

3) 최적화하기

트라이 자료구조

노드에 인기 검색어를 캐시해놔서 질의 시간 복잡도를 낮출 수 있다. 저장공간을 많이 잡아먹는 단점이 있지만 빠른 속도가 중요하다면 trade-off할만한 가치가 있음

 

데이터 수집 서비스

실시간으로 데이터를 수정하면 실용적이지 못하다. 트라이가 만들어지고 나면 인기 검색어는 그다지 자주 바뀌진 않을 것이다. 트라이는 자주 갱신할 필요가 없다.

 

데이터가 어디서 어떻게 이용되는지가 중요하다. X(구 트위터)처럼 실시간 서비스인지 구글처럼 검색인지. 그러나 용례가 다르더라도 구현법의 토대는 바뀌지 않는다.

 

 

 

보통 데이터 분석 서비스나 로깅 서비스를 통해 트라이를 만든다. 로그는 검색창에 입력된 질의에 관한 원본 데이터가 보관된다. 새로운 데이터가 추가될 뿐 수정은 이루어지지 않으며, 인덱스를 걸지 않는다.

 

로그는 양이 엄청나고 데이터 형식이 제각각인 경우가 많다. 따라서 데이터를 잘 취합하여 시스템이 쉽게 소비할 수 있도록 해야 한다. 데이터 취합 주기는 용례에 따라서 설정한다.

 

취합된 데이터를 가지고 작업 서버는 비동기적으로 트라이를 만들고 DB에 저장한다. 이떼 분산 캐시 시스템으로 트라이 데이터를 메모리에 유지하여 읽기 연산 성능을 높이는 구실을 한다.

 

트라이 데이터베이스로 어떤 선택지가 있을까? 대체적으로 NoSQL을 사용한다.

• document 형식
  • 새 트라이를 매번 만들 것이므로, 주기적으로 트라이를 직렬화하여 DB에 저장할 수 있다. 
• key-value 형식
  • 모든 트라이 노드의 값(접두어)을 해시테이블 키로 변환한다. 그리고 트라이 노드에 보관된 데이터를 해시테이블 값을 변환해 저장한다.

 

참고) 트라이 연산

생성 - 작업 서버가 담당. 로그나 DB에서 취합된 데이터 이용

 

갱신 - 노드를 개별적으로 갱신하는 방법, 데이터가 많으면 비효율적. 마지막 단어 노드까지 거쳐가면서 상위 노드에 기록된 빈도 수치 모두 갱신.

 

삭제 - 특정 이유로(혐오, 폭력, 성적) 질의어를 삭제해야 할 때 자동완성 결과에서 제거해야 한다. 서버와 트라이 캐시 사이에 필터 계층을 해결한다. 다음번 트라이 갱신 때 물리적으로 단어를 삭제한다.

 

참고) 추가적인 내용

다국어를 지원하려면 유니코드를 저장해야 한다. 유니코드는 "고금을 막론하고 세상에 존재하는 모든 문자 체계를 지원하는 표준 인코딩 시스템"이다.

 

국가별 인기 검색어 순위가 다르다면 국가별로 다른 트라이를 사용한다. 트라이 또한 CDN에 저장 가능하다.

 

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

 

영어 트라이일 때도 트라이의 크기는 방대해 하나의 데이터베이스에 저장하지 못할 수 있다. 이때 샤딩을 사용하는데, 첫 접두사를 샤드키로 사용하기도 한다. 하지만 x, y, z 같은 알파벳으로 시작하는 단어들은 상대적으로 적기 때문에, 비순차적으로 샤드에 저장하는 게 효율적이다. 이럴 땐 어느 샤드에 검색어가 존재하는지 확인하는 DB를 탐색한 후 샤드 DB에 접근할 수 있도록 하면 된다.