The highest tagged major version is
README
¶
IAVL+ Tree
Note: Requires Go 1.8+
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 ¶
Basic usage of VersionedTree.
import "github.com/tendermint/iavl"
import "github.com/tendermint/tmlibs/db"
...
tree := iavl.NewVersionedTree(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", KeyProof, nil
proof.Verify([]byte("bob"), val, root) // nil
Proof of absence:
_, proof, err = tree.GetVersionedWithProof([]byte("tom"), 2) // nil, KeyProof, 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 PrintTree(tree *Tree)
- func RegisterWire(cdc *amino.Codec)
- func WriteDOTGraph(w io.Writer, tree *Tree, paths []PathToLeaf)
- type Node
- type PathToLeaf
- type RangeProof
- type Tree
- func (t *Tree) Get(key []byte) (index int, value []byte)
- func (t *Tree) Get64(key []byte) (index int64, value []byte)
- func (t *Tree) GetByIndex(index int) (key []byte, value []byte)
- func (t *Tree) GetByIndex64(index int64) (key []byte, value []byte)
- func (t *Tree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error)
- func (t *Tree) GetWithProof(key []byte) (value []byte, proof *RangeProof, err error)
- func (t *Tree) Has(key []byte) bool
- func (t *Tree) Hash() []byte
- func (t *Tree) Height() int
- func (t *Tree) Height8() int8
- func (t *Tree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *Tree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
- func (t *Tree) IterateRangeInclusive(start, end []byte, ascending bool, ...) (stopped bool)
- func (t *Tree) Remove(key []byte) ([]byte, bool)
- func (t *Tree) Set(key []byte, value []byte) (updated bool)
- func (t *Tree) Size() int
- func (t *Tree) Size64() int64
- func (t *Tree) String() string
- func (t *Tree) Version() int
- func (t *Tree) Version64() int64
- type VersionedTree
- func (tree *VersionedTree) DeleteVersion(version int64) error
- func (tree *VersionedTree) GetVersioned(key []byte, version int64) (index int, value []byte)
- func (tree *VersionedTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) ([][]byte, [][]byte, *RangeProof, error)
- func (tree *VersionedTree) GetVersionedWithProof(key []byte, version int64) ([]byte, *RangeProof, error)
- func (tree *VersionedTree) Hash() []byte
- func (tree *VersionedTree) IsEmpty() bool
- func (tree *VersionedTree) Load() (int64, error)
- func (tree *VersionedTree) LoadVersion(targetVersion int64) (int64, error)
- func (tree *VersionedTree) Remove(key []byte) ([]byte, bool)
- func (tree *VersionedTree) Rollback()
- func (tree VersionedTree) SaveAs(version int64)
- func (tree *VersionedTree) SaveVersion() ([]byte, int64, error)
- func (tree *VersionedTree) Set(key, val []byte) bool
- func (tree *VersionedTree) String() string
- func (tree *VersionedTree) Tree() *Tree
- func (tree *VersionedTree) VersionExists(version int64) bool
Constants ¶
const Version = "0.8.1"
Variables ¶
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") // ErrNilRoot is returned when the root of the tree is nil. ErrNilRoot = fmt.Errorf("tree root is nil") )
var ErrVersionDoesNotExist = fmt.Errorf("version does not exist")
Functions ¶
func RegisterWire ¶ added in v0.8.0
func RegisterWire(cdc *amino.Codec)
func WriteDOTGraph ¶
func WriteDOTGraph(w io.Writer, tree *Tree, paths []PathToLeaf)
Types ¶
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 (*Node) PathToLeaf ¶ added in v0.8.0
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 PathToLeaf ¶ added in v0.8.0
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 ¶ added in v0.8.0
func (pl PathToLeaf) String() string
func (PathToLeaf) StringIndented ¶ added in v0.8.0
func (pl PathToLeaf) StringIndented(indent string) string
type RangeProof ¶ added in v0.8.0
type RangeProof struct {
// You don't need the right path because
// it can be derived from what we have.
RootHash cmn.HexBytes `json:"root_hash"`
LeftPath PathToLeaf `json:"left_path"`
InnerNodes []PathToLeaf `json:"inner_nodes"`
Leaves []proofLeafNode `json:"leaves"`
// contains filtered or unexported fields
}
func (*RangeProof) String ¶ added in v0.8.0
func (proof *RangeProof) String() string
String returns a string representation of the proof.
func (*RangeProof) StringIndented ¶ added in v0.8.0
func (proof *RangeProof) StringIndented(indent string) string
func (*RangeProof) Verify ¶ added in v0.8.0
func (proof *RangeProof) Verify(root []byte) error
Verify that proof is valid.
func (*RangeProof) VerifyAbsence ¶ added in v0.8.0
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 ¶ added in v0.8.0
func (proof *RangeProof) VerifyItem(i int, key, value []byte) error
Verify that a leaf is some value. Does not assume that the proof itself is value. For that, use Verify(root).
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree is a container for an immutable AVL+ Tree. Changes are performed by swapping the internal root with a new one, while the container is mutable. Note that this tree is not thread-safe.
func (*Tree) Get ¶
Get returns the index and value of the specified key if it exists, or nil and the next index, if it doesn't.
func (*Tree) GetByIndex ¶
GetByIndex gets the key and value at the specified index.
func (*Tree) GetByIndex64 ¶ added in v0.6.0
func (*Tree) GetRangeWithProof ¶
func (t *Tree) 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. To specify a descending range, swap the start and end keys.
func (*Tree) GetWithProof ¶
func (t *Tree) 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 (*Tree) IterateRange ¶
func (t *Tree) 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)
func (*Tree) IterateRangeInclusive ¶
func (t *Tree) 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)
func (*Tree) Remove ¶
Remove tries to remove a key from the tree and if removed, returns its value, and 'true'.
type VersionedTree ¶
type VersionedTree struct {
// contains filtered or unexported fields
}
VersionedTree is a persistent tree which keeps track of versions.
func NewVersionedTree ¶
func NewVersionedTree(db dbm.DB, cacheSize int) *VersionedTree
NewVersionedTree returns a new tree with the specified cache size and datastore.
func (*VersionedTree) DeleteVersion ¶
func (tree *VersionedTree) DeleteVersion(version int64) error
DeleteVersion deletes a tree version from disk. The version can then no longer be accessed.
func (*VersionedTree) GetVersioned ¶
func (tree *VersionedTree) GetVersioned(key []byte, version int64) ( index int, value []byte, )
GetVersioned gets the value at the specified key and version.
func (*VersionedTree) GetVersionedRangeWithProof ¶
func (tree *VersionedTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) ([][]byte, [][]byte, *RangeProof, error)
GetVersionedRangeWithProof gets key/value pairs within the specified range and limit. To specify a descending range, swap the start and end keys.
Returns a list of values, a list of keys, and a proof.
func (*VersionedTree) GetVersionedWithProof ¶
func (tree *VersionedTree) 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. A proof of existence or absence is returned alongside the value.
func (*VersionedTree) Hash ¶
func (tree *VersionedTree) 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 (*VersionedTree) IsEmpty ¶
func (tree *VersionedTree) IsEmpty() bool
IsEmpty returns whether or not the tree has any keys. Only trees that are not empty can be saved.
func (*VersionedTree) Load ¶
func (tree *VersionedTree) Load() (int64, error)
Load the latest versioned tree from disk.
Returns the version number of the latest version found
func (*VersionedTree) LoadVersion ¶ added in v0.6.0
func (tree *VersionedTree) LoadVersion(targetVersion int64) (int64, error)
Load a versioned tree from disk.
If version is 0, the latest version is loaded.
Returns the version number of the latest version found
func (*VersionedTree) Remove ¶
func (tree *VersionedTree) Remove(key []byte) ([]byte, bool)
Remove removes a key from the working tree.
func (*VersionedTree) Rollback ¶ added in v0.6.0
func (tree *VersionedTree) Rollback()
Rollback resets the working tree to the latest saved version, discarding any unsaved modifications.
func (VersionedTree) SaveAs ¶ added in v0.6.0
func (tree VersionedTree) SaveAs(version int64)
SaveAs saves the underlying Tree and assigns it a new version. Saves orphans too.
func (*VersionedTree) SaveVersion ¶
func (tree *VersionedTree) 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 (*VersionedTree) Set ¶
func (tree *VersionedTree) Set(key, val []byte) bool
Set sets a key in the working tree. Nil values are not supported.
func (*VersionedTree) String ¶
func (tree *VersionedTree) String() string
String returns a string representation of the tree.
func (*VersionedTree) Tree ¶
func (tree *VersionedTree) Tree() *Tree
Tree returns the current working tree.
func (*VersionedTree) VersionExists ¶
func (tree *VersionedTree) VersionExists(version int64) bool
VersionExists returns whether or not a version exists.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
cmd
module
|
|
|
legacydump
Module
|
|
|
Package sha256truncated provides a sha256 hash.Hash whose output is truncated to 20 bytes (160 bits).
|
Package sha256truncated provides a sha256 hash.Hash whose output is truncated to 20 bytes (160 bits). |
|
v2
|
|
|
migrate
Module
|