K4 – High performance open-source transactional, durable embedded storage engine
github.com
github.com
I've been working on a few storage engine designs recently implementing an LSM tree and would like to share K4.
K4 is a storage engine written completely in GO with no dependencies. The write speed surpasses RocksDB (7.8.3) with similar configuration.
I will write way more comprehensive benchmarks down the line.
The current features of K4
------------------------------
- High speed writes and reads
- Durability
- Variable length binary keys and values. Keys and their values can be any length
- Write-Ahead Logging (WAL). System writes PUT and DELETE operations to a log file before applying them to the LSM tree.
- Atomic transactions. Multiple PUT and DELETE operations can be grouped together and applied atomically to the LSM tree.
- Paired compaction. SSTables are paired up during compaction and merged into a single SSTable(s). This reduces the number of SSTables and minimizes disk I/O for read operations.
- Memtable implemented as a skip list.
- In-memory and disk-based storage
- Configurable memtable flush threshold
- Configurable compaction interval (in seconds)
- Configurable logging
- Configurable skip list
- Bloom filter for faster lookups. SSTable initial pages contain a bloom filter. The system uses the bloom filter to determine if a key is in the SSTable before scanning the SSTable.
- Recovery from WAL
- Granular page locking
- Thread-safe
- TTL (time to live) support
- Optional compression support (Simple lightweight and optimized Lempel-Ziv 1977 inspired compression algorithm
- Range and equi functionality (Get, NGet, Range, NRange, GreaterThan, GreaterThanEq, LessThan, LessThanEq)
- No dependencies
I am in the process of writing a C binding for K4 which will enable me to write FFI's for multiple other languages like Python, Node.JS, Ruby, etc.
I hope you get a chance to check it out and do let me know your thoughts!
Thank you kindly.
You will inevitably face a lot of the typical questions like 'Why not just use RocksDB', 'Why is this necessary' etc. All I'd say is, don't get disheartened if/when that happens.
Maintaining an open source project is not easy and is often thankless, plus it takes a huge effort to get something of this complexity done. Thanks you for the effort!
I love, love, love programming and have for over 15 years, nothing will change that. I enjoy sharing my ideas, and am a big open-source enthusiast. It's a good thing trying to be innovate. :)
You mentioned thread safe, is it multithreaded so it takes advantage of multiple cores?
It's a storage engine that offer's a key value type store.
You mentioned thread safe, is it multithreaded so it takes advantage of multiple cores?
Threadsafe as in multiple threads can access an instance at the same time with no harm.
For transaction, how are conflicts on concurrent transaction handled? What’s the ordering? Are you considering any conditional check operation like compare-and-swap? For example I think Deno KV’s API where each value has a versionstamp and for transactions there’s an operation CHECK(key, versionstamp) that cancels the transaction if key doesn’t have the given versionstamp at the time of transaction.
It's first come first serve. If there are say 2 transactions, a and b. If b commits before a, b will supersede a in regards to an atomic bunch(operations in a single unit of work). The way it works is a transaction will block the memtable whilst it completes its operations and its first come first serve based on which commits first (FCFS).
I did not want to implement MVCC nor a complex transaction scheme as I designed everything else to be quite simple.
Do you believe a graph storage can be layered on top of K4?
You can build a columnar db, graph db, document db. Absolutely, with ease! Maybe I'll write a tutorial on how to get started :D
https://medium.com/@fithis2001/ingesting-the-omdb-dataset-fc...
I may take time to experiment. Lucky to know some Golang.
Do let me know how your experience with K4 is, if you do end up experimenting. I'm always striving to make it the best it can possibly be. :) I'm open to opinions, new features etc.
Cheers
Here is a pretty nice article you could check out. Uses RocksDB but should be fairly similar to setup.
Cheers
Cheers all
I've implemented various storage engines and data structures in C and C++. For this specific storage engine, I chose Go because I had previously developed a similar engine called TidesDB in C++. While K4 has a similar feature set, it outperforms TidesDB.
Although Go can be slower than languages like C, Rust, and C++, it avoids the complexity of manual memory management and intricate optimizations that can introduce performance overhead. Go allows for a more approachable development experience, enabling you to focus on higher-level constructs without getting bogged down in low-level details, ultimately making it easier to optimize and write less buggy code.