MySQL · 引擎介绍 · Sphinx源码剖析（一）

介绍

Sphinx是一个全文索引引擎，他被设计为可以非常简单方便的与各种数据库(mysql,PG…)进行交互。它提供了两种读取接口，a) sphinx自己实现的mysql协议的接口, SphinxQL。b) 各种语言客户端的接口,也就是native搜索API. c) 也可以直接通过mysql server的一个存储引擎插件来访问, SphinxSE.

接下来我们会有一些列文章来分析Sphinx的设计以及源码实现。

本篇是第一篇，主要是简要的介绍Sphinx的源码结构，设计以及索引文件的构成。我们当前分析的代码版本是sphinx-2.3.2-beta.tar.gz.

源码结构

sphinx的源码结构比较简单，下面主要是一些比较重要的目录:

api 这个目录主要是包含了各种sphinx的native客户端.config 这个目录包含了configure需要的一些文件.cmake 这个目录包含了cmake构建需要的一些模块(当前Sphinx支持两种构建模式).mysqlse 这个目录包含了SphinxSEsrc 这个目录就是最主要的源码目录。src/http search服务的http接口

Sphinx最终会生成4个可执行文件，分别是:

indexer 主要是操作索引文件，比如合并索引，重新构建索引等等indextool dump索引的一些信息，比如统计信息等searchd 搜索服务spelldump 拼写检查的工具

我们先来看Sphinx源码的CmakeFiles（src/CMakeLists.txt) ：

set (LIBSPHINX_SRCS sphinx.cpp sphinxexcerpt.cpp sphinxquery.cpp sphinxsoundex.cpp sphinxmetaphone.cpp sphinxstemen.cpp sphinxstemru.cpp sphinxstemcz.cpp sphinxstemar.cpp sphinxutils.cpp sphinxstd.cpp sphinxsort.cpp sphinxexpr.cpp sphinxfilter.cpp sphinxsearch.cpp sphinxrt.cpp sphinxjson.cpp sphinxaot.cpp sphinxplugin.cpp sphinxudf.c sphinxqcache.cpp sphinxrlp.cpp) set (INDEXER_SRCS indexer.cpp) set (INDEXTOOL_SRCS indextool.cpp) set (SEARCHD_SRCS searchd.cpp searchdha.cpp http/http_parser.c searchdhttp.cpp) set (SPELLDUMP_SRCS spelldump.cpp) ... add_library (libsphinx STATIC ${LIBSPHINX_SRCS} ${HEADERS} ${GHEADERS})

通过上面的构建文件我们可以看到4个可执行文件对应4个源文件(除了搜索服务，searchdha.cpp是分布式搜索，searchdhttp.cpp是搜索服务的http接口实现).剩下的源代码都会被编译为一个libsphinx的库.

因此下面简单介绍下libsphinx的几个文件主要作用:

sphinx.cpp 核心的文件，一些核心功能的实现都在这里，比如读写索引文件，比如搜索的核心方法sphinxexcerpt.cpp 生成excerptsphinxquery.cpp 处理querysphinxstemen.cpp sphinxstemru.cpp sphinxstemcz.cpp sphinxstemar.cpp 各种语言的解析器sphinxutils.cpp 一些工具函数，比如读写文件，日志，动态库等sphinxstd.cpp 库函数，实现了很多基本数据结构，比如 list/vector 等sphinxexpr.cpp 处理搜索的querysphinxfilter.cpp 处理query的filtersphinxsearch.cpp 核心的搜索处理函数sphinxrt.cpp rt index的实现sphinxjson.cpp json的处理

压缩格式

以RT索引为例，sphinx会有配置来决定内存中的索引大小(rt_mem_limit)，超过这个大小后，sphinx将会把内存索引刷新到磁盘中。接下来我们就来看sphinx的索引的含义以及原始格式。

在Sphinx中所有的索引最终都是被压缩的，压缩算法比较简单，要么是delta encoding, 要么是VLB(variable length byte string):

delta encoding 主要用来保存递增的一个序列，每一个元素都保存和前一个元素的差值。这种压缩更高效，结果更小(比起VLB) 比如： source-sequence = 3, 5, 7, 11, 13, 17, ... delta-encoded = 3, 2, 2, 4, 2, 4, ... VLB 将一个固定大小(34/64)的整数值转换为一个字符串，每个字节分为高1位和低七位，最高位表示当前是否解析结束，低7位表示压缩的值，原理很简单，那么就是对于大多数整数来说,不需要完整的8个字节(或者4个字节)来表示一个整数，因为没有那么大。而由于是每次移动7位，那么对于最高位为1的情况也可以处理(因为每次移动完毕的最高位都是无意义的值)。例子: source-value = 0x37 encoded-value = 0x37 source-value = 0x12345 encoded-value = 0x84 0xC6 0x45 // 0x84 == ( ( 0x12345>>14 ) & 0x7F ) | 0x80 // 0xC6 == ( ( 0x12345>>7 ) & 0x7F ) | 0x80 // 0x45 == ( ( 0x12345>>0 ) & 0x7F ) 下面我们来看代码，对应的函数是CSphReader::UnzipInt以及CSphWriter::ZipInt，其中前一个是解压缩，后一个是压缩。 先来看压缩, DWORD可以简单地认为是int64_t,代码比较简单，首先先计算可以用几个字节来保存当前的数(iBytes),然后循环的保存每个字节: void CSphWriter::ZipInt ( DWORD uValue ) { int iBytes = 1; DWORD u = ( uValue>>7 ); while ( u ) { u >>= 7; iBytes++; } while ( iBytes-- ) PutByte ( ( 0x7f & ( uValue >> (7*iBytes) ) ) | ( iBytes ? 0x80 : 0 ) ); }

然后是解压缩，刚好和压缩相反，也就是通过最高位来判断是否结束解压缩，然后通过左移以及累加来不断地计算原有的值。

DWORD CSphReader::UnzipInt () { SPH_VARINT_DECODE ( DWORD, GetByte() ); } #define SPH_VARINT_DECODE(_type,_getexpr) \ register DWORD b = _getexpr; \ register _type res = 0; \ while ( b & 0x80 ) \ { \ res = ( res<<7 ) + ( b & 0x7f ); \ b = _getexpr; \ } \ res = ( res<<7 ) + b; \ return res;

索引文件介绍

在介绍索引文件之前，我们先介绍几个概念：

document 每一条数据也就是一个document。word 这里word表示一个单词，也就是Sphinx分词器处理完一条document之后，所得到的分词。hits 也就是一个word在一条document中的频率。attribute 一些扩展的字段，主要是为了做一些过滤（filter）。

然后来看索引文件的简单介绍.

然后我们来看索引的种类以及格式，在sphinx中，每一个索引都包含了下面几个文件： sph文件 保存了索引的头文件，主要是一些索引元信息 实现在WriteHeader/LoadHeader中。spi文件 保存了wordlist,也就是索引文件中最核心的一个文件。 也就是通过spi文件可以迅速的从一个keywords(word)映射到一堆document list。下面就是spi文件的格式(dict=keywords)： byte dummy = 0x01 keyword[] keyword_blocks keyword is: byte keyword_editcode byte[] keyword_delta if keyword_editcode == 0: assert keyword_delta = { 0 } return block_end zint doclist_offset zint num_docs zint num_hits if num_docs >= DOCLIST_HINT_THRESH: byte doclist_sizehint if ver >= 31 and num_docs > SKIPLIST_BLOCK: zint skiplist_pos zint skiplist_len if min_infix_len > 0: tag "infix-entries" infix_entry[] infix_hash_entries checkpoint[] checkpoints checkpoint is: dword keyword_len byte[] keyword [ keyword_len ] qword dict_offset if min_infix_len > 0: tag "infix-blocks" infix_block[] infix_hash_blocks tag "dict-header" zint num_checkpoints zint checkpoints_offset zint infix_codepoint_bytes zint infix_blocks_offset 文件生成是在cidxHit中。spa文件 保存了attributesps文件 单独保存string类型的attribute值spd文件 保存了document list 所有的document id都保存在这个这个文件中，也就是通过spi文件得到document list的信息后，可以迅速在spd文件中定位document list。spe文件 保存了skip listspk文件 保存了 kill listspm文件 保存了MVA 值spp文件 保存了hit list。 保存了一个word在document中的所有出现的位置。也就是给定一个document 和一个keywords，这个文件将会返回所有的匹配位置(在当前的document中).

其中spp/spi/spd/spa/spe文件的生成都在RtIndex_t::SaveDiskDataImpl中实现。

在下一篇文章，我们会详细的介绍每个索引文件的生成。

参考文档

http://sphinxsearch.com/docs/current.html

相关资源：python入门教程(PDF版)