solidstatedb / silicondb

A concurrent key-value store, column-oriented database and more.

silicondb

A concurrent key value store, column oriented database and more.

Overview

silicondb was a project created to understand how modern NoSQL scalable distributed databases work. In particular, the author intends to learn how to implement lock-free data structures, log-structured merge trees, column-oriented data storage, Merkle trees and data replication at scale.

This project doesn't aim to compete with existing NoSQL databases and does not provide any novel feature addressing a particular pain point. However, we plan to provide implementations of wait-free simulated lock-free data structures. (See references) This project aims to be a scalable, robust alternative to modern databases with production-level code.

silicondb prioritizes efficiency on SSDs. Hence we focus on log-structured merge trees as the driving data-storage data structure instead of b-trees.

Apart from API Documentation, we describe the implementation of certain aspects of silicondb in the Wiki.

💻 Storage Engine modules

• A concurrent in memory map implemented as a hashtable.
• A lock-free variant of the map mentioned above.
• A wait-free simulation of the lock-free map.
• A lock-free concurrent SSTable simulated in a wait-free manner.
• Compaction operations on SSTable.
• Column oriented storage support. (Needs further elaboration)
• Content correctness verification and replication using merkle trees for SSTable and Column oriented storage.
• Message sequencing with merkle trees.

🏂 Features

• Partial implementation of the Redis protocol:
  • Key, Value retreival
  • Key Ranged operations
• REST API server for accessing data.
• CAP compliant.

🏗️ Build Instructions

Pre-requisites

• gcc-9.3+
• cmake

git clone [email protected]:arindas/silicondb.git
cd silicondb
cmake -S . -B build/

This produces a binary build/silicondb which is the silicondb daemon server.

🧪 Testing

cd build && ctest

This should run all tests.

License

silicondb is licensed under the MIT License See LICENSE for the full license text.

📖 References

• [Book] C++ Concurrency in Action - Anthony Williams - Manning Publications. ISBN: 978-1-933-98877-1
• [Book] Designing Data Intensive Applications - Martin Kleppmann - Oreilly. ISBN: 978-1-449-37332-0
• [Paper] A Practical Wait-Free Simulation for Lock-Free Data Structures http://dx.doi.org/10.1145/2555243.2555261

silicondb's Issues

Create a basic online password manager once the Bitcask paper is implemented.

Features requested:

• Key / Value password storage, both keys and passwords are encrypted with a master password
• JWT based authenticated REST server with endpoints for storing and retrieving password
• React frontend preferably hosted on GitHub pages in a separate repo. The frontend should be able to specify the IP of the password manager server

A functional implementation of the bitcask paper.

https://riak.com/assets/bitcask-intro.pdf

The following goals are proposed:

• Implement data persistence with log-structured key-value files
• Implement merging and compaction operations
• Use the concurrent map implementation as a hash index
• Present a REST server to interact with the db. Endpoints suggested:
  - GET /key
  - POST /key?value=<value>

Add a contains() method to silicondb::map

Add a new method to silicondb::map :

// map::contains(): returns true if the map contains a value mapped to the given key, false otherwise.
template <typename Key, typename Value, typename Hash = std::hash<Key>>
bool silicondb::map::contains(Key const& key) { ... }

The implementation will require adding a contains() method for map::bucket. We simply need to check whether, in the bucket mapped to the hash, there is an entry with the given key or not. (Hint: use find_entry_for)