Unix目录结构的快速逐行“grep -n”等效工具

Question

我正在尝试创建一个网页界面，用来搜索大量的配置文件（大约60000个文件，每个文件的大小在20KB到50MB之间）。这些文件还经常更新（大约每天更新3次）。

需求：

• 支持并发处理
• 必须能够识别每个匹配行的行号
• 更新性能要好

我考虑过的方案：

• Lucene：为了识别行号，每一行都必须存储在一个单独的Lucene文档中，每个文档包含两个字段（行号和内容）。这样更新就变得很麻烦和慢。
• SOLR和Sphinx：这两个也是基于Lucene的，面临同样的问题，无法识别行号。
• 带有全文索引的SQL表：同样无法显示行号。
• 每行一个单独行的SQL表：我在SQLite和MySQL上测试过这个，更新性能是所有选项中最差的。更新一个50MB的文档花了超过一个小时。
• eXist-db：我们把每个文本文件转换成XML格式，像这样：<xml><line number="1">test</line>...</xml>。更新大约需要5分钟，这样勉强能用，但我们还是不太满意。
• Python的Whoosh：基本上和Lucene差不多。我实现了一个原型，通过删除和重新导入给定文件的所有行来工作。用这种方法更新一个50MB的文档大约需要2-3分钟。
• GNU id utils：这是sarnold推荐的，速度非常快（在我的测试机器上更新一个50MB的文档不到10秒），如果有分页和API就完美了。

你会如何实现一个替代方案？

Answer 1

如果有人需要，我创建了一个叫做Whooshstore的工具，它其实是一个基于Whoosh的、纯Python写的GNU id工具的克隆版，提供增量更新、分页功能和Python接口。

命令行客户端的使用方法如下：

ws-update -b --index my.idx datadir  # build the index
ws-update -b --append --index my.idx datadir  # incremental update
ws --index my.idx hello world     # query the index

(-b是用于批量更新的选项，这样更新速度更快，但需要更多的内存。如果想了解完整的命令行语法，可以使用--help。)

虽然它的速度比GNU id工具慢很多，但通过使用几次增量批量（在内存中）更新来更新索引，对于我们来说已经足够快了。

Answer 2

你可能想了解一下GNU idutils这个工具包。在本地的Linux内核源代码上，它可以输出如下内容：

$ gid ugly
include/linux/hil_mlc.h:66:  * a positive return value causes the "ugly" branch to be taken.
include/linux/hil_mlc.h:101:    int         ugly;   /* Node to jump to on timeout       */

从冷缓存重建索引的速度还算快：

$ time mkid

real    1m33.022s
user    0m17.360s
sys     0m2.730s

从热缓存重建索引则快得多：

$ time mkid

real    0m15.692s
user    0m15.070s
sys     0m0.520s

对于我2.1GB的数据，索引只占用了46MB的空间——虽然和你的数据相比算小，但这个比例感觉还不错。

找到399个foo的出现次数只花了0.039秒：

$ time gid foo > /dev/null

real    0m0.038s
user    0m0.030s
sys     0m0.000s

更新

Larsmans对在内核源代码上使用git grep的性能很感兴趣——这也是一个很好的方式来展示gid(1)带来的性能提升。

在冷缓存的情况下，git grep foo（返回了1656条记录，远远超过idutils的结果）：

$ time git grep foo > /dev/null

real    0m19.231s
user    0m1.480s
sys     0m0.680s

一旦缓存变热，git grep foo的运行速度就快多了：

$ time git grep foo > /dev/null

real    0m0.264s
user    0m1.320s
sys     0m0.330s

因为我的数据集在缓存热的时候完全可以放进内存，所以git grep的表现相当不错：它的速度仅比gid(1)慢七倍，绝对足够用于交互式使用。如果数据集无法完全缓存（这可能才是有趣的地方），那么索引带来的性能优势就显而易见了。

关于idutils的两个抱怨：

1. 没有分页。这确实是个缺点，不过根据我的经验，它运行得足够快，可以把搜索结果存储到其他地方。如果搜索结果占原始数据集的比例比较大，那么存储部分结果就会很麻烦。

2. 没有API：确实没有API。但源代码是可以获取的；src/lid.c中的report_grep()函数接受一个匹配输出的文件链表。稍微调整一下这个函数，甚至可以实现分页功能。（这需要一些工作。）最终，你会得到一个C语言的API，虽然可能不够理想，但定制起来看起来也不算太糟。

不过，最糟糕的弱点可能是缺乏增量数据库更新。如果所有文件每天更新三次，这没什么大不了。如果某些文件每天更新三次，那就会做一些不必要的工作。如果只有少数文件每天更新三次，那肯定有更好的解决方案。