잉여의 생각저장소

선행

Lucene 역색인(Inverted Index) 심층분석 1 - 전체 색인 구조

Lucene 역색인(Inverted Index) 심층분석 2 - FST

참고

Lucene90 FST code

Lucene90 BlockTreeTerms code

Burst Tries - A Fast, Efficient Data Structure for String Keys 논문

분석

Burst Tries 논문은 너무 추상적이고 정답이 없는 문제를 다뤄 증명 대신 실험에 의한 효과 증명으로 결과를 입증한다. 따라서 이번 글에선 최적화 요소가 더 많이 적용되고 더 직관적으로 이해할 수 있는 Lucene 역색인 모듈들을 직접 분석한다.

1. BlockTreeTerms Writer

심층분석 1에서 대략적으로 다뤘듯이 Lucene은 색인할 Term 전체를 FST에 저장하지 않는다. Lucene의 역색인은 BYTE 단위로 Term을 잘라 common prefix는 FST에 저장하고 나머지 suffix들은 Block으로 묶어서 저장한다. 색인 전 과정은 BlockTreeTermsWriter가 담당하며 아래 정의 및 절차에 따라 진행한다.

1. Terms는 사전순 정렬을 전제로 하며 순차적으로 iteration 하며 common prefix를 찾는다.
2. 가장 긴 prefix를 기준으로 Block 가능성을 탐색한다.
   (예를들어 "abc", "abd"의 common prefix는 "a" 일수도 있지만 "ab"가 더 길어서 기준이 됨)
3. Block 구성에 필요한 최소 Term 수(MIN_BLOCK_SIZE)는 25, 최대 Term 수(MAX_BLOCK_SIZE)는 48개 이다.
4. MAX_BLOCK_SIZE 넘어서는 common prefix는 여러 Block들로 나눠 저장하며 이는 FloorBlock이라 한다.
5. Term에서 common prefix 이후 첫 BYTE를 label이라 한다. floorLeadLabel은 FloorBlock 첫 Term의 label 이다.
6. Block으로 묶으면 Pendings의 Term들이 하나의 SubBlock으로 대체된다.
   (그림1에서 "ab" ~ "abcz" Term들이 "ab" SubBlock이 됨)
7. Block은 Terms 뿐만 아니라 SubBlock도 저장할 수 있다. 때문에 .tim의 구조를 BlockTreeTerms 라 불린다.
8. Block 내 SubBlock 없이 Terms 만 있다면 LeafBlock이라 한다.

그림1의 "ab" leafBlock 생성과정을 통해 자세히 알아보자. BlockTreeTermsWriter는 common prefix를 가진 Term 수가 MIN_BLOCK_SIZE 이상이 될 때까지 Pendings를 탐색한다. "aa"로 시작하는 Terms는 하나이므로 "ab"를 기준으로 Terms 범위를 찾는다. ("aa"는 추후 "a" Block에 저장한다.) "ab" ~ "abcz" Terms는 40개로 MIN_BLOCK_SIZE 이상 MAX_BLOCK_SIZE 미만이라서 하나의 Block만 생성한다. Block 생성 시 FST에는 .tim FP, floor info를 저장하며 BlockTreeTerms에는 suffixes 및 postings FP를 저장한다.

"ab~" Terms는 Pendings에서 SubBlock으로 변환하여 하나의 요소가 된다. 이후 "ac~", "ad~", "ae~" 기준들로 Block 생성 시도하지만 MIN_BLOCK_SIZE를 넘지 못해 넘어간다. 이후 "b" Term을 처리하는 시점(leadLabel의 index가 바뀌는 시점)에 "a~" Pendings로 Block 생성 시도한다.

"a~" Pendings는 총 74개로 MAX_BLOCK_SIZE를 넘어 여러 Block들로 저장해야 한다. 이때도 label을 기준으로 Block들을 나누는 기준이 된다. 그림2 예시로 "a" ~ "acw" 까지 26개 Pendings가 묶인다. 이때까지 label은 'c'이며 "ada"를 탐색하는 순간 label이 'd'로 바뀐다. Block에 Pendings를 넣을 때 "ada" ~ "adx" 중 top 몇 개의 Pendings 만 넣을 수 없다. 현재 26개 Pendings로 구성하고 있는 Block에 MAX_BLOCK_SIZE를 채우기 위해 모자란 22개 "ad~" Terms만 Block에 넣을 수 없다는 뜻이다. "a" ~ "adx"로 Block을 구성하면 50개로 MAX_BLOCK_SIZE를 넘기에 "a" ~ "acw" 까지 최초의 "a~" Block을 생성한다. 첫 번째 Term이 suffix가 없으면 lead label이 -1 이다.

leadLabal이 'd' 인 상태로 나머지 Block 생성을 진행한다. "ad~" Pendings는 MIN_BLOCK_SIZE를 넘지않아 leadLabel 'e' 까지 탐색하고 "ada" ~ "aex" 까지 총 48개 Pendings로 Block을 생성한다. "ad~" Pendings는 MIN_BLOCK_SIZE를 넘지 않지만 "ae~" Pendings는 MIN_BLOCK_SIZE를 넘으면 어떻게 Block을 구성할 지 의문이 들 수 있다. 예를들어 "ad~" Pendings가 24개이고 "ae~" Pendings가 30개라면 총 54개로 MAX_BLOCK_SIZE를 넘기 때문이다. 하지만 이 경우는 존재하지 않는다. "a~" Pendings로 Blocks를 구성하는 시점에 "ae~" Pendings는 이미 MIN_BLOCK_SIZE를 넘어 하나의 SubBlock Pending으로 변해 있기 때문이다. 때문에 두 개의 서로 다른 labels로 Block 내 MAX_BLOCK_SIZE 이상 Pendings를 저장 할 수 없다. 그리고 MAX_BLOCK_SIZE는 이론상 (MIN_BLOCK_SIZE - 1)의 배수여야 한다.

SubBlock을 저장은 .tim의 경우 현재 FP 위치와 prefix Block FP의 차이만큼 저장한다. 그림2 예시로 "a"(-1) Block 내 "ab" SubBlock의 FP가 500이고 "ab~" Block의 FP가 20 이라면 next FP에 480을 저장하는 방식이다. BlockTreeTerms는 이렇게 간단하게 구현하지만 FST는 약간 복잡하다. 왜냐하면 "ab~" Block을 먼저 생성하고 "a~" Block이 나중에 생성 되었으므로 사전순으로 FST에 색인할 수 없기 때문이다. 이를 해결하기 위해 색인 중에만 BlockTree level에 따라 subIndices라는 child FST를 생성한다. Block 생성시 subIndice 병합하는 과정을 아래와 같이 거쳐 FST 생성 시 사전 순 입력을 보장한다. (BlockTreeTermsWriter::compileIndex 참고)

  public void compileIndex(
      List<PendingBlock> blocks,
      ByteBuffersDataOutput scratchBytes,
      IntsRefBuilder scratchIntsRef)
      throws IOException {

      ...

      // Copy over index for all sub-blocks
      for (PendingBlock block : blocks) {
        if (block.subIndices != null) {
          for (FST<BytesRef> subIndex : block.subIndices) {
            append(fstCompiler, subIndex, scratchIntsRef);
          }
          block.subIndices = null;
        }
      }
      
      ...
  }

  private void append(
        FSTCompiler<BytesRef> fstCompiler, FST<BytesRef> subIndex, IntsRefBuilder scratchIntsRef)
        throws IOException {
      final BytesRefFSTEnum<BytesRef> subIndexEnum = new BytesRefFSTEnum<>(subIndex);
      BytesRefFSTEnum.InputOutput<BytesRef> indexEnt;
      while ((indexEnt = subIndexEnum.next()) != null) {
        fstCompiler.add(Util.toIntsRef(indexEnt.input, scratchIntsRef), indexEnt.output);
      }
    }
  }

전반적인 프로세스 설명은 마치며 FST -> BlockTreeTerms -> Doc, Pos, Pay 절차 및 Codec을 간략히 정리하면 아래와 같다. Lucene은 끊임없이 최적화 요소를 적용하고 있어서 자세한 사항은 내부 구현 및 테스트로 확인해야 한다.

2. BlockTreeTerms Reader

색인에서 term을 찾고 데이터를 읽는 과정이다. 앞서 BlockTreeTermsWriter 과정 이해를 전제로 한다.

SegmentTermsEnum이 각각의 Segment에 대응하여 생성되고, 특정 term을 찾거나 전체 term들을 찾는 동작을 수행한다. SegmentTermsEnum은 Block의 depth 마다 SegmentTermsEnumFrame을 생성하고 읽기 상태에 따라 FST.Arcs, term 데이터를 관리한다. SegmentTermsEnumFrame이 Block을 읽는 역할을 수행하며 FloorBlock들도 한 Frame 내에서 읽는다.

Block을 읽는 동작과 Postings를 읽는 동작은 분리되어 있다. 즉 term을 찾을 땐 .tip/.tim 파일만 decoding 하고 해당 term의 Postings를 읽을 때 .doc/.pos/.pay 파일을 decoding 한다.

전체 Terms 탐색 (NextTerm)

1. 전체 탐색은 .tip에서 .tim 시작 FP만 참조할 뿐 .tip에서 검색하지 않는다.
2. .tim의 root Block에서 SegmentTermsEnumFrame을 생성하고, root Block의 term 들을 순차적으로 탐색한다.
3. 탐색할 때 NonLeafBlock(term이 아닌 Block)이 나오면 SegmentTermsEnumFrame를 하나 더 생성하고 depth가 증가한다.
4. 마치 tree 탐색처럼 모든 Leaf를 탐색하면 depth가 감소하여 다시 탐색하는 동작을 반복한다.

특정 Term 탐색 (SeekExact)

1. 특정 term 탐색은 .tip에서 term의 첫 번째 char부터 순차적으로 FST를 탐색한다.
2. FST에 char의 arc를 찾을 수 있다면 SegmentTermsEnumFrame을 생성하고 다음 char를 탐색한다.
   (이때 SegmentTermsEnumFrame에는 arc 정보와 FST의 output을 읽어서 저장한다.)
3. FST에서 찾을 수 있는 최대 길이의 prefix를 다 찾았다면 FloorBlock을 탐색한다.
4. FloorBlock들의 정보는 FST의 output에 VInt로 저장되어 순차적으로 탐색해야 한다.
5. 최종 확인해야 할 Block이 정해지면 해당 Block을 load 한다. (suffixs, stats, postings FP 정보)
6. suffixs를 탐색하여 해당 term이 매칭되는지 확인한다.
   
   

심화

Lucene 역색인 시공간 복잡도

MIN_BLOCK_SIZE, FST::BYTE가 색인의 크기, 검색 속도를 결정하는 중요한 값.

Block의 시공간 복잡도

• "a~" blocks 에는 "ab~" pendings가 MIN_BLOCK_SIZE개 이상 존재할 수 없다.
• "a~" blocks 의 가능한 모든 label의 경우의 수는 기본값 FST::BYTE의 크기이며 최대 256 이다.
• "a~" blocks 내 같은 label의 최대 pendings 수는 MIN_BLOCK_SIZE - 1 이다.
• "a~" blocks 내 최대 pendings 수는 BYTE x (같은 label 최대 pendings 수) 이므로 256 * (MIN_BLOCK_SIZE - 1) 이다.
• 그렇다면 최대 FloorBlock 수도 구할 수 있다. label이 최대 BYTE 가지 존재하고 label이 바뀌는 시점마다 FloorBlock을 생성 할 수 있다. label이 최소 2번은 바뀌어야 FloorBlock을 생성 할 수 있기 때문에 최대 FloorBlock 수는 BYTE1 / 2 이다.
  
  

MIN_BLOCK_SIZE 특성

• MAX_BLOCK_SIZE는 (MIN_BLOCK_SIZE - 1) 의 배수
• MIN_BLOCK_SIZE가 높을수록 FST와 BlockTreeTerms의 크기 및 깊이가 감소한다.
• MIN_BLOCK_SIZE가 높을수록 전체 Block 수는 감소하지만 FloorBlock 수는 지수배로 늘어난다.
  물론 MIN_BLOCK_SIZE가 1 ~ 5로 극단적으로 작다면 Block 및 FloorBlock 수 모두 늘어나고 검색효율도 떨어진다.
• MIN_BLOCK_SIZE가 높을수록 SeekExact 시 FST 탐색속도 빨라지고 BlockTreeTerms 탐색속도는 상당히 느려진다.
  애초에 FST가 빠른 탐색이 목적이기에 전체 검색속도는 FST 탐색이 감소한만큼 급격하게 늘어난다.
  FloorBlocks는 현재 순차적으로 탐색하기에 여기에서 병목 또한 늘어날 것으로 예상한다.
  FloorBlocks 탐색 개선요소 주석
  
  

FST::BYTE 가 커질 수록

• Block을 묶는 기준이 강화되서 총 Block 수 및 depth가 감소한다.
• 최대 FloorBlock 수가 늘어난다. (BYTE_SIZE / 2)
• FST 크기가 소폭 감소한다. 특정 Block에서 FloorBlock 수가 늘어 output이 커질 수 있지만 총 Block 수가 줄어드므로 전체 크기는 감소한다. FST 탐색속도는 언어에 따라 다를 수 있다. 예를들어 한글의 경우 BYTE2 이상으로 설정하면 불필요한 구간에서 node, arc가 발생하지 않아 검색속도 개선에 유리하다.
• BlockTreeTerms 크기가 증가한다. 더 세밀하게 term들을 쪼개지 못해 평균 FloorBlock 수가 증가 했으므로 탐색시간이 증가한다. depth가 줄어들어 크기는 감소할 수 있지만 묶지 못한 케이스가 많을 경우 suffix 데이터가 증가하여 전체 크기는 증가한다.