Branch | master | develop | --------------- | ----------------------------------------------------------- | ------------------------------------------------------------- | Docs | | Drone | | codecov.io | | License |

A Key/Value Store For SSDs

Introduction
Description
Requirements
Example
Building
Algorithm
License
Contact

Introduction

NuDB is an append-only, key/value store specifically optimized for random read performance on modern SSDs or equivalent high-IOPS devices. The most common application for NuDB is content addressable storage where a cryptographic digest of the data is used as the key. The read performance and memory usage are independent of the size of the database. These are some other features:

Low memory footprint
Database size up to 281TB
All keys are the same size
Append-only, no update or delete
Value sizes from 1 to 2^32 bytes (4GB)
Performance independent of growth
Optimized for concurrent fetch
Key file can be rebuilt if needed
Inserts are atomic and consistent
Data file may be efficiently iterated
Key and data files may be on different devices
Hardened against algorithmic complexity attacks
Header-only, no separate library to build

Description

This software is close to final. Interfaces are stable. For recent changes see the CHANGELOG.

NuDB has been in use for over a year on production servers running rippled, with database sizes over 3 terabytes.

Requirements

Boost 1.69 or higher
C++11 or greater
SSD drive, or equivalent device with high IOPS

These components are optionally required in order to build the tests and examples:

CMake 3.7.2 or later (optional)
Properly configured bjam/b2 (optional)

Example

This complete program creates a database, opens the database, inserts several key/value pairs, fetches the key/value pairs, closes the database, then erases the database files. Source code for this program is located in the examples directory.

#include <nudb/nudb.hpp>
#include <cstddef>
#include <cstdint>

int main()
{
    using namespace nudb;
    std::size_t constexpr N = 1000;
    using key_type = std::uint32_t;
    error_code ec;
    auto const dat_path = "db.dat";
    auto const key_path = "db.key";
    auto const log_path = "db.log";
    create<xxhasher>(
        dat_path, key_path, log_path,
        1,
        make_salt(),
        sizeof(key_type),
        block_size("."),
        0.5f,
        ec);
    store db;
    db.open(dat_path, key_path, log_path, ec);
    char data = 0;
    // Insert
    for(key_type i = 0; i < N; ++i)
        db.insert(&i, &data, sizeof(data), ec);
    // Fetch
    for(key_type i = 0; i < N; ++i)
        db.fetch(&i,
            [&](void const* buffer, std::size_t size)
        {
            // do something with buffer, size
        }, ec);
    db.close(ec);
    erase_file(dat_path);
    erase_file(key_path);
    erase_file(log_path);
}

Building

NuDB is header-only so there are no libraries to build. To use it in your project, simply copy the NuDB sources to your project's source tree (alternatively, bring NuDB into your Git repository using the git subtree or git submodule commands). Then, edit your build scripts to add the include/ directory to the list of paths checked by the C++ compiler when searching for includes. NuDB #include lines will look like this:

#include <nudb/nudb.hpp>

To link your program successfully, you'll need to add the Boost.Thread and Boost.System libraries to link with. Please visit the Boost documentation for instructions on how to do this for your particular build system.

NuDB tests require Beast, and the benchmarks require RocksDB. These projects are linked to the repository using git submodules. Before building the tests or benchmarks, these commands should be issued at the root of the repository:

git submodule init
git submodule update

For the examples and tests, NuDB provides build scripts for Boost.Build (b2) and CMake. To generate build scripts using CMake, execute these commands at the root of the repository (project and solution files will be generated for Visual Studio users):

cd bin
cmake ..                                    # for 32-bit Windows build

cd ../bin64
cmake ..                                    # for Linux/Mac builds, OR
cmake -G"Visual Studio 14 2015 Win64" ..    # for 64-bit Windows builds

To build with Boost.Build, it is necessary to have the b2 executable in your path. And b2 needs to know how to find the Boost sources. The easiest way to do this is make sure that the version of b2 in your path is the one at the root of the Boost source tree, which is built when running bootstrap.sh (or bootstrap.bat on Windows).

Once b2 is in your path, simply run b2 in the root of the Beast repository to automatically build the required Boost libraries if they are not already built, build the examples, then build and run the unit tests.

On OSX it may be necessary to pass "toolset=clang" on the b2 command line. Alternatively, this may be site in site-config.jam or user-config.jam.

The files in the repository are laid out thusly:

./
    bench/          Holds the benchmark sources and scripts
    bin/            Holds executables and project files
    bin64/          Holds 64-bit Windows executables and project files
    examples/       Holds example program source code
    extras/         Additional APIs, may change
    include/        Add this to your compiler includes
        nudb/
    test/           Unit tests and benchmarks
    tools/          Holds the command line tool sources

Algorithm

Three files are used.

The data file holds keys and values stored sequentially and size-prefixed.
The key file holds a series of fixed-size bucket records forming an on-disk hash table.
The log file stores bookkeeping information used to restore consistency when an external failure occurs.

In typical cases a fetch costs one I/O cycle to consult the key file, and if the key is present, one I/O cycle to read the value.

Usage

Callers must define these parameters when creating a database:

KeySize: The size of a key in bytes.
BlockSize: The physical size of a key file record.

The ideal block size matches the sector size or block size of the underlying physical media that holds the key file. Functions are provided to return a best estimate of this value for a particular device, but a default of 4096 should work for typical installations. The implementation tries to fit as many entries as possible in a key file record, to maximize the amount of useful work performed per I/O.

LoadFactor: The desired fraction of bucket occupancy

LoadFactor is chosen to make bucket overflows unlikely without sacrificing bucket occupancy. A value of 0.50 seems to work well with a good hash function.

Callers must also provide these parameters when a database is opened:

Appnum: An application-defined integer constant which can be retrieved later from the database [TODO].
AllocSize: A significant multiple of the average data size.

Memory is recycled to improve performance, so NuDB needs AllocSize as a hint about the average size of the data being inserted. For an average data size of 1KB (one kilobyte), AllocSize of sixteen megabytes (16MB) is sufficient. If the AllocSize is too low, the memory recycler will not make efficient use of allocated blocks.

Two operations are defined: fetch, and insert.

`fetch`

The fetch operation retrieves a variable length value given the key. The caller supplies a factory used to provide a buffer for storing the value. This interface allows custom memory allocation strategies.

`insert`

insert adds a key/value pair to the store. Value data must contain at least one byte. Duplicate keys are disallowed. Insertions are serialized, which means [TODO].

Implementation

All insertions are buffered in memory, with inserted values becoming immediately discoverable in subsequent or concurrent calls to fetch. Periodically, buffered data is safely committed to disk files using a separate dedicated thread associated with the database. This commit process takes place at least once per second, or more often during a detected surge in insertion activity. In the commit process the key/value pairs receive the following treatment:

An insertion is performed by appending a value record to the data file. The value record has some header information including the size of the data an

NuDB

Install / Use

README