介绍
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 这个目录包含了SphinxSE
- src 这个目录就是最主要的源码目录。
- 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 生成excerpt
- sphinxquery.cpp 处理query
- sphinxstemen.cpp sphinxstemru.cpp sphinxstemcz.cpp sphinxstemar.cpp 各种语言的解析器
- sphinxutils.cpp 一些工具函数,比如读写文件,日志,动态库等
- sphinxstd.cpp 库函数,实现了很多基本数据结构,比如 list/vector 等
- sphinxexpr.cpp 处理搜索的query
- sphinxfilter.cpp 处理query的filter
- sphinxsearch.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):
- sph文件 保存了索引的头文件,主要是一些索引元信息
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文件 保存了attribute
- sps文件 单独保存string类型的attribute值
- spd文件 保存了document list
- 所有的document id都保存在这个这个文件中,也就是通过spi文件得到document list的信息后,可以迅速在spd文件中定位document list。
- spe文件 保存了skip list
- spk文件 保存了 kill list
- spm文件 保存了MVA 值
- spp文件 保存了hit list。
- 保存了一个word在document中的所有出现的位置。也就是给定一个document 和一个keywords,这个文件将会返回所有的匹配位置(在当前的document中).
其中spp/spi/spd/spa/spe文件的生成都在RtIndex_t::SaveDiskDataImpl中实现。
在下一篇文章,我们会详细的介绍每个索引文件的生成。