README ¶
IAVL+ Tree
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/okex/exchain/libs/iavl" import "github.com/okex/exchain/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 ¶
- Constants
- Variables
- func AbsenceOpDecoder(pop merkle.ProofOp) (merkle.ProofOperator, error)
- func Blue(args ...interface{}) string
- func ColoredBytes(data []byte, textColor, bytesColor func(...interface{}) string) string
- func Cyan(args ...interface{}) string
- func GetIgnoreVersionCheck() bool
- func Green(args ...interface{}) string
- func ParseDBName(db dbm.DB) string
- func PrintTree(tree *ImmutableTree)
- func RegisterWire(cdc *amino.Codec)
- func Repair013Orphans(db dbm.DB) (uint64, error)
- func SetIgnoreVersionCheck(check bool)
- func SetLogFunc(l LogFuncType)
- func SetLogger(l logger)
- func SetProduceDelta(pd bool)
- func ValueOpDecoder(pop merkle.ProofOp) (merkle.ProofOperator, error)
- func WriteDOTGraph(w io.Writer, tree *ImmutableTree, paths []PathToLeaf)
- type AbsenceOp
- type CommitOrphansImp
- type ExportNode
- type Exporter
- type ImmutableTree
- func (t *ImmutableTree) Export() *Exporter
- func (t *ImmutableTree) Get(key []byte) (index int64, value []byte)
- func (t *ImmutableTree) GetByIndex(index int64) (key []byte, value []byte)
- func (t *ImmutableTree) GetMembershipProof(key []byte) (*ics23.CommitmentProof, error)
- func (t *ImmutableTree) GetNonMembershipProof(key []byte) (*ics23.CommitmentProof, error)
- func (t *ImmutableTree) GetPersistedRoots() map[int64][]byte
- func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error)
- func (t *ImmutableTree) GetUpgradeVersion() int64
- func (t *ImmutableTree) GetWithProof(key []byte) (value []byte, proof *RangeProof, err error)
- func (t *ImmutableTree) GetWithProof2(key []byte) (value []byte, proof *RangeProof, err error)
- func (t *ImmutableTree) Has(key []byte) bool
- func (t *ImmutableTree) Hash() []byte
- func (t *ImmutableTree) Height() int8
- func (t *ImmutableTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *ImmutableTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *ImmutableTree) IterateRangeInclusive(start, end []byte, ascending bool, ...) (stopped bool)
- func (t *ImmutableTree) RenderShape(indent string, encoder NodeEncoder) []string
- func (t *ImmutableTree) SetUpgradeVersion(version int64)
- func (t *ImmutableTree) Size() int64
- func (t *ImmutableTree) String() string
- func (t *ImmutableTree) Version() int64
- type Importer
- type KeyFormat
- type LogFuncType
- type MutableTree
- func (tree *MutableTree) AvailableVersions() []int
- func (tree *MutableTree) DeleteVersion(version int64) error
- func (tree *MutableTree) DeleteVersions(versions ...int64) error
- func (tree *MutableTree) DeleteVersionsRange(fromVersion, toVersion int64, enforce ...bool) error
- func (tree *MutableTree) GetCommitVersion() int64
- func (tree *MutableTree) GetDBReadCount() int
- func (tree *MutableTree) GetDBReadTime() int
- func (tree *MutableTree) GetDBWriteCount() int
- func (tree *MutableTree) GetDelta()
- func (tree *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)
- func (tree *MutableTree) GetModuleName() string
- func (tree *MutableTree) GetNodeReadCount() int
- func (tree *MutableTree) GetUpgradeVersion() int64
- func (tree *MutableTree) GetVersioned(key []byte, version int64) (index int64, value []byte)
- func (tree *MutableTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) (keys, values [][]byte, proof *RangeProof, err error)
- func (tree *MutableTree) GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)
- func (tree *MutableTree) GetVersions() ([]int64, error)
- func (tree *MutableTree) Hash() []byte
- func (tree *MutableTree) Import(version int64) (*Importer, error)
- func (tree *MutableTree) IsEmpty() bool
- func (tree *MutableTree) LazyLoadVersion(targetVersion int64) (int64, error)
- func (tree *MutableTree) Load() (int64, error)
- func (tree *MutableTree) LoadVersion(targetVersion int64) (int64, error)
- func (tree *MutableTree) LoadVersionForOverwriting(targetVersion int64) (int64, error)
- func (tree *MutableTree) NewBatch() dbm.Batch
- func (tree *MutableTree) PreChanges(keys []string, setOrDel []byte)
- func (tree *MutableTree) Remove(key []byte) ([]byte, bool)
- func (tree *MutableTree) ResetCount()
- func (tree *MutableTree) Rollback()
- func (tree *MutableTree) SaveBranch(batch dbm.Batch, node *Node) []byte
- func (tree *MutableTree) SaveVersion(useDeltas bool) ([]byte, int64, TreeDelta, error)
- func (tree *MutableTree) SaveVersionAsync(version int64, useDeltas bool) ([]byte, int64, error)
- func (tree *MutableTree) SaveVersionSync(version int64, useDeltas bool) ([]byte, int64, error)
- func (tree *MutableTree) Set(key, value []byte) bool
- func (tree *MutableTree) SetDelta(delta *TreeDelta)
- func (tree *MutableTree) SetInitialVersion(version uint64)
- func (tree *MutableTree) SetUpgradeVersion(version int64)
- func (tree *MutableTree) StopTree()
- func (tree *MutableTree) String() string
- func (tree *MutableTree) VersionExists(version int64) bool
- func (tree *MutableTree) VersionExistsInDb(version int64) bool
- func (tree *MutableTree) WorkingHash() []byte
- type Node
- type NodeCache
- type NodeEncoder
- type NodeJson
- type NodeJsonImp
- type Options
- type OrphanInfo
- type PathToLeaf
- type ProofInnerNode
- type ProofLeafNode
- type RangeProof
- func (proof *RangeProof) ComputeRootHash() []byte
- func (proof *RangeProof) Keys() (keys [][]byte)
- func (proof *RangeProof) LeftIndex() int64
- func (proof *RangeProof) String() string
- func (proof *RangeProof) StringIndented(indent string) string
- func (proof *RangeProof) Verify(root []byte) error
- func (proof *RangeProof) VerifyAbsence(key []byte) error
- func (proof *RangeProof) VerifyItem(key, value []byte) error
- type RuntimeState
- type SyncMap
- func (sm *SyncMap) Clone() map[int64]bool
- func (sm *SyncMap) Delete(key int64)
- func (sm *SyncMap) DeleteWithoutLock(key int64)
- func (sm *SyncMap) Get(key int64) bool
- func (sm *SyncMap) Has(key int64) bool
- func (sm *SyncMap) Len() int
- func (sm *SyncMap) Range(f func(key int64, value bool) bool)
- func (sm *SyncMap) Set(key int64, value bool)
- type TreeDelta
- type TreeDeltaMap
- type TreeDeltaMapImp
- type TreeMap
- type ValueOp
- type VersionInfo
Examples ¶
Constants ¶
const ( IavlErr = 0 IavlInfo = 1 IavlDebug = 2 )
const ( FlagIavlCommitIntervalHeight = "iavl-commit-interval-height" FlagIavlMinCommitItemCount = "iavl-min-commit-item-count" FlagIavlHeightOrphansCacheSize = "iavl-height-orphans-cache-size" FlagIavlMaxCommittedHeightNum = "iavl-max-committed-height-num" FlagIavlEnableAsyncCommit = "iavl-enable-async-commit" )
const ( PreloadConcurrencyThreshold = 4 PreChangeOpSet byte = 1 PreChangeOpDelete byte = 0 PreChangeNop byte = 0xFF )
const ( ANSIReset = "\x1b[0m" ANSIBright = "\x1b[1m" ANSIFgGreen = "\x1b[32m" ANSIFgBlue = "\x1b[34m" ANSIFgCyan = "\x1b[36m" )
const (
FlagIavlCacheInitRatio = "iavl-cache-init-ratio"
)
const (
FlagOutputModules = "iavl-output-modules"
)
const ProofOpIAVLAbsence = "iavl:a"
const ProofOpIAVLValue = "iavl:v"
Variables ¶
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 = 100 )
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") )
var ( Version = "" Commit = "" Branch = "" )
Version of iavl. Fill in fields with build flags
var ErrNoImport = errors.New("no import in progress")
ErrNoImport is returned when calling methods on a closed importer
var ExportDone = errors.New("export is complete") // nolint:golint
ExportDone is returned by Exporter.Next() when all items have been exported.
var (
IavlCacheInitRatio float64 = 0
)
var (
OutputModules map[string]int
)
Functions ¶
func AbsenceOpDecoder ¶
func AbsenceOpDecoder(pop merkle.ProofOp) (merkle.ProofOperator, error)
func ColoredBytes ¶
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 GetIgnoreVersionCheck ¶ added in v1.0.0
func GetIgnoreVersionCheck() bool
func ParseDBName ¶
func PrintTree ¶
func PrintTree(tree *ImmutableTree)
PrintTree prints the whole tree in an indented form.
func RegisterWire ¶
func Repair013Orphans ¶
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 SetIgnoreVersionCheck ¶
func SetIgnoreVersionCheck(check bool)
func SetLogFunc ¶
func SetLogFunc(l LogFuncType)
func SetProduceDelta ¶ added in v1.0.0
func SetProduceDelta(pd bool)
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
type CommitOrphansImp ¶ added in v1.1.6
func (*CommitOrphansImp) MarshalToAmino ¶ added in v1.1.6
func (ci *CommitOrphansImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)
MarshalToAmino marshal data to amino bytes.
func (*CommitOrphansImp) UnmarshalFromAmino ¶ added in v1.1.6
func (ci *CommitOrphansImp) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error
UnmarshalFromAmino unmarshal data from animo bytes.
type ExportNode ¶
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 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) 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) (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) GetMembershipProof ¶ added in v1.3.0
func (t *ImmutableTree) GetMembershipProof(key []byte) (*ics23.CommitmentProof, error)
func (*ImmutableTree) GetNonMembershipProof ¶ added in v1.3.0
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 ¶ added in v1.0.0
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 ¶ added in v1.3.0
func (t *ImmutableTree) GetUpgradeVersion() int64
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 ¶ added in v1.3.0
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) 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) SetUpgradeVersion ¶ added in v1.3.0
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 ¶
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.
type KeyFormat ¶
type KeyFormat struct {
// contains filtered or unexported fields
}
Provides a fixed-width lexicographically sortable []byte key format
func NewKeyFormat ¶
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 ¶
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 ¶
Format the byte segments into the key format - will panic if the segment lengths do not match the layout.
type LogFuncType ¶
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 ¶
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) GetCommitVersion ¶ added in v1.0.0
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 ¶ added in v1.0.0
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 ¶ added in v1.3.0
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 ¶ added in v1.5.4
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) 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 ¶ added in v1.3.0
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 ¶ added in v1.0.0
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 ¶
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 (*MutableTree) SaveVersionSync ¶
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 ¶ added in v1.0.0
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 ¶ added in v1.3.0
func (tree *MutableTree) SetUpgradeVersion(version int64)
func (*MutableTree) StopTree ¶
func (tree *MutableTree) StopTree()
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 ¶ added in v1.5.4
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 ¶
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 NodeJsonToNode ¶ added in v1.0.0
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.
type NodeCache ¶ added in v1.3.1
type NodeCache struct {
// contains filtered or unexported fields
}
type NodeEncoder ¶
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 ¶ added in v1.0.0
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 ¶ added in v1.0.0
NodeToNodeJson get NodeJson from Node
func (*NodeJson) MarshalToAmino ¶ added in v1.1.6
MarshalToAmino marshal data to amino bytes.
type NodeJsonImp ¶ added in v1.1.6
func (*NodeJsonImp) MarshalToAmino ¶ added in v1.1.6
func (ni *NodeJsonImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)
MarshalToAmino marshal data to amino bytes.
func (*NodeJsonImp) UnmarshalFromAmino ¶ added in v1.1.6
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 ¶ added in v1.3.1
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) 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 ¶ added in v1.5.0
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) DeleteWithoutLock ¶
type TreeDelta ¶ added in v1.0.0
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 ¶ added in v1.1.6
type TreeDeltaMap ¶ added in v1.1.6
func (TreeDeltaMap) MarshalAmino ¶ added in v1.1.6
func (tdm TreeDeltaMap) MarshalAmino() ([]*TreeDeltaMapImp, error)
func (TreeDeltaMap) MarshalToAmino ¶ added in v1.1.6
func (tdm TreeDeltaMap) MarshalToAmino(cdc *amino.Codec) ([]byte, error)
MarshalToAmino marshal to amino bytes
func (TreeDeltaMap) UnmarshalAmino ¶ added in v1.1.6
func (tdm TreeDeltaMap) UnmarshalAmino(treeDeltaList []*TreeDeltaMapImp) error
func (TreeDeltaMap) UnmarshalFromAmino ¶ added in v1.1.6
func (tdm TreeDeltaMap) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error
UnmarshalFromAmino decode bytes from amino format.
type TreeDeltaMapImp ¶ added in v1.1.6
TreeDeltaMapImp convert map[string]*TreeDelta to struct
func (*TreeDeltaMapImp) MarshalToAmino ¶ added in v1.1.6
func (ti *TreeDeltaMapImp) MarshalToAmino(cdc *amino.Codec) ([]byte, error)
MarshalToAmino marshal data to amino bytes
func (*TreeDeltaMapImp) UnmarshalFromAmino ¶ added in v1.1.6
func (ti *TreeDeltaMapImp) UnmarshalFromAmino(cdc *amino.Codec, data []byte) error
UnmarshalFromAmino unmarshal data from amino bytes.
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
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 ¶
- codec.go
- doc.go
- export.go
- immutable_tree.go
- import.go
- key_format.go
- logger.go
- mutable_ibc_adapter.go
- mutable_tree.go
- mutable_tree_map.go
- mutable_tree_oec.go
- mutable_tree_preload.go
- node.go
- node_ibc_adapter.go
- nodedb.go
- nodedb_cache.go
- nodedb_oec.go
- nodedb_orphan.go
- nodedb_orphan_info.go
- nodedb_statistics.go
- nodedb_tpp.go
- nodedb_update_branch.go
- options.go
- proof.go
- proof_iavl_absence.go
- proof_iavl_value.go
- proof_ibc_adapter.go
- proof_path.go
- proof_range.go
- repair.go
- sync_map.go
- synclist.go
- tree_delta.go
- tree_dotgraph.go
- util.go
- version.go
- wire.go