로그 모니터링 개발 기록 02. 검색엔진의 조회 구조 이해하기

2021년 11월부터 현재(24년 1월)까지 약 2년동안 와탭 로그 모니터링을 개발하면서 배우고 느꼈던 것들을 정리하려고 합니다. 전체적인 흐름을 어떻게 구조를 잡을까 고민해보다가 Lucene In Action에서 Lucene에 대해서 설명하고 있는 구조를 그대로 차용하겠습니다.

---

검색 엔진의 조회 구조

이전 글에서 Inverted Index와 SSTable의 구조에 대해서 설명었습니다. 이 두가지 자료구조에 대한 설명을 전제로 시작해보겠습니다.

검색 엔진에서 제공하는 검색 기능에는 크게 3가지 종류의 이론적이 모델이 있습니다.

1. 순수 불리언 모델
2. 벡터 공간 모델

순수 불리언 모델

질의에 매칭되는 문서가 있는지 없는지를 판단합니다. 각각의 Token에 대한 가중치 또는 검색 결과에 대한 점수 계산은 존재하지 않습니다. 각 Document, Field, Token에 대해서 연관도 점수가 없기 때문에 저장할 때 사용한 구조 그대로 정렬된 결과를 받을 수 있습니다.

벡터 공간 모델

질의와 문서 모두 고차원 공간의 벡터로 표현됩니다. 색인 생성 과정에서 Field가 분석된 결과인 각각의 Token(정확하게는 Term)이 하나의 차원에 해당합니다. 하나의 Document 포함된 Field들 그리고 Field이 분석된 결과인 각각의 Token에 대해서 사용자가 입력한 검색어와 유사로를 계산합니다. Document의 연관도 점수는 각각의 Token에 대해서 계산된 점수의 합입니다.

확률 모델

확률적인 방법을 통해 개별 문서가 질의와 일치하는지 확률을 계산한다. 이 부분에 대해서는 잘 몰라서 넘어가겠습니다.

Lucene과 와탭 검색 모델의 차이

Lucene은 순수 불리언 모델과 벡터 공간 모델을 함께 사용합니다. 와탭 로그 모니터링은 순수 불리언 모델만 사용합니다. 이 말을 사용자 관점에서 쉽게 풀어쓰면 “Lucene은 약간 틀리게 검색해도 잘 찾아주고, 와탭 로그 모니터링은 정확하게 입력했을 때만 찾아준다.” 입니다. 순수 불리언 모델과 벡터 공간 모델을 함께 쓰면 사용자는 편하고, 엔지니어는 힘들죠.

이러한 차이는 어디서 시작될까요? 이전 글 ‘검색엔진의 조회 구조 이해하기’에서 ‘원본 문서를 색인하고 검색하기 좋은 형태로 변환’이라는 말을 했었습니다. 검색엔진의 조회 기능은 색인한 형태로만 조회할 수 있습니다. 좀 더 구체적으로는 Lucene에서는 Field를 추출하고 Token으로 분석하는 과정을 Analyzer라는 이름으로 커스터마이징할 수 있도록 제공합니다. 반면에 와탭에서는 Grok Parser, Json Parser라는 이름으로 특정 Key-Value 쌍을 추출하는 기능만을 제공합니다.

Lucene의 Analyzer의 커스터마이징, Whatap Parser의 추출을 예시를 들어서 비교해보겠습니다. 수집한 로그에 ‘U.S.’라는 단어가 포함되어 있을 때, 와탭의 파서는 키워드를 추출하는 방식이기 때문에 정확하게 U.S.가 포함된 단어만 색인하고 검색할 수 있습니다. 반면에 Lucene에서는 synonyms analyzer를 사용해서 ‘U.S.’라는 단어에 American, ‘United States of America’와 같은 동의어를 추가할 수 있습니다. 좀 더 디테일하게는 SSTable에서 사용하는 offset에 대해서 원본 Token과 유의어 Token의 값을 같은 값으로 설정하는 방법을 사용합니다.

순수 불리언 모델은 간단하면서 정확하게 일치하는 것만 검색합니다. 작고 빠르고 정확합니다. 벡터 공간 모델은 서비스의 목적에 따라서 analyzer를 최적화를 잘 한다면 풍부하면서도 사용자의 의도에 맞는 검색 결과를 제공할 수 있습니다. 하지만 어쩔 수 없이 저장 공간을 더 많이 사용하고 상황에 따라서 조회 속도가 느릴 수 있습니다. 관점에 따라서, analyzer를 최적화 정도의 영향으로, 신뢰도가 낮은 검색 결과를 제공한다고 볼 수도 있습니다. 그래서 순수 불리언 모델보다 항상 벡터 공간 모델이 더 좋은 모델이라고 할 수는 없습니다. 물론 이 두 가지 방식을 모두 제공하는 것이 더 진화된 검색인 것은 분명합니다.

조회 기능 개발시 고려사항

검색 엔진의 저장 구조에서는 자료 구조를 예시로 들었다면, 조회 기능에서는 이런 자료 구조를 사용할 때의 고려사항을 이야기해보겠습니다. 아래의 모든 내용은 순수 불리언 모델을 기준으로 합니다.

여러 개의 검색어에 대한 AND, OR 검색 구현하기

AND / OR 어떤 방법으로 검색할지 결정하기

만약에 사용자가 여러 개의 검색어를 입력했다면, 검색 인터페이스에 맞게 AND 검색인지 OR 검색인지를 판단해야 합니다. 그런데 사용자가 입력한 값이 AND 검색인지 OR 검색인지는 사용자 인터페이스에 따라서 서비스의 내부 정책에 따라서 달라집니다.

와탭 로그 모니터링은 검색어를 Key-Value 쌍으로 선택합니다. 이 과정에서 같은 Key에 대해서는 여러개의 Value를 입력할 때 OR를 적용하고, 서로 다른 Key를 여러개 입력하면 AND로 처리합니다.

예를 들어 아래와 같이 검색어를 입력한다면

다음과 같은 로직으로 처리합니다.

(keyA == valueA || keyA == ValueB) && keyB == ValueC

 

여담이지만, 내부적으로 동작하는 검색의 방식을 사용자에게 자세하게 제공해야하는가?를 고민해볼 필요는 있습니다. Google에서 valueA, valueB, valueC에 대해서 검색할 때 AND로 검색할지 OR로 검색할지 일반 사용자가 생각하지는 않습니다. 그냥 검색할뿐이죠. 사실 AND OR는 순수 불리언 모델에 대한 관점이고, 아마 구글은 벡터 공간 모델로 점수 기반의 검색을 제공하는 것 같습니다.

AND / OR 검색 구현하기

다시 돌아와서 AND / OR 중 어떤 검색 방법을 사용할지 정해졌다면, 이를 구현할 때에는 어떻게 해야할까요? inverted index의 자료 구조는 Token의 정보를 사용해서 원본 데이터를 찾아가는 과정이라고 할 수 있습니다.

Token으로 원본 데이터를 찾을 수 있다는 가정이 있다면, AND와 OR 조건을 Token에 대해서만 적용을 하면 됩니다. 그리고 이 결과에 맞는 원본 파일을 찾으면 됩니다.

• KeyA - ValueA 검색 조건에 맞는 Token : TokenA, TokenB
• KeyB - ValueB 검색 조건에 맞는 Token : TokenA, TokenC
• 두 검색어를 AND 검색할 때 : TokenB가 포함된 원본 데이터만 조회
• 두 검색어를 OR 검색할 때 : TokenA, TokenB, TokenC가 포함된 원본 데이터를 모두 조회 단, 조회 순서는 원본 데이터의 저장 순서에 따름

막상 이 개념을 그대로 코드로 적용할 때에는 OR 보다 AND 방식의 검색을 더 선호하게 됩니다.

1. 사용자로부터 여러 개의 검색어 입력받기
2. 각각의 검색어에 대해서 연관된 Token을 조회하기
3. 각각의 Token Set에 대해서 AND 또는 OR 적용하기
4. 3단계의 결과에 따라 원본 데이터 조회하기

인덱스 기반 검색이 이루어지는 과정 중 3단계에서 메모리 사용량나서 OOM이 발생할 수 있기 때문입니다. transactionId나 containerId와 같이 cardinality가 높은 검색 키워드 2개에 대해서 OR 검색을 한다면, Token Set을 구하는 과정에서 OOM이 발생할 수 있습니다.

검색된 데이터를 모두 보여주어야 하나?

앞에서 구글 검색의 예시를 보면 97억 5천개의 데이터를 검색했다고 나옵니다. (0.38초 만에;;) 그런데 사실 사용자가 조회해보는 데이터는 대부분 첫 페이지의 상단에 있는 데이터뿐입니다. 많이 넘어간다고 해도 두 번째, 세 번째 페이지까지만 조회해봅니다.

이럴 때에는 “굳이 다 보여주어야하나?”의 관점에서 생각해볼 수 있습니다. 이 부분에 대한 생각은 이전에 작성했던 글의 링크로 대체하겠습니다.
2023.09.24 - [개발/INSIGHT] - COUNT와 Pagination, 필요없을 수 있습니다

엔지니어 관점보다 사용자의 관점에서 생각해보기

다시 구글 검색의 예시를 들어보겠습니다. 만약 “valueA valueB valueC” 라는 키워드로 여러번 검색을 하는데 어떨 때에는 97억 5천만개를 검색하고 어떨 때는 97억 4783만개를 검색한다면 어떨까요?

사실 제가 엔지니어 관점에서 “서버에서 자원이 남으면 남는 자원 사용해서 최대한 더 검색해야지”라고 접근했던 방식의 결과였습니다. 이 부분에 대한 생각도 이전에 작성해둔 글이 있어 링크를 남겨두겠습니다.

2023.09.20 - [개발/INSIGHT] - 성능과 사용자 경험의 사이에서

 

마치며

검색 기능을 만들면서 배우고 느낀 부분에 대한 기본적인 내용은 정리가 된 것 같습니다. 다음으로는 검색엔진의 고도화와 트러블슈팅에 대해서 글을 써보겠습니다.