Lucene数据存储实现：行存&列存

lucene数据存储格式

Lucene作为最强大的开源的全文检索引擎，其倒排索引机制可以快速的根据term值找到docid，此外lucene也可以保存明细数据，通过docid将明细数据返回，并且有两种方式-行存、列存。

一、一次查询的流程

 

                                                             

上图是lucene一次查询的流程，首先是从倒排索引中获取docid，之后再从行存或者列存中找到数据。只有建立索引的字段才会生成term和term对应的docid列表。当然，如果字段需要分词，就对分词器的切分后的每个分词单元建立term和对应的doclist。否则整个字段作为一个term，并建立doclist。从图中也可以看到两个关系：

1）索引与数据是独立存储的，两者之间是通过docid关联。

2）行存和列存是独立存储的，他们只和docid关联，彼此无关联。

二、数据存储文件结构

 

                                                                                 

上图是lucene中的文件结构，其中fdx、fdt是行存数据文件，dvm、dvd是列存数据文件。

三、重编码

在数据存储系统中，对磁盘的占用是很敏感，因为相同的数据信息占用磁盘越多，意味着硬件成本越高，读取相同数据信息的io资源随之升高。如果按照已有的数据格式（比如java中的int、long）存储数据将会造成很大的数据浪费，可以见下图：

                          

上图中long和int二进制表示中红色高位是不起作用的，也就是被“浪费”了。因为long和int的序列化方式是不可控的，只要在int范围的数据就会占用四个字节。Lucene对此解决方案是-重编码。重编码在lucene文件存储中被广泛用于数值类型数据的压缩，可以极大的减少空间的浪费，通过将byte（字节）重组，以bit（位）为单位，尽可能的利用每一个bit（位）。下面是一个重编码的例子：

int[] ints = {3,16,7,12}

二进制表示：

{0000 0011,0001 0000,0000 0111,0000 1100 }

选择其中有效位最大那个作为定长，也就是16->1 0000，下面就是重编码之后的结果

四、行存存储

行存存储本质是通过docid获取整行数据，适用于多列数据展示，数据文件对应fdx,fdt，其中fdt存储数据，fdx是fdt文件的索引。

 

                                                     

fdx、fdt两个文件的组织结构是类似树形结构，保证可以根据docid快速获取整行数据。

 

                                             

这个图中每个block对应1024个chunk，每个chunk对应128个doc，这样可以快速根据block定位到属于哪个chunk，再根据每个chun到具体的doc的位置。其中block是fdx中的概念，chunk是fdt中的概念。

1）fdx文件结构

 

                                                  

除去不重要的文件头和尾信息之外，存储的是每个block的信息，每个block的信息有

1.  Chunk个数
2. 起始docid
3. 平均个数
4. 存储每个chunk个数占用的字节数
5. 存储每个chunk的个数
6. 起始fdt文件偏移量
7. 平均chunk大小
8. 存储每个chunk对应fdt地址占用的字节数
9. 存储每个chunk对应的fdt地址

其中查询的流程是根据每个block的起始docid快速定位到给定的docid是属于哪个block，接着根据chunk个数数组定位到属于哪个chunk，找到对应的数组下标，然后从chunk地址数组中找到该chunk对应的fdt文件地址。其中在存储chunk包含doc个数和chunk对应fdt文件地址的时候使用“存储真实值和平均值的差值来代替存储真实值”的方法，可以起到压缩数据的作用，下面是一个采用该方法的例子：

[10000,9888,10002,99997,10003] => [0,-2,2,-3,3]

转换之后的存储个数明显变少，接着在对转换之后的数组使用重编码的方法继续压缩。由于fdx并不存储真是数据，只是一些索引信息，所以一般是需要常驻内存的，用于加快数据的搜索。

2） fdt文件结构

 

                                                           

Fdt文件就简单不少了，主要存储的是一个多个chunk块的信息：

1. 起始docid
2. 当前chunk包含的doc个数
3. 每个doc包含的字段的个数
4. 每个doc的长度
5. 具体的每行数据，每行数据又包括每个列的列编号、列长度、列值。

可以发现numStoredFields和lengths都是数值型数组，所以这两个部分的数据存储都采用了重编码的机制。数据量真正大的地方是存储每行数据，由于是行村，每个列的树交叉存储，所以版很难做存储结构上的优化，此处使用的全局压缩算法，lucene提供了三种压缩算法：

1.  DeflateCompressor
2. LZ4FastCompressor
3. LZ4HighCompressor

每种压缩算法的性能和耗时不同，下面是做了简单测试：

                                                

                                                

 

压缩比分别是DeflateCompressor > LZ4HighCompressor> LZ4FastCompressor，但是对应的压缩时间就是相反的。压缩比高就要更多的时间去压缩。Lucene默认采用了LZ4HighCompressor压缩算法，兼顾性能和耗时。

Fdt文件一般都是比较大的，不会常驻内存，只有在需要的时候才会加载到内存中。

五、列存存储

列存存储本质是通过docid获取一例数据，减少需要加载的数据量，列存使用场景：排序、facet、地理位置查询等，对应的数据文件dvm , dvd。其中dvd存储列存数据，dvm是dvd文件的索引。

 

                                                               

1） dvd/dvm文件结构

 

                                                

由于是列存存储所以每个列的数据是连续存储的，每个字段的元数据也是连续存储的，这样有利于数据的加载，其中dvm文件存储的内容主要有：

1. 列编号
2. 列的数据类型
3. 索引格式
4. 空值信息
5. 当前列对应的dvd文件的地址
6. 文档的数量
7. 索引数据

由于每个列的数据是存储在一起的，所以这里可以有不同的数据存储格式，lucene提供了种四种：

i. CONST_COMPRESSED
只有一个常量值和空值的情况下采用这种格式。这种格式很简单，直接把该常量值写入 dvm中，解压时，直接读取 dvm中的常量即可。

ii. TABLE_COMPRESSED
当不满足i且唯一值小于等于 256 个，采用这种格式，把这些唯一值放到一个数组中，排好序，然后把唯一值写到 meta 中，把每个文档的值在数组中的下标重编码之后写到 dvd文件 中即可。

iii. GCD_COMPRESSED
当不满足上述两个，且最大公约数不是0&1时，采用这种结构，最大公约数压缩格式：(value - minValue) / gcd，重编码之后存储在dvd文件中。

 

                                               

iiii.GCD_COMPRESSED
把最小值写到 meta 中，用值减去最小值，得到差值，写到 data 中。比较适用所有值差别不大的情况。

lsql是我们做的基于lucene的分布式搜索引擎，架构为分布式索引+大数据，将大数据组件融合进分布式搜索中，如果你有兴趣了解产品，可以登录官网，如果你想加入一起搞分布式搜索，请给我发简历，我们是一家技术驱动的公司~

官网：www.lucene.xin

邮箱：[email protected]