루씬(Lucene) 검색 엔진의 구조 (FST, Burst Trie, 역 인덱스)

ElasticSearch는 아파치 루씬(Apache Lucene)이라는 검색 엔진 라이브러리를 활용해 분산 환경에서의 고성능 검색 기능을 제공한다.

고성능 검색 기능은 루씬(Lucene)의 저수준 API를 조립해 REST API로 제공하는 것인데, 루씬은 어떤 방식을 사용하길래 대용량 데이터를 디스크에서 빨리 읽을 수 있는 걸까? 루씬의 구조를 파악해 보자.

사전 지식 1. 역 인덱스

역 인덱스

역 인덱스는 위의 이미지처럼 Hash Table로 되어있지 않지만 단어(Term)로 문서의 아이디를 찾을 수 있는 자료구조라고 이해하자.

사전 지식 2. 루씬은 최소 단위로 세그먼트를 사용한다.

루씬(Lucene)은 색인의 최소 단위로 세그먼트(segment)를 사용한다. 다시 세그먼트는 여러 문서(Document)로 되어있는데, 중요한 것은 세그먼트 단위로 관리한다는 것을 기억하자.

세그먼트는 하나의 디렉토리다. 이 디렉토리 안에 여러 파일들이 있고,`.tip`, `.tim`, `.doc`, `.pos`, `.pay` 파일이 있다.

이 파일들에 실제 문서(Document)가 저장되니, 즉 `.tip`, `.tim`, `.doc`, `.pos`, `.pay` 파일이 하나의 세그먼트를 이룬다.

각 파일들에 대한 설명은 아래에서 자세히 다루니 지금은 넘어가자.

사전 지식 3. 세그먼트들이 모여 루씬 인덱스(Lucene Index)가 된다.

Lucene Index

루씬(Lucene)은 세그먼트(디렉토리)들을 모아 루씬 인덱스(Lucene Index)를 구성한다. 루씬 인덱스는 역 인덱스(Inverted Index)를 포함하는 파일의 집합 개념으로 좀 더 큰 의미의 인덱스다로 이해하자. 루씬 인덱스를 이루는 세그먼트들은 역 인덱스의 일부를 구성한다.

(세그먼트(디렉토리) → 역 인덱스(파일들) → 루씬 인덱스)

 

이제부터 루씬에서 사용하는 특별한 자료구조를 알아보자.

전체 색인 구조

먼저 전체 색인 구조를 보자. 위의 세그먼트에서 알아봤듯이 `.tip`, `.tim`, `.doc/.pos/.pay`는 모두 디스크에 저장되는 파일을 의미한다.

루씬(Lucene)은 인입된 단어(Term)를 prefix와 suffix로 나눠서 저장하는데,

"he", "hell", "hello"라는 단어들이 인입되면 공통된 접두어(common prefix)인 "he"는 `.tip`에, 나머지 suffix("ll", "llo")는 `.tim`에 나눠서 저장한다.

 

각 파일은 아래와 같이 간략하게 설명한다.

• `.tip` 파일:
  • tip은 Term Index Prefix를 의미한다.
  • 단어(Term)들의 공통 접두어(common prefix)를 저장한다.
  • FST(Finite State Transducer) 자료구조를 사용한다.
  • FST 자료구조에서 리프 노드는 `.tim` 파일의 파일 포인터(File Pointer; FP)를 저장하고, 이 파일 포인터는 해당 `.tim` 파일을 디스크의 어느 위치부터 읽어야 하는지를 알려주는 오프셋(offset)을 의미한다.
• `.tim` 파일:
  • tim은 Term Index Map을 의미한다. 단어(Term)와 단어가 나타나는 문서의 위치(Position) 등을 연결(Mapping)한다.
  • 단어(Term)의 suffix들을 저장한다.
  • Burst Trie 자료구조를 사용한다. (Trie 자료구조와 유사하다)
  • Burst Trie 자료구조에서 리프 노드는 `.doc/.pos/.pay` 파일의 파일 포인터(FP)를 저장한다.
• `.doc/.pos/.pay` 파일은 각각 문서 아이디의 배열(skip list 형태이 Document ID), 문서 내 단어의 위치(Position), 사용자 정의 메타데이터(중요도 등 사용자가 별도로 정의)가 저장되어 있다.

이제 가장 위의 `.tip` 파일과 관련된 FST부터 알아보자.

.tip 파일과 FST (Finite State Transducer) 자료구조

FST 자료구조는 단어(Term)를 효율적으로 처리하는 자료구조다.

단어를 효율적으로 처리한다는 의미는 쓰기 작업과 읽기 작업이 효율적이라는 뜻이다.

다시 말해, 쓰기(색인) 작업할 때 저장하는 크기를 줄이고, 읽기(검색) 작업할 때의 성능을 높인다는 의미다. 루씬 Repository에 구현되어 있다.

 

좀 더 살펴보면 FST는 `상태(state)`와 `전이(trasition)`로 구성된 트리 구조의 형태를 띤다.

• 상태(state)는 단어들의 공통된 접두어(prefix)를 나타내며, 트리의 노드이다. 각 노드는 `Arc`의 배열로 연결되어 있고, 사전순으로 정렬되어 있다. (`Arc`는 FST의 상태와 전이 정보를 나타내는 구조체이다.)
  
  예를 들어, "he", "hell", "hello"라는 단어가 있다면 "he"라는 공통 prefix를 갖는다. FST는 공통된 "he"를 하나의 상태(=노드)로 합치고, 나머지 "hell", "hello"는 다른 상태(=노드)로 분기한다.
• 전이(transition)는 현재 노드에서 특정 입력 문자(label)에 따라 다음 노드로 이동하는 과정을 의미한다. 이런 전이를 통해 문자열의 prefix를 따라가며 검색한다.
  
  예를 들어, "hello"라는 단어로 검색을 하면 먼저 "he"라는 prefix를 따라 FST 노드를 순차적으로 이동한다.
  전이 동작은 먼저 루트 노드에서 "h"라는 입력 문자(label)를 기준으로 "h"에 해당하는 `Arc`를 찾는다.
  그다음 입력 문자 "e"를 기준으로 "e"에 해당하는 `Arc`를 찾아 "e" 노드로 이동한다.
  참고로 트리에서 각 노드들(prefix)에 연결된 `Arc` 배열은 사전순으로 정렬되어 있기 때문에 "h" 다음의 "e"라는 `Arc`를 찾을 땐 binary search를 활용한다. (시간 복잡도: O(log n))

입력한 문자(label)를 따라가며 노드를 이동하는 과정(=전이)에서 binary search를 사용하는 부분

https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/util/fst/FST.java

public Arc<T> findTargetArc(int labelToMatch, Arc<T> follow, Arc<T> arc, BytesReader in)
      throws IOException {

    // ... 생략

    // Array is sparse; do binary search:
    int low = 0;
    int high = arc.numArcs() - 1;
    while (low <= high) {
        // System.out.println("    cycle");
        int mid = (low + high) >>> 1;
        // +1 to skip over flags
        in.setPosition(arc.posArcsStart() - (arc.bytesPerArc() * mid + 1));
        int midLabel = readLabel(in);
        final int cmp = midLabel - labelToMatch;
        if (cmp < 0) {
          low = mid + 1;
        } else if (cmp > 0) {
          high = mid - 1;
        } else {
          arc.arcIdx = mid - 1;
          // System.out.println("    found!");
          return readNextRealArc(arc, in);
        }
    }
    
    // ... 생략
  }

 

.tip(FST) 파일과 .tim(Burst Trie) 파일의 관계

다시 돌아오자.

FST는 단어(Term)를 통째로 저장하지 않는다. 단어들의 공통된 접두어(common prefix)를 노드(=상태)로 저장한다.

그럼 왜 공통된 접두어(common prefix)만 저장할까?

그 이유는 검색 속도를 위해 단어들의 공통된 부분(common prefix)만 잘라내어 하나의 노드로 합치면 트리의 깊이를 최소화할 수 있기 때문이다.

대신 suffix 부분은 `.tim` 파일 (Burst Trie 자료구조)에 그대로 저장한다. 그리고 해당 `.tim` 파일의 파일 포인터(FP)를 FST의 리프 노드에 저장한다. FST는 리프 노드에 파일 포인터(FP)를 저장하기 때문에 파일 포인터(오프셋)를 통해 관련 suffix가 있는 위치로 점프해서 읽을 수 있게 되고, 이 때문에 디스크에 저장하더라도 검색 성능이 빠른 것이다!

.tim 파일과 Burst Trie

루씬은 역 인덱스에서 suffix 부분을 `.tim` 파일에 저장하는데, Burst Trie 자료구조를 사용한다.

Burst Trie는 Trie 자료구조와 유사하지만, 검색 효율을 위해 메모리 할당과 I/O 성능을 최적화한 자료구조다.

그렇다면 어떻게 메모리 할당과 I/O 성능을 최적화하는지 알아보자.

Burst Trie 자료구조 핵심 원리

대규모 데이터를 다룰 때 메모리는 디스크보다 상대적으로 크기가 작기 때문에 한계가 있을 수밖에 없다.

• Burst Trie는 이런 한계를 극복하고 트라이 구조에서 발생할 수 있는 메모리 낭비를 방지하기 위해 일부 노드는 디스크에 저장한다.
• 또한, 한 노드에 저장되는 데이터의 개수가 일정 수준을 넘어가면 노드를 터트려서(Burst) 하위 노드를 생성해 데이터를 분산시킨다.
• 트리 구조와 파일포인터(FP)를 합친 형태로 메모리 주소가 아닌 디스크의 파일 포인터를 가리킨다. 따라서 검색할 때 파일포인터(오프셋)를 통해 필요한 부분만 디스크에서 읽어와 메모리에 로드해 메모리 사용량을 줄이고 빠른 탐색이 가능한 것이다.

루씬에서 Burst Trie의 원리를 적용하는 방법

단어(Term)를 색인할 때

루씬의 Lucene90BlockTreeTermsWriter는 Burst Trie의 원리를 적용해 트리 구조의 `.tim` 파일을 생성한다. 저장하는 값은 

루트 노드에 단어(Term)의 common prefix를 저장하는데, 이 common prefix를 기준으로 하위 노드를 나누고 하위 노드에 suffix와 .doc/.pos/.pay 파일 포인터가 저장된다. 한 노드에 저장하는 단위는 블록(Block)이며, 한 블록엔 단어(Term) 최소 25 ~ 최대 48개를 저장한다. 각 단어(Term)마다 아래 네 가지가 저장된다.

1. suffix (FST에서 단어(Term)의 prefix를 제외한 나머지)
2. .doc의 파일 포인터 (검색한 단어(Term)가 등장하는 문서의 ID들의 배열
   (skip list 형태: 문서 ID가 [100, 105, 110]일 경우, [100, +5, +5]로 저장))
3. .pos의 파일 포인터 (문서 내에서 해당 단어의 위치)
4. .pay의 파일 포인터 (사용자 정의 메타데이터)를 저장한다.

만약 블록이 최대 48개가 넘는다면 Burst를 통해 하위 블록으로 나누는 부분은 아래 코드로 구현되어 있다.

// Lucene90BlockTreeTermsWriter.writeBlocks() 메서드 중 일부
if (itemsInBlock >= minItemsInBlock && end - nextBlockStart > maxItemsInBlock) {
    boolean isFloor = itemsInBlock < count;
    newBlocks.add(
        writeBlock(
            prefixLength,
            isFloor,
            nextFloorLeadLabel,
            nextBlockStart,
            i,
            hasTerms,
            hasSubBlocks));

    hasTerms = false;
    hasSubBlocks = false;
    nextFloorLeadLabel = suffixLeadLabel;
    nextBlockStart = i;
  }

 

단어(Term)를 검색할 때

읽을 때는 Lucene90BlockTreeTermsReader가 동작하고, FST를 활용해 Burst Trie와 비슷한 방식으로 탐색한다.

특정 단어(Term)를 검색했을 때 대략 아래와 같은 순서로 검색한다.

1. `.tip` 탐색: `.tip` 파일에서 단어(Term)의 첫 번째 char부터 순서대로 FST(prefix)를 탐색하고 리프 노드에서 prefix에 해당하는 `.tim` 파일 포인터(FP)를 가져온다.
2. `.tim` 탐색: Burst Trie를 메모리로 로드하고, suffix를 탐색하여 `.doc/.pos/.pay` 파일 포인터(FP)를 가져온다.
3. `.doc/.pos/.pay` 접근: 각 파일을 디스크에서 읽어 단어(Term)가 등장하는 문서 ID 배열, 위치, 메타데이터를 반환한다.

참조

• https://chocolate-life.tistory.com/8
• https://chocolate-life.tistory.com/9
• https://chocolate-life.tistory.com/10
• https://github.com/apache/lucene