작년에 ICDE에서 발표된 WipDB라는 논문을 보면서 LSM 트리(log-structured merge tree, LSM Tree)라는 자료구조를 접했습니다. LSM 트리를 처음 접하는 것은 아니지만, LSM 트리라는 것이 워낙 많이 쓰이기도 하고, 이 논문과 다른 여러 논문을 읽을 때 도움이 될 것 같아 이 기회에 정리를 해보려고 합니다. 이 글에서는 LSM 트리가 무엇인지, 어디에 쓰이는지, 어떤 변형들이 있는지 간단하게 정리할 것입니다. 다른 배경지식에 흥미가 없으시면 바로 LSM Tree 섹션으로 건너뛰셔도 무방합니다.

Index

학부에서 인덱스에 대해 배우셨나요?

우리가 학부에서 배우는 데이터베이스 수업에서는 인덱스(index)에 대해서 배웁니다. 먼저 인덱스에 대해서 가볍게 짚고 넘어가고자 합니다.

데이터의 탐색

꼭 데이터베이스가 아니더라도, 어딘가에 데이터가 저장되어 있다면 우리는 그것을 효율적으로 탐색할 수 있어야 합니다. 우리가 데이터를 탐색하는 가장 쉽고 직관적인 방식은 처음부터 끝까지 전체 내용을 훑어보는 것이겠죠. 이것을 우리는 선형 탐색(linear search)이라고 부르며, O(n)의 실행 시간을 가집니다. 만약 데이터가 정렬되어 있다면, 그 값들을 절반씩 건너뛰며 탐색을 할 수 있습니다. 이 방법은 이진 탐색(binary search)이라고 부르고, O(log n)의 탐색 시간을 가지죠.

하지만 어느 쪽이든 장단점이 있습니다. 선형 탐색은 직관적이고 구현이 쉽지만, 데이터의 양이 많아질수록 비효율적이라는 단점이 있습니다. 이진 탐색은 선형 탐색에 비해 데이터의 양에 실행 시간이 영향을 덜 받지만, 전체 데이터가 정렬되어 있어야 한다는 전제조건이 붙습니다. 즉 이진 탐색 자체는 효율적일 수 있지만, 데이터의 순서를 정렬하고 유지하는 데에 추가적인 비용이 듭니다.

인덱스

데이터베이스와 같이 많은 양의 데이터를 다룰 때에는 탐색 알고리즘만으로는 부족할 때가 많습니다. 그래서 보통 색인, 즉 인덱스를 두죠. 인덱스를 저장하는 데에 소모되는 추가적인 메모리를 희생해 보다 빠른 탐색 시간을 목표로 하는 것입니다.

인덱스는 일반적으로 전체 데이터베이스의 크기보다 훨씬 작고, Key-Value의 형태로 데이터를 저장합니다. 여기서 Key는 우리가 인덱싱하고자 하는 attribute를 저장하고, Value는 해당 Key를 가지는 tuple이 메모리 상에 위치하는 포인터를 저장합니다.

인덱스를 사용할 때 성능 평가의 기준이 되는 요소는 다음의 다섯 가지가 있습니다.

• Access types: 어떤 종류의 access를 가장 효율적으로 처리하는지를 말합니다. 특정 값을 찾거나(point query) 특정 범위에 해당하는 값을 찾는(range query) 등의 종류가 이에 해당합니다.
• Access time: 특정 값 혹은 범위의 값을 탐색할 때 걸리는 시간을 말합니다.
• Insertion time: 새로운 값을 추가할 때 소모되는 시간을 말합니다. 값이 추가될 정확한 위치를 찾을 때 소모되는 시간과 값이 추가될 때 인덱스 구조가 변경되는 데에 소모되는 시간을 모두 포함합니다.
• Deletion time: 기존의 값을 삭제할 때 소모되는 시간을 말합니다. 삭제될 값의 위치를 찾을 때 소모되는 시간과 값이 삭제될 때 인덱스 구조가 변경되는 데에 소모되는 시간을 모두 포함합니다.
• Space overhead: 인덱스 구조를 유지함에 추가적으로 소모되는 메모리를 말합니다.

출처: Silberschatz, Abraham. “Indexing.” Database System Concepts, 7th ed., MCGRAW-HILL EDUCATION, Ney York, 2019, pp. 623–624.

당연한 말이지만, 이 모든 조건을 동시에 최대로 만족하는 인덱스는 존재하지 않습니다. Point query를 빠르게 처리할 수 있으면 range query를 효과적으로 처리하지 못하거나, insertion time이 적게 소모된다면 access time이나 deletion time이 많이 소모되거나 하죠. 아마 학부때 배우셨을 해시 인덱스(hash index)를 예로 들어보자면, 해시 함수 특성상 특정 값을 매우 빠르게 탐색할 수 있다는 장점이 있습니다. 우리가 찾는 키를 해시 함수에 통과시킨 후 출력되는 값에 해당하는 버킷(bucket)을 살펴보면 되기 때문입니다. 하지만 해시 인덱스는 범위 탐색에 매우 취약하다는 단점이 있습니다. 키 값이 이산적이고 범위가 작다면 그 키들을 해시 함수에 넣어 그 값들에 해당하는 버킷만 살펴보면 되기 때문에 그나마 시간이 덜 소모될 수 있지만, 대부분의 경우 그냥 선형 탐색을 하는 것이 보다 효과적입니다. 이는 비록 키 값이 연속적이더라도 해시 함수에 따라 전혀 다른 버킷에 배정될 수 있기 때문입니다.

이런 기본적인 이야기를 하는 이유는 이번 포스팅에서 다루는 LSM 트리를 사용하는 동기를 이해하기 위해서 필요하기 때문입니다. LSM 트리를 조금 다룬 뒤, 인덱스의 성능 평가의 기준이 되는 위 다섯 가지 지표로 다시 돌아와 왜 LSM 트리가 고안되었고, 어떤 분야에서 사용되는지를 설명하도록 하겠습니다.

B+ Tree

B+ 트리는 LSM 트리를 이해하는 데 있어 상당히 중요합니다. 원래는 이번 포스팅에 B+ 트리까지 한꺼번에 다룰 생각이었는데, B+ 트리를 얕게 다루자니 너무 내용이 빈약해질 것 같고 깊게 다루자니 너무 내용이 방대해질 것 같아 별도의 포스팅으로 내용을 분리하기로 했습니다. (링크) B+ 트리에 대해 잘 모르시거나 기억이 나지 않으시면 해당 포스팅을 참고하시는 것도 도움이 될 것입니다.

LSM Tree

B+ 트리의 큰 단점 중 하나는 write, delete 등의 업데이트 쿼리가 많을 때 그 성능이 크게 감소한다는 것입니다. 컴퓨터 구조 혹은 그와 비슷한 과목에서 메모리 계층 구조를 배우셨다면 아시겠지만, 컴퓨터가 메모리를 접근하는 시간과 디스크를 접근하는 시간에는 엄청난 차이가 존재합니다. 따라서 인덱스의 성능 향상을 위해서는 디스크 접근을 줄이고 메모리 내부에서 최대한 많은 일을 처리할 수 있도록 해야 하는데, B+ 트리는 많은 디스크 접근을 필요로 하기 때문에 이 부분에서 성능 저하가 발생하는 것입니다.

The log-structured merge-tree (LSM-tree)

출처: O’Neil, Patrick, et al. “The log-structured merge-tree (LSM-tree).” Acta Informatica 33.4 (1996): 351-385.

LSM 트리에 관해 가장 먼저 살펴볼 것은 이것을 처음 제시한 논문입니다. 1996년에 나온 논문으로, 벌써 30년 가까이 된 논문입니다. LSM 트리가 소개된 당시는 지금보다 메모리의 속도도 물론 느렸지만, 메모리의 가격이 훨씬 비쌌고 용량도 적었기 때문에 당시의 메모리는 지금 우리가 사용하는 메모리보다 훨씬 비싼 자원이었습니다. 따라서 당시 제안된 LSM 트리는 현재 널리 사용되는 LSM 트리와 많은 차이가 있습니다. 여기서는 간단하게 LSM 트리의 특징만 알아보고, 트리의 자세한 구성과 동작 방법에 대해서는 다음 섹션에서 깊게 다루도록 하겠습니다.

LSM 트리는 여러 개의 계층으로 구성되어 있는 트리입니다. 가장 상위의 계층을 Level 0으로 지칭하고 다음 계층부터 Level 1에서 Level L로 지칭합니다. 여기서 중요한 점은 다음의 세 가지가 있습니다.

1. 각 Level은 하나의 B 트리로 구성됩니다.
2. Level 0은 메모리 상에 위치하며(in-memory), Level 1 이하는 2차 저장 장치(secondary storage)에 위치합니다.
3. 각 Level에 저장되는 엔트리의 양은 특정 상수 T에 비례해 커집니다. 즉, Level 0에 x개의 엔트리가 저장된다면 Level 1에는 x⋅T개의 엔트리가, Level L에는 x⋅T^L개의 엔트리가 위치하게 됩니다.

특징적인 것은 각 Level이 하나의 B 트리로 구성된다는 점입니다. 앞서 말씀드렸다시피 당시에는 메모리가 비쌌기 때문에 이와 같이 각 Level을 트리로 구성해 보다 효율적으로 메모리를 사용하려는 노력을 했던 것인데요, 지금은 메모리가 훨씬 싸졌기 때문에 이와 같은 구조에도 차이가 생기게 됩니다. LSM 트리를 처음 제시한 이 논문에서는 훨씬 많은 내용이 포함되어 있지만, 현재 사용되는 LSM 트리와는 차이가 있기 때문에 이 논문에 대한 것은 이만 줄이도록 하겠습니다.

Modern LSM Trees

출처: Dayan, Niv, Manos Athanassoulis, and Stratos Idreos. “Monkey: Optimal navigable key-value store.” Proceedings of the 2017 ACM International Conference on Management of Data. 2017.

B 트리가 그랬듯이 LSM 트리고 나온 지 수십 년이 되었기 때문에 수많은 개선과 개량이 있었습니다. 저는 그 중에서 위 논문이 설명하는 LSM 트리를 기준으로 설명드리고자 합니다.

What it stores

LSM 트리는 흔히 말하는 Key-Value pair를 저장합니다. (앞으로 키와 값으로 지칭하도록 하겠습니다. ) 예를 들면 (사원번호, 이름)과 같은 쌍을 저장하는 것이죠. 물론 B 트리처럼 키와 포인터를 저장한 뒤 포인터가 기리키는 위치에 가변 길이 혹은 많은 양의 값을 저장할 수도 있습니다. 하지만 이것은 결국 본질적으로 같은 의미일 뿐더러 이야기를 복잡하게 할 뿐이기 때문에 여기서는 다루지 않겠습니다. 즉 LSM 트리는 키-값의 쌍을 저장한다, 라는 것만 알고 가면 됩니다.

The tree structure

LSM 트리는 기본적으로 L개의 계층(level)으로 이루어져 있습니다. 이 중에서 Level 0은 메모리 상에 일종의 버퍼로 존재하며(in-memory), Level 1 이하는 2차 저장 장치(secondary storage) 에 위치합니다. LSM 트리를 처음 제시한 위 논문과 비슷하지만 약간의 차이가 있습니다. 값비싼 자원이었던 메모리를 효율적으로 사용하기 위해 각 레벨을 하나의 B 트리로 구성했던 초기 논문과 달리 최근에는 각 레벨을 하나의 배열로 둔다는 것입니다. 메모리가 많이 싸졌기 때문에 굳이 트리를 구성하면서 추가적인 시간을 쓰지 않아도 되는 것이죠! (물론 2차 저장 장치에 비해서는 아직도 훨씬 비싼 자원이긴 합니다. ) 메모리가 싸지면서 생긴 구조상의 차이점은 이뿐만이 아닙니다만, 나머지는 뒤쪽에서 이어서 작성하도록 하겠습니다.

Level 0을 메모리 상에 위치시키면서 생기는 이점은 업데이트에 최적화된다는 것입니다. 여기서 업데이트란 삽입(inserts), 갱신(updates), 삭제(deletes)를 모두 포함하는 표현인데, 편의상 업데이트로 지칭하도록 하겠습니다. 왜 LSM 트리가 업데이트에 최적화되어있냐하면, 업데이트 쿼리가 들어오면 그냥 Level 0 버퍼에 추가만 하기 때문입니다. 업데이트에 대한 로그(log)를 남긴다고 생각하면 쉽습니다. 이미 버퍼에 위치하는 값에 대한 업데이트가 들어오면 그 값을 그대로 덮어씌웁니다.

만약 메모리 안에 위치한 Level 0 버퍼가 가득 차게 되면 어떻게 할까요? 이 때는 버퍼 내의 엔트리(entry)들을 키에 따라 정렬해 하나의 배열로 구성하고 Level 1으로 내려보냅니다. 이렇게 구성된 하나의 배열을 run이라고 부릅니다. 각 Level은 T개의 run을 저장할 수 있습니다. Level 1은 메모리 상의 Level 0 버퍼의 크기만한 run을 T개 저장할 수 있습니다. Level 1이 가득 차게 되면, 즉 Level 0에서 내려온 run을 T개만큼 저장했다면, Level 0에서 했던 것과 같이 Level 1에 저장된 값들을 키에 따라 정렬해 하나의 배열로 구성하고 Level 2로 내려보냅니다. 즉 Level 0 버퍼에 x개의 엔트리가 위치할 수 있다면 Level i에는 Level L에는 x⋅T^L개의 엔트리가 위치하게 됩니다. 이 기본적인 개념은 위의 첫 논문과 크게 다르지 않습니다.

The merge operation - Leveling and Tiering

앞선 설명에서, 한 Level이 최대로 수용 가능한 만큼 가득 찼다면 이 엔트리를 하나의 run이라고 불리는 정렬된 배열로 바꾸어 다음 Level로 내려보낸다고 했습니다. 그렇다면 해당 run을 받게 되는 하위의 Level은 이 새로운 run을 어떻게 처리하게 될까요?

이 run을 어떻게 처리하느냐에 따라 LSM 트리는 크게 두 종류로 나뉘어집니다. Leveling과 tiering이 그것입니다. 이 두 방식은 읽기와 쓰기 성능에 차이가 있습니다. 어느 방식이 어느 기능에 최적화가 되어있는지 살펴보도록 하겠습니다.

Leveling 방식은 Level i-1에서 하나의 run이 내려왔을 때, 해당 run을 Level i에 위치하던 배열과 즉시 병합 정렬(merge sort)을 합니다. 이 방식의 장점은 값을 읽는 작업에 최적화 되어있다는 것입니다. Leveling 방식을 사용해 각 Level에 하나의 배열만이 존재한다면, 특정 값 혹은 특정 범위의 값을 탐색하는 쿼리가 입력되었을 때 훨씬 효율적일 것입니다. 이미 정렬되어 있는 하나의 배열을 탐색하는 것이기 때문입니다. 이 방식의 단점은 값이 추가될 때 상대적으로 비효율적이라는 것입니다. Level i-1에서 하나의 run이 생성되어 다음 Level로 넘어갈 때마다 Level i에 위치한 run과 병합 정렬을 수행해야 하기 때문입니다.

Tiering 방식은 Level i-1에서 하나의 run이 내려왔을 때, 해당 run을 건드리지 않고 Level i로 내려보내기만 하는 것입니다. 이 방식을 사용한다면 Level i에는 최소 0개에서 최대 T-1개의 (Level i-1에서 만들어진 run 만큼의 크기의) 정렬된 배열이 존재할 것입니다. 이 방식의 장점은 값을 쓰는 작업이 상대적으로 효율적이라는 것입니다. Level i-1에서 하나의 run이 생성되어 다음 Level로 넘어갈 때 Level i에 위치한 run과 병합 정렬할 필요 없이 append하기만 하면 되기 때문에 추가적인 작업이 없어 효율적입니다. 이 방식의 단점은 값을 읽는 작업이 비효율적이라는 것입니다. 한 Level에서 특정 값 혹은 특정 범위의 값을 탐색한다면 최대 T-1개의 정렬된 배열을 탐색해야 하기 때문에 탐색이 비효율적입니다.

Additional Structures

앞서 메모리의 값이 저렴해지면서 한 Level의 구조를 메모리를 효율적으로 사용하는 B 트리에서 단순한 배열 구조로 바꾸었다고 말씀드렸습니다. 또한, 메모리가 싸지면서 추가적으로 생긴 구조적인 변화가 있다고 말씀드렸죠. 그 대표적인 예시가 지금부터 설명드릴 Fence Pointer와 Bloom Filter입니다. 쿼리 실행 시간을 줄이기 위해 메모리에 상주하는 자료구조를 추가한 형태입니다.

Fence pointer는 말 그대로 울타리 포인터입니다. 모든 run을 구성하는 각 disk page의 최솟값, 최댓값과 해당 page에 대한 포인터를 저장합니다. 마치 울타리처럼 disk page에 위치하는 값들의 양 끝 값을 알려주기 때문에 fence pointer라고 부르는 듯 합니다. 값을 탐색하는 쿼리가 입력되었을 때 이 fence pointer를 기준으로 해당 disk page를 탐색할 것인지를 판단할 수 있습니다. 만약 탐색하려는 값이 fence pointer의 범위를 벗어난다면 그 page를 건너뛰어도 무방합니다. 탐색을 할 때는 이 fence pointer의 배열을 이진 탐색하고, 그 결과 2차 저장장치에 대한 I/O를 줄일 수 있습니다.

다음은 bloom filter입니다. 상당히 간단한 자료구조인데, 꽤나 재미있는 친구이기 때문에 별도의 포스팅으로 분리했습니다. 간단하게 말하자면 특정 값이 존재하지 않는 것은 100% 확률로 알려주고, 특정 값이 존재한다는 것은 어느 정도의 오차를 두고 알려주는 자료구조입니다. 어느 정도의 오차를 돈다는 것은 즉 거짓 양성(false positive)이 있다는 것입니다. LSM 트리는 이런 bloom filter를 각 Level마다 하나씩 가지고 있습니다. 그래서 값을 탐색할 때 먼저 bloom filter를 살펴본 뒤 값이 없음이 판명된다면 해당 Level은 건너뜁니다. Bloom filter가 값이 없다고 출력하는 것은 확실하게 값이 없다는 의미이기 때문입니다.

이와 같이 fence pointer와 bloom filter를 사용하면 보다 효율적으로 값을 탐색할 수 있습니다. 저렴해진 메모리 덕분에 이런 자료구조들을 메모리에 상주시키기도 쉬워졌고, 이런 자료구조들을 사용해서 탐색하는 범위를 줄여나갈 때의 이득이 자료구조를 생성, 유지하는 것보다 효율적이기 때문입니다.

Conclusion

이것으로 LSM 트리에 대한 기본적인 내용들은 얼추 정리가 되었습니다. 간단하게 LSM 트리에 대해서 정리만 하려고 한 것이 생각보다 내용이 많아져서 포스팅이 너무 길어졌습니다. 이 포스팅으로 LSM 트리에 대한 개념이 어느 정도 잡혔으면 하는 바람입니다.