Elasticsearch - BM25

ElasticSearch란?

2004년 샤이 배논(Shay Banon)은 Compass 라는 이름의 오픈소스 검색엔진을 개발하는 사람이였다.

처음 Compass 검색엔진 개발을 하게 된 계기는 요리 공부를 시작한 아내를 위해 레시피 검색 프로그램을 만들기 위해서였다.

레시피 검색 프로그램에 아파치 루씬(Apache Lucene)을 적용하려던 중 루씬이 가진 한계를 보완하기 위해 새로 검색엔진을 만들기 위한 프로젝트를 시작한 것이 계기였다.

2010년 샤이는 Compass를 Elasticsearch라고 이름을 바꾸고 프로젝트를 오픈소스로 공개하였는데, 곧 수 많은 검색 개발자들에게 인기를 얻으며 급속도로 성장하기 시작했다.

(그리고 샤이 배논의 아내는 아직도 레시피 프로그램을 기다리고 있다..)

Logstash, Kibana와 함께 사용 되면서 한동안 ELK Stack (Elasticsearch, Logstash, Kibana) 이라고 널리 알려지게 된 Elastic은 2013년에 Logstash, Kibana 프로젝트를 정식으로 흡수하여 한 지붕 아래에서 함께 개발을 해 나가고 있다.

2015년에는 회사명을 Elasticsearch 에서 Elastic으로 변경하고, ELK Stack 대신 제품명을 Elastic Stack이라고 정식으로 명명하면서 모니터링, 클라우드 서비스, 머신러닝 등의 기능을 계속해서 개발, 확장해 나가고 있다.

LIKE '%검색어%

검색의 근본적인 문제는 이 쿼리를 통해서 설명이 가능하다.

보통 무언 갈 검색하려면 인덱스을 걸어서 최적화를 많이한다.

인덱스를 거는 이유는 인덱스 레인지 스캔을 통해 필요한 범위만 빠르게 읽고 원하는 값을 가져올 수 있기 때문이다.

다중 칼럼 인덱스의 정렬 방식은 인덱스의 N번째 키 값은 N-1번째 키 값에 대해서 다시 정렬된다.

이건 데이터 타입이 varchar()이여도 통하는 것인데 압축해서 말해보자면, 인덱스에서 가용성을 지키려면 left_most가 되어야한다

예시로 들면 사전으로 이해할 수 있을 것 같다, 보통 사전에서 원하는 단어를 찾을때 맨 앞글자부터 찾지 않는가? 이 또한 같은 것 이다.

 

그림에서 볼 수 있듯이 왼쪽이 고정되지 않으면 인덱스 레인지 스캔이 불가능하고 풀 테이블 스캔을 해야한다.

풀 테이블 스캔은 인덱스를 전혀 사용하지 못하는 방식으로 테이블의 첫번째 레코드부터 마지막 레코드까지 순차적으로 검색하여 무식한 방식으로 속도가 매우 느리다.

LIKE '%셔츠' 랑 뭐가 다름?

LIKE '%셔츠%'는 "셔츠"가 어디에든 있으면 됨 → "면 셔츠 반팔" OK!

LIKE '%셔츠'는 "셔츠"로 끝나야 함 → "면 셔츠" OK!, "면 셔츠 반팔" NO

매칭 범위만 다를 뿐이지, 왼쪽이 고정 안 된 건 똑같아서 둘 다 인덱스 레인지 스캔 불가능, 둘 다 풀스캔

인덱스 관점에서는 의미 없는 차이이다.

결국 인덱스를 타려면 LIKE '셔츠%'처럼 왼쪽이 고정되어야만 한다.

그게 불가능한 상황에서는 ES의 역색인이 필요한 것이다.

편리한 검색은 후처리도 필요함

빠른 검색도 있지만, 정확한 검색도 필요함.

 

예를들어 “셔츠”라고 검색하면, “shirt”도 검색에 포함이 되어야함, 이걸 동의어 처리라고 한다.

하지만 기존 RDB에서는 이러한 기능을 구현하기가 쉽지않다.

 

동의어 테이블을 따로 만들어서 "셔츠 = shirt = shirts"를 매핑해두고 JOIN으로 검색하는 방식이다.

근데 이러면 생기는 문제점이 다양한다.

1. 쿼리가 복잡해진다.
2. 동의어가 늘어날수록 성능이 떨어진다
3. 형태소 분석(셔츠를 → 셔츠)까지 하려면 애플리케이션 레벨에서 직접 다 구현해야 한다.

하지만 ES는 다르다!

Elasticsearch는 모든 형태와 규모의 데이터를 검색, 인덱싱, 분석할 수 있도록 데이터를 중앙에 저장하는 분산형 RESTful 검색 및 분석 엔진이다.

Elasticsearch는 문서형 데이터 베이스(NoSQL)이다. (관계형(Relational) 구조가 아닌 문서형으로 저장한다)

NoSQL은 값을 저장할 때 문서인 JSON 형태로 데이터를 저장한다.

• 이러한 JSON을 Elasticsearch에 저장한다면 색인을 사용하여 저장한다.

• Elasticsearch는 그냥 저장하는 게 아니라, 검색 가능한 형태로 가공해서 저장한다.

• 해당 JSON은 불변타입으로 저장하게된다.
• 여기서 오는 많은 특징이 있는데, 장점과 단점으로 나눠본다

장점

#1. 불변타입 - 동시 읽기 - cache hit

• 불변타입으로 저장되므로 데이터 일관성을 보장(LOCK) 할 필요가 없어진다.
• 따라서 여러명에서 동시에 읽기를 시도할 때, 데이터 충돌이 발생할 위험도 없어진다.
• 값을 자주 바꾸지않는다면 캐시에 자리잡을 때도 오랫동안 자리잡을 수 있다.
• OS 계층과 Application 계층의 모두에서 cache hit률이 증가한다.

#2. 확장성 - 수직 & 수평

• RDB는 서버를 확장시킬 때 수직확장을 많이한다.
  • 일반적으로 서버가 한대로 부족하다면, 하나 더 추가하기보단, 그냥 서버 스펙을 늘린다.
  • 왜냐하면 데이터 일관성(트랜잭션, JOIN, 외래키)을 보장하려면 데이터가 한 곳에 있는게 유리하다.

• ES는 서버를 확장시킬 때 수평 확장을 많이한다. 왜그럴까? 
  • ES는 검색에 특화된 도구이기 때문이다.
  • 만약 서버가 하나라면, 데이터를 한 곳에서 다 뒤져야한다.

• 이런식으로 인덱싱을 거친 후 4대로 나눈다면, 1/4 크기만큼 동시에 뒤지면 된다.
• 따라서 서버를 늘릴수록 검색 속도가 비례해서 빨라진다.

• 이를 가능하게 하는 구조는 샤드라고 한다.
  • 각 노드에는 샤드라는 데이터가 실제로 저장되는 물리적 단위로 할당되고, 이 곳에 데이터를 분할 저장한다.
  • 나중에 색인을 했을 때 필요한 노드의 샤드부분만 빠르게 읽어 검색 속도가 향상될 수 있다.

• 또한 각 샤드는 레플리카(복제본)를 다른 노드에 저장한다.
  (같은 노드에 보관하면, 원본과 복제본이 같이 사라지기 때문이다.)

이러면 특정 노드가 장애로 죽어도 다른 노드의 레플리카가 해당 데이터를 가지고 있기 때문에,
데이터의유실 없이 검색이 가능하다.

레플리카도 검색 요청을 처리할 수 있어서, 병렬 검색 성능 향상 + 장애 안정성을 동시에 챙길 수 있다.

단점

#1. 재색인

• 기존 DBMS처럼 UPDATE 쿼리를 통해 조건에 해당 레코드만 수정하는 것이아니라, 문서 전체를 삭제하고 새로 작성해야됨.
• 생성 뿐만 아니라 색인도 다시해줘야 된다.
• 매번 최신화 하기에는 디스크 I/O 오버헤드가 발생함.

#2. 세그먼트 병합

• 재색인의 I/O 오버헤드를 줄이기 위해서 refresh 시점에 새로운 세그먼트로 디스크에 기록한다.
• 이 과정에서 새롭게 추가되는 문서들은 최신화가 바로 일어나지만, 삭제시킨 문서는 “지웠다”라는 표시만 남겨둔다.
• 어느정도 버퍼풀이 쌓인다면, 세그먼트를 병합해주는데, 이때 문서의 삭제가 실제로 일어난다.
• 결국 구 문서와 신 문서가 같이 존재하기 때문에 디스크 용량도 2배로 차지하게된다.

#3. Near Real-Time

• Near Real-Time 지연이 있는데, 새로 색인한 문서가 바로 검색에 잡히는 게 아니라,
  refresh가 일어나야 검색 가능해진다.
• 기본값이 1초라서 거의 실시간이긴 한데, 엄밀히는 즉시 반영이 아니다.
• 실시간 정합성이 중요한 시스템(예: 결제 잔액 조회)에서는 문제가 될 수 있다.

지금까지 ES가 왜 빠른지를 봤다.

트레이드 오프를 비교해보고, 검색 성능이 매우 중요하다면 Elasticsearch는 매우 매력적이다.

 근데 정확하기도 해야되지 않나?

정확하려면 어떻게 해야될까? → 잘 저장해야 된다!

딸깍~! (분석기)

문서는 DB에 저장되기 전에 분석기를 거친다.

분석기를 더 쪼개보면, Character Filter, Tokenizer, Token Filter 로 쪼갤 수 있다.

전체 청사진

먼저 청사진으로 전체 흐름을 파악해보자!

 

Character Filter

• 원본 문자 스트림을 대상으로 문자를 추가, 수정 또는 삭제한다. (다듬기)
• html 파일을 받는다고하면 <p>, </p>, <code>, <b>, </b>, 💳 같은 색인에 도움이 되지않는 문자를 제거한다.
• 근데 현실적으로는 삭제와 수정만 하게되고, 추가는 TokenFilter에 단계에서 동의어 처리할 때 처리한다.

Tokenizer

• 문장에 속한 단어들을 텀 단위로 하나 씩 분리해 내는 처리한다.
• 한국어는 조사가 많아서, 탐색의 한계가 있을 것을 고려하여 형태소 분석기가 따로 존재한다.

여기서 살짝 짐작할 수 있는게, RAG 개발에 ES를 쓴다면, Tokenizer의 종류에 따라 성능차이가 날 수 있다.

Tokenizer는 대표적으로 3개가 존재하는데 standard, Nori, N-gram 이다.

#1. Standard

공백과 구두점 기준으로 쪼갠다.

입력: "결제 승인 API는 POST /v1/payments/confirm으로 요청합니다"

토큰: [결제] [승인] [API는] [POST] [v1] [payments] [confirm으로] [요청합니다]

문제: "API는", "confirm으로" 처럼 조사가 붙어있음
→ 한국어에서는 이게 치명적
→ "API"로 검색하면 "API는"이 매칭이 안 될 수 있음

#2. Nori (한글 형태소 분석기)

한국어 문법을 이해해서 조사, 어미를 분리해준다.

입력: "결제 승인 API는 POST /v1/payments/confirm으로 요청합니다"

토큰: [결제] [승인] [API] [는] [POST] [v1] [payments] [confirm] [으로] [요청] [하] [ㅂ니다]

→ "API"와 "는"이 분리됨.
→ "API"로 검색하면 정확히 매칭됨.

#3. N-gram

글자를 일정 단위로 겹쳐서 쪼갠다, 자동완성 검색에 많이 쓰인다.

입력: "결제승인"  (2-gram 기준)

토큰: [결제] [제승] [승인]

→ "제승"이라고 쳐도 매칭이 됨
→ 자동완성에는 좋지만 토큰이 많아져서 인덱스 크기가 커짐

나중에 RRF 방식으로 Vector DB와 같이 사용한다면 Nori를 사용하는게 맞겠지만,
N-gram과 비교해 볼 수도 있을 것 같다.

Token Filter (후처리)

• Tokenizer가 분리해준 토큰들을 후처리(Post-processing) 해준다, 크게 3가지를 하는데
  1. 불용어 제거:
     1. Nori가 분리해준 [는], [으로], [하], [ㅂ니다] 같은 조사와 어미는 검색에 도움이 안 되니까 여기서 날려버린다.
  2. 동의어 추가:
     1. [결제]라는 토큰이 들어오면 [payment]도 같이 추가해둔다.
     2. 이러면 나중에 영어로 'payment'라고 검색해도 한국어 '결제' 문서가 나온다.
     3. 아까 LIKE %검색어% 쿼리에서 불가능했던 게 여기서 해결되는 것이다.
  3. 소문자 변환:
     1. [API]를 [api]로, [POST]를 [post]로 통일한다.
     2. 이래야 사용자가 대문자로 치든 소문자로 치든 같은 결과가 나온다.

역색인

문장을 단어로 잘게 쪼개어놨다면, 이제 역색인을 통해 ES에 저장해야된다.

Token Filter를 후처리된 단어들을 ES에 저장하면 아래와 같이 저장된다.

 

결론적으론 이런식으로 검색을 했을 때 단어에 맞는 문서를 넘겨 주는 것이 ES의 역할이다.

 

여기까지 ES의 BM25 알고리즘 기반 키워드 검색의 원리이다.

 

 

키워드 정리

역색인 

보통 RDB에서 LIKE '%검색어%'로 검색하면 left_most 규칙에 의해, 인덱스를 탈 수 없어 full table scan을 해야 한다.
ES는 이 문제를 역색인으로 해결한다. 
역색인은 Analyzer의 3단계를 거치게 된다.

1. Charactor Filter -  문장에 필요없는 문자들을 제거한다.

2. Tokenizer - 문장에 속한 단어들을 텀 단위로 하나 씩 분리한다. (토큰화)

3. Token Filter - Tokenizer가 분리해준 토큰들을 후처리를  해준다. (불용어 제거, 동의어 추가, 소문자 변환)  

불변저장

ES는 문서를 불변으로 저장하기 때문에, 한번 캐시에 올라간 데이터는 캐시 무효화가 잘 일어나지 않는다.
OS, APP 계층에서 cache hit률이 높아지고 오버헤드가 줄어든다.
또한 데이터가 변경될 일이 없으므로 정합성을 맞출 필요가 없어 Lock이 불필요해진다.

Lock이 불필요 해지니, 동시다발적으로 같은 데이터를 읽을 수 있다.

수평 확장

ES는 하나의 서버의 사양을 늘리는 방식이 아니라, 여러 노드를 추가하여 확장한다.
하나의 인덱스를 여러 샤드로 분할하여 노드에 분산 저장한다.
검색 시에는 샤드 단위로 병렬 처리가 이루어지며, 이 샤드들이 여러 노드에 분산되어 실행된다.
이러한 구조는 성능 향상을 가져올 수 있지만, 네트워크 비용, 샤드 수, 클러스터 구성 등에 따라 선형적으로 증가하지는 않는다.

 

샤드에 대해 좀더 자세히 찾아봐야겠다.

 

 

다음은 기존 RAG를 구현할 때 쓰는 Vector DB의 kNN 알고리즘은 어떤 문제점이 있고 BM25가 어떤 도움을 줄 수 있는지 알아 보자...