LSM Tree ( Log Structured Merge Tree )

Bitcask, MongoDB, Bigtable, Cassandra, InfluxDB및 SQLite4와 같은 최신 관계형 및 비관계형 데이터베이스에서 사용하고 있는 데이터 구조이다..

LSM-T 알고리즘은 DB에 데이터를 Condense하게 적재하면 데이터베이스에서 비용이 가장 많이 소모되는 디스크 엑세스 I/O를 줄여 최적화한 데이터구조이다. 하지만 추가적인 메모리가 소모되는 단점이 있다.

다음은 RDBMS에서 주로 사용하는 B+TREE와 LSM TREE의 비교이다.

 

https://www.cs.umb.edu/~poneil/lsmtree.pdf 

LSM 데이터 구조는 다음과 같은 원리로 데이터를 read/write한다.

1. 데이터를 write하면 인메모리 b-tree 데이터 구조에 데이터를 추가한다. - memtable

2. memtable의 크기가 임계값을 넘어가면 SS 테이블 파일로 디스크에 기록한다.

3. 데이터 read 요청을 하면 memtable에서 key를 찾는다. 해당 키에 해당하는 디스크에서 최신의 세그먼트를 찾아 읽는다.

0.  백그라운드에서는 지속적으로 컴팩션 과정을 통해 LSM의 데이터를 합치고, 정렬한다.

 

LSM 특징 3가지

1. Bloom Filter

데이터가 데이터베이스에 존재하느지 확률적으로 알아 낼 수 있는 자료구조. 데이터가 데이터베이스에 존재하지만 데이터가 없다고 판단하는 False Positive가 발생할 수 있음.

2. Leveled Compaction

SS테이블은 여러 Level로 구분한다. 단계가 높아질수록 테이블의 크기가 커진다. SS테이블은 일정한 임계값에 도달한 테이블을 합쳐 더 큰 테이블을 만들고, 일정할 Level에 도달하면 디스크로 데이터를 동기화시킨다.

3. Skip List

memtable에 데이터를 효율적으로 쓰고 읽기 위해 memtable을 skip list로 구현하는 경우가 있다.

- linked list와 비슷하게 다음 원소를 가르키는 포인터를 가지고 있다.

Linked list

linked list를 먼저 그려보면 위와 같다. 삽입/삭제는 앞, 뒤 노드만 수정하면 되기 때문에 빠르게 할 수 있지만 역시 검색이 문제다. 다음 원소를 가리키는 포인터만 따라가서는 당연히 속도가 좋지 않기 때문인데, 포인터를 여러 개 두는 방향으로 이를 개선한다.

 

Skip list

 

메모리를 추가할수록 속도가 빨라짐.

 

 

https://ohgym.tistory.com/10