LSM Tree
Log Structured Merge Tree(LSM Tree, LSM 트리)를 살펴보기 전에 데이터 저장에 대해서 잠깐 생각해보자.
데이터 저장은 디스크와 같은 물리적 공간에 데이터를 기록하는 의미다. 시스템은 데이터가 필요할 때마다 디스크에 저장한 위치로 이동해 해당 데이터를 읽는다. 그러나 시스템이 데이터를 읽을 때마다 데이터를 저장한 위치를 알지 못하면 시스템은 디스크 전체 탐색해야 한다. 시스템이 디스크 전체를 탐색하는 과정은 많은 자원을 소비한다. 따라서 디스크 전체를 탐색하는 과정은 비효율적이기 때문에 시스템은 어떤 데이터를 어디에 저장했는지 따로 관리하는 것이 좋다. 데이터베이스는 어떤 데이터를 어디에 저장했는지 관리하는 시스템이다. 데이터베이스는 시스템의 데이터 수정, 추가, 읽기 작업을 효율적으로 지원하는 데이터 관리 시스템이다. LSM 트리는 데이터베이스 시스템이 데이터를 관리하는 방법 중 하나다.
Log Strutured
LSM 트리에서 Log Structured(로그 구조)는 로그를 저장하듯이 데이터를 저장한다는 의미다. 로그(Log)를 생각해보자. 로그를 저장할 때 이미 저장한 로그는 수정하지 않는다. 그리고 임의의 위치에 로그를 저장하지도 않는다. 시스템은 어떤 로그가 생기면 순서대로 차근차근 해당 로그를 저장한다.
간단하게 정리해보면, 로그 구조는
-
기존의 저장한 데이터를 수정하지 않는다.
-
새로운 데이터는 순차적으로 기존 데이터 뒤에 저장한다.
로그 구조에서의 데이터 추가, 수정, 그리고 읽기 작업이 어떻게 이뤄질 수 있는지 생각해보자. 저장하는 데이터는 하나의 유일한 키를 가진 키-값(Key-Value)데이터로 생각하자.
데이터 추가
데이터 추가 작업은 간단하다. 앞서 말했듯이 데이터베이스는 데이터를 순차적으로 파일의 맨 마지막 부분에 저장한다. 아래는 ID 값이 1인 데이터를 저장한 모습이다.
데이터 수정
데이터 수정 작업도 비슷하다. 로그 구조(Log Structured)의 특징을 기억하자. 데이터베이스는 기존 데이터를 수정하지 않고 파일에 맨 마지막 부분에 수정한 데이터를 저장한다.
데이터베이스가 데이터 파일에 name 값을 IPhone에서 IPhone14로 수정한 모습이다. 기존에 저장한 데이터를 수정하지 않고 로그를 저장하듯이 데이터베이스는 수정한 데이터를 파일의 맨 마지막에 저장했다. 이 모습을 보면 한 가지 의아한 부분이 있다. 키-값 데이터 중 키는 유일한 값이다. 그런데 위의 데이터 파일에는 하나의 키를 가진 두 개의 데이터가 존재한다. 기존에 있는 데이터를 삭제해주어야만 하나의 키를 가진 데이터가 하나만 남을 수 있다. 그러나 LSM 트리 구조를 사용하는 데이터베이스는 기존 데이터를 삭제하지도 않고 이를 해결했다.
데이터 읽기
데이터 읽기 작업에서 데이터베이스는 데이터 파일의 맨 마지막부터 처음까지 데이터를 탐색한다. 데이터를 탐색하는 과정에서 데이터베이스는 찾고자 하는 데이터를 발견하면 해당 데이터를 사용하고 더 이상 탐색을 진행하지 않는다. 로그 구조(Log Structured)의 특징을 보면 맨 마지막에 쓰여진 데이터가 가장 최근의 데이터를 보장하기 때문에 데이터베이스는 이전 데이터를 탐색할 필요가 없다.
데이터 추가와 수정 작업 이후, ID 가 1인 데이터를 읽는 과정을 보자. 데이터베이스는 데이터 탐색 방향으로 진행하면서 제일 먼저 발견한 데이터는 name 값인 IPhone14인 데이터다. 이 데이터 읽기 작업의 특징 때문에 앞서 걱정한 하나의 키에 두 개 이상의 데이터를 저장해도 문제가 없다. 데이터 파일에 데이터를 실제로 저장하고 있어도 더 이상 필요 없어진 데이터를 사용하지 않기 때문이다.
데이터 삭제
로그 구조(Log Structured)의 특징을 생각하면 임의의 위치에 있는 데이터를 삭제할 수 없다. 그러면 데이터베이스는 어떻게 데이터를 삭제할까.
데이터베이스가 ID 값이 1인 데이터 삭제를 한 모습이다. 이미 저장한 데이터를 삭제할 수 없기 때문에 삭제할 데이터에 대한 데이터를 파일 맨 마지막에 저장한다. 대신에 데이터 삭제를 나타내기 위해서 특정 표시와 같이 저장한다. 위에서는 D라는 표시와 함께 데이터 삭제를 나타냈다. 데이터베이스는 데이터를 읽을 때, D 표시를 가진 데이터를 만나면 해당 데이터는 삭제되었다는 것을 알 수 있다.
로그 구조(Log Structured)에서 데이터베이스의 데이터 추가, 수정, 읽기, 그리고 삭제 작업을 살펴봤다. 그렇다면 데이터베이스가 해당 구조로 데이터를 관리했을 때 문제점은 없을까.
데이터 수정(삭제) 작업이 자주 발생했을 때
로그 구조의 특징 때문에 데이터 수정(삭제) 작업은 기존의 데이터를 수정하지 않고 파일에 맨 마지막에 계속 데이터를 추가로 저장했다. 데이터 수정 작업이 자주 발생한다면 데이터베이스는 데이터를 계속해서 데이터 파일의 맨 마지막에 추가해야 한다. 이때 이전에 저장한 데이터는 더 이상 사용하지 않지만 그대로 데이터 파일 안에 있다. 데이터베이스는 데이터를 읽을 때 불필요해진 데이터를 계속해서 확인해야 한다. 이는 데이터베이스의 읽기 성능에 부정적 영향을 준다. 또 사용하지 않는 데이터가 쌓이면서 디스크인 물리적 공간을 차지하고 결과적으로 디스크 공간을 부족하게 만들 수 있다.
데이터의 볼륨 계속해서 커질 때
데이터 볼륨이 커지면 커질 수록 저장한 데이터도 많아진다. 수 많은 데이터에서 특정 데이터를 읽기 작업이 어떻게 진행할까. 앞서 살펴봤듯이 데이터 읽기 작업은 파일의 맨 마지막 부분부터 탐색을 시작한다. 이는 데이터가 많으면 많을 수록 탐색해야 할 데이터도 많다는 것이다. 운이 좋게 최근 데이터를 읽으면 괜찮지만 아주 오래 전에 저장한 데이터를 읽거나 저장하지 않은 데이터를 읽을 때에는 데이터를 다 탐색해봐야 한다. 데이터의 볼륨이 커지면 커질수록 데이터 읽기 작업은 느려질 수 밖에 없다.
Merge
머지(Merge) 작업은 사용하지 않는 데이터가 불필요하게 데이터 공간을 차지하고 있는 상황을 해결하는 방법이다. 데이터 수정 작업이 필연적으로 불필요한 데이터를 만들어낸다. 머지 작업은 앞서 저장한 데이터들을 머지하면서 가장 마지막에 저장한 데이터만 남기는 작업이다.
머지 전-후의 데이터 파일의 모습인다. ID 가 1인 데이터는 머지 이후에 데이터가 더 이상 존재하지 않는다. ID 가 2인 데이터는 불필요한 이전 데이터는 사라지고 마지막에 저장한 데이터만 남았다. 이 머지 작업은 불필요한 데이터가 계속 쌓이는 문제를 해결하고 물리적 공간을 확보할 수 있다.
머지 작업을 통해 앞서 살펴봤던 2가지 문제 중 하나를 해결할 수 있지만, 여전히 데이터 볼륨이 클 때의 읽기 작업의 성능은 개선할 수 없다. 어떻게 하면 읽기 작업의 성능을 해결할 수 있을까.
색인(Index)
데이터 읽기 성능을 확보하기 위해 가장 쉽게 접근할 수 있는 방법인 색인(Index)이다. 데이터베이스가 데이터를 저장한 위치와 데이터의 키 값을 따로 저장한다고 생각해보자. 데이터를 읽을 때 파일의 맨 마지막부터 읽지 않고 키 값과 같이 저장한 데이터 위치를 참조하고 파일의 해당 위치로 바로 탐색할 수 있다. 물론 데이터 추가, 수정, 그리고 삭제 작업에서 데이터베이스는 색인 데이터도 지속적으로 관리해야 하지만 읽기 성능을 확실히 높일 수 있다. 그런데 이 색인이 최선의 방법일까. 문제는 데이터 볼륨에 증가함에 따라 색인 데이터도 증가한다는 것이다.
Sorted String Table
데이터 볼륨에 따라 색인 데이터가 커지는 상황을 보완하기 위해 Sorted String Table(SSTable)를 생각해볼 수 있다. SSTable은 데이터를 키를 기준으로 데이터를 정렬하고 이를 저장하는 구조다. 단순히 문자열 데이터를 저장한다고 생각하자. 별도의 키를 두지 않고 해당 데이터가 키로 생각하자.
이전에 살펴봤던 색인은 각각의 키인 가방, 나라, 다람쥐, ..., 사진, 축구에 대한 위치를 다 기록하고 있어야만 한다. 그러나 데이터가 정렬되어 있고 가방, 사진에 대한 위치만 알고 있다면 어떨까. 다람쥐라는 데이터를 찾을 때에는 가방과 사진 사이의 있다는 것을 알 수 있기 때문에 데이터베이스는 가방 위치부터 탐색할 수 있다. 다시 말하자면, 데이터를 정렬했기 때문에 모든 키에 대한 색인을 만들지 않고 특정 키에 대해서만 색인을 만들 수 있다. 모든 키에 대한 색인을 가지고 있는 것보다 데이터 읽기 작업은 느릴 수 있으나 모든 색인을 저장하지 않는 만큼의 저장 공간은 확보할 수 있다. 그리고 여전히 데이터 파일을 전체 탐색하는 것이 아니라 찾고자하는 데이터와 가까운 위치에서부터 탐색할 수 있어 읽기 작업도 어느정도 빠르게 처리할 수 있다. 추가적으로 데이터를 정렬한 채로 저장했기 때문에 범위(Range) 조회도 가능해졌다. 그러나 데이터베이스가 데이터를 저장할 때마다 디스크에 정렬한 데이터를 저장하는 것이 효율적일까.
Memtable
데이터베이스가 디스크가 아닌 메모리에서 데이터를 정렬을 더 빠르게 할 수 있다면 어떨까. Memtable(멤테이블)은 데이터베이스가 데이터 추가, 저장, 삭제 작업을 메모리에 하도록 만들어준다. 이 멤테이블은 보통 이진 트리 구조를 기반으로 한 레드-블랙 트리 또는 AVL 트리로 구성한다. 그리고 데이터베이스는 멤테이블의 크기가 일정 수준 이상이 되거나 특정 주기마다 멤테이블의 데이터를 SSTable로 디스크에 저장한다. 그러나 이 멤테이블의 문제는 데이터를 메모리에서 관리하는 것이다. 시스템 이상으로 메모리에 있는 데이터가 날아가면 데이터 유실이 발 생한다.
Write Ahead Log
Write Ahead Log(WAL)는 멤테이블을 복구하기 위해 도입했다. 데이터를 추가, 수정, 그리고 삭제 작업을 진행할 때, 데이터베이스는 멤테이블에 저장하기 전에 해당 작업에 대한 로그를 남긴다. 시스템의 이상으로 멤테이블의 데이터가 사라졌다면 데이터베이스는 WAL를 통해 멤테이블을 복구할 수 있다.
데이터 쓰기(추가, 수정, 그리고 삭제)
데이터베이스는 데이터를 디스크에 바로 저장하는 것이 아니라 멤테이블에 저장한다. 데이터를 메모리에 있는 멤테이블에 저장하기 때문에 디스크에 저장했을 때보다 데이터베이스의 쓰기 작업 성능을 향상시킬 수 있다.
데이터 읽기
데이터 읽기 작업은 데이터베이스가 데이터 파일인 SSTable을 바로 탐색하는 것이 아니라 멤테이블을 먼저 확인한다. 그 다음 멤테이블에 해당 데이터를 찾을 수 없다면 SSTable을 탐색한다. SSTable을 탐색할 때에도 이전과 마찬가지로 가장 최근에 생성된 SSTable을 먼저 탐색한다. 최근에 생성한 SSTable부터 가장 오래 전에 생성한 SSTable까지 데이터를 탐색한다.
Compaction
데이터베이스는 멤테이블을 주기적으로 SSTable파일을 디스크에 저장한다. 이전과 살펴봤듯이 SSTable파일이 쌓이면 쌓일 수록 사용하지 않는 데이터가 발생한다. Compaction(컴팩션)은 이전에 얘기 했듯이 데이터베이스가 SSTable파일들을 합치는 과정이다. 다만 이전에 머지 과정은 최근 데이터를 남기도록 했지만, 이제는 최근 데이터를 남기면서 데이터를 정렬한 상태를 유지해야한다. 정렬을 위한 여러 알고리즘이 있지만 이미 정렬된 여러 데이터를 합쳐는 Merge Sort를 활용할 수 있다. 그러면 데이터베이스는 언제 컴팩션을 진행할까.
컴팩션을 언제 진행하는 방법에 따라 여러 전략이 있다.
Size-tiered Compaction Strategy
Size-tiered Compaction Strategy(STCS)는 비슷한 크기의 SSTable파일들을 같은 버킷(Bucket)에 저장한다. 동일 버킷 내에서 파일들의 크기가 허용 값보다 커질 때 데이터베이스는 컴팩션을 진행한다. Small 크기의 파일들 전체를 Medium 크기의 파일들 전체와 컴팩션을 진행한다.
그러나 이 STCS는 Space Amplification 문제점을 가지고 있다. Small 크기와 Medium 크기의 파일들을 컴팩션을 하는 과정에서 최소 2배의 디스크 볼륨을 사용한다. 컴팩션 작업을 위해 분산되어 있는 SSTable 파일들을 한 쪽으로 보내야하기 떄문이다.
Leveled Compaction Strategy
Leveled Compaction Strategy(LCS)는 위의 STCS 문제를 해결하기 위해 고안된 방법이다. 각각 레벨마다 고정된 크기의 작은 파일로 SSTable을 저장한다. 그러나 레벨이 클수록 저장할 파일의 개수가 증가한다. Level-0에서 2개의 파일을 저장한다면 Level-1은 4개, Level-2는 8개로 저장한다. 컴팩션은 각 고정된 크기의 파일이 커지면 해당 파일을 가져와 다음 레벨에 있는 파일들과 컴팩션을 진행한다. Level-1에 있는 한 파일이 고정 크기보다 커졌다면 해당 파일을 Level-2에 있는 파일들과 컴팩션한다. 다수의 파일들로 저장하지만 각 파일들마다 담당하는 키 범위가 있기 때문에 Level-2에 있는 전체 파일을 사용하지 않아도 된다. Level-1에서 넘어온 하나의 파일이 담당하고 있는 키 범위에 해당하는 파일들만 컴팩션을 진행한다. 그러나 LCS는 Write Amplification 문제점을 가지고 있다.
Bloom Filter
데이터 읽기 작업을 다시 생각해보자. 데이터 읽기 작업은 아래와 같이 진행한다.
- 멤테이블에서 데이터 탐색
- 멤테이블에 데이터가 없을 경우, SSTable에서 데이터 탐색
그렇다면 읽으려고 하는 데이터가 없다면 어떨까. 데이터가 없다는 사실을 모른채 멤테이블을 탐색하고 모든 SSTable을 탐색한다. 전체 SSTable 탐색하는 작업은 결코 빠른 작업이 아니다. 블룸 필터(Bloom Filter)는 저장한 적이 없는 데이터를 읽는 작업을 보다 빠르게 만든다.
블름 필터는 아래와 같은 역할을 한다.
- 데이터 탐색 시, 데이터 없음을 반드시 보장한다.
- 데이터 탐색 시, 데이터 있음에 대하여 false positive다. 데이터가 있다고 했지만 실제로는 데이터가 없을 수 있다.
따라서 저장한 적이 없는 데이터를 탐색하기 전에 블룸 필터를 거쳐 데이터가 없는 것을 미리 확인할 수 있다. 이로서 빠른 읽기 작업을 지원한다.