# 검색어 자동완성 시스템

### 요구 사항

- 빠른 응답 속도 : 100ms 이하

- 연관성 

- 정렬 :  인기도 같은 순위 모델에 따라 정렬

- 규모 확장성, 고가용성

### 규모 추청

**Given**

- DAU = 10,000,000명

- 사용자당 일일 검색량 = 10 검색

- 질의

    - 검색 한 번 당 평균 데이터량 = 20B

    - 문자 인코딩 방식 = ASCII(1문자 = 1B)

    - 한 단어 = 5글자, 한 번 검색 = 4단어 = 20바이트

- 글자 입력마다 요청 전송 = 검색당 20회 질의

- 질의 중 20%는 신규 검색어

**Derived**

- 초당 질의수(QPS) = 10,000,000명 x 10 검색 x 20 글자 / 1 하루
-                             = 2 \times 10^{9} \div (24 \times 3600) \approx 초당 24,000 질의

- 최대 QPS = QPS x 2 = 48,000

- 신규 검색 바이트 = 24,000 QPS x 20% = 4.8KB/sec \approx 0.4GB/day

## 개략적인 설계안

- 데이터 수집 서비스 : 사용자의 입력을 수집해 빈도 테이블을 갱신한다.

- 질의 서비스 : 빈도 테이블을 살펴 자동완성 검색어를 반환한다.

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

## 상세 설계

### 트라이 자료구조

RDBMS 대신 trie(prefix tree)를 사용하여 검색 속도를 향상시킬 것이다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134422_V2mZMZyVjIfNyf8uku?q=80&s=1280x180&t=outside&f=webp)

**정의**

- p : 접두어의 길이 (즉, tree의 depth)

- n : 노드 개수

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

**자동완성 검색어 추출**

- 해당 접두어로 트리를 따라간다. O(p)

- 하위 트리를 탐색해 유효 노드(검색 문자열)를 찾는다. O(c)

- 유효 노드를 정렬해 인기 있는 검색어 k개를 찾는다. O(c \cdot \log{c})

**한계 극복**

k개의 결과를 얻기 위해 트리 전체를 탐색해야 할 수도 있기 때문에

- 접두어의 최대 길이를 제한하고

- 인기 검색어를 캐싱한다.

    - 적절한 노드에 하위 트리의 인기 검색어를 캐싱할 수 있다.

    - 공간이 많이 필요하지만 응답속도는 매우 빠르다.

### 데이터 수집 서비스

질의마다 매번 트라이를 갱신하기에는 비용이 많이 든다. 이 방법보다는 질의를 로그로 남기고 로그를 주기적으로 분석해 트라이를 갱신하는 방법이 효과적이다. 

- **데이터 분석 서비스 로그** : 질의마다 (질의, 시간) 데이터를 로그로 저장한다.

- **로그 취합 서버** : 로그를 주기적으로 취합한다. 10분에서 일주일까지 비즈니스에 따라 상이하다.

- **취합 데이터** : 로그를 일주일마다 취합해 (질의, 주차, 빈도) 테이블을 만든다. 

- **트라이 캐시** : 분단 캐시 시스템으로 매주 trie DB의 스냅샷을 떠 갱신한다.

- **트라이 데이터베이스 **

    - Document : MongoDB 같이 트라이를 직렬화해 저장

    - Key-Value : Redis 같이 해시 테이블 형태로 변환해 저장

### 질의 최적화 방안

- **AJAX req** : 페이지를 새로고침하고 필요한 데이터만 벡엔드에서 가져온다.

- 브라우저 캐싱 : 자동완성 검색어 제안은 실시간으로 바뀌지 않기 때문에 브라우저에 캐싱한다.

    - `cache-control: private, max-age=3600`

    - **private** : 공용 캐시에 저장해서는 안된다.

    - **max-age** : 최대 저장 시간, 단위는 초이다.

- **데이터 샘플링** : N 개의 요청 중 1개만 로깅해 전체 용량을 줄인다.

### 트라이 연산

**트라이 갱신**

- 매주 한 번 갱신, 새로운 트라이를 만들어 기존의 것을 대체한다.

- 노드를 개별적으로 갱신, 느리다.

**검색어 삭제**

- 필터 레이어를 둔다.

**저장소 규모 확장**

- 샤딩할 수 있다. (a~m과 j~r)은 다른 서버에 저장

For the site tree, see the [root Markdown](https://slashpage.com/kaonmir.md).