bundledb

package module
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
}

Source Files

View all Source files

Directories

Path Synopsis
badger

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.