일단 써보기

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

Apache Lucene

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

Apache Lucene은 문서를 빠르게 색인하고 검색할 수 있는 기능을 제공하는데, 특히 증분식 색인(incremental indexing) 기법을 통해 문서가 추가될 때마다 효율적으로 색인을 갱신하는 방식을 사용하고 있습니다.

여기서 증분식 색인(incremental indexing) 기법은 기존 문서 집합에 새로운 문서가 추가될 때, 전체 문서를 다시 색인하지 않고 추가된 문서만 색인하는 방식입니다.

Lucene에서는 이를 위해 병합 색인(merge indexing) 기법을 사용합니다. 주요 특징은 다음과 같습니다:

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

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

Doug Cutting이 개발한 루씬에서 사용된 증분식 색인 기법은 그의 1990년대 후반 연구에 기반합니다. 이에 대한 자세한 내용은 다음 논문에서 확인할 수 있습니다.

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).

이 논문에서는 동적 색인 유지보수를 위한 최적화 기법에 대해 설명하고 있습니다. 특히 증분식 색인 구축 과정에서 발생하는 오버헤드를 최소화하기 위한 방법으로, 작은 색인들을 주기적으로 병합하는 기법을 제안하였습니다. 이는 Lucene의 증분식 색인 기법의 핵심 아이디어가 되었습니다.

논문 읽기

배경

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

그런데 이런 시스템에서 다루는 문서들의 집합, 즉 코퍼스(corpus)는 끊임없이 변화합니다. 새로운 문서들이 추가되기도 하고, 기존 문서들이 삭제 또는 수정되기도 합니다. 이렇게 빠르게 변화하는 코퍼스에 대해 자유 텍스트 검색 서비스를 제공하려면, 역색인을 실시간으로 갱신할 수 있어야 합니다.

가령 어떤 문서가 새로 추가되었다면, 해당 문서에 출현한 단어들을 곧바로 역색인에 반영해야 그 문서도 검색될 수 있을 것입니다. 만약 색인 갱신이 지연된다면 사용자는 검색 결과에서 누락을 경험하게 될 것입니다.

따라서 빠르게 변화하는 코퍼스를 대상으로 자유 텍스트 검색을 제공하기 위해서는, 역색인을 동적으로 갱신하는 것이 기본적으로 요구됩니다. 단순히 주기적으로 색인을 다시 만드는 정적 방식으로는 한계가 있기 때문입니다.

이 논문은 바로 이러한 배경에서, B-tree를 기반으로 역색인을 효과적으로 동적 갱신하는 방안을 연구한 것입니다. 제안된 여러 최적화 기법들은 역색인 검색 시스템의 성능과 확장성을 높이는 데 기여할 수 있습니다.

역색인(Inverted Indices)

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

예를 들어 "word1"이라는 단어가 문서1, 문서2, 문서3에 출현했다면, 이에 대한 역색인 엔트리는 다음과 같은 형태가 될 것입니다.

"word1" -> {1, 2, 3}

여기서 {1, 2, 3}이 "word1"의 포스팅이 됩니다.

이러한 역색인을 실제로 구현할 때는 다양한 성능 기준을 고려해야 합니다. 논문에서는 특히 다음 다섯 가지 기준을 강조하고 있습니다.

1. 색인 구축 속도 (index build speed)
2. 색인 검색 속도 (access speed)
3. 색인의 크기 (index size)
4. 동적 갱신의 용이성 (dynamics)
5. 확장성 (scalability)

한편 실제 포스팅에는 문서 식별자 외에도 추가적인 정보가 포함될 수 있습니다. 예를들어 단어가 문서 내에서 출현한 위치(offset)라든가, 출현 빈도(frequency) 같은 것이 될 수 있습니다. 다만 이는 역색인을 어떤 검색 알고리즘에 활용하느냐에 따라 달라질 수 있습니다.

역색인에서 가장 빈번하게 수행되는 연산은 특정 단어가 주어졌을 때 그 단어가 포함된 문서들을 찾아내는 것입니다. 이를 위해서는 단어를 키로 하여 색인에 접근할 수 있어야 합니다. 따라서 역색인은 단어들에 대해 정렬되어 있거나, 단어를 키로 하는 해시 테이블 형태로 구성되는 것이 일반적입니다.

이러한 역색인을 실제로 구현할 때는 다양한 요인들을 고려해야 합니다. 먼저 새로운 문서가 추가되었을 때 이를 색인에 반영하는 데 걸리는 시간, 즉 블록 단위 갱신 속도가 중요합니다. 새 문서의 색인 생성이 너무 오래 걸리면 검색 시스템의 실시간성이 떨어질 수 있기 때문입니다.

또한 사용자가 특정 단어를 검색했을 때 그 결과를 가져오는 데 걸리는 시간, 즉 접근 속도도 매우 중요한 성능 지표입니다. 사용자는 검색 결과를 빨리 받아보기를 원하므로, 색인 구조는 빠른 검색을 뒷받침할 수 있어야 합니다.

아울러 색인을 저장하는 데 드는 공간 비용, 즉 색인 크기도 무시할 수 없는 요소입니다. 색인이 지나치게 커지면 저장 공간 뿐 아니라 입출력 비용도 커지게 되므로, 적절한 압축이나 최적화를 통해 색인 크기를 적정 수준으로 유지할 필요가 있습니다.

한편 문서 집합이 동적으로 변한다는 점도 역색인 구현에 많은 영향을 미칩니다. 새 문서의 추가나 기존 문서의 삭제, 수정이 빈번히 일어난다면 이를 색인에 반영하는 증분 갱신 작업이 용이해야 합니다. 그렇지 않으면 색인 유지에 너무 큰 비용이 들 수 있습니다.

특히 문서 삭제의 경우, 해당 문서에 대한 모든 색인 항목을 빠짐없이 제거해야 합니다. 그런데 문서 내용을 알 수 없다면 색인 전체를 뒤져가며 관련 항목을 찾아내야 할 수도 있습니다. 따라서 가능하다면 문서 식별자와 문서 내용을 함께 관리하는 것이 색인 관리에 유리합니다.

문서 집합의 크기가 커짐에 따라 이러한 요소들이 어떻게 변화하는지, 즉 확장성도 역시 중요하게 고려해야 할 부분입니다. 문서가 많아질수록 색인의 크기가 커지고 색인 연산의 비용도 증가할 수밖에 없는데, 이를 얼마나 효과적으로 감당할 수 있느냐가 확장성을 좌우하기 때문입니다.

역색인을 설계하고 구현할 때는 이처럼 다양한 요인들을 복합적으로 고려해야 합니다. 단순히 검색 성능만을 최적화할 것이 아니라, 갱신 용이성, 저장 비용, 확장성 등을 두루 살펴가며 절충안을 찾아내는 것이 중요합니다.

Naive B-tree의 단점

B-tree는 디스크와 같은 2차 저장소에 저장되는 균형 잡힌 트리 구조입니다. 각 노드는 디스크 페이지로 표현되며, 하나의 노드에는 여러 개의 엔트리(키-값 쌍)가 담길 수 있습니다. 이때 하나의 노드가 담을 수 있는 엔트리의 수를 B-tree의 분기 계수(branching factor)라고 합니다.

B-tree에서는 이 분기 계수를 b라고 할 때, 노드 간 균형을 맞추기 위한 알고리즘을 통해 삽입, 검색, 삭제 연산의 시간 복잡도가 O(log_b N)으로 보장됩니다. 여기서 N은 B-tree가 담고 있는 총 엔트리의 수입니다. 또한 B-tree의 높이, 즉 루트 노드에서 리프 노드까지의 거리를 'B-tree의 깊이(depth)'라고 하는데, 이는 log_b N과 같습니다.

B-tree에 저장된 엔트리는 키 순으로 정렬되어 있으므로, 순차 접근 시에는 전체 엔트리를 키 순으로 읽어올 수 있습니다. 이때의 시간 복잡도는 O(N)이며, 대략 N/b번의 디스크 접근이 필요합니다.

B-tree의 분기 계수 b는 보통 100 정도로 크게 잡습니다. 이렇게 하면 100만 개의 엔트리를 담은 B-tree의 깊이는 3 정도가 되므로, 최대 3번의 디스크 접근으로 원하는 엔트리에 도달할 수 있습니다.

만약 B-tree의 일부 노드를 메모리에 캐싱한다면 접근 속도를 더욱 높일 수 있습니다. 예를 들어 루트 노드를 항상 메모리에 들고 있으면 모든 연산에서의 디스크 접근 횟수를 1만큼 줄일 수 있는데, 이때 b개의 엔트리를 메모리에 추가로 저장하는 대신 디스크 접근을 1회 아낄 수 있게 되는 셈입니다.

이를 일반화하면, 메모리에 C개의 엔트리를 저장할 수 있다고 할 때 B-tree 연산에 필요한 디스크 접근 횟수는 대략 log_b N - log_b C가 됩니다 (N ≥ C 인 경우). 즉, 캐시 크기를 늘리면 디스크 접근 횟수를 줄일 수 있습니다.

나이브한 B-tree 기반 역색인 구현에서는 (단어, 위치) 쌍을 B-tree의 엔트리로 삼습니다. 단어 단위로 인접하게 배치하므로 특정 단어에 대한 포스팅 리스트를 얻으려면 B-tree를 차례로 읽으면서 관련 엔트리들을 뽑아내면 됩니다. 이때 b개 엔트리마다 한 번씩 디스크 접근이 일어나게 됩니다.

그러나 새로운 문서의 색인을 만들 때는, 그 안의 모든 단어에 대해 (단어, 위치) 엔트리를 B-tree에 삽입해야 합니다. n개의 단어를 새로 색인한다면 대략 n * (log_b N - log_b C)번의 디스크 읽기가 필요할 것입니다.

문서 내용을 알고 있다면 기존 문서에 대한 포스팅을 제거하는 것도 같은 비용으로 가능합니다. 그러나 문서 내용을 모른다면 B-tree 전체를 훑어가며 관련 엔트리를 찾아 지워야 하므로 비용이 크게 증가할 수 있습니다.

이상의 내용을 정리하면, B-tree는 역색인을 구현하는 데 있어 접근 속도, 갱신 지원, 확장성 측면에서 장점을 가지지만, 엔트리 중복으로 인한 공간 낭비와 문서 단위 색인 갱신의 비효율성이 단점으로 지적될 수 있습니다. 이러한 단점을 극복하기 위해 몇가지 최적화 방안을 도입할 수 있습니다.

Speed Optimization

앞서 살펴본 나이브한 B-tree 역색인에서는 새 문서의 색인을 추가할 때 문서 내 모든 단어에 대해 (단어, 위치) 엔트리를 역색인에 삽입해야 했습니다. 이때 각 삽입 연산마다 B-tree의 루트에서부터 리프까지 탐색해 내려가야 하므로 디스크 접근이 많이 발생하게 됩니다.

이를 개선하는 한 가지 방법은 B-tree의 상위 노드들을 메모리에 상주시켜 캐싱하는 것인데, 이렇게 하면 삽입 시 디스크 접근 횟수를 줄일 수 있습니다. 그런데 논문에서는 이것보다 더 나은 방법을 제시하고 있습니다.

바로 새 문서의 (단어, 위치) 정보들을 메모리 버퍼에 임시로 저장했다가, 버퍼가 가득 차면 이를 한꺼번에 정렬하여 B-tree에 병합하는 것입니다. 이 '병합을 통한 갱신(merge update)' 최적화를 적용하면 삽입 연산에 필요한 디스크 접근을 대폭 줄일 수 있습니다.

n개의 새로운 포스팅 정보를 메모리 버퍼에 받아두면, 실제로는 중복을 제외한 w개의 단어에 대한 색인 엔트리만 B-tree에 삽입하면 됩니다. 이때 각 단어의 엔트리는 인접한 위치에 저장될 가능성이 높으므로, 삽입을 위한 B-tree 탐색 비용이 줄어듭니다.

한편 단어 w에 대한 포스팅 리스트의 길이를 f(w)라 하고, 이것이 Zipf 분포를 따른다고 가정하면 f(w)와 w 사이의 관계식을 세울 수 있습니다. 이를 바탕으로 n, w, N(전체 색인의 크기) 사이의 관계를 분석해 볼 수 있는데, 결론적으로 병합 방식이 캐싱 방식보다 디스크 접근 횟수가 훨씬 적다는 것을 보일 수 있습니다.

수식의 자세한 전개 과정은 후술하겠습니다만, 논문에서 주어진 예시를 보면 병합 방식이 캐싱 방식 대비 약 1/5 수준의 디스크 접근만으로 갱신을 처리할 수 있음을 알 수 있습니다. 이는 버퍼링과 배치 처리가 역색인 갱신 성능 향상에 매우 효과적임을 보여주는 사례입니다.

[수식의 전개 과정]
먼저 캐싱 방식을 적용했을 때 n개의 새 포스팅 정보를 삽입하는데 필요한 디스크 읽기 횟수의 기댓값은 다음과 같이 주어집니다 (수식 2).

X = n(log_b N - log_b C)

여기서 b는 B-tree의 분기 계수, N은 전체 색인의 크기, C는 캐시의 크기입니다.

한편 병합 방식에서는 n개의 포스팅이 w개의 단어에 대한 포스팅 리스트로 변환된 후 B-tree에 삽입됩니다. 이때 필요한 디스크 읽기 횟수의 기댓값은 다음과 같습니다 (수식 3).

Y = w(log_b N - log_b w)

이제 두 방식의 비용을 비교하기 위해 C = n 이라 가정합시다. 즉, 캐시의 크기와 새로 삽입할 포스팅의 수가 같다고 볼 수 있습니다. 그러면 식 (2)와 (5)로부터 다음이 성립합니다.

X = z ln z (log_b N - log_b (z ln z)) (6) Y = z (log_b N - log_b z) (7)

여기서 z는 n개의 포스팅이 포함하는 고유 단어의 수입니다.

식 (7)을 약간 변형하면,

Y = X / ln z + z log_b(ln z) (8)

입니다.

만약 X > Y 라면 식 (8)에 의해,

X > X / ln z + z log_b(ln z)

이고, 이를 정리하면

z(ln z - 1) > log_b(ln z)

을 얻게 됩니다.

식 (6)을 이용해 위 부등식의 좌변을 X에 관한 식으로 바꾸고 이를 정리하면 다음과 같은 부등식을 얻게 됩니다.

(ln z - 1)(log_b N - log_b(z ln z)) > log_b(ln z)

이를 다시 정리하면,

ln^2 z log_b N > log_b z + log_b(ln z) ln z

입니다.

부등식의 양변에 지수함수를 취하면,

N > z (ln z)^(ln z / (ln z - 1)) (10)

이 됩니다. 즉, N과 z가 부등식 (10)을 만족할 때 X > Y 임을 알 수 있습니다.

그런데 z ln z = n = C 이고 식 (2)가 성립하려면 N ≥ C 이어야 하므로, N > z ln z 임을 알 수 있습니다. 충분히 큰 z에 대해 ln z / (ln z - 1)는 1에 가까우므로, 갱신 연산의 경우 대체로 X > Y 라 예상할 수 있습니다.

논문의 예시에서는 b = 100, N = 1,000,000, z ln z = 10,000 일 때 z ≈ 1,383 이고,

X ≈ 10,000, Y ≈ 1,977

로 계산됩니다. 이는 식 (11)에 의해서도 확인할 수 있는데,

X = ln z (Y - z log_b(ln z)) (11)

이므로 Y 값으로부터 계산된 X 값은 대략 10,000에 근접합니다.

따라서 병합 기반 갱신이 캐싱 기반 갱신보다 디스크 접근 비용 측면에서 훨씬 효율적임을 이론적으로 확인할 수 있습니다. 논문에서는 이처럼 Zipf 분포의 특성을 활용하여 현실적인 최적화 기법의 우수성을 입증하고 있습니다.

Space Optimization

가장 단순한 형태의 역색인에서는 색인의 각 엔트리가 (단어, 위치) 쌍으로 구성되므로, 같은 단어에 대한 엔트리들 사이에 단어 정보가 중복되는 문제가 있습니다. 이를 해결하기 위해 제안된 방법이 '그룹핑(grouping)'으로, 같은 단어에 대한 포스팅 정보를 (단어, 빈도, 위치 리스트) 형태로 묶는 것입니다.

이렇게 하면 엔트리 하나당 단어 정보를 한 번만 저장하므로 중복이 제거됩니다. 다만 위치 리스트의 길이를 별도로 저장해야 하는 작은 오버헤드가 발생하는데, 이는 동시에 해당 단어의 문서 내 출현 빈도를 나타내는 데에도 활용될 수 있습니다.

단순 색인 방식과 그룹핑 방식의 공간 효율성을 분석해 보면, N개의 포스팅에 대해 전자는 2N 개의 저장 공간을 사용하는 데 비해, 후자는 W(2 + ln W) 개의 공간을 사용합니다 (W는 고유 단어 수). 보통 W ln W ≪ N 이므로 그룹핑이 더 공간 효율적임을 알 수 있고, 이는 대략 50% 가량의 절감 효과가 있는 것으로 나타납니다.

한편 그룹핑을 적용한 B-tree 역색인에서는 하나의 엔트리에 들어갈 수 있는 위치 정보의 수가 제한되는 문제가 있습니다. 극단적으로 출현 빈도가 높은 단어의 경우 위치 리스트가 B-tree 노드 크기를 초과할 수 있습니다.

이를 해결하기 위해 제안된 것이 '힙 파일(heap file)'입니다. B-tree 노드에는 (단어, 빈도, 포인터) 형태의 엔트리를 저장하고, 포인터가 가리키는 힙 파일에 위치 정보를 별도 저장하는 것입니다. 힙 파일 내에서는 가변 길이 청크를 동적 할당하여 위치 리스트를 저장하게 됩니다.

힙 파일을 사용하면 하나의 단어에 대한 색인 엔트리를 읽어들이는 데 최대 log_b W + 1 회의 디스크 읽기가 필요합니다 (트리 탐색 + 힙 파일 접근). 그리고 새로운 문서에 대한 색인을 추가할 때에는 힙 파일의 청크 크기가 딱 맞지 않을 경우 재할당이 일어날 수 있는데, 이에 따른 추가 비용은 무시할 만한 수준입니다.

결과적으로 N개의 새 포스팅에 대한 역색인 갱신 시간은 n(log_b w - log_b c + 1) 에 비례하게 되며, 앞서 소개된 병합 최적화 기법을 함께 적용하면 이를 더욱 개선할 수 있습니다.

힙 파일을 사용한 역색인의 공간 복잡도는 단순 그룹핑 대비 힙 파일 포인터 정보가 추가되는 것을 제외하면 거의 동일합니다. 즉 공간 효율성의 큰 저하 없이 B-tree 노드 크기 제한 문제를 해결할 수 있습니다.

Pulsing

Pulsing은 B-tree 노드 공간을 더 효율적으로 활용하기 위한 방법입니다. 앞서 힙 파일을 사용하면 모든 단어의 위치 정보를 B-tree 노드 밖으로 빼냈지만, 사실 대부분의 단어는 출현 빈도가 그리 높지 않아 노드 안에 충분히 저장할 수 있습니다.

따라서 Pulsing에서는 각 단어별로 B-tree 노드 안에 저장할 수 있는 위치 정보의 수를 제한합니다. 이 제한값을 초과하는 단어들에 대해서만 힙 파일을 사용하게 됩니다. 이렇게 하면 B-tree를 통한 직접 접근이 가능한 단어가 많아지므로 전반적인 검색 속도 향상을 기대할 수 있습니다.

Pulsing을 적용한 B-tree의 엔트리는 (단어, 총빈도, 노드 내 위치 수, 위치 리스트, 힙 포인터) 형태가 됩니다. 노드 내 위치 수가 제한값 이하일 때는 힙 포인터가 생략되어 공간이 절약됩니다.

Pulsing의 효과는 'hit ratio'로 분석할 수 있는데, 이는 검색 시 B-tree 노드만으로 처리 가능한 비율을 뜻합니다. Hit ratio가 높을수록 힙 파일 접근 없이 검색이 완료될 확률이 높아집니다. 노드 내 위치 수 제한값인 t를 적절히 설정함으로써 원하는 수준의 hit ratio를 얻을 수 있습니다.

• 각 단어마다 B-tree 노드 안에 저장할 수 있는 위치 정보의 수를 t개로 제한합니다. 이를 'pulsing threshold'라고 합니다.
• 어떤 단어의 색인 엔트리를 B-tree에 추가할 때, 그 단어의 총 출현 횟수가 t 이하면 위치 정보를 노드 안에 직접 저장합니다.
• 만약 이미 t개의 위치 정보가 노드 안에 있다면, 기존의 위치 정보를 모두 힙 파일로 옮기고 새 위치 정보도 힙 파일에 저장합니다. 이 과정을 'pulsing out'이라고 합니다.
• 즉, B-tree 노드 안에는 언제나 출현 빈도가 높은 단어들의 최신 위치 정보 t개만 저장되고, 나머지는 힙 파일로 overflow됩니다.
• 이때 B-tree 노드의 엔트리는 (단어, 총빈도, 노드 내 위치 수, 위치 리스트, 힙 포인터) 형태가 됩니다. 총빈도가 t 이하면 힙 포인터는 생략됩니다.
• 검색할 때는 먼저 B-tree를 탐색해 해당 단어의 엔트리를 찾고, 노드 안의 위치 정보를 읽습니다. 만약 총빈도가 t보다 크다면 힙 파일에서 나머지 위치 정보를 읽어옵니다.
• Pulsing의 효과는 'hit ratio'로 측정할 수 있습니다. 이는 B-tree 탐색만으로 검색이 완료될 확률입니다. Hit ratio는 threshold t에 의해 결정되는데, t가 클수록 hit ratio도 높아집니다.

Delta Encoding

Delta Encoding은 위치 정보 자체를 압축하는 방법입니다. 역색인 검색에서는 대개 위치 정보를 순차적으로 읽어가므로, 각 위치를 이전 위치와의 차이(delta)로 표현해도 무방합니다. 실제 위치 값 대신 delta를 저장하면 그 값이 상당히 작아지게 되어 압축 효과를 얻을 수 있습니다.

또한 delta 값을 저장할 때 크기에 따라 가변 바이트 수를 사용하면 공간 효율을 더욱 높일 수 있습니다. 이러한 인코딩을 적용하면 색인 크기를 크게 줄일 수 있습니다.

Delta Encoding은 힙 파일의 위치 리스트뿐 아니라 Pulsing의 노드 내 위치 리스트에도 활용 가능합니다. 다만 개별 위치에 대한 직접 접근은 어려워지므로 문서 삭제 연산 등에는 부적합하다는 단점이 있습니다.

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)