ForestDB - A Fast Key-Value Storage Engine Based on Hierarchical B+-Tree Trie

Related tags

Database forestdb
Overview

ForestDB

ForestDB is a key-value storage engine developed by Couchbase Caching and Storage Team, and its main index structure is built from Hierarchical B+-Tree based Trie, called HB+-Trie. ForestDB paper has been published in IEEE Transactions on Computers.

Compared with traditional B+-Tree based storage engines, ForestDB shows significantly better read and write performance with less storage overhead. ForestDB has been tested on various server OS environments (Centos, Ubuntu, Mac OS x, Windows) and mobile OSs (iOS, Android). The test coverage stats for ForestDB are available in ForestDB Code Coverage Report.

ForestDB benchmark program is also available for performance comparisons with other key-value storage engines.

Please visit the ForestDB wiki for more details.

Main Features

  • Keys and values are treated as an arbitrary binary.
  • Applications can supply a custom compare function to support a customized key order.
  • A value can be retrieved by its sequence number or disk offset in addition to a key.
  • Write-Ahead Logging (WAL) and its in-memory index are used to reduce the main index lookup / update overhead.
  • Multi-Version Concurrency Control (MVCC) support and append-only storage layer.
  • Multiple snapshot instances can be created from a given ForestDB instance to provide different views of database.
  • Rollback is supported to revert the database to a specific point.
  • Ranged iteration by keys or sequence numbers is supported for a partial or full range lookup operation.
  • Manual or auto compaction can be configured per ForestDB database file.
  • Transactional support with read_committed or read_uncommitted isolation level.

How to build

See INSTALL.MD

How to Use

Please refer to Public APIs and tests/fdb_functional_test.cc in ForestDB source directory.

How to contribute code

  1. Sign the Couchbase Contributor License Agreement
  2. Submit code changes via either a Github PR or via Gerrit (for Gerrit usage, see Instructions from the couchbase-spark-connector project.)

Note regarding master branch

The 'master' git branch of forestdb contains a number of changes which ultimately were not kept for production builds of Couchbase Server. Production builds were kept on an earlier release branch named 'watson' corresponding to Couchbase Server 4.5. Couchbase Server 5.0, 5.1, 5.5, and 6.0 added some bug fixes on branches made from 'watson', namely 'spock' and 'vulcan'. For Couchbase Server 6.5 and forward, a new branch 'cb-master' was created from the then-current 'vulcan' branch.

'cb-master' should be seen as the equivalent of 'master' for all Couchbase Server production build purposes. Any additional production bug fixes will go there, and release-specific branches will be made from there when necessary.

The current 'master' branch is left untouched and unsupported, for use by community users who may depend on the work done there.

Comments
  • Improve MemoryPool locality

    Improve MemoryPool locality

    Improve cache locality by using a stack for indexes and a continuous block of memory.

    Although it now requires a multiplication (at least preserving this API) the operations on the underlining vector are faster and have better locality than the previous underlining deque.

    opened by arthurprs 7
  • Error building on OSX -- fatal error: 'snappy-c.h' file not found

    Error building on OSX -- fatal error: 'snappy-c.h' file not found

    Steps to build:

    $ brew install cmake
    $ brew install snappy # note, I didn't use "sudo", does that make a difference?
    $ git clone <repo>
    $ cd forestdb && mkdir build && cd build && cmake ../
    

    Cmake output: https://gist.github.com/tleyden/555a6ea565f768c739f3

    When I ran make all, I got an error:

    [ 27%] Building CXX object CMakeFiles/docio_test.dir/src/docio.cc.o
    /Users/tleyden/DevLibraries/forestdb/src/docio.cc:26:10: fatal error: 'snappy-c.h' file not found
    #include "snappy-c.h"
             ^
    1 error generated.
    make[2]: *** [CMakeFiles/docio_test.dir/src/docio.cc.o] Error 1
    make[1]: *** [CMakeFiles/docio_test.dir/all] Error 2
    make: *** [all] Error 2
    

    Full make all output: https://gist.github.com/tleyden/86c926a85adfd9d175da

    I do have snappy-c.h in my /usr/local/Cellar dir:

    $ find /usr/local/Cellar -iname "*snappy*"
    /usr/local/Cellar/snappy
    /usr/local/Cellar/snappy/1.1.1/include/snappy-c.h
    ....
    

    but it doesn't seem to be found during the compilation. Is my brew misconfigured or do I need to do another step?

    opened by tleyden 7
  • CMakeLists.txt: easily switch between static and shared libs

    CMakeLists.txt: easily switch between static and shared libs

    This PR makes it easy to switch between building forestdb as a shared library or as a static library via the BUILD_SHARED_LIBS option. By default it will build a shared lib as before.

    Building a static lib can be invoked ala:

    cmake -DBUILD_SHARED_LIBS:bool=OFF

    Signed-off-by: Mark Nelson [email protected]

    opened by markhpc 5
  • Database files larger than 2GB

    Database files larger than 2GB

    Database files larger than 2GB do not work on Windows as the 32bit version of the seek function returns a signed long, which causes downstream functions to fail as the offsets are no longer valid.

    opened by wiredprairie 4
  • Error building on Master branch

    Error building on Master branch

    I did the following steps on ubuntu 18.04

    mkdir build
    cd build
    cmake ../
    make all
    

    it produces an error:

    /forestdb/utils/debug.cc:88:5: error: ‘ucontext’ was not declared in this scope
         ucontext *u = (ucontext *)context;
         ^~~~~~~~
    

    Screenshot from 2019-05-23 13-31-43

    opened by waleedhammam 2
  • libmusl compatibility

    libmusl compatibility

    I'm working on compiling couchbase on alpine linux. There were just two changes needed to get forestdb to successfully run all tests:

    spin_t

    The existing code doesn't call spin_init() for some (most?) spin_t variables. The code works fine, however, since SPIN_INITIALIZER seems to be properly 'initializing' them. This is not the case when running on libmusl though, and calling spin_lock() on such 'initialized' spin_t's leads to a deadlock.

    While the proper solution would entail properly initializing all spin_t variables by calling spin_init(), I'm reluctant to do so, as there's no clear place where this can be done. Instead, setting the initializer to the correct value for musl (spin_t)(0) instead of (spin_t)(1) does the trick.

    pthread stack

    Threads are crashing since the default musl pthread stack size is only 80k as opposed to the 2Mb when running on glibc. So I'm explicitly setting the stack size to 2Mb.

    Change-Id: I02f7f4123a8d46d0ce1cef2285ac8fcefe02dc0d

    opened by jlopez 2
  • build error for aarch64

    build error for aarch64

    orestdb/utils/debug.cc:93:57: error: no member named 'gregs' in 'mcontext_t'; did you mean 'regs'?
        unsigned char *pc = (unsigned char *)u->uc_mcontext.gregs[REG_EIP];
                                                            ^~~~~
                                                            regs
    /usr/include/aarch64-linux-gnu/sys/ucontext.h:55:34: note: 'regs' declared here
        unsigned long long int __ctx(regs)[31];
                                     ^
    forestdb/utils/debug.cc:93:63: error: use of undeclared identifier 'REG_EIP'
        unsigned char *pc = (unsigned char *)u->uc_mcontext.gregs[REG_EIP];
                                                                  ^
    
    opened by calvin2021y 1
  • Some questions and Suggestions about ForestDB

    Some questions and Suggestions about ForestDB

    ForestDB is a very good KV storage component, Some questions and Suggestions about ForestDB:

    1. The binary cross-c/C++ compiler call is not supported on MSVC because in fdb_types.h: #ifndef __cplusplus

      #pragma once

    #define false (0)

    #define true (1)

    #define bool int

    #endif sizeof(bool)==1 On the c ++ compiler, and sizeof(bool)==4 On the c ++ compiler, ForestDB must be compiled using the c ++ compiler, because byte alignment is different, the result error by call fdb_get_default_config() and fdb_get_default_kvs_config() API.

    1. Some API parameters are not appropriate:

      LIBFDB_API fdb_config fdb_get_default_config(void) change for LIBFDB_API fdb_status fdb_get_default_config(fdb_config* fconfig) LIBFDB_API fdb_kvs_config fdb_get_default_kvs_config(void) change for LIBFDB_API fdb_status fdb_get_default_kvs_config(fdb_kvs_config* config) fdb_status fdb_doc_update(fdb_doc **doc,... change for fdb_status fdb_doc_update(fdb_doc *doc,...

      That's more reasonable.

    2. After enable stale block reusing, repeat full table write->commit->full table update->commit->full table delete->commit, etc,stale block reusing ineffectiveness, If you control the commit granularity, that you can.

    4.enable DOCIO_BLOCK_ALIGN macro in option.h, Partial record call fdb_get_kv() retrieval failed.

    1. When num_keeping_headers is set to 1, Write 100w record(key: int, value: 1KB), set/get/update is good, But deleting errors: [FDB ERR: -61] Read error: BID 550859 in a database file './tag-table.db' is not read correctly: only -61 bytes read (hex) 0x88d2400, 4096 (0x1000) bytes 0000 00 20 00 00 00 04 3d dc ff ff ff ff ff ff ff ff . ....=......... ... ... 0ff0 ff ff ff ff ff ff ff ff 00 00 00 00 00 00 00 ff ................ [FDB ERR: -61] Failed to read a database header with block id 550859 in a database file './tag-table.db' [FDB ERR: -5] Read error: read offset 14757395258967638016 exceeds the file's current offset 2256322560 in a database file './tag-table.db'

    [FDB ERR: -5] Failed to read a database header with block id 14757395258967641292 in a database file './tag-table.db'

    No error occurred while num_keeping_headers>1.

    opened by tpri-hq 1
  • MB-13095 fdb_get_byoffset fails if only offset specified

    MB-13095 fdb_get_byoffset fails if only offset specified

    Example:

    let mut doc: *mut ffi::fdb_doc = ptr::null_mut();
    ffi::fdb_doc_create(&mut doc,
                        ptr::null_mut(), 0,
                        ptr::null_mut(), 0,
                        ptr::null_mut(), 0);
    (*doc).offset = doc1.offset(); // actual offset
    // if this line is missing - result is key not found error
    (*doc).seqnum = 0xffffffffffffffff;
    // (*doc).seqnum = doc1.seq_num(); // this works too
    
    let res = ffi::fdb_get_byoffset(store.get_raw(), doc);
    assert_eq!(res, 0);
    

    Happened because fdb_doc_create sets seqnum to 0 and later on equal_doc returns false as considers 0 to be a correct value to check against found document.

    opened by vhbit 1
  • Add 'const' qualifiers in API

    Add 'const' qualifiers in API

    In the public API in forestdb.h, please add the const qualifier to function parameters that take pointers but do not modify the memory pointed to. For example,

    fdb_status fdb_open(fdb_handle *handle, char *filename, fdb_config *config);
    

    should be

    fdb_status fdb_open(fdb_handle *handle, const char *filename, const fdb_config *config);
    
    opened by snej 1
  • Crash when parsing malformed FDB

    Crash when parsing malformed FDB

    Hi folks,

    An interesting crash was found while fuzz testing of the forestdb_dump binary which can be triggered via a malformed database file. Although this malformed file only crashes the program as-is, it could potentially be crafted further and create a security issue where these kinds of files would be able compromise the process's memory through taking advantage of affordances given by memory corruption. It's recommend to harden the code to prevent these kinds of bugs as it could greatly mitigate such this issue and even future bugs.

    crash.fdb.txt

    (renamed to .txt for github)

    $ forestdb_dump crash.fdb
    Segmentation fault (core dumped)
    
    $ gdb -q forestdb_dump
    Reading symbols from forestdb_dump...
    
    (gdb) r crash.fdb
    Starting program: forestdb_dump crash.fdb
    [Thread debugging using libthread_db enabled]
    Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
    [New Thread 0x7ffff79f2700 (LWP 1245583)]
    [New Thread 0x7ffff71f1700 (LWP 1245584)]
    [New Thread 0x7ffff69f0700 (LWP 1245585)]
    [New Thread 0x7ffff61ef700 (LWP 1245586)]
    
    Thread 1 "forestdb_dump" received signal SIGSEGV, Segmentation fault.
    _sb_read_given_no (file=0x5555555df630, sb_no=<optimized out>, sb=<optimized out>, log_callback=<optimized out>) at forestdb/src/superblock.cc:1520
    1520	        sb->bmp_doc_offset[i] = _endian_decode(enc_u64);
    
    (gdb) bt
    #0  _sb_read_given_no (file=0x5555555df630, sb_no=<optimized out>, sb=<optimized out>, log_callback=<optimized out>) at forestdb/src/superblock.cc:1520
    #1  0x00005555555a7aa7 in sb_read_latest (file=0x5555555df630, sconfig=..., log_callback=<optimized out>) at forestdb/src/superblock.cc:1674
    #2  0x000055555557d75e in filemgr_open (filename=filename@entry=0x7fffffffc5c0 "crash.fdb", ops=<optimized out>, config=config@entry=0x7fffffffc270, 
        log_callback=log_callback@entry=0x5555555db048) at forestdb/src/filemgr.cc:1005
    #3  0x0000555555584036 in _fdb_open (handle=handle@entry=0x5555555daee0, filename=filename@entry=0x7fffffffe6b0 "crash.fdb", filename_mode=filename_mode@entry=FDB_VFILENAME, 
        config=config@entry=0x7fffffffdf10) at forestdb/src/forestdb.cc:1689
    #4  0x0000555555585ae1 in fdb_open (ptr_fhandle=0x7fffffffe160, filename=0x7fffffffe6b0 "crash.fdb", fconfig=0x7fffffffe1a0)
        at forestdb/src/forestdb.cc:833
    #5  0x0000555555563654 in process_file (opt=0x7fffffffe2e0) at forestdb/tools/forestdb_dump.cc:254
    #6  0x0000555555561f75 in main (argc=2, argv=0x7fffffffe418) at forestdb/tools/forestdb_dump.cc:390
    
    (gdb) i r
    rax            0x68                104
    rbx            0x5555555dfc00      93824992803840
    rcx            0x5555555e0d30      93824992808240
    rdx            0x88f46760570fd337  -8578117726758776009
    rsi            0x652e23e27000      111248844943360
    rdi            0x0                 0
    rbp            0x7ffffffd4b20      0x7ffffffd4b20
    rsp            0x7ffffffd4850      0x7ffffffd4850
    r8             0x0                 0
    r9             0x0                 0
    r10            0x5555555ea000      93824992845824
    r11            0xfffffffffffff000  -4096
    r12            0xe744e44a068       15892692115560
    r13            0x5555555df630      93824992802352
    r14            0x7ffffffd48b8      140737488177336
    r15            0xdeadcafebeefc002  -2401039830844719102
    rip            0x5555555a7783      0x5555555a7783 <_sb_read_given_no(filemgr*, size_t, superblock*, err_log_callback*)+883>
    eflags         0x10202             [ IF RF ]
    cs             0x33                51
    ss             0x2b                43
    ds             0x0                 0
    es             0x0                 0
    fs             0x0                 0
    gs             0x0                 0
    
    (gdb) x/i $rip
    => 0x5555555a7783 <_sb_read_given_no(filemgr*, size_t, superblock*, err_log_callback*)+883>:	mov    %rdx,-0x68(%r8,%rax,1)
    
    (gdb) exploitable
    Description: Access violation near NULL on destination operand
    Short description: DestAvNearNull (15/22)
    Hash: d6199a1b37a756f3d37f258a8faaa290.ecc8eda54691748cb17fcce5cae118bb
    Exploitability Classification: PROBABLY_EXPLOITABLE
    Explanation: The target crashed on an access violation at an address matching the destination operand of the instruction. This likely indicates a write access violation, which means the attacker may control write address and/or value. However, it there is a chance it could be a NULL dereference.
    Other tags: AccessViolation (21/22)
    
    opened by retpoline 0
  • Tag a New Release

    Tag a New Release

    I know that the project is dormant and development has stagnated, but it'd be awesome if y'all could tag a new release at whatever commit you feel is reasonable. I'd like to include this as a dependency in a project, but I'd hate to have to refer to either HEAD or a specific commit hash directly.

    Thanks!

    opened by haneefmubarak 6
Owner
null
LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values.

LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values. Authors: Sanjay Ghem

Google 31.5k Jan 1, 2023
A Key-Value data storage system. - dorea db

Dorea DB ?? Dorea is a key-value data storage system. It is based on the Bitcask storage model Documentation | Crates.io | API Doucment 简体中文 | English

ZhuoEr Liu 112 Dec 2, 2022
Immutable Ordered Key-Value Database Engine

PumpkinDB Build status (Linux) Build status (Windows) Project status Usable, between alpha and beta Production-readiness Depends on your risk toleranc

null 1.3k Jan 2, 2023
An embedded, in-memory, immutable, copy-on-write, key-value database engine

An embedded, in-memory, immutable, copy-on-write, key-value database engine. Features In-memory database Multi-version concurrency control Rich transa

SurrealDB 7 May 5, 2024
AgateDB is an embeddable, persistent and fast key-value (KV) database written in pure Rust

AgateDB is an embeddable, persistent and fast key-value (KV) database written in pure Rust. It is designed as an experimental engine for the TiKV project, and will bring aggressive optimizations for TiKV specifically.

TiKV Project 535 Jan 9, 2023
RedisLess is a fast, lightweight, embedded and scalable in-memory Key/Value store library compatible with the Redis API.

RedisLess is a fast, lightweight, embedded and scalable in-memory Key/Value store library compatible with the Redis API.

Qovery 145 Nov 23, 2022
A fast and simple in-memory database with a key-value data model written in Rust

Segment Segment is a simple & fast in-memory database with a key-value data model written in Rust. Features Dynamic keyspaces Keyspace level control o

Segment 61 Jan 5, 2023
A "blazingly" fast key-value pair database without bloat written in rust

A fast key-value pair in memory database. With a very simple and fast API. At Xiler it gets used to store and manage client sessions throughout the pl

Arthur 16 Dec 16, 2022
A LSM-based Key-Value Store in Rust

CobbleDB A LSM-based Key-Value Store in Rust Motivation There is no open-source LSM-based key-value store in Rust natively. Some crates are either a w

Yizheng Jiao 2 Oct 25, 2021
A rust Key-Value store based on Redis.

Key-Value Store A Key-Value store that uses Redis to store data. Built using an async web framework in Rust with a full Command-Line interface and log

Miguel David Salcedo 0 Jan 14, 2022
Plugin for macro-, mini-quad (quads) to save data in simple local storage using Web Storage API in WASM and local file on a native platforms.

quad-storage This is the crate to save data in persistent local storage in miniquad/macroquad environment. In WASM the data persists even if tab or br

ilya sheprut 9 Jan 4, 2023
Distributed transactional key-value database, originally created to complement TiDB

Website | Documentation | Community Chat TiKV is an open-source, distributed, and transactional key-value database. Unlike other traditional NoSQL sys

TiKV Project 12.4k Jan 3, 2023
PickleDB-rs is a lightweight and simple key-value store. It is a Rust version for Python's PickleDB

PickleDB PickleDB is a lightweight and simple key-value store written in Rust, heavily inspired by Python's PickleDB PickleDB is fun and easy to use u

null 155 Jan 5, 2023
CLI tool to work with Sled key-value databases.

sledtool CLI tool to work with Sled key-value databases. $ sledtool --help Usage: sledtool <dbpath> <command> [<args>] CLI tool to work with Sled da

Vitaly Shukela 27 Sep 26, 2022
Pure rust embeddable key-value store database.

MHdb is a pure Rust database implementation, based on dbm. See crate documentation. Changelog v1.0.3 Update Cargo.toml v1.0.2 Update Cargo.toml v1.0.1

Magnus Hirth 7 Dec 10, 2022
RefineDB - A strongly-typed document database that runs on any transactional key-value store.

RefineDB - A strongly-typed document database that runs on any transactional key-value store.

Heyang Zhou 375 Jan 4, 2023
Log structured append-only key-value store from Rust In Action with some enhancements.

riakv Log structured, append only, key value store implementation from Rust In Action with some enhancements. Features Persistent key value store with

Arindam Das 5 Oct 29, 2022
A sessioned Merkle key/value store

storage A sessioned Merkle key/value store The crate was designed to be the blockchain state database. It provides persistent storage layer for key-va

Findora Foundation 15 Oct 25, 2022
🔥🌲 High-performance Merkle key/value store

merk High-performance Merkle key/value store Merk is a crypto key/value store - more specifically, it's a Merkle AVL tree built on top of RocksDB (Fac

Nomic 189 Dec 13, 2022