This Key-Value Engine is a data storage system that utilizes advanced algorithms and data structures to efficiently manage and retrieve data using key-value pairs. It has been developed as part of the "Advanced Algorithms and Data Structures" course on the Faculty of Tehnical Sciencies, Novi Sad. The engine is implemented in the programing language Golang as a console application enabling user interaction.
Basic Operations:
PUT(key, value): Adds a new entry into the system. The key is a string, and the value is a byte array.
GET(key) -> value: Retrieves the value associated with the given key.
DELETE(key): Deletes the entry associated with the provided key.
Write path:
1.) Logging data in the commit log
2.) Writing data to the memtable
3.) Flushing data from the memtable
4.) Storing data on disk in SSTables
Read path:
1.) When a user sends a GET request, we first check if the record exists in the Memtable structure
(if it does, we return the response).
2.) After that, we check if the record exists in the Cache structure (if it does, we return the response).
3.) Next, we check each SSTable structure one by one by loading its Bloom Filter and querying if the key is present.
If it is not, we move on to the next SSTable. If it might be, we need to check the remaining structures
of the current table.
- Bloom Filter - implemented by cofi420 & natasakasikovic
- Count Min Sketch - implemented by MilicMilosRS & anasinik
- Hyper Log Log - implemented by draganjordanovic
- SimHash - implemented by cofi420 & natasakasikovic
- B-Tree - implemented by MilicMilosRS
- Skip List - implemented by anasinik
- Memtable - implemented by draganjordanovic
- Write Ahead Log - implemented by cofi420
- Sorted Strings Table - implemented by anasinik & natasakasikovic
- Merkle Tree - implemented by natasakasikovic
- LRU Cache - implemented by cofi420
- Token bucket - implemented by cofi420
- LSM Tree - implemented by MilicMilosRS