keydb

README

keydb

keydb is deprecated, use robaho/leveldb which is more stable and uses the Google LevelDB api (similar).

high performance key value database written in Go

bulk insert and sequential read < 1 micro sec

random access read of disk based record < 4 micro secs

uses LSM trees, see https://en.wikipedia.org/wiki/Log-structured_merge-tree

limitation of max 1024 byte keys, to allow efficient on disk index searching, but has compressed keys which allows for very efficient storage of time series data (market tick data) in the same table

use the dbdump and dbload utilities to save/restore databases to a single file, but just zipping up the directory works as well...

see the related http://github.com/robaho/keydbr which allows remote access to a keydb instance, and allows a keydb database to be shared by multiple processes

TODOs

make some settings configurable

purge removed key/value, it currently stores an empty []byte

How To Use

db, err := keydb.Open("test/mydb", true)
if err != nil {
	t.Fatal("unable to create database", err)
}
tx, err := db.BeginTX("main")
if err != nil {
	t.Fatal("unable to create transaction", err)
}
err = tx.Put([]byte("mykey"), []byte("myvalue"))
if err != nil {
	t.Fatal("unable to put key/Value", err)
}
err = tx.Commit()
if err != nil {
    t.Fatal("unable to commit transaction", err)
}
err = db.Close()
if err != nil {
    t.Fatal("unable to close database", err)
}

Performance

Using example/performance.go

Using Go 1.15.5:

insert time  10000000 records =  17890 ms, usec per op  1.7890143
close time  8477 ms
scan time  2887 ms, usec per op  0.2887559
scan time 50%  81 ms, usec per op  0.162584
random access time  3.508029 us per get
close with merge 1 time  0.148 ms
scan time  2887 ms, usec per op  0.2887248
scan time 50%  85 ms, usec per op  0.171406
random access time  3.487226 us per get

Documentation

Index

• Variables
• func FindNodes(node *node, lower []byte, upper []byte, fn func(*node))
• func IsValidDatabase(path string) error
• func Remove(path string) error
• type Database
  • func Open(path string, createIfNeeded bool) (*Database, error)
  • func (db *Database) BeginTX(table string) (*Transaction, error)
  • func (db *Database) Close() error
  • func (db *Database) CloseWithMerge(segmentCount int) error
• type LookupIterator
• type Transaction
  • func (tx *Transaction) Commit() error
  • func (tx *Transaction) CommitSync() error
  • func (tx *Transaction) Get(key []byte) (value []byte, err error)
  • func (tx *Transaction) GetID() uint64
  • func (tx *Transaction) Lookup(lower []byte, upper []byte) (LookupIterator, error)
  • func (tx *Transaction) Put(key []byte, value []byte) error
  • func (tx *Transaction) Remove(key []byte) ([]byte, error)
  • func (tx *Transaction) Rollback() error
• type Tree
  • func (t *Tree) Find(key []byte) (value []byte, ok bool)
  • func (t *Tree) FindNodes(lower []byte, upper []byte) []TreeEntry
  • func (t *Tree) Insert(key, data []byte)
  • func (t *Tree) Remove(key []byte) (value []byte, ok bool)
• type TreeEntry

Variables

var DatabaseClosed = errors.New("database closed")

var DatabaseHasOpenTransactions = errors.New("database has open transactions")

var DatabaseInUse = errors.New("database in use")

var EmptyKey = errors.New("key is empty")

var EndOfIterator = errors.New("end of iterator")

var KeyNotFound = errors.New("key not found")

var KeyTooLong = errors.New("key too long, max 1024")

var NoDatabaseFound = errors.New("no database found")

var NotADirectory = errors.New("path is not a directory")

var NotValidDatabase = errors.New("path is not a valid database")

var ReadOnlySegment = errors.New("read only segment")

var TransactionClosed = errors.New("transaction closed")

Functions

func FindNodes

func FindNodes(node *node, lower []byte, upper []byte, fn func(*node))

FindNodes calls function fn on nodes with key between lower and upper inclusive

func IsValidDatabase

func IsValidDatabase(path string) error

IsValidDatabase checks if the path points to a valid database or empty directory (which is also valid)

func Remove

func Remove(path string) error

Remove the database, deleting all files. the caller must be able to gain exclusive multi to the database

Types

type Database

type Database struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Database reference is obtained via Open()

func Open

func Open(path string, createIfNeeded bool) (*Database, error)

Open a database. The database can only be opened by a single process, but the *Database reference can be shared across Go routines. The path is a directory name. if createIfNeeded is true, them if the db doesn't exist it will be created Additional tables can be added on subsequent opens, but there is no current way to delete a table, except for deleting the table related files from the directory

func (*Database) BeginTX

func (db *Database) BeginTX(table string) (*Transaction, error)

BeginTX starts a transaction for a database table. a Transaction can only be used by a single Go routine. each transaction should be completed with either Commit, or Rollback

func (*Database) Close

func (db *Database) Close() error

Close the database. any memory segments are persisted to disk. The resulting segments are merged until the default maxSegments is reached

func (*Database) CloseWithMerge

func (db *Database) CloseWithMerge(segmentCount int) error

CloseWithMerge closes the database with control of the segment count. if segmentCount is 0, then the merge process is skipped

type LookupIterator

type LookupIterator interface {
	// returns EndOfIterator when complete, if err is nil, then key and value are valid
	Next() (key []byte, value []byte, err error)
	// contains filtered or unexported methods
}

LookupIterator iterator interface for table scanning. all iterators should be read until completion

type Transaction

type Transaction struct {
	// contains filtered or unexported fields
}

Transaction for keydb operations

func (*Transaction) Commit

func (tx *Transaction) Commit() error

Commit persists any changes to the table. after Commit the transaction can no longer be used

func (*Transaction) CommitSync

func (tx *Transaction) CommitSync() error

CommitSync persists any changes to the table, waiting for disk segment to be written. note that synchronous writes are not used, so that a hard OS failure could leave the database in a corrupted state. after Commit the transaction can no longer be used

func (*Transaction) Get

func (tx *Transaction) Get(key []byte) (value []byte, err error)

Get a value for a key, error is non-nil if the key was not found or an error occurred

func (*Transaction) GetID

func (tx *Transaction) GetID() uint64

GetID returns the internal transaction identifier

func (*Transaction) Lookup

func (tx *Transaction) Lookup(lower []byte, upper []byte) (LookupIterator, error)

Lookup finds matching record between lower and upper inclusive. lower or upper can be nil and and then the range is unbounded on that side. Using the iterator after the transaction has been Commit/Rollback is not supported.

func (*Transaction) Put

func (tx *Transaction) Put(key []byte, value []byte) error

Put a key/value pair into the table, overwriting any existing entry. empty keys are not supported.

func (*Transaction) Remove

func (tx *Transaction) Remove(key []byte) ([]byte, error)

Remove a key and its value from the table. empty keys are not supported.

func (*Transaction) Rollback

func (tx *Transaction) Rollback() error

Rollback discards any changes to the table. after Rollback the transaction can no longer be used

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree is an auto balancing CVL tree, based on code from 'applied go', but modified for []byte key and values, and range searching

func (*Tree) Find

func (t *Tree) Find(key []byte) (value []byte, ok bool)

Find the value for a given key, ok is true if the key was found

func (*Tree) FindNodes

func (t *Tree) FindNodes(lower []byte, upper []byte) []TreeEntry

FindNodes returns a slice of nodes with the keys in range lower and upper inclusive

func (*Tree) Insert

func (t *Tree) Insert(key, data []byte)

Insert a key value pair into the Tree

func (*Tree) Remove

func (t *Tree) Remove(key []byte) (value []byte, ok bool)

Remove the value for a key, returning it. ok is true if the node existed and was found. If the key was not found a 'nil' value is inserted into the tree

type TreeEntry

type TreeEntry struct {
	Key   []byte
	Value []byte
}

TreeEntry is node returned by FindNodes