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 的算法应该非常轻量高效。

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

[lervard358]

https://stackoverflow.com/questions/47686560/what-makes-everythings-file-search-and-index-so-efficient

[tool2d]

先用 bloom filter 过滤一下，能直接把数据量从 200 万降低到 20 万。

再用红蓝树/std::priority_queue 之类的查询，速度一般来说还是挺快的。

你看以前上亿数据库是怎么分库的，就是分而治之呗。只要数据量下来了，什么都好办。

[hkhk366]

@lervard358 谢谢回复，但是这个 stackoverflow 的帖子没什么帮助，那个帖子主要是在讨论 MFT 的知识，这些我早就已经解决了，并且已经在本帖最开头就已经提到了，我的话题是仅仅讨论 everything 的索引原理，有什么其他关于索引的分享吗？谢谢。

[MoYi123]

用这个数据结构为基础, 我猜应该可以做到差不多的性能.
https://github.com/BurntSushi/fst

[hkhk366]

@tool2d 感谢回帖，我也想过 bloom filter ，但是我自己测试是这样的，上面也有提到，我的硬盘中有 100 万文件，其中几十万（具体 90 万）文件都包含"a"，我不知道他是如何在 5 毫秒（ everything 单个字符搜索 5 毫秒，二哥字符 15 毫秒）内完成的，现在 bloom filter 对这个案例过滤不了多少，并且用 priority_queue 也无法保证在 5 毫秒内完成 90 万文件搜索+排序。所以最大的问题是，everything 能再 5 毫秒内完成 90 万文件的操作，并且整个过程中好像还没有并行计算，我观察 CPU 都多核没变化。如果按照分库分表并行的话，必然 CPU 会有不少波动，我上面说的并行方法其实就用的分库分表，不能符合预期。还有什么其他的方法愿意分享吗？多谢

[matrix1010]

没明白 abc.txt 难分词的原因，搜索 a 那所有包含 a 的文件都应该显示。另外"倒排 100 万文件大约需要 1 个 GB 的空间"感觉也不对，你是用 sqlite 的全文检索测试的吗

[tool2d]

@hkhk366 就我个人来说，并不觉得 everything 用了太多黑科技算法。可能就是单纯代码写的好，优化的好。

现代 CPU 缓存也挺重要的，说不定 5ms 只是占了高速缓存的便宜。长字符串搜索，相对优势就没那么明显了。

bloom filter 也有很多变种，针对文件名高度优化后的效果，肯定和普通开源代码有区别的。

[mosakashaka]

@hkhk366 SO 帖子里评论说，数据是存在 sqlite 里面的。加载到内存里查询。

[xtreme1]

试没试过 ripgrep..

[shinession]

内存占用也很少, 大概 100 万文件, 只占用不到 100M 内存, 同样感兴趣, mark 下

[aoguai]

我记得 everything 用的 NTFS 文件系统的 USN 日志所以那么快。具体可以搜搜。随便找的一篇👇🏻
GitHub - LeiHao0/Fake-Everything: Everything 的原理猜想与实现
https://github.com/LeiHao0/Fake-Everything

[kuituosi]

全文索引加剪枝就能实现，文件名中有大量重复的内容，剪枝可以减少很多内存

[SmiteChow]

空间换时间，没有魔法

[xiang0818]

esdb

[kuanat]

其实你这个思路偏了啊，当你意识到 5ms 连文件 IO 都完成不了的时候，应该考虑这不是个算法问题而是个策略问题。



官方页面上已经说得很清楚了，因为关键内容不多，我就直接复制过来：

来自 https://www.voidtools.com/support/everything/searching/

Content Searching

Warning: content searching is extremely slow.

File content is not indexed.

Please combine content: functions with other filters for the best performance.

Content search functions:
content:<text> Search file content using the associated iFilter. If no iFilter exists UTF-8 content is used.
ansicontent:<text> File contents are treated as ANSI text.
utf8content:<text> File contents are treated as UTF-8 text.
utf16content:<text> File contents are treated as UTF-16 (Unicode) text.
utf16becontent:<text> File contents are treated as UTF-16 (Big Endian) text.

另外 https://www.voidtools.com/forum/viewtopic.php?t=9793 这里有更详细的说明。

Everything will keep content in memory.
Content indexing is intended for indexing user documents only.
I do not recommend indexing over 1GB of text.
For the best performance, set an include only folder.

By default, Everything will index the following file types for content:
*.doc;*.docx;*.pdf;*.txt;*.xls;*.xlsx



这 5ms 就做了一个内存数据库的检索，而且数量级并不是你想象中的 100 万。你在没有验证的情况下，就认为它扫描了文件，所以思路跑偏了。即使没有一点逆向基础，也有很简单的办法知道一个程序运行的时候打开读取了哪些文件，如果你验证了这一点，估计已经找到答案了。

所有的“索引”类算法，核心思想并不在“算”上面，而在于将原始数据结构以一种易于被检索的数据格式存储。换句话说，之所以索引可以加速搜索，是因为提前生成了要查询的结果。

Windows 自身有个索引服务，但是绝大多数文件格式都是二进制的，在不了解它的文件结构的情况下，是没有办法进行文本搜索的。所以 Windows 提供了一个 IFilter 机制，由文件格式的创建者，主动暴露可以被索引的信息。然后再通过后台服务对于相关的文件格式进行索引，首次全盘索引完成之后，只有文件内容发生变化，才会触发索引更新。几大操作系统的索引都是相同的机制。

Everything 的说明就是这样一个意思，它会在内存索引少数路径下的特定格式的文件，为其建立文本内容索引。后续的搜索只是内存搜索引。至于全文匹配到底用了什么算法，是不是有指令集优化，是另外的事情，到了这个层面，只要思路对，算法是不是最优化已经不重要了。（ Everything 是 C 写的，但是没有什么混淆加密，稍微逆向一下大概就能弄清楚。）

[denok]

是内存，我记得 8G 到 32G 的时候，速度肉眼可见的变快

[littlewing]

这个帖子的回复已经有 3 个人是不看内容只看标题的，所以楼主以后还是把标题写长一点写清楚一点吧

[cy18]

我记得好像哪看到好像就是直接把索引丢 sqlite 里面然后用 sqlite 搜索？

[BeautifulSoap]

虽然但是，，，，，，，，，我试了下，用 go 生成了包含 100 万个随机字符串的数组，然后直接简单粗暴地用 for 遍历整个数组，然后对每个成员做 strings.Contains() 搜索，遍历完成都才花了 11ms

lz 你是不是对现代计算机的性能有误解。。。。。

[hkhk366]

@kuanat 你好，谢谢你的回复，但是你完全没有仔细阅读 1 楼的内容，我从来没有讨论文件内容索引的问题，我从来没提文件 IO 的事情。我一直讨论的是文件名，文件路径，文件大小，修改时间这些快速索引，搜索，排序的问题。

至于 x64 逆向我会，但是你能从从汇编反向推出来核心索引算法吗？除非花费大量的时间，否则根本不可能，你顶多下个断点，知道什么时候触发一下。

[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 找它好久了）~~~

[beijiaoff]

同好奇此话题。或许可以先看看类似 everything 的软件如何实现，能打开一些思路？