tendermint多版本状态库

平衡二叉树简介

在之前的课程中,我们简单地使用磁盘文件来保存状态,对于简单的学习或验证 而言没有问题,但在生产环境中,tendermint推荐我们使用其基于avl树实现的 多版本状态库。

avl树得名于发明者G. M. Adelson-Velsky和Evgenii Landis,它是一种 自平衡二叉检索树,这包括两个核心的思想:二叉、平衡。

二叉是指整棵树中每个节点最多有两个子节点,左侧的子节点值一定小于父节点值,而 右侧的子节点值一定大于父节点值,二叉树的主要用途是进行数据检索:当查找指定的数值时, 只需要逐层与节点值比较即可快速定位,因此被称为二叉检索树。

例如,下图就是一个典型的二叉检索树,每个节点列出了其表示的值:

btree

当我们需要在树中定位值为19的节点时,从根节点出发,只需要三次对比就可以定位:

10 < 50,因此进入50的左侧子树继续搜索
19 > 17,因此进入17的右侧子树继续搜索
19 < 23,因此进入23的左侧子树继续搜索
19 == 19,定位成功
平衡是指树中任一节点旳左右两棵子树的高度差不超过1。例如,上面的树就不是平衡的, 该数据集对应的平衡树如下图所示:
avl-tree

自平衡指的是树的形成算法:当一个新的节点加入树树中时,算法将通过旋转等手段使整棵树 始终处于平衡状态,因此看起来就树就是靠自己找到了平衡状态。

多版本状态库 avl + merkle

为了快速计算状态集合的哈希以及进行默克尔验证,基于avl树和merkle树,tendermint实现了 多版本状态库iavl,它提供了类似于key/value数据库的操作接口:

iavl-store

为了便于计算默克尔哈希,在tendermint的avl树实现中,只有在叶节点中才会保存实际的状态值, 中间节点仅用于key的比较和哈希的计算。由于在所有节点中已经预存了左右子节点的哈希,因此可以 快速获取整棵树的根节点哈希,即状态集合的哈希。

iavl支持同一个key值的多个版本,这通过在节点结构中引入version项来实现:当一个节点被新版本 的数据更新后,iavl会同时保留其历史版本,因此使用iavl可以快速回溯到任何状态的任意历史版本。

安装iavl:

~$ go get github.com/tendermint/iavl

使用多版本状态库

tendermint/iavl软件包的主要模型包括可修改树(MutableTree)、只读树(ImmutableTree) 以及状态证据(RangeProof)等,其关系如下图所示:

iavl-um

ImmutableTree是一个只读的二叉平衡哈希树,而MutableTree则提供了Set()方法来修改树 的节点构成并保证其处于平衡状态,RangeProof则是默克尔证据的封装结构。

加载状态库

iavl使用leveldb数据库保存节点以及其关系,例如,下面的代码从当前目录下的 counter数据库加载状态库,并使用Load()方法将载入最后版本的状态:

1
2
3
gdb,_ := db.NewGoLevelDB("counter",".")
tree := iavl.NewMutableTree(gdb,128)
tree.Load()

工作区

类似于git,iavl也有一个工作区的概念 —— 所有的修改操作都是在工作区完成的,而不是 直接操作状态库。可以使用Load()方法载入最后(新)版本的状态库到工作区,也可以使用 LoadVersion()方法载入指定版本的状态库到工作区。

一旦将状态载入工作区,我们就可以利用Set()方法设置指定的键/值对了。例如,下面的 代码设置键name的值为tommy:

tree.Set([]byte("name"),[]byte("Tommy"))
当我们调用Get()方法时,是从当前工作区中读取指定键的值,例如:

idx,val := tree.Get([]byte("name"))
其中,返回的idx表示该键对应的叶节点在集合中的先后序号,val表示键对应的值。

如果需要从状态库中指定版本读取键值,可以使用GetVersioned()方法。例如, 下面的代码读取版本2的指定键值:

idx,val := tree.GetVersioned([]byte{"name"},2)
提交新版本

所有的修改完毕后,使用SaveVersion()方法将工作区的变更提交到库中,这将返回根节点 哈希和新的版本号:

hash,ver,err := tree.SaveVersion()
iavl库的版本号是从0开始,每个版本加1。

封装iavl操作

为了简化iavl的操作,我们将编解码等繁琐的操作封装到一个单独的结构Store里:

store

Store的结构声明如下,除了iavl库,额外的两个成员分别记录状态的最后版本号以及最后 状态的默克尔哈希:

1
2
3
4
5
type Store struct {
tree *iavl.MutableTree //iavl库
LastVersion int64 //状态的最后版本号
LastHash []byte //最后版本状态的根哈希
}

GetBalance()方法获取指定地址的当前(最后版本)余额:

1
2
3
4
5
6
7
8
func (store *Store) GetBalance(addr crypto.Address) (int,error) {
_,bz := store.tree.Get(addr)
if bz == nil { return 0,errors.New("account not found") }
var val int
err := codec.UnmarshalBinary(bz,&val)
if err !=nil { return 0,errors.New("decode error")}
return val,nil
}

GetBalanceVersoined()方法获取特定版本的指定地址余额:

1
2
3
4
5
6
7
8
func (store *Store) GetBalanceVersioned(addr crypto.Address,version int64) (int,error) {
_,bz := store.tree.GetVersioned(addr,version)
if bz == nil { return 0,errors.New("account not found on this version") }
var val int
err := codec.UnmarshalBinary(bz,&val)
if err !=nil { return 0,errors.New("decode error")}
return val,nil
}

SetBalance()方法修改指定地址的余额:

1
2
3
4
5
6
func (store *Store) SetBalance(addr crypto.Address,value int) error {
bz,err := codec.MarshalBinary(value)
if err != nil { return err }
store.tree.Set(addr,bz)
return nil
}

Commit()提交当前工作区的修改:

1
2
3
4
5
6
func (store *Store) Commit() {
hash,ver,err := store.tree.SaveVersion()
if err != nil { panic(err) }
store.LastVersion = ver
store.LastHash = hash
}

升级代币状态机

基于Store的封装,很容易为代币状态机加入iavl的支持:

1
2
3
4
type TokenApp struct {
types.BaseApplication
store *Store
}

转账交易

1
2
3
4
5
6
7
8
func (app *TokenApp) transfer(from,to crypto.Address,value int) error {
fromBalance,_ := app.store.GetBalance(from)
if fromBalance < value {return errors.New("no enough balance")}
toBalance,_ := app.GetBalance(to)
app.SetBalance(from,fromBalance - val)
app.SetBalance(to,toBalance + val)
return nil
}

发行交易

1
2
3
4
5
6
func (app *TokenApp) issue(issuer,to crypto.Address,value int) error {
if !bytes.Equal(issuer,SYSTEM_ISSUER) return { errors.New("invalid issuer") }
toBalance,_ := app.store.GetBalance(to)
app.SetBalance(to,toBalance + val)
return nil
}

实现Commit()

1
2
3
4
5
6
func (app *TokenApp) Commit() types.ResponseCommit{
hash,ver,_ := app.store.Commit()
app.Version = ver
app.Hash = hash
return types.ResponseCommit{Data:hash}
}

查询状态

1
2
3
4
5
6
7
8
func (app *AccountApp) Query(req types.RequestQuery) types.ResponseQuery{
if len(req.Data) == 0 {
return types.ResponseQuery{Code:1,Info:"no address specified"}
}
addr := cryto.Address(req.Data)
val,_:= app.store.GetBalance(addr)
return types.ResponseQuery{Key:addr,Value:val}
}

坚持原创技术分享,您的支持将鼓励我继续创作!