iavl

README

IAVL+ Tree

A snapshottable (immutable) AVL+ tree for persistent data

Note Please make sure you read the caveat on Copy. If you have a backing DB and call Save to persist the state, all existing copies become potentially invalid and may panic if used. For safe coding, you must throw away all references upon save, and Copy again from the new, committed state.

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

Index

• Constants
• func PrintIAVLNode(node *IAVLNode)
• type Formatter
• type IAVLNode
  • func MakeIAVLNode(buf []byte, t *IAVLTree) (node *IAVLNode, err error)
  • func NewIAVLNode(key []byte, value []byte) *IAVLNode
• type IAVLProof
  • func ReadProof(data []byte) (*IAVLProof, error)
  • func (proof *IAVLProof) Root() []byte
  • func (proof *IAVLProof) Verify(key []byte, value []byte, root []byte) bool
• type IAVLProofInnerNode
  • func (branch IAVLProofInnerNode) Hash(childHash []byte) []byte
• type IAVLProofLeafNode
  • func (leaf IAVLProofLeafNode) Hash() []byte
• type IAVLTree
  • func NewIAVLTree(cacheSize int, db dbm.DB) *IAVLTree
  • func (t *IAVLTree) BatchSet(key []byte, value []byte)
  • func (t *IAVLTree) ConstructProof(key []byte) (value []byte, proof *IAVLProof)
  • func (t *IAVLTree) Copy() merkle.Tree
  • func (t *IAVLTree) Dump(verbose bool, mapping *KeyValueMapping)
  • func (t *IAVLTree) Get(key []byte) (index int, value []byte, exists bool)
  • func (t *IAVLTree) GetByIndex(index int) (key []byte, value []byte)
  • func (t *IAVLTree) Has(key []byte) bool
  • func (t *IAVLTree) Hash() []byte
  • func (t *IAVLTree) HashWithCount() ([]byte, int)
  • func (t *IAVLTree) Height() int8
  • func (t *IAVLTree) Iterate(fn func(key []byte, value []byte) bool) (stopped bool)
  • func (t *IAVLTree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)
  • func (t *IAVLTree) Load(hash []byte)
  • func (t *IAVLTree) Proof(key []byte) (value []byte, proofBytes []byte, exists bool)
  • func (t *IAVLTree) Remove(key []byte) (value []byte, removed bool)
  • func (t *IAVLTree) Save() []byte
  • func (t *IAVLTree) Set(key []byte, value []byte) (updated bool)
  • func (t *IAVLTree) Size() int
• type KeyValueMapping

Constants

const Version = "0.4.0" // benchmarking, update proof

Functions

func PrintIAVLNode

func PrintIAVLNode(node *IAVLNode)

Prints the in-memory children recursively.

Types

type Formatter

type Formatter func(in []byte) (out string)

type IAVLNode

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

func MakeIAVLNode

func MakeIAVLNode(buf []byte, t *IAVLTree) (node *IAVLNode, err error)

NOTE: The hash is not saved or set. The caller should set the hash afterwards. (Presumably the caller already has the hash)

func NewIAVLNode

func NewIAVLNode(key []byte, value []byte) *IAVLNode

type IAVLProof

type IAVLProof struct {
	LeafHash   []byte
	InnerNodes []IAVLProofInnerNode
	RootHash   []byte
}

func ReadProof

func ReadProof(data []byte) (*IAVLProof, error)

ReadProof will deserialize a IAVLProof from bytes

func (*IAVLProof) Root

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

Please leave this here! I use it in light-client to fulfill an interface

func (*IAVLProof) Verify

func (proof *IAVLProof) Verify(key []byte, value []byte, root []byte) bool

type IAVLProofInnerNode

type IAVLProofInnerNode struct {
	Height int8
	Size   int
	Left   []byte
	Right  []byte
}

func (IAVLProofInnerNode) Hash

func (branch IAVLProofInnerNode) Hash(childHash []byte) []byte

type IAVLProofLeafNode

type IAVLProofLeafNode struct {
	KeyBytes   []byte
	ValueBytes []byte
}

func (IAVLProofLeafNode) Hash

func (leaf IAVLProofLeafNode) Hash() []byte

type IAVLTree

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

Immutable AVL Tree (wraps the Node root) This tree is not goroutine safe.

func NewIAVLTree

func NewIAVLTree(cacheSize int, db dbm.DB) *IAVLTree

NewIAVLTree creates both im-memory and persistent instances

func (*IAVLTree) BatchSet

func (t *IAVLTree) BatchSet(key []byte, value []byte)

BatchSet adds a Set to the current batch, will get handled atomically

func (*IAVLTree) ConstructProof

func (t *IAVLTree) ConstructProof(key []byte) (value []byte, proof *IAVLProof)

Returns nil, nil if key is not in tree.

func (*IAVLTree) Copy

func (t *IAVLTree) Copy() merkle.Tree

The returned tree and the original tree are goroutine independent. That is, they can each run in their own goroutine. However, upon Save(), any other trees that share a db will become outdated, as some nodes will become orphaned. Note that Save() clears leftNode and rightNode. Otherwise, two copies would not be goroutine independent.

func (*IAVLTree) Dump

func (t *IAVLTree) Dump(verbose bool, mapping *KeyValueMapping)

Dump everything from the database

func (*IAVLTree) Get

func (t *IAVLTree) Get(key []byte) (index int, value []byte, exists bool)

func (*IAVLTree) GetByIndex

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

func (*IAVLTree) Has

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

func (*IAVLTree) Hash

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

func (*IAVLTree) HashWithCount

func (t *IAVLTree) HashWithCount() ([]byte, int)

func (*IAVLTree) Height

func (t *IAVLTree) Height() int8

func (*IAVLTree) Iterate

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

func (*IAVLTree) IterateRange

func (t *IAVLTree) 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 inclusive If either are nil, then it is open on that side (nil, nil is the same as Iterate)

func (*IAVLTree) Load

func (t *IAVLTree) Load(hash []byte)

Sets the root node by reading from db. If the hash is empty, then sets root to nil.

func (*IAVLTree) Proof

func (t *IAVLTree) Proof(key []byte) (value []byte, proofBytes []byte, exists bool)

func (*IAVLTree) Remove

func (t *IAVLTree) Remove(key []byte) (value []byte, removed bool)

func (*IAVLTree) Save

func (t *IAVLTree) Save() []byte

func (*IAVLTree) Set

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

func (*IAVLTree) Size

func (t *IAVLTree) Size() int

type KeyValueMapping

type KeyValueMapping struct {
	Key   Formatter
	Value Formatter
}