#database-engine #key-value-store #embedded-database #database #atomic #memdb #memodb

async-skipdb

An embedded, in-memory, zero-copy, atomicity, consistency, MVCC, almost lock-free and serializable snapshot isolation database engine

2 releases

0.2.1 Apr 27, 2024
0.2.0 Apr 27, 2024
0.1.5 Apr 25, 2024

#123 in Concurrency

MIT/Apache

300KB
8K SLoC

Async SkipDB

An embedded, in-memory, zero-copy, atomicity, consistency, MVCC, almost lock-free and serializable snapshot isolation database engine.

github Build codecov license

LoC docs.rs crates.io crates.io

English | 简体中文

Introduction

An embedded, in-memory, zero-copy, MVCC, almost lock-free and serializable snapshot isolation database engine.

async-skipdb's SSI (Serializable Snapshot Isolation) transaction model is referenced to foundationdb's paper and badger.

For sync version, please see skipdb.

This crate contains two kinds of in-memory key-value database:

  1. SerializableDb

    Supports both concurrent execution of full serializable snapshot isolation transactions and optimistic concurrency control transactions.

    Transactions are created by SerializableDb::serializable_write can handle all kinds of write skew correctly.

    Transactions are created by SerializableDb::optimistic_write can handle all kinds of direct dependent write skew, but cannot handle all kinds of indirect dependent write skew e.g. https://wiki.postgresql.org/wiki/SSI#Intersecting_Data.

  2. OptimisticDb

    Only support oncurrent execution of optimistic concurrency control, which means the write transaction cannot detect all kinds of write skew.

    All kinds of direct dependent write skew can be handled correctly, but cannot handle all kinds of indirect dependent write skew e.g. https://wiki.postgresql.org/wiki/SSI#Intersecting_Data.

Features

  • Atomicity, Consistency, Isolation, MVCC, concurrent safe and almost lock-free.
  • No extra allocation and copy, there is no Arc wrapper for both key and value stored in the database, which means that users provide K and V, and database store K and V directly.
  • Zero-copy and in-place compaction, which means there is no copy, no extra allocation when compacting.
  • Concurrent execution of transactions, providing serializable snapshot isolation, avoiding write skews.
  • Both read transaction and write transaction are Send + Sync + 'static, which means you do not need to handle annoying lifetime problem anymore.
  • Lock-free and concurrent safe read transaction: the read transaction is totally concurrent safe and can be shared in multiple threads, there is no lock in read transaction.
  • BTreeMap like user friendly API and all iterators implement Iterator trait, which means users use Rust powerful conbinators when iterating over the database.
  • Runtime agnostic, tokio, async-std, smol, wasm-bindgen-futures and any other async runtime.
  • 100% safe, sets [forbid(unsafe_code)].

Installation

  • tokio

    [dependencies]
    async-skipdb = { version = "0.2", features = ["tokio"] }
    
  • async-std

    [dependencies]
    async-skipdb = { version = "0.2", features = ["async-std"] }
    
  • smol

    [dependencies]
    async-skipdb = { version = "0.2", features = ["smol"] }
    
  • wasm-bindgen-futures

    [dependencies]
    async-skipdb = { version = "0.2", features = ["wasm"] }
    

Example

use async_skipdb::serializable::TokioSerializableDb;

#[derive(Debug)]
struct Person {
  name: String,
  hobby: String,
  age: u8,
}

#[tokio::main]
async fn main() {
  let db: TokioSerializableDb<u64, Person> = TokioSerializableDb::new().await;

  {
    let alice = Person { name: "Alice".to_string(), hobby: "swim".to_string(), age: 20 };
    let bob = Person { name: "Bob".to_string(), hobby: "run".to_string(), age: 30 };

    let mut txn = db.serializable_write().await;
    txn.insert(1, alice).unwrap();
    txn.insert(2, bob).unwrap();

    {
      let alice = txn.get(&1).unwrap().unwrap();
      assert_eq!(alice.value().name, "Alice");
      assert_eq!(alice.value().age, 20);
      assert_eq!(alice.value().hobby, "swim");
    }

    txn.commit().await.unwrap();
  }

  {
    let txn = db.read().await;
    let alice = txn.get(&1).unwrap();
    assert_eq!(alice.value().name, "Alice");
    assert_eq!(alice.value().age, 20);
    assert_eq!(alice.value().hobby, "swim");

    let bob = txn.get(&2).unwrap();
    assert_eq!(bob.value().name, "Bob");
    assert_eq!(bob.value().age, 30);
    assert_eq!(bob.value().hobby, "run"); 
  }
}

License

async-skipdb is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2024 Al Liu.

Dependencies

~3–16MB
~202K SLoC