对于Unix目录结构,快速,按行"grep -n"等效

Question

我正在尝试创建一个Web界面来搜索大量的大型配置文件(大约60000个文件,每个文件的大小在20 KB到50 MB之间).这些文件也经常更新(约3次/天).

要求:

• 并发
• 必须标识每个匹配行的行号
• 良好的更新性能

我所研究的内容:

• Lucene:要识别行号,每行必须存储在单独的Lucene文档中,每个文档包含两个字段(行号和行).这使得更新变得困难/缓慢.
• SOLR和Sphinx:两者都基于Lucene,他们有同样的问题,不允许识别行号.
• 带有全文索引的SQL表:再次,无法显示行号.
• SQL表与每行在一个单独的行中:使用SQLite或MySQL进行测试,更新性能是所有选项中最差的.更新50 MB文档花了一个多小时.
• eXist-db:我们将每个文本文件转换为XML,如下所示:<xml><line number="1">test</line>...</xml>.更新需要大约5分钟,这有点奏效,但我们仍然不满意.
• 飞快移动 Python:非常像Lucene.我已经实现了一个原型,通过删除/重新导入给定文件的所有行来进行排序.使用此方法更新50MB文档大约需要2-3分钟.
• GNU id utils:由sarnold推荐,这是非常快的(50MB文档在我的测试机器上不到10秒更新)并且如果它具有分页和API将是完美的.

你会如何实现替代方案？

Answer 1

您可能希望研究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.1演出数据的索引只需要46兆字节 - 这与你的数据相比微不足道,但这个比例感觉还不错.

发现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

因为我的数据集一旦缓存温暖就完全适合RAM,git grep非常惊人:它只比gid(1)实用程序慢七倍,当然它对于交互式使用来说足够快.如果有问题的数据集不能完全缓存(这可能是事情真正变得有趣的地方),那么索引的性能优势是明确无误的.

关于idutils的两个投诉:

1. 没有分页.这绝对是一个缺点,尽管根据我的经验,它运行得足够快,只是将搜索结果存储在其他地方.如果搜索将返回原始数据集的可观百分比,则部分结果的存储肯定会令人讨厌.

2. 没有API:真的,没有API.但是来源可用; src/lid.cfunction report_grep()获取与输出匹配的文件的链接列表.稍微摆弄这个功能甚至应该提供分页.(这需要做一些.)在一天结束时,你会有一个C API,这可能仍然不理想.但定制它看起来并不糟糕.

但是,最糟糕的弱点是缺少增量数据库更新.如果所有文件每天更新​​三次,这不是什么大问题.如果某些文件每天更新​​三次,则会进行不必要的工作.如果少数文件每天更新​​三次,那么必须有更好的解决方案.