Introduction to LSM Trees: May the logs be with you 번역

https://priyankvex.wordpress.com/2019/04/28/introduction-to-lsm-trees-may-the-logs-be-with-you/

원문링크

Introduction to LSM Trees: May the logs be with you

소개

 

우리가 생각할 수 있는 가장 심플한 데이터 베이스의 구현은 어떤 것일까 ?

간단하게 파일의 끝에 append 하는 방법이 가장 그럴싸한(구현하기 쉬운) 설계일 것이다.

사실 이 바닥에서는 불변의(새로만들지 않는) append-only 데이터 구조가  실제로 가장 강력한 아이디어다. Appen 전용의 로그에 데이터를 저장하는 이 아이디어는 SSTable 과 LSM Tree 의 기본 개념이다. 카산드라와 RockDB 가 이런 개념의 DB이다.

 

What is an LSM Tree?

LSM Tree를 정의한다면 다음과 같다.

 

“Log Structured Merge Tree” 는 성능을 우선시하는 그래서 인서트와 업데이트 비율이 높은 성격의 데이터를 저장할 때 매력적인 데이터 스트럭쳐다.

LSM Tree는 2 혹은 그 이상의 레벨로 구성된 트리 같은 데이터 스트럭쳐다. 가장 간단한 버전은 C0와 C1 두 레벨로 구성된다.

 

C0 은 memtable 이라고도 불리는데 온전히 메모리에만 존재한다. memtable 은  AVL 같은 Balanced tree 구조를 이용해서 구현하고 key로 정렬된 key-value 형태로 저장한다. 모든 insert 와 update 는 C0 에 쓰여진다.

 

C1은 사이즈가 매우 크고 메모리가 아니라 디스크에 저장된다. C1은 빠른 key lookup 을 위해 해쉬 인덱스(Hash Index)를 동반한 불변 immutable 로그 세그먼트들로 구성된다.

C1은 일반적으로 SSTable 로 구현한다.

 

What are SSTables and how does it fit in the LSM tree?

 

log 기반의 데이터 스트럭쳐에서 , Insert 와 update 들은 로그 파일에 append 된다. 파일에 append 한다는 것이 매우 효율적이고 빠르다는 것이 main 아이디어이고 이 아이디어가  DB가 많은 양의 쓰기 작업을 감당할 수 있게 만들어 준다. 로그 파일들이 늘어감에 따라 이 파일들을 분할 (segment) 하는 것이 당연하다. 이래서 SSTable (String Sorted Table) 이 등장한 것이다.

 

SSTable 은 immutable 로그 세그먼트들에 문자열 기준으로 정렬되어 key-value 쌍 형태로 저장된다.

 

이런 구조이 주요 장점

1. Lookup 이 매우 빠르고 효율적이다. Hash Index가 없을 때도

2. Range query (범위 질의)가 가능함

 

만약 C0의 in-meomory 사이즈가 설정치를(일반적으로 몇 메가바이트)  초과하게 되면 SSTable 에 키로 정렬된 새로운 Segment로 Disk에 flush 된다

 

Overview of LSM Tree’s working:

지금까지 LSM 트리에 대한 모든 컨셉들을 살펴보았기 때문에 이제 각각의 조각들을 합쳐서 큰 그림을 볼 수 있게 되었다.

 

Inserting data into LSM Tree:

 

1. 쓰기 요청이 들어오면 메모리 상주  table 에 insert 하고

2. 메모리 상주 table 의 사이즈가 설정치를 초과하면 disk 에 flush 되고

3. 메모리 상주 table이 이미 정렬되어 있다면 새로운  SSTable segment 를 생성한다

4. old segment들은 주기적으로  merge 되서 disk space 에 저장되고  data 의 파편화를 최소화한다.

 

Reading data from LSM Tree:

1. 주어진 키가 먼저 메모리 상주  table에서 lookup 되고

2. 그런 다음에  hash index 를 사용하여 compaction 상태에 따라 하나 혹은 그 이상의 segment 에서  search 한다.

 

Sample use case in a system

LSMTree 설계에서 지적했듯이  트랜잭션 로그 라든가 사용자 이벤트 혹은 어떤 스트림 데이터를 자주 쓰는  workload가 많은 경우를 처리하기 위해서 좋은 방식이다.

 

예를 들어  LSM Tree  은 어떤 애플리케이션들이 생성한 이벤트들을 저장할 때 활용될 수 있다.

 

Advantages of LSM tree

 

1. LSM Tree 는 매우 높은  write 성능을 낼 수 있다

2. LSM Tree 는 더 잘 압축되어 사이즈가 훨씨 적은 로그 세그먼트 파일을 만들어 낼 수 있다.

 

Disadvantages of LSM Tree

1. 압축(Compaction) 과정이 현재 실행중인 read write 성능을 저하시킬 수 있다

2. Read/Write 처리량이 압축과정에서 소모되어 성능을 감소 시킬 수 있다.

3. 각각의 키가 동시에 여러 곳에  존재하기 때문에 키의 존재 여부를 체크할 때는 모든  세그먼트를 다 스캔해야 한다.

 

Conclusion

LSM Tree 는 단지 log 에  append 한다는 아이디어 기반한다. 전통적인 데이터 베이스 시스템에서 병목지점인 매우 높은  쓰기 처리량을 필요로 할 때 유용하다.