4 ms·
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
by alexpadula 2y ago
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.
- Genbox 2y agoDo you have any regrets about an algorithm/data structure and wish you picked something else?
- alexpadula 2y agoAbsolutely not. I love log structured merge trees and I worked on the algorithms for weeks and I'm fairly confident and happy with them.
- alexpadula 2y agoTo 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
- alexpadula 2y agoI don't know why star doesn't show above but BTree, BStarTree, BStarPlus tree I meant not "BTree, BTree B+Tree"
- arunabha 2y agoCongratulations 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!
- alexpadula 2y agoHey 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. :)
- relistan 2y agoLooks pretty great. Will definitely take a serious look at it for future projects. Very happy that it’s in Go, which is our stack.
- alexpadula 2y agoThank 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
- gregw2 2y agoIs 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?
- alexpadula 2y agoIs 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.
- alexpadula 2y agoYou can use K4 to build a columnar database for sure. It's a storage engine primarily.