/wiskey

Golang implementation of Wiskey paper

Primary LanguageGoGNU General Public License v3.0GPL-3.0

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 storage