iavl

package module
v0.6.2 Latest Latest
Warning

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

 Go to latest Published: Mar 8, 2018 License: Apache-2.0 Imports: 13 Imported by: 0

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 algortihm 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

View Source 
const Version = "0.6.1"

Variables

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

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

	// ErrInvalidRoot is returned when the root passed in does not match the proof's.
	ErrInvalidRoot = fmt.Errorf("invalid root")

	// ErrNilRoot is returned when the root of the tree is nil.
	ErrNilRoot = fmt.Errorf("tree root is nil")
)
View Source 
var ErrVersionDoesNotExist = fmt.Errorf("version does not exist")

Functions

func Restore added in v0.6.0 

func Restore(empty *Tree, kvs []NodeData)

Restore will take an (empty) tree restore it from the keys returned from a SerializeFunc.

func RestoreUsingDepth added in v0.6.0 

func RestoreUsingDepth(empty *Tree, kvs []NodeData)

func WriteDOTGraph 

func WriteDOTGraph(w io.Writer, tree *Tree, paths []*PathToKey)

Types

type Chunk added in v0.6.0 

type Chunk []OrderedNodeData

Chunk is a list of ordered nodes. It can be sorted, merged, exported from a tree and used to generate a new tree.

func GetChunk added in v0.6.0 

func GetChunk(tree *Tree, depth, count uint) Chunk

GetChunk finds the count-th subtree at depth and generates a Chunk for that data.

func MergeChunks added in v0.6.0 

func MergeChunks(left, right Chunk) Chunk

MergeChunks does a merge sort of the two Chunks, assuming they were already in sorted order.

func (Chunk) CalculateRoot added in v0.6.0 

func (c Chunk) CalculateRoot() []byte

CalculateRoot creates a temporary in-memory iavl tree to calculate the root hash of inserting all the nodes.

func (Chunk) PopulateTree added in v0.6.0 

func (c Chunk) PopulateTree(empty *Tree)

PopulateTree adds all the chunks in order to the given tree.

func (Chunk) Sort added in v0.6.0 

func (c Chunk) Sort()

Sort does an inline quicksort.

type InnerKeyProof added in v0.6.0 

type InnerKeyProof struct {
	*KeyExistsProof
}

InnerKeyProof represents a proof of existence of an inner node key.

func GetChunkHashesWithProofs added in v0.6.0 

func GetChunkHashesWithProofs(tree *Tree) ([][]byte, []*InnerKeyProof, uint)

GetChunkHashesWithProofs takes a tree and returns the list of chunks with proofs that can be used to synchronize a tree across the network.

func ReadInnerKeyProof added in v0.6.0 

func ReadInnerKeyProof(data []byte) (*InnerKeyProof, error)

ReadKeyInnerProof will deserialize a InnerKeyProof from bytes.

func (*InnerKeyProof) Verify added in v0.6.0 

func (proof *InnerKeyProof) Verify(hash []byte, value []byte, root []byte) error

Verify verifies the proof is valid and returns an error if it isn't.

type KeyAbsentProof 

type KeyAbsentProof struct {
	RootHash cmn.HexBytes `json:"root_hash"`

	Left  *pathWithNode `json:"left"`
	Right *pathWithNode `json:"right"`
}

KeyAbsentProof represents a proof of the absence of a single key.

func (*KeyAbsentProof) Bytes 

func (proof *KeyAbsentProof) Bytes() []byte

Bytes returns a go-wire binary serialization

func (*KeyAbsentProof) Root 

func (proof *KeyAbsentProof) Root() []byte

func (*KeyAbsentProof) String 

func (p *KeyAbsentProof) String() string

func (*KeyAbsentProof) Verify 

func (proof *KeyAbsentProof) Verify(key, value []byte, root []byte) error

Verify verifies the proof is valid and returns an error if it isn't.

type KeyExistsProof 

type KeyExistsProof struct {
	RootHash cmn.HexBytes `json:"root_hash"`
	Version  int64        `json:"version"`

	*PathToKey `json:"path"`
}

KeyExistsProof represents a proof of existence of a single key.

func (*KeyExistsProof) Bytes 

func (proof *KeyExistsProof) Bytes() []byte

Bytes returns a go-wire binary serialization

func (*KeyExistsProof) Root 

func (proof *KeyExistsProof) Root() []byte

func (*KeyExistsProof) Verify 

func (proof *KeyExistsProof) Verify(key []byte, value []byte, root []byte) error

Verify verifies the proof is valid and returns an error if it isn't.

type KeyFirstInRangeProof 

type KeyFirstInRangeProof struct {
	KeyExistsProof `json:"key_proof"`

	Left  *pathWithNode `json:"left"`
	Right *pathWithNode `json:"right"`
}

KeyFirstInRangeProof is a proof that a given key is the first in a given range.

func (*KeyFirstInRangeProof) String 

func (proof *KeyFirstInRangeProof) String() string

String returns a string representation of the proof.

func (*KeyFirstInRangeProof) Verify 

func (proof *KeyFirstInRangeProof) Verify(startKey, endKey, key, value []byte, root []byte) error

Verify that the first in range proof is valid.

type KeyInRangeProof 

type KeyInRangeProof interface {
	Verify(startKey, endKey, key, value, root []byte) error
}

KeyInRangeProof is an interface which covers both first-in-range and last-in-range proofs.

type KeyLastInRangeProof 

type KeyLastInRangeProof struct {
	KeyExistsProof `json:"key_proof"`

	Left  *pathWithNode `json:"left"`
	Right *pathWithNode `json:"right"`
}

KeyLastInRangeProof is a proof that a given key is the last in a given range.

func (*KeyLastInRangeProof) String 

func (proof *KeyLastInRangeProof) String() string

String returns a string representation of the proof.

func (*KeyLastInRangeProof) Verify 

func (proof *KeyLastInRangeProof) Verify(startKey, endKey, key, value []byte, root []byte) error

Verify that the last in range proof is valid.

type KeyProof 

type KeyProof interface {
	// Verify verfies the proof is valid. To verify absence,
	// the value should be nil.
	Verify(key, value, root []byte) error

	// Root returns the root hash of the proof.
	Root() []byte

	// Serialize itself
	Bytes() []byte
}

KeyProof represents a proof of existence or absence of a single key.

func ReadKeyProof added in v0.6.0 

func ReadKeyProof(data []byte) (KeyProof, error)

ReadKeyProof reads a KeyProof from a byte-slice.

type KeyRangeProof 

type KeyRangeProof struct {
	RootHash   cmn.HexBytes `json:"root_hash"`
	Versions   []int64      `json:"versions"`
	PathToKeys []*PathToKey `json:"paths"`

	Left  *pathWithNode `json:"left"`
	Right *pathWithNode `json:"right"`
}

KeyRangeProof is proof that a range of keys does or does not exist.

func (*KeyRangeProof) String 

func (proof *KeyRangeProof) String() string

func (*KeyRangeProof) Verify 

func (proof *KeyRangeProof) Verify(
	startKey, endKey []byte, limit int, keys, values [][]byte, root []byte,
) error

Verify that a range proof is valid.

This method expects the same parameters passed to query the range.

type Node 

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

Node represents a node in a Tree.

func MakeNode 

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

MakeNode constructs an *Node from an encoded byte slice.

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

func NewNode 

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

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

func (*Node) String 

func (node *Node) String() string

String returns a string representation of the node.

type NodeData added in v0.6.0 

type NodeData struct {
	Key   []byte
	Value []byte
	Depth uint8
}

NodeData groups together a key, value and depth.

func InOrderSerialize added in v0.6.0 

func InOrderSerialize(t *Tree, root *Node) []NodeData

InOrderSerialize returns all key-values in the key order (as stored). May be nice to read, but when recovering, it will create a different.

func StableSerializeBFS added in v0.6.0 

func StableSerializeBFS(t *Tree, root *Node) []NodeData

StableSerializeBFS serializes the tree in a breadth-first manner.

func StableSerializeFrey added in v0.6.0 

func StableSerializeFrey(t *Tree, top *Node) []NodeData

StableSerializeFrey exports the key value pairs of the tree in an order, such that when Restored from those keys, the new tree would have the same structure (and thus same shape) as the original tree.

the algorithm is basically this: take the leftmost node of the left half and the leftmost node of the righthalf. Then go down a level... each time adding leftmost node of the right side. (bredth first search)

Imagine 8 nodes in a balanced tree, split in half each time 1 1, 5 1, 5, 3, 7 1, 5, 3, 7, 2, 4, 6, 8

type OrderedNodeData added in v0.6.0 

type OrderedNodeData struct {
	SortOrder uint64
	NodeData
}

OrderedNodeData is the data to recreate a leaf node, along with a SortOrder to define a BFS insertion order.

func NewOrderedNode added in v0.6.0 

func NewOrderedNode(leaf *Node, prefix uint64) OrderedNodeData

NewOrderedNode creates the data from a leaf node.

type PathToKey 

type PathToKey struct {
	InnerNodes []proofInnerNode `json:"inner_nodes"`
}

PathToKey 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 (*PathToKey) String 

func (p *PathToKey) String() string

type RestoreFunc added in v0.6.0 

type RestoreFunc func(*Tree, []NodeData)

RestoreFunc is an implementation that can restore an iavl tree from NodeData.

type SerializeFunc added in v0.6.0 

type SerializeFunc func(*Tree, *Node) []NodeData

SerializeFunc is any implementation that can serialize an iavl Node and its descendants.

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 NewTree 

func NewTree(db dbm.DB, cacheSize int) *Tree

NewTree creates both in-memory and persistent instances

func (*Tree) Get 

func (t *Tree) Get(key []byte) (index int, value []byte)

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) Get64 added in v0.6.0 

func (t *Tree) Get64(key []byte) (index int64, value []byte)

func (*Tree) GetByIndex 

func (t *Tree) GetByIndex(index int) (key []byte, value []byte)

GetByIndex gets the key and value at the specified index.

func (*Tree) GetByIndex64 added in v0.6.0 

func (t *Tree) GetByIndex64(index int64) (key []byte, value []byte)

func (*Tree) GetFirstInRangeWithProof 

func (t *Tree) GetFirstInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyFirstInRangeProof, error)

GetFirstInRangeWithProof gets the first key/value pair in the specified range, with a proof.

func (*Tree) GetLastInRangeWithProof 

func (t *Tree) GetLastInRangeWithProof(startKey, endKey []byte) ([]byte, []byte, *KeyLastInRangeProof, error)

GetLastInRangeWithProof gets the last key/value pair in the specified range, with a proof.

func (*Tree) GetRangeWithProof 

func (t *Tree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) ([][]byte, [][]byte, *KeyRangeProof, error)

GetRangeWithProof 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 keys, a list of values and a proof.

func (*Tree) GetWithProof 

func (t *Tree) GetWithProof(key []byte) ([]byte, KeyProof, 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) Has 

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

Has returns whether or not a key exists.

func (*Tree) Hash 

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

Hash returns the root hash.

func (*Tree) Height 

func (t *Tree) Height() int

Height returns the height of the tree.

func (*Tree) Height8 added in v0.6.0 

func (t *Tree) Height8() int8

func (*Tree) Iterate 

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

Iterate iterates over all keys of the tree, in order.

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 

func (t *Tree) Remove(key []byte) ([]byte, bool)

Remove tries to remove a key from the tree and if removed, returns its value, and 'true'.

func (*Tree) Set 

func (t *Tree) Set(key []byte, value []byte) (updated bool)

Set a key. Nil values are not supported.

func (*Tree) Size 

func (t *Tree) Size() int

Size returns the number of leaf nodes in the tree.

func (*Tree) Size64 added in v0.6.0 

func (t *Tree) Size64() int64

func (*Tree) String 

func (t *Tree) String() string

String returns a string representation of Tree.

func (*Tree) Version added in v0.6.0 

func (t *Tree) Version() int

Version returns the version of the tree.

func (*Tree) Version64 added in v0.6.0 

func (t *Tree) Version64() int64

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

func (tree *VersionedTree) GetVersionedFirstInRangeWithProof(startKey, endKey []byte, version int64) ([]byte, []byte, *KeyFirstInRangeProof, error)

GetVersionedFirstInRangeWithProof gets the first key/value pair in the specified range, with a proof.

func (*VersionedTree) GetVersionedLastInRangeWithProof 

func (tree *VersionedTree) GetVersionedLastInRangeWithProof(startKey, endKey []byte, version int64) ([]byte, []byte, *KeyLastInRangeProof, error)

GetVersionedLastInRangeWithProof gets the last key/value pair in the specified range, with a proof.

func (*VersionedTree) GetVersionedRangeWithProof 

func (tree *VersionedTree) GetVersionedRangeWithProof(startKey, endKey []byte, limit int, version int64) ([][]byte, [][]byte, *KeyRangeProof, 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 keys, a list of values and a proof.

func (*VersionedTree) GetVersionedWithProof 

func (tree *VersionedTree) GetVersionedWithProof(key []byte, version int64) ([]byte, KeyProof, 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

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.