• Stars
    star
    266
  • Rank 154,103 (Top 4 %)
  • Language
    Rust
  • License
    Apache License 2.0
  • Created about 3 years ago
  • Updated about 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

A pure Rust database implementation using an append-only B-Tree file format.

Nebari

nebari forbids unsafe code nebari is considered alpha crate version Live Build Status HTML Coverage Report for main branch Documentation for main branch

nebari - noun - the surface roots that flare out from the base of a bonsai tree

This crate provides the Roots type, which is the transactional storage layer for BonsaiDb. It is loosely inspired by Couchstore.

This crate blocks the current thread when accessing the filesystem. If you are looking for an async-ready database, BonsaiDb is our vision of an async-aware database built atop Nebari.

This crate is alpha. While its format is considered stable, there may be bugs that could lead to data loss. Please have a good backup strategy while using this crate.

Examples

Inserting a key-value pair in an on-disk tree with full revision history:

use nebari::{
    tree::{Root, Versioned},
    Config,
};

let database_folder = tempfile::tempdir().unwrap();
let roots = Config::default_for(database_folder.path())
    .open()
    .unwrap();
let tree = roots.tree(Versioned::tree("a-tree")).unwrap();
tree.set("hello", "world").unwrap();

For more examples, check out nebari/examples/.

Features

Nebari exposes multiple levels of functionality. The lowest level functionality is the TreeFile. A TreeFile is a key-value store that uses an append-only file format for its implementation.

Using TreeFiles and a transaction log, Roots enables ACID-compliant, multi-tree transactions.

Each tree supports:

  • Key-value storage: Keys can be any arbitrary byte sequence up to 65,535 bytes long. For efficiency, keys should be kept to smaller lengths. Values can be up to 4 gigabytes (2^32 bytes) in size.
  • Flexible query options: Fetch records one key at a time, multiple keys at once, or ranges of keys.
  • Powerful multi-key operations: Internally, all functions that alter the data in a tree use TreeFile::modify() which allows operating on one or more keys and performing various operations.
  • Pluggable low-level modifications: The Vault trait allows you to bring your own encryption, compression, or other functionality to this format. Each independently-addressible chunk of data that is written to the file passes through the vault.
  • Optional full revision history. If you don't want to lose old revisions of data, you can use a VersionedTreeRoot to store information that allows scanning old revision information. Or, if you want to avoid the extra IO, use the UnversionedTreeRoot which only stores the information needed to retrieve the latest data in the file.
  • ACID-compliance:
    • Atomicity: Every operation on a TreeFile is done atomically. Operation::CompareSwap can be used to perform atomic operations that require evaluating the currently stored value.

    • Consistency: Atomic locking operations are used when publishing a new transaction state. This ensures that readers can never operate on a partially updated state.

    • Isolation: Currently, each tree can only be accessed exclusively within a transaction. This means that if two transactions request the same tree, one will execute and complete before the second is allowed access to the tree. This strategy could be modified in the future to allow for more flexibility.

    • Durability: The append-only file format is designed to only allow reading data that has been fully flushed to disk. Any writes that were interrupted will be truncated from the end of the file.

      Transaction IDs are recorded in the tree headers. When restoring from disk, the transaction IDs are verified with the transaction log. Because of the append-only format, if we encounter a transaction that wasn't recorded, we can continue scanning the file to recover the previous state. We do this until we find a successfluly commited transaction.

      This process is much simpler than most database implementations due to the simple guarantees that append-only formats provide.

Why use an append-only file format?

@ecton wasn't a database engineer before starting this project, and depending on your viewpoint may still not be considered a database engineer. Implementing ACID-compliance is not something that should be attempted lightly.

Creating ACID-compliance with append-only formats is much easier to achieve, however, as long as you can guarantee two things:

  • When opening a previously existing file, can you identify where the last valid write occurred?
  • When writing the file, do not report that a transaction has succeeded until the file is fully flushed to disk.

The B-Tree implementation in Nebari is designed to offer those exact guarantees.

The major downside of append-only formats is that deleted data isn't cleaned up until a maintenance process occurs: compaction. This process rewrites the file's contents, skipping over entries that are no longer alive. This process can happen without blocking the file from being operated on, but it does introduce IO overhead during the operation.

Nebari provides APIs that perform compaction, but currently delegates scheduling and automation to consumers of this library.

Open-source Licenses

This project, like all projects from Khonsu Labs, are open-source. This repository is available under the MIT License or the Apache License 2.0.

To learn more about contributing, please see CONTRIBUTING.md.

More Repositories

1

bonsaidb

A developer-friendly document database that grows with you, written in Rust
Rust
1,018
star
2

cushy

An experimental cross-platform graphical user interface (GUI) crate for Rust.
Rust
462
star
3

okaywal

A Write Ahead Log (WAL) implementation in Rust
Rust
214
star
4

justjson

An efficient JSON Value parser
Rust
75
star
5

sediment

A low-level MVCC file format for storing blobs.
Rust
63
star
6

kludgine

A kludgey 2d game engine written in Rust atop wgpu
Rust
62
star
7

pot

A concise, self-describing binary format written in Rust for Serde
Rust
53
star
8

budlang

A safe, fast, lightweight embeddable scripting language written in Rust.
Rust
20
star
9

cosmicverge

A systematic, sandbox MMO still in the concept phase. Will be built with Rust atop BonsaiDb and Gooey
HTML
18
star
10

lrumap

A set of safe Least Recently Used (LRU) map/cache types for Rust
Rust
16
star
11

easygpu

A small wrapper around wgpu to make some things simpler
Rust
16
star
12

fabruic

An easy-to-use QUIC-based protocol that supports reliable payload delivery.
Rust
15
star
13

basws

A basis for building an async client-server Websocket protocol
Rust
15
star
14

circulate

Lightweight async PubSub framework
Rust
12
star
15

rsn

Rust
11
star
16

refuse

An easy-to-use, incremental, multi-threaded garbage collector for Rust
Rust
9
star
17

pulldown-cmark-frontmatter

A Frontmatter extractor for Markdown documents built atop pulldown-cmark
Rust
8
star
18

ordered-varint

Variable-length signed and unsigned integer encoding that is byte-orderable for Rust
Rust
8
star
19

transmog

Utilities for serializing with multiple formats of data in Rust.
Rust
8
star
20

figures

A math library specialized for 2d screen graphics.
Rust
8
star
21

delve-rs

A crate search engine powered by Rust and BonsaiDb
Rust
7
star
22

watchable

An observable RwLock-like type for Rust that is compatible with both multi-threaded and async code
Rust
7
star
23

ncog

Rust
7
star
24

alot

A forbid-unsafe, generational slot map with usize-sized IDs
Rust
5
star
25

interner

Rust
5
star
26

nominals

Formatting of nominal identifiers in various languages (ordered list headings)
Rust
5
star
27

muse

Rust
5
star
28

minority-game

A mini-game demo of BonsaiDb + Gooey
Rust
4
star
29

englishid

English formatting for unsigned integer IDs
Rust
4
star
30

rustme

A tool for managing a Rust project's README-like files.
Rust
4
star
31

cityhasher

Rust
4
star
32

custodian

End-user secret management with Rust. Early WIP.
Rust
3
star
33

kempt

A #[forbid_unsafe] ordered collection crate for Rust
Rust
3
star
34

dossier

An artifact server built with BonsaiDb
Rust
3
star
35

gooey-attempt-2

The second attempt at the `gooey` crate for Rust. Never published to crates.io.
Rust
3
star
36

magrathea

A pixel-art-style planet generator
Rust
2
star
37

muse-archive

Virtual instrument synthesizer library for rust built atop cpal
Rust
2
star
38

actionable

An enum-based async framework for building permission-driven APIs
Rust
2
star
39

async-handle

A reference-counted async RwLock for Rust
Rust
2
star
40

easing-function

Rust
2
star
41

pixaxe

A scriptable, indexed pixel art editor written in Rust
Rust
2
star
42

appit

An opinionated wrapper for `winit` utilizing a single-thread-per-window model
Rust
2
star
43

watchfile

An easy-to-use automatic file reloader.
Rust
1
star
44

async-locking-benchmarks

Rust
1
star
45

khonsubase

Khonsubase is a lightweight project management and knowledgebase collaboration tool written in Rust.
HTML
1
star
46

budget-executor

An approach to "throttling" async tasks in Rust using manual instrumentation
Rust
1
star
47

pot-diff

Rust
1
star
48

yew-bulma

Yew wrappers for the Bulma CSS framework
Rust
1
star
49

ncog-archived

A consumer-centric, privacy and safety-forward authentication service written with game developers in mind
CSS
1
star
50

console-thingy

Rust
1
star
51

approximint

A large integer Rust crate using an approximate representation inspired by scientific notation
Rust
1
star
52

FunnyBones

A simple 2D kinematics library for Rust
Rust
1
star
53

cushy-clicker

A proof-of-concept library for creating clicker/incremental games in Rust using Cushy
Rust
1
star
54

gooey-canvas

A Canvas widget for the `Gooey` UI framework
Rust
1
star
55

file-manager

Rust
1
star
56

gooey-attempt-1

The first attempt at the `gooey` crate for Rust. Never published to crates.io.
Rust
1
star