mavl

Documentation

Overview

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

Index

• Constants
• Variables
• func ClosePrune()
• func DelKVPair(db dbm.DB, storeDel *types.StoreGet, treeCfg *TreeConfig) ([]byte, [][]byte, error)
• func DelLeafCountKV(db dbm.DB, blockHeight int64, treeCfg *TreeConfig) error
• func GetKVPair(db dbm.DB, storeGet *types.StoreGet, treeCfg *TreeConfig) ([][]byte, error)
• func GetKVPairProof(db dbm.DB, roothash []byte, key []byte, treeCfg *TreeConfig) ([]byte, error)
• func InitGlobalMem(treeCfg *TreeConfig)
• func InnerNodeProofHash(childHash []byte, branch *types.InnerNode) []byte
• func IterateRangeByStateHash(db dbm.DB, statehash, start, end []byte, ascending bool, treeCfg *TreeConfig, ...)
• 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, treeCfg *TreeConfig)
• func PruningTree(db dbm.DB, curHeight int64, treeCfg *TreeConfig)
• func PruningTreePrintDB(db dbm.DB, prefix []byte)
• func ReleaseGlobalMem()
• func SetKVPair(db dbm.DB, storeSet *types.StoreSet, sync bool, treeCfg *TreeConfig) ([]byte, error)
• 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, treeCfg *TreeConfig) *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 TreeConfig
• 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

Constants

const (

	//DefaultPruneHeight ...
	DefaultPruneHeight = 10000
)

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, treeCfg *TreeConfig) ([]byte, [][]byte, error)

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

func DelLeafCountKV

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

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

func GetKVPair

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

GetKVPair 获取kv对外接口

func GetKVPairProof

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

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

func InitGlobalMem

func InitGlobalMem(treeCfg *TreeConfig)

InitGlobalMem 初始化全局变量

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, treeCfg *TreeConfig, 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, treeCfg *TreeConfig)

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

func PruningTree

func PruningTree(db dbm.DB, curHeight int64, treeCfg *TreeConfig)

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, treeCfg *TreeConfig) ([]byte, error)

SetKVPair 设置kv对外接口

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, treeCfg *TreeConfig) *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 TreeConfig

type TreeConfig struct {
	EnableMavlPrefix bool
	EnableMVCC       bool
	EnableMavlPrune  bool
	PruneHeight      int32
	EnableMemTree    bool
	EnableMemVal     bool
	TkCloseCacheLen  int32
}

TreeConfig ...

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 元素长度