mavl

Documentation

Overview

Package mavl 默克尔平衡树算法实现以及裁剪

Index

• Variables
• func ClosePrune()
• func DelKVPair(db dbm.DB, storeDel *types.StoreGet) ([]byte, [][]byte, error)
• func DelLeafCountKV(db dbm.DB, blockHeight int64) error
• func EnableMVCC(enable bool)
• func EnableMavlPrefix(enable bool)
• func EnableMemTree(enable bool)
• func EnableMemVal(enable bool)
• func EnablePrune(enable bool)
• func GetKVPair(db dbm.DB, storeGet *types.StoreGet) ([][]byte, error)
• func GetKVPairProof(db dbm.DB, roothash []byte, key []byte) ([]byte, error)
• func InnerNodeProofHash(childHash []byte, branch *types.InnerNode) []byte
• func IterateRangeByStateHash(db dbm.DB, statehash, start, end []byte, ascending bool, ...)
• func LoadTree2MemDb(db dbm.DB, hash []byte, mp map[uint64]struct{})
• func PrintLeafNodeParent(db dbm.DB, key, hash []byte, height int64)
• func PrintMemStats(height int64)
• func PrintNode(node *Node)
• func PrintNodeDb(db dbm.DB, hash []byte)
• func PrintSameLeafKey(db dbm.DB, key string)
• func PrintTreeLeaf(db dbm.DB, roothash []byte)
• func PruningTree(db dbm.DB, curHeight int64)
• func PruningTreePrintDB(db dbm.DB, prefix []byte)
• func ReleaseGlobalMem()
• func SetKVPair(db dbm.DB, storeSet *types.StoreSet, sync bool) ([]byte, error)
• func SetPruneHeight(height int)
• func TkCloseCacheLen(len int32)
• func VerifyKVPairProof(db dbm.DB, roothash []byte, keyvalue types.KeyValue, proof []byte) bool
• type MemTreeOpera
• type Node
  • func MakeNode(buf []byte, t *Tree) (node *Node, err error)
  • func NewNode(key []byte, value []byte) *Node
  • func (node *Node) Hash(t *Tree) []byte
• type Proof
  • func ReadProof(roothash []byte, leafhash []byte, data []byte) (*Proof, error)
  • func (proof *Proof) Root() []byte
  • func (proof *Proof) Verify(key []byte, value []byte, root []byte) bool
• type Tree
  • func NewTree(db dbm.DB, sync bool) *Tree
  • func (t *Tree) ConstructProof(key []byte) (value []byte, proof *Proof)
  • func (t *Tree) Copy() *Tree
  • func (t *Tree) Get(key []byte) (index int32, value []byte, exists bool)
  • func (t *Tree) GetByIndex(index int32) (key []byte, value []byte)
  • func (t *Tree) GetHash(key []byte) (index int32, hash []byte, exists bool)
  • func (t *Tree) Has(key []byte) bool
  • func (t *Tree) Hash() []byte
  • func (t *Tree) Height() int32
  • 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, fn func(key, value []byte) bool) (stopped bool)
  • func (t *Tree) Load(hash []byte) (err error)
  • func (t *Tree) Proof(key []byte) (value []byte, proofBytes []byte, exists bool)
  • func (t *Tree) Remove(key []byte) (value []byte, removed bool)
  • func (t *Tree) RemoveLeafCountKey(height int64)
  • func (t *Tree) Save() []byte
  • func (t *Tree) Set(key []byte, value []byte) (updated bool)
  • func (t *Tree) SetBlockHeight(height int64)
  • func (t *Tree) Size() int32
• type TreeARC
  • func NewTreeARC(size int) *TreeARC
  • func (ta *TreeARC) Add(key, value interface{})
  • func (ta *TreeARC) Contains(key interface{}) bool
  • func (ta *TreeARC) Delete(key interface{})
  • func (ta *TreeARC) Get(key interface{}) (value interface{}, ok bool)
  • func (ta *TreeARC) Len() int
• type TreeMap
  • func NewTreeMap(size int) *TreeMap
  • func (tm *TreeMap) Add(key, value interface{})
  • func (tm *TreeMap) Contains(key interface{}) bool
  • func (tm *TreeMap) Delete(key interface{})
  • func (tm *TreeMap) Get(key interface{}) (value interface{}, ok bool)
  • func (tm *TreeMap) Len() int

Variables

var (
	// ErrNodeNotExist node is not exist
	ErrNodeNotExist = errors.New("ErrNodeNotExist")
)

Functions

func ClosePrune

func ClosePrune()

ClosePrune 关闭裁剪

func DelKVPair

func DelKVPair(db dbm.DB, storeDel *types.StoreGet) ([]byte, [][]byte, error)

DelKVPair 剔除key对应的节点在本次tree中，返回新的roothash和key对应的value

func DelLeafCountKV

func DelLeafCountKV(db dbm.DB, blockHeight int64) error

DelLeafCountKV 回退时候用于删除叶子节点的索引节点

func EnableMVCC

func EnableMVCC(enable bool)

EnableMVCC 使能MVCC

func EnableMavlPrefix

func EnableMavlPrefix(enable bool)

EnableMavlPrefix 使能mavl加前缀

func EnableMemTree

func EnableMemTree(enable bool)

EnableMemTree 使能mavl数据载入内存

func EnableMemVal

func EnableMemVal(enable bool)

EnableMemVal 使能mavl叶子节点数据载入内存

func EnablePrune

func EnablePrune(enable bool)

EnablePrune 使能裁剪

func GetKVPair

func GetKVPair(db dbm.DB, storeGet *types.StoreGet) ([][]byte, error)

GetKVPair 获取kv对外接口

func GetKVPairProof

func GetKVPairProof(db dbm.DB, roothash []byte, key []byte) ([]byte, error)

GetKVPairProof 获取指定k:v pair的proof证明

func InnerNodeProofHash

func InnerNodeProofHash(childHash []byte, branch *types.InnerNode) []byte

InnerNodeProofHash 计算inner节点的hash

func IterateRangeByStateHash

func IterateRangeByStateHash(db dbm.DB, statehash, start, end []byte, ascending bool, fn func([]byte, []byte) bool)

IterateRangeByStateHash 在start和end之间的键进行迭代回调[start, end)

func LoadTree2MemDb

func LoadTree2MemDb(db dbm.DB, hash []byte, mp map[uint64]struct{})

LoadTree2MemDb 从数据库中载入mem tree

func PrintLeafNodeParent

func PrintLeafNodeParent(db dbm.DB, key, hash []byte, height int64)

PrintLeafNodeParent 查询叶子节点的父节点

func PrintMemStats

func PrintMemStats(height int64)

PrintMemStats 打印内存使用情况

func PrintNode

func PrintNode(node *Node)

PrintNode the in-memory children recursively.

func PrintNodeDb

func PrintNodeDb(db dbm.DB, hash []byte)

PrintNodeDb 查询hash节点以及其子节点

func PrintSameLeafKey

func PrintSameLeafKey(db dbm.DB, key string)

PrintSameLeafKey 查询相同的叶子节点

func PrintTreeLeaf

func PrintTreeLeaf(db dbm.DB, roothash []byte)

PrintTreeLeaf 通过roothash打印所有叶子节点

func PruningTree

func PruningTree(db dbm.DB, curHeight int64)

PruningTree 裁剪树

func PruningTreePrintDB

func PruningTreePrintDB(db dbm.DB, prefix []byte)

PruningTreePrintDB pruning tree print db

func ReleaseGlobalMem

func ReleaseGlobalMem()

ReleaseGlobalMem 释放全局缓存

func SetKVPair

func SetKVPair(db dbm.DB, storeSet *types.StoreSet, sync bool) ([]byte, error)

SetKVPair 设置kv对外接口

func SetPruneHeight

func SetPruneHeight(height int)

SetPruneHeight 设置每次裁剪高度

func TkCloseCacheLen

func TkCloseCacheLen(len int32)

TkCloseCacheLen 设置缓存close ticket数目

func VerifyKVPairProof

func VerifyKVPairProof(db dbm.DB, roothash []byte, keyvalue types.KeyValue, proof []byte) bool

VerifyKVPairProof 验证KVPair 的证明

Types

type MemTreeOpera

type MemTreeOpera interface {
	Add(key, value interface{})
	Get(key interface{}) (value interface{}, ok bool)
	Delete(key interface{})
	Contains(key interface{}) bool
	Len() int
}

MemTreeOpera memtree操作接口

type Node

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

Node merkle avl Node

func MakeNode

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

MakeNode 从数据库中读取数据，创建Node NOTE: The hash is not saved or set. The caller should set the hash afterwards. (Presumably the caller already has the hash)

func NewNode

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

NewNode 创建节点；保存数据的是叶子节点

func (*Node) Hash

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

Hash 计算节点的hash

type Proof

type Proof struct {
	LeafHash   []byte
	InnerNodes []*types.InnerNode
	RootHash   []byte
}

Proof merkle avl tree proof证明结构体

func ReadProof

func ReadProof(roothash []byte, leafhash []byte, data []byte) (*Proof, error)

ReadProof will deserialize a MAVLProof from bytes

func (*Proof) Root

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

Root 证明节点的root hash

func (*Proof) Verify

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

Verify key:value 的proof确认

type Tree

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

Tree merkle avl tree

func NewTree

func NewTree(db dbm.DB, sync bool) *Tree

NewTree 新建一个merkle avl 树

func (*Tree) ConstructProof

func (t *Tree) ConstructProof(key []byte) (value []byte, proof *Proof)

ConstructProof Returns nil, nil if key is not in tree.

func (*Tree) Copy

func (t *Tree) Copy() *Tree

Copy copy tree

func (*Tree) Get

func (t *Tree) Get(key []byte) (index int32, value []byte, exists bool)

Get 通过key获取leaf节点信息

func (*Tree) GetByIndex

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

GetByIndex 通过index获取leaf节点信息

func (*Tree) GetHash

func (t *Tree) GetHash(key []byte) (index int32, hash []byte, exists bool)

GetHash 通过key获取leaf节点hash信息

func (*Tree) Has

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

Has 判断key是否存在tree中

func (*Tree) Hash

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

Hash 计算tree 的roothash

func (*Tree) Height

func (t *Tree) Height() int32

Height 获取tree的高度

func (*Tree) Iterate

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

Iterate 依次迭代遍历树的所有键

func (*Tree) IterateRange

func (t *Tree) IterateRange(start, end []byte, ascending bool, fn func(key []byte, value []byte) bool) (stopped bool)

IterateRange 在start和end之间的键进行迭代回调[start, end)

func (*Tree) IterateRangeInclusive

func (t *Tree) IterateRangeInclusive(start, end []byte, ascending bool, fn func(key, value []byte) bool) (stopped bool)

IterateRangeInclusive 在start和end之间的键进行迭代回调[start, end]

func (*Tree) Load

func (t *Tree) Load(hash []byte) (err error)

Load 从db中加载rootnode

func (*Tree) Proof

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

Proof 获取指定k:v pair的proof证明

func (*Tree) Remove

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

Remove 删除key对应的节点

func (*Tree) RemoveLeafCountKey

func (t *Tree) RemoveLeafCountKey(height int64)

RemoveLeafCountKey 删除叶子节点的索引节点（防止裁剪时候回退产生的误删除）

func (*Tree) Save

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

Save 保存整个tree的节点信息到db中

func (*Tree) Set

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

Set 设置k:v pair到tree中

func (*Tree) SetBlockHeight

func (t *Tree) SetBlockHeight(height int64)

SetBlockHeight 设置block高度到tree

func (*Tree) Size

func (t *Tree) Size() int32

Size 获取tree的叶子节点数

type TreeARC

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

TreeARC lru的mem tree

func NewTreeARC

func NewTreeARC(size int) *TreeARC

NewTreeARC new lru mem tree

func (*TreeARC) Add

func (ta *TreeARC) Add(key, value interface{})

Add 添加元素

func (*TreeARC) Contains

func (ta *TreeARC) Contains(key interface{}) bool

Contains 查看是否包含元素

func (*TreeARC) Delete

func (ta *TreeARC) Delete(key interface{})

Delete 删除元素

func (*TreeARC) Get

func (ta *TreeARC) Get(key interface{}) (value interface{}, ok bool)

Get 获取元素

func (*TreeARC) Len

func (ta *TreeARC) Len() int

Len 元素长度

type TreeMap

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

TreeMap map形式memtree

func NewTreeMap

func NewTreeMap(size int) *TreeMap

NewTreeMap new mem tree

func (*TreeMap) Add

func (tm *TreeMap) Add(key, value interface{})

Add 添加元素

func (*TreeMap) Contains

func (tm *TreeMap) Contains(key interface{}) bool

Contains 查看是否包含元素

func (*TreeMap) Delete

func (tm *TreeMap) Delete(key interface{})

Delete 删除元素

func (*TreeMap) Get

func (tm *TreeMap) Get(key interface{}) (value interface{}, ok bool)

Get 获取元素

func (*TreeMap) Len

func (tm *TreeMap) Len() int

Len 元素长度