LSM의 Write
Log Structured Merge Tree에서는 Update에 대해 Update-in-Place가 아닌 Append 방식으로 수행합니다.
분산된 Record들에 대해 Position을 찾은 후 Update 하는 과정을 제거함으로서 Write 성능을 개선했습니다.
실제로 Sequential I/O는 Random I/O 대비 Memory에서도 10배 가까이 빠른 성능을 보입니다.
Append Write는 Sequential Disk I/O 입니다.
Sequential Write을 사용하는 데이터 관리 구조는 Logging / Journaling / Heap file이 있습니다.
이 구조들은 Sequential Write를 사용함으로서 실제 Write 성능이 이론적인 Disk Write 성능에 근접합니다.
그러나 이 구조들은 Random Read 또는 역 탐색에 대해서는 Write 작업에 비해 매우 낮은 성능을 보입니다.
일반적인 Random Read의 성능 개선 방안
낮은 Random Read 성능을 개선하기 위해서 사용할 수 있는 방법으로는 아래 4가지가 있습니다.
1. Sorted File : data를 정렬하여 file에 저장한 후 binary search 또는 index를 이용한 탐색을 수행합니다.
2. Hash : Hash 함수를 이용하여 data를 분류/보관합니다.
3. B+ : B+ Tree 파일 구조를 구성하여 탐색을 수행합니다.
4. External File : Data를 Logging 방식의 heap 구조로 유지하면서 추가적으로 hash 또는 tree index를 만듭니다.
위 방법은 Read 성능을 O(log(n))으로 확실하게 개선시켜 줍니다.
그러나 이 구조들은 내부적으로 순서(order)를 유지해 주어야 하는데 이 과정이 결국 Write 성능을 감소 시키게 됩니다.
(2),(3)번의 경우 Write 작업이 일어날 때 마다 hash table 또는 B+ index의 구조를 변경해야 하기 때문에 추가적으로 두 번의 I/O가 필요합니다.
(4)번의 경우 최신 값에 대한 index를 memory에 유지시키면서 한번의 Disk I/O로 탐색을 할 수 있도록 하면서 성능을 확보할 수 있습니다.
그러나 Scalablity의 측면에서 매우 많은 수의 작은 data들에 대해서는 index 사이즈가 data 사이즈에 비해 상당히 커지는 문제점이 있습니다.
LSM의 간단한 동작
LSM Tree에서는 batch 단위의 write가 정렬된 상태로 작은 사이즈의 파일에 저장됩니다.
그러므로 각 파일은 짧은 시간동안의 변경사항을 포함하고 있다고 할 수 있습니다.
이렇게 생성된 파일은 불변(Immutable)합니다. 새로운 변경사항은 새로운 파일에 쓰여기지 때문입니다.
LSM Tree에서 Read를 할 때는 모든 파일을 검사합니다.
그렇기 때문에 주기적으로 파일을 병합(Merge)시켜주는 작업이 수행되면서 파일의 수를 줄여줍니다.
LSM 더 들여다보기
Write
새로운 data들은 작은 사이즈의 파일에 저장되기 전에 빠른 write 성능을 위해 memory buffer(Memtable)에 추가됩니다.
MemTable은 보통 tree 또는 skiplist(leveldb) 구조로 구성되며 입력된 data의 순서를 유지하고 있습니다.
(데이터 복구 용도로 Memtable의 복제본을 Disk에 저장합니다. 주로 저널링으로 구현됩니다.)
MemTable의 일정 사이즈가 넘어서면 디스크로 플러시되며 Sequential Write를 통해 파일이 생성됩니다.
이 파일은 위에서 언급한대로 정렬되어 있고 불변합니다. 키가 중복되는 Entry는 최신 Entry의 값을 사용합니다.
Data 입력이 많아질수록 중복되는 Entry가 늘어나며 중복을 제거하기 위해 주기적으로 Compaction을 수행합니다.
Compaction은 여러개의 파일을 병합하면서 파일의 개수를 줄이고 중복된 키나 삭제된 키를 제거합니다.
파일 내부가 정렬이 되어 있기 때문에 병합은 꽤 효율적으로 이루어 집니다.
Read
Data를 읽을 때는 최신 값들이 존재하는 MemTable을 먼저 탐색합니다.
탐색에 실패했을 경우 Disk의 파일들을 최신 순으로 검사합니다.
그러나 파일의 수에 비례하여 시간이 걸리는 문제가 있습니다.
이를 보완하기 위해 파일 인덱스나 파일의 블록 인덱스를 만들어 메모리에 캐싱해 놓는 방법도 있습니다.
더 나아가 블룸 필터를 사용하여 탐색 시간을 줄여보려는 방법도 존재합니다.
하지만 이것은 Read 성능을 올려주는 대신 Write의 오버헤드를 증가시킵니다.
그러나 상대적으로 매우 낮은 Read 성능을 끌어올리기 위해 Write 성능을 약간 희생하는 것은 나쁘지 않습니다.
Basic Compaction
'CS > Data Structure' 카테고리의 다른 글
| levelDB Diagram (0) | 2021.03.13 |
|---|