Documentation
¶
Overview ¶
Package mkvs provides a Merklized Key-Value Store (MKVS) implementation.
Index ¶
Constants ¶
const MaxPrefetchDepth = 255
MaxPrefetchDepth is the maximum depth of the prefeteched tree.
Variables ¶
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 WithProofBuilder ¶ added in v0.2400.0
func WithProofBuilder(pb *syncer.ProofBuilder) IteratorOption
WithProofBuilder configures the iterator for generating proofs of all visited nodes with the given proof builder.
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 ¶
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
// Copy creates an isolated copy of the overlay tree.
//
// The passed tree is used as the underlying tree of the copy.
//
// In case the passed tree is nil, the underlying tree is shared by both copies (e.g. both
// copies commit to and read from the same tree instance).
Copy(inner KeyValueTree) OverlayTree
// Commit commits any modifications to the underlying tree.
//
// Returns the underlying tree on success.
Commit(ctx context.Context) (KeyValueTree, error)
}
OverlayTree is an overlay tree.
func NewOverlay ¶
func NewOverlay(inner KeyValueTree) 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.
func NewOverlayWrapper ¶ added in v0.2300.0
func NewOverlayWrapper(inner Tree) OverlayTree
NewOverlayWrapper wraps an existing tree so it can behave as an overlay tree without any actual overlay overhead.
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 NewWithRoot ¶
NewWithRoot creates a new MKVS tree with an existing root, backed by the given node database.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
Package checkpoint provides methods for creating MKVS checkpoints.
|
Package checkpoint provides methods for creating MKVS checkpoints. |
|
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. |
|
pathbadger
Package pathbadger provides a Badger-backed node database that uses trie paths as keys.
|
Package pathbadger provides a Badger-backed node database that uses trie paths as keys. |
|
testing
Package testing provides helpers for running node database tests.
|
Package testing provides helpers for running node database tests. |
|
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. |