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!
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!
Hey arunabha, I appreciate the comment! This isn't my first rodeo as they say :)
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. :)
Thank you for the kind comment! That's great! I do plan on the repository to have a showcase section so when you do get around to get let us know what you build :D
To add to this, I've played around with implementing many more disk based data structures such as BTree, BTree B+Tree, etc and LSM tree is the easiest to work with, optimize, etc. The write speed also is much greater than the b tree and its varients which I like. I will continue to do research on them all as I normally do :P
It’s cool to see new storage engines, thanks for sharing.
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.
Just putting this out there. I will be writing a paper on my experiences writing storage engines and I will be releasing a full website for K4 at k4db.com
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.
Hello everyone! I hope you are all well.
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.
Congratulations on getting this out!
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!
Hey arunabha, I appreciate the comment! This isn't my first rodeo as they say :)
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. :)
Is it a rowstore or a columnstore? Have you considered an HTAP design?
You mentioned thread safe, is it multithreaded so it takes advantage of multiple cores?
Is it a rowstore or a columnstore? Have you considered an HTAP design?
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.
You can use K4 to build a columnar database for sure. It's a storage engine primarily.
Looks pretty great. Will definitely take a serious look at it for future projects. Very happy that it’s in Go, which is our stack.
Thank you for the kind comment! That's great! I do plan on the repository to have a showcase section so when you do get around to get let us know what you build :D
Do you have any regrets about an algorithm/data structure and wish you picked something else?
Absolutely not. I love log structured merge trees and I worked on the algorithms for weeks and I'm fairly confident and happy with them.
To add to this, I've played around with implementing many more disk based data structures such as BTree, BTree B+Tree, etc and LSM tree is the easiest to work with, optimize, etc. The write speed also is much greater than the b tree and its varients which I like. I will continue to do research on them all as I normally do :P
I don't know why star doesn't show above but BTree, BStarTree, BStarPlus tree I meant not "BTree, BTree B+Tree"
It’s cool to see new storage engines, thanks for sharing.
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.
Hey! Thank you for the comment.
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.
Just putting this out there. I will be writing a paper on my experiences writing storage engines and I will be releasing a full website for K4 at k4db.com
Cheers all
Nice work! Any reason why Go was used and not C or Rust? I was under the impression Go would be slower and you are aiming for high performance.
Thank you! I love Go.
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.
This should be a ‘Show HN’?
Hm, possibly. My apologies :)
Keep it coming. I love the work people put on storage engines.
Do you believe a graph storage can be layered on top of K4?
https://medium.com/pinterest-engineering/building-pinterests...
Here is a pretty nice article you could check out. Uses RocksDB but should be fairly similar to setup.
Cheers
Oh yes, for sure!
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
Insane.