CaskDB is a disk-based, embedded, persistent, key-value store based on the Riak's bitcask paper, written in Python.

Overview

CaskDB - Disk based Log Structured Hash Table Store

made-with-python build codecov MIT license

architecture

CaskDB is a disk-based, embedded, persistent, key-value store based on the Riak's bitcask paper, written in Python. It is more focused on the educational capabilities than using it in production. The file format is platform, machine, and programming language independent. Say, the database file created from Python on macOS should be compatible with Rust on Windows.

This project aims to help anyone, even a beginner in databases, build a persistent database in a few hours. There are no external dependencies; only the Python standard library is enough.

If you are interested in writing the database yourself, head to the workshop section.

Features

  • Low latency for reads and writes
  • High throughput
  • Easy to back up / restore
  • Simple and easy to understand
  • Store data much larger than the RAM

Limitations

Most of the following limitations are of CaskDB. However, there are some due to design constraints by the Bitcask paper.

  • Single file stores all data, and deleted keys still take up the space
  • CaskDB does not offer range scans
  • CaskDB requires keeping all the keys in the internal memory. With a lot of keys, RAM usage will be high
  • Slow startup time since it needs to load all the keys in memory

Dependencies

CaskDB does not require any external libraries to run. For local development, install the packages from requirements_dev.txt:

pip install -r requirements_dev.txt

Installation

PyPi is not used for CaskDB yet (issue #5), and you'd have to install it directly from the repository by cloning.

Usage

disk: DiskStorage = DiskStore(file_name="books.db")
disk.set(key="othello", value="shakespeare")
author: str = disk.get("othello")
# it also supports dictionary style API too:
disk["hamlet"] = "shakespeare"

Prerequisites

The workshop is for intermediate-advanced programmers. Knowing Python is not a requirement, and you can build the database in any language you wish.

Not sure where you stand? You are ready if you have done the following in any language:

  • If you have used a dictionary or hash table data structure
  • Converting an object (class, struct, or dict) to JSON and converting JSON back to the things
  • Open a file to write or read anything. A common task is dumping a dictionary contents to disk and reading back

Workshop

NOTE: I don't have any workshops scheduled shortly. Follow me on Twitter for updates. Drop me an email if you wish to arrange a workshop for your team/company.

CaskDB comes with a full test suite and a wide range of tools to help you write a database quickly. A Github action is present with an automated tests runner, code formatter, linter, type checker and static analyser. Fork the repo, push the code, and pass the tests!

Throughout the workshop, you will implement the following:

  • Serialiser methods take a bunch of objects and serialise them into bytes. Also, the procedures take a bunch of bytes and deserialise them back to the things.
  • Come up with a data format with a header and data to store the bytes on the disk. The header would contain metadata like timestamp, key size, and value.
  • Store and retrieve data from the disk
  • Read an existing CaskDB file to load all keys

Tasks

  1. Read the paper. Fork this repo and checkout the start-here branch
  2. Implement the fixed-sized header, which can encode timestamp (uint, 4 bytes), key size (uint, 4 bytes), value size (uint, 4 bytes) together
  3. Implement the key, value serialisers, and pass the tests from test_format.py
  4. Figure out how to store the data on disk and the row pointer in the memory. Implement the get/set operations. Tests for the same are in test_disk_store.py
  5. Code from the task #2 and #3 should be enough to read an existing CaskDB file and load the keys into memory

Use make lint to run mypy, black, and pytype static analyser. Run make test to run the tests locally. Push the code to Github, and tests will run on different OS: ubuntu, mac, and windows.

Not sure how to proceed? Then check the hints file which contains more details on the tasks and hints.

Hints

  • Check out the documentation of struck.pack for serialisation methods in Python
  • Not sure how to come up with a file format? Read the comment in the format module

What next?

I often get questions about what is next after the basic implementation. Here are some challenges (with different levels of difficulties)

Level 1:

  • Crash safety: the bitcask paper stores CRC in the row, and while fetching the row back, it verifies the data
  • Key deletion: CaskDB does not have a delete API. Read the paper and implement it
  • Instead of using a hash table, use a data structure like the red-black tree to support range scans
  • CaskDB accepts only strings as keys and values. Make it generic and take other data structures like int or bytes.

Level 2:

  • Hint file to improve the startup time. The paper has more details on it
  • Implement an internal cache which stores some of the key-value pairs. You may explore and experiment with different cache eviction strategies like LRU, LFU, FIFO etc.
  • Split the data into multiple files when the files hit a specific capacity

Level 3:

  • Support for multiple processes
  • Garbage collector: keys which got updated and deleted remain in the file and take up space. Write a garbage collector to remove such stale data
  • Add SQL query engine layer
  • Store JSON in values and explore making CaskDB as a document database like Mongo
  • Make CaskDB distributed by exploring algorithms like raft, paxos, or consistent hashing

Name

This project was named cdb earlier and now renamed to CaskDB.

Line Count

$ tokei -f format.py disk_store.py
===============================================================================
 Language            Files        Lines         Code     Comments       Blanks
===============================================================================
 Python                  2          391          261          103           27
-------------------------------------------------------------------------------
 disk_store.py                      204          120           70           14
 format.py                          187          141           33           13
===============================================================================
 Total                   2          391          261          103           27
===============================================================================

License

The MIT license. Please check LICENSE for more details.

Owner
I git stuff done
Repository, with small useful and functional applications

Repositorio,com pequenos aplicativos uteis e funcionais A ideia e ir deselvolvendo pequenos aplicativos funcionais e adicionar a este repositorio List

GabrielDuke 6 Dec 06, 2021
An application to see if your Ethereum staking validator(s) are members of the current or next post-Altair sync committees.

eth_sync_committee.py Since the Altair upgrade, 512 validators are randomly chosen every 256 epochs (~27 hours) to form a sync committee. Validators i

4 Oct 27, 2022
An awesome script to convert the University Of Oviedo web calendar to Google or Outlook calendars.

autoUniCalendar Un script en Python para convertir el calendario de la intranet de la Universidad de Oviedo en un calendario de Outlook o Google Calen

Bimo99B9 14 Sep 28, 2022
Python Common things by Problem Fighter Library, (Exception, Debug Log, etc.)

In the name of God, the Most Gracious, the Most Merciful. PF-PY-Common Documentation Install and update using pip: pip install -U xxxx Please find the

Problem Fighter 3 Jan 15, 2022
Class XII computer science project.

Computer Science Project — Class XII Kshitij Srivastava (XI – A) Introduction The aim of this project is to create a fully operational system for a me

Kshitij Srivastava 2 Jul 21, 2022
TrainingBike - Code, models and schematics I've used to interface my stationary training bike with PC.

TrainingBike Code, models and schematics I've used to interface my stationary training bike with PC. You can find more information about the project i

1 Jan 01, 2022
Boamp-extractor - Script d'extraction des AOs publiés au BOAMP

BOAMP Extractor BOAMP-Extractor permet d'extraire les offres de marchés publics publiées au bulletin officiel des annonces des marchés publics (BOAMP)

Julien 3 Dec 09, 2022
Projeto para ajudar no aprendizado da linguagem Pyhon

Economize Este projeto tem o intuito de criar desáfios para a codificação em Python, fazendo com que haja um maior entendimento da linguagem em seu to

Lucas Cunha Rodrigues 1 Dec 16, 2021
Bootstraparse is a personal project started with a specific goal in mind: creating static html pages for direct display from a markdown-like file

Bootstraparse is a personal project started with a specific goal in mind: creating static html pages for direct display from a markdown-like file

1 Jun 15, 2022
This is the Quiz that I made using Python Programming Language. This can only run in the Terminal

This is the Quiz that I made using Python Programming Language. This can only run in the Terminal

YOSHITHA RATHNAYAKE 1 Apr 08, 2022
Kolibri: the offline app for universal education

Kolibri This repository is for software developers wishing to contribute to Kolibri. If you are looking for help installing, configuring and using Kol

Learning Equality 564 Jan 02, 2023
Irrigation Component V4 providing support for a custom card

Irrigation Component V4 This release sees the delivery of a custom card https://github.com/petergridge/irrigation_card to render the program options s

12 Oct 28, 2022
A web project to control the daily life budget planing

Budget Planning - API In this repo there's only the API and Back-End of the this project. Install and run the project # install virtualenv --python=py

Leonardo Da Vinci 1 Oct 24, 2021
Aggressor script that gets the latest commands from CobaltStrikes web site and creates an aggressor script based on tool options.

opsec-aggressor Aggressor script that gets the latest commands from CobaltStrikes opsec page and creates an aggressor script based on tool options. Gr

JP 10 Nov 26, 2022
Check is a integer is even

Is Even Check if interger is even using isevenapi. https://isevenapi.xyz/ Main features: cache memoization api retry handler hide ads Install pip inst

Rosiney Gomes Pereira 45 Dec 19, 2022
ARA Records Ansible and makes it easier to understand and troubleshoot.

ARA Records Ansible ARA Records Ansible and makes it easier to understand and troubleshoot. It's another recursive acronym. What it does Simple to ins

Community managed Ansible repositories 1.6k Dec 25, 2022
A minimal configuration for a dockerized kafka project.

Docker Kafka Quickstart A minimal configuration for a dockerized kafka project. Usage: Run this command to build kafka and zookeeper containers, and c

Nouamane Tazi 5 Jan 12, 2022
A simple program to run through inputs for a 3n+1 problem

Author Tyler Windemuth Collatz_Conjecture A simple program to run through inputs for a 3n+1 problem Purpose: doesn't really have a purpose, did this t

0 Apr 22, 2022
Little tool in python to watch anime from the terminal (the better way to watch anime)

anipy-cli Little tool in python to watch anime from the terminal (the better way to watch anime) Has a resume playback function when picking from Hist

sdao 97 Dec 29, 2022
Team Hash Brown Science4Cast Submission

Team Hash Brown Science4Cast Submission This code reproduces Team Hash Brown's (@princengoc, @Xieyangxinyu) best submission (ee5a) for the competition

3 Feb 02, 2022