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

in #bitshares7 years ago (edited)

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

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

索引模型

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

indexobject 一样是个抽象类, 定义的是关于索引的基本操作方法并且成员基本都是纯虚成员, 所以 index 也不能被直接实例化, 需要被继承并被实例化其子类, generic_indexsimple_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_indexprimary_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_indexsimple_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_indexsimple_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_indexsimple_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_indexbase_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_indexsimple_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+ 的这个优点.

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

Sort:  

不明觉厉

O 哥文章才是真的厉害~

我那是“大海啊,全是水~~”

O 哥真是我在 steemit 上碰到最谦虚的大佬 :D

Congratulations @cifer, this post is the seventh most rewarded post (based on pending payouts) in the last 12 hours written by a User account holder (accounts that hold between 0.1 and 1.0 Mega Vests). The total number of posts by User account holders during this period was 2924 and the total pending payments to posts in this category was $5126.37. To see the full list of highest paid posts across all accounts categories, click here.

If you do not wish to receive these messages in future, please reply stop to this comment.

喜欢技术文章,看不懂,总多少知道点皮毛,谢谢

感谢您的喜欢~

真人不露相

露相不真人, 现在露相了 :D

正好公司最近也在做相关项目,学习一下

厉害的公司~

不明觉历

哪里哪里, 码农读读代码而已

genertic_index是index的子类,但是并没有实现get_next_id(), use_next_id()这几个纯虚函数,编译却没有问题,这是什么回事?

不会通过generic_index直接生成对象,index对象都是通过primary_index生成的,而primary_index则是继承generic_index或者simple_index。看起来有点绕,@cifer在文章中说明了

抱歉没注意到文章多了评论, 原因就是 @chaimyu 说的, 感谢~

高手,学习...

期待出共识篇~