bitcask

README

bitcask

A high performance Key/Value store written in Go with a predictable read/write performance and high throughput. Uses a Bitcask on-disk layout (LSM+WAL) similar to Riak. 🗃️

For a more feature-complete Redis-compatible server, distributed key/value store have a look at Bitraft which uses this library as its backend. Use Bitcask as a starting point or if you want to embed in your application, use Bitraft if you need a complete server/client solution with high availability with a Redis-compatible API.

Features

• Embeddable (import "github.com/prologic/bitcask")
• Builtin CLI (bitcask)
• Builtin Redis-compatible server (bitcaskd)
• Predictable read/write performance
• Low latecny
• High throughput (See: Performance )

Development

1. Get the source

$ git clone https://github.com/prologic/bitcask.git

1. Install required tools

This library uses Protobuf to serialize data on disk. Please follow the instructions for installing protobuf on your system. You will also need the following Go libraries/tools to generate Go code from Protobuf defs:

1. Build the project

$ make

This will invoke go generate and go build.

• protoc-gen-go

Install

$ go get github.com/prologic/bitcask

Usage (library)

Install the package into your project:

$ go get github.com/prologic/bitcask

package main

import "github.com/prologic/bitcask"

func main() {
    db, _ := bitcask.Open("/tmp/db")
    defer db.Close()
    db.Put("Hello", []byte("World"))
    val, _ := db.Get("Hello")
}

See the godoc for further documentation and other examples.

Usage (tool)

$ bitcask -p /tmp/db set Hello World
$ bitcask -p /tmp/db get Hello
World

Usage (server)

There is also a builtin very simple Redis-compatible server called bitcaskd:

$ ./bitcaskd ./tmp
INFO[0000] starting bitcaskd v0.0.7@146f777              bind=":6379" path=./tmp

Example session:

$ telnet localhost 6379
Trying ::1...
Connected to localhost.
Escape character is '^]'.
SET foo bar
+OK
GET foo
$3
bar
DEL foo
:1
GET foo
$-1
PING
+PONG
QUIT
+OK
Connection closed by foreign host.

Docker

You can also use the Bitcask Docker Image:

$ docker pull prologic/bitcask
$ docker run -d -p 6379:6379 prologic/bitcask

Performance

Benchmarks run on a 11" Macbook with a 1.4Ghz Intel Core i7:

$ make bench
...
BenchmarkGet/128B-4         	  500000	      2537 ns/op	     672 B/op	       7 allocs/op
BenchmarkGet/256B-4         	  500000	      2629 ns/op	    1056 B/op	       7 allocs/op
BenchmarkGet/512B-4         	  500000	      2773 ns/op	    1888 B/op	       7 allocs/op
BenchmarkGet/1K-4           	  500000	      3202 ns/op	    3552 B/op	       7 allocs/op
BenchmarkGet/2K-4           	  300000	      3904 ns/op	    6880 B/op	       7 allocs/op
BenchmarkGet/4K-4           	  300000	      5678 ns/op	   14048 B/op	       7 allocs/op
BenchmarkGet/8K-4           	  200000	      8948 ns/op	   27360 B/op	       7 allocs/op
BenchmarkGet/16K-4          	  100000	     14635 ns/op	   53472 B/op	       7 allocs/op
BenchmarkGet/32K-4          	   50000	     28292 ns/op	  114912 B/op	       7 allocs/op

BenchmarkPut/128B-4         	  200000	      8173 ns/op	     409 B/op	       6 allocs/op
BenchmarkPut/256B-4         	  200000	      8404 ns/op	     538 B/op	       6 allocs/op
BenchmarkPut/512B-4         	  200000	      9741 ns/op	     829 B/op	       6 allocs/op
BenchmarkPut/1K-4           	  100000	     13118 ns/op	    1411 B/op	       6 allocs/op
BenchmarkPut/2K-4           	  100000	     17982 ns/op	    2573 B/op	       6 allocs/op
BenchmarkPut/4K-4           	   50000	     35477 ns/op	    5154 B/op	       6 allocs/op
BenchmarkPut/8K-4           	   30000	     54021 ns/op	    9804 B/op	       6 allocs/op
BenchmarkPut/16K-4          	   20000	     96551 ns/op	   18849 B/op	       6 allocs/op
BenchmarkPut/32K-4          	   10000	    129957 ns/op	   41561 B/op	       7 allocs/op

BenchmarkScan-4             	 1000000	      2011 ns/op	     493 B/op	      25 allocs/op

For 128B values:

• ~400,000 reads/sec
• ~130,000 writes/sec

The full benchmark above shows linear performance as you increase key/value sizes.

License

bitcask is licensed under the MIT License

Documentation

Index

• Constants
• Variables
• func Merge(path string, force bool) error
• type Bitcask
  • func Open(path string, options ...Option) (*Bitcask, error)
  • func (b *Bitcask) Close() error
  • func (b *Bitcask) Delete(key string) error
  • func (b *Bitcask) Fold(f func(key string) error) error
  • func (b *Bitcask) Get(key string) ([]byte, error)
  • func (b *Bitcask) Has(key string) bool
  • func (b *Bitcask) Keys() chan string
  • func (b *Bitcask) Len() int
  • func (b *Bitcask) Merge() error
  • func (b *Bitcask) Put(key string, value []byte) error
  • func (b *Bitcask) Scan(prefix string, f func(key string) error) error
  • func (b *Bitcask) Stats() (stats Stats, err error)
  • func (b *Bitcask) Sync() error
• type Option
  • func WithMaxDatafileSize(size int) Option
  • func WithMaxKeySize(size int) Option
  • func WithMaxValueSize(size int) Option
• type Stats

Constants

const (
	// DefaultMaxDatafileSize is the default maximum datafile size in bytes
	DefaultMaxDatafileSize = 1 << 20 // 1MB

	// DefaultMaxKeySize is the default maximum key size in bytes
	DefaultMaxKeySize = 64 // 64 bytes

	// DefaultMaxValueSize is the default value size in bytes
	DefaultMaxValueSize = 1 << 16 // 65KB
)

Variables

var (
	// ErrKeyNotFound is the error returned when a key is not found
	ErrKeyNotFound = errors.New("error: key not found")

	// ErrKeyTooLarge is the error returned for a key that exceeds the
	// maximum allowed key size (configured with WithMaxKeySize).
	ErrKeyTooLarge = errors.New("error: key too large")

	// ErrValueTooLarge is the error returned for a value that exceeds the
	// maximum allowed value size (configured with WithMaxValueSize).
	ErrValueTooLarge = errors.New("error: value too large")

	// ErrChecksumFailed is the error returned if a key/value retrieved does
	// not match its CRC checksum
	ErrChecksumFailed = errors.New("error: checksum failed")

	// ErrDatabaseLocked is the error returned if the database is locked
	// (typically opened by another process)
	ErrDatabaseLocked = errors.New("error: database locked")
)

Functions

func Merge

func Merge(path string, force bool) error

Merge calls Bitcask.Merge() XXX: Deprecated; Please use the `.Merge()` method XXX: This is only kept here for backwards compatibility

it will be removed in future releases at some point

Types

type Bitcask

type Bitcask struct {
	*flock.Flock
	// contains filtered or unexported fields
}

Bitcask is a struct that represents a on-disk LSM and WAL data structure and in-memory hash of key/value pairs as per the Bitcask paper and seen in the Riak database.

func Open

func Open(path string, options ...Option) (*Bitcask, error)

Open opens the database at the given path with optional options. Options can be provided with the `WithXXX` functions that provide configuration options as functions.

func (*Bitcask) Close

func (b *Bitcask) Close() error

Close closes the database and removes the lock. It is important to call Close() as this is the only way to cleanup the lock held by the open database.

func (*Bitcask) Delete

func (b *Bitcask) Delete(key string) error

Delete deletes the named key. If the key doesn't exist or an I/O error occurs the error is returned.

func (*Bitcask) Fold

func (b *Bitcask) Fold(f func(key string) error) error

Fold iterates over all keys in the database calling the function `f` for each key. If the function returns an error, no further keys are processed and the error returned.

func (*Bitcask) Get

func (b *Bitcask) Get(key string) ([]byte, error)

Get retrieves the value of the given key. If the key is not found or an/I/O error occurs a null byte slice is returned along with the error.

func (*Bitcask) Has

func (b *Bitcask) Has(key string) bool

Has returns true if the key exists in the database, false otherwise.

func (*Bitcask) Keys

func (b *Bitcask) Keys() chan string

Keys returns all keys in the database as a channel of string(s)

func (*Bitcask) Len

func (b *Bitcask) Len() int

Len returns the total number of keys in the database

func (*Bitcask) Merge

func (b *Bitcask) Merge() error

Merge merges all datafiles in the database. Old keys are squashed and deleted keys removes. Duplicate key/value pairs are also removed. Call this function periodically to reclaim disk space.

func (*Bitcask) Put

func (b *Bitcask) Put(key string, value []byte) error

Put stores the key and value in the database.

func (*Bitcask) Scan

func (b *Bitcask) Scan(prefix string, f func(key string) error) error

Scan performs a prefix scan of keys matching the given prefix and calling the function `f` with the keys found. If the function returns an error no further keys are processed and the first error returned.

func (*Bitcask) Stats

func (b *Bitcask) Stats() (stats Stats, err error)

Stats returns statistics about the database including the number of data files, keys and overall size on disk of the data

func (*Bitcask) Sync

func (b *Bitcask) Sync() error

Sync flushes all buffers to disk ensuring all data is written

type Option

type Option func(*config) error

Option is a function that takes a config struct and modifies it

func WithMaxDatafileSize

func WithMaxDatafileSize(size int) Option

WithMaxDatafileSize sets the maximum datafile size option

func WithMaxKeySize

func WithMaxKeySize(size int) Option

WithMaxKeySize sets the maximum key size option

func WithMaxValueSize

func WithMaxValueSize(size int) Option

WithMaxValueSize sets the maximum value size option

type Stats

type Stats struct {
	Datafiles int
	Keys      int
	Size      int64
}

Stats is a struct returned by Stats() on an open Bitcask instance