tendermint多版本状态库

平衡二叉树简介

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

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

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

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

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

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

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

多版本状态库 avl + merkle

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

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

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

安装iavl：

~$ go get github.com/tendermint/iavl

使用多版本状态库

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

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的结构声明如下，除了iavl库，额外的两个成员分别记录状态的最后版本号以及最后状态的默克尔哈希：

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

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

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()方法获取特定版本的指定地址余额：

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()方法修改指定地址的余额：

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()提交当前工作区的修改：

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

升级代币状态机

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

type TokenApp struct {
  types.BaseApplication
  store *Store
}

转账交易

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
}

发行交易

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

func (app *TokenApp) Commit() types.ResponseCommit{
  hash,ver,_ := app.store.Commit()
  app.Version = ver
  app.Hash = hash
  return types.ResponseCommit{Data:hash}
}

查询状态

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