baradb

README

baradb

baradb is a Key/Value storage engine based on Bitcask model, which is a log-structured storage.

bara: バラ, Japanese name of rose

Design Overview

WRITE:

1. Append a log record to the current active log file
2. Update the index

READ:

1. Find the position in the index by the given key
2. If the position is found, then find the value of the given key in a log file by the position

References

1. Bitcask: A Log-Structured Hash Table for Fast Key/Value Data

Install

$ go get -u github.com/saint-yellow/baradb

Usage

Basic Operations

// launch a DB engine 
opts := baradb.DefaultDBOptions
db, err := baradb.Launch(opts)
if err != nil {
    panic(err)
}

// put a key/value pair to the DB engine
err = db.Put([]byte("114514"), []byte("1919810"))
if err != nil {
    panic(err)
}

// get vlue of a key from the DB engine  
value, err := db.Get([]byte("114514"))
if err != nil {
    panic(err)
}
fmt.Println(string(value))

// delete a key/value pair from the DB engine
err = db.Delete([]byte("114514"))
if err != nil {
    panic(err)
}

Batch Operations

// initialze a write batch
wb := db.NewWriteBatch(baradb.DefaultWriteBatchOptions)

// put a key/value pair to the write batch 
err = wb.Put([]byte("1919"), []byte("1919"))
if err != nil {
    panic(err)
}

// the DB engine will not store data in the write batch 
// since the write batch is not committed
value, err = db.Get([]byte("1919"))
if err != nil {
    panic(err)
}
fmt.Println(string(value))

// delete a key/value pair in the write batch 
err = wb.Delete([]byte("114514"))
if err != nil {
    panic(err)
}

// commit the write batch 
err = wb.Commit()
if err != nil {
    panic(err)
}

// the DB engine can get data in the write batch 
// that is successfully committed
value, err = db.Get([]byte("1919"))
if err != nil {
    panic(err)
}
fmt.Println(string(value))

Features

Strengths

• Low latency per item read or written
• High throughput, especially when writing an incoming stream of random items
• Ability to handle datasets larger than RAM without degradation
• Single seek to retrieve any value
• Predictable lookup and insert performance
• Easy backup
• Batch options which guarantee atomicity, consistency, and durability
• Support iterator for forward and backward

Weaknesses

• Keys must fit in memory
• Startup speed is affected by the amount of data

Applications

Integrate HTTP into the K/V storage engine

• Case: baradb-http

Implement Redis on the top of the K/V storage engine

• Case: baradb-redis

And... More!

Contributing

PRs accepted.

License

MIT © Saint-Yellow

Documentation

Index

• Variables
• type DB
  • func Launch(options DBOptions) (*DB, error)
  • func (db *DB) Backup(directory string) error
  • func (db *DB) Close() error
  • func (db *DB) Delete(key []byte) error
  • func (db *DB) Fold(fn userOperationFunc) error
  • func (db *DB) Fork(directory string) (*DB, error)
  • func (db *DB) Get(key []byte) ([]byte, error)
  • func (db *DB) ListKeys() [][]byte
  • func (db *DB) Merge() error
  • func (db *DB) NewItrerator(options index.IteratorOptions) *Iterator
  • func (db *DB) NewWriteBatch(options WriteBatchOptions) *WriteBatch
  • func (db *DB) Put(key, value []byte) error
  • func (db *DB) Stat() *Stat
  • func (db *DB) Sync() error
• type DBOptions
• type Iterator
  • func (it *Iterator) Close()
  • func (it *Iterator) Key() []byte
  • func (it *Iterator) Next()
  • func (it *Iterator) Rewind()
  • func (it *Iterator) Seek(key []byte)
  • func (it *Iterator) Valid() bool
  • func (it *Iterator) Value() ([]byte, error)
• type Stat
  • func (s Stat) String() string
• type WriteBatch
  • func (wb *WriteBatch) Commit() error
  • func (wb *WriteBatch) Delete(key []byte) error
  • func (wb *WriteBatch) Put(key, value []byte) error
• type WriteBatchOptions

Variables

var (
	ErrKeyIsEmpty                = errors.New("the key is empty")
	ErrIndexUpdateFailed         = errors.New("failed to update index")
	ErrFileNotFound              = errors.New("file not found")
	ErrKeyNotFound               = errors.New("key not found")
	ErrDirectoryIsEmpty          = errors.New("data path is empty")
	ErrMaxDataFileSizeIsNegative = errors.New("the maximum size of data file is negative")
	ErrDirectoryCorrupted        = errors.New("maybe the directory of the DB is corrupted")
	ErrExceedMaxBatchNumber      = errors.New("exceed the maximum batch number")
	ErrMergenceIsInProgress      = errors.New("mergence is in progress, try again later")
	ErrDatabaseIsUsed            = errors.New("the database is used by other process")
	ErrInvalidMergenceThreshold  = errors.New("invalid mergence threshold")
	ErrNoMoreDiskSpace           = errors.New("no more disk space to store data")
)

User-defined errors

var (
	// DefaultDBOptions Default options for launching DB engine
	DefaultDBOptions = DBOptions{
		Directory:       "/tmp/baradb",
		MaxDataFileSize: 512 * 1024 * 1024,
		SyncWrites:      false,
		IndexType:       index.ARtree,
		MMapAtStartup:   false,
	}
	// DefaultWriteBatchOptions Default options for batch writing
	DefaultWriteBatchOptions = WriteBatchOptions{
		MaxBatchNumber: 100,
		SyncWrites:     true,
	}
)

Types

type DB

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

DB represents a baradb engine

func Launch

func Launch(options DBOptions) (*DB, error)

Launch launches a DB engine instance

func (*DB) Backup

func (db *DB) Backup(directory string) error

Backup copies the DB's data files to a given directory.

NOTE: only data files will be copied, other files like tran-no, flock will be ignored.

func (*DB) Close

func (db *DB) Close() error

Close closes the DB engine

func (*DB) Delete

func (db *DB) Delete(key []byte) error

Delete Delete data by the given key

func (*DB) Fold

func (db *DB) Fold(fn userOperationFunc) error

Fold retrieves all the data and iteratively executes an user-specified operation (UDF) Once the UDF failed, the iteration will stop intermediatelly

func (*DB) Fork

func (db *DB) Fork(directory string) (*DB, error)

Fork creates a new DB engine instance mainly for merging data

func (*DB) Get

func (db *DB) Get(key []byte) ([]byte, error)

Get Reads data from the DB engine by a given key

func (*DB) ListKeys

func (db *DB) ListKeys() [][]byte

ListKeys gets all keys in the DB engine

func (*DB) Merge

func (db *DB) Merge() error

Merge clears invalid data files and generates hint files

func (*DB) NewItrerator

func (db *DB) NewItrerator(options index.IteratorOptions) *Iterator

NewItrerator initializes an iterator of DB engine

func (*DB) NewWriteBatch

func (db *DB) NewWriteBatch(options WriteBatchOptions) *WriteBatch

NewWriteBatch initializes a write batch in the DB engine

func (*DB) Put

func (db *DB) Put(key, value []byte) error

Put Writes data to the DB engine

func (*DB) Stat

func (db *DB) Stat() *Stat

Stat returns statistical information of the DB engine

func (*DB) Sync

func (db *DB) Sync() error

Sync persistence of data in active data file of the DB engine

type DBOptions

type DBOptions struct {
	// Directory of a DB engine instance where data files are stored in
	Directory string

	// Maximum size of every single data file (uint: Byte).
	//
	// It should be greater than 0.
	MaxDataFileSize int64

	// SyncWrites indicates whether persist data after writing
	SyncWrites bool

	// IndexType indicates the type of the index of the DB engine
	IndexType index.IndexType

	// SyncThreshold indicates a threshold for persisting data.
	//
	// It should equals 0 or be greater than 0 (uint: Byte).
	//
	// When the DB engine wrote bytes more than this threshold, the DB engine will sync the wirtten bytes to the acitve data file.
	SyncThreshold uint

	// MMapAtStartup indicates whether load memory mapping while starting up the DB engine
	MMapAtStartup bool

	// MergenceThreshold indicates a threshold for merging data.
	//
	// When proportion of the invalid data in the DB engine is greater than this threshold,
	// the DB engine will merge all its data.
	//
	// The value of this threshold should be between 0 and 1.
	//
	// If the value is 0, then this threshold is disabled and the DB engine will not merge its data.
	MergenceThreshold float64
}

Options represents options of a DB engine instance

type Iterator

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

Iterator an iterator of DB

func (*Iterator) Close

func (it *Iterator) Close()

func (*Iterator) Key

func (it *Iterator) Key() []byte

func (*Iterator) Next

func (it *Iterator) Next()

func (*Iterator) Rewind

func (it *Iterator) Rewind()

func (*Iterator) Seek

func (it *Iterator) Seek(key []byte)

func (*Iterator) Valid

func (it *Iterator) Valid() bool

func (*Iterator) Value

func (it *Iterator) Value() ([]byte, error)

type Stat

type Stat struct {
	KeyNumber       uint  `json:"keyNumber"`       // Number of key(s) in the DB engine
	DataFileNumber  uint  `json:"dataFileNumber"`  // Number of data file(s) in the DB engine
	ReclaimableSize int64 `json:"reclaimableSize"` // Amount of mergable data (unit: byte)
	DiskSize        int64 `json:"diskSize"`        // Size of the DB engine occuppied in disk (unit: byte)
}

Stat represents statistical information of a DB engine

func (Stat) String

func (s Stat) String() string

type WriteBatch

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

WriteBatch A transaction that batch writes data and makes sure atomicity

func (*WriteBatch) Commit

func (wb *WriteBatch) Commit() error

Commit commits the transaction, writes the pending data to the disk and updates the in-memory index

func (*WriteBatch) Delete

func (wb *WriteBatch) Delete(key []byte) error

Delete deletes data

func (*WriteBatch) Put

func (wb *WriteBatch) Put(key, value []byte) error

Put writes data

type WriteBatchOptions

type WriteBatchOptions struct {
	MaxBatchNumber int  // Maximum amount of data in one batch
	SyncWrites     bool // Sync data after writing if true
}

WriteBatchOptions options for batch writing