History[02][04]

The ForestDB project came from ACM SIGMOD 2011 programming contest. It is now under the development of Couchbase's Caching and Storage team to replace the previous Couchstore storage engine and plans to conduct optimizations for SSD, support reduce feature and allow users to pause/resume compaction.

Checkpoints[05][06]

For every commit operations, the system checks the log size. If the size exceeds some threshold, the system will aggregate those logs and write them to the persistent storage (disk) in batch. ForestDB uses fsync() to flush logs to persistent storage, so it is a blocking checkpointing.

Compression[07]

ForestDB allows users to enable the compression on both keys and values. It uses Snappy library to compress data.

Concurrency Control[07][03]

ForestDB supports Multi-version Concurrency Control and uses append-only manner to store records. Besides, its indices are also designed to be easily maintained in MVCC. The in-memory WB index is log-structured. All B+ tree nodes in the HB+-trie are also updated in append-only manner.

Data Model[07]

Key/value store establishes a mapping from one entity to another. In ForestDB, the maximum size of key is 64KB and that of value is 4GB.

Indexes

Isolation Levels[07]

Currently, the forestDB only supports two isolation levels: READ COMMITTED and READ UNCOMMITTED.

Joins

Logging[05]

ForestDB stores all mutations in append-only manner. For each insert and update, ForestDB directly appends the new key/value pair at the end of a file. For each delete, ForestDB marks the key/value pair as deleted. It uses periodical compaction to conduct limit the log size. For each compaction, all records (key/value pairs) that are committed will be written to a new file. Once the compaction completes, ForestDB replaces the old file with the new file.

Query Compilation

Query Interface[07][08]

As a common key/value storage engine, ForestDB supports create, read, update and delete operations with a key/value pair and the metadata of keys. The maximum size of key and its metadata are both 64KB while that of value is 4GB. ForestDB supports retrieving metadata and the value by their corresponding key and the sequence number. It also supports retrieving metadata and the value of a record directly by its byte offset on disk.

Storage Architecture[05]

ForestDB is a disk-oriented storage engine. All records (documents) are stored on the disk in files. All updates on records are appended at the end of the corresponding file. The HB+-trie is also stored on disk.

Storage Model[05]

In ForestDB, a file on disk contains multiple blocks. Within each block, ForestDB uses NSM to organize records. Each record stores the value and the metadata of the key. Users can enable block alignment in ForestDB, which does not allow records to be stored across blocks. If the record size is larger than the size of a single block, ForestDB will compare the number of blocks required if the record were stored at the end of last record against if the record were stored at the beginning of the next block. ForestDB will choose the way requiring fewer blocks.

Storage Organization[05]

All records (documents) are stored in log-structured on disk. All updates are appended at the end of files on the disk. Similarly, all nodes of the HB+-trie index are also stored on disk. When there are updates on the HB+-trie index, those updates are also appended at the end of the file as new nodes in the HB+-trie. After all updates on the index are appended, a new block storing pointers to the new nodes is appended at the end of the file.

Stored Procedures

System Architecture[03]

ForestDB is a single-node storage engine.

Views