Lucene 是由 Doug Cutting 大神开发的，这哥们同时还创立了 Nutch 和 Hadoop，他和 QEMU、FFmpeg、tinycc、QuickJS 的发明者 Fabrice Bellard 一样多产且开发的东西都十分牛逼。

Lucene 是一个 Java 开发的搜索引擎，其全文检索基于 Inverted Index 实现。此文章所使用的代码都可以在 RitterHou/test_lucene 中找到。

基础使用

首先我们对数据进行索引操作，这里我们选择了把数据存储在 RAM 中，但是要知道 Lucene 也支持把数据存储在磁盘上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private void index () {
    Directory directory = new RAMDirectory();
    Analyzer analyzer = new IKAnalyzer();
    IndexWriterConfig config = new IndexWriterConfig(analyzer);
    IndexWriter indexWriter = new IndexWriter(directory, config);

    addDoc(indexWriter, "游戏编程算法与技巧", "9787121276453");
    addDoc(indexWriter, "计算机程序的构造和解释(原书第2版) : 原书第2版", "9787111135104");
    addDoc(indexWriter, "编码 : 隐匿在计算机软硬件背后的语言", "9787121106101");
    addDoc(indexWriter, "计算机网络（第5版）", "9787302274629");
    addDoc(indexWriter, "Python网络编程攻略", "9787115372697");
    addDoc(indexWriter, "UNIX网络编程", "9787302119746");
    addDoc(indexWriter, "算法导论（原书第3版）", "9787111407010");

    indexWriter.close();
}

private void addDoc(IndexWriter w, String title, String isbn) {
    Document doc = new Document();
    // TextField表示使用配置中分词器对字符串进行分词
    doc.add(new TextField("title", title, Field.Store.YES));
    // StringField则保存原始字符串而不进行分词
    doc.add(new StringField("isbn", isbn, Field.Store.YES));
    w.addDocument(doc);
}

上面的代码包含了

  • 创建内存 Dir
  • 创建 IKAnalyzer 分词器，这是一个中文分词器；把该分词器放到 config 对象中
  • 创建 IndexWriter 对象
  • 将数据创建为一条条的 Document（文档）并进行存储

上一步操作中数据已经被保存成功，下面进行数据检索的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Directory directory = new RAMDirectory();
Query q = new QueryParser("title", new IKAnalyzer()).parse(input);

int hitsPerPage = 10;
IndexReader reader = DirectoryReader.open(directory);
IndexSearcher searcher = new IndexSearcher(reader);
TopDocs docs = searcher.search(q, hitsPerPage);
ScoreDoc[] hits = docs.scoreDocs;

System.out.println("Found " + hits.length + " hits.");
for (int i = 0; i < hits.length; ++i) {
    int docId = hits[i].doc;
    Document d = searcher.doc(docId);
    System.out.println((i + 1) + ". " + d.get("isbn") + "\t" + d.get("title"));
}
  • 和 IndexWriter 使用同一个 Dir
  • 创建查询语句，我们这里是根据title字段查询，因为这是一个 TextField 所以用于查询的字符串也需要先使用 IKAnalyzer 进行分词
  • 根据查询语句查询出hits
  • 根据hits中的docId取回数据

基础查询的完整代码位于 SimpleTest.java

NRT 查询

我们知道 Lucene 存储引擎使用的是 LSM Tree 形式，关于 LSM Tree 可以参考我之前的文章 Log structured merge tree，简而言之 Lucene 会把数据写到一个个的段（Segment）中。所谓 NRT 查询即 Near Real Time 查询，这意味着我们写到 Lucene 的数据是不能够被立即查询到的，原因如下

Segment 在被 flush 或 commit 之前，数据保存在内存中，是不可被搜索的，这也就是为什么 Lucene 被称为提供近实时而非实时查询的原因。读了它的代码后，发现它并不是不能实现数据写入即可查，只是实现起来比较复杂。原因是 Lucene 中数据搜索依赖构建的索引（例如倒排依赖 Term Dictionary），Lucene 中对数据索引的构建会在 Segment flush 时，而非实时构建，目的是为了构建最高效索引。当然它可引入另外一套索引机制，在数据实时写入时即构建，但这套索引实现会与当前 Segment 内索引不同，需要引入额外的写入时索引以及另外一套查询机制，有一定复杂度。 —— Lucene 解析 - 基本概念

上面解释了 Lucene 不能实现实时查询的原因，下面我们看一看如何能实现 NRT 查询

首先还是创建配置等这一套代码

1
2
3
4
Analyzer analyzer = new IKAnalyzer();
RAMDirectory index = new RAMDirectory();
IndexWriterConfig config = new IndexWriterConfig(analyzer);
final IndexWriter indexWriter = new IndexWriter(index, config);

随后是 NRT 的配置以及开启 NRT 的定时刷新线程

1
2
3
4
5
6
7
8
9
10
// NRT查询的相关配置
TrackingIndexWriter trackingIndexWriter = new TrackingIndexWriter(indexWriter);
final ReferenceManager<IndexSearcher> searcherManager = new SearcherManager(indexWriter, true, null);

// NRT查询的定时刷新线程
ControlledRealTimeReopenThread<IndexSearcher> nrtReopenThread = new ControlledRealTimeReopenThread<>(trackingIndexWriter, searcherManager, 1.0, 0.1);
nrtReopenThread.setName("NRT Reopen Thread");
nrtReopenThread.setPriority(Math.min(Thread.currentThread().getPriority() + 2, Thread.MAX_PRIORITY));
nrtReopenThread.setDaemon(true);
nrtReopenThread.start();

其中最重要的就是ControlledRealTimeReopenThread类的1.0和0.1这两个参数

  • targetMaxStaleSec: reader 的最大 open 间隔
  • targetMinStaleSec: reader 的最小可 open 间隔

有了以上这些设置，我们就能实现不重新打开 reader 也可以读到最新的数据了，当然读取的数据对应写入的数据并不是实时的。

完整代码位于 NRTTest.java

相关度打分

一般的数据库的查询中，某一条数据针对指定查询条件只存在符合要求或者不符合要求这两种情况；而搜索引擎则还需要提供某条数据与查询条件有多大程度相似的这种情况，这种比较相似度的需求就是通过相似度打分的计算来实现的。在搜索引擎进行查询的同时也会计算指定文档与查询条件的相似度得分，得分高的一般来说就需要优先展示。

Lucene 内部包含了多种相似度算法，其中最经典的就是 TF/IDF 算法，Lucene 的 TF/IDF 计算实现位于 org.apache.lucene.search.similarities.TFIDFSimilarity 类中。除了 TF 和 IDF，Lucene 在该类中计算得分时还会使用到一些其它的参数

计算因子介绍
coord指定文档中命中的查询关键词个数 ÷ 所有的查询关键词个数
TFterm 在指定文档中出现的次数，次数越多得分越高
IDFterm 在全部文档中出现的次数，次数越多得分越低
boost一个影响因子，供用户在查询时修改以影响最终得分
queryNorm常数
norms文档的长度，长度越短权重越高

coord 实现

1
2
3
4
5
/** Implemented as <code>overlap / maxOverlap</code>. */
@Override
public float coord(int overlap, int maxOverlap) {
    return overlap / (float)maxOverlap;
}

TF 的实现

1
2
3
4
5
/** Implemented as <code>sqrt(freq)</code>. */
@Override
public float tf(float freq) {
    return (float)Math.sqrt(freq);
}

IDF 的实现

1
2
3
4
5
/** Implemented as <code>log(numDocs/(docFreq+1)) + 1</code>. */
@Override
public float idf(long docFreq, long numDocs) {
    return (float)(Math.log(numDocs/(double)(docFreq+1)) + 1.0);
}

计算最终得分的公式如下（公式来自 Lucene 官方文档）

提升搜索速度

我们知道 Lucene 使用反向索引存储数据，例如针对如下数据

id标题isbn
1游戏编程算法与技巧9787121276453
2计算机程序的构造和解释 (原书第 2 版) : 原书第 2 版9787111135104
3编码 : 隐匿在计算机软硬件背后的语言9787121106101
4计算机网络（第 5 版）9787302274629
5Python 网络编程攻略9787115372697
6UNIX 网络编程9787302119746
7算法导论（原书第 3 版）9787111407010

针对上面的数据我们可以构建的部分反向索引结构如下

标题的反向索引：

关键词doc_ids
算法[1, 7]
编程[1, 5, 6]
计算机[2, 3, 4]

isbn 的反向索引：

关键词doc_ids
97871211061013
97871153726975

根据上表我们知道 Lucene 需要构造一个 关键词 -> doc_id 之前的关系映射，如果让我自己实现一个映射关系那我很可能会选择使用哈希表，即关键词使用哈希表的方式进行查找。Lucene 选择了使用一个类似于 trie 树叫做 FST(Finite State Transducer) 的数据结构来保存关键词，虽然 FST 在写入和查找速度上都不及哈希表，但是它在前缀查找等方式上却有着巨大的优势，此外 FST 十分的节省空间，这使得我们可以把 FST 全部放在内存中以提高数据操作速度。关于 FST 可以参考 这篇文章。

Lucene 的数据存储架构如下

上面我们介绍的 FST 其实是 Term dict index 这一部分，通过 Term dict index 我们可以找到 Term dict 中的相应 term，例如上面我们提到的 计算机 或者 9787121106101 等等。找到了相应的 term 之后我们可以继续根据 term 找到相应的 Inverted Index，Inverted Index 使用 SkipList 保存，SkipList 可以让多个 term 的查询结果合并速度更快。顺便提一下，Elasticsearch 会对 filter 类型的查询结果使用 bitset 进行缓存，如果下次查询缓存命中则可以直接通过 bitset 的缓存进行结果合并，速度更快。

生成正向索引

我们上面提到的都是数据检索阶段的工作，也看到了 Inverted Index 在数据检索上十分优秀，但是当我们已经取回了数据需要对数据做进一步的排序或聚合时，反向索引就显得力不从心了。Lucene 需要把取回的数据通过计算再生成一份正向索引，之后使用正向索引实现排序或聚合等操作，生成正向索引十分耗费资源，因此 Lucene4 之后对这些生成的正向索引做了缓存即 fieldcache，这样这些正向索引的结果就会被缓存在内存中，fieldcache 的命中可以大大提高数据排序或聚合的速度。

fieldcache 对内存是一个很大的挑战，如果缓存数据过多会导致内存占用过高。新版的 Lucene 中引入了 DocValues 概念，Lucene 会在数据索引阶段就生成一份列式存储的正向索引，即 DocValues。DocValues 因为是在索引阶段生成的，又被保存在磁盘上，所以避免了 fieldcache 会产生的一些问题。当然，DocValues 会增加磁盘空间的使用，所以 Lucene 允许我们只针对某些需要排序或聚合的字段使用 DocValues，这样就节省了部分的磁盘空间。

参考

Welcome to Lucene Tutorial.com - Lucene Tutorial.com
Lucene 近实时搜索 | IT 草根
Lucene 解析 - 基本概念
Lucene 原理与代码分析 - 随笔分类
lucene 的评分机制
Lucene 查询原理及解析

Lucene 中的文本相似度算法
Okapi BM25, TF-IDF, 以及 ElasticSearch/Lucene 搜索结果的分数
elasticsearch-full
Lucene 查询原理
ElasticSearch 查询的秘密
Elasticsearch Modules