everything 索引原理探讨

[hkhk366]

everything 索引原理探讨

MFT 如何获取硬盘所有文件信息和监控整个硬盘文件变动，这两个比较简单，我做了一个简单实现可以在 200 毫秒扫描整个硬盘所有分区下所有文件信息，总共 100 万个对象的信息，这个第一步比较简单。

主要是第二步，如何高效的为文件增加索引？ everything 如何在 5 毫秒内完成 100 万文件的全文搜索并排序的？我利用 everything 开启 HTTP 服务，发送请求计算出来总共需要 5 毫秒就能完成这个搜索。这对我来说太难，我想了很久也没有想明白是如何做的。

思路 1：使用全文搜索，建立倒排索引，因为文件名经常出现比如“abc.txt“”这样的，所以很难分词，如果按每个字母建立倒排索引的话，100 万文件大约需要 1 个 GB 的空间，因为太多的文件有"a"这种字符，所以这个方案不行。

我看到论坛里有个开源的项目实现的，我粗略的看了一下，他套了一个全文搜索引擎，但是如果搜"a"这种字符，首先结果出来不全，可能只截取了一部分，但是 everything 可以搜索完立刻就知道总共有多少条符合的，而且搜索出来就已经排序了，比如按文件大小排序，我想不明白 5 毫秒内如何做到的。

思路 2：并行计算，我把 100 万文件并行去计算，我的极限可以把 100 万文件全文搜索控制在 6 毫秒，而且还没排序，但是我 7900x 的 24 核心芯片的每一个核心都参与了计算，而我在 everything 搜索的时候，我发现其 CPU 基本不怎么波动，没有出现大量核参与运算的样子，他是如何做的？

思路 3：使用 simd ，看着也不像，我感觉 everything 搜索的时候 CPU 波动非常的小。

思路 4：前缀树后缀树，这个只能搜索某个字符串开头的，没法实现全文搜索。

思路 5：我研究了一些多模态匹配字符串搜索算法，但是无论我怎么优化，都无法实现 5 毫秒这么快的速度。

思路 6：我研究了各种排序算法，我个人认为比如搜索“a”在我机器上有几十万个文件，无论用什么有我知道的算法，极限并行排序 100 万文件需要 10 毫秒左右，所以我才猜测 everything 不像是结果直接全部排序完成才返回的，更像是只获取前 100 个，然后后面慢慢排序，在你拖动滚动条的时候再把结果放出来。

思路 7：B+树，这个可能对排序建立索引有点用，但是全文搜索没什么帮助。

思路 8：索引建立速度，根据我录屏然后慢速分析，我发现，everything 1.4 扫描所有文件信息到建立索引，在我的机器上 1 秒以内就能完成，这是如何做的，我尝试了很久，如果算法太复杂就会消耗太多时间，显然 everything 的算法应该非常轻量高效。

希望高人能指点一下上面的谜题，让我能了解一下这个原理，非常感谢。

[hkhk366]

@matrix1010 感谢回复，但是用 sqlite 即使关闭各种配置以增加吞吐量也是无法在 1 秒内实现 100 万数据的插入，包括文件名，文件路径，文件大小，修改时间，访问时间，创建时间。我已经说了，文件名不能用普通分词，我是按照每个字母当分词，我自己实现了倒排索引一个版本，再用 sqlite 都不行，sqlite 比我自己实现的还慢。论坛上有其他人套壳全文搜索引擎，最后同样的文件 everything 120MB 以内，全文搜索引擎内存超过 250MB ，而且结果没按照文件大小排序，这些我都在 1 楼帖子说明过。

[iseki]

我记得在这个软件的论坛上这个问题有讨论，作者自己实现了一个高效 regex

[hkhk366]

@BeautifulSoap 感谢，你是唯一愿意自己动手测试一下，go 语言我也会，我一开始整个项目就是 go 写的，后来发现性能完全不能满足我的要求，所以我换成了比 go 更快的编译型语言写。正如你自己所说，你是用的随机字符串，并不是真实数据，所以就会有很大的偏差，我当然自己也试过，我不是那种不动手就上来。实验结果就是真实数据单线程查询超过了 40 毫秒，因为我搜的是包含"a"，100 万真实数据有大量是包含“a”的，而且有个最关键因素，你搜的[]string 吧，真实数据每一个记录不可能 string ，因为至少还有文件大小，修改时间等等，一带上这些立刻性能严重下降，为什么会突然下降呢？这个问题留给你

[iseki]

https://www.voidtools.com/forum/viewtopic.php?p=60222

[hkhk366]

@kuituosi 我想了解一下，如何剪枝，怎么剪枝这很关键。剪枝一般用于树，全文索引可不是树，你怎么剪枝呢？请给一个具体例子

[soy]

挺有意思的问题，void 自己的解答在这里： https://www.voidtools.com/forum/viewtopic.php?t=9463

The database is basically a list of all the file names (in UTF-8), size, date modified and pointers to parent folders.
Indexes are maintained for name, path, size and date modified.

Everything is written entirely in C.

Searches are compiled into byte code and executed.
Everything uses an optimized multi-threaded strstr search on every single filename in the database.

I wrote the Everything database specifically for filenames to be efficient as possible.

>> That means you create your own regexp engine, in C?
Basically, yes.

基本上就是优化搜索词，逐条匹配每个文件。

至于搜索结果快速排序，everything 额外维护了一个快速排序索引，所有文件已经按日期/大小等索引预排序了
https://www.voidtools.com/support/everything/indexes/

[hkhk366]

@iseki
@soy
非常感谢两位，这个作者的回复收益良多。我自己测试过，多线程正则的确能将速度压倒 6 到 10 毫秒，对方是经过特殊优化的，我这个只是通用的。
我想问一下“至于搜索结果快速排序，everything 额外维护了一个快速排序索引，所有文件已经按日期/大小等索引预排序了”这个具体如何做？

根据我的理解，比如按文件大小排序，文件大小是排序 key ，然后每一项至少还得保存一个指针指向自己的主结构吧，然后遍历这个提前排好的数组或者链表，然后一个一个走正则。当文件变动的时候这个数组或者链表也要调整。

[soy]

@hkhk366 对，差不多就是这样

[ntedshen]

话说我用 mariadb 10.6.7 集成的 mroonga 全文本引擎测试了一下我自己做测试用的自己的色图文件夹索引。。。
817778 个文件节点
dataLength 167.37 MB (175,497,216)
indexLength 68.31 MB (71,630,848)
主键，单独的标题列，描述列，标签列，和 JSON 打包整合前三数据的索引列，时间状态和各类参数的总表。。。

使用
select SQL_NO_CACHE * from node where match(index_node) against ('fate grand order') order by title limit 500;
查询基本也是在 ms 量级。。。

mroonga/groonga 这引擎很老了。。。倾向于这大概是全文本基本功。。。

[matrix1010]

@hkhk366 按照官方说明索引 100 万文件要花 1 分钟： https://www.voidtools.com/en-us/faq/#how_long_will_it_take_to_index_my_files. 考虑到要建索引和分词 1 秒 100 万不太可能。倒排索引我觉得 1gram 和 2gram 就行。文件名 1 个索引，文件大小 1 个索引。文件名索引存[]string ，其他索引直接存[]bytes 方便 bitwise 操作。比如搜"abcd", 那就 ("ab"索引 AND "bc"索引 AND "cd"索引) 。然后再 AND 文件大小索引。最后反查一遍文件名数组把 bitwise 结果为 1 的找出来。对于 regex 的情况如果包含常固定字符可以先用 ngram 过滤一遍，剩余结果再真用 regex 匹配

[secondwtq]

Linux 也有 locate ，考虑参考一下？

[secondwtq]

而且几 ms 就完成不能得出搜索时 CPU 占用很低的结论，任务管理器一秒更新一次数据，那么把 CPU 占满 10ms ，你看到的也就 1%的占用率变动，这个甚至不如日常使用时其他进程的波动大 ...

[kuituosi]

@hkhk366 比如文件名称 aabbcc ，1 个字符只有 abc 三个，2 个字符只有 aa ab bb bc cc ， 而没有 ac ca cb
这样算下来全文索引并不是很大

[kuanat]

@hkhk366 #20

我知道问题出在哪里了，是“全文搜索”这个词有歧义，我理解成了 document retrieval 而你想表达的是 substring indexing 。

回到“建索引”这个事情上，我说下 everything 的做法。很早之前逆向过，有个大致的印象，不保证适用于现在的版本。即使不逆向，很多思路也能推理出来。

1.
持久化层面上，本地数据库就是 MFT 解析之后换了个私有格式，文件夹和文件分开，排序之后保存。目的是加速冷启动之后的数据重建。这个排序反正是一次性的，后续根据 Journal 来更新。

重点在于它是用什么样的数据结构来描述文件系统的树型关系，考虑到查询是经常需要按某个子路径做筛选的，所以文件和文件夹都会记录 parent 的指向。这里 parent 就是比较重要的索引之一。

2.
其他可以检索的字段的索引都是在内存中重建的，比如文件大小、扩展名和时间戳这些。

就是类似 sql 那种对某个字段建索引，说白了就是换个结构重写了一份。印象用的是 B+ 树而不是 hash ，因为 hash 不太适合做范围查询。

3.
字符串匹配明显是基于正则的。所以像文件名、路径名是没必要做“索引”的，都是全量匹配。

一般来说，解释型的正则引擎都比较慢。编译型的正则引擎要么是编译成 bytecode 然后 JIT 运行，要么是编译时就把所有匹配路径都预先编译好。后面这个方式只适用于正则比较简单的情况，everything 是支持 \n 回溯的，生成的二进制文件也很小，不太可能是后面的做法。

手写正则引擎这个事情我没做过，理论上要建 NFA 然后转成 DFA ，这个过程比较麻烦。运行的时候只需要对 pattern 做一次，然后就可以匹配所有字符串了，对于文件名 substring matching 这个场景是非常合适的。

4.
everything 没有用 pcre 的原因应该是它不需要“通用”的正则引擎（没有替换的需求，也就不需要记录中间状态），自己写一个性能会更好。

另外它不支持模糊查询，我理解这里不是个性能问题，计算 Levenshtein 距离没有太大开销，但是结果排序的开销会很大。



顺便一提逆向的事情。具体到 everything 上面，主要还是靠静态分析。因为这个程序写得非常好，又没有刻意做混淆，尽管 c 程序非 debug 版是不带符号表的，但是通过字符串 xrefs 很容易理解并还原调用逻辑，特别是你大概能猜到作者思路的情况下。

另外用逆向手段还原算法有两种，比如加密狗之类的逻辑一般需要硬怼，但像 everything 这种主要靠猜，根据传参和返回还有逻辑，从语义上理解操作过程，毕竟它大概率是某个已知算法，而不是作者自创的。

[hkhk366]

@ntedshen 感谢手动测试，类似的测试我试过，你看你的索引文件已经超过 120MB ，显然还是 everything 的方式更小，而且你这样做是不支持 everything 正则表达式的，everything 正则表达式和普通搜索是几乎一样速度，而且你只获取了前 500 个，这个不能说明问题，如果不优化会出现深分页问题。还有就是这种方法我也尝试过，如果大量插入数据，无法在 1 秒内对 100 万文件实现插入。

[hkhk366]

@kuanat 恕我直言，你这个和没逆向没有任何区别。
1.MFT 和 USN 这个所有人都知道，根本不需要逆向，直接跳过。
2.文件大小，修改时间这些信息当然不用逆向都知道必须存内存，否则根本无法这么快。能优化排序的方法就那么几个，和没说一样。
3.唯一有逆向价值的就是，everything 作者自述它自己实现了高度优化的正则引擎，而这个你又根本什么都没分析出来。
4.pcre 需要外部安装，这根本不需要逆向，Levenshtein 内存消耗太大，everything 搜索的时候根本内存变化很小，根本没必要逆向就知道不使用的外部 PCRE 或者 RE2 。

恕我直言，你这个逆向和没逆向没有任何区别，都仅仅是泛泛而谈，不停的在表示 everything 没壳没混淆很好分析，而我表示大部分算法级别从汇编还原是非常难的。

我可没有泛泛而谈，每一个实现方法我都说出了具体算法名字和我自己实现后大约什么性能，我是真的做过测试。既然这样你认为逆向分析 everything 这么简单，那你就分析一下作者这个高度优化正则引擎具体是怎么做的，把具体分析的地址和对应汇编贴出来还有你分析过的 everything 版本都发出来，我看得懂汇编，我也懂动态和静态逆向分析，请不要泛泛而谈。Talk is cheap. Show me the code.

[superrichman]

请考虑给作者捐赠，接着发邮件直接问。诚恳一点，把你探索的过程写给他看看。

[Ethkuil]

稍微歪一点题，不过也是关于 Everything 的性能。偶尔的偶尔需搜索文件内容时，Everything 有这个功能、但慢到我直接当不存在。不过我发现 grep 也差不多慢，该不会底层是 grep 吧🤣？如果是这样的话，能不能指望 Everything 更新改用 ripgrep ？

当然，很多时候不会满足于只搜到文件，还需要知道具体匹配到了哪些行，那样的话只能开终端跑 rg 了。

[followNew]

https://www.voidtools.com/zh-cn/donate/
不如直接找作者

[wjx0912]

op 是不是想搞个跨平台的 everything ，这个必须要支持（ mac 找它好久了）~~~