基于lucene的内嵌式kv存储

标签: lucene kv | 发表时间:2016-10-24 21:53 | 作者:quentinXXZ
出处:http://www.iteye.com

应用背景

诸多业务场景下,都有使用kv型式存储数据供快速查询的需求。正常的做法有使用HashMap存入内存,或者存入外部的nosql KV数据库/缓存。

  • 使用HashMap做KV存储,速度快,但是如果数据量达到百万及至千万级时,HashMap必将占用大量的java堆内存,给应用带来极大的内存回收压力。
  • 外部kv存储,以堆外(offHeap)存储的方式让我们的应用免于内存回收之忧,但其查询性能往往低于内存map。假设采用外部db的方式作kv存储,就会引入服务之间的通信成本,以基于LR(逻辑回归)实现推荐系统的打分服务为例,每次打分,须执行近求成百上万次kv查询(lr参数的查询),如此的查询量对性能的要求是极高的,如果每一次查询都要查询外部服务,那么网络io势必占用大量的时间。

此外,在工作中会发现很多算法问题,都会被转换为一种追求效率的搜索问题,高效的内嵌式kv存储就会显得更有价值。

需求与方案选择

综上所述,本人想要的KV存储,应当满足如下五点要求:

  • 内嵌的形式,做为内部存储。这样做的好处在于,能够大大减少通讯成本与性能消耗。而且很多时候,我们所需的kv存储并未达到需要做到分布式的数据量级。
  • 采用堆外的方式存储数据。
  • 接近于内存Map的查询速度。
  • 最好具有硬盘执久化的能力,避免每次重启全量构建。
  • 适用于java开发环境。由于我们的各种引擎构建以java为主要开发语言,所以我需要的是一种适用于java的内嵌式kv存储,最好这种存储就是java实现的。
    鉴于上述要求,本文选择lucene的mmap存储方式。如果不考虑第五点需求,鼎鼎大名的leveldb是一个很好的选择。leveldb与lucene都可以视作为lsm-tree实现的存储library。原生的leveldb 是用c++实现的。如果以java方式调用,必然会涉及一定量的改造工作。leveldb也有存java实现的版本,据说性能并不逊于lucene,未敢用过。
    基于上述要求,我采用lucene4.5.1做kv存储(本文是对之前工作的整体,请不要吐槽我的版本太老),以mmap方式加载lucene索引。由于lucene本身是为搜索设计的,其索引结构远比正常的map形式kv索引复杂得多,存在很多的简化与性能优化的空间。下文描述就是基于lucene MMap实现KV索引,并作不同尝试过程。
    以下所有测试采用长度为20的string作为key,int作为value,索引构建条目数为200w。
    测试代码地址: https://github.com/quentinxxz/LuceneKVTest

以HashMap为性能参考

参考代码: HashMapTest
首先,以HashMap存储的方式。
每百万次查询,结果如下:



 
百万次查询平均用时,仅用0.14s,可见HashMap查询的速度相当惊人。

方法1:store存储value,默认压缩

参考代码: LuceneSotreTest.java
value值以lucene store的方式存储。Value field的定义如下:

   protected static class ValueField extends Field {

    /**
     * Type for numeric DocValues.
     */
    public static final FieldType TYPE = new FieldType();

    static {

        // TYPE.setIndexed(true);
        TYPE.setStored(true);
        // TYPE.setDocValueType(DocValuesType.NUMERIC);
        TYPE.setNumericType(NumericType.INT);// 需要支持范围查询,NumbericType会自动建Trie结构
        TYPE.setOmitNorms(true);
        TYPE.setIndexOptions(IndexOptions.DOCS_ONLY);
        TYPE.freeze();
    }

    public ValueField(String name, int value){
        super(name, TYPE);
        fieldsData = value;
    }
}

查询时,并没有直接使用TermQuery进行查询。TermQuery的内部操作较复杂,我们只作KV查询可以使用更底层的接口进行查询。
首先初始化termsEnumList,避免每次查询时又重新初始化,而且注意termsEnumList不能多线程共享,否则会有线程问题:

     IndexReader indexReader = DirectoryReader.open(new MMapDirectory(indexPath));          
  List<TermsEnum> termsEnumList = new ArrayList<TermsEnum>();// 事先初始化termsEnumList,会有多线程问题,当多线程查询时,请用ThreadLocal封装       
  for (AtomicReaderContext context : indexReader.leaves()) {
      termsEnumList.add(context.reader().terms("key").iterator(null));
  }

百万次查询代码如下:

       // mmap方式查询
    IndexSearcher indexSearcher = new IndexSearcher(indexReader);
    for (int i = 0; i < 10; i++) {
        start = System.currentTimeMillis();
        keys.stream().limit(1000000).forEachOrdered(key -> {

            Term term = new Term("key", key);
            for (int l = 0; l < termsEnumList.size(); l++) {
                try {

                    TermsEnum termsEnum = termsEnumList.get(l);
                    // TermsEnum termsEnum = ctx.reader().terms(term.field()).iterator(null);
                    if (termsEnum.seekExact(term.bytes()) == false) continue;
                    DocsEnum docs = termsEnum.docs(null, null);
                    int docId = docs.nextDoc();
                    Document d = indexSearcher.doc(docId);
                    int result = (Integer) d.getField("value").numericValue();
                    // System.out.println(result);
                    return;
                } catch (IOException e) {
                }
            }
            System.out.println("not found");

        });  

百万次查询用的时测试结果如下:




 
在200w条记录的情况下,百万次查询,平均用时3.4s。

方法2:store存储value,去压缩

参考代码: LuceneUnCompressedSotreTest.java
UnCompressedLucene45Codec.java
利用jvisualvm监控方法1查询过程,发现主要的cpu消耗,在于vaule信息读取解压缩的过程。所以接下来的一步优化在于去掉store存储的压缩。具体做法需要自定义lucene的Codec,对UnCompressedLucene45Codec稍作修改:

   public class UnCompressedLucene45Codec extends Codec {

    // private final StoredFieldsFormat fieldsFormat = new Lucene41StoredFieldsFormat();
    private final StoredFieldsFormat fieldsFormat     = new Lucene40StoredFieldsFormat();
    private final TermVectorsFormat  vectorsFormat    = new Lucene42TermVectorsFormat();
    private final FieldInfosFormat   fieldInfosFormat = new Lucene42FieldInfosFormat();
    private final SegmentInfoFormat  infosFormat      = new Lucene40SegmentInfoFormat();
    private final LiveDocsFormat     liveDocsFormat   = new Lucene40LiveDocsFormat();
         ......

将第一个成员fieldFormat由 Lucene41StoredFieldsFormat,换成Lucene40StoredFieldFormat()。要使得自定义的Codec生效还如其步骤,可参考  http://www.romseysoftware.co.uk/2012/07/04/writing-a-new-lucene-codec/
再次进行测试,得到百万次查询用时约1.8s。

方法3:使用DocValues存储vaule

参考代码: LuceneDocValuesTest.java
DocValues存储的结构比store方式存储更为简单,理应效率更高。这里对Value field的定义再作修改,如下:

   protected static class ValueField extends Field {

    /**
     * Type for numeric DocValues.
     */
    public static final FieldType TYPE = new FieldType();

    static {

        TYPE.setIndexed(true);
        TYPE.setStored(false);
        TYPE.setDocValueType(DocValuesType.NUMERIC);
        TYPE.setNumericType(NumericType.INT);
        TYPE.setOmitNorms(true);
        TYPE.setIndexOptions(IndexOptions.DOCS_ONLY);
        TYPE.freeze();
    }

    public ValueField(String name, long value){
        super(name, TYPE);
        fieldsData = value;
    }
}

具体搜索方法请参考代码。
再次测试,得到平均百万次查询用时约为1.5s。

方法4:使用Payload存储vaule

参考代码: LucenePayloadTest.java
IntPayloadTokenizer.java
Payload 是 Lucene 一个允许在索引中为词条储存元数据信息。这边自定义Payload内容是采用重写Tokenizer实现的,具体过程不再赘述,请参考代码。
测试结果为,百万次查询用时约3.6s,较慢。

方法5: lucene FSA存储value

参考代码:
lucene FSA(有限自动机) 或称为FST。它是lucene4开始大量使用的一种索引结构。该算法可以利用索引词的前缀与后缀信息做加压缩,类似Double Array Trie Tree需要查询复杂度为O(n),n为key的字符长度。演示代码是使用lucene FSA的底层api实现。
本人使用时遇到两个明显的问题:

  • 条目添加时必须事先排序,即必须所有key按字典序排好,再作插入操作,索引查询结果不正确。
  • FST的构建本身是发生heap中的,构建结束再一次序列化到磁盘,也就是说如果KV的量很大的话,构建过程会消耗大量的heap空间。
    所以当数据量较大时,直接使用并不是一个很好的选择。为了解决上速问题,可以尝试类似lucene普通索引构建一样,分多个小的segment,在内存上构建一个较小的FST结构再写入磁盘,然可以对多个segment作merge操作。而我在阅读lucene代码BlockTreeTremWriter时,发现,lucene并不是直接使用FST,而是先用FST index+ Block(相同前缀的key分到一个块)分块的方案。
    百万次查询平均用时1.3s。

方法5:Freq存储value信息

最外,还尝试使用Freq存储value信息,由于Freq为int类型,只能存储4个byte,无法存储double类型,所以只做性能测试。具体实现方法较为复杂,不作赘述。 查询时,获取Freq值的方法如下:

               if(termsEnum.seekExact(term.bytes())==false) return null;
            DocsEnum docs = termsEnum.docs(null,null);
            docs.nextDoc();
            return docs.freq()

之前的测试代码找不到后,以后有机会再作补充。了解lucene索存结构的读者,应该能猜到这种方式是最快的。(以前得到的结论,具体多快得补充代码后测试才可知)

总结

本人目前kv存储一般采用DocValues存储,mmap读,即方法3。主要两点考虑,一是为了达到性能上的要求,另一点允许任意长度的value值(代码稍作修改,读者可自行探索)。

 

20161023首发于3dobe.com   http://3dobe.com/archives/247/

本站链接   http://quentinXXZ.iteye.com/blog/2332914

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [lucene kv] 推荐:

基于lucene的内嵌式kv存储

- - 开源软件 - ITeye博客
诸多业务场景下,都有使用kv型式存储数据供快速查询的需求. 正常的做法有使用HashMap存入内存,或者存入外部的nosql KV数据库/缓存. 使用HashMap做KV存储,速度快,但是如果数据量达到百万及至千万级时,HashMap必将占用大量的java堆内存,给应用带来极大的内存回收压力. 外部kv存储,以堆外(offHeap)存储的方式让我们的应用免于内存回收之忧,但其查询性能往往低于内存map.

Nginx+KV db进行AB灰度测试

- - IT技术博客大学习
周6参加华东运维大会,听了人家淘宝用nginx的一些场景,其中AB的灰度测试可能适用场景会比较普遍,当然大会上,并没有详细讨论实现. 大概需求是: 网站类业务在更新new feature时,并不想让全量用户看到,可以针对地区性用户开放此feature. 大概构思了一个方式,使用 nginx+redis/memcache+IP库实现,简单的流程图如下:.

lucene排序

- - 开源软件 - ITeye博客
排序是对于全文检索来言是一个必不可少的功能,在实际运用中,排序功能能在某些时候给我们带来很大的方便,比如在淘宝,京东等一些电商网站我们可能通过排序来快速找到价格最便宜的商品,或者通过排序来找到评论数最高或卖的最好的商品,再比如在Iteye里的博客栏里,每天都会以降序的方式,来显示出最新发出的几篇博客,有了排序,我们就能在某些时候很方便快速的得到某些有效信息,所以说排序功能,无处不在 ^_^.

[原]Lucene系列-facet

- - 文武天下
facet:面、切面、方面. 个人理解就是维度,在满足query的前提下,观察结果在各维度上的分布(一个维度下各子类的数目). 如jd上搜“手机”,得到4009个商品. 其中品牌、网络、价格就是商品的维度(facet),点击某个品牌或者网络,获取更细分的结果. 点击品牌小米,获得小米手机的结果,显示27个.

[原]Lucene系列-FieldCache

- - 文武天下
域缓存,加载所有文档中某个特定域的值到内存,便于随机存取该域值. 当用户需要访问各文档中某个域的值时,IndexSearcher.doc(docId)获得Document的所有域值,但访问速度比较慢,而且只能获得Stored域的值. FieldCache能获得域值数组,根据docId random access域值.

Lucene 使用教程

- - 行业应用 - ITeye博客
1 lucene简介 . 1.1 什么是lucene . Lucene是一个全文搜索框架,而不是应用产品. 因此它并不像 http://www.baidu.com/ 或者google Desktop那么拿来就能用,它只是提供了一种工具让你能实现这些产品. 1.2 lucene能做什么 . 要回答这个问题,先要了解lucene的本质.

Lucene 4.x 之 IndexReader

- - zzm
在Lucene 3.x时代,《Lucene In Action》是一本相当不错的参考书,书中详细介绍了Lucene各种高级使用技术,对于开发者来说非常实用. 但是近期Lucene升级到了4.x版本,在性能等各方面有了很大的提高,值得在新项目中使用. 然而Lucene 4.x中的API相比3.x来说有了很大的改变,《Lucene In Action》中的很多内容都已经过时了,并且由于4.x推出的时间不长,还没有比较好的文档来对用法进行说明,这个系列文章就是想记录下自己使用Lucene 4.x的经验体会,供大家参考使用.

文章: 集成Lucene和HBase

- - InfoQ cn
在所有先进的应用程序中,不管是购物站点还是社交网络乃至风景名胜站点,搜索都扮演着关键的角色. Lucene搜索程序库事实上已经成为实现搜索引擎的标准. 苹果、IBM、Attlassian(Jira)、Wolfram以及很多大家喜欢的公司【1】都使用了这种技术. 因此,大家对任何能够提升Lucene的可伸缩性和性能的实现都很感兴趣.

Solr\Lucene优劣势分析

- - 淘宝网综合业务平台团队博客
最早lucene2.4以及以前,追溯到2008年前后,lucene刚刚引起大家的关注,到后来Nutch. 、solr的出现,lucene变得更加热. Nutch、Solr的发展,极大推动了lucene的升级. 对于一些接触过搜索,使用过lucene、solr的人来说,一般都会感觉lucene、solr很牛逼.