RocksDB 기본
1. 서론
RocksDB는 Facebook에서 시작된 오픈소스 데이터베이스 개발 프로젝트로, 서버 워크로드와 같은 대용량 데이터 처리에 적합하고 빠른 저장장치, 특히 플래시 저장장치에서 높은 성능을 내도록 최적화되어있다. RocksDB는 C++ 라이브러리 형태로 제공되고 key-value 저장 방식을 취한다. 그리고 원자 읽기/쓰기(atomic read/write)를 지원한다.
RocksDB는 메모리, 플래시, 하드디스크, HDFS 등 다양한 환경에서 실행 가능하고, 그에 따라 환경 설정을 유연하게 조정할 수 있다. 그리고 다양한 압축 알고리즘과 제작 지원, 디버깅을 위한 툴들도 제공한다.
RocksDB는 오픈 소스 프로젝트인 LevelDB를 기반으로 하고, Apache HBase에서도 아이디어를 채용했다. 최초 코드는 LevelDB 1.5 버전에서 fork 되었다. 또한 RocksDB 전에 Facebook에서 개발된 코드와 아이디어를 토대로 개발되었다.
2. 가정과 목표
성능(Performance):
RocksDB의 주요한 디자인 포인트는 빠른 저장장치와 서버 워크로드에 적합해야 한다는 것이다. 즉, flash나 RAM이 제공하는 높은 읽기/쓰기 성능을 완전히 활용할 수 있어야 한다. 그리고 효율적인 포인트 검색(point lookup)은 물론 범위 스캔(range scan)도 제공해야 한다. 또한 랜덤한 읽기가 많은 워크로드, 업데이트가 많은 워크로드, 이 둘을 합친 워크로드를 지원하기 위해 설정 가능(configurable)해야 한다. 마지막으로, Read/Write/Space Amplification을 쉽게 튜닝할 수 있는 아키텍처를 제공해야 한다.
제작 지원(Production Support):
RocksDB는 제작 환경에서 배포 및 디버깅을 돕는 도구와 유틸리티가 기본적으로 내장되도록 설계되어야 한다. 그리고 대부분의 주요 매개 변수(parameter)는 다른 하드웨어의 다른 응용 프로그램에서도 사용할 수 있도록 완전히 조정 가능 해야한다.
하위 호환성(Backward Compatibility):
RocksDB를 최신 버전으로 업그레이드 할 때 기존 버전을 변경할 필요가 없도록, 최신 버전은 이전 버전과 호환되어야 한다.
3. High Level Architecture
RocksDB는 key와 value가 임의의 byte stream인 내장형 key-value 저장 방식을 취한다. RocksDB는 모든 데이터를 순서대로 정렬해 구성하며 일반적인 작업(operation)은 Get(key), Put(key), Delete(key), Scan(key)이다.
RocksDB의 세 가지 기본 구조는 memtable, sstfile 그리고 logfile 이다. memtable 은 메모리에서의 데이터 구조다. 쓰기(write) 요청이 들어오면 메모리의 memtable 에 먼저 써지고 그 다음에 선택적으로 logfile 에 써진다. logfile 은 저장장치에 순차적으로 쓰이는 파일이다. memtable 이 가득 차면, memtable 은 저장장치의 sstfile 에 플러시(flush)되고, 해당 memtable 과 관련된 logfile 은 삭제된다. 그리고 sstfile 의 데이터는 key를 쉽게 찾을 수 있도록 정렬되어 있다.
sstfile 의 기본 포맷은 여기에 자세히 설명되어 있다.
4. 특징
Gets, Iterators and Snapshots
Key와 value는 순수한 byte stream으로 이루어져있다. Key 또는 value의 크기에는 제한이 없다. Get API는 어플리케이션이 데이터베이스에서 하나의 key-value를 가져올 수 있도록 한다. MultiGet API는 어플리케이션이 데이터베이스에서 여러 개의 key를 검색할 수 있게 한다. MultiGet 호출을 통해 반환된 모든 key-value는 서로 consistent하다.
데이터베이스의 모든 데이터는 논리적으로 정렬되어 있다. 어플리케이션은 key의 전체적인 순서를 결정하는 key 비교 method를 지정할 수 있다. Iterator API는 어플리케이션이 데이터베이스에서 RangeScan을 할 수 있게 한다. Iterator가 특정 key를 찾으면, 어플리케이션은 그 시점부터 한 번에 key 하나씩 스캔을 시작할 수 있다. Iterator API는 데이터베이스의 key를 역순으로 탐색하는 데에도 사용될 수 있다. Iterator가 만들어지면, 데이터베이스의 일관된 특정 시점보기(consistent-point-in-time)가 만들어진다. 따라서, Iterator를 통해 반환된 모든 key는 데이터베이스의 일관된 뷰에서 가져온 것이다.
Snapshot API는 어플리케이션이 데이터베이스의 특정 시점(point-in-time) 뷰를 생성할 수 있게 한다. Get 및 Iterator API는 특정 스냅 샷에서 데이터를 읽어오는 데에 사용할 수 있다. 어떤 점에서, Snapshot과 Iterator는 둘 다 데이터베이스의 특정 시점 뷰를 제공하지만, 그들의 구현 방식은 다르다. 단시간 스캔은 iterator를 통해 수행하는 것이 가장 좋으며, 장기간 스캔은 스냅샷을 통해 수행하는 것이 좋다. Iterator는 데이터베이스의 특정 시점 뷰에 해당하는 모든 파일에 대한 참조 횟수(reference count)를 유지한다. 이 파일들은 iterator가 릴리즈 될 때까지 삭제되지 않는다. 반면 스냅샷은 파일 삭제를 막지 않는다. 대신 compaction 프로세스는 스냅샷의 존재를 인식하고, 기존 스냅샷에서 볼 수 있는 키들은 절대 삭제하지 않는 것을 보장한다.
스냅샷은 데이터베이스가 다시 시작될 때까지 유지되지 않는다. 서버를 다시 시작하여 RocksDB 라이브러리를 다시 로드하면 기존의 모든 스냅 샷이 해제된다.
Prefix Iterators
대부분의 LSM 엔진에서는 모든 데이터 파일을 탐색해야하므로 효율적인 RangeScan API를 지원할 수 없다. 그러나 대부분의 어플리케이션들은 데이터베이스에서 key 범위에 대해 완전히 랜덤한 스캔을 하진 않는다. 일반적으로 어플리케이션들은 key-prefix(접두어) 내에서 스캔한다. RocksDB는 이 점을 장점으로 사용한다. 어플리케이션은 prefix_extractor를 구성하여 key-prefix를 지정할 수 있다. RocksDB는 이를 이용해 모든 key-prefix에 대한 bloom을 저장한다. Prefix(ReadOptions를 통해)를 지정하는 iterator는 이러한 bloom bit를 사용하여, 지정된 key-prefix를 가진 key가 없는 데이터 파일을 탐색하는 것을 방지한다.
Updates
Put API는 하나의 key-value를 데이터베이스에 삽입한다. Key가 이미 데이터베이스에 존재하면, 이전 값을 덮어쓴다. Write API는 여러 개의 key-value를 원자적으로(atomic하게) 데이터베이스에 삽입한다. 데이터베이스는 하나의 Write 호출에 해당하는 모든 key-value들이 데이터베이스에 삽입되거나 아니면 아무것도 데이터베이스에 삽입되지 않을 것을 보장한다(All or Nothing). 해당 key가 이미 데이터베이스에 존재하면, 이전 값은 덮어 쓰여진다.
Persistency
RocksDB에는 트랜잭션 로그가 있다. 모든 Puts는 memtable이라는 메모리 내 버퍼에 저장될뿐만 아니라 선택적으로 트랜잭션 로그에 쓰여진다. 각각의 Put은WriteOptions를 통해 설정된 플래그 집합을 가지는데, 이는 Put을 트랜잭션 로그에 삽입해야 하는지에 대한 여부를 지정한다. 또한, WriteOptions은 Put이 커밋되기 전에 sync 호출이 트랜잭션 로그에 발행되어야 하는지에 대한 여부도 지정할 수 있다.
내부적으로 RocksDB는 트랜잭션들을 함께 묶어서 트랜잭션 로그에 내리기 위해 batch-commit 메커니즘을 사용하므로, 하나의 sync 호출을 사용하여 여러 트랜잭션을 커밋할 수 있다.
Fault Tolerance
RocksDB는 checksum을 사용하여 저장장치의 손상(corruption)을 감지한다. 이 checksum은 각 블록(일반적으로 4K ~128K 크기)에 대한 것이다. 한 번 저장장치에 쓰여진 블록은 절대 수정되지 않는다. RocksDB는 checksum 계산을 위해 하드웨어 지원을 동적으로 탐지하고, 사용 가능할 때 해당 지원을 사용한다.
Multi-Threaded Compactions
어플리케이션이 기존 key를 덮어 쓰는 경우 발생할 수 있는 동일한 key의 여러 복사본을 제거하려면 compaction이 필요하다. 또한, compaction은 key 삭제도 처리한다. Compaction이 적절하게 구성된다면, 여러 thread에서 compaction이 발생할 수 있다.
LSM 데이터베이스의 전체 쓰기 처리량은, 특히 데이터가 SSD 또는 RAM과 같은 빠른 스토리지에 저장되어 있을 때, compaction이 발생하는 속도에 따라 달라진다. RocksDB는 여러 thread에서 동시에 compaction 요청을 이슈하도록 구성될 수 있다. 데이터베이스가 SSD에 있을 때 single-threaded compaction과 비교해보면, multi-threaded compaction으로 지속 쓰기 속도가 10배까지 증가할 수 있다.
전체 데이터베이스는 일련의 sstfiles에 저장된다. memtable이 가득 차면, 그 내용은 Level-0 (L0) 파일에 쓰여진다. memtable에서 L0 파일로 플러시 될 때, RocksDB는 memtable에서 중복되고 덮어 쓰여진 key들을 제거한다. 어떤 파일은 주기적으로 읽어들여지고 더 큰 파일을 만들기 위해 병합되기도 한다 - 이를 compaction이라고 한다.
RocksDB는 두 가지 스타일의 compaction을 지원한다. 첫 번째로 Universal Style Compaction은 모든 파일을 L0에 저장하며 모든 파일은 시간 순서대로 정렬된다. Compaction은 시간순으로 서로 인접한 파일 몇 개를 선택하여 병합한 후, 새 파일로 만들어 L0에 쓴다. 그리고 모든 파일에는 겹치는 key가 있을 수 있다.
Level Style Compaction은 데이터베이스를 여러 레벨로 나누어서 데이터를 저장한다. 가장 최근의 데이터는 L0에 저장되고 가장 오래된 데이터는 Lmax에 저장된다. L0의 파일에는 겹치는 key가 있을 수 있지만, 다른 레벨의 파일에는 겹치는 key가 없다. Compaction 프로세스는 Ln의 파일 한 개와 Ln+1의 모든 겹치는 파일을 선택하고 병합한 뒤, Ln+1의 새 파일로 대체한다. 일반적으로 Universal Style Compaction은 Level Style Compaction보다 write amplification은 낮지만 space amplification은 높다.
데이터베이스의 MANIFEST 파일은 데이터베이스 상태를 기록한다. Compaction 프로세스는 데이터베이스에 새로운 파일을 추가하고 기존 파일을 삭제하는데, MANIFEST 파일에 그 내용을 기록함으로써 그 작업들이 persistent 하게 만든다. MANIFEST 파일에 기록된 트랜잭션은 batch-commit 알고리즘을 사용하여, 반복된 동기화(sync) 비용을 MANIFEST 파일로 분할 상환(amortize)한다.
Avoiding Stalls
Background compaction thread는 memtable의 내용을 저장 장치의 파일에 플러시하는 데에도 사용된다. 만약 모든 background compaction thread가 오랜 시간이 걸리는 compaction을 하느라 바쁘면, 갑작스런 쓰기 작업들이 memtable(s)을 빠르게 채울 수 있고, 이 경우 새로운 쓰기 작업들이 지연된다. 이 상황은, memtable을 저장장치로 플러시하는 일만 하는 작은 thread 집합을 유지하도록 RocksDB를 설정함으로써 피할 수 있다.
Compaction Filter
일부 어플리케이션은 compaction 시간에 key를 처리하려고 할 수 있다. 예를 들어, TTL (time-to-live)를 지원하는 데이터베이스는 만료된 key를 제거하려고 할 수 있다. 이 작업은 어플리케이션이 정의한 Compaction Filter를 통해 수행될 수 있다. 어플리케이션이 특정 시간보다 오래된 데이터를 계속해서 삭제하려고 하는 경우, compaction filter를 사용하여 만기된 레코드를 삭제할 수 있다. RocksDB Compaction Filter는 어플리케이션이 key 값을 수정하거나 compaction 프로세스의 일부로 key를 완전히 삭제할 수 있도록 제어한다. 예를 들어, 어플리케이션은 compaction의 일부로 지속적으로 데이터 sanitizer를 실행할 수 있다.
ReadOnly Mode
RocksDB에서는 읽기 전용(ReadOnly) 모드로 데이터베이스를 열 수 있다. 이 모드에서는 응용 프로그램이 데이터베이스의 내용을 수정할 수 없다. 자주 접근되는 코드의 경우, 읽기 전용 모드로 lock 없이도 읽기가 가능하기 때문에 읽기 성능을 훨씬 향상시킬 수 있다.
Database Debug Logs
RocksDB는 LOG*이라는 파일에 자세한 로그를 기록한다. 이 로그들은 주로 실행중인 시스템을 디버깅하거나 분석하는 데에 사용된다. 이 LOG는 특정 주기에 roll 하도록 설정될 수 있다.
Data Compression
RocksDB는 snappy, zlib, bzip2, lz4, lz4_hc 압축 방식을 지원한다. RocksDB는 다른 레벨의 데이터에 대해서 다른 압축 알고리즘을 사용할 수 있도록 설정할 수 있다. 일반적으로, 90%의 데이터가 Lmax 레벨에 존재한다. 일반 설치의 경우, 레벨 L0-L2의 경우 압축을 사용하지 않고, 중간 레벨의 경우 snappy 압축 기법, Lmax의 경우 zlib 압축 기법으로 설정되어 있다.
Transaction Logs
RocksDB는 트랜잭션을 logfile에 저장하여 시스템 충돌을 방지한다. 다시 시작할 때, logfile에 기록된 모든 트랜잭션을 다시 처리한다. logfile은 sstfile들이 저장된 디렉토리와 다른 디렉토리에 저장되도록 설정할 수 있다. 이는 비영구적인 빠른 저장장치에 모든 데이터 파일을 저장하려는 경우에 필요하다. 동시에, 모든 트랜잭션 로그를 느리지만 영구적인 저장장치에 저장함으로써 데이터 손실을 방지할 수 있다.
Full Backups, Incremental Backups and Replication
RocksDB has support for full backups and incremental backups. RocksDB is an LSM database engine, so, once created, data files are never overwritten, and this makes it easy to extract a list of file-names that correspond to a point-in-time snapshot of the database contents. The API DisableFileDeletions instructs RocksDB not to delete data files. Compactions will continue to occur, but files that are not needed by the database will not be deleted. A backup application may then invoke the API GetLiveFiles/GetSortedWalFiles to retrieve the list of live files in the database and copy them to a backup location. Once the backup is complete, the application can invoke EnableFileDeletions; the database is now free to reclaim all the files that are not needed any more.
Incremental Backups and Replication need to be able to find and tail all the recent changes to the database. The API GetUpdatesSince allows an application to tail the RocksDB transaction log. It can continuously fetch transactions from the RocksDB transaction log and apply them to a remote replica or a remote backup.
A replication system typically wants to annotate each Put with some arbitrary metadata. This metadata may be used to detect loops in the replication pipeline. It can also be used to timestamp and sequence transactions. For this purpose, RocksDB supports an API called PutLogData that an application may use to annotate each Put with metadata. This metadata is stored only in the transaction log and is not stored in the data files. The metadata inserted via PutLogData can be retrieved via the GetUpdatesSince API.
RocksDB transaction logs are created in the database directory. When a log file is no longer needed, it is moved to the archive directory. The reason for the existence of the archive directory is because a replication stream that is falling behind might need to retrieve transactions from a log file that is way in the past. The API GetSortedWalFiles returns a list of all transaction log files.
Support for Multiple Embedded Databases in the same process
A common use-case for RocksDB is that applications inherently partition their data set into logical partitions or shards. This technique benefits application load balancing and fast recovery from faults. This means that a single server process should be able to operate multiple RocksDB databases simultaneously. This is done via an environment object named Env. Among other things, a thread pool is associated with an Env. If applications want to share a common thread pool (for background compactions) among multiple database instances, then it should use the same Env object for opening those databases.
Similarly, multiple database instances may share the same block cache.
Block Cache -- Compressed and Uncompressed Data
RocksDB uses a LRU cache for blocks to serve reads. The block cache is partitioned into two individual caches: the first caches uncompressed blocks and the second caches compressed blocks in RAM. If a compressed block cache is configured, then the database intelligently avoids caching data in the OS buffers.
Table Cache
The Table Cache is a construct that caches open file descriptors. These file descriptors are for sstfiles. An application can specify the maximum size of the Table Cache.
External Compaction Algorithms
LSM 데이터베이스의 성능은 compaction 알고리즘과 그 구현에 따라 크게 달라진다. RocksDB에는 LevelStyle과 UniversalStyle의 두 가지 compaction 알고리즘이 있다. 우리는 대규모 개발자 커뮤니티에서 다른 compaction 알고리즘을 개발하고 실험 할 수 있게 하고 싶다. 이러한 이유로 RocksDB에서는 내장된 compaction 알고리즘을 끌 수 있으며, 어플리케이션이 자체 compaction 알고리즘을 실행할 수 있도록 하는 API를 제공한다.
Options.disable_auto_compaction이 설정되면, 기본 compaction 알고리즘은 비활성화된다. GetLiveFilesMetaData API를 사용하면 외부 컴포넌트가 데이터베이스의 모든 데이터 파일을 탐색하고, 어떤 데이터 파일을 병합하고 압축할 지 결정할 수 있다. DeleteFile API는 어플리케이션이 더 이상 사용되지 않는 것으로 간주되는 데이터 파일을 삭제할 수 있게 한다.
Non-Blocking Database Access
There are certain applications that are architected in such a way that they would like to retrieve data from the database only if that data retrieval call is non-blocking, i.e., the data retrieval call does not have to read in data from storage. RocksDB caches a portion of the database in the block cache and these applications would like to retrieve the data only if it is found in this block cache. If this call does not find the data in the block cache then RocksDB returns an appropriate error code to the application. The application can then schedule a normal Get/Next operation understanding that fact that this data retrieval call could potentially block for IO from the storage (maybe in a different thread context).
Stackable DB
RocksDB has a built-in wrapper mechanism to add functionality as a layer above the code database kernel. This functionality is encapsulated by the StackableDB API. For example, the time-to-live functionality is implemented by a StackableDB and is not part of the core RocksDB API. This approach keeps the code modularized and clean.
Backupable DB
One feature implemented using the StackableDB interface is BackupableDB, which makes backing up RocksDB simple. You can read more about it here: How to backup RocksDB?
Memtables:
Pluggable Memtables:
The default implementation of the memtable for RocksDB is a skiplist. The skiplist is a sorted set, which is a necessary construct when the workload interleaves writes with range-scans. Some applications do not interleave writes and scans, however, and some applications do not do range-scans at all. For these applications, a sorted set may not provide optimal performance. For this reason, RocksDB supports a pluggable API that allows an application to provide its own implementation of a memtable. Three memtables are part of the library: a skiplist memtable, a vector memtable and a prefix-hash memtable. A vector memtable is appropriate for bulk-loading data into the database. Every write inserts a new element at the end of the vector; when it is time to flush the memtable to storage the elements in the vector are sorted and written out to a file in L0. A prefix-hash memtable allows efficient processing of gets, puts and scans-within-a-key-prefix.
Memtable Pipelining
RocksDB supports configuring an arbitrary number of memtables for a database. When a memtable is full, it becomes an immutable memtable and a background thread starts flushing its contents to storage. Meanwhile, new writes continue to accumulate to a newly allocated memtable. If the newly allocated memtable is filled up to its limit, it is also converted to an immutable memtable and is inserted into the flush pipeline. The background thread continues to flush all the pipelined immutable memtables to storage. This pipelining increases write throughput of RocksDB, especially when it is operating on slow storage devices.
Memtable Compaction:
When a memtable is being flushed to storage, an inline-compaction process removes duplicate records from the output steam. Similarly, if an earlier put is hidden by a later delete, then the put is not written to the output file at all. This feature reduces the size of data on storage and write amplification greatly. This is an essential feature when RocksDB is used as a producer-consumer-queue, especially when the lifetime of an element in the queue is very short-lived.
Merge Operator
RocksDB는 기본적으로 Put 레코드, Delete 레코드, Merge 레코드의 세 가지 유형의 레코드를 지원한다. Compaction 프로세스가 Merge 레코드를 발견하면, Merge Operator라고 불리는 어플리케이션 지정 method를 호출한다. Merge는 여러 개의 Put 및 Merge 레코드를 하나의 레코드로 병합할 수 있다. 이 강력한 기능을 통해 일반적으로 읽기-수정-쓰기 작업을 수행하는 어플리케이션이 읽기 작업을 모두 피할 수 있다. 또한 Merge Operator는 어플리케이션이 operation의 의도(intent-of-the-operation)를 Merge 레코드로 기록할 수 있게 해주며, RocksDB compaction 프로세스는 해당 의도를 원래 값에 느리게 적용한다. 이 기능은 Merge Operator에 자세히 설명되어 있다.
5. 제공하는 툴
Production 환경에서 데이터베이스를 지원하는 데 사용되는 여러 흥미로운 툴들이 있다. sst_dump 유틸리티는 sst 파일의 모든 key-value를 덤프한다. ldb 툴은 데이터베이스 내용을 넣고, 가져오고, 스캔할 수 있다. 또한, ldb는 MANIFEST의 내용을 덤프할 수 있으며, 데이터베이스 레벨 수를 변경하는 데 사용될 수도 있다. 그리고 데이터베이스를 수동으로 압축하는 데에도 사용할 수 있다.
6. 테스트
RocksDB에서는 데이터베이스의 특정 기능을 테스트할 수 있는 많은 unit 테스트를 제공한다. make check 명령은 모든 unit 테스트를 실행한다. Unit 테스트는 RocksDB의 특정 기능을 실행시키는데, 규모에 따른 데이터 정확성을 테스트하도록 설계되지는 않았다. 규모에 따른 데이터의 정확성을 검증하기 위해서는 db_stress 테스트를 사용하면 된다.
7. 성능
RocksDB 성능은 db_bench라는 유틸리티를 통해 벤치마크 할 수 있다. db_bench는 RocksDB 소스 코드의 일부분이다. 플래시 저장장치를 몇몇 전형적인 워크로드를 사용해 성능 평가한 결과는 여기에서 확인할 수 있다. 또한 in-memory 워크로드에 대한 RocksDB 성능 평과 결과는 여기에서 확인할 수 있다.