iavl

package
v0.0.0-...-21d70e9 Latest Latest
Warning

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

 Go to latest Published: Apr 25, 2024 License: MIT Imports: 24 Imported by: 1

Documentation

Index

Constants

View Source 
const ProofOpIAVLAbsence = "iavl:a"
View Source 
const ProofOpIAVLValue = "iavl:v"

Variables

View Source 
var (
	// ErrInvalidProof is returned by Verify when a proof cannot be validated.
	ErrInvalidProof = fmt.Errorf("invalid proof")

	// ErrInvalidInputs is returned when the inputs passed to the function are invalid.
	ErrInvalidInputs = fmt.Errorf("invalid inputs")

	// ErrInvalidRoot is returned when the root passed in does not match the proof's.
	ErrInvalidRoot = fmt.Errorf("invalid root")
)
View Source 
var ErrVersionDoesNotExist = errors.New("version does not exist")

ErrVersionDoesNotExist is returned if a requested version does not exist.

Functions

func AbsenceOpDecoder 

func AbsenceOpDecoder(pop merkle.ProofOp) (merkle.ProofOperator, error)

func LoadStore 

func LoadStore(db dbm.DB, id types.CommitID, pruning types.PruningOptions, lazyLoading bool, cache types.SingleStoreCache, iavlCacheSize int64) (types.CommitStore, error)

LoadStore loads the iavl store

func ValueOpDecoder 

func ValueOpDecoder(pop merkle.ProofOp) (merkle.ProofOperator, error)

Types

type AbsenceOp 

type AbsenceOp struct {

	// To encode in ProofOp.Data.
	// Proof is nil for an empty tree.
	// The hash of an empty tree is nil.
	Proof *RangeProof `json:"proof"`
	// contains filtered or unexported fields
}

IAVLAbsenceOp takes a key as its only argument

If the produced root hash matches the expected hash, the proof is good.

func NewAbsenceOp 

func NewAbsenceOp(key []byte, proof *RangeProof) AbsenceOp

func (AbsenceOp) GetKey 

func (op AbsenceOp) GetKey() []byte

func (AbsenceOp) ProofOp 

func (op AbsenceOp) ProofOp() merkle.ProofOp

func (AbsenceOp) Run 

func (op AbsenceOp) Run(args [][]byte) ([][]byte, error)

func (AbsenceOp) String 

func (op AbsenceOp) String() string

type ImmutableTree 

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

ImmutableTree contains the immutable tree at a given version. It is typically created by calling MutableTree.GetImmutable(), in which case the returned tree is safe for concurrent access as long as the version is not deleted via DeleteVersion() or the tree's pruning settings.

Returned key/value byte slices must not be modified, since they may point to data located inside IAVL which would also be modified.

func NewImmutableTree 

func NewImmutableTree(db dbm.DB, cacheSize int) *ImmutableTree

NewImmutableTree creates both in-memory and persistent instances

func NewImmutableTreeWithOpts 

func NewImmutableTreeWithOpts(db dbm.DB, cacheSize int, opts *Options) *ImmutableTree

NewImmutableTreeWithOpts creates an ImmutableTree with the given options.

func (*ImmutableTree) Get 

func (t *ImmutableTree) Get(key []byte) (index int64, value []byte)

Get returns the index and value of the specified key if it exists, or nil and the next index otherwise. The returned value must not be modified, since it may point to data stored within IAVL.

func (*ImmutableTree) GetByIndex 

func (t *ImmutableTree) GetByIndex(index int64) (key []byte, value []byte)

GetByIndex gets the key and value at the specified index.

func (*ImmutableTree) GetRangeWithProof 

func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error)

GetRangeWithProof gets key/value pairs within the specified range and limit.

func (*ImmutableTree) GetWithProof 

func (t *ImmutableTree) GetWithProof(key []byte) (value []byte, proof *RangeProof, err error)

GetWithProof gets the value under the key if it exists, or returns nil. A proof of existence or absence is returned alongside the value.

func (*ImmutableTree) Has 

func (t *ImmutableTree) Has(key []byte) bool

Has returns whether or not a key exists.

func (*ImmutableTree) Hash 

func (t *ImmutableTree) Hash() []byte

Hash returns the root hash.

func (*ImmutableTree) Height 

func (t *ImmutableTree) Height() int8

Height returns the height of the tree.

func (*ImmutableTree) Iterate 

func (t *ImmutableTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)

Iterate iterates over all keys of the tree, in order. The keys and values must not be modified, since they may point to data stored within IAVL.

func (*ImmutableTree) IterateRange 

func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)

IterateRange makes a callback for all nodes with key between start and end non-inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate). The keys and values must not be modified, since they may point to data stored within IAVL.

func (*ImmutableTree) IterateRangeInclusive 

func (t *ImmutableTree) IterateRangeInclusive(start, end []byte, ascending bool, fn func(key, value []byte, version int64) bool) (stopped bool)

IterateRangeInclusive makes a callback for all nodes with key between start and end inclusive. If either are nil, then it is open on that side (nil, nil is the same as Iterate). The keys and values must not be modified, since they may point to data stored within IAVL.

func (*ImmutableTree) RenderShape 

func (t *ImmutableTree) RenderShape(indent string, encoder NodeEncoder) []string

RenderShape provides a nested tree shape, ident is prepended in each level Returns an array of strings, one per line, to join with "\n" or display otherwise

func (*ImmutableTree) Size 

func (t *ImmutableTree) Size() int64

Size returns the number of leaf nodes in the tree.

func (*ImmutableTree) String 

func (t *ImmutableTree) String() string

String returns a string representation of Tree.

func (*ImmutableTree) Version 

func (t *ImmutableTree) Version() int64

Version returns the version of the tree.

type KeyFormat 

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

Provides a fixed-width lexicographically sortable []byte key format

func NewKeyFormat 

func NewKeyFormat(prefix byte, layout ...int) *KeyFormat

Create a []byte key format based on a single byte prefix and fixed width key segments each of whose length is specified by by the corresponding element of layout.

For example, to store keys that could index some objects by a version number and their SHA256 hash using the form: 'c<version uint64><hash [32]byte>' then you would define the KeyFormat with: 

var keyFormat = NewKeyFormat('c', 8, 32)

Then you can create a key with: 

func ObjectKey(version uint64, objectBytes []byte) []byte {
	hasher := sha256.New()
	hasher.Sum(nil)
	return keyFormat.Key(version, hasher.Sum(nil))
}

func (*KeyFormat) Key 

func (kf *KeyFormat) Key(args ...interface{}) []byte

Format the args passed into the key format - will panic if the arguments passed do not match the length of the segment to which they correspond. When called with no arguments returns the raw prefix (useful as a start element of the entire keys space when sorted lexicographically).

func (*KeyFormat) KeyBytes 

func (kf *KeyFormat) KeyBytes(segments ...[]byte) []byte

Format the byte segments into the key format - will panic if the segment lengths do not match the layout.

func (*KeyFormat) Prefix 

func (kf *KeyFormat) Prefix() string

Return the prefix as a string.

func (*KeyFormat) Scan 

func (kf *KeyFormat) Scan(key []byte, args ...interface{})

Extracts the segments into the values pointed to by each of args. Each arg must be a pointer to int64, uint64, or []byte, and the width of the args must match layout.

func (*KeyFormat) ScanBytes 

func (kf *KeyFormat) ScanBytes(key []byte) [][]byte

Reads out the bytes associated with each segment of the key format from key.

type MutableTree 

type MutableTree struct {
	*ImmutableTree // The current, working tree.
	// contains filtered or unexported fields
}

MutableTree is a persistent tree which keeps track of versions. It is not safe for concurrent use, and should be guarded by a Mutex or RWLock as appropriate. An immutable tree at a given version can be returned via GetImmutable, which is safe for concurrent access.

Given and returned key/value byte slices must not be modified, since they may point to data located inside IAVL which would also be modified.

The inner ImmutableTree should not be used directly by callers.

func NewMutableTree 

func NewMutableTree(db dbm.DB, cacheSize int) (*MutableTree, error)

NewMutableTree returns a new tree with the specified cache size and datastore.

func NewMutableTreeWithOpts 

func NewMutableTreeWithOpts(db dbm.DB, cacheSize int, opts *Options) (*MutableTree, error)

NewMutableTreeWithOpts returns a new tree with the specified options.

func (*MutableTree) AvailableVersions 

func (tree *MutableTree) AvailableVersions() []int

AvailableVersions returns all available versions in ascending order

func (*MutableTree) DeleteVersion 

func (tree *MutableTree) DeleteVersion(version int64) error

DeleteVersion deletes a tree version from disk. The version can then no longer be accessed.

func (*MutableTree) DeleteVersions 

func (tree *MutableTree) DeleteVersions(versions ...int64) error

DeleteVersions deletes a series of versions from the MutableTree. An error is returned if any single version is invalid or the delete fails. All writes happen in a single batch with a single commit.

func (*MutableTree) GetImmutable 

func (tree *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)

GetImmutable loads an ImmutableTree at a given version for querying. The returned tree is safe for concurrent access, provided the version is not deleted, e.g. via `DeleteVersion()`.

func (*MutableTree) GetVersioned 

func (tree *MutableTree) GetVersioned(key []byte, version int64) (
	index int64, value []byte,
)

GetVersioned gets the value at the specified key and version. The returned value must not be modified, since it may point to data stored within IAVL.

func (*MutableTree) GetVersionedRangeWithProof 

func (tree *MutableTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) (
	keys, values [][]byte, proof *RangeProof, err error)

GetVersionedRangeWithProof gets key/value pairs within the specified range and limit.

func (*MutableTree) GetVersionedWithProof 

func (tree *MutableTree) GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)

GetVersionedWithProof gets the value under the key at the specified version if it exists, or returns nil.

func (*MutableTree) Hash 

func (tree *MutableTree) Hash() []byte

Hash returns the hash of the latest saved version of the tree, as returned by SaveVersion. If no versions have been saved, Hash returns nil.

func (*MutableTree) IsEmpty 

func (tree *MutableTree) IsEmpty() bool

IsEmpty returns whether or not the tree has any keys. Only trees that are not empty can be saved.

func (*MutableTree) LazyLoadVersion 

func (tree *MutableTree) LazyLoadVersion(targetVersion int64) (*MutableTree, error)

LazyLoadVersion attempts to lazy load only the specified target version without loading previous roots/versions. Lazy loading should be used in cases where only reads are expected. Any writes to a lazy loaded tree may result in unexpected behavior. If the targetVersion is non-positive, the latest version will be loaded by default. If the latest version is non-positive, this method performs a no-op. Otherwise, if the root does not exist, an error will be returned.

func (*MutableTree) Load 

func (tree *MutableTree) Load() (int64, error)

Load the latest versioned tree from disk.

func (*MutableTree) LoadVersion 

func (tree *MutableTree) LoadVersion(targetVersion int64) (int64, error)

Returns the version number of the latest version found

func (*MutableTree) LoadVersionForOverwriting 

func (tree *MutableTree) LoadVersionForOverwriting(targetVersion int64) (int64, error)

LoadVersionForOverwriting attempts to load a tree at a previously committed version, or the latest version below it. Any versions greater than targetVersion will be deleted.

func (*MutableTree) Remove 

func (tree *MutableTree) Remove(key []byte) ([]byte, bool)

Remove removes a key from the working tree. The given key byte slice should not be modified after this call, since it may point to data stored inside IAVL.

func (*MutableTree) Rollback 

func (tree *MutableTree) Rollback()

Rollback resets the working tree to the latest saved version, discarding any unsaved modifications.

func (*MutableTree) SaveVersion 

func (tree *MutableTree) SaveVersion() ([]byte, int64, error)

SaveVersion saves a new tree version to disk, based on the current state of the tree. Returns the hash and new version number.

func (*MutableTree) Set 

func (tree *MutableTree) Set(key, value []byte) bool

Set sets a key in the working tree. Nil values are invalid. The given key/value byte slices must not be modified after this call, since they point to slices stored within IAVL.

func (*MutableTree) String 

func (tree *MutableTree) String() string

String returns a string representation of the tree.

func (*MutableTree) VersionExists 

func (tree *MutableTree) VersionExists(version int64) bool

VersionExists returns whether or not a version exists.

func (*MutableTree) WorkingHash 

func (tree *MutableTree) WorkingHash() []byte

WorkingHash returns the hash of the current working tree.

type Node 

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

Node represents a node in a Tree.

func MakeNode 

func MakeNode(buf []byte) (*Node, error)

MakeNode constructs an *Node from an encoded byte slice.

The new node doesn't have its hash saved or set. The caller must set it afterwards.

func NewNode 

func NewNode(key []byte, value []byte, version int64) *Node

NewNode returns a new node from a key, value and version.

func (*Node) PathToLeaf 

func (node *Node) PathToLeaf(t *ImmutableTree, key []byte) (PathToLeaf, *Node, error)

If the key does not exist, returns the path to the next leaf left of key (w/ path), except when key is less than the least item, in which case it returns a path to the least item.

func (*Node) String 

func (node *Node) String() string

String returns a string representation of the node.

type NodeEncoder 

type NodeEncoder func(id []byte, depth int, isLeaf bool) string

NodeEncoder will take an id (hash, or key for leaf nodes), the depth of the node, and whether or not this is a leaf node. It returns the string we wish to print, for iaviwer

type Options 

type Options struct {
	Sync bool
}

Options define tree options.

func DefaultOptions 

func DefaultOptions() *Options

DefaultOptions returns the default options for IAVL.

type PathToLeaf 

type PathToLeaf []ProofInnerNode

PathToLeaf represents an inner path to a leaf node. Note that the nodes are ordered such that the last one is closest to the root of the tree.

func (PathToLeaf) Index 

func (pl PathToLeaf) Index() (idx int64)

returns -1 if invalid.

func (PathToLeaf) String 

func (pl PathToLeaf) String() string

type ProofInnerNode 

type ProofInnerNode struct {
	Height  int8   `json:"height"`
	Size    int64  `json:"size"`
	Version int64  `json:"version"`
	Left    []byte `json:"left"`
	Right   []byte `json:"right"`
}

func (ProofInnerNode) Hash 

func (pin ProofInnerNode) Hash(childHash []byte) []byte

func (ProofInnerNode) String 

func (pin ProofInnerNode) String() string

type ProofLeafNode 

type ProofLeafNode struct {
	Key       cmn.HexBytes `json:"key"`
	ValueHash cmn.HexBytes `json:"value"`
	Version   int64        `json:"version"`
}

func (ProofLeafNode) Hash 

func (pln ProofLeafNode) Hash() []byte

func (ProofLeafNode) String 

func (pln ProofLeafNode) String() string

type RangeProof 

type RangeProof struct {
	// You don't need the right path because
	// it can be derived from what we have.
	LeftPath   PathToLeaf      `json:"left_path"`
	InnerNodes []PathToLeaf    `json:"inner_nodes"`
	Leaves     []ProofLeafNode `json:"leaves"`
	// contains filtered or unexported fields
}

func (*RangeProof) ComputeRootHash 

func (proof *RangeProof) ComputeRootHash() []byte

ComputeRootHash computes the root hash with leaves. Returns nil if error or proof is nil. Does not verify the root hash.

func (*RangeProof) Keys 

func (proof *RangeProof) Keys() (keys [][]byte)

Keys returns all the keys in the RangeProof. NOTE: The keys here may include more keys than provided by tree.GetRangeWithProof or MutableTree.GetVersionedRangeWithProof. The keys returned there are only in the provided [startKey,endKey){limit} range. The keys returned here may include extra keys, such as: - the key before startKey if startKey is provided and doesn't exist; - the key after a queried key with tree.GetWithProof, when the key is absent.

func (*RangeProof) LeftIndex 

func (proof *RangeProof) LeftIndex() int64

The index of the first leaf (of the whole tree). Returns -1 if the proof is nil.

func (*RangeProof) String 

func (proof *RangeProof) String() string

String returns a string representation of the proof.

func (*RangeProof) StringIndented 

func (proof *RangeProof) StringIndented(indent string) string

func (*RangeProof) Verify 

func (proof *RangeProof) Verify(root []byte) error

Verify that proof is valid.

func (*RangeProof) VerifyAbsence 

func (proof *RangeProof) VerifyAbsence(key []byte) error

Verify that proof is valid absence proof for key. Does not assume that the proof itself is valid. For that, use Verify(root).

func (*RangeProof) VerifyItem 

func (proof *RangeProof) VerifyItem(key, value []byte) error

Also see LeftIndex(). Verify that a key has some value. Does not assume that the proof itself is valid, call Verify() first.

type Store 

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

Store Implements types.KVStore and CommitStore.

func UnsafeNewStore 

func UnsafeNewStore(tree *MutableTree, numRecent int64, storeEvery int64, cache types.SingleStoreCache) *Store

CONTRACT: tree should be fully loaded. nolint: unparam

func (*Store) CacheWrap 

func (st *Store) CacheWrap() types.CacheWrap

Implements Store.

func (*Store) CacheWrapWithTrace 

func (st *Store) CacheWrapWithTrace(w io.Writer, tc types.TraceContext) types.CacheWrap

CacheWrapWithTrace implements the Store interface.

func (*Store) Commit 

func (st *Store) Commit() types.CommitID

Implements Committer.

func (*Store) Delete 

func (st *Store) Delete(key []byte) error

Implements types.KVStore.

func (*Store) Get 

func (st *Store) Get(key []byte) (value []byte, err error)

Implements types.KVStore.

func (*Store) GetStoreType 

func (st *Store) GetStoreType() types.StoreType

Implements Store.

func (*Store) Has 

func (st *Store) Has(key []byte) (exists bool, err error)

Implements types.KVStore.

func (*Store) Iterator 

func (st *Store) Iterator(start, end []byte) (types.Iterator, error)

Implements types.KVStore.

func (*Store) LastCommitID 

func (st *Store) LastCommitID() types.CommitID

Implements Committer.

func (*Store) LazyLoadStore 

func (st *Store) LazyLoadStore(version int64, cache types.SingleStoreCache) (*Store, error)

LoadLazyVersion returns a reference to a new store backed by an immutable IAVL tree at a specific version (height) without any pruning options. This should be used for querying and iteration only. If the version does not exist or has been pruned, an error will be returned. Any mutable operations executed will result in a panic.

func (*Store) Query 

func (st *Store) Query(req abci.RequestQuery) (res abci.ResponseQuery)

Query implements ABCI interface, allows queries

by default we will return from (latest height -1), as we will have merkle proofs immediately (header height = data height + 1) If latest-1 is not present, use latest (which must be present) if you care to have the latest data to see a tx results, you must explicitly set the height you want to see

func (*Store) ReverseIterator 

func (st *Store) ReverseIterator(start, end []byte) (types.Iterator, error)

Implements types.KVStore.

func (*Store) Rollback 

func (st *Store) Rollback(version int64) error

func (*Store) Set 

func (st *Store) Set(key, value []byte) error

Implements types.KVStore.

func (*Store) SetPruning 

func (st *Store) SetPruning(opt types.PruningOptions)

Implements Committer.

func (*Store) VersionExists 

func (st *Store) VersionExists(version int64) bool

VersionExists returns whether or not a given version is stored.

type Tree 

type Tree interface {
	Has(key []byte) bool
	Get(key []byte) (index int64, value []byte)
	Set(key, value []byte) bool
	Remove(key []byte) ([]byte, bool)
	SaveVersion() ([]byte, int64, error)
	DeleteVersion(version int64) error
	Version() int64
	Hash() []byte
	VersionExists(version int64) bool
	GetVersioned(key []byte, version int64) (int64, []byte)
	GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)
	GetImmutable(version int64) (*ImmutableTree, error)
}

Tree defines an interface that both mutable and immutable IAVL trees must implement. For mutable IAVL trees, the interface is directly implemented by an iavl.MutableTree. For an immutable IAVL tree, a wrapper must be made.

type ValueOp 

type ValueOp struct {

	// To encode in ProofOp.Data.
	// Proof is nil for an empty tree.
	// The hash of an empty tree is nil.
	Proof *RangeProof `json:"proof"`
	// contains filtered or unexported fields
}

IAVLValueOp takes a key and a single value as argument and produces the root hash.

If the produced root hash matches the expected hash, the proof is good.

func NewValueOp 

func NewValueOp(key []byte, proof *RangeProof) ValueOp

func (ValueOp) GetKey 

func (op ValueOp) GetKey() []byte

func (ValueOp) ProofOp 

func (op ValueOp) ProofOp() merkle.ProofOp

func (ValueOp) Run 

func (op ValueOp) Run(args [][]byte) ([][]byte, error)

func (ValueOp) String 

func (op ValueOp) String() string

Source Files

View all Source files

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.