管中窥豹 EOS 数据存储 | database::find

服务端缓存数据的存储方式,既要支撑起上层业务的快速增删改查,又要保持数据一致性实现持久化存储,是决定性能吞吐量的核心因素之一。

eos 的 database 利用 multi_index_container 容器实现了数据的快速增删改查。本文通过详细分析 database::find 模板函数的实现窥探eos的内存模型,eos 的版本是 mainnet-1.5.1 ,文件路径在 eos/libraries/chainbase/include/chainbase/chainbase.hpp。

本文以 get_abi 函数为入口开始分析,

利用 database 的 find 模板函数,模板函数的类型实参分别为 account_object 类型和 by_name 类型(此处 database::find 模板函数的类型参数为3个,最后一个可以通过函数的实际参数类型推导出来即 eosio::chain::name ,所以不需要显式声明),实现通过账户名称快速查找到账户信息。此处我们的第一感觉 database::find 的实现应该是利用关联性容器的 find,比如 std::map 的 find,std::map 内部是红黑树实现的平衡二叉树,理论上它的查找操作复杂度为对数级别。

database::find 函数分析

接下来我们逐行分析 database::find 的代码

get_index_type 模板类分析

get_index_type 模板类的内部自定义类型 type 为各个 ObjectType 关联的多索引容器类型,此处 account_object 关联的多索引容器类型为 account_index 。get_index_type 模板类的通用模板定义为:

各个需要存储的 ObjectType 通过宏 CHAINBASE_SET_INDEX_TYPE 特化此模板类,从而实现了通过 ObjectType 类型找到关联的多索引容器类型。

account_index 多索引容器分析

理解了此特化过程,可以通过宏,快速找到 ObjectType 关联的 index_type 。搜索代码可得:account_object 关联的类型为 account_index :

具体的 account_object 类型和 account_index 类型如下:

查看 account_index 类型,我们发现此容器建立了两个 ordered_unique 索引,索引的 tag 分别为 by_id 和 by_name 。ordered_unique 索引大家可以理解为 std::map ,key 不能重复,按照中序遍历为从小到大排序,顺序依赖小于语义的函数实现。

database::get_index 模板函数分析

回到 database 的 find 函数,怎么通过 index_type 类型找到具体的 index_type 类型对象实例,此过程调用模板函数 get_index ,模板函数实参类型为 account_index 类型:

generic_index 模板类分析

关于 generic_index 模板类型及其 undo 和 commit 此处暂时不展开。eos 通过 database 的 add_index 模板函数添加要存储的 generic_index<index_type> 对象实例,所有的 generic_index<index_type> 实例对象的地址会存储在 database 的成员变量 _index_map 中,以 index_type::value_type::type_id 做为 vector 的下标索引找到 generic_index<index_type> 的对象实例。

通过 generic_index 的 indices 函数我们找到了 index_type 的实例,既 multi_index_container 容器类型的对象实例,然后可以根据索引的 tag 获取获取类似于 std::map 的对象,实现快速查找。

回到 database 的 find 函数,利用 multi_index_container的 get< IndexedByType >() 函数,我们通过 by_name 这个 tag 找到类 std::map 对象,用对数复杂度的 find 函数找到 account_object 对象。实现了通过名称查找账户信息。

总结

通过以上分析,我们可以总结下 find 函数的工作流程:

  1. get_index_type 模板类的特化实现了通过 ObjectType 获取相对应的 index_type。
  2. 以 index_type::value_type::type_id 做为 _index_map 这个 vector 的下标索引找到 generic_index<index_type> 的对象实例,进而获取 index_type 类型对象实例。
  3. 在 index_type 类型对象实例中通过 IndexedByType 类型 tag 获取关联性容器对象实例,进而进行数据操作。

database 的 _index_map 成员变量利用 vector 存储了 generic_index<index_type> 对象的指针(可以通过 database::add_index 函数查看存储了那些 generic_index 对象,可以通过宏 CHAINBASE_SET_INDEX_TYPE 查找 ObjectType 和与之关联的 index_type 类型)。找到 multi_index_container 类型定义可以看到建立了那些 tag 索引,是不可重复的红黑树,还是可重复的红黑树,是不可重复的哈希表,还是可以重复的哈希表,是随机访问数组,还是其他,进而可以有效利用缓存里面的 eos 数据,利用 multi_index_container 的索引快速获取 account_object 对象,进行相应的对象上的操作。

预告

管中窥豹EOS数据存储系列致力于深入源码底层细节剖析 eos 的存储模型。 下篇管中窥豹EOS数据存储系列重点讲述 database::add_index 和 _index_map ,请关注后续更新。

1 thought on “管中窥豹 EOS 数据存储 | database::find

发表评论

电子邮件地址不会被公开。 必填项已用*标注