자동완성 기능
- 서비스에서 사용자가 입력 중인 단어 낱말의 나머지 부분을 예측해서 제안하는 기능
- 영어 동의어로는 autocomplete, typeahead, instant search
- 과거에는 단순하게 찾고자 하는 검색어의 나머지 부분을 제안하는 수준 (LIKE 검색)
- 최근에는 사용자의 니즈를 충족시키기 위해 부가정보를 넣어서 고도화하는 추세
자동완성 기능을 구현하기 위해 필요한 조건
1. 자동완성 후보 키워드를 위한 데이터 셋
- 사용자의 최근 검색어 목록
- 인기 키워드 후보군
2. 제한된 개수 및 길이
- 키워드의 길이가 너무 길지 않아야 함
- 제안하는 키워드의 개수가 반드시 많을 필요 없음
3. 요청에 대한 빠른 응답
- 응답할 데이터 후보군을 캐싱하여 100ms 이내로 응답
4. 색인 시 고려사항
- 자소분리 기능
- 색인량이 상대적으로 적고 변경이 많지 않은 경우 유리
5. 기능적 요구사항
- 오타를 정타로 추천할 수 있는 기능
- 키워드의 중간에서 매칭되거나, 키워드가 아예 매칭이 되지 않는 경우도 대응이 가능해야 할 수도 있음
자동완성 품질 평가
- 품질 평가는 어떤 지표에 중점을 두느냐에 따라 나뉨
- 순위의 품질에 중점을 둔 지표
- 사용자의 노력이 얼마나 절약되었는지에 중점을 둔 지표
1. 순위의 품질에 중점을 둔 지표
- 사용자 마지막 입력 시 클릭한 아이템의 순위 기반
2. 사용자의 노력이 얼마나 절약되었는지에 중점을 둔 지표
- MKS(Minimum Keystroke Length)
- e-Saved(Expected Saved)
- p-Saved(Perceived Saved)
2.1 MKS
- 사용자가 대상 쿼리를 선택할 때까지 수행해야 할 작업 수
- 이때 문자 입력과 대상 쿼리의 위치에 도달하기 위해 누르는 수고를 모두 포함
- k번째 키 입력에서 idx번째 위치에 있는 쿼리를 선택한 경우 (k + idx)로 계산
- ex) 사용자가 fa 입력했을 때 첫 번째로 노출된 facebook 클릭했다면 입력한 수(2) + 첫 번째 노출된 키워드 클릭(1) = 3
2.2 e-Saved
- 쿼리 자동 완성 기능이 사용자의 시간을 얼마나 절약해 주는지 측정하는 척도
- 사용자가 절약한 실제 문자 수를 측정하는 객관적인 지표
- 사용자가 완성되지 않은 쿼리를 입력할 때, 자동 완성 제안이 제공되어 입력을 완료해며 해당 제안을 통해 절약된 문자 수를 계산
- ex) 사용자가 "Elastics"까지 입력했을 때 "Elasticsearch"라는 제안이 나타난다면, "earch"라는 5개의 문자가 절약되며 이런 식으로 절약된 문자 수를 전체 문자 수와 비교하여 백분율로 표현할 수 있음
- (1 - 8/13) * 100 = 약 38.46%
2.3 p-Saved
- 키 입력 측면에서 절약된 작업량을 측정하기 위한 척도
- 사용자 경험을 더 직접적으로 반영하는 지표로 사용자가 느끼는 효율성을 측정
- p-Saved는 주관적인 사용자 피드백과 사용 패턴에 기반
- 사용자가 쿼리를 제출할 때까지 입력을 건너뛸 수 있는 예상 문자 비율을 계산
- 사용자가 긴 쿼리를 사용할 때 자동완성 검색의 이점이 드러나기 때문에 p-Saved 지표로 평가하는 것이 의미 있음
자동완성을 위한 로깅
- 일반적으로 검색 쿼리 로그는 사용자 ID, timestamp, 제출된 쿼리 및 관련 검색 결과를 포함하지만 자동완성에 필요한 검색창에 입력한 순차적인 키 입력인 접두어와 그에 따른 자동완성 제안이 포함되지 않은 경우가 많음
- 실제 사용자의 행동을 잘 분석하고 이해하기 위해서는 전체 자동완성 프로세스에서 각 키 입력과 관련 시스템 응답에서 사용자와 자동완성 엔진 간의 상호작용을 기록하는 고도화된 자동완성 로그를 도입하여 분석할 필요가 있음
- 제출된 각 쿼리에 대해 기존 검색 쿼리 로그에는 하나의 레코드만 존재하지만
- 자동완성 로그에서는 제출된 각 쿼리가 사용자가 검색창에 입력한 첫 번째 키 입력부터 최종 제출된 쿼리까지로 정의되는 자동완성 세션과 연결됨
- 각 자동완성 세션에 기록된 정보에는 사용자가 입력한 각 키 입력, 키 입력의 timestamp, 접두사(prefix)에 해당하는 상위 n개 추천 쿼리, 사용자 ID, 최종 클릭한 쿼리 포함
Elasticsearch가 제공하는 자동완성 API 없이 자동완성을 구현한다면
- 충분히 가능하지만 단점들이 존재하므로 Elasticsearch가 제공하는 자동완성 API를 사용하는 것을 권장
1. Trie 자료구조
Elasticsearch 없이 자동완성을 구현한다면 Trie 자료구조를 사용할 수 있습니다.
- 효과적으로 탐색이 가능하며 트리 기반으로 루트 노드부터 자식 노드들을 따라가면서 접두사 기반으로 매칭되는 결과를 찾을 수 있음
- 단어의 길이가 n일 때 단어 삽입의 시간 복잡도는 O(n)
- 검색할 접두사의 길이를 m이라고 할 때, 검색의 시간 복잡도는 O(m)이지만 접두사에 해당하는 Trie의 노드까지 이동한 이후에는 해당 노드에서부터 모든 단어를 탐색하므로 단어의 개수에 비례하지 않음
장점
- 문자열을 하나씩 전부 비교하는 것보다 효율적이고 빠름
단점
- prefix 기반이기 때문에 공간복잡도가 문제 될 수 있음
- O(m)인 시간복잡도를 달성하기 위해 다음 문자를 가리키는 노드가 필요
- ex) 알파벳에 대해 트라이를 형성할 경우 a~z인 총 26개의 포인터 배열을 지니고 있어야 함
2. Map 자료구조
사용자의 입력을 key, 그에 대한 응답값을 value로 저장하는 Map 자료구조를 사용할 수 있습니다.
장점
- Hash 충돌만 없다면 자동완성을 위한 검색 속도가 O(1)에 가까울 수 있음
단점
- 정확한 일치 검색에는 효과적일 수 있지만 중간에서 일치하는 부분 일치 검색에는 적합하지 않음
- 저장된 키의 개수에 따라 메모리 사용량이 증가
- 동일한 prefix를 가진 다른 값들을 중복해서 저장해야 하는데 key-value 쌍인 Map 자료구조는 하나의 키에 대응하는 값만 저장할 수 있으므로 부분 일치 검색을 효율적으로 처리하기 어려움
- ex) "trie"와 "tripod"이라는 두 단어가 있을 때, "tri"이라는 접두사로 시작하는 모든 단어를 검색하기 위해서는 "tri" 키에 대응하는 값을 찾아야 함
3. Redis
in-memory DB를 사용해서 자동완성을 구현하는 것도 충분히 가능합니다.
장점
- 빠르게 응답을 받을 수 있음
단점
- 자동완성 API에 조건에 따른 다양한 필터 혹은 정렬 기능이 들어가게 되면 고려사항이 많아짐
Elasticsearch가 제공하는 자동완성 API
- ngram
- edge_ngram
- search_as_you_type
- prefix_query
- completion_suggester
1. ngram
- 단어의 일부만 가지고 검색할 수 있게 나눈 단어의 부위로 자동완성의 특성상 일부의 단어를 가지고 응답을 반환해야 하기 때문에 적합한 자료구조
- 1글자 단위로 나누면 unigram, 2글자 단위로 나누면 bigram, 3글자 단위로 나누면 trigram
- Elasticsearch에서는 ngram을 지원하기 위해 tokenizer 지원 (ngram)
- ngram의 글자 단위가 많아지면 색인해야 하는 글자 수가 많아지기 때문에 주의 필요
1.1 ngram 옵션 설명
- min_gram: 최소값이며 default 값은 1 즉 unigram
- max_gram: 최대값이며 default 값은 2 즉 bigram
- token_chars: 토큰에 포함되어야 하는 문자 타입을 정의하며 default로는 모든 타입 수용
- letter: 문자
- digit: 숫자
- whitespace: 빈칸이나 개행문자
- punctuation: 마침표(.), 쉼표(,) 등
- symbol: $와 같은 특수 기호
1.2 ngram 인덱스 생성 예시
부연 설명
- Elasticsearch에서 제공하는 ngram 토크나이저가 아닌 커스텀 토크나이저인 ngram_tokenizer 정의
- "type": 토크나이저 유형으로 ngram 지정
- "min_gram": 생성할 ngram의 최소 길이를 지정하며 여기서는 bigram
- "max_gram": 생성할 ngram의 최대 길이를 지정하며 여기서는 trigram
- "token_chars": 토큰을 생성할 때 고려할 문자 유형을 지정하며 여기서는 문자와 숫자만 포함
1.3 ngram 분석
부연 설명
- token_chars를 letter와 digit으로 지정했으므로 공백 문자와 특수 기호인 ! 무시
- min_gram을 bigram으로 설정하였으므로 2는 숫자임에도 unigram이므로 결과에 나타나지 않음
2. edge_ngram
- ngram을 사용하더라도 대부분은 앞에서부터 검색을 하는 경우가 많음
- 텀 앞쪽의 ngram 만 저장하기 위해서는 edge_ngram 토크나이저를 사용
- 보통 자동완성에서도 앞에서부터 매칭된 결과를 보여주기 때문에 ngram보다 색인되는 토큰이 줄어듦
2.1 edge_ngram 옵션 설명
- ngram 옵션과 동일하므로 생략
2.2 edge_ngram 인덱스 생성 예시
부연 설명
- 1.2와 달라진 점은 tokenizer type을 ngram에서 edge_ngram으로 대체했다는 점
2.3 edge_ngram 분석
부연 설명
- 맨 앞을 기준으로 ngram을 진행하므로 색인되는 토큰이 현저히 줄어든 것을 확인할 수 있음
3. search-as-you-type
- 자동완성을 위한 데이터 타입 제공
- 전체 색인된 텍스트와 부분적으로 일치하는 쿼리를 매칭시키기 위한 효율적인 서브필드 제공
- prefix 일치와 중간일치 제공
3.1 search-as-you-type 옵션 설명
- my_field: analyzer 지원하며, 설정 안 할 경우 기본 standard analyzer로 동작
- my_field._2gram: 크기 2의 shingle token filter로 wrapping
- my_field._3gram: 크기 3의 shingle token filter로 wrapping
- my_field._index_prefix: my_field._3gram + edge ngram token filter로 wrapping
shingle token filter
- ngram과 edge_ngram은 둘 다 하나의 단어로부터 토큰을 확장하는 토큰 필터
- 문자가 아니라 단어 단위로 구성된 묶음을 shingle이라고 함
3.2 search-as-you-type 색인
부연 설명
"서울시 강남구 청담동" 기준으로 설명
- my_field는 standard analyzer로 인해 ["서울시", "강남구", "청담동"]으로 색인
- my_field._2gram은 ["서울시 강남구", "강남구 청담동"]으로 색인
- my_field._3gram은 ["서울시 강남구 청담동"]으로 색인
- my_field._index_prefix은 ["서", "서울", "서울시", "서울시 강", "서울시 강남", "서울시 강남구", "서울시 강남구 청", "서울시 강남구 청담", "서울시 강남구 청담동"]으로 색인
3.3 search-as-you-type 검색
- multi_match와 bool_prefix를 같이 사용하는 것이 효과적
- 실제로 bool_prefix 없이 서로 검색하면 hits가 빈 배열로 나옴
- multi_match의 경우 strict 하지 않기 때문에 "서울시 강"으로 검색해도 둘 다 나옴
- 만약 엄격한 검색 결과를 원한다면 match_phrase_prefix 사용하는 것을 권장
3.3.1 multi_match + bool_prefix
3.3.2 match_phrase_prefix
4. prefix query
- 특정 필드에 요청한 prefix를 포함한 문서를 응답해 주는 쿼리
4.1 prefix query 옵션 설명
색인 시 index_prefixes 하위에 다음 파라미터 설정 가능
- min_chars: 0보다 큰 값으로 default 값은 2
- max_chars: 20보다 작은 값으로 default 값은 5
4.2 prefix query 색인
부연 설명
- 쿼리의 응답 성능을 높이기 위해 색인 시 파라미터를 추가하면 효과적
- 앞서 설명한 min_chars, max_chars 참고
4.3 prefix query 고려사항
- strict 한 조건이 맞아야 하기 때문에 유연성이 떨어질 수 있음
- fuzzy 검색을 지원하지 않기 때문에 오타 처리 불가
- 텍스트가 많은 경우 리소스 소모량이 높을 수 있음
5. Suggester
- 자동완성은 근본적으로 사용자가 입력하는 동안에 응답이 바로 이루어져야 하기 때문에 빠르게 응답이 되어야 함
- 일반적인 검색 API의 경우 많은 term들과 해당 term이 얼마나 존재하는지를 체크해야 하기 때문에 성능상 제약 존재
- suggester API는 색인이 된 대상을 FST(유한상태 변환기)라는 데이터 구조로 만들어 in-memory에 올려 일반 검색 API보다 응답이 빠르며 in-memory에 올리기 때문에 변경이 적은 것이 좋음
- 단, suggester api는 중간 키워드로는 검색이 안되기 때문에 검색을 원하는 대상을 배열로 지정하는 것이 필요
- ex) ["서울시 강남구 청담동", "강남구", "강남구 청담동", "청담동"]
6. Completion Suggester
- 응답 속도가 빨라야 하는 경우 사용하기 좋은 자동완성 API
- 색인 데이터 구조를 빠르게 조회하기 위해 in-memory에 올려놓음
- 키워드에 대한 가중치(weight)를 부여할 수 있음
6.1 Completion Suggester 옵션 설명
- analyzer: 색인 시 분석기
- search_analyzer: 검색 시 분석기
- preserve_separators: 띄어쓰기를 유지할지 여부를 나타내며 default 값은 true
- max_input_length: 색인하는 데이터가 증가되는 것을 막기 위한 최대 input의 길이를 제한하며 default 값은 50
6.2 Completion Suggester 색인
부연 설명
- 보통 구체적인 지역명을 검색하므로 [동, 구, 도] 순으로 가중치 부여
6.3 Completion Suggester 검색
부연 설명
- _source: 소스에서 보고 싶은 필드만 필터링
- size: 반환 개수
- _source와 size 옵션을 적절히 설정하여 최대한 빠르게 응답받는 것이 중요
- 적을수록 네트워크 트래픽이 적어지고 응답 속도가 빨라짐
6.4 Completion Suggester 오타 처리
- fuzzy 검색을 사용하여 오타에 대해서 고려한 결과 반환
- fuzziness 옵션을 통해 Edit Distance 설정
6.5 Completion Suggester Context 반영
- 자동완성 내 특정 기준에 따라 boosting 하거나 필터링하는 조건을 넣는 방법
- ex) 영화 목록을 자동완성에 넣을 때, 특정 장르의 영화를 부스팅
- ex) 음식점을 자동완성에 넣을 때 현재 gps 근처 음식점만 나오도록 함 (geo location 사용)
자동완성 시 클라이언트 고려사항
- 자동완성 기능은 일반 검색 대비 트래픽이 많기 때문에 클라이언트 단에서 추가적으로 고려할 사항들이 있음
- ex) "아이폰"이라는 검색어의 경우 일반적인 검색으로는 한 번의 검색이지만 자동완성 기능으로는 자소단위를 포함할 경우 최대 "ㅇ,ㅏ,ㅇ,ㅣ,ㅍ,ㅗ,ㄴ"으로 총 7번의 API 요청이 이루어질 수 있음
1. 쓰로틀링(throttling)
- 클라이언트의 요청을 제한하는 메커니즘
- API 요청의 빈도를 제한하여 서버에 과부하를 방지하는 기능
- 쓰로틀링은 일정한 시간 간격으로 API 요청을 제한하거나 일정한 요청량을 초과하는 경우에 대한 처리 수행 가능
2. 디바운싱(debouncing)
- 사용자의 입력을 처리하기 전 일정 시간 동안 대기하는 메커니즘
- 사용자가 연속해서 입력을 하는 경우 중복된 요청 방지 가능
- ex) 사용자가 검색어를 입력할 때마다 API 요청을 보내는 대신, 일정 시간 동안 사용자의 입력이 없을 때에만 API 요청을 보내는 방식
- onkeyup 이벤트 발생 이후 일정 시간 동안 onkeypress 이벤트가 발생하지 않을 경우 요청을 보내는 방식
3. 로컬 스토리지 사용
- 자동완성에서 일반적으로 많이 쓰이는 사용자의 최근 검색어의 경우 클라이언트 단에서 로컬 스토리지를 사용할 수 있음
- 로컬 스토리지를 사용하면 서버에 매번 요청을 보내지 않아도 되기 때문에 서버 부하를 줄일 수 있고 사용자 경험 향상도 도모할 수 있음
- 또한, 로컬 스토리지는 일반적으로 빠른 Read/Write 속도를 제공하기 때문에 검색어를 빠르게 로드하고 갱신할 수 있음
3.1 로컬 스토리지 사용 시 주의할 점
- 사용자 개인정보는 마스킹해서 저장
- 사용자의 검색 기록이 길어질 경우 용량을 초과할 수 있으므로 필요한 경우 검색 기록을 관리하고 정리하는 로직 추가 필요
- 로컬 스토리지는 사용자의 "로컬" 브라우저에 저장되기 때문에 다른 기기나 브라우저에는 동기화되지 않음
- 여러 기기에서 동기화되길 원한다면 서버에 최근 검색어를 저장하고 동기화하는 메커니즘 추가 필요
참고
- 패스트 캠퍼스 - 고성능 검색 엔진 구축으로 한 번에 끝내는 Elasticsearch
반응형
'Elastic Search' 카테고리의 다른 글
| [Elasticsearch] Fuzzy 쿼리 (0) | 2024.06.19 |
|---|---|
| [Elasticsearch] 스크립트 쿼리 (0) | 2024.06.13 |
| [Elasticsearch] 집계 (3) | 2024.06.09 |
| [Elasticsearch] 검색 (0) | 2024.06.07 |
| [Elasticsearch] 분석기(analyzer) (3) | 2024.06.07 |