LibraDB

README

LibraDB

LibraDB is a simple, persistent key/value store written in pure Go. The project aims to provide a working yet simple example of a working database. If you're interested in databases, I encourage you to start here.

This database accompanies my blog post on how to write a database from scratch.

Installing

To start using LibraDB, install Go and run go get:

go get -u github.com/amit-davidson/LibraDB

Basic usage

package main

import "github.com/amit-davidson/LibraDB"

func main() {
	path := "libra.db"
	db, _ := LibraDB.Open(path, LibraDB.DefaultOptions)

	tx := db.WriteTx()
	name := []byte("test")
	collection, _ := tx.CreateCollection(name)

	key, value := []byte("key1"), []byte("value1")
	_ = collection.Put(key, value)

	_ = tx.Commit()
}

Transactions

Read-only and read-write transactions are supported. LibraDB allows multiple read transactions or one read-write transaction at the same time. Transactions are goroutine-safe.

LibraDB has an isolation level: Serializable. In simpler words, transactions are executed one after another and not at the same time.This is the highest isolation level.

Read-write transactions

tx := db.WriteTx()
...
if err := tx.Commit(); err != nil {
    return err
}

Read-only transactions

tx := db.ReadTx()
...
if err := tx.Commit(); err != nil {
    return err
}

Collections

Collections are a grouping of key-value pairs. Collections are used to organize and quickly access data as each collection is B-Tree by itself. All keys in a collection must be unique.

tx := db.WriteTx()
collection, err := tx.CreateCollection([]byte("test"))
if err != nil {
	return err
}
_ = tx.Commit()

Auto generating ID

The Collection.ID() function returns an integer to be used as a unique identifier for key/value pairs.

tx := db.WriteTx()
collection, err := tx.GetCollection([]byte("test"))
if err != nil {
    return err
}
id := collection.ID()
_ = tx.Commit()

Key-Value Pairs

Key/value pairs reside inside collections. CRUD operations are possible using the methods Collection.Put Collection.Find Collection.Remove as shown below.

tx := db.WriteTx()
collection, err := tx.GetCollection([]byte("test"))
if  err != nil {
    return err
}

key, value := []byte("key1"), []byte("value1")
if err := collection.Put(key, value); err != nil {
    return err
}
if item, err := collection.Find(key); err != nil {
    return err
}

if err := collection.Remove(key); err != nil {
    return err
}
_ = tx.Commit()

Documentation

Index

• Variables
• func LibraDB()
• type Collection
  • func (c *Collection) Find(key []byte) (*Item, error)
  • func (c *Collection) ID() uint64
  • func (c *Collection) Put(key []byte, value []byte) error
  • func (c *Collection) Remove(key []byte) error
• type DB
  • func Open(path string, options *Options) (*DB, error)
  • func (db *DB) Close() error
  • func (db *DB) ReadTx() *tx
  • func (db *DB) WriteTx() *tx
• type Item
• type Node
  • func NewEmptyNode() *Node
  • func NewNodeForSerialization(items []*Item, childNodes []pgnum) *Node
• type Options

Variables

var DefaultOptions = &Options{
	MinFillPercent: 0.5,
	MaxFillPercent: 0.95,
}

Functions

func LibraDB

func LibraDB()

Types

type Collection

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

func (*Collection) Find

func (c *Collection) Find(key []byte) (*Item, error)

Find Returns an item according based on the given key by performing a binary search.

func (*Collection) ID

func (c *Collection) ID() uint64

func (*Collection) Put

func (c *Collection) Put(key []byte, value []byte) error

Put adds a key to the tree. It finds the correct node and the insertion index and adds the item. When performing the search, the ancestors are returned as well. This way we can iterate over them to check which nodes were modified and rebalance by splitting them accordingly. If the root has too many items, then a new root of a new layer is created and the created nodes from the split are added as children.

func (*Collection) Remove

func (c *Collection) Remove(key []byte) error

Remove removes a key from the tree. It finds the correct node and the index to remove the item from and removes it. When performing the search, the ancestors are returned as well. This way we can iterate over them to check which nodes were modified and rebalance by rotating or merging the unbalanced nodes. Rotation is done first. If the siblings don't have enough items, then merging occurs. If the root is without items after a split, then the root is removed and the tree is one level shorter.

type DB

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

func Open

func Open(path string, options *Options) (*DB, error)

func (*DB) Close

func (db *DB) Close() error

func (*DB) ReadTx

func (db *DB) ReadTx() *tx

func (*DB) WriteTx

func (db *DB) WriteTx() *tx

type Item

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

type Node

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

func NewEmptyNode

func NewEmptyNode() *Node

func NewNodeForSerialization

func NewNodeForSerialization(items []*Item, childNodes []pgnum) *Node

NewNodeForSerialization creates a new node only with the properties that are relevant when saving to the disk

type Options

type Options struct {
	MinFillPercent float32
	MaxFillPercent float32
	// contains filtered or unexported fields
}