索引、内存、正则把 fsearch 的「毫秒级」拆开看它到底快在哪【免费下载链接】fsearchWhole-disk file search for macOS: fuzzy names, typo tolerance, indexed content grep. ~1 ms over 8M files.项目地址: https://gitcode.com/gh_mirrors/fsea/fsearch一个在 macOS 上做全盘文件搜索的工具标称 770 万文件条目、按名称搜索 p50 1.3 ms内存占用 30–135 MB——这个量级意味着什么如果按每毫秒扫一遍全盘的朴素直觉770 万条记录一毫秒内扫完近乎不可能如果按数据库全表扫描的经验这个响应时间又快到反常。fsearch本仓库README.md给出的答案其实并不神秘它把搜索拆成了三层工程——预建的索引、按需驻留的内存、以及把过滤条件压进常量的查询计划。本文直接进入仓库源码Rust 实现约十个源文件把「毫秒级」逐层拆开索引怎么建、怎么更新、内存怎么省、正则和过滤语法能做到哪一步最后与数据库型全文索引如 ClickHouse 的 FTS 重构做一次思路对照。一、毫秒的前提一次全盘快照被排版成可按范围查询的索引1.1 构建一次系统调用批量取回整目录毫秒级查询的前提是查询时不用碰磁盘而这取决于全盘快照怎么建。fsearch 首次构建走的是src/walk.rs通过 macOS 的getattrlistbulk(2)一次性批量取回一个目录下成百上千条记录名字、类型、大小、mtime、隐藏标志一次到位没有逐文件的 stat。目录之间用 rayon 池并行展开子目录用openat()相对父目录的 fd 打开路径不必逐层拼接重建PATH_MAX 也不再成为约束。源码里留了一条实测注释src/walk.rs在这台机器上open()close()约 19 µs/目录getattrlistbulk约 14 µs超过约 8 线程后内核侧不再扩展。也就是说构建瓶颈在 I/O 系统调用而不是 CPU这也是为什么首次全盘扫描能压到 20 秒左右README.md而引擎在索引未就绪时返回的报错信息也直言 indexing (first run scans the whole disk, ~20s)src/engine.rs。1.2 布局DFS 块 扁平段mmap 即用构建完成后src/index.rs的Index::build把所有 listing 按深度优先顺序排布进一个扁平 blob每个目录的子孙在条目表里是一段连续区间dir_start..dir_end。这带来两个直接收益路径解析lookup走的是每目录二分查找孩子块内按名称排序in:范围过滤是范围切片不是逐条过滤——Searcher::scope_range直接由 scope 目录的子树区间得到(lo, hi)src/query.rs。整个索引是 16 个 section 拼接成的单文件magicFSIDX0074 KiB 头 64 字节对齐段加载方式是mmap整个文件、from_raw_parts直接当切片用src/index.rs。mmap 意味着索引不在进程堆里页面由内核按需调入闲下来可被回收查询进程本身几乎没有常驻负担。full_build完成后还有一个细节——重新从文件 mmap 一遍把匿名内存换成可驱逐的页面缓存src/engine.rs。启动时prefault()只把查询必经的六个段掩码、名称偏移、名称、条目名、kind、parent按 16 KiB 步长 touch 一遍大小、mtime、目录表则按需分页src/index.rs。于是从冷启动到能回答第一条查询只需约 50 msREADME.md的 fff 对比表中ready after launch。1.3 一次构建的成本换来什么仓库自带的对比基准在demo/vs_fff.pyChromium 目录 509k 文件、同一台机器、同一组查询录屏见demo/fsearch-vs-fff.mp4按名称找文件 1.1 ms vs 13.8 ms文件内容搜索 5.6 ms vs 53 ms拼写错误仍把正确文件排在首位 98% vs 88%启动就绪 50 ms vs 2.5 s内存 50 MB全盘vs 358 MB仅该目录——这些数字全部来自仓库自身的测量脚本方法是可复现的。二、保鲜索引不是快照是 FSEvents 驱动的实时状态索引是一次性快照的话毫秒级没有任何意义——磁盘每分钟都在变。fsearch 的更新链路是src/fsevents.rs起的 FSEvents 流 src/live.rs的增量应用重新定义了索引的含义。2.1 base dead overlay 三段式src/live.rs的Live结构是三个部分的组合base不可变的 mmap 索引dead一个 u64 位图标记 base 中已消失的条目每条目 1 bitoverlay一个 BTreeMap按路径有序存放增量条目OEnt带 kind/size/mtime/掩码。每个 FSEvents 目录事件的处理方式统一为list 该目录 → 与当前状态 diff → 应用。diff 是幂等的所以重放历史、重复事件、与压缩竞态的事件都无害。搜索时search()先查 base、再查 overlay、合并后截断到 limitsrc/query.rs。这样索引永远活着新建/重命名/删除的文件约 0.1 秒内即可被搜到README.md而不是像传统更新数据库那样定时全量重建。2.2 压缩何时把增量落定overlay 不能无限长大因为每次搜索都要扫全 overlay。压缩由两个阈值触发src/engine.rsCOMPACT_PENDING 50_000overlay 死亡标记超过 5 万即压缩约 1 秒 CPU 和约 280 MB 写入繁忙磁盘上大约每小时一次COMPACT_EVERY 12 小时即便增量不大只要 base 落后于事件流也定期压缩平时则约两天一次。压缩本身是Live::to_listings()把三部分重建成 listing再走一次Index::build并原子写盘tmp renamesrc/index.rs的save。只重放 FSEvents、只在必要时重建这是索引保鲜策略的核心。2.3 事件丢失的兜底内核丢事件、历史不可用时fsearch 不会退回全盘重扫relist_changed根据自上次同步以来 mtime 变过的目录做定向重列src/engine.rs。索引头部存着event_id与synced_atsrc/index.rschanged_dirs对每个目录一次 lstat、找出 mtime 更新的少数目录再重列秒级完成而不是整盘重爬。三、内存账30–135 MB 装下 770 万条目770 万条目如果朴素地每条目存一个 String光名字就得上 GB。fsearch 的内存账目是层层抠出来的。3.1 名称驻留与字符掩码src/index.rs的注释给出了关键数字7.5M 条目共享约 2M 个不同名称。所以名称被驻留intern成一份每个去重名称再带一个 u64 的字符掩码name_mask——每个字符类小写、大写、数字、点、连字符/下划线、空格、非 ASCII、其他占一个 bit高位 spare bit 存名称首字母与每个空格分词的首字母的哈希位start_bit41–63 位。这个掩码的威力在查询侧一个查询 token 携带自己的mask一个 AND 运算就能拒绝全盘绝大多数名称src/query.rs的Token::fits且被刻意写成无分支以便向量化。typo 场景还利用了loose位允许缺一个字符类和start位要求某个词以某字母开头来预筛——大多数名字在读到字符串之前就被干掉了。3.2 字段压缩与大小编码条目表本身是定宽紧凑数组名称 idu32、kindu8含隐藏/挂载标志、parentu32、sizeu32、mtimeu32。其中 size 的编码src/index.rs的enc_size值得一提2 GiB 以下精确存储以上退化为 2 MiB 粒度的高位编码——大多数桌面文件都能精确表示而巨文件只需要 2 MiB 的精度就够用了。目录表则存 entry 下标、孩子块范围、子树结束、位置先验等全部定宽。整个索引文件的大小就在数百 MB 量级README 表格里 daemon 内存 30–135 MB 即包含 mmap 视图。3.3 mmap、分配器与查询缓冲池内存优化的另一半在临时内存管理全局分配器src/main.rs大于 1 MB 的分配直接mmap、释放直接munmap。注释记录了一个典型教训macOS malloc 会把释放的大块保留为映射的脏页一次索引构建后守护进程 footprint 飙到约 1 GB而存活数据只有约 2 MB。大分配绕开 malloc 后构建峰值随分配即走。查询期缓冲池DENSE_POOL约 24 MB 的稠密名称命中表与MEMO_POOL约 13 MB 的目录记忆在查询间复用避免每次查询触发缺页风暴空闲 60 秒后trim_if_idle连同names_cache一起回收src/query.rs。QoS 隔离名称搜索跑在USER_INTERACTIVE的专用线程池避免落到能效核内容索引构建跑在UTILITY4 线程池src/engine.rs互不拖累。四、正则与过滤查询语言的能力边界4.1 语法面src/query.rs的Query::parse定义了完整的查询语言普通词是模糊 tokenx精确、^x前缀、x$后缀、!x排除过滤器有ext:、type:image/video/audio/doc/code/archive/font 七大类映射到扩展名表、kind:、in:、size:、mtime:、re:名称正则、path:路径正则、limit:、以及内容侧grep:/regex:/sym:。范围语法支持、、a..bmtime:7d是7 天内修改过的相对时间。type:app有专门的合成kind 目录 .app扩展名。4.2 两阶段打分先名称后条目性能的关键在于把过滤拆成两个阶段src/query.rs的Searcher::search_base名称阶段只对约 2M 个去重名称打分一次得到哪些名称命中、命中哪些 token、分数多少的表——输入时下一次按键通常只是上一次查询的收窄NameKey::narrows检测查询只是变长/变严直接在上一次名称表上继续筛而不是重扫。条目阶段命中名称携带的条目数低于SELECTIVE 60_000时走selective 路径只访问这些条目的名称→条目倒排表name_ents否则走 full 路径对条目区间做一遍顺序扫描 TopK。top_k用每线程一个小堆 合并时再选的方式避免了全局堆在大部分磁盘都命中时的开销。目录 token如in:内多 token 查询通过DirMemo做祖先折叠每个目录记住它的名字或祖先名字命中了哪些 token条目打分时只需查父目录的记忆位不必为每个条目重建路径字符串。这个记忆表也进了缓冲池复用。4.3 掩码过滤与 typo 的代价模糊匹配是 fzf-v1 风格最左结束匹配 从右收缩起点 边界/驼峰/连续命中加分memchr的 SIMD 让大多数名字在第一个字节就失败src/query.rs的fuzzy_score。拼写容错走的是one_edit_prefix5 个字符以上的 fuzzy 词允许一个编辑错误错、多、缺、交换且数字永不参与编辑hat_18 不是 hat_98 的 typo。typo 命中按正确拼写分数 − 60计保证干净匹配永远排前面。位置先验src/index.rs的prior_adjust把/Applications、.app、node_modules、target等目录的权重做了显式编码——搜索结果的排序不是纯字符串匹配而是匹配质量 位置先验 时效性的加权。4.4 内容搜索trigram 倒排 候选二次验证按名称搜是索引查询按内容搜则是另一套索引src/content.rs的 trigram 倒排。文本文件限制 1 MB 内、白名单扩展名、跳过 node_modules/.git/target 等被切成语义无关的 3 字节 trigram倒排表用 delta varint 或位图超过 1/8 文档含该 trigram 时自动切换存储段文件FSCSEG03同样 mmap。查询侧字面量模式 AND 出全部 trigram 的 posting list 求交集正则模式先用regex-syntax解析 HIR推导出该正则必须含哪些 trigram的查询计划src/content.rs的regex_plan候选集因此大幅收窄sym:则直接查声明关键词后标识符的哈希 key。最关键的设计是候选—验证分离索引只负责哪些文件可能匹配最终匹配永远从磁盘重新读文件、用真正则验证。所以结果永不过期src/content.rs模块注释索引的滞后最多影响候选选择。验证带 250 ms 预算与每文件最多 5 个命中行的上限超时返回已拿到的最好结果。这是索引保鲜思想在内容侧的延伸——索引可以有轻微滞后但结果必须新鲜。4.5 边界与取舍能力边界同样写死在代码里正向 token 最多 8 个typo 只对 ≥5 字符的 fuzzy 词生效token 掩码只能按字符类拒绝不能拒绝同字符类的近拼写所以 typo 路径仍要逐个名字扫描代价约 10 倍注释明言内容索引只覆盖$HOME范围内可识别为文本的文件in:/etc这类范围会退化为从名称索引挑文件、直接 grep的扫描路径src/content.rs的scan_paths。这些不是缺陷而是显式取舍——把预算花在 99% 的场景上。五、与数据库型全文索引ClickHouse FTS 重构的思路对比社区情报中有一条值得对照的线索ClickHouse 重构全文索引、在对象存储上跑出高性能 Full-Text SearchInfoQ 报道。两者看似风马牛不相及——一个是桌面守护进程一个是分布式分析数据库——但把 fsearch 的内容索引src/content.rs和数据库全文索引放在一起看骨架是同构的倒排表 posting listfsearch 是 trigram → 文档 id 列表delta varint 或位图ClickHouse 类是 token/gram → row id 列表。编码手段同源列表稀疏用变长增量、稠密用位图。候选—验证fsearch 用索引缩小候选、读原文验证数据库全文索引同样面临索引滞后 vs 数据新鲜只是把验证换成读存储上的原始列数据。分段与合并fsearch 的段按大小分层、每层 8 段合并一次merge_planMERGE_CAP限流合并峰值内存数据库全文索引的 LSM 式段合并是同一个思路——用不可变段 分层合并把增量成本摊平而不是原地更新倒排。查询计划推导fsearch 从正则 HIR 反推必含 trigramregex_plan数据库查询优化器从 SQL 反推可用索引——本质上都是从查询语言向索引结构做下推。真正的分野在工程形态维度fsearch数据库型全文索引如 ClickHouse FTS数据规模单机百万级条目分布式、列存、可到 PB索引载体本地 mmap 文件随进程按需分页对象存储/远端需要物化与缓存策略新鲜度FSEvents 实时 diff秒级可见批式/异步提交时效由写入链路决定并发模型单进程多线程QoS 隔离多节点并行扫描分布式 top-k定位交互式桌面检索250 ms 预算内出结果分析型查询吞吐优先结论是毫秒级不是算法魔法而是工程取舍的系统性结果——全盘快照只建一次之后用 FSEvents 增量保鲜索引以定宽字段 mmap 常驻查询把过滤条件压进 u64 掩码和范围切片把昂贵正则推迟到最后一步内存则用驻留、复用、按需分页和自定义分配器四件套压到 135 MB 以内。把这一套拆开看每一层都很朴素合在一起就是 770 万条目上 1.3 ms 的由来。如果你要复现这些数字仓库给了完整工具链cargo build --release后fsearch bench可在进程内对保存的索引计时src/main.rsdemo/vs_fff.py则是与同类工具的可复现对比基准。源码里那些注释掉的实测数字系统调用耗时、线程扩展上限、内存峰值教训本身就是一份难得的性能工程笔记。【免费下载链接】fsearchWhole-disk file search for macOS: fuzzy names, typo tolerance, indexed content grep. ~1 ms over 8M files.项目地址: https://gitcode.com/gh_mirrors/fsea/fsearch创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
