从零编写操作系统 14 - 抢占调度:时间片结束后怎样换一个任务
第 13 篇能够保存两条调用链,但 A 一旦进入不含 yield 的无限循环,已经就绪的 B 就无法运行。 本篇把第 08 篇的 PIT 时钟接入同一个调度器,让两个没有主动让出点的计算任务都取得进展。 时间片采用最小规则:每次时钟中断提出一次轮转请求,允许调度时在中断处理出口切换。 切换函数仍然只保存四个被调用者保存寄存器。 被时钟打断的完整寄存器与 EFLAGS 则留在原任务的中断栈帧里,等该任务恢复以后由 IRETD 还原。 实验另外检查允许中断但禁止抢占、真正关闭中断、嵌套恢复,以及屏蔽 IRQ0 后另一个任务停滞的区别。 时钟可以打断调用约定没有覆盖的位置 普通 task_yield() 是编译器可见的函数调用。 编译器会按 ABI 处理跨调用仍然有效的数据,第 13 篇因此只需在切换函数中保存 EBP、EBX、ESI、EDI 和栈位置。 时钟中断却可能发生在加法与后续条件跳转之间,也可能发生在 EAX 刚算出一个值、尚未写回内存的时候。 这种位置没有普通函数调用,不能允许中断处理随意丢弃 EAX、ECX、EDX 或条件标志。 若只保存四个寄存器,两个计数任务可能仍偶...
从零编写操作系统 13 - 保存与恢复执行现场:先实现协作式任务
第 12 篇已经能按字节分配内核对象,但执行路径仍沿着同一份调用栈推进。 普通函数 A 调用 B 后,只有 B 返回,A 才能继续;如果 B 一直计算,其他工作就无法通过这条调用链取得 CPU。 本篇为两个内核任务各分配一张栈页,让任务在 task_yield() 处暂停,并在以后从同一次调用之后继续。 正常实验要求 A、B 各完成 128 轮计数,跨切换保留局部数组、被调用者保存寄存器和各自的中断允许状态,退出后归还两张栈页。 另一个镜像让 A 永远不调用 yield,检查 B 虽然已经就绪,计数仍然停在零。 这套实现只在单 CPU、ring 0、普通函数调用边界切换,没有时钟抢占,也没有独立用户地址空间。 暂停的调用链需要独立栈 函数调用会把返回位置放到栈上,局部变量与被保存的寄存器也可能占用栈空间。 若把一个执行中的函数暂停,再让另一个函数在同一片空间从头建立调用栈,前一个函数恢复时就可能读到被覆盖的数据。 独立栈使两条尚未结束的调用链能够同时保存在内存里;单 CPU 在任意时刻仍只执行其中一条。 第 10 篇的 page_alloc() 每次返回一张 4096 字节物理...
从零构建现代搜索引擎(E05):磁盘 ANN 与引擎工程对照
主线第 19 篇把向量全部加载到内存中的 HNSW 图里。100 篇文档、512 维 float32,总共 200 KB——任何机器都装得下。但如果语料从 100 篇增长到 100 万篇,200 KB 变成 2 GB;到 1 亿篇,就是 200 GB。常规服务器的内存通常在 64-256 GB 之间,向量数据已经不够放了。 这是向量检索的内存墙问题。解法有三个方向:量化压缩(第 22 篇)、分片分散(第 26 篇)、把向量放到磁盘上。本篇讨论第三个方向——磁盘 ANN,以及在什么规模下应该考虑从 Lucene 切换到专用向量引擎。 内存墙 向量数据的内存占用计算: 123456789内存 = 文档数 × 向量维度 × 每维字节数512d float32: 1K 文档: 2 MB 100K 文档: 200 MB 1M 文档: 2 GB 10M 文档: 20 GB 100M 文档: 200 GB 1B 文档: 2 TB int8 量化(第 22 篇)把每维从 4 字节降到 1 字节,内存降到 1/4。但 1 亿篇文档量化后仍需 50 GB,加上 HNSW ...
从零构建现代搜索引擎(E04):有界多步搜索与引用答案
用户搜"Java 虚拟线程和平台线程的性能差异",搜索引擎返回 10 篇文档链接。用户点开第一篇,发现只讲了虚拟线程的概念;点开第二篇,有性能数据但对比的是 Go 协程;翻到第五篇才找到需要的对比数据。 这个场景暴露了传统检索的局限:搜索引擎只负责找文档,把"从多篇文档中提取、整合、回答问题"的工作留给了用户。RAG(Retrieval-Augmented Generation)把这最后一步自动化——检索文档后用语言模型生成带引用的答案。 但 RAG 不是无限制的。模型可能幻觉,检索可能失败,生成可能超时。有界多步搜索在 RAG 之上加入资源预算:限定最大检索轮次、总耗时和 token 消耗,在可控成本内给出最佳答案。 单次检索的失败模式 主线 30 篇建立的搜索管线是单次检索:query → BM25 + 向量 → 融合 → 重排 → Top-K。这条管线在以下场景失败: 模糊 query:用户搜"那个 Java 的东西"——query 信息量太低,召回的文档分散在多个无关主题上。 多跳问题:回答需要综合多篇文档的信...
从零构建现代搜索引擎(E03):多模态文档搜索
技术文档的信息不全在文字里。一份 API 文档中的架构图、一篇论文里的实验结果表格、一页 PDF 中的流程图——这些视觉元素承载的信息量常常超过周围的文字描述。传统的文本检索管线对这些内容视而不见:OCR 提取的文字丢失版式信息,表格变成无结构的字符串,流程图直接被忽略。 多模态 embedding 模型提供了另一条路径:直接把页面图像编码为向量,跳过 OCR,保留视觉结构。 OCR 管线的局限 PDF 文档检索的传统做法: 1PDF → 逐页渲染为图像 → OCR 提取文字 → 文字进入倒排索引/embedding 这条管线在纯文字 PDF 上效果尚可,但遇到以下内容时问题显著: 表格:OCR 把表格读成一行行文字,丢失行列关系。“性能 | 100ms | 200ms"变成"性能 100ms 200ms”——搜"性能低于 150ms 的方案"时,无法区分哪个数字属于哪个方案。 图表:流程图、架构图中的文字被 OCR 提取出来,但箭头、连线、布局信息全部丢失。"A → B → C"的流程关系在纯文字中不存在。 扫描件:...
从零构建现代搜索引擎(E02):多向量与 Late Interaction
主线第 18 篇把整篇文档压缩成一个 512 维向量。这个"池化"操作不可避免地丢失信息:一篇同时讨论"线程池配置"和"垃圾回收调优"的长文档,其单向量是两个主题的模糊平均——搜任何一个主题都不会得到高分,搜两个主题的交集反而可能命中。 ColBERT(Khattab & Zaharia, 2020)提出了不同的方案:不池化,保留每个 token 的独立向量,在检索时做 token 级的细粒度匹配。 单向量的信息瓶颈 把一篇 200 个 token 的文档压缩成 1 个向量,信息压缩比是 200:1。对短文档(标题、摘要)这个损失可以接受;对长文档(技术文章、API 文档),关键细节可能被淹没。 具体场景: 123456789文档: "ConcurrentHashMap 使用分段锁实现线程安全。 初始容量默认 16,负载因子 0.75。 Java 8 之后改用 CAS + synchronized 替代分段锁。"单向量: [0.12, -0.34, 0.56, ...] ...
从零构建现代搜索引擎(E01):学习稀疏检索
BM25 靠精确词匹配召回文档。用户搜"怎样并行处理",文档里写的是"多线程编程"——BM25 一条也召不回来。dense retrieval 用向量弥补词汇鸿沟,但丢掉了精确匹配的优势:搜错误码 NullPointerException,dense 模型可能把它和所有异常类文档混在一起。 学习稀疏检索(learned sparse retrieval)试图兼得两头:保留倒排索引的精确匹配和可解释性,同时用模型扩展词汇覆盖范围。 词汇鸿沟的代价 回顾 BM25 的召回逻辑:query 中的 term 必须出现在文档中,文档才能进入候选集。这意味着: 同义词缺失:用户搜"取消订单",文档写的是"订单退回"→ 无命中 上下位词:搜"数据库",文档讨论的是"PostgreSQL"→ 无命中 缩写/全称:搜"JVM",文档写的是"Java 虚拟机"→ 无命中 传统解法是同义词表。第 13 篇介绍的同义词扩展能缓解部分问题,但...
从零构建现代搜索引擎(30):从空目录完成最终演示
30 篇文章构建了一个完整的搜索引擎:从爬虫到倒排索引,从 BM25 到向量搜索,从单机到分片,从权限过滤到相关性迭代。 本篇把所有组件打包成一个可以从空目录启动的完整系统,写清楚 README,固定测试数据,提供完整运行脚本,并诚实列出限制。最终演示覆盖查询、修改、删除、模型停机、进程重启、重新查询的全过程。 项目结构 目录布局 1234567891011121314151617181920search-engine/├── README.md├── pom.xml├── run.sh # 一键启动脚本├── demo.sh # 全流程演示脚本├── data/│ ├── seed-corpus.jsonl # 固定测试语料│ └── eval-queries.jsonl # 评测查询集├── config/│ └── search-config.yaml # 配置文件├── src/main/java/search/│ ├── crawl/ ...
从零构建现代搜索引擎(29):形成可重复的相关性迭代流程
前 28 篇构建了一个功能完整的搜索系统。但"能跑"和"搜得好"之间还有距离。搜索相关性需要持续迭代——改了分词器、加了同义词、调了 BM25 参数,怎么判断是变好了还是变差了? 本篇建立可重复的相关性迭代流程:归因失败查询、做盲评、写离线实验报告、设计 A/B 实验。每次变更都有证据支撑接受或拒绝的决定。 失败查询归因 什么是失败查询 评测集中 nDCG@10 = 0 的查询是明确的失败查询——Top-10 中没有相关文档。但更多失败是隐性的: nDCG@10 < 0.3:有相关文档但排位很低 Recall@100 = 0:相关文档根本不在召回集中 用户从搜索结果页直接退出(线上才能观测到) 四类失败 1234567891011121314151617181920212223242526272829303132333435363738enum FailureType { COVERAGE, // 相关文档不在索引中 RECALL, // 在索引中但未被召回 RANKING, ...
从零构建现代搜索引擎(28):搜索质量与访问边界
搜索引擎返回的结果必须尊重访问权限——用户不该看到无权访问的文档,哪怕那个文档与查询高度相关。同时需要过滤垃圾页和限制恶意查询,防止低质量内容和滥用行为影响系统。 本篇在检索内部实现权限过滤,而不是在结果页面上隐藏。同时处理租户隔离、垃圾页过滤、查询限额和缓存泄漏。 文档级权限过滤 为什么必须在检索阶段过滤 错误做法:先检索 Top-10,再过滤掉无权限的文档。 问题:如果 Top-10 中有 8 条无权限,过滤后只剩 2 条结果。用户看到的结果数量不可预测,体验极差。更严重的是,排序位置本身就泄露了信息——"第一条结果被过滤了"告诉用户那个位置有内容存在。 正确做法:在 Lucene 检索遍历倒排列表和 HNSW 图时过滤。过滤后的文档不参与评分和排序,就像它们不存在一样。 权限模型 每个文档存储一个访问控制列表(ACL),记录哪些用户或角色可以访问: 12345678910111213141516171819void indexDocumentWithAcl(IndexWriter writer, String docId, String ...








