iavl

package
v0.1.1 Latest Latest
Warning

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

 Go to latest Published: Mar 29, 2023 License: Apache-2.0, Apache-2.0 Imports: 33 Imported by: 0

README

IAVL+ Tree

version license API Reference codecov Lint Test Discord chat

Note: Requires Go 1.13+

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

The purpose of this data structure is to provide persistent storage for key-value pairs (say to store account balances) such that a deterministic merkle root hash can be computed. The tree is balanced using a variant of the AVL algorithm so all operations are O(log(n)).

Nodes of this tree are immutable and indexed by their hash. Thus any node serves as an immutable snapshot which lets us stage uncommitted transactions from the mempool cheaply, and we can instantly roll back to the last committed state to process transactions of a newly committed block (which may not be the same set of transactions as those from the mempool).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

In Ethereum, the analog is Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes -- inner nodes and leaf nodes. On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

Documentation

Overview

Package iavl implements a versioned, snapshottable (immutable) AVL+ tree for persisting key-value pairs.

The tree is not safe for concurrent use, and must be guarded by a Mutex or RWLock as appropriate - the exception is immutable trees returned by MutableTree.GetImmutable() which are safe for concurrent use as long as the version is not deleted via DeleteVersion().

Basic usage of MutableTree: 

import "github.com/okx/okbchain/libs/iavl"
import "github.com/okx/okbchain/libs/tm-db"
...

tree := iavl.NewMutableTree(db.NewMemDB(), 128)

tree.IsEmpty() // true

tree.Set([]byte("alice"), []byte("abc"))
tree.SaveVersion(1)

tree.Set([]byte("alice"), []byte("xyz"))
tree.Set([]byte("bob"), []byte("xyz"))
tree.SaveVersion(2)

tree.LatestVersion() // 2

tree.GetVersioned([]byte("alice"), 1) // "abc"
tree.GetVersioned([]byte("alice"), 2) // "xyz"

Proof of existence: 

root := tree.Hash()
val, proof, err := tree.GetVersionedWithProof([]byte("bob"), 2) // "xyz", RangeProof, nil
proof.Verify([]byte("bob"), val, root) // nil

Proof of absence: 

_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 2) // nil, RangeProof, nil
proof.Verify([]byte("tom"), nil, root) // nil

Now we delete an old version: 

tree.DeleteVersion(1)
tree.VersionExists(1) // false
tree.Get([]byte("alice")) // "xyz"
tree.GetVersioned([]byte("alice"), 1) // nil

Can't create a proof of absence for a version we no longer have: 

_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 1) // nil, nil, error

Index

Examples

Constants

View Source 
const (
	IavlErr   = 0
	IavlInfo  = 1
	IavlDebug = 2
)
View Source 
const (
	FlagIavlCommitIntervalHeight    = "iavl-commit-interval-height"
	FlagIavlMinCommitItemCount      = "iavl-min-commit-item-count"
	FlagIavlHeightOrphansCacheSize  = "iavl-height-orphans-cache-size"
	FlagIavlMaxCommittedHeightNum   = "iavl-max-committed-height-num"
	FlagIavlFastStorageCacheSize    = "iavl-fast-storage-cache-size"
	FlagIavlDiscardFastStorage      = "discard-fast-storage"
	DefaultIavlFastStorageCacheSize = 10000000
)
View Source 
const (
	PreloadConcurrencyThreshold = 4

	PreChangeOpSet    byte = 1
	PreChangeOpDelete byte = 0
	PreChangeNop      byte = 0xFF
)
View Source 
const (
	FlagIavlCacheInitRatio     = "iavl-cache-init-ratio"
	FlagIavlCommitAsyncNoBatch = "iavl-commit-async-no-batch"
)
View Source 
const (
	ANSIReset  = "\x1b[0m"
	ANSIBright = "\x1b[1m"

	ANSIFgGreen = "\x1b[32m"
	ANSIFgBlue  = "\x1b[34m"
	ANSIFgCyan  = "\x1b[36m"
)
View Source 
const (
	FlagOutputModules = "iavl-output-modules"
)
View Source 
const ProofOpIAVLAbsence = "iavl:a"
View Source 
const ProofOpIAVLValue = "iavl:v"

Variables

View Source 
var (
	// ErrVersionDoesNotExist is returned if a requested version does not exist.
	ErrVersionDoesNotExist = errors.New("version does not exist")

	// Parameters below here are changed from cosmos-sdk, controlled by flag
	CommitIntervalHeight      int64 = 100
	MinCommitItemCount        int64 = 500000
	HeightOrphansCacheSize          = 8
	MaxCommittedHeightNum           = minHistoryStateNum
	EnableAsyncCommit               = false
	EnablePruningHistoryState       = true
	CommitGapHeight           int64 = config.DefaultCommitGapHeight

	PruningChannelSize = 10
)
View Source 
var (
	IavlCacheInitRatio     float64 = 0
	IavlCommitAsyncNoBatch bool    = false
)
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 (
	Version = ""
	Commit  = ""
	Branch  = ""
)

Version of iavl. Fill in fields with build flags

View Source 
var ErrNoImport = errors.New("no import in progress")

ErrNoImport is returned when calling methods on a closed importer

View Source 
var ExportDone = errors.New("export is complete") // nolint:golint

ExportDone is returned by Exporter.Next() when all items have been exported.

View Source 
var (
	OutputModules map[string]int
)

Functions

func AbsenceOpDecoder 

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

func Blue 

func Blue(args ...interface{}) string

func ColoredBytes 

func ColoredBytes(data []byte, textColor, bytesColor func(...interface{}) string) string

ColoredBytes takes in the byte that you would like to show as a string and byte and will display them in a human readable format. If the environment variable TENDERMINT_IAVL_COLORS_ON is set to a non-empty string then different colors will be used for bytes and strings.

func Cyan 

func Cyan(args ...interface{}) string

func GetEnableFastStorage 

func GetEnableFastStorage() bool

GetEnableFastStorage get fast storage enable value

func GetFastNodeCacheSize 

func GetFastNodeCacheSize() int

GetFastNodeCacheSize get fast node cache size

func GetFastStorageVersion 

func GetFastStorageVersion(db dbm.DB) (int64, error)

func GetFinalCommitGapOffset 

func GetFinalCommitGapOffset() int64

func GetIgnoreVersionCheck 

func GetIgnoreVersionCheck() bool

func Green 

func Green(args ...interface{}) string

func IsFastStorageStrategy 

func IsFastStorageStrategy(db dbm.DB) bool

IsFastStorageStrategy check the db is FSS

func NewIterator 

func NewIterator(start, end []byte, ascending bool, tree *ImmutableTree) dbm.Iterator

Returns a new iterator over the immutable tree. If the tree is nil, the iterator will be invalid.

func ParseDBName 

func ParseDBName(db dbm.DB) string

func PrintTree 

func PrintTree(tree *ImmutableTree)

PrintTree prints the whole tree in an indented form.

func RegisterWire 

func RegisterWire(cdc *amino.Codec)

func Repair013Orphans 

func Repair013Orphans(db dbm.DB) (uint64, error)

Repair013Orphans repairs incorrect orphan entries written by IAVL 0.13 pruning. To use it, close a database using IAVL 0.13, make a backup copy, and then run this function before opening the database with IAVL 0.14 or later. It returns the number of faulty orphan entries removed. If the 0.13 database was written with KeepEvery:1 (the default) or the last version _ever_ saved to the tree was a multiple of `KeepEvery` and thus saved to disk, this repair is not necessary.

Note that this cannot be used directly on Cosmos SDK databases, since they store multiple IAVL trees in the same underlying database via a prefix scheme.

The pruning functionality enabled with Options.KeepEvery > 1 would write orphans entries to disk for versions that should only have been saved in memory, and these orphan entries were clamped to the last version persisted to disk instead of the version that generated them (so a delete at version 749 might generate an orphan entry ending at version 700 for KeepEvery:100). If the database is reopened at the last persisted version and this version is later deleted, the orphaned nodes can be deleted prematurely or incorrectly, causing data loss and database corruption.

This function removes these incorrect orphan entries by deleting all orphan entries that have a to-version equal to or greater than the latest persisted version. Correct orphans will never have this, since they must have been deleted in a future (non-existent) version for that to be the case.

func SetEnableFastStorage 

func SetEnableFastStorage(enable bool)

SetEnableFastStorage set enable fast storage

func SetFinalCommitGapOffset 

func SetFinalCommitGapOffset(offset int64)

func SetForceReadIavl 

func SetForceReadIavl(enable bool)

SetForceReadIavl force read from iavl

func SetIgnoreAutoUpgrade 

func SetIgnoreAutoUpgrade(enable bool)

func SetIgnoreVersionCheck 

func SetIgnoreVersionCheck(check bool)

func SetLogFunc 

func SetLogFunc(l LogFuncType)

func SetLogger 

func SetLogger(l logger)

func SetProduceDelta 

func SetProduceDelta(pd bool)

func UpdateCommitGapHeight 

func UpdateCommitGapHeight(gap int64)

func ValueOpDecoder 

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

func WriteDOTGraph 

func WriteDOTGraph(w io.Writer, tree *ImmutableTree, paths []PathToLeaf)

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 CommitOrphansImp 

type CommitOrphansImp struct {
	Key         string
	CommitValue int64
}

func (*CommitOrphansImp) MarshalToAmino 

func (ci *CommitOrphansImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

MarshalToAmino marshal data to amino bytes.

func (*CommitOrphansImp) UnmarshalFromAmino 

func (ci *CommitOrphansImp) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

UnmarshalFromAmino unmarshal data from animo bytes.

type ExportNode 

type ExportNode struct {
	Key     []byte
	Value   []byte
	Version int64
	Height  int8
}

ExportNode contains exported node data.

type Exporter 

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

Exporter exports nodes from an ImmutableTree. It is created by ImmutableTree.Export().

Exported nodes can be imported into an empty tree with MutableTree.Import(). Nodes are exported depth-first post-order (LRN), this order must be preserved when importing in order to recreate the same tree structure.

func (*Exporter) Close 

func (e *Exporter) Close()

Close closes the exporter. It is safe to call multiple times.

func (*Exporter) Next 

func (e *Exporter) Next() (*ExportNode, error)

Next fetches the next exported node, or returns ExportDone when done.

type FastIterator 

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

FastIterator is a dbm.Iterator for ImmutableTree it iterates over the latest state via fast nodes, taking advantage of keys being located in sequence in the underlying database.

func (*FastIterator) Close 

func (iter *FastIterator) Close()

Close implements dbm.Iterator

func (*FastIterator) Domain 

func (iter *FastIterator) Domain() ([]byte, []byte)

Domain implements dbm.Iterator. Maps the underlying nodedb iterator domain, to the 'logical' keys involved.

func (*FastIterator) Error 

func (iter *FastIterator) Error() error

Error implements dbm.Iterator

func (*FastIterator) Key 

func (iter *FastIterator) Key() []byte

Key implements dbm.Iterator

func (*FastIterator) Next 

func (iter *FastIterator) Next()

Next implements dbm.Iterator

func (*FastIterator) Valid 

func (iter *FastIterator) Valid() bool

Valid implements dbm.Iterator.

func (*FastIterator) Value 

func (iter *FastIterator) Value() []byte

Value implements dbm.Iterator

type FastIteratorWithCache 

type FastIteratorWithCache struct {
	*UnsavedFastIterator
}

func NewFastIteratorWithCache 

func NewFastIteratorWithCache(start, end []byte, ascending bool, ndb *nodeDB) *FastIteratorWithCache

type FastNode 

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

func DeserializeFastNode 

func DeserializeFastNode(key []byte, buf []byte) (*FastNode, error)

DeserializeFastNode constructs an *FastNode from an encoded byte slice.

func NewFastNode 

func NewFastNode(key []byte, value []byte, version int64) *FastNode

NewFastNode returns a new fast node from a value and version.

type FastNodeCache 

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

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) DebugFssVersion 

func (t *ImmutableTree) DebugFssVersion() ([]byte, error)

Only used for debug!

func (*ImmutableTree) DebugGetNode 

func (t *ImmutableTree) DebugGetNode(nodeHash []byte) *Node

Only used for debug!

func (*ImmutableTree) Export 

func (t *ImmutableTree) Export() *Exporter

Export returns an iterator that exports tree nodes as ExportNodes. These nodes can be imported with MutableTree.Import() to recreate an identical tree.

func (*ImmutableTree) Get 

func (t *ImmutableTree) Get(key []byte) []byte

Get returns the value of the specified key if it exists, or nil. The returned value must not be modified, since it may point to data stored within IAVL. Get potentially employs a more performant strategy than GetWithIndex for retrieving the value.

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) GetMembershipProof 

func (t *ImmutableTree) GetMembershipProof(key []byte) (*ics23.CommitmentProof, error)

func (*ImmutableTree) GetNonMembershipProof 

func (t *ImmutableTree) GetNonMembershipProof(key []byte) (*ics23.CommitmentProof, error)

GetNonMembershipProof will produce a CommitmentProof that the given key doesn't exist in the iavl tree. If the key exists in the tree, this will return an error.

func (*ImmutableTree) GetPersistedRoots 

func (t *ImmutableTree) GetPersistedRoots() map[int64][]byte

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) GetUpgradeVersion 

func (t *ImmutableTree) GetUpgradeVersion() int64

func (*ImmutableTree) GetWithIndex 

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

GetWithIndex 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) 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) GetWithProof2 

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

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) IsFastCacheEnabled 

func (t *ImmutableTree) IsFastCacheEnabled() bool

IsFastCacheEnabled returns true if fast cache is enabled, false otherwise. For fast cache to be enabled, the following 2 conditions must be met: 1. The tree is of the latest version. 2. The underlying storage has been upgraded to fast cache

func (*ImmutableTree) Iterate 

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

Iterate iterates over all keys of the tree. The keys and values must not be modified, since they may point to data stored within IAVL.Returns true if stopped by callback, false otherwise

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) Iterator 

func (t *ImmutableTree) Iterator(start, end []byte, ascending bool) dbm.Iterator

Iterator returns an iterator over the immutable tree.

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) SetUpgradeVersion 

func (t *ImmutableTree) SetUpgradeVersion(version int64)

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 Importer 

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

Importer imports data into an empty MutableTree. It is created by MutableTree.Import(). Users must call Close() when done.

ExportNodes must be imported in the order returned by Exporter, i.e. depth-first post-order (LRN).

Importer is not concurrency-safe, it is the caller's responsibility to ensure the tree is not modified while performing an import.

Example 
tree, err := NewMutableTree(db.NewMemDB(), 0)
if err != nil {
	// handle err
}

tree.Set([]byte("a"), []byte{1})
tree.Set([]byte("b"), []byte{2})
tree.Set([]byte("c"), []byte{3})
_, version, _, err := tree.SaveVersion(false)
if err != nil {
	// handle err
}

itree, err := tree.GetImmutable(version)
if err != nil {
	// handle err
}
exporter := itree.Export()
defer exporter.Close()
exported := []*ExportNode{}
for {
	var node *ExportNode
	node, err = exporter.Next()
	if err == ExportDone {
		break
	} else if err != nil {
		// handle err
	}
	exported = append(exported, node)
}

newTree, err := NewMutableTree(db.NewMemDB(), 0)
if err != nil {
	// handle err
}
importer, err := newTree.Import(version)
if err != nil {
	// handle err
}
defer importer.Close()
for _, node := range exported {
	err = importer.Add(node)
	if err != nil {
		// handle err
	}
}
err = importer.Commit()
if err != nil {
	// handle err
}

Output:

func (*Importer) Add 

func (i *Importer) Add(exportNode *ExportNode) error

Add adds an ExportNode to the import. ExportNodes must be added in the order returned by Exporter, i.e. depth-first post-order (LRN). Nodes are periodically flushed to the database, but the imported version is not visible until Commit() is called.

func (*Importer) Close 

func (i *Importer) Close()

Close frees all resources. It is safe to call multiple times. Uncommitted nodes may already have been flushed to the database, but will not be visible.

func (*Importer) Commit 

func (i *Importer) Commit() error

Commit finalizes the import by flushing any outstanding nodes to the database, making the version visible, and updating the tree metadata. It can only be called once, and calls Close() internally.

type Iterator 

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

Iterator is a dbm.Iterator for ImmutableTree

func (*Iterator) Close 

func (iter *Iterator) Close()

Close implements dbm.Iterator

func (*Iterator) Domain 

func (iter *Iterator) Domain() ([]byte, []byte)

Domain implements dbm.Iterator.

func (*Iterator) Error 

func (iter *Iterator) Error() error

Error implements dbm.Iterator

func (*Iterator) IsFast 

func (iter *Iterator) IsFast() bool

IsFast returnts true if iterator uses fast strategy

func (*Iterator) Key 

func (iter *Iterator) Key() []byte

Key implements dbm.Iterator

func (*Iterator) Next 

func (iter *Iterator) Next()

Next implements dbm.Iterator

func (*Iterator) Valid 

func (iter *Iterator) Valid() bool

Valid implements dbm.Iterator.

func (*Iterator) Value 

func (iter *Iterator) Value() []byte

Value implements dbm.Iterator

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))
}

if the last term of the layout ends in 0

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 LogFuncType 

type LogFuncType func(level int, format string, args ...interface{})

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. Deprecated: please use DeleteVersionsRange instead.

func (*MutableTree) DeleteVersionsRange 

func (tree *MutableTree) DeleteVersionsRange(fromVersion, toVersion int64, enforce ...bool) error

DeleteVersionsRange removes versions from an interval from the MutableTree (not inclusive). An error is returned if any single version has active readers. All writes happen in a single batch with a single commit.

func (*MutableTree) Get 

func (tree *MutableTree) Get(key []byte) []byte

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

func (*MutableTree) GetCommitVersion 

func (tree *MutableTree) GetCommitVersion() int64

func (*MutableTree) GetDBReadCount 

func (tree *MutableTree) GetDBReadCount() int

func (*MutableTree) GetDBReadTime 

func (tree *MutableTree) GetDBReadTime() int

func (*MutableTree) GetDBWriteCount 

func (tree *MutableTree) GetDBWriteCount() int

func (*MutableTree) GetDelta 

func (tree *MutableTree) GetDelta()

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) GetModuleName 

func (tree *MutableTree) GetModuleName() string

func (*MutableTree) GetNodeReadCount 

func (tree *MutableTree) GetNodeReadCount() int

func (*MutableTree) GetUpgradeVersion 

func (tree *MutableTree) GetUpgradeVersion() int64

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) GetVersions 

func (tree *MutableTree) GetVersions() ([]int64, error)

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) Import 

func (tree *MutableTree) Import(version int64) (*Importer, error)

Import returns an importer for tree nodes previously exported by ImmutableTree.Export(), producing an identical IAVL tree. The caller must call Close() on the importer when done.

version should correspond to the version that was initially exported. It must be greater than or equal to the highest ExportNode version number given.

Import can only be called on an empty tree. It is the callers responsibility that no other modifications are made to the tree while importing.

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) IsUpgradeable 

func (tree *MutableTree) IsUpgradeable() bool

Returns true if the tree may be auto-upgraded, false otherwise An example of when an upgrade may be performed is when we are enaling fast storage for the first time or need to overwrite fast nodes due to mismatch with live state.

func (*MutableTree) Iterate 

func (tree *MutableTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)

Iterate iterates over all keys of the tree. The keys and values must not be modified, since they may point to data stored within IAVL. Returns true if stopped by callnack, false otherwise

func (*MutableTree) Iterator 

func (tree *MutableTree) Iterator(start, end []byte, ascending bool) dbm.Iterator

Iterator returns an iterator over the mutable tree. CONTRACT: no updates are made to the tree while an iterator is active.

func (*MutableTree) LazyLoadVersion 

func (tree *MutableTree) LazyLoadVersion(targetVersion int64) (int64, 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) NewBatch 

func (tree *MutableTree) NewBatch() dbm.Batch

func (*MutableTree) PreChanges 

func (tree *MutableTree) PreChanges(keys []string, setOrDel []byte)

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) ResetCount 

func (tree *MutableTree) ResetCount()

func (*MutableTree) Rollback 

func (tree *MutableTree) Rollback()

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

func (*MutableTree) SaveBranch 

func (tree *MutableTree) SaveBranch(batch dbm.Batch, node *Node) []byte

SaveBranch saves the given node and all of its descendants. NOTE: This function clears leftNode/rigthNode recursively and calls _hash() on the given node. TODO refactor, maybe use hashWithCount() but provide a callback.

func (*MutableTree) SaveVersion 

func (tree *MutableTree) SaveVersion(useDeltas bool) ([]byte, int64, TreeDelta, 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) SaveVersionAsync 

func (tree *MutableTree) SaveVersionAsync(version int64, useDeltas bool) ([]byte, int64, error)

func (*MutableTree) SaveVersionSync 

func (tree *MutableTree) SaveVersionSync(version int64, useDeltas bool) ([]byte, int64, error)

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) SetDelta 

func (tree *MutableTree) SetDelta(delta *TreeDelta)

func (*MutableTree) SetInitialVersion 

func (tree *MutableTree) SetInitialVersion(version uint64)

SetInitialVersion sets the initial version of the tree, replacing Options.InitialVersion. It is only used during the initial SaveVersion() call for a tree with no other versions, and is otherwise ignored.

func (*MutableTree) SetUpgradeVersion 

func (tree *MutableTree) SetUpgradeVersion(version int64)

func (*MutableTree) StopTree 

func (tree *MutableTree) StopTree()

func (*MutableTree) StopTreeWithVersion 

func (tree *MutableTree) StopTreeWithVersion(version int64)

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) VersionExistsInDb 

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

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 NodeJsonToNode 

func NodeJsonToNode(nj *NodeJson) *Node

NodeJsonToNode get Node from NodeJson

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 NodeCache 

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

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 NodeJson 

type NodeJson struct {
	Key       []byte `json:"key"`
	Value     []byte `json:"value"`
	Hash      []byte `json:"hash"`
	LeftHash  []byte `json:"left_hash"`
	RightHash []byte `json:"right_hash"`
	Version   int64  `json:"version"`
	Size      int64  `json:"size"`

	Height       int8 `json:"height"`
	Persisted    bool `json:"persisted"`
	PrePersisted bool `json:"pre_persisted"`
	// contains filtered or unexported fields
}

NodeJson provide json Marshal of Node.

func NodeToNodeJson 

func NodeToNodeJson(node *Node) *NodeJson

NodeToNodeJson get NodeJson from Node

func (*NodeJson) MarshalToAmino 

func (nj *NodeJson) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

MarshalToAmino marshal data to amino bytes.

func (*NodeJson) UnmarshalFromAmino 

func (nj *NodeJson) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

UnmarshalFromAmino unmarshal data from amino bytes.

type NodeJsonImp 

type NodeJsonImp struct {
	Key       string
	NodeValue *NodeJson
}

func (*NodeJsonImp) MarshalToAmino 

func (ni *NodeJsonImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

MarshalToAmino marshal data to amino bytes.

func (*NodeJsonImp) UnmarshalFromAmino 

func (ni *NodeJsonImp) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

UnmarshalFromAmino unmarshal data from amino bytes.

type Options 

type Options struct {
	// Sync synchronously flushes all writes to storage, using e.g. the fsync syscall.
	// Disabling this significantly improves performance, but can lose data on e.g. power loss.
	Sync bool

	// InitialVersion specifies the initial version number. If any versions already exist below
	// this, an error is returned when loading the tree. Only used for the initial SaveVersion()
	// call.
	InitialVersion uint64
	UpgradeVersion uint64
}

Options define tree options.

func DefaultOptions 

func DefaultOptions() Options

DefaultOptions returns the default options for IAVL.

type OrphanInfo 

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

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 RuntimeState 

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

type SyncMap 

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

func NewSyncMap 

func NewSyncMap() *SyncMap

func (*SyncMap) Clone 

func (sm *SyncMap) Clone() map[int64]bool

func (*SyncMap) Delete 

func (sm *SyncMap) Delete(key int64)

func (*SyncMap) DeleteWithoutLock 

func (sm *SyncMap) DeleteWithoutLock(key int64)

func (*SyncMap) Get 

func (sm *SyncMap) Get(key int64) bool

func (*SyncMap) Has 

func (sm *SyncMap) Has(key int64) bool

func (*SyncMap) Len 

func (sm *SyncMap) Len() int

func (*SyncMap) Range 

func (sm *SyncMap) Range(f func(key int64, value bool) bool)

func (*SyncMap) Set 

func (sm *SyncMap) Set(key int64, value bool)

type TreeDelta 

type TreeDelta struct {
	NodesDelta         []*NodeJsonImp      `json:"nodes_delta"`
	OrphansDelta       []*NodeJson         `json:"orphans_delta"`
	CommitOrphansDelta []*CommitOrphansImp `json:"commit_orphans_delta"`
}

TreeDelta is the delta for applying on new version tree

func (*TreeDelta) MarshalToAmino 

func (td *TreeDelta) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

func (*TreeDelta) UnmarshalFromAmino 

func (td *TreeDelta) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

type TreeDeltaMap 

type TreeDeltaMap map[string]*TreeDelta

func (TreeDeltaMap) MarshalAmino 

func (tdm TreeDeltaMap) MarshalAmino() ([]*TreeDeltaMapImp, error)

func (TreeDeltaMap) MarshalToAmino 

func (tdm TreeDeltaMap) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

MarshalToAmino marshal to amino bytes

func (TreeDeltaMap) UnmarshalAmino 

func (tdm TreeDeltaMap) UnmarshalAmino(treeDeltaList []*TreeDeltaMapImp) error

func (TreeDeltaMap) UnmarshalFromAmino 

func (tdm TreeDeltaMap) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

UnmarshalFromAmino decode bytes from amino format.

type TreeDeltaMapImp 

type TreeDeltaMapImp struct {
	Key       string
	TreeValue *TreeDelta
}

TreeDeltaMapImp convert map[string]*TreeDelta to struct

func (*TreeDeltaMapImp) MarshalToAmino 

func (ti *TreeDeltaMapImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)

MarshalToAmino marshal data to amino bytes

func (*TreeDeltaMapImp) UnmarshalFromAmino 

func (ti *TreeDeltaMapImp) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error

UnmarshalFromAmino unmarshal data from amino bytes.

type TreeMap 

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

type UnsavedFastIterator 

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

UnsavedFastIterator is a dbm.Iterator for ImmutableTree it iterates over the latest state via fast nodes, taking advantage of keys being located in sequence in the underlying database.

func (*UnsavedFastIterator) Close 

func (iter *UnsavedFastIterator) Close()

Close implements dbm.Iterator

func (*UnsavedFastIterator) Domain 

func (iter *UnsavedFastIterator) Domain() ([]byte, []byte)

Domain implements dbm.Iterator. Maps the underlying nodedb iterator domain, to the 'logical' keys involved.

func (*UnsavedFastIterator) Error 

func (iter *UnsavedFastIterator) Error() error

Error implements dbm.Iterator

func (*UnsavedFastIterator) Key 

func (iter *UnsavedFastIterator) Key() []byte

Key implements dbm.Iterator

func (*UnsavedFastIterator) Next 

func (iter *UnsavedFastIterator) Next()

Next implements dbm.Iterator Its effectively running the constant space overhead algorithm for streaming through sorted lists: the sorted lists being underlying fast nodes & unsavedFastNodeChanges

func (*UnsavedFastIterator) Valid 

func (iter *UnsavedFastIterator) Valid() bool

Valid implements dbm.Iterator.

func (*UnsavedFastIterator) Value 

func (iter *UnsavedFastIterator) Value() []byte

Value implements dbm.Iterator

type UnsavedFastIteratorWithCache 

type UnsavedFastIteratorWithCache struct {
	*UnsavedFastIterator
}

func NewUnsavedFastIteratorWithCache 

func NewUnsavedFastIteratorWithCache(start, end []byte, ascending bool, ndb *nodeDB, fncIn *fastNodeChanges) *UnsavedFastIteratorWithCache

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

type VersionInfo 

type VersionInfo struct {
	IAVL      string `json:"iavl"`
	GitCommit string `json:"commit"`
	Branch    string `json:"branch"`
	GoVersion string `json:"go"`
}

VersionInfo contains useful versioning information in struct

func GetVersionInfo 

func GetVersionInfo() VersionInfo

Returns VersionInfo with global vars filled in

func (VersionInfo) String 

func (v VersionInfo) String() string

Source Files

View all Source files

Directories

Path Synopsis
benchmarks
cosmos-exim
cmd
iaviewer
Package mock is a generated GoMock package.
 Package mock is a generated GoMock package.

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.