Log Structured Merged Tree - LSMTree

log structured merge tree. Cassandra, Elasticsearch 등 최신 DB들에서 많이 사용되며 Data를 immutable하게 관리할 수 있다. Disk의 Sequantial Read/Write 속도는 Memory 의 Random access에 비해서도 10배 가까이 빠른 성능을 내므로, LSM tree 는 B+ tree에 비해 더 높은 write workloads를 처리할 수 있다. Random write가 발생하는 b tree와 다르게, SSTable의 write는 항상 sequantial하기 때문이다. 그러나 매우 높은 write 을 처리해야하는 부하 상황에서 Lag이 생길 수 있으며 merge&compaction작업이 느려지면 그만큼 Read가 늘어나 퍼포먼스가 불안정해진다는 단점이 있다. 그에 비해  B+ Tree는 경험적으로 높은 read workload를 처리할 수 있다고 알려져있으며 높은 write workload에서도 lsmtree에 비해 처리 속도는 느리지만 안정적이다.

LSM의 Write

Log Structured Merge Tree는 Update에 대해 Update-in-Place가 아닌 Append 방식으로 수행한다. 분산된 Record들에 대해 Position을 찾은 후 Update 하는 과정을 제거함으로서 Write 성능을 개선한다. 실제로 Sequential I/O는 Random I/O 대비 Memory에서도 10배 가까이 빠른 성능을 보인다.

https://queue.acm.org/detail.cfm?id=1563874

Append Write는 Sequential Disk I/O 이다. Sequential Write을 사용하는 데이터 관리 구조는 Logging / Journaling / Heap file이 있다.이 구조들은 Sequential Write를 사용함으로서 실제 Write 성능이 이론적인 Disk Write 성능에 근접한다.그러나 이 구조들은 Random Read 또는 역 탐색에 대해서는 Write 작업에 비해 매우 낮은 성능을 보인다.

Bigtable paper에 기반한 Elasticsearch, Hbase, Cassandra, Riak, rocksdb 같은 최근 DB 들은 LSM tree를 사용하고 있다. LSM의 인덱싱 방식을 간단히 요약하면 아래와 같다.

1. 새로운 write이 in-memorry sorted balanced tree(red black tree, avl tree) 에 추가 된다. 이 인메모리 tree는 memtable이라고 부른다
2. memtable의 사이즈가 커지면, SSTable 파일로 disk에 flush 한다. SSTable도 memtable과 마찬가지로 정렬된 key-value 스토리지이다. SSTable가 디스크에 써지는동안 새로운 write는 memtable에 계속 추가된다.
3. read는 먼저 memtable을 찾아보고, 없으면 가장 최근의 SSTable부터 찾는다. SSTable은 정렬되어있기 때문에, range query를 하기에 쉽다
4. 뒷단에서는(in the background), 중복된 키를 SSTable를 찾아 가장 최근의 key를 가지게 된다. 이것을 compaction이라고 한다.
5. compacted sstable은 새로운 sstable로 합쳐된다. sstable이 정렬되어있기 때문에 sstable을 합치는 것은 꽤 빠르다.

경험적으로, LSM tree 는 높은 write workloads를 처리할 수 있고, B-tree는 높은 read workload를 처리할 수 있다. random write가 발생하는 b tree와 다르게, SSTable의 write는 항상 sequantial하기 때문이다.

b+tree는 durability를 위해 추가적인 파일인 Write Ahead Logs(WAL)를 쓴다. WAL은 파일에 append하는 것을 말한다. 이 WAL는 b-tree에 crash가 난 경우 consistent state를 복구할 때 쓴다. B-tree에 write한다는 것은 WAL에 먼저 쓴다는 것이기 때문에, 추가적인 작업이며 느린 write를 의미한다.

일반적으로 LSMtree에서 merge & compaction작업은 매우 빠르지만, 때때로 write 뒤에 lag을 발생시킬 수 있다. database에 매우 높은 write workload가 진행되고 있을때 일어날 수 있다. 느린 compaction & merging은 더 많은 SSTable을 읽게 하기때문에 역으로 read에 영향을 준다. 이 같은 LSMtree의 단점은 매우 높은 write throughput 시나리오에서 일어나고, 퍼포먼스가 불안정해진다. B-tree는 그에 비해 안정적인 퍼포먼스를 보인다.

 

참조: Fundamentals of System Design - Part 3