iavl

package module
v2.0.0-alpha.4 Latest Latest
Warning

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

 Go to latest Published: Dec 31, 2024 License: Apache-2.0 Imports: 28 Imported by: 4

README

IAVL+ Tree

version license API Reference Lint Test Discord chat

Note: Requires Go 1.18+

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

Benchmarks

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.

IAVL x Cosmos SDK

IAVL DB Interface Cosmos SDK
v0.19.x tm-db v0.45.x, v0.46.x
v0.20.x cometbft-db v0.47.x
v1.0.3 cosmos-db v0.50.0-5
v1.1.2,4 iavl-db v0.50.6
v1.2.x iavl-db v0.50.7+
v1.3.0 iavl-db v0.52.x
v2.0.0 iavl-db cosmossdk.io/store/v2

NOTE: In the past, a v0.21.x release was published, but never used in production. It was retracted to avoid confusion.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var ErrNoImport = errors.New("no import in progress")

ErrNoImport is returned when calling methods on a closed importer

View Source 
var ErrorExportDone = fmt.Errorf("export done")

Functions

func EncodeBytes 

func EncodeBytes(w io.Writer, bz []byte) error

func FindDbsInPath 

func FindDbsInPath(path string) ([]string, error)

func NewIngestSnapshotConnection 

func NewIngestSnapshotConnection(snapshotDbPath string) (*sqlite3.Conn, error)

func SetGlobalPruneLimit 

func SetGlobalPruneLimit(n int)

Types

type Exporter 

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

func (*Exporter) Close 

func (e *Exporter) Close() error

func (*Exporter) Next 

func (e *Exporter) Next() (*Node, error)

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.

func (*Importer) Add 

func (i *Importer) Add(node *Node) 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.

func (*Importer) Close 

func (i *Importer) Close()

Close frees all resources. It is safe to call multiple times. Uncommitted nodes may already have been flushed to the database, but will not be visible.

func (*Importer) Commit 

func (i *Importer) Commit() error

Commit finalizes the import by flushing any outstanding nodes to the database, making the version visible, and updating the tree metadata. It can only be called once, and calls Close() internally.

type Iterator 

type Iterator interface {
	// Domain returns the start (inclusive) and end (exclusive) limits of the iterator.
	// CONTRACT: start, end readonly []byte
	Domain() (start []byte, end []byte)

	// Valid returns whether the current iterator is valid. Once invalid, the TreeIterator remains
	// invalid forever.
	Valid() bool

	// Next moves the iterator to the next key in the database, as defined by order of iteration.
	// If Valid returns false, this method will panic.
	Next()

	// Key returns the key at the current position. Panics if the iterator is invalid.
	// CONTRACT: key readonly []byte
	Key() (key []byte)

	// Value returns the value at the current position. Panics if the iterator is invalid.
	// CONTRACT: value readonly []byte
	Value() (value []byte)

	// Error returns the last error encountered by the iterator, if any.
	Error() error

	// Close closes the iterator, relasing any allocated resources.
	Close() error
}

type LeafIterator 

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

func (*LeafIterator) Close 

func (l *LeafIterator) Close() error

func (*LeafIterator) Domain 

func (l *LeafIterator) Domain() (start []byte, end []byte)

func (*LeafIterator) Error 

func (l *LeafIterator) Error() error

func (*LeafIterator) Key 

func (l *LeafIterator) Key() (key []byte)

func (*LeafIterator) Next 

func (l *LeafIterator) Next()

func (*LeafIterator) Valid 

func (l *LeafIterator) Valid() bool

func (*LeafIterator) Value 

func (l *LeafIterator) Value() (value []byte)

type MultiTree 

type MultiTree struct {
	Trees map[string]*Tree
	// contains filtered or unexported fields
}

MultiTree encapsulates multiple IAVL trees, each with its own "store key" in the context of the Cosmos SDK. Within IAVL v2 is only used to test the IAVL v2 implementation, and for import/export of IAVL v2 state.

func ImportMultiTree 

func ImportMultiTree(pool *NodePool, version int64, path string, treeOpts TreeOptions) (*MultiTree, error)

func NewMultiTree 

func NewMultiTree(rootPath string, opts TreeOptions) *MultiTree

func (*MultiTree) Close 

func (mt *MultiTree) Close() error

func (*MultiTree) Hash 

func (mt *MultiTree) Hash() []byte

Hash is a stand in for code at https://github.com/cosmos/cosmos-sdk/blob/80dd55f79bba8ab675610019a5764470a3e2fef9/store/types/commit_info.go#L30 it used in testing. App chains should use the store hashing code referenced above instead.

func (*MultiTree) LoadVersion 

func (mt *MultiTree) LoadVersion(version int64) error

func (*MultiTree) MountTree 

func (mt *MultiTree) MountTree(storeKey string) error

func (*MultiTree) MountTrees 

func (mt *MultiTree) MountTrees() error

func (*MultiTree) QueryReport 

func (mt *MultiTree) QueryReport(bins int) error

func (*MultiTree) SaveVersion 

func (mt *MultiTree) SaveVersion() ([]byte, int64, error)

func (*MultiTree) SaveVersionConcurrently 

func (mt *MultiTree) SaveVersionConcurrently() ([]byte, int64, error)

func (*MultiTree) SetInitialVersion 

func (mt *MultiTree) SetInitialVersion(version int64) error

func (*MultiTree) SnapshotConcurrently 

func (mt *MultiTree) SnapshotConcurrently() error

func (*MultiTree) WarmLeaves 

func (mt *MultiTree) WarmLeaves() error

type Node 

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

Node represents a node in a Tree.

func IngestSnapshot 

func IngestSnapshot(conn *sqlite3.Conn, prefix string, version int64, nextFn func() (*SnapshotNode, error)) (*Node, error)

func MakeNode 

func MakeNode(pool *NodePool, nodeKey NodeKey, buf []byte) (*Node, error)

MakeNode constructs a *Node from an encoded byte slice.

func NewImportNode 

func NewImportNode(key, value []byte, version int64, height int8) *Node

func (*Node) Bytes 

func (node *Node) Bytes() ([]byte, error)

func (*Node) GetHash 

func (node *Node) GetHash() []byte

func (*Node) Height 

func (node *Node) Height() int8

func (*Node) Key 

func (node *Node) Key() []byte

func (*Node) String 

func (node *Node) String() string

func (*Node) Value 

func (node *Node) Value() []byte

func (*Node) Version 

func (node *Node) Version() int64

func (*Node) WriteBytes 

func (node *Node) WriteBytes(w io.Writer) error

type NodeKey 

type NodeKey [12]byte

NodeKey represents a key of node in the DB.

func NewNodeKey 

func NewNodeKey(version int64, sequence uint32) NodeKey

func (NodeKey) IsEmpty 

func (nk NodeKey) IsEmpty() bool

func (NodeKey) Sequence 

func (nk NodeKey) Sequence() uint32

func (NodeKey) String 

func (nk NodeKey) String() string

String returns a string representation of the node key.

func (NodeKey) Version 

func (nk NodeKey) Version() int64

type NodePool 

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

func NewNodePool 

func NewNodePool() *NodePool

func (*NodePool) Get 

func (np *NodePool) Get() *Node

func (*NodePool) Put 

func (np *NodePool) Put(_ *Node)

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

func (ProofInnerNode) String 

func (pin ProofInnerNode) String() string

type ProofLeafNode 

type ProofLeafNode struct {
	Key       []byte `json:"key"`
	ValueHash []byte `json:"value"`
	Version   int64  `json:"version"`
}

func (ProofLeafNode) Hash 

func (pln ProofLeafNode) Hash() ([]byte, error)

func (ProofLeafNode) String 

func (pln ProofLeafNode) String() string

type SnapshotNode 

type SnapshotNode struct {
	Key     []byte
	Value   []byte
	Version int64
	Height  int8
}

type SnapshotOptions 

type SnapshotOptions struct {
	StoreLeafValues   bool
	WriteCheckpoint   bool
	DontWriteSnapshot bool
	TraverseOrder     TraverseOrderType
}

type SqliteDb 

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

func NewInMemorySqliteDb 

func NewInMemorySqliteDb(pool *NodePool) (*SqliteDb, error)
TODO delete MemoryDb support

NewInMemorySqliteDb probably needs deleting now that the file system is a source of truth for shards. Otherwise shard indexing can be pushed into root.db

func NewSqliteDb 

func NewSqliteDb(pool *NodePool, opts SqliteDbOptions) (*SqliteDb, error)

func (*SqliteDb) Close 

func (sql *SqliteDb) Close() error

func (*SqliteDb) GetLatestLeaf 

func (sql *SqliteDb) GetLatestLeaf(key []byte) (val []byte, topErr error)

func (*SqliteDb) ImportMostRecentSnapshot 

func (sql *SqliteDb) ImportMostRecentSnapshot(
	targetVersion int64, traverseOrder TraverseOrderType, loadLeaves bool) (root *Node, version int64, topErr error)

func (*SqliteDb) ImportSnapshotFromTable 

func (sql *SqliteDb) ImportSnapshotFromTable(
	version int64, traverseOrder TraverseOrderType, loadLeaves bool) (root *Node, topErr error)

func (*SqliteDb) LoadRoot 

func (sql *SqliteDb) LoadRoot(version int64) (root *Node, topErr error)

func (*SqliteDb) Revert 

func (sql *SqliteDb) Revert(version int) error

func (*SqliteDb) SaveRoot 

func (sql *SqliteDb) SaveRoot(version int64, node *Node, isCheckpoint bool) (topErr error)

func (*SqliteDb) Snapshot 

func (sql *SqliteDb) Snapshot(ctx context.Context, tree *Tree) (topErr error)

func (*SqliteDb) WarmLeaves 

func (sql *SqliteDb) WarmLeaves() error

func (*SqliteDb) WriteLatestLeaves 

func (sql *SqliteDb) WriteLatestLeaves(tree *Tree) (topErr error)

func (*SqliteDb) WriteSnapshot 

func (sql *SqliteDb) WriteSnapshot(
	ctx context.Context, version int64, nextFn func() (*SnapshotNode, error), opts SnapshotOptions,
) (root *Node, topErr error)

type SqliteDbOptions 

type SqliteDbOptions struct {
	Path       string
	Mode       int
	MmapSize   uint64
	WalSize    int
	CacheSize  int
	ConnArgs   string
	ShardTrees bool
	Readonly   bool
	// contains filtered or unexported fields
}

func (SqliteDbOptions) EstimateMmapSize 

func (opts SqliteDbOptions) EstimateMmapSize() (uint64, error)

type SqliteKVStore 

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

SqliteKVStore is a generic KV store which uses sqlite as the backend and be used by applications to store and retrieve generic key-value pairs, probably for metadata.

func NewSqliteKVStore 

func NewSqliteKVStore(opts SqliteDbOptions) (kv *SqliteKVStore, err error)

func (*SqliteKVStore) Delete 

func (kv *SqliteKVStore) Delete(key []byte) error

func (*SqliteKVStore) Get 

func (kv *SqliteKVStore) Get(key []byte) (value []byte, err error)

func (*SqliteKVStore) Set 

func (kv *SqliteKVStore) Set(key []byte, value []byte) error

type TraverseOrderType 

type TraverseOrderType uint8

TraverseOrderType is the type of the order in which the tree is traversed. 

const (
	PreOrder TraverseOrderType = iota
	PostOrder
)

type Tree 

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

func NewTree 

func NewTree(sql *SqliteDb, pool *NodePool, opts TreeOptions) *Tree

func (*Tree) Close 

func (tree *Tree) Close() error

func (*Tree) DeleteVersionsTo 

func (tree *Tree) DeleteVersionsTo(_ int64) error

func (*Tree) Export 

func (tree *Tree) Export(version int64, order TraverseOrderType) (*Exporter, error)

func (*Tree) Get 

func (tree *Tree) Get(key []byte) ([]byte, error)

func (*Tree) GetByIndex 

func (tree *Tree) GetByIndex(index int64) (key []byte, value []byte, err error)

func (*Tree) GetProof 

func (tree *Tree) GetProof(version int64, key []byte) (proof *ics23.CommitmentProof, err error)

func (*Tree) GetRecent 

func (tree *Tree) GetRecent(version int64, key []byte) (bool, []byte, error)

func (*Tree) GetWithIndex 

func (tree *Tree) GetWithIndex(key []byte) (int64, []byte, error)

func (*Tree) Has 

func (tree *Tree) Has(key []byte) (bool, error)

func (*Tree) Hash 

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

func (*Tree) Height 

func (tree *Tree) Height() int8

func (*Tree) Import 

func (tree *Tree) Import(version int64) (*Importer, error)

func (*Tree) IterateRecent 

func (tree *Tree) IterateRecent(version int64, start, end []byte, ascending bool) (bool, Iterator)

func (*Tree) Iterator 

func (tree *Tree) Iterator(start, end []byte, inclusive bool) (itr Iterator, err error)

func (*Tree) LoadSnapshot 

func (tree *Tree) LoadSnapshot(version int64, traverseOrder TraverseOrderType) (err error)

func (*Tree) LoadVersion 

func (tree *Tree) LoadVersion(version int64) (err error)

func (*Tree) NewLeafNode 

func (tree *Tree) NewLeafNode(key []byte, value []byte) *Node

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

func (*Tree) PathToLeaf 

func (tree *Tree) PathToLeaf(node *Node, 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 (*Tree) ReadonlyClone 

func (tree *Tree) ReadonlyClone() (*Tree, error)

func (*Tree) Remove 

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

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 (*Tree) ReverseIterator 

func (tree *Tree) ReverseIterator(start, end []byte) (itr Iterator, err error)

func (*Tree) SaveSnapshot 

func (tree *Tree) SaveSnapshot() (err error)

func (*Tree) SaveVersion 

func (tree *Tree) SaveVersion() ([]byte, int64, error)

SaveVersion saves the staged version of the tree to storage. It returns the hash of the root node. Not thread-safe.

func (*Tree) Set 

func (tree *Tree) Set(key, value []byte) (updated bool, err error)

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. It returns true when an existing value was updated, while false means it was a new key.

func (*Tree) SetInitialVersion 

func (tree *Tree) SetInitialVersion(version int64) error

func (*Tree) SetShouldCheckpoint 

func (tree *Tree) SetShouldCheckpoint()

func (*Tree) Size 

func (tree *Tree) Size() int64

func (*Tree) Version 

func (tree *Tree) Version() int64

func (*Tree) WorkingBytes 

func (tree *Tree) WorkingBytes() uint64

func (*Tree) WriteLatestLeaves 

func (tree *Tree) WriteLatestLeaves() (err error)

type TreeIterator 

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

func (*TreeIterator) Close 

func (i *TreeIterator) Close() error

func (*TreeIterator) Domain 

func (i *TreeIterator) Domain() (start []byte, end []byte)

func (*TreeIterator) Error 

func (i *TreeIterator) Error() error

func (*TreeIterator) Key 

func (i *TreeIterator) Key() (key []byte)

func (*TreeIterator) Next 

func (i *TreeIterator) Next()

func (*TreeIterator) Valid 

func (i *TreeIterator) Valid() bool

func (*TreeIterator) Value 

func (i *TreeIterator) Value() (value []byte)

type TreeOptions 

type TreeOptions struct {
	CheckpointInterval  int64
	CheckpointMemory    uint64
	StateStorage        bool
	HeightFilter        int8
	EvictionDepth       int8
	MetricsProxy        metrics.Proxy
	PruneRatio          float64
	MinimumKeepVersions int64
}

func DefaultTreeOptions 

func DefaultTreeOptions() TreeOptions

type VersionRange 

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

func (*VersionRange) Add 

func (r *VersionRange) Add(version int64) error

func (*VersionRange) Copy 

func (r *VersionRange) Copy() *VersionRange

func (*VersionRange) FindMemoized 

func (r *VersionRange) FindMemoized(version int64) int64

func (*VersionRange) FindNext 

func (r *VersionRange) FindNext(version int64) int64

func (*VersionRange) FindPrevious 

func (r *VersionRange) FindPrevious(version int64) int64

func (*VersionRange) FindRecent 

func (r *VersionRange) FindRecent(version, n int64) int64

func (*VersionRange) FindShard 

func (r *VersionRange) FindShard(version int64) int64

FindShard returns the shard ID for the given version. It calls FindPrevious, but if version < first shardID it returns the first shardID.

func (*VersionRange) First 

func (r *VersionRange) First() int64

func (*VersionRange) Last 

func (r *VersionRange) Last() int64

func (*VersionRange) Len 

func (r *VersionRange) Len() int

func (*VersionRange) Remove 

func (r *VersionRange) Remove(version int64)

func (*VersionRange) TruncateTo 

func (r *VersionRange) TruncateTo(version int64)

Source Files

View all Source files

Directories

Path Synopsis
cmd
gen
rollback
scan
snapshot
migrate module

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.