WiscKey: Separating Keys from Values in SSD-conscious Storage

LevelDB 나 RocksDB와 같은 LSM-tree 기반의 데이터베이스 구조에서, Write amplification (WA)를 줄이고 I/O bandwidth를 최대한 활용하기 위한 최적화 방안에 대해 제시한 논문이다. 추가적으로 최적화된 Compaction (CP) 혹은 Garbage Collection (GC)를 통해 CP/GC를 진행하는 동안 요청되는 일반적인 read/write의 성능에 최소한의 영향을 미치는 것도 목표로 하고 있다. 

key/value를 분리한다는 간단한 아이디어로 충분히 납득 가능할 방식을 통해 LSM-tree를 최적화 해서 좋은 아이디어라고 생각한다. 특히, 프로토타입 코드가 아닌 실제 LevelDB 코드를 수정해서 완전히 구현한 것은 매우 바람직하다고 생각하다. 

또한, 내 연구분야와 비슷한 내용이면서 현재까지 잘 사용되고 있지 않는 SSD의 병렬성을 활용하려고 하는 것은 매우 좋다고 생각한다. 

posix_fadvise()와 fallocate()의 활용을 요즘 내가 관심있는 연구와 비슷하고 실제로 이를 활용하는 DB가 얼마 없어서 많은 곳에서 사용되길 바라고 있었는데 아주 적절한 방식으로 사용하고 있는 것 같다. 

다만 단점으로는, vLog의 GC시 변경된 Value들의 위치에 대한 offset 저장을 LSM-tree에 반영을 해야 할텐데 어떤식으로 반영을 했고 그 정보를 저장하는 지에 대한 내용이 부족하다.

multi-thread보다 libaio를 사용해 보았으면 어떨까 하는 의문점도 남는다. 

그래도 여기저기 적용해볼만한 아이디어와 새로운 아이디어가 떠올랐으므로 나에게는 매우 좋은 논문으로 남을 것 같다.

아래는 논문 요약이다. 

1. 서론

기본 아이디어는 간단하다. Flash Memory 기반의 저장장치 (기본 SSD 포함 NVMe 등)가 대중화 되고 다양한 storage engine이 사용되고 있다는 요즘 논문에서 흔히 볼 수 있는 아주 일반적인 서론으로 시작한다. 특히나 LSM-tree 기반의 데이터 관리 기법이 여러 애플리케이션 및 데이터베이스에서 사용되고 있음을 말한다. 

LSM 특징은 다들 알다시피 데이터의 입력 처리를 random input/sequential input과 상관없이 모두 sequential write로 변경하는게 주된 목적이다. 가장 대표적인 사용처로는 구글의 BigTable과 LevelDB, 페이스북의 RocksDB, 야후의 PNUTS, Basho의 Riak, 기타 Cassandra, HBase 등을 언급하고 있다. 

기존의 LSM-tree 구조는 생략하도록 한다. (모두 다 잘 알것으로 파악, 혹은 wikipedia 참조)

SSD에 추가로 최적화 하기 위해 이 논문에서 주목한 점 중 하나는 SSD parallelism 이다. 이는 나중에 설명 하도록 한다. 

전체적인 서론 내용중 WiscKey 데이터베이스에 적용한 주된 아이디어는 Key-Value 구조에서 Key 와 Value의 분리된 저장공간 사용이다. 

Key 는 기존의 LSM-tree 로 관리를 하고 Value는 완전히 분리된 하나의 파일에 기록하는 방식이다. 

또한 multi-thread를 통해서 SSD의 병렬성을 최대한 활용하려는 모습을 보여주고 있다. 

2. 배경 지식

1) LSM-tree

기본 내용은 생략한다. 보통 Key-value 모두 LSM 구조로 관리를 하며 여러가지 이유로 인해 Log파일을 관리하여 Consistency를 보장한다. Redundant한 데이터들로 인한 CP/GC 작업은 항상 서로 인접할 레벨 사이에서만 발생하며, CP/GC 중에 다른 일반 요청도 수행할 수 있다. (Background 작업이 가능하다)

보통 Lookup (Point query) 에서는 안좋은 성능을 보여주며 (다중 레벨 파일을 뒤져야 하기 때문), Insert 위주의 워크로드나 Range Query 위주의 작업에서 좋은 성능을 보여준다. Insert/Update는 Sequential write로 모두 변환되므로 좋은 성능을 보이고 Range query의 경우 sorted된 데이터를 가져올수 있으므로 나쁘지 않은 성능을 보여준다. 

2) LevelDB

구글에서 개발한 대표적인 LSM-tree 기반의 key-value store이다. 홈페이지를 참고 

3. Motivation 

1) Write and Read Amplification 

 LSM의 구조상 Write시 CP/GC와 같은 이유로 많은 Write amplification이 일어나는것은 매우 당연하고, Read 시에도 다중 파일들에 같은 Key/value 값이 섞여 있으므로 불필요한 Read Amplification 도 발생하게 된다. 

또한 기존의 LevelDB와 같은 LSM-tree 기반의 스토어들은 SSD의 병렬성을 활용하지 못하고 있다. 

논문에서 단순 실험을 통해서는 병렬성이 32인 경우 4KB까지만 가도 최대 Bandwidth의 50% 가까이 활용이 가능함을 알 수 있고, 64KB 이상에 대해서는 거의 100%의 성능을 사용할 수 있는 것을 볼 수 있다. 

2) Fast Storage Hardware

SSD의 erase-before-write 특성에 비추어 볼때, Sequential write만 유발하는 LSM-tree는 이미 그상태로도 SSD에 적합하긴 하다. 그러나 Random read가 빠른 특성은 전혀 살리지 못하고 SSD의 병렬성이 고려되지 못하고 있다. 

또한 LSM-tree에서 가장 주된 성능 하락의 원인인 CP/GC가 발생할 경우 너무나 큰 Write WA로 인하여 SSD의 전체적인 성능및 수명을 감소시키는 문제가 있다. 

4. WiscKey 

메인 아이디어는 서론에서 설명한 것과 같이 LSM-tree로는 key만 관리를 하고 Value는 다른 파일에 분리해서 저장하는 방식의 key-value store이다. 실제 구현은 LevelDB의 소스코드를 변형하였다. 

1) 개발 목표

- Low write amplification

- Low read amplification

- SSD optimized

- Feature-rich API

- Rea;istic key-value size test

자세한 내용은 논문을 참조하면 되지만, 각각의 아이템에서 대충 내용은 짐작할 수 있을 것이다. 

2) Key-value separation 

LSM-tree에는 key와 value의 offset만 저장을 한다. Value는 분리된 value log (vLog) 파일에 append only 형태로 저장한다. 

Key/offset만을 저장하므로 LSM-tree의 크기가 훨씬 작아지게 되고, CP 발생시 옮겨지는 데이터의 양도 훨씬 적어지게 된다. 부가적인 효과로는 적은 양의 tree로 인해서 대부분의 tree가 in-memory 상에 올라와 있을 수 있다는 것이다. 보통 100GB의 DB를 생성시 2GB의 트리만 필요하게 된다고 한다. 이는 현대 PC에서 충분히 캐싱 가능한 크기이다. 

Delete의 경우도 LSM-tree에서 key만 삭제하면 되므로 매우 빠른 성능을 보인다. 사용하지 않는 value는 뒤에서 설명할 GC를 통해 제거한다. 

3) 병렬성 최적화 

SSD의 병렬성을 활용하기 위해서 단순히 32개의 thread를 활용하여 동시에 여러 read를 요청하는 것으로 처리하였다. 또한 예측 가능한 경우 prefetch도 하도록 구현하였다고 한다. 

4) Garbage Collection 

Key와 Value를 서로 분리된 공간에서 관리하므로 vLog 파일에서도 불필요한 공간이 생겨서 Garbage Collection (GC)를 수행해줄 필요가 생기게 된다. 효율적인 GC를 위하여 vLog에 value 저장시 (keysize, key, valuesize, value) 형태로 저장을 한다. GC는 단순하다. vLog로부터 스캔하면서 Key를 읽어서 LSM-tree에 존재하는 key인 경우 새로운 위치로 옮기고 그렇지 않을 경우 그냥 버린다. 

LSM-tree에서 key를 찾는 것은 모두 caching이 되기때문에 비용이 들지 않는다고 가정한것 같다. 

5) 기타 최적화 

- value를 쓰기 전에 buffering을 통해 small write를 방지한다. 

- vLog에 입력된 순서대로 key가 들어와 있으므로 LevelDB의 Log역할을 없애고 vLog가 이를 대체하여 사용될 수 있다. 

- posix_fadvise()와 fallocate() 시스템 콜을 통해 IO 패턴 및 공간 활용을 최적화 하였다.