数据库内核月报 － 2016 / 11

介绍

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)：

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中实现。

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

参考文档

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