bundledb

package module
Version: v0.0.0-...-4cb7ada Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 25, 2018 License: MIT Imports: 9 Imported by: 0

README

CircleCI

BundleDB

An embedded DB for Golang with collections that automatically split as they grow.

BundleDB provides several abstractions of common collections which map onto a key-value store. It also looks to optimize reads and writes of collections which have small, nested and/or sequential keys. Writing one big row compared to several smaller rows is more efficient in most KV stores. For this reason, it provides an abstraction which groups keys together.

godoc

Warning

This is pre-Alpha. Don't use it unless you know what you are doing. This has not been used in production and makes no guarantees about performance and stability.

Scalable Collections

The behaviour of collections was roughly inspired by Redis.

  • Collections remain embedded until a certain size.
  • After reaching a limit, the collection will pop out of being embedded into its own shard in the KV store.
  • A shard will split into smaller chunks if it gets too large.

Collection Types

  • Maps
  • Sets
  • Lists (Double-Ended Queue)
  • Timeline (Useful to keep a history with an "active" value)

Architecture

Each bundle is backed by a Primitive that implements an API. The Primitive acts as a Database that assigns a Byte Value to a uint64 Key. Primitives know when to split and when to remain embedded. Bundles are a layer on top of primitives which coordinate fetching them from the database and writing. To implement a new type of bundle, implement the primitive interface.

New Bundle types can be created by composing primitives together (for example, the list type embeds a Map Bundle).

Bundles' Values can be other bundles creating a tree. You can use nested nodes by using the FindMap, FindSet, and FindList methods.

Limitations

Deletion

Bundles will delete themselves if all keys are deleted. However, if you are nesting values, you will need to iterate over the parent bundles and recursively delete the children. There is no current utility to do this because the child topography varies.

Key length

Keys are fixed at 8 bytes. This makes the internals much more streamlined than a dynamic length and makes zero copy reads much easier. Try to design your application around this.

If you need to use larger keys, an example is included in /extra of a ByteTree which implements a ByteSet and a ByteMap. In these the keys are of arbitrary length, but are split into 8 byte chunks to form a tree. A key of 20 Bytes would consist of 3 8 byte keys in 3 nested maps.

Embedded bundles

Bundles will remain embedded until a certain size at which point it will pop out to a single shard. Once a Bundle becomes unembedded, it wont re-embed if values are deleted.

Usage

All bundles start with a Root. Roots live in a key. Roots can be created with GetRootSet, GetRootMap, GetRootList or GetRootBundle. Make sure to defer Close() to clean up any children you accessed. If you make any changes, Commit() will commit the root and all nested bundles that were opened and modified from the root.

Example

package main

import (
    "fmt"
    "github.com/hansonkd/bundledb/store/badger"
    "github.com/hansonkd/bundledb/store"
    bdb "github.com/hansonkd/bundledb"
)

func main() {
    db, _ := badger.OpenBadgerDB("./data")
    defer db.Close()

    db.Update([]byte("partion1"), func(txn *store.Txn) error {
        key := bdb.StrToKey("hello")

        // Sets
        s, _ := bdb.GetRootSet(bdb.StrToKey("setKey"), txn)
        defer s.Close()
        exists, _ := s.Add(key)
        exists, _ = s.Contains(key)
        exists, _ = s.Remove(key)
        s.Commit()


        // Maps
        m, _ := bdb.GetRootMap(bdb.StrToKey("mapKey"), txn)
        defer m.Close()

        exists, _ = m.Insert(key, []byte("world"))
        val, exists, _ := m.Lookup(key)
        exists, _ = m.Delete(key)
        m.Commit()

        fmt.Println(val, exists)

        // Lists
        l, _ := bdb.GetRootList(bdb.StrToKey("listKey"), txn)
        defer l.Close()

        l.RPush([]byte("world"))
        l.LPush([]byte("hello"))
        l.Commit()


        // Bundles can be arbitrarily nested
        n, _ := bdb.GetRootBundle(bdb.StrToKey("nested"), txn)
        defer n.Close()

        nm, _ := n.FindMap(bdb.StrToKey("maps"), bdb.Key(0), bdb.Key(9999))
        nm.Insert(key, []byte("world"))

        ns, _ := n.FindSet(bdb.StrToKey("sets"), bdb.Key(111), bdb.Key(2222))
        ns.Add(key)

        nl, _ := n.FindList(bdb.StrToKey("lists"), bdb.Key(222), bdb.Key(3333))
        nl.RPush([]byte("hello"))

        return n.Commit() // Commits all changes to the nested bundles
    })
}

Documentation

Overview

BundleDB provides several abstractions of common collections which map onto a key-value store. It also looks to optimize reads and writes of collections which have small, nested and/or sequential keys. Writing one big row compared to several smaller rows is more efficient in most KV stores. For this reason, it provides an abstraction which groups keys together.

Index

Constants

View Source
const (
	KeyLength = 8
	MaxKey    = Key(1<<64 - 1)
	MinKey    = Key(0)
)
View Source
const (
	ListLeft  = Key(0)
	ListRight = Key(1)
	ListTree  = Key(2)
	ListStart = MaxKey / 2
)
View Source
const (
	MAX_SHARD_MAP_SIZE     = 10
	MAX_EMBEDDED_MAP_SIZE  = 5
	MAX_EMBEDDED_MAP_BYTES = 1920
)
View Source
const (
	MAX_SHARD_SET_SIZE    = 10
	MAX_EMBEDDED_SET_SIZE = 5
)
View Source
const (
	TimelineCurrent    = Key(0)
	TimelinePast       = Key(1)
	TimelineCurrentKey = Key(2)
)
View Source
const (
	TupleLeft  = Key(0)
	TupleRight = Key(1)
)

Variables

View Source
var (
	InvalidHeader    = errors.New("Invalid Header for object")
	EmbeddedNotFound = errors.New("Invalid Header for object")
	// When using FixMap or FixSet, keys are fixed size and values are in fixed locations so
	// all intermediate nodes are strictly maps.
	MapPaths       = []Decoder{DecodeMap}
	DecodeSet      = setType{}
	DecodeTuple    = tupleType{}
	DecodeMap      = mapType{}
	DecodeList     = listType{}
	DecodeTimeline = timelineType{}
)

Functions

This section is empty.

Types

type Bundle

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

A bundle Represents a collection that has the ability to automatically shard. The underlying datastructure of a Bundle is determined by what Primitive is backing it. A bundle's primitive can be embedded, in which case no additional database fetches happen, or it can be sharded in which case it will go to the database to fetch the key (if the shard isn't in cache already)

func (*Bundle) Delete

func (bndl *Bundle) Delete(key Key) (bool, error)

Delete the value for `key`.

func (*Bundle) FindBundle

func (bndl *Bundle) FindBundle(final Decoder, keys ...Key) (*Bundle, error)

Traverse the keys and assume all intermediate nodes are maps. The last key will populate a bundle with the type of `final` and return.

func (*Bundle) FindBundleWithCycle

func (bndl *Bundle) FindBundleWithCycle(final Decoder, cycle []Decoder, keys ...Key) (*Bundle, error)

Traverse the keys and will cycling through Decoders in cycle for the intermediate nodes, repeating the cycle in a loop until all keys are exhausted.

func (*Bundle) FindList

func (bndl *Bundle) FindList(keys ...Key) (*List, error)

Shortcut to find a List collection

func (*Bundle) FindMap

func (bndl *Bundle) FindMap(keys ...Key) (*Map, error)

Shortcut to find a Map collection

func (*Bundle) FindSet

func (bndl *Bundle) FindSet(keys ...Key) (*Set, error)

Shortcut to find a Set collection

func (*Bundle) FindTimeline

func (bndl *Bundle) FindTimeline(keys ...Key) (*Timeline, error)

Shortcut to find a Timeline collection

func (*Bundle) Iterator

func (bndl *Bundle) Iterator() (BundleIterator, error)

Start a new key Iterator

func (*Bundle) Primitive

func (bndl *Bundle) Primitive(key Key) (Primitive, error)

Retrieve the Primitive for `key`, fetching the shard in the DB if necassary.

func (*Bundle) Read

func (bndl *Bundle) Read(key Key) (Value, bool, error)

Read the value for `key`.

func (*Bundle) Write

func (bndl *Bundle) Write(key Key, value Value) (bool, error)

Write the value for `key`.

type BundleIterator

type BundleIterator interface {
	Next()
	Seek(Key)
	IsValid() bool
	Key() Key
}

func Chain

func Chain(its ...BundleIterator) BundleIterator

Chain should only be used if you can guarantee that each iterator does not have overlapping keys and the min keys of each iterator are sequential.

func Intersect

func Intersect(its ...BundleIterator) BundleIterator

Compute a Set Intersection

func ListIterator

func ListIterator(keys []Key) BundleIterator

Simple Iterator from a slice of keys (Keys should be in order)

func NilIterator

func NilIterator() BundleIterator

func Union

func Union(its ...BundleIterator) BundleIterator

Compute a Set Union

type Decoder

type Decoder interface {
	Table() byte
	NewPrimitive() Primitive
	IsPrimitive([]byte) bool
	IsPointer([]byte) bool
}

Holds information about how to decode a Primitive. These are passed when fetching Bundles, so the Bundle knows how to decode the underlying structure.

type Key

type Key uint64

func BytesToKey

func BytesToKey(keyFull []byte) Key

func StrToKey

func StrToKey(keyFull string) Key

func (Key) Bytes

func (pk Key) Bytes() []byte

func (Key) Next

func (pk Key) Next() Key

func (Key) Serialize

func (pk Key) Serialize(w *bytes.Buffer) int

func (Key) Size

func (pk Key) Size() int

func (Key) ToString

func (pk Key) ToString() string

type List

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

func (*List) Iterator

func (d *List) Iterator() (BundleIterator, error)

func (*List) LPeek

func (d *List) LPeek(index Key) ([]byte, bool, error)

func (*List) LPop

func (d *List) LPop() ([]byte, bool, error)

func (*List) LPush

func (d *List) LPush(val []byte) error

func (*List) RPeek

func (d *List) RPeek(index Key) ([]byte, bool, error)

func (*List) RPop

func (d *List) RPop() ([]byte, bool, error)

func (*List) RPush

func (d *List) RPush(val []byte) error

type Map

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

func (*Map) Delete

func (m *Map) Delete(key Key) (bool, error)

func (*Map) Insert

func (m *Map) Insert(key Key, val []byte) (bool, error)

func (*Map) Iterator

func (m *Map) Iterator() (BundleIterator, error)

func (*Map) Lookup

func (m *Map) Lookup(key Key) ([]byte, bool, error)

type Primitive

type Primitive interface {
	Value

	Max() Key
	Keys() []Key

	Write(Key, Value) bool
	Read(Key) (Value, bool)
	Delete(Key) bool

	// Make a pointer to the shard group. This will be embedded as the bundle's new value
	MakePointer([]byte) []byte
	// Signal that a shard has data that has changed and needs to be commited.
	CanDelete() bool
	// Signal that a shard has data that has changed and needs to be commited.
	IsDirty() bool
	// Signal that the Primitive is too big to be embedded and should be copied to a shard
	CanPopEmbed() bool
	// Signal that a shard has data that has changed and needs to be commited.
	CanSplitShard() bool
	// Split the primitive in 2. The split should place all the highest keys on the object that was called and return a new Primitive with the lowest keys.
	Split() Primitive
	// Typically Primitives can be read in a Zero-Copy fashion through pointer casting. This speeds up reads, but is unsafe.
	FromBytesReadOnly([]byte) error
	// Returns a write-safe copy of the datastructure.
	FromBytesWritable([]byte) error
	// Is a Key in Range of this Primitive's key range
	InRange(Key) bool
}

Primitives are the heart of BundleDB. They define the storage behavior and give the ability to split and shard. Each primitive type has an API much like a DB, you can Write, Read, and Delete values from a primitive. This API gets exposed through a Bundle.

type RawVal

type RawVal []byte

func (RawVal) Bytes

func (v RawVal) Bytes() []byte

func (RawVal) Serialize

func (v RawVal) Serialize(w *bytes.Buffer) int

func (RawVal) Size

func (v RawVal) Size() int

type Root

type Root struct {
	*Bundle
	// contains filtered or unexported fields
}

Root is a top level bundle. Make sure to defer Close() after opening and Commit() any changes that need to be persisted.

func GetRootBundle

func GetRootBundle(root Key, txn *store.Txn) (*Root, error)

func NewRootWithDecoder

func NewRootWithDecoder(root Key, primType Decoder, txn *store.Txn) (*Root, error)

An application will be divided into different Roots. There might be several Root for different indexes and different roots for different collections of data.

func (*Root) Close

func (ctx *Root) Close()

Cleans up any resources that may have been opened by the Bundle or the Bundle's children.

func (*Root) Commit

func (ctx *Root) Commit() error

Commit all changes that occured on this tree. This will also trigger bundles to split if necassary.

type RootList

type RootList struct {
	*List
	// contains filtered or unexported fields
}

func GetRootList

func GetRootList(root Key, txn *store.Txn) (*RootList, error)

func (*RootList) Close

func (m *RootList) Close()

func (*RootList) Commit

func (m *RootList) Commit() error

type RootMap

type RootMap struct {
	*Map
	// contains filtered or unexported fields
}

func GetRootMap

func GetRootMap(root Key, txn *store.Txn) (*RootMap, error)

func (*RootMap) Close

func (m *RootMap) Close()

func (*RootMap) Commit

func (m *RootMap) Commit() error

type RootSet

type RootSet struct {
	*Set
	// contains filtered or unexported fields
}

func GetRootSet

func GetRootSet(root Key, txn *store.Txn) (*RootSet, error)

func (*RootSet) Close

func (m *RootSet) Close()

func (*RootSet) Commit

func (m *RootSet) Commit() error

type RootTimeline

type RootTimeline struct {
	*Timeline
	// contains filtered or unexported fields
}

func GetRootTimeline

func GetRootTimeline(root Key, txn *store.Txn) (*RootTimeline, error)

func (*RootTimeline) Close

func (m *RootTimeline) Close()

func (*RootTimeline) Commit

func (m *RootTimeline) Commit() error

type Set

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

func (*Set) Add

func (m *Set) Add(key Key) (bool, error)

func (*Set) Contains

func (m *Set) Contains(key Key) (bool, error)

func (*Set) Iterator

func (d *Set) Iterator() (BundleIterator, error)

func (*Set) Remove

func (m *Set) Remove(key Key) (bool, error)

type Timeline

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

func (*Timeline) Current

func (d *Timeline) Current() ([]byte, Key, error)

func (*Timeline) Iterator

func (d *Timeline) Iterator() (BundleIterator, error)

func (*Timeline) Past

func (d *Timeline) Past(key Key) ([]byte, bool, error)

func (*Timeline) Set

func (d *Timeline) Set(key Key, val []byte) (bool, error)

func (*Timeline) SetLatest

func (d *Timeline) SetLatest(val []byte) (bool, error)

func (*Timeline) SetNext

func (d *Timeline) SetNext(val []byte) (bool, error)

type UserVal

type UserVal []byte

func (UserVal) Bytes

func (v UserVal) Bytes() []byte

func (UserVal) Serialize

func (v UserVal) Serialize(w *bytes.Buffer) int

func (UserVal) Size

func (v UserVal) Size() int

type Value

type Value interface {
	Size() int
	Bytes() []byte
	Serialize(*bytes.Buffer) int
}

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL