Graphene 源码阅读 ~ 数据库篇 ~ 索引模型

最近这一周一直在研究共识机制, 本来想先写一篇共识篇的, 无奈共识涉及到的东西太多, 一直没有构思好怎么写, 眼看着距离上一篇 对象模型 一文越来越远, 再不动笔有跳票嫌疑了, 所以共识篇就暂且往后放, 再来一篇数据库篇凑凑数.

话不多说, 让我们进入数据库篇的第二篇 - 索引模型

索引模型

从源码结构来讲, 索引和前一篇 对象模型 所介绍的 object 基类属于同一层级. 索引结构的定义位于 <db>/index.hpp, <db>/generic_index.php 和 <db>/simple_index.hpp 这三个头文件中. 这里面核心的几个类有 index, generic_index, simple_index, 以及 base_primary_index, primary_index.

index 和 object 一样是个抽象类, 定义的是关于索引的基本操作方法并且成员基本都是纯虚成员, 所以 index 也不能被直接实例化, 需要被继承并被实例化其子类, generic_index 和 simple_index 就是继承自 index 的两个子类, 而且它俩也是模板类, 模板实例化时需以具体对象为参数, generic_index 除了对象参数, 还需要提供一个索引类型参数 MultiIndexType (代码 2.1).

// 代码 2.1

template<typename ObjectType, typename MultiIndexType>
class generic_index : public index
{
    ….
}

实际代码中, 传入的 MultiIndexType 实际上是 boost::multi_index_container<> 模板类的实例, 关于 boost::multi_index_container<> 模板类就不过多展开了, 这里我们只需要知道 multi_index_container<> 能让我们方便的构建多键复合索引就可以了.

base_primary_index 是 primary_index 的基类, 定义了几个回调函数, 关键在于 primary_index (代码 2.2), 这个类一看就知道是代表主键索引, 在这里我们又看到了熟悉的 奇异递归模板模式, 前一篇 对象模型 已经介绍过了, 在实际的 bitshares-core 的代码中, primary_index 的模板参数正是 generic_index 或者 simple_index.

// 代码 2.2

template<typename DerivedIndex>
class primary_index  : public DerivedIndex, public base_primary_index
{
    ….
    ….
}
  

graphene 为每个对象类型 (还记得对象的 space_id 和 type_id 吗?) 都实例对应的 generic_index 和 simple_index 类, 并进而实例对应的 primary_index 类, 进而管理存储所有属于这个类型的所有对象.

在后续的 “对象索引库” 一文中, 我们将会看到 db::object_database 又是 primary_index 的直接上层, 管理着所有类型的 primary_index, 相应的, 在 base_primary_index 类中我们也能看到 object_database& _db; 这个私有成员, 这就是指向操纵本索引的 db::object_database 对象的引用.

下面我们具体浏览一下上述几个类的代码, 假设你手头有一份 bitshares-core 的源码.

代码详解

首先 index 类中定义了下面这两个纯虚方法, 如果你看过 对象模型 那这两个方法的作用应该一看便知. 前面说的每个索引模板实例管理着同一类型下的所有对象, 所以这两个方法用于获取对象的 space_id 和 type_id.

// 代码 2.3

virtual uint8_t object_space_id()const = 0;
virtual uint8_t object_type_id()const = 0;

这两个方法的实现并不在 generic_index 和 simple_index 中, 而是在 primary_index 中, 实现很简单, 不多说. 注意 primary_index 并没有继承 index, 但是 primary_index 的奇异递归模板参数是 generic_index 或者 simple_index, 这两个类继承了 index, 所以 index 的这两个纯虚方法也得以被实现, 所以代码编译才没有问题. index 中的一些其他方法也是类似道理.

index 中还定义了 get_next_id(), use_next_id() 等几个方法, 并且在 primary_index 中维护着 _next_id 成员, 每当有新对象被创建添加进索引时, _next_id 会相应的改变.

// 代码 2.4

// class index
virtual object_id_type get_next_id()const = 0;
virtual void           use_next_id() = 0;
virtual void           set_next_id( object_id_type id ) = 0;

// class primary_index
object_id_type _next_id;

然后是 insert(), create(), find(), modify(), remove() 方法. insert() 是真正将对象 “插入” 索引数据结构的方法, 任何对象要存入索引, 最终都会经过这个 insert(); 而任何需要存入索引的对象的创建都会经过 create() 方法, create() 会用传进来的构造函数实例对象并调用 insert(), 同时还会负责 _next_id 的自增工作; find(), modify(), remove() 则分别是在索引结构中找, 修改, 以及删除对象. 这几个方法的实现在 generic_index 和 simple_index 中, 他们底层是不同的数据结构, 所以对对象的增删改查实现会有些许差异, generic_index 的结构是 boost::multi_index, 而 simple_index 的结构是 std::vector :P

// 代码 2.5

virtual const object& insert( object&& obj ) = 0;
virtual const object&  create( const std::function<void(object&)>& constructor ) = 0;
virtual const object*      find( object_id_type id )const = 0;
virtual void               modify( const object& obj, const std::function<void(object&)>& ) = 0;
virtual void               remove( const object& obj ) = 0;

再然后是 open(), load(), save(). 这三个方法是处理索引数据的落盘和加载的, 涉及到对象的序列化和反序列化. 顺便还有一个 object_from_variant() 方法, 我们都将在本篇章后续的 “对象的反射与序列化” 一文中详细介绍.

// 代码 2.6

virtual void open( const fc::path& db ) = 0;
virtual const object&  load( const std::vector<char>& data ) = 0;
virtual void save( const fc::path& db ) = 0;

virtual void               object_from_variant( const fc::variant& var, object& obj )const = 0;

剩下的 index 中定义的还有 inspect_all_objects(), hash(), object_default() 不多说了, add_observer() 方法也是一目了然, observer 这块主要 primary_index 代码中体现, primary_index 从 base_primary_index 中继承了一个 _observers 成员, 当索引中的对象发生变化时, 会相应的通知所有 observers.

witness_index 示例

依照惯例, 我们再拿 witness_index 的例子来看一下上层代码是怎么用这些索引类的, witness_index 和上篇文章介绍的 witness_object 一样定义在 <chain>/witness_object.hpp 中,

// 代码 2.7

   using witness_multi_index_type = multi_index_container<
      witness_object,
      indexed_by<
         ordered_unique< tag<by_id>,
            member<object, object_id_type, &object::id>
         >,
         ordered_unique< tag<by_account>,
            member<witness_object, account_id_type, &witness_object::witness_account>
         >,
         ordered_unique< tag<by_vote_id>,
            member<witness_object, vote_id_type, &witness_object::vote_id>
         >
      >
   >;
   using witness_index = generic_index<witness_object, witness_multi_index_type>;

在程序启动数据库初始化过程中, 会调用 initialize_indexes db::object_database::add_index<> 方法添加各种索引到自己的控制下, 其中就包含这一行:

// 代码 2.8

…
add_index< primary_index<witness_index> >();
…

到此可以看到 witness_object 的索引确实就是按照我们上面说的方式定义并被使用的.

后记

到此我们可以看到, graphene 的索引结构的核心就是 generic_index 和 simple_index, 而 genertic_index 的核心就是 multi_index_container<>, simple_index 的核心实际就是 std::vector. 深入了解一下会发现 multi_index_container<> 的底层实际上是 std::map, 而 std::map 底层实际是红黑树.

所以 graphene 的索引模型实质是什么呢? 就是红黑树 + 数组嘛.

稍微对数据库有了解的同学可能会觉得这不科学, 竟然是红黑树和数组, 数据库索引不一般都是 B+ 树吗? 我开始也这么想, 后来看了 db::object_database 这部分源码我想自己大概知道了原因. B+ 的优点在于减少 IO 次数, 而 grapehne 代码启动时是直接将所有索引数据一次性全加载进内存的, 根本用不上 B+ 的这个优点.

好了, 本文到此为止, 敬请期待后续章节: 对象的反射与序列化 以及 对象索引库.