1 stable release
1.0.0 | Dec 2, 2022 |
---|
#108 in Database implementations
1MB
16K
SLoC
RainDB
A persistent key-value store based on an LSM tree implemented in Rust
Motivation and goals
This project serves more as a toy project and tool for learning about database internals. As such, the code will be annotated as much as possible. We aim to achieve high readability via well structured code, eschew "elegant" tricks, and by having redundant documentation. Concepts and reasoning are expounded upon in the design docs, the generated API docs, and inline with the code. Whether your best mode of learning is through reading code or through reading docs, information is often repeated in multiple areas to make following along easier.
RainDB does not aim to be high performance nor aim to have binary compatibility with LevelDB. These things would be nice side-effects though 😀. Despite not aiming for binary compatibility, the behaviors are largely the same (i.e. a direct port) and the same test cases from LevelDB are used to check this conformance.
High Level Design
RainDB's storage engine is an LSM tree and has/will have the traditional components that come from the fact:
- Memtable - Initially a skip list but will be swappable in the future with other data structures
- Table files
- Write-ahead log
As can be seen from the list above, RainDB's LSM tree is a two-layer system with an in-memory memtable and table files persistable to a single storage medium. The table file store can be on disk but an in-memory store is also provided (and usually used for testing purposes).
See the docs folder for more information on architecture and design.
Usage
use raindb::{DbOptions, ReadOptions, WriteOptions, DB};
// Use the default options to create a database that uses disk to store table files
let options = DbOptions {
create_if_missing: true,
..DbOptions::default()
};
// Optionally handle any errors that can occur when opening the database
let db = DB::open(options).unwrap();
db.put(
WriteOptions::default(),
"some_key".into(),
"some_value".into(),
).unwrap();
let read_result = db.get(ReadOptions::default(), "some_key".as_bytes()).unwrap();
Using an in-memory store
use raindb::{DbOptions, DB};
use raindb::fs::{FileSystem, InMemoryFileSystem};
let options = DbOptions {
create_if_missing: true,
..DbOptions::with_memory_env()
};
// OR
let mem_fs: Arc<dyn FileSystem> = Arc::new(InMemoryFileSystem::new());
let options = DbOptions {
filesystem_provider: Arc::clone(&mem_fs),
create_if_missing: true,
..DbOptions::default()
};
let db = DB::open(options).unwrap();
Other usage examples
The examples folder has some examples of how to embed RainDB in an application. I
usually hate having to look through source code for examples but the
db/db_test.rs
module contains a lot of example usage of the public API.
Pedigree
The work here builds heavily on the existing work of LevelDB. A big thank you goes to the creators for making so much of their design documentation available alongside the code itself. Because of the heavy basis in this project, some of the options and documentation is pulled directly from it.
Inspiration was also drawn from the Go port of LevelDB and dermesser's Rust port.
A Legacy
heading will be present in doc comments where tactical decisions were made to differ from
LevelDB. This can include name changes so that parallels can still be drawn between RainDB and
LevelDB.
A lot of the tests are also taken from LevelDB to ensure behavioral fidelity.
Other art
Future ideas
- Use as part of a distributed store with Raft for leader election
- Add data sharding
References
- Aside from the docs folder, more notes and references for various components can also be found on my blog
- Database Internals by Alex Petrov
- Oren Eini - Blog Series - Reviewing LevelDB
- MrCroxx - Blog Series
- This is in Chinese but Google translate actually does a good job here. Only skimmed a bit of the compaction article but it was very well done and seems like a great learning resource for understanding LevelDB.
Disclaimer
This is not an officially supported Google product.
Dependencies
~4–12MB
~153K SLoC