nessDB

nessDB is an embedded key-value DBMS written in ANSI C with BSD license. It does not require any external dependencies and works in most POSIX systems.

As for storage engine, nessDB used LSM-tree (Log-Structured Merge Tree) in v1.8, B-epsilon-tree in v2.0. nessDB also used fractional cascading to speed up the query.

History

It has released two main versions (v1.8 and v2.0), while v3.0 is still work in progress. This article is based on the last released version, v2.0.

Compression

Naïve (Page-Level)

nessDB v2.0 used QuickLZ, a compression library written in C, to compress the key-value pair when storing the pair into tree nodes.

Concurrency Control

Not Supported

For nessDB v2.0, there are two mutexes for the meta data and SST (Small-Splittable Tree), and no tuple level latch. A thread must get the latch before merging the SST nodes.

Storage Architecture

Disk-oriented

nessDB is a disk-oriented DBMS. All data are stored in non-volatile storage after shutdown.

Data Model

Key/Value

nessDB is a key-value DBMS, which supports Redis-like protocol, such as SET, GET, DEL, EXISTS. To be specific, both key and value are general raw data and are represented by a pointer with length.

Joins

Not Supported

nessDB does not support join. It is a key-value DBMS with only interfaces such as SET, GET, DEL, EXISTS.

Indexes

Log-Structured Merge Tree

nessDB used LSM-tree (Log-Structured Merge Tree) in v1.8, Small-Splittable Tree in v2.0. Those data structures are suitable for high-performance insertion compared to B-tree.

Storage Organization

Heaps

For a tree node file, there is a header which stored count of the key-value pair in each level. The header is followed by several var-length key-value pairs with data offset. The following diagram shows the structure of a tree node file, and the first line represents the header part.

| L0 count | L1 count | L2 count | L3 count |
| Key 0 length | key 0 data | data offset | operation flag|
| Key 1 length | key 1 data | data offset | operation flag|
...
| Key N length | key N data | data offset | operation flag|

Checkpoints

Not Supported

nessDB v2.0 does not support recovery and checkpoint.

System Architecture

Embedded

Stored Procedures

Not Supported

Storage Model

N-ary Storage Model (Row/Record)

nessDB v2.0 used a Small-Splittable Tree (SST), a B-Epsilon-tree with small height (level), for storage engine. SST has multiple levels with exponential expanding size. For level 0, the data is un-sorted and the other levels are sorted. This data structure is designed for random write workloads.

Query Execution

Tuple-at-a-Time Model

nessDB is a key-value DBMS and each query only involves a single key-value pair.

Foreign Keys

Not Supported

nessDB is a key-value DBMS so it does not support foreign key.

Isolation Levels

Not Supported

nessDB v2.0 uses a single mutex for the whole SST structure instead of tuple-level latches.

Query Interface

Custom API

nessDB is an embedded DBMS with custom C API, as well as wrappers for Java, Python and Lua.

nessDB Logo
Website

https://github.com/BohuTANG/nessDB

Source Code

https://github.com/BohuTANG/nessDB

Tech Docs

https://github.com/BohuTANG/nessDB/wiki

Developer

Bohu Tang

Country of Origin

CN

Start Year

2011

End Year

2016

Project Type

Open Source

Written in

C

Supported languages

C, C++, Java, Lua, Python

Operating Systems

BSD, Linux

Licenses

BSD