MongoDB的索引代码实现–BtreeBasedAccessMethod

lyhabc

基于B树的访问方法

前言

学习开源软件的最好的办法就是阅读代码，MongoDB整个代码库有接近90万行代码，DB核心层大概50万行，代码量确实非常多。本文作为MongoDB代码导读的第一篇，从Index部分上入手分析代码实现。
为何从索引部分开始介绍，首先代码量较少，总共5000多行，且相对其他模块来说比较独立；其次索引对数据库的优化至关重要，了解其实现，对日后的运维优化和索引自身的限制约定都具有实际意义。毕竟文档上的描述还是没有代码来的准确。本文没有逐行的去分析源码，一来工作量太大，二来也没有办法完全揣测出作者的意图，莫不如只描述大概，剩下的留给阅读者自己思考。

代码导读

代码集中在src/db/index目录下，里面并没有涉及具体的btree数据结构，而是描述了一些操作方法，索引解析等。MongoDB的代码实现上涉及到了比较多的设计模式，比如Builder，Combination，Strategy，Factory等。如图，这部分代码主要采用的是Combination和Adapter模式，整个代码都围绕着BtreeBasedAccessMethod。
MongoDB-src-index

index_descriptor.h[cpp]

构造函数和初始化成员

_magic_code，通过magic检查一定程度上避免内存错误，野指针等造成的数据错乱。
_collection，所属的Collection
_infoObj，配置管理信息
_numFields，索引字段数量，大于一个就是联合索引
_keyPattern，索引匹配串
_parentNS，namespace
_isIdIndex，ID索引，如果索引字段只是_id则认为是IDIndex
_indexName，索引的名字，用户可以指定
_sparse，是否是稀疏索引，稀疏索引不包含NULL字段
_unique，是否是唯一索引
_indexNamespace，索引的namespace，parentNs.$name
_version，数据结构版本号，0和1两个，参看btree_key_generator.h[cpp]
_cachedEntry，看到再说
areIndexOptionsEquivalent

检查是否是稀疏索引，是否是_ID索引，并且是否是唯一索引，注释里也说明了，不关心ID索引的排序顺序，因为升序或者降序，对查询来说，都是等价的，最后比较Options，注意version和ns是不比较的，background是创建时的参数，创建后就不再有意义

index_cursor.h

定义了一些游标接口方法，并声明了Yield逻辑，注释写的很清晰：

/**
* Yielding semantics:
* If the entry that a cursor points at is not deleted during a yield, the cursor will
* point at that entry after a restore.
* An entry inserted during a yield may or may not be returned by an in-progress scan.
* An entry deleted during a yield may or may not be returned by an in-progress scan.
* An entry modified during a yield may or may not be returned by an in-progress scan.
* An entry that is not inserted or deleted during a yield will be returned, and only once.
* If the index returns entries in a given order (Btree), this order will be mantained even
* if the entry corresponding to a saved position is deleted during a yield.
*/
如果游标指向的元素在Yield期间没有被删除，那么在恢复后仍然指向这个位置。在Yield时，插入，删除，或者修改的元素，是否会被游标发现是不确定的。

因为考虑的效率问题，游标可能会Cache一批数据，这部分数据不会与原始的数据同步。同样，Yield时没有加入或者删除的元素，都会被返回，且只返回一次。

元素的返回顺序应该按照指定的顺序返回（升序或者降序），甚至是在Yield期间，指向的元素被删除了也要维持原有的顺序返回。

index_access_method.h[cpp]

操作接口，CRUD方法，注意是非线程安全的。对调用者来说，需要考虑底层的所以结构，接口的行为是不透明的。注释比较简单，不翻译了：

/**
* An IndexAccessMethod is the interface through which all the mutation, lookup, and
* traversal of index entries is done. The class is designed so that the underlying index
* data structure is opaque to the caller.
*
* IndexAccessMethods for existing indices are obtained through the system catalog.
*
* We assume the caller has whatever locks required.  This interface is not thread safe.
*
*/
btree_based_access_method.h[cpp]

继承自IndexAccessMethod，声明getKeys，交给由子类实现，是个Adapter模式。

insert
通过getKeys获得doc的所有key，然后进行迭代修改Index，修改成功后，会对numInserted++，计数，统计本次操作修改索引次数。如果遇到失败情况，则要清理所有之前已经写入的数据，保证操作的原子性，即使失败，也要保证恢复到操作之前的数据状态（索引结构可能会发生变化，但是数据集合是等价的）。 另外，background build index，可能会重复插入索引，因为doc数据可能会在磁盘上移动，也就是会被重复扫描到。

remove
remove比insert就简单多了，因为remove是不可能失败的

find
找到后返回RecordID

update
对比先后两个对象，计算出diff，包括需要删除的和需要增加的，然后批量提交修改。注意，这里可能会失败，但是失败后索引没有再回滚到之前的数据集合。并且是先删除后增加，极端情况下会导致索引错误。思考：如果是先增加后删除，是不是更合适一点？

btree_based_bulk_access_method.h[cpp]

只支持insert的bulk操作，insert的数据先保存在一个外部存储里，最大内存使用10MB大小，commit时再全部读出处理。

btree_key_generator.h[cpp]

该对象封装了一套解析解析算法，目的是解析出obj中的索引key，MongoDB相比较于传统的DB系统，在索引创建上支持Array结构，Array数据内容会根据索引扩展出来。

例如：

索引Pattern：{a: 1, b: 1}
被索引OBJ：{a: [1, 2, 3], b: 2}，
解析出来的IndexKeys：{'': 1, '': 2}{'': 2, '': 2}{'': 3, '': 2}
特别说明的是，只支持并列的一个数组索引，如果是多个数据都想被索引，会失败。因为会造成索引数量的不可控(A*B)。

实际上，MongoDB这里提供了两个版本的算法，V0和V1，2.0以后的MongoDB默认采用了V1，V0与WT存储引擎上还有写兼容性问题，参见：SERVER-16893
所以，MongoDB现在只在mmap上支持V0算法，相关的检验代码：

catalog_index.cpp

if (v == 0 && !getGlobalEnvironment()->getGlobalStorageEngine()->isMmapV1()) {
    return Status( ErrorCodes::CannotCreateIndex,
                  str::stream()
                  << "use of v0 indexes is only allowed with the "
                  << "mmapv1 storage engine");
}
V1和V0的不同点也集中在数组的处理上，V0版本，过于简单，很多数组结构索引解析出来的结果不完整，主要体现在了NULL的处理。
例如：

PATTERN        OBJ        V0        V1
{‘a.b.c’:1}        {a:[1,2,{b:{c:[3,4]}}]}        [{:3 }{:4}]        [{:null}{:3}{:4}]
{‘a’:1,’a.b’:1}        {a:[{b:1}]}        [{:[{b:1} ],:1}]        [{:{b:1},:1}]
{a:1,a:1}        {a:[1,2]}        [{:1,:[ 1,2]}{:2,:[1,2]}]        [{:1,:1}{:2,:2}]
更多的数据测试可以参考btreekeygenerator_test.cpp中的测试case。

虽然官方在ReleaseNote里说明：V1版本的索引更快，更节省空间，但实际上是V0版本算法漏洞太多。参见ReleaseNote 2.0

其他

index目录下还包含了FTS，GEO相关的代码没有说明，FTS部分等阅读到了在说，毕竟使用的场景不多；GEO部分涉及到了一些地理运算，图形学运算，虽然不复杂，后面作为GEO的专题讨论。余下的代码，主要逻辑在BtreeKeyGenerator部分，尤其是V1算法，读者可以再认真学习下。