go-wiskey

WARNING: When I wrote this, only God and I understood what I was doing. Now, God only knows. It's a working implementation of Wiskey paper but it doesn't support a great concurrency control. also I didn't find an explanation on how Wiskey deletes unused keys from sstables so I made my custom ugly implementation(ask how it works if you are interested) Code is test covered , however, as it was my first big GoLang project I didn't really know how to organize it so right now code is unmaintainable

Golang implementation of a Wiskey paper

Description

Dead simple lsm implementation which stores values in the vlog which decreases write amplification of lsm tree during merging

Things that are implemented

1. SSTable
   • Create sstable
   • Read from sstable
2. Memtable(in memory redblack tree that stores the data and flushes it once memory is full)
   • Put
   • Delete
   • Get
3. Lsm tree
   • Put
   • Get
   • Delete
4. Http interface
   • Http Get
   • Http Put
   • Http Delete
5. Crash recovery
   • Store the last head position in the separate file
   • Store al values from head to tail into the memtable during recovery
6. Merge sstable files
7. Cli interface
   • specify sstable path
   • specify vlog path
   • specify checkpoint path
   • specify memtable size
8. Reclaim space
   • Merge sstables
   • Garbage collect vlog

Install

In order to install the binary run go get github.com/strogiyotec/go-wiskey , it will be installed in $HOME/go/bin/wiskey

Usage

In order to start the app run wiskey -s ../go-wiskey/sstable -v vlog -c checkpoint -m 20 where :

1. -s - directory with sstables
2. -v - path to vlog file(vlog doesn't have to exist)
3. -c - path to checkpoint (checkpoint doesn't have to exist)
4. -m - memtable size in bytes(the size of in memory red black tree that keeps keys , when full will flush this tree to sstable)

It will start an http server

Http server

In order to GET/UPDATE/DELETE you can use http endpoints

1. Save key value
   • curl -X POST -H "Content-Type: application/json" -d '{"value":"Developer"}' http://localhost:8080/anita it will save value Developer with a key anita
2. Get by key - curl -i localhost:8080/fetch/anita
3. Delete by key - curl -X DELETE localhost:8080/anita

How it works

Here is the general image on how the storage works