Facebook의 Key-Value DB, "Rocksdb"

 

RocksDB 공식 Logo

3학년 하계방학 때 Facebook에서 개발한 Key-Value 저장소인 RocksDB에 대해서 분석했습니다.

교수님과 조교님의 지도 하에 여러 팀들이 각자 관심 있는 주제로 연구하고, 매주 세미나에서 공유하는 시간을 가졌는데 스스로 공부도 많이 했고 다른 팀의 발표도 들을 수 있어 유익한 시간이었습니다!

2달간 진행된 분석 스터디라 깊은 내용을 다루진 못했고, 이미 연구한 내용들은 README에 정리해뒀지만

회고하는 의미에서 정리해두려 합니다. 😁

 

 

 

 

RocksDB

RocksDB란 Google의 LevelDB를 기반(fork)으로 Facebook에서 개발한 Key-Value store이며, 서버와 같이 대용량 데이터 처리에 적합하고 SSD와 같은 스토리지에서 읽기/쓰기 성능을 최대한 이끌어 낼 수 있도록 개선되었습니다. 

또한 RocksDB는 익히 들어 알고 있는 관계형 데이터베이스(ex. MYSQL)와 다르게 NoSQL입니다. 

 

NoSQL?

여기서 NoSQL이란 관계형 데이터베이스의 반대, 비관계형 데이터베이스를 말합니다.

NoSQL은 SQL과 달리 정해진 스키마나 JOIN, 관계라는 개념이 없습니다. 따라서 데이터를 필요한 형식에 맞춰 저장할 수 있는 유연함이 보장됩니다. 그러나 데이터 중복이라는 문제점도 있는데, 이는 나중에 Database 포스팅에서 다시 정리할 예정입니다.

가장 중요한 것은 SQL이든 NoSQL이든 정답은 없다는 점, RocksDB는 NoSQL이라는 점입니다.

 

 

 

 

핵심 3가지

Memtable

Memtable은 Memory 내부에 존재하며 Disk의 SST file로 Flush 되기 전에 데이터를 저장하는 데이터 구조입니다. 쓰기 요청이 들어오면 반드시 Memtable에 우선적으로 쓰이며, 읽기 또한 RocksDB 특성상 가장 최신의 데이터부터 찾기 시작하므로 Memtable 먼저 확인합니다.

만약 Memtable이 가득 차면 데이터는 변경이 불가능 읽기 전용 Memtable(Immutable Memtable)로 Flush 됩니다. 만약 읽기 전용 Memtable도 가득 차면 Disk로 Flush가 됩니다.

 

 

SST files

Memtable이 가득차면 Disk로 flush 되는데, 가장 먼저 Level 0의 SST file로 가게 됩니다. SST file은 Key 순서에 따라 정렬이 되어 있는데, Level 0는 각 SST file마다 Key 값이 겹칠 수 있습니다만 다른 Level은 절대 겹치지 않습니다.

Disk의 레벨은 여러 개로 이루어져 있습니다. 레벨 0을 제외한 각 레벨은 하나의 정렬된 데이터의 연속입니다. 

또한 각 레벨의 내부는 여러 개의 SST 파일로 나누어져 있는데, SST 파일은 각각의 Key range를 갖습니다. 만약 찾고 싶은 Key값이 있다면 Key가 들어있는 SST 파일, 파일 내부의 Key range에서 이진 탐색(Binary search)을 합니다.

 

 

WAL

RocksDB에서는 WAL(Write Ahead Log) 방식을 이용하여 로그 파일을 작업합니다. Memtable의 내용이 Disk로 안전하게 flush 될 때까지 Memtable의 작업을 영구적으로 Disk에 보관합니다. 치명적인 장애가 발생한 경우에 기록해뒀던 WAL file을 이용하여 Memtable을 재구성합니다. WAL은 일정 부분 성능을 하락시키기도 하지만, RocksDB의 안정성을 위해 필수적입니다.

 

 

 

 

이 외

LSM Tree

RocksDB에서는 B Tree가 아닌 LSM Tree를 사용하고 있습니다. LSM는 in-place Update가 아닌 out-of-place Update로 Update를 할 때 이전 항목을 덮어쓰지 않고 새로운 위치에 Update 합니다. 때문에 Tree에 의한 공간 증폭(Space Amplification)이 발생합니다.

LSM 트리는 sequential write를 사용하기 때문에 B 트리에 비해 쓰기 속도가 상당히 빠르고, 쓰기 처리량이 많습니다.

그러나 읽기 측면에선 성능이 좋지 못한데, 최악의 경우는 없는 Key를 조회하려 할 경우가 대표적으로 그렇습니다. 

이러한 단점을 보완하기 위해 블룸 필터(Bloom Filter)를 적용하는데, 블룸 필터는 찾으려는 Key가 반드시 없다는 것을 보장해줍니다. 물론 블룸 필터가 Key 값이 있다고 할 때는 있을 수도 없을 수도 있지만, 만약 Key값이 없다고 한다면 반드시 없습니다.

 

 

Compaction

Compaction은 궁극적으로 해당 레벨에 들어 있는 데이터가 레벨의 최대 크기를 넘지 않도록 하는 것이 목표입니다. 레벨의 크기는 하위 레벨로 갈수록 증가하는데, default multiplier값은 10으로 Ln 의 크기는 Ln-1 * 10과 같은 형식으로 크게 증가됩니다. 

Compaction이 발생하는 조건은 L0의 파일 수가 일정 수준(Option: level0_file_num_compaction_trigger)을 넘었을 때 입니다. 이 경우 L0의 파일은 L1에 병합되는데, L0의 파일은 Key 값이 중첩될 수 있기에 모든 파일이 Compaction 대상으로 선택되어야 합니다.

대충 들어있는 데이터

그림과 같은 경우에서 L0의 파일이 level0_file_num_compaction_trigger를 넘었다고 하면, L1로의 Compaction이 일어납니다. 

L0의 모든 파일이 선택되어 L1의 파일과 병합됩니다. 

병합 이후에는 중복되는 Key들이 사라지고 L1으로 내려오게 됩니다. 이때, L0과의 병합으로 L1의 파일 수가 L1의 최대 크기를 넘으면 또 다시 Compaction이 발생합니다.

이 경우에선 중복되는 Key값이 없기 때문에 L0와 같이 모든 파일을 선택하지 않고 하나 이상의 파일을 선택합니다. 그리고 L2에서 이 파일과 중복되는 Key range를 갖는 파일들만 선택해 병합합니다.

이후 과정도 위와 마찬가지로 진행됩니다. 그림은 간략하게 L3까지 그렸지만 아래에 더 많은 레벨에서 활발하게 Compaction이 일어납니다.

 

 

 

---

다음엔 제가 속한 팀이 중점적으로 공부했던 3가지 증폭(write,read,space)에 대해 기록하려 합니다.

까먹지 않기 위해 기억나는 대로 적어봤는데, 혹시 틀린 부분이 있다면 꼭 말씀해주시면 감사하겠습니다. :-)