介绍

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

  1. set (LIBSPHINX_SRCS sphinx.cpp sphinxexcerpt.cpp
  2.         sphinxquery.cpp sphinxsoundex.cpp sphinxmetaphone.cpp
  3.         sphinxstemen.cpp sphinxstemru.cpp sphinxstemcz.cpp
  4.         sphinxstemar.cpp sphinxutils.cpp sphinxstd.cpp
  5.         sphinxsort.cpp sphinxexpr.cpp sphinxfilter.cpp
  6.         sphinxsearch.cpp sphinxrt.cpp sphinxjson.cpp
  7.         sphinxaot.cpp sphinxplugin.cpp sphinxudf.c
  8.         sphinxqcache.cpp sphinxrlp.cpp)
  9. set (INDEXER_SRCS indexer.cpp)
  10. set (INDEXTOOL_SRCS indextool.cpp)
  11. set (SEARCHD_SRCS searchd.cpp searchdha.cpp http/http_parser.c searchdhttp.cpp)
  12. set (SPELLDUMP_SRCS spelldump.cpp)
  13. ...
  14. 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) 比如：
  1.     source-sequence = 3, 5, 7, 11, 13, 17, ...
  2.     delta-encoded = 3, 2, 2, 4, 2, 4, ...
  • VLB
    • 将一个固定大小(34/64)的整数值转换为一个字符串，每个字节分为高1位和低七位，最高位表示当前是否解析结束，低7位表示压缩的值，原理很简单，那么就是对于大多数整数来说,不需要完整的8个字节(或者4个字节)来表示一个整数，因为没有那么大。而由于是每次移动7位，那么对于最高位为1的情况也可以处理(因为每次移动完毕的最高位都是无意义的值)。
    • 例子:
  1.     source-value = 0x37
  2.     encoded-value = 0x37
  4.     source-value = 0x12345
  5.     encoded-value = 0x84 0xC6 0x45
  6.         // 0x84 == ( ( 0x12345>>14 ) & 0x7F ) | 0x80
  7.         // 0xC6 == ( ( 0x12345>>7 ) & 0x7F ) | 0x80
  8.         // 0x45 == ( ( 0x12345>>0 ) & 0x7F )
  • 下面我们来看代码，对应的函数是CSphReader::UnzipInt以及CSphWriter::ZipInt，其中前一个是解压缩，后一个是压缩。 先来看压缩, DWORD可以简单地认为是int64_t,代码比较简单，首先先计算可以用几个字节来保存当前的数(iBytes),然后循环的保存每个字节:
  1. void CSphWriter::ZipInt ( DWORD uValue )
  2. {
  3.     int iBytes = 1;
  5.     DWORD u = ( uValue>>7 );
  6.     while ( u )
  7.     {
  8.         u >>= 7;
  9.         iBytes++;
  10.     }
  12.     while ( iBytes-- )
  13.         PutByte (
  14.             ( 0x7f & ( uValue >> (7*iBytes) ) )
  15.             | ( iBytes ? 0x80 : 0 ) );
  16. }

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

  1. DWORD CSphReader::UnzipInt ()            { SPH_VARINT_DECODE ( DWORD, GetByte() ); }
  3. #define SPH_VARINT_DECODE(_type,_getexpr) \
  4.     register DWORD b = _getexpr; \
  5.     register _type res = 0; \
  6.     while ( b & 0x80 ) \
  7.     { \
  8.         res = ( res<<7 ) + ( b & 0x7f ); \
  9.         b = _getexpr; \
  10.     } \
  11.     res = ( res<<7 ) + b; \
  12.     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)：
  1. byte dummy = 0x01
  2. keyword[] keyword_blocks
  3. keyword is:
  4.     byte keyword_editcode
  5.     byte[] keyword_delta
  6.     if keyword_editcode == 0:
  7.         assert keyword_delta = { 0 }
  8.         return block_end
  9.     zint doclist_offset
  10.     zint num_docs
  11.     zint num_hits
  12.     if num_docs >= DOCLIST_HINT_THRESH:
  13.         byte doclist_sizehint
  14.     if ver >= 31 and num_docs > SKIPLIST_BLOCK:
  15.         zint skiplist_pos
  16.         zint skiplist_len
  18. if min_infix_len > 0:
  19.     tag "infix-entries"
  20.     infix_entry[] infix_hash_entries
  22. checkpoint[] checkpoints
  23. checkpoint is:
  24.     dword keyword_len
  25.     byte[] keyword [ keyword_len ]
  26.     qword dict_offset
  28. if min_infix_len > 0:
  29.     tag "infix-blocks"
  30.     infix_block[] infix_hash_blocks
  32. tag "dict-header"
  33. zint num_checkpoints
  34. zint checkpoints_offset
  35. zint infix_codepoint_bytes
  36. 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