NoSQL SSTable, LSM tree의 구조

1. 개념

DB는 일반적으로 두 가지로 나뉜다고 한다.
RDBMS는 오래 전부터 사용되던, redo log를 적은 뒤 데이터 파일을 수정하는 방식(WAL)으로 동작하고, NOSQL은 Amazon Dynamo, Google Bigtable에서 비롯된, RDBMS 외의 DB를 말한다. (link: 둘의 차이))
그 중 NOSQL(ex Cassandra)에서 주로 사용하는 SSTable, LSM tree에 대해 알아보겠다.

2. SSTable (Sorted Strings Table)

segments

SSTable은 "segment files"이다. 각 segment 안은 key로 정렬된 key-value들이 저장되있고, 한 segment 안에는 unique한 key만 가질 수 있다. 또한, 당연히 value가 여러번 바뀔 수 있으니까 내부적으로 value에 timestamp 칼럼을 추가로 갖고 있을 것이다. (link: ex Cassandra)

3. LSM tree

memtable

LSM tree를 사용하는 DB는 insert, update 요청이 들어오면 최신 segment에 기록하는게 아닌, 메모리 안의 red-black tree에 저장한다. 이를 memtable이라고 한다. memtable의 entry 개수가 일정 이상이 되면 segment file로 flush한다. 즉, 여러 요청을 single sequential write로 만든다.

write, read

write는 memtable의 최신 segment에 해당하는 red-black tree에 수행하면 된다. read는 우선 최신 segment순대로 각 segment 안에 주어진 key가 있는지 확인해야 한다. memtable에 있는 segment에서 찾아진다면 red-black tree라서 쉽게 찾지만, memtable에 없어서 file로 flush된 segment에서 찾는다면 좀 복잡해진다. 이 segment들에서 binary로 쓰여진 key-value들을 하나씩 읽어나가야 할텐데, 이를 빠르게 하기 위해서 sparse index를 메모리에 저장해놓는다. 추가적으로, 찾는 key가 segment 안에 있는지 빠르게 알기 위해서 bloom filter를 사용한다.

sparse index, bloom filter

sparse index는 말 그대로 띄엄띄엄 어떤 offset에 어떤 key가 있는지 저장하는건데, SSTable은 정렬되있으니, 내 key가 어느 offset 사이에 있는지 찾으면 그 부분만 읽으면 된다. 읽는게 sequential하게 되므로 SSTable과 아주 잘 들어맞는 index이다. sparse index는 segment마다 하나씩 있고, 메모리에만 존재한다.
bloom filter는 다음 알고리즘으로 동작한다. 1)기록된 key는 여러 개의 해시값으로 만들어서 각 해시값에 표시를 한다. 2)찾을 key는 방금 사용된 여러 개의 해시값으로 만들어서 각 해시값을 확인한다.
우연히 없는 key에 대한 해시값들이 다 표시되있어서 false positive가 발생할 수 있다. 즉, key가 없는데도 segment안을 뒤져야할 수도 있다.

delete

SSTable에서는 삭제도 삭제한다는 내용을 append 해야된다. 간단히 삭제할 key에 대한 value를 'tombstone'으로 write하면 해결된다.

compaction

segment file 개수가 너무 많아지면 여러 개의 segment를 하나의 segment로 합쳐야한다. 이를 compaction이라 하는데, 각 file에서 최신 key-value만 남긴 segment를 만들고, 기존 file은 지우는 작업을 말한다. 참고로, tombstone을 가진 key-value는 기록을 하지 않음으로써 삭제한다. compaction은 background process로 동작한다. 추가로, 위 내용은 major compaction이라 하고, memtable을 flush 하고 tablet log(쓰기 요청 내역)를 지우는 것을 minor compaction이라고 한다. HBase에서는 minor compaction이 최근에 flush된 파일 몇 개를 하나로 합치는 것을 말한다.

4. 중간 정리

1. write는 memtable에 기록한다. sparse index, bloom filter는 필요하면 업데이트한다.
2. memtable이 너무 커지면 SSTable segment로 flush한다.
3. read는 최신 segment(memtable 포함)부터 찾는다. 각 segment의 bloom filter를 먼저 확인하고, 없으면 다음 segment로 가고, 있으면 그 segment에 해당되는 sparse index를 확인한다. sparse index에 맞는 부분을 sequential read로 확인한다.

5. recovery

1. tablet log를 보고 memtable 재생성
2. segment들의 sparse index 생성

6. 특징

1. 빠른 쓰기가 가능.
2. 읽기가 메모리 밖 범위에서 RDBMS(B tree)에 비해 느림. B tree vs LSM tree(https://stackoverflow.com/a/8654903)
3. memtable flush, segments compaction, tablet log가 함께 디스크 대역폭을 공유하므로 많은 쓰기가 발생하면 갑작스럽게 성능이 떨어질 수 있음.(=성능이 안정적이지 못함.)
4. major compaction이 느리게 진행될 때, minor compaction이 빠르게 진행된다면 디스크가 다 차버릴 수 있음. 이런 상황은 보통 DB에서 관리하지 않음. 명시적인 모니터링이 필요함.

참고

1. https://yetanotherdevblog.com/lsm/
2. 책: 데이터 중심 애플리케이션 설계
3. https://dzone.com/articles/state-storage-engine