LSM-Tree에 대한 고찰

안녕하시와요
 
 
거의 4달 만에 블로그를 쓰는데.. 그동안 많은 일이 있었지만 줄줄이 쓰기에는 시간 아까우니 요약하자면.
 
그동안 그저 막연하게 백엔드 서버 개발자를 향했던 것에서 벗어나 대학원이라는 선택지를 열어두게 되었고,
이번 여름방학부터 DCCL(Data Centric Computing Lab)에서 학부 연구생으로 살고 있다.
 
7월 3일부터 출근을 시작했으니 연구 생활을 시작한 지 이제 한 달 반 정도가 지난 것인데
이전까지 교수님께서 매주 보내주시는 LSM-Tree 관련 논문들을 읽고 분석하고 있었고, 2주 전부터 주제를 받아서 연구를 진행하고 있다.
 
 
그동안 논문들을 읽으면서 들었던 생각은 다음과 같다.
1. 해결법들은 생각보다 거창하지 않다. (알고 있던 자료구조들을 응용 또는 새로운 protocol을 사용)
2. 여러 해결법을 잘 정리해두었다가, 무언가 해결해야 하는 문제가 생겼을 때 그 해결법들을 통해서 인사이트를 얻을 수 있을 것이다.
 
그렇다. 지금 진행하고 있는 연구에서 해결해야 하는 굉장한 문제가 있다.
 
따라서 이전에 읽었던 논문들에 대해서, 비록 지금 진행하는 연구와는 살짝 다른 주제이긴 하지만
저자들이 집중했던 문제점과 그의 원인, 그리고 해결 방법들을 한번 쭉 정리해 보고자 이 글을 작성한다.
(나만 알아볼 수 있을 정도로 축약해서 작성했기 때문에 양해 부탁쓰요)
 
 

PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees

---

VMware Research | PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees

 

문제점

high write amplification (쓰기 증폭 현상)

 

원인

at each level, all SST contain disjoint sets of keys
 
각 disk level에 저장되어 있는 SSTable들은 서로 겹치지 않는 key 범위를 가지기 때문에,
한 level이 꽉 차서 상위 level로 flush 되어야 할 때 compaction 연산이 발생한다.
 
→ 목표
- low write amplification
- high write throughput
- high read throughput

 

해결 방법

FLSM : Fragmented SSTables + Guards
 
Guards
- divide the key space into disjoint units
- SSTs in the guard could have overlapping key ranges
 
Guard에는 저장할 수 있는 key의 범위가 지정되어 있다.
그 범위에 해당하는 key 범위를 저장하고 있는 SST들은 바로 그 Guard로 flush 된다.
→ faster compaction으로 인해 이점을 얻는다. (simply add the SST in the next level)
 
e.g., 아래 그림에서 Guard 5는 key range : min 5 ~ max 374까지인 SST들을 저장할 수 있다.
 

 

한계점

1. sequential key들이 insert 될 경우 성능이 좋지 않다.
guard를 새로 생성하고, SST를 split 해야 하기 때문이다.
 
2. range query 성능이 좋지 않다.
한 Guard 내부에 있는 여러 SST들은 저장하고 있는 key 범위가 중복되기 때문에, 일일이 search 후 sort을 진행해야 하기 때문이다.
 
 

Redesigning LSMs for Nonvolatile Memory with NoveLSM

---

Redesigning LSMs for Nonvolatile Memory with NoveLSM | USENIX

 

문제점

1. serializaion & deserialization cost
2. only allows changes to in-memory data structure → compaction & logging cost
3. LSM hierarchy가 증가할수록 read-access latency도 증가한다.

 

원인

non-persistent in-memory structures

 

해결 방법

NoveLSM : LSM + non-volatile memory(NVM)
- persistent NVM-based MemTable (byte-addressable skip list)
- direct mutability of persistent state
- read parallelism
 
NVM : byte-addressable, persistent, fast
→ 비휘발성 층을 둠으로써 위의 문제들을 해결한다.
 

 
 

Revisiting Secondary Indexing in LSM-based Storage Systems with Persistent Memory

---

Revisiting Secondary Indexing in LSM-based Storage Systems with Persistent Memory | USENIX

 

문제점

LSM-Tree fails to efficiently support secondary indexing

 

원인

store a secondary index as another LSM-Tree (e.g., column family),
but secondary index require high search performance
 
- small key-value pairs, but LSM : heavy lookup
- there are multiple associated PKs, but LSM's out-of-place write pattern scatters them
- consistency problem by LSM's blind-write pattern, so validation is required

 

해결 방법

PERSEID : new persistent memory-based(= NVM) secondary indexing mechanism for LSM-based key-value stores
→ secondary indexing에 대한 새로운 구조를 고안하였다.
 

 
PS-Tree
log-structured + B+-Tree leaf nodes

 

 
hybrid PM-DRAM & hash-based validation approach
- seq #을 통한 validation (유효한 secondary index인지 검사)
- failure 발생 시 DRAM에 있던 것만 복구하면 된다.
 

 
non-index-only query optimizations on primary table searching
1. zone map that records seq # range (≈ seq # filter)
2. parallel primary table searching (with shared queue)
 
 

RubbleDB: CPU-Efficient Replication with NVMe-oF

---

RubbleDB: CPU-Efficient Replication with NVMe-oF | USENIX

 

문제점

compactions in replicated LSM-Trees (분산 key-value store)

 

원인

compaction is the bottleneck in LSM-Trees (RocksDB consumes 72% of the total CPU cycles on compaction)
but, compaction is conducted on each machine = redundant effort

 

해결 방법

RubbleDB : the first key-value store that takes advantage of NVMe-oF for efficient replication
→ 새로운 protocol을 사용하고, 그로 인해 발생할 수 있는 문제점들을 해결하였다.
 

 
main idea : primary node만이 compaction 연산을 진행, 그로 인해서 생성된 SST들을 secondary node들에게 전달한다.
but. additional CPU consumption occurs in secondary nodes
→ use NVMe-oF protocol
 

 

two challenges by using NVMe-oF

1. File system inconsistency
NVMe-oF protocol에서는 secondary node의 CPU를 거치지 않고, 심지어 file system layer 아래에서 command를 실행시킨다.
따라서 primary가 전달해 주는 new SST에 대한 경로는 secondary의 입장에서는 없는 경로이기 때문에 문제가 발생한다.
→ file pre-allocation (file pool + file map)
 

 
2. Application inconsistency
non-deterministic thread scheduling
→ LSM-Tree synchronization (MemTable ID + buffer / seq # + counter + buffer)