如何构建实时全文检索引擎

    这个话题很有意思，以lucene为代表的全文检索引擎大多出于性能的考虑放弃实时特性，由此诞生了Elasticsearch，今年刚刚上市，市值50亿美元，它是一个强大的检索软件系统，但是它并不是实时，新的写入一般会在1秒之后可以检索。当然并不是任何系统都有强烈的实时需求，没有白白的得到也没有白白的失去，牺牲了一定的实时性换来了高吞吐，很多时候仍然是一笔划算的交易。

    “彼之蜜糖,吾之毒药”，也有很多场景我们是强烈要求实时性，比如mysql为代表的数据库系统，那么它们是如何解决实时性问题的呢，这个话题超出了本文的讨论范围，简单的说不同的系统有不同的系统的特点，因此也会有不同的策略，不过核心的逻辑在底层仍然是统一的，就是成本，或者说代价，平衡收益和成本，这笔交易不划算就不会有人买单。说到成本，我总觉得没有人不在乎成本（特别喜欢经济学中对成本的定义，成本就是放弃的最大价值），有些人之所以觉得自己可以不计成本，要么是他没算清楚这笔帐要么就是赌注很大，押宝未来。

    切回主题，那么如何构建实时全文检索引擎呢？这里我们以lucenen为例（lucene相关的文章海了去了，不明白的同学出门左转问问百度）简单说一下它的核心，主要是两点一个以segment的形式分段存储数据，另一个就是使用FST这种数据结构存储term dict。其实在我看来，因为FST所以segment。FST的好处当然是大大的，一个节约空间，另一个就是高效查询，这里稍微解释一下节约空间的事情，一个document经过分词之后建立本地索引，这样占用的空间就会放大，不是放大一点点，举个🌰，笔者曾经把一个1K的文档分词之后总的空间占用达到3K+，放大了2倍。由此可见空间资源应该是一个重要的考虑因素。但是FST有一个弊端就是它对实时修改支持的很不好。这样问题就来了，要实时可见，那么就必须在写入文档的同时构建FST，这就意味这需要生成一个新的segment，大家可以想想这里的问题所在，我就不展开描述了。

    引入另外一个问题，那就是删除，lucene这么架构如何支持删除document的呢？其实听起来也很简单，一个segment维护一个delete文件，segment上的document被删除，并不是修改segment（segment一旦生成就是只读的），而是append的方式记录在segment上，这样read的时候会查询关联的delete文件，过滤掉那些已经删除的document，通过segment的合并异步的完成真正的删除。一个document删除，如果为了实时性直接修改对应的segment上的delete文件是不现实的，segment是只读，这一点很重要，这里涉及到快照隔离的问题，大家可以自行脑补一下。

    到这里，我们的重点来了，那就是我们看到lucene的这套存储架构对于检索实在是非常合适，这是我们不愿意放弃的，因为毕竟很多现实世界的很多场景都是写少读多（不意味着写不重要，相反它很重要很重要很重要），但是我们还想要实时性，因此我在调研了很多材料之后（以下结论并非独创），认为基于类似架构解决实时性，只有实质性的解决delete document（保证可接受的写吞吐基础上）才能说它做到了实时性。

    首先说提升吞吐的问题，显然每次写都直接写磁盘肯定是不行的，类LSM架构是一个不错的选择，也就是新的写暂时缓存在内存中，等到了一定的容量之后再批量写入磁盘以提升写吞吐，那么问题来了，内存中的数据如何也可以实时可见呢？直观的方案就是我在内存里也构建跟磁盘一样的segment，只不过是内存的，那么问题依然存在，还引入了新的问题，首先这种思路仍然没有解决某些场景下频繁delete disk segment document和segment只读之间的矛盾，lucene要让新的修改可见必须reload all segment，这个代价是很大的。新的问题就是当一个memory segment需要flush到磁盘的时候正好有delete document发生在这个segment上，那么改如何处理？这两个问题是最核心的问题，如果说不解决这两个问题，我不相信有人可以做到实时性。

    另外一种思路就是内存不实用FST这种结构存储索引，替换成可以友好支持实时修改的存储结构，看起来也不错，不过问题在于这等于重新构建一套新的检索引擎，总的工程量看看lucene你就知道了，另一个问题就是内存到磁盘的转换也是一个不简单的问题。不过事情的转机也在这里。

    delete的问题的解决之道在于MVCC，只有这样才能在不牺牲吞吐的前提下优雅的完成各种场景下delete document的正确性。我们常见的各种KV存储引擎leveleDB，boltDB，badgerDB，rocksDB都有不错的，它们的底层逻辑是MVCC+LSM，因此在笔者看来这几乎是一个完美的选择，这些KV引擎都是按照key全局有序的，我们就可以利用这些能力构建我们的内存文档检索引擎。我们把所有的索引+docID都按照特定的编码，这样postlist就构建好了。有了底层的postlist，那么上层的检索就好构建了，这里不在展开描述实现细节，国内开源的悟空检索引擎就是类似的思路，大家可以去参考。对于delete document的问题，也就迎刃而解了，每一个内存块满了之后就可以flush到磁盘上，因为MVCC的存在，这个时候新的delete一定是写在新的内存块上，那么快照隔离没有问题，读写不冲突（可以flush的内存块是只读内存块），flush过程不受任何干扰，也实现了类似Elasticsearch的批量flush的特性，写吞吐也达到了可接受的范围，这里需要补充一点，目前从理论上很难做到同等场景下elasticsearch的写吞吐，但是我们场景主要是针对类mysql，对分词的要求不高，很少有全文检索的需求，因此从这个层面上讲吞吐是可以得到保证的，实际测试的效果也是如此。

    今天就分享到这里，总之我认为我们找到了破解问题的钥匙，并且实践证明我们的思路是可行的，后面有时间再专门聊聊我们在开发的过程踩过的坑吧。