Log structured append-only key-value store from Rust In Action with some enhancements.

Overview

riakv

ci-tests rustdoc License: MIT

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

Features

  • Persistent key value store with a hash table index
  • crc32 checksum validation for every key value pair stored.
  • Optionally, persistent index for fast loading
  • Exhaustive, comprehensive tests

Design enhancements

Generic storage

The underlying storage used by the key value store is completely generic. It is subject to Read + Write + Seek trait bounds.

#[derive(Debug)]
pub struct RiaKV<F>
where
    F: Read + Write + Seek,
{
    f: F,
    pub index: HashMap<ByteString, u64>,
}

This allows for creation of key value store instances from an in-memory buffer:

impl RiaKV<io::Cursor<Vec<u8>>> {
    pub fn open_from_in_memory_buffer(capacity: usize) -> Self {
        RiaKV {
            f: io::Cursor::new(vec![0; capacity]),
            index: HashMap::new(),
        }
    }
}

Refactors in iteration over key value pairs stored in file

Instead of duplicating iteration code in RiaKV::find and RiaKV::load, we refactor the loop into RiaKV::for_each. This method accepts a callback to operate on the key value pair received in every iteration. Finally, the callback returns an enum which specifies how to update the store hashtable index using the key value pair.

This is implemented as follows. First, we have an index operation type:

pub enum IndexOp {
    Insert(KeyValuePair, u64),
    Delete(KeyValuePair, u64),
    End,
    Nop,
}

Next we define the for each function:

pub fn for_each_kv_entry_in_storage<Func>(&mut self, mut callback: Func) -> io::Result<()>
    where
        Func: FnMut(KeyValuePair, u64) -> IndexOp,
    { ...

As we can see the callback take the key value pair, and its position in the file, and returns an index operation. Now in the iteration step, we match on the value returned by the callback and perform the required index operation.

    loop { 

        ...
        
        match callback(kv, position) {
                IndexOp::Insert(kv, position) => {
                    self.index.insert(kv.key, position);
                }
                IndexOp::Delete(kv, _) => {
                    self.index.remove(&kv.key);
                }
                IndexOp::Nop => {}
                IndexOp::End => {
                    break;
                }
            }
        }
        
        ...

This function is used as follows:

pub fn load(&mut self) -> io::Result<()> {
    self.for_each_kv_entry_in_storage(|kv, position| {
        if kv.value.len() > 0 {
            IndexOp::Insert(kv, position)
        } else {
            IndexOp::Delete(kv, position)
        }
    })
}

// ...

pub fn find(&mut self, target: &ByteStr) -> io::Result<Option<(u64, ByteString)>> {
    let mut found: Option<(u64, ByteString)> = None;

    self.for_each_kv_entry_in_storage(|kv, position| {
        if kv.key == target.to_vec() {
            found = Some((position, kv.value));
            IndexOp::End
        } else {
            IndexOp::Nop
        }
    })?;

    Ok(found)
}

Building

After cloning the repository, simply run cargo build --release from the project root. This project provides two binaries riakv_mem and riakv_disk. The _* suffix specifies whether the index is persisted in the disk or not.

License

riakv is licensed under the MIT License. See LICENSE for the full license text.

FOSSA Status

You might also like...
🔥🌲 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

The core innovation of EinsteinDB is its merge-append-commit protocol

The core innovation of EinsteinDB is its merge-append-commit protocol. The protocol is friendly and does not require more than two parties to agree on the order of events. It is also relativistic and can tolerate clock and network lag and drag.

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.

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

A
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

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

Distributed transactional key-value database, originally created to complement TiDB
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

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

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

Comments
Releases(v1.0.0)
  • v1.0.0(Aug 23, 2021)

    • Initial release with core features:
      • [x] Persistent key-value store with a hash table index
      • [x] crc32 checksum validation for every key-value pair stored.
      • [x] Optionally, persistent index for fast loading
      • [x] Exhaustive, comprehensive tests
    • Github actions for tests and rustdocs deployment
    Source code(tar.gz)
    Source code(zip)
Owner
Arindam Das
Specializes in Deep Learning model serving and AI SaaS at scale. Experienced in distributed system design, architecture, and deployment.
Arindam Das
A pure Rust database implementation using an append-only B-Tree file format.

nebari nebari - noun - the surface roots that flare out from the base of a bonsai tree Warning: This crate is early in development. The format of the

Khonsu Labs 194 Jan 3, 2023
A lock-free, append-only atomic pool.

A lock-free, append-only atomic pool. This library implements an atomic, append-only collection of items, where individual items can be acquired and r

Jon Gjengset 64 Oct 24, 2022
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
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
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
A simple embedded key-value store written in rust as a learning project

A simple embedded key-value store written in rust as a learning project

Blobcode 1 Feb 20, 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
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 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