LSM (Log Structured Merge Tree),最早是谷歌的 “BigTable” 提出来的,目标是保证写入性能,同时又能支持较高效率的检索,在很多 NoSQL 中都有使用,Lucene 也是使用 LSM 思想来写入。
普通的B+树增加记录可能需要执行 seek+update 操作,这需要大量磁盘寻道移动磁头。而 LSM 采用记录在文件末尾,顺序写入减少移动磁头/寻道,执行效率高于 B+树。具体 LSM 的原理是什么呢?
为了保持磁盘的IO效率,lucene避免对索引文件的直接修改,所有的索引文件一旦生成,就是只读,不能被改变的。其操作过程如下:
合并的过程:
Basic Compaction
每个文件固定N个数量,超过N,则新建一个sstable;当sstable数大于M,则合并一个大sstable;当大sstable的数量大于M,则合并一个更大的sstable文件,依次类推。
但是,这会出现一个问题,就是大量的文件被创建,在最坏的情况下,所有的文件都要搜索。
Levelled Compaction
像 LevelDB 和 Cassandra解决这个问题的方法是:实现了一个分层的,而不是根据文件大小来执行合并操作。
所以, LSM 是日志和传统的单文件索引(B+ tree,Hash Index)的中立,他提供一个机制来管理更小的独立的索引文件(sstable)。
通过管理一组索引文件而不是单一的索引文件,LSM 将B+树等结构昂贵的随机IO变的更快,而代价就是读操作要处理大量的索引文件(sstable)而不是一个,另外还是一些IO被合并操作消耗。
Lucene的Segment设计思想,与LSM类似但又有些不同,继承了LSM中数据写入的优点,但是在查询上只能提供近实时而非实时查询。
Segment在被flush或commit之前,数据保存在内存中,是不可被搜索的,这也就是为什么Lucene被称为提供近实时而非实时查询的原因。读了它的代码后,发现它并不是不能实现数据写入即可查,只是实现起来比较复杂。原因是Lucene中数据搜索依赖构建的索引(例如倒排依赖Term Dictionary),Lucene中对数据索引的构建会在Segment flush时,而非实时构建,目的是为了构建最高效索引。当然它可引入另外一套索引机制,在数据实时写入时即构建,但这套索引实现会与当前Segment内索引不同,需要引入额外的写入时索引以及另外一套查询机制,有一定复杂度。
数据字典 Term Dictionary,通常要从数据字典找到指定的词的方法是,将所有词排序,用二分查找即可。这种方式的时间复杂度是 Log(N),占用空间大小是 O(N*len(term))。缺点是消耗内存,存在完整的term,当 term 数达到上千万时,占用内存非常大。
lucene从4开始大量使用的数据结构是FST(Finite State Transducer)。FST有两个优点:
那么 FST 数据结构是什么原理呢? 先来看看什么是 FSM (Finite State Machine), 有限状态机,从“起始状态”到“终止状态”,可接受一个字符后,自循环或转移到下一个状态。
而FST呢,就是一种特殊的 FSM,在 Lucene 中用来实现字典查找功能(NLP中还可以做转换功能),FST 可以表示成FST的形式
举例:对“cat”、 “deep”、 “do”、 “dog” 、“dogs” 这5个单词构建FST(注:必须已排序),结构如下:
当存在 value 为对应的 docId 时,如 cat/0 deep/1 do/2 dog/3 dogs/4, FST 结构图如下:
FST 还有一个特点,就是在前缀公用的基础上,还会做一个后缀公用,目标同样是为了压缩存储空间。
其中红色的弧线表 NEXT-optimized,可以通过 画图工具 来测试。
为了能够快速查找docid,lucene采用了SkipList这一数据结构。SkipList有以下几个特征:
在什么位置设置跳表指针?
• 设置较多的指针,较短的步长, 更多的跳跃机会
• 更多的指针比较次数和更多的存储空间
• 设置较少的指针,较少的指针比较次数,但是需要设置较长的步长较少的连续跳跃
如果倒排表的长度是L,那么在每隔一个步长S处均匀放置跳表指针。
也叫 Block KD-tree,根据FST思路,如果查询条件非常多,需要对每个条件根据 FST 查出结果,进行求并集操作。如果是数值类型,那么潜在的 Term 可能非常多,查询销量也会很低,为了支持高效的数值类或者多维度查询,引入 BKD Tree。在一维下就是一棵二叉搜索树,在二维下是如果要查询一个区间,logN的复杂度就可以访问到叶子节点对应的倒排链。
二进制处理,通过BKD-Tree查找到的docID是无序的,所以要么先转成有序的docID数组,或者构造BitSet,然后再与其他结果合并。
IndexSorting是一种预排序,在ES6.0之后才有,与查询时的Sort不同,IndexSorting是一种预排序,即数据预先按照某种方式进行排序,它是Index的一个设置,不可更改。
一个Segment中的每个文档,都会被分配一个docID,docID从0开始,顺序分配。在没有IndexSorting时,docID是按照文档写入的顺序进行分配的,在设置了IndexSorting之后,docID的顺序就与IndexSorting的顺序一致。
举个例子来说,假如文档中有一列为Timestamp,我们在IndexSorting中设置按照Timestamp逆序排序,那么在一个Segment内,docID越小,对应的文档的Timestamp越大,即按照Timestamp从大到小的顺序分配docID。
IndexSorting 之所以可以优化性能,是因为可以提前中断以及提高数据压缩率,但是他并不能满足所有的场景,比如使用非预排序字段排序,还会损耗写入时的性能。
搜索引擎正是靠优秀的理论加极致的优化,做到查询性能上的极致,后续会再结合源码分析压缩算法如何做到极致的性能优化的。