일단 써보기

Apache Lucene에서 사용된 Incremental indexing기법의 기반이 된 Doug Cutting의 Optimizations for dynamic inverted index maintenance.논문을 읽고 정리한 글입니다.
https://dl.acm.org/doi/10.1145/96749.98245

1. Apache Lucene 소개

Apache Lucene은 오픈소스 정보 검색 라이브러리로, 트위터, 위키피디아, 링크드인, 넷플릭스, 아이튠즈 스토어, 세일즈포스 등 구글과 페이스북을 제외한 대부분의 검색 엔진에서 사용됩니다. 솔라(Solr), 엘라스틱서치(ElasticSearch) 등의 검색엔진이 Apache Lucene을 기반으로 하고 있어 그 중요성이 더욱 부각됩니다.

Apache Lucene은 문서를 빠르게 색인하고 검색할 수 있는 기능을 제공하는데, 특히 증분식 색인(incremental indexing) 기법을 통해 문서가 추가될 때마다 효율적으로 색인을 갱신하는 방식을 사용합니다. 이 기술은 Doug Cutting의 1990년대 후반 연구에 기반합니다.

1.1 증분식 색인(Incremental Indexing)이란?

증분식 색인이란 기존 문서 집합에 새로운 문서가 추가될 때, 전체 문서를 다시 색인하지 않고 추가된 문서만 색인하는 방식입니다. Lucene에서는 이를 위해 병합 색인(merge indexing) 기법을 사용합니다.

1.2 Lucene의 증분식 색인 주요 특징

1. 개별 색인 생성: 새 문서가 추가되면, 해당 문서만을 위한 작은 색인을 따로 생성
2. 색인 병합: 일정 개수의 작은 색인들이 쌓이면, 이들을 하나의 큰 색인으로 병합
3. 백그라운드 처리: 병합 과정은 백그라운드에서 이루어져 검색 성능에 영향을 최소화
4. 증분식 갱신: 이 과정을 반복하면서 전체 문서 집합의 색인을 증분식으로 갱신
5. 다중 색인 검색: 검색 시에는 모든 색인을 동시에 검색하여 안정적인 검색 성능 보장

이러한 증분식 색인 기법을 통해 대용량 문서 집합에 대해서도 빠르게 색인을 갱신하고 일관된 검색 결과를 얻을 수 있습니다. 이는 Lucene이 실시간 검색 엔진으로 널리 사용되는 데 크게 기여한 핵심 기술입니다.

2. 논문 분석

2.1 배경

많은 문서 검색 시스템에서는 사용자가 자유롭게 키워드를 입력하면 그에 맞는 문서를 찾아주는 자유 텍스트 검색(free-text search) 기능을 제공합니다. 이때 시스템 내부적으로는 역색인(inverted index)을 사용하여 검색을 수행합니다.

문서 집합(코퍼스)은 끊임없이 변화하기 때문에, 새로운 문서들이 추가되거나 기존 문서들이 삭제 또는 수정될 때마다 역색인을 실시간으로 갱신할 수 있어야 합니다. 이러한 배경에서, 이 논문은 B-tree를 기반으로 역색인을 효과적으로 동적 갱신하는 방안을 연구했습니다.

2.2 역색인(Inverted Indices)

역색인은 기본적으로 단어(word)를 키로 하고, 그 단어가 출현한 문서들의 식별자(document ID)를 값으로 가지는 일종의 맵핑 테이블입니다. 논문에서는 이때 값에 해당하는 문서 식별자들의 집합을 포스팅(posting)이라고 지칭합니다.

역색인을 설계할 때 고려해야 할 주요 성능 기준은 다음과 같습니다:

1. 색인 구축 속도(index build speed): 새 문서를 색인에 추가하는 속도
2. 색인 검색 속도(access speed): 쿼리에 대한 결과를 검색하는 속도
3. 색인의 크기(index size): 저장 공간의 효율성
4. 동적 갱신 용이성(dynamics): 색인이 변경될 때 효율적으로 갱신하는 능력
5. 확장성(scalability): 문서 수가 증가해도 성능을 유지하는 능력

2.3 Naive B-tree의 단점

B-tree는 디스크와 같은 2차 저장소에 저장되는 균형 잡힌 트리 구조입니다. 분기 계수(branching factor) b가 클 때 다양한 장점이 있지만, 역색인 구현에 있어 몇 가지 단점이 있습니다.

나이브한 B-tree 기반 역색인 구현의 주요 단점:

• 단어 중복: (단어, 위치) 쌍을 엔트리로 사용할 경우 같은 단어가 여러 번 중복 저장됨
• 비효율적인 갱신: 새 문서마다 모든 단어에 대해 개별 B-tree 삽입 작업 필요
• 디스크 접근 과다: 삽입 시 B-tree를 루트에서 리프까지 탐색해야 함
• 문서 삭제 비용: 문서 내용을 모른다면 전체 색인을 스캔해야 함

2.4 속도 최적화 (Speed Optimization)

논문에서는 B-tree 기반 역색인의 갱신 속도를 높이기 위해 '병합을 통한 갱신(merge update)' 최적화를 제안합니다:

병합을 통한 갱신 방식:

1. 새 문서의 단어 정보를 메모리 버퍼에 임시 저장
2. 버퍼가 가득 차면 수집된 포스팅 정보를 단어 기준으로 정렬
3. 정렬된 포스팅을 한꺼번에 B-tree에 병합

이 방식은 단어별로 한 번씩만 B-tree 탐색을 수행하므로, 문서의 모든 단어마다 개별적으로 B-tree를 탐색하는 나이브한 방식보다 디스크 접근이 크게 감소합니다.

수학적 분석: 논문에서는 병합 방식과 캐싱 방식의 성능을 수학적으로 비교 분석하였습니다. n개의 새 포스팅이 w개의 고유 단어로 구성될 때, 병합 방식은 캐싱 방식 대비 약 1/5 수준의 디스크 접근만으로 갱신을 처리할 수 있음을 보였습니다.

2.5 공간 최적화 (Space Optimization)

역색인의 공간 효율성을 높이기 위해 논문에서는 두 가지 방법을 제안합니다:

1) 그룹핑(Grouping)

같은 단어에 대한 포스팅 정보를 (단어, 빈도, 위치 리스트) 형태로 묶습니다. 이렇게 하면:

• 단어 정보의 중복 저장을 방지
• 단어당 한 번만 단어 정보를 저장해 약 50% 공간 절약
• 위치 리스트의 길이(빈도)도 함께 저장

2) 힙 파일(Heap File)

특히 자주 등장하는 단어의 위치 리스트가 B-tree 노드 크기를 초과하는 문제를 해결하기 위해 도입:

• B-tree 노드에는 (단어, 빈도, 포인터) 형태의 엔트리만 저장
• 포인터가 가리키는 별도의 힙 파일에 실제 위치 정보 저장
• 가변 길이 청크를 동적 할당하여 위치 리스트 관리

2.6 Pulsing

Pulsing은 B-tree 노드 공간을 더 효율적으로 활용하고 검색 성능을 향상시키는 기법입니다.

Pulsing의 주요 특징:

• 선택적 힙 파일 활용: 자주 등장하지 않는 단어들은 B-tree 노드 내에 직접 위치 정보 저장
• 임계값(threshold) t: 각 단어당 B-tree 노드 안에 저장할 수 있는 최대 위치 정보 수
• 효율적인 공간 활용: 빈도가 t 이하인 단어는 노드 내에만 저장해 힙 포인터 공간 절약
• 검색 성능 향상: 대부분의 단어는 B-tree 노드만으로 검색이 완료되어 디스크 접근 감소
• Hit ratio: B-tree 탐색만으로 검색이 완료될 확률, t가 클수록 향상됨

2.7 Delta Encoding

Delta Encoding은 위치 정보 자체를 압축하는 방법입니다. 역색인 검색에서는 대개 위치 정보를 순차적으로 읽어가므로, 각 위치를 이전 위치와의 차이(delta)로 표현하면 저장 공간을 절약할 수 있습니다.

Delta Encoding의 특징:

• 차이값 저장: 절대 위치 대신 이전 위치와의 차이(delta)를 저장
• 작은 숫자 활용: 인접한 위치 간 차이는 대개 작은 값이므로 저장 공간 절약
• 가변 바이트 인코딩: delta 값의 크기에 따라 1~4바이트로 가변적 저장
• 적용 범위: 힙 파일의 위치 리스트와 Pulsing의 노드 내 위치 리스트 모두 적용 가능
• 단점: 개별 위치에 대한 직접 접근이 어려워지므로 문서 삭제 연산에는 부적합

3. 결론

Doug Cutting의 이 논문은 Apache Lucene의 증분식 색인 기법의 이론적 토대를 제공했습니다. 논문에서 제안된 B-tree 기반 역색인의 최적화 기법들은 다음과 같은 측면에서 큰 성능 개선을 가져왔습니다:

• 병합을 통한 갱신: 디스크 접근 횟수 약 80% 감소
• 그룹핑: 색인 크기 약 50% 절감
• 힙 파일: 대규모 포스팅 리스트 관리 개선
• Pulsing: 검색 속도와 공간 효율성의 균형 유지
• Delta Encoding: 추가적인 공간 절약

이러한 기법들은 오늘날 Lucene을 비롯한 현대적인 검색 엔진에서 여전히 활용되고 있으며, 실시간 검색 성능과 대용량 문서 처리 능력을 위한 핵심 기술로 자리잡고 있습니다.

4. Lucene의 현대적 구현과 발전

현대의 Apache Lucene은 Doug Cutting의 초기 연구를 토대로 계속 발전해왔습니다. 특히 증분식 색인 기법은 더욱 세련되게 개선되었습니다.

4.1 Lucene의 현대적 색인 구성

현대의 Lucene은 Doug Cutting이 초기에 제안한 아이디어를 기반으로 하지만, 더욱 정교한 구현 방식을 채택하고 있습니다:

• 세그먼트 기반 구조: 색인은 여러 개의 독립적인 '세그먼트'로 구성되며, 각 세그먼트는 불변(immutable)입니다.
• 계층적 병합 정책: 세그먼트들은 크기에 따라 계층화되어 관리되며, 비슷한 크기의 세그먼트들이 병합됩니다.
• 압축 기술 개선: FST(Finite State Transducer)를 사용하여 사전(terms dictionary)을 효율적으로 압축합니다.
• 실시간 검색 지원: 커밋되지 않은 변경사항도 검색 가능한 Near Real-Time 검색을 지원합니다.

4.2 최신 최적화 기법

최신 버전의 Lucene에서는 다음과 같은 추가적인 최적화 기법들이 도입되었습니다:

• DocValues: 컬럼 형태로 데이터를 저장하여 정렬, 그룹화, 집계 연산을 효율적으로 처리
• Block KD-Tree: 다차원 범위 검색을 위한 효율적인 인덱싱 구조
• Roaring Bitmaps: 메모리 효율적인 비트맵 인덱스로 부울 쿼리 최적화
• Codec 아키텍처: 다양한 압축 및 인코딩 기법을 플러그인 방식으로 적용 가능

4.3 증분식 색인의 확장 사례

논문에서 제안된 증분식 색인 기법은 현대 검색 엔진에서 다양한 방식으로 확장되었습니다:

주요 확장 사례:

• ElasticSearch: 분산 환경에서의 샤딩(sharding)을 통한 수평적 확장 및 고가용성 제공
• Solr: 클라우드 모드에서의 자동화된 샤드 밸런싱 및 분산 코디네이션
• LinkedIn Galene: 소셜 네트워크의 실시간 프로필 업데이트를 위한 지연 전파 아키텍처
• Twitter Earlybird: 초당 수천 개의 트윗을 색인하면서도 실시간 검색을 제공하는 특화된 구조

5. 최종 결론

Doug Cutting의 "Optimizations for dynamic inverted index maintenance" 논문에서 제안된 증분식 색인 기법은 Apache Lucene의 핵심 기술이 되었으며, 현대 검색 시스템의 근간을 이루고 있습니다. 초기의 아이디어는 다음과 같이 발전해왔습니다:

증분식 색인 기법은 다음과 같은 이유로 현대 검색 시스템에서 필수적인 요소가 되었습니다:

1. 확장성: 대규모 데이터셋에서도 효율적인 색인 생성 및 유지 가능
2. 실시간성: 새로운 문서가 추가되더라도 빠르게 검색 결과에 반영
3. 자원 효율성: 색인 구축과 검색 처리에 필요한 컴퓨팅 자원 최소화
4. 분산 처리: 여러 노드에 걸쳐 색인 작업 분산 및 병렬화 가능

논문에서 제안된 기본 개념들은 모던 검색 엔진의 토대가 되었고, 클라우드 기반 서비스와 빅데이터 시대에도 그 관련성을 잃지 않고 있습니다. 특히 실시간 데이터 처리가 중요해진 오늘날, 증분식 색인 기법의 중요성은 더욱 커지고 있습니다.

참고 문헌:
Cutting, D., & Pedersen, J. (1989). Optimizations for dynamic inverted index maintenance. In Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 405-411).

Mendel Rosenblum, author of The Design and Implementation of a Log-Structured File system

LFS는 많은 synchronous random write를 작은 asynchronous sequential write로 전환하여 raw disk bandwidth를 100% 활용 하는것이 기본 개념입니다.

LFS는 쓰기 요청을 세그먼트 버퍼에 모으고 세그먼트 단위로 디스크에 Sequential write하여 Random write에서도 최적의 성능을 보여줍니다. 하지만 이러한 세그먼트를 활용하는 특성때문에 세그먼트 할당을 위한 공간을 확보하기 위한 Segment cleaning을 수행해야 합니다.

LFS의 등장 배경(Background)

Technology Trends

• CPU의 속도가 크게 증가한데 비해 디스크의 접근속도의 향상은 미미했습니다.
• 메모리의 용량이 증가함에 따라 읽기 요청을 효과적으로 처리할 수 있게 되었고, 쓰기 요청이 부각되었습니다.
• 디스크 기술 또한 비약적으로 증가하였지만 들어가는 비용에 비해 성능이 크게 증가하지 못했습니다.

Workloads Trends

• 일반 사무실과 공장은 작은 파일에대한 접근을 주로 하는 경향이 있습니다.
• 메인 메모리의 크기 향상은 더많은 파일 캐싱을 가능하게 하였고, 이로인해 읽기보다는 쓰기에 대한 Disk traffic이 부각되었습니다.

LFS - Purpose

• FFS가 read performance에 목표를 두었다면, LFS는 write performane를 향상시키는것을 목표로 합니다.
• LSF에서는 작은 파일 접근의 효율화에 집중하고 있으며, 큰 파일의 경우 하드웨어의 대역폭 향상에 의존합니다.

LFS - Design

• 메모리에 충분한 데이터가 모일때까지 버퍼링하였다가 버퍼링된 segment를 한번에 disk에 씁니다.
  • 메모리의 휘발성으로 인한 이슈가 존재합니다.
• Overwrite를 하지않고, Old copy가 앞에 남아있는 상태로 뒤에 공간을 할당합니다(out place update)
• 새로운 위치에 write하고 포인터를 바꾸기때문에 old file에 대한 GC(Garbage Collection)이 필요합니다.

Inode

위의 그림에서 배열 b[0]에 대해 수정이 발생하여 기존 데이터 블럭을 수정하지 않고 새로운 디스크 블럭 $D_{k,0}$ 를 쓰고, 마찬가지로 기존 inode를 수정하지 않고 새로운 inode를 생성하여 b[0]가 새로운 디스크 블럭 주소 위치를 가리키게 합니다.

$$E = mc^2$$

Inode map : LFS에서의 Inode는 log에 쓰여저 고정된 위치에 존재하지 않습니다

• LFS의 Out place update라는 특성으로 인해 inode는 고정된 위치에 존재하지 않습니다. 따라서 LFS는 각 inode의 위치를 파악하기 위해서 inode map이라는 자료구조를 사용합니다.
• inode map은 inode number를 입력값으로 가장 최근버전의 inode의 disk address를 출력합니다. 따라서 매번 inode가 디스크에 쓰여질때마다 imap또한 update되어 새로운 위치에 쓰여지게 됩니다
• 위의 그림과 같이 모든 새로운 정보를 쓰는 작업이 끝난 위치 바로 뒤에 imap이 쓰여지게 됩니다.

Check point region

• imap 또한 위치가 고정되지 않고 디스크의 여러곳에 위치하게 됩니다. 결국 파일시스템은 파일의 look up을 시작하기위해 정보를 담고있는 고정된 위치가 필요합니다.
• LFS는 check-point region(CR)이라는 고정된 위치에 가장 최근의 inode map의 정보를 저장하고 CR을 확인함으로써 imap의 위치를 파악할 수 있습니다.
• CR은 주기적(ex, 30초)으로 업데이트 되기 때문에 성능에 나쁜영향을 주지 않습니다.
• 정리하자면 CR은 imap에 대한 위치정보를 imap은 inode에 대한 위치정보를 inode는 파일에대한 위치정보를 담고 있습니다.

Directory

inode의 위치가 변경될 수 있지만 변경 사항은 디렉토리 자체에 반영되지는 않습니다. 대신 디렉토리가 동일한 이름 : inode 번호 mapping을 가지고 있는 동안 imap 구조가 업데이트됩니다. 따라서 간접적으로 LFS는 재귀 업데이트 문제를 방지합니다.

Segement

• 시간이 지나 log가 디스크의 끝에 도달하게 되면 파일이 삭제되고 덮어쓰기됨에 따라 가용공간이 여러 작은 조각들로 단편화 됩니다.
• LFS에서는 이를 Threading과 Copying으로 해결합니다.
  • Threading은 유효한 데이터들을 포인터들을 통해 연결시키는 방식입니다. 하지만 이러한 threading은 더많은 가용공간을 단편화시켜 큰 순차쓰기를 불가능하게 하고 이로인해 LFS는 기존 파일시스템에 비해 느려지게 됩니다.
  • Copying은 유효한 데이터를 Copy하여 한군데로 모아 큰 가용공간을 확보하는 방법입니다. 하지만 이러한 방법은 비용이 큽니다.
• Sprinte LFS는 Thread와 Copy두가지 방법을 모두 사용합니다.
  • 먼저 디스크를 큰 고정크기의 segment들로 나눕니다.
  • 각 segment에서는 처음부터 끝까지 순차적으로 쓰입니다.
  • 모든 유효 데이터는 segment가 다시 쓰여지기 전에 다른 segment에 copy됩니다.
  • 하지만 로그는 순차적으로 쓰여야 하므로 segment끼리 thread 되어 연결됩니다.
• Segment의 크기는 충분히 크게잡아 disk의 bandwidth를 모두 활용할 수 있도록 합니다.

Garbage Collection (Segement Cleaning)

• 데이터를 수정할때 LFS는 기존의 데이터위치에 쓰지 않고 디스크의 새로운 위치에 데이터를 씁니다. 이때 기존의 데이터는 garbage가됩니다.
• M개의 현재 존재하는 Segment를 compact하여 N개의 Segment로 만들고(N < M), 디스크의 N개의 Segment에 쓰기작업을 합니다. 이후 M개의 오래된 segment는 지워지고 후속 쓰기작업을 위해 사용될 수 있습니다.
  • 각 Segment는 마지막 쓰기작업을 기준으로 분류됩니다.
  • Segment cleaner는 백그라운드에서 동작합니다.

Determine Block Liveness

# A : address location of inode
# N : inode number
# T : offset
(N,T) = SegmentSummary[A];
inode = Read(imap[N]);
if (inode[T] == A) 
  // block D is alive
else
  // block D is garbage

• LFS는 block이 유효한지 판단하기 위해 해당 블럭의 위치 A를 SegmentSummary block을 통해 조회합니다.
• SegmentSummary block에서 inode번호 N과 offset T를 확인하고 imap을 통해 유효한 N의 위치를 알아내고 N을 읽습니다.
• 마지막으로 inode를 통해 파일의 T번째 블록의 위치를 알아내고 만약 A의 주소값과 일치한다면 live block, 일치하지 않으면 garbage block으로 판단합니다.

LFS는 파일이 수정되거나 삭제되면 imap의 version number를 증가시켜 기록합니다. 또 disk의 segment에도 version number를 기록하여 imap의 version number와 disk의 version number를 비교하여 추가적인 읽기 작업 없이 블럭의 liveness를 판단합니다.

Policy : Which Blocks To Clean

언제 GC를 수행할지는 시스템의 유휴시간 또는 주기적으로 하면 되기때문에 어려운 문제가 아니지만, 어떤 블럭을 clean할지는 결정하기 어려운 문제입니다.

Determining by Hot & Cold

Hot 세그먼트의 경우 자주 overwrite되기 때문에 오랫동안 기다렸다가 유휴공간이 많이 나오면 clean하는것이 좋습니다. 반면 Cold 세그먼트의 경우 유효 블럭의 개수가 많이 남아있을 확률이 높습니다. 따라서 LFS에서는 Hot세그먼트는 천천히 Cold세그먼트는 비교적 빠르게 GC을 수행합니다.

Log : Crash Recovery

LFS의 버퍼는 세그먼트에 쓰기작업을 한후 디스크에 세그먼트를 쓰는 작업을 합니다. Checkpoint Region(CR)은 세그먼트의 시작부분과 끝부분을 가리키고 각 세그먼트는 다음 쓰일 세그먼트를 가리킵니다. 이러한 segment쓰기 작업이나 CR쓰기작업시 충돌이 발생할 수 있습니다.

CR 쓰기작업에서의 충돌 해결

LFS에서는 CR업데이트를 원자적으로 수행하기 위해서 두개의 CR을 디스크의 양 끝단에 배치하고 번갈아 쓰기작업을 합니다. 그리고 타임스템프와 함께 헤더에 쓰고 CR부분에 쓰고 다시 타임스템프와 함께 마지막 블록에 써서 조심스럽게 CR을 업데이트 합니다. 만약 시스템 충돌이 발생할 경우 타임 스템프를 비교하여 시스템 충돌을 감지하고 가장 최근의 일관성있는 CR을 선택하여 일관성있는 CR쓰기작업을 가능하게 합니다.

Segment 쓰기작업에서의 충돌 해결

LFS는 30초 정도마다 CR을 쓰기 때문에 파일 시스템의 일관성 있는 마지막 스냅샷은 오래되었을 확률이 높습니다. 따라서 재부팅할 때 LFS는 체크포인트 영역, 가리키는 imap, 이후 파일 및 디렉토리만 읽어도 쉽게 복구할 수 있지만 마지막 몇 초 동안의 업데이트는 손실됩니다.

이를 개선하기 위해 LFS는 데이터베이스 커뮤니티에서 롤포워드(rollforward)라는 기술을 통해 이러한 세그먼트 중 많은 부분을 복구합니다. 기본 아이디어는 마지막 체크포인트 영역부터 시작하여 로그의 끝 부분(CR 내부에 존재)을 찾은 다음 이를 사용하여 끝까지 읽습니다. 그리고 다음 세그먼트에서 유효한 업데이트가 있는지 확인하고, 있는 경우 LFS는 파일 시스템을 업데이트하여 마지막 체크포인트 이후 작성된 많은 데이터와 메타데이터를 복구합니다.

그림 출처
Operating Systems: Three Easy Pieces, Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau (University of Wisconsin-Madison)