MongoDB的索引代码实现–BtreeBasedAccessMethod

前言

学习开源软件的最好的办法就是阅读代码,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算法,读者可以再认真学习下。

 

 

发表评论