/silicondb

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

Primary LanguageC++MIT LicenseMIT

silicondb

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

silicondb

Build Status Doxygen docs Publishing Status

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 git@github.com: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.

FOSSA Status

📖 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