Binstore

Binstore is a simple key-value store written in Rust. This means that serialization/deserialization is not handled by binstore. All it does is storing key-value elements in a cache-friendly and compact file format. For now, this project is mostly for fun, but could hopefully evolve into something useable in the future.

File format

Headers

| Field name | Description | Type | | ---------------- |:---------------------------------|-----:| | magic | Magic number | u32 | | version | Version number | u8 | | timestamp | Creation timestamp | i64 | | sibaseoffset | Where the sparse index begins | u64 | | dibaseoffset | Where the dense index begins | u64 | | databaseoffset | Where the compressed data begins | u64 | | num_entries | Number of entries in file | u64 |

Sparse Index

| Key | DI Offset | |--------|-----------| | h0000 | dioff1 | | h1000 | dioff2 | | h2000 | dioff3 | | ... | ... | | hxxxx | dioffx |

Dense Index

| DI Offset | Key | Data Offset | |-----------|--------|-------------| | dioff1 | h0000 | dataoff1 | | | h0001 | dataoff2 | | | h0013 | dataoff3 | | ... | ... | ... | | | h0988 | dataoff4 | | dioff2 | h1000 | dataoff5 | | | h1003 | dataoff6 | | ... | ... | ... | | dioffx | hxxxx | dataoff_x |

Data

| Data Offset | Data | |-------------|-------| | dataoff1 | LZ41 | | dataoff2 | LZ42 | | dataoff3 | LZ43 | | ... | ... | | dataoffx | LZ4x |

Explanation

A binstore file is split in four sections:

1. The headers. The headers help us identify a binstore file (via the magic number), they allow us to know whether the current binstore engine can read a given binstore file (version number), and when the binstore file was created. We also store the offsets for the other sections and the number of entries stored in this data file.
2. The sparse index. An index of no more than 1-2 MB; the sparse is used to jump into the dense index at roughly the spot where the key we are looking for is located. The sparse index is essential to avoid a full scan.
3. The dense index. In the dense index, there is a mapping from a key (keys are explained below) to the file offset where the set of Values associated with that key is stored. The dense index entries are of fixed sized and are ordered by their keys; this enables binary searching.
4. The data. This is where the actual Values are stored. To save space, we use the LZ4 compression algorithm.

Examples

Query

```rust use std::iter::FromIterator; use std::collections::{BTreeMap, BTreeSet}; use tempfile::NamedTempFile; use binstore::bucket::*;

fn main() { let mut bmap = BTreeMap::new(); for key in 0 .. 100 { bmap.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128))); }

let tmp = NamedTempFile::new().unwrap();
create(tmp.path(), &bmap).expect("create");

{
    let bucket = Bucket::open(tmp.path()).expect("open");
    let mut bucket = bucket.check_headers().expect("check_headers");
    let si = bucket.read_sparse_index().expect("sparse index");

    for (key, actual_values) in &bmap {
        let (offset_1, offset_2) = si.try_get(*key).expect("try_get");
        let values = bucket.try_get(*key, offset_1, offset_2)
            .expect("try_get (1)")
            .expect("try_get (2)");
        assert_eq!(actual_values, &values);
    }
}

} ```

Merge

```rust use std::iter::FromIterator; use std::collections::{BTreeMap, BTreeSet}; use tempfile::NamedTempFile; use binstore::bucket::*;

fn main() { let mut bmap1 = BTreeMap::new(); for key in 0 .. 100 { bmap1.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128))); }

let mut bmap2 = BTreeMap::new();
for key in 0 .. 200 {
    bmap2.insert(key as u64, BTreeSet::from_iter(0 .. (key as u128)));
}

let tmp1 = NamedTempFile::new().unwrap();
let tmp2 = NamedTempFile::new().unwrap();
let merged_file = NamedTempFile::new().unwrap();

create(tmp1.path(), &bmap1).unwrap();
create(tmp2.path(), &bmap2).unwrap();
merge(tmp1.path(), tmp2.path(), merged_file.path()).unwrap();

} ```

More examples will be added to examples/ in the future.