iavl

package module
v0.12.4 Latest Latest
Warning

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

Go to latest
Published: Dec 15, 2020 License: Apache-2.0 Imports: 16 Imported by: 2

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

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

Basic usage of MutableTree.

import "github.com/evdatsion/iavl"
import "github.com/evdatsion/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

View Source
const (
	ANSIReset  = "\x1b[0m"
	ANSIBright = "\x1b[1m"

	ANSIFgGreen = "\x1b[32m"
	ANSIFgBlue  = "\x1b[34m"
	ANSIFgCyan  = "\x1b[36m"
)
View Source
const ProofOpIAVLAbsence = "iavl:a"
View Source
const ProofOpIAVLValue = "iavl:v"
View Source
const Version = "0.12.3"

Version of iavl.

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")
)
View Source
var ErrVersionDoesNotExist = fmt.Errorf("version does not exist")

ErrVersionDoesNotExist is returned if a requested version does not exist.

Functions

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 Green

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

func IAVLAbsenceOpDecoder

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

func IAVLValueOpDecoder

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

func PrintTree

func PrintTree(tree *ImmutableTree)

PrintTree prints the whole tree in an indented form.

func RegisterWire

func RegisterWire(cdc *amino.Codec)

func WriteDOTGraph

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

Types

type IAVLAbsenceOp

type IAVLAbsenceOp 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 NewIAVLAbsenceOp

func NewIAVLAbsenceOp(key []byte, proof *RangeProof) IAVLAbsenceOp

func (IAVLAbsenceOp) GetKey

func (op IAVLAbsenceOp) GetKey() []byte

func (IAVLAbsenceOp) ProofOp

func (op IAVLAbsenceOp) ProofOp() merkle.ProofOp

func (IAVLAbsenceOp) Run

func (op IAVLAbsenceOp) Run(args [][]byte) ([][]byte, error)

func (IAVLAbsenceOp) String

func (op IAVLAbsenceOp) String() string

type IAVLValueOp

type IAVLValueOp 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 NewIAVLValueOp

func NewIAVLValueOp(key []byte, proof *RangeProof) IAVLValueOp

func (IAVLValueOp) GetKey

func (op IAVLValueOp) GetKey() []byte

func (IAVLValueOp) ProofOp

func (op IAVLValueOp) ProofOp() merkle.ProofOp

func (IAVLValueOp) Run

func (op IAVLValueOp) Run(args [][]byte) ([][]byte, error)

func (IAVLValueOp) String

func (op IAVLValueOp) String() string

type ImmutableTree

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

ImmutableTree is a container for an immutable AVL+ ImmutableTree. 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 NewImmutableTree

func NewImmutableTree(db dbm.DB, cacheSize int) *ImmutableTree

NewImmutableTree creates both in-memory and persistent instances

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, if it doesn't.

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

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

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

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)

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)

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

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 MutableTree

type MutableTree struct {
	*ImmutableTree // The current, working tree.
	// contains filtered or unexported fields
}

MutableTree is a persistent tree which keeps track of versions.

func NewMutableTree

func NewMutableTree(db dbm.DB, cacheSize int) *MutableTree

NewMutableTree returns a new tree with the specified cache size and datastore.

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

func (tree *MutableTree) GetImmutable(version int64) (*ImmutableTree, error)

GetImmutable loads an ImmutableTree at a given version for querying

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.

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

LoadVersionOverwrite returns the version number of targetVersion. Higher versions' data will be deleted.

func (*MutableTree) Remove

func (tree *MutableTree) Remove(key []byte) ([]byte, bool)

Remove removes a key from the working tree.

func (*MutableTree) Rollback

func (tree *MutableTree) Rollback()

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

func (*MutableTree) SaveVersion

func (tree *MutableTree) 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 (*MutableTree) Set

func (tree *MutableTree) Set(key, value []byte) bool

Set sets a key in the working tree. Nil values are not supported.

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) 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 (*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 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 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 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.

Directories

Path Synopsis
cmd

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL