mkvs

package
v0.2103.0 Latest Latest
Warning

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

Go to latest
Published: Sep 27, 2021 License: Apache-2.0 Imports: 14 Imported by: 0

Documentation

Overview

Package mkvs provides a Merklized Key-Value Store (MKVS) implementation.

Index

Constants

View Source
const MaxPrefetchDepth = 255

MaxPrefetchDepth is the maximum depth of the prefeteched tree.

Variables

View Source
var (
	// ErrClosed is the error returned when methods are used after Close is called.
	ErrClosed = errors.New("mkvs: tree is closed")

	// ErrKnownRootMismatch is the error returned by CommitKnown when the known
	// root mismatches.
	ErrKnownRootMismatch = errors.New("mkvs: known root mismatch")
)

Functions

This section is empty.

Types

type ClosableTree

type ClosableTree interface {
	// Close releases resources associated with this tree. After calling this
	// method the tree MUST NOT be used anymore and all methods will return
	// the ErrClosed error.
	//
	// Any pending write operations are discarded. If you need to persist them
	// you need to call Commit before calling this method.
	Close()
}

ClosableTree is a tree interface that can be closed.

type CommitOption added in v0.2010.0

type CommitOption func(o *commitOptions)

CommitOption is an option that can be specified during Commit.

func NoPersist added in v0.2010.0

func NoPersist() CommitOption

NoPersist returns a commit option that makes the Commit only compute all the hashes but does not actually persist any roots in the database. All dirty data remains in memory.

type ImmutableKeyValueTree

type ImmutableKeyValueTree interface {
	// Get looks up an existing key.
	Get(ctx context.Context, key []byte) ([]byte, error)

	// NewIterator returns a new iterator over the tree.
	NewIterator(ctx context.Context, options ...IteratorOption) Iterator
}

ImmutableKeyValueTree is the immutable key-value store tree interface.

type Iterator

type Iterator interface {
	// Valid checks whether the iterator points to a valid item.
	Valid() bool
	// Err returns an error in case iteration failed due to an error.
	Err() error
	// Rewind moves the iterator to the first key in the tree.
	Rewind()
	// Seek moves the iterator either at the given key or at the next larger
	// key.
	Seek(node.Key)
	// Next advances the iterator to the next key.
	Next()
	// Key returns the key under the iterator.
	Key() node.Key
	// Value returns the value under the iterator.
	Value() []byte
	// GetProof builds a proof for all items iterated over by the iterator.
	//
	// You must initialize the iterator with a WithProof option, otherwise
	// calling this method will panic.
	GetProof() (*syncer.Proof, error)
	// GetProofBuilder returns the proof builder associated with this iterator.
	GetProofBuilder() *syncer.ProofBuilder
	// Close releases resources associated with the iterator.
	//
	// Not calling this method leads to memory leaks.
	Close()
}

Iterator is a tree iterator.

Iterators are not safe for concurrent use.

type IteratorOption

type IteratorOption func(it Iterator)

IteratorOption is a configuration option for a tree iterator.

func IteratorPrefetch

func IteratorPrefetch(prefetch uint16) IteratorOption

IteratorPrefetch sets the number of next elements to prefetch.

If no prefetch is specified, no prefetching will be done.

func WithProof

func WithProof(root hash.Hash) IteratorOption

WithProof configures the iterator for generating proofs of all visited nodes.

type KeyValueTree

type KeyValueTree interface {
	ImmutableKeyValueTree

	// Insert inserts a key/value pair into the tree.
	Insert(ctx context.Context, key, value []byte) error

	// RemoveExisting removes a key from the tree and returns the previous value.
	RemoveExisting(ctx context.Context, key []byte) ([]byte, error)

	// Remove removes a key from the tree.
	Remove(ctx context.Context, key []byte) error
}

KeyValueTree is the key-value store tree interface.

type Option

type Option func(t *tree)

Option is a configuration option used when instantiating the tree.

func Capacity

func Capacity(nodeCapacity, valueCapacityBytes uint64) Option

Capacity sets the capacity of the in-memory cache.

If no capacity is specified, the cache will have a maximum capacity of 16MB for values and 5000 for nodes.

If a capacity of 0 is specified, the cache will have an unlimited size (not recommended, as this will cause unbounded memory growth).

func WithoutWriteLog

func WithoutWriteLog() Option

WithoutWriteLog disables building a write log when performing operations.

Note that this option cannot be used together with specifying a ReadSyncer and trying to use it with a tree that also specifies a non-nil ReadSyncer will cause a panic.

type OverlayTree

type OverlayTree interface {
	KeyValueTree
	ClosableTree

	// Commit commits any modifications to the underlying tree.
	Commit(ctx context.Context) error
}

OverlayTree is an overlay tree.

func NewOverlay

func NewOverlay(inner Tree) OverlayTree

NewOverlay creates a new key-value tree overlay that holds all updates in memory and only commits them if requested. This can be used to create snapshots that can be discarded.

While updates (inserts, removes) are stored in the overlay, reads are not cached in the overlay as the inner tree has its own cache and double caching makes less sense.

The overlay is not safe for concurrent use.

type Tree

type Tree interface {
	KeyValueTree
	ClosableTree
	syncer.ReadSyncer

	// PrefetchPrefixes populates the in-memory tree with nodes for keys
	// starting with given prefixes.
	PrefetchPrefixes(ctx context.Context, prefixes [][]byte, limit uint16) error

	// ApplyWriteLog applies the operations from a write log to the current tree.
	//
	// The caller is responsible for calling Commit.
	ApplyWriteLog(ctx context.Context, wl writelog.Iterator) error

	// CommitKnown checks that the computed root matches a known root and
	// if so, commits tree updates to the underlying database and returns
	// the write log.
	//
	// In case the computed root doesn't match the known root, the update
	// is NOT committed and ErrKnownRootMismatch is returned.
	CommitKnown(ctx context.Context, root node.Root) (writelog.WriteLog, error)

	// Commit commits tree updates to the underlying database and returns
	// the write log and new merkle root.
	Commit(ctx context.Context, namespace common.Namespace, version uint64, options ...CommitOption) (writelog.WriteLog, hash.Hash, error)

	// DumpLocal dumps the tree in the local memory into the given writer.
	DumpLocal(ctx context.Context, w io.Writer, maxDepth node.Depth)

	// RootType returns the storage root type.
	RootType() node.RootType
}

Tree is a general MKVS tree interface.

func New

func New(rs syncer.ReadSyncer, ndb db.NodeDB, rootType node.RootType, options ...Option) Tree

New creates a new empty MKVS tree backed by the given node database.

func NewWithRoot

func NewWithRoot(rs syncer.ReadSyncer, ndb db.NodeDB, root node.Root, options ...Option) Tree

NewWithRoot creates a new MKVS tree with an existing root, backed by the given node database.

Directories

Path Synopsis
Package checkpoint provides methods for creating MKVS checkpoints.
Package checkpoint provides methods for creating MKVS checkpoints.
db
api
Package api provides a persistent node database interface for MKVS trees.
Package api provides a persistent node database interface for MKVS trees.
badger
Package badger provides a Badger-backed node database.
Package badger provides a Badger-backed node database.
MKVS interoperability test helpers.
MKVS interoperability test helpers.
cmd
Package cmd implements the commands for MKVS interoperability test helpers.
Package cmd implements the commands for MKVS interoperability test helpers.
Package node defines MKVS tree nodes.
Package node defines MKVS tree nodes.
Package syncer provides the read-only sync interface.
Package syncer provides the read-only sync interface.
Package tests contains helpers for testing MKVS trees.
Package tests contains helpers for testing MKVS trees.

Jump to

Keyboard shortcuts

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