Kraken2 是宏基因组 reads 分类领域中具有代表性的工具。它并不只是一个生物信息学程序，也可以被视为一个小型系统工程案例：算法层面涉及 k-mer、minimizer、taxonomy tree 与 LCA；数据结构层面涉及紧凑哈希表、开放寻址与概率性误差；系统层面涉及大规模内存访问、缓存局部性、I/O、并行调度、mmap、page cache 与输出顺序维护。以 Kraken2 为主线进行学习，能够把宏基因组分类算法、Rust 语言实践、操作系统知识和计算机体系结构问题组织在同一个问题域中。
本文是这一系列笔记的启动篇。它不试图立即解释 Kraken2 的全部细节，而是先界定本系列的目标、问题边界、学习路径与可验证成果。后续文章将从论文、手册、源码和独立实现四个层面逐步展开。
Table of contents
Open Table of contents
问题背景与基本目标
宏基因组测序通常产生大量来自混合微生物群落的 reads。一个基本任务是判断每条 read 最可能来自哪个 taxon，并在样本层面进一步推断物种组成或丰度结构。严格地说，Kraken2 的核心任务是 read-level taxonomic classification；如果需要 abundance profiling，通常还需要结合类似 Bracken 的后处理方法。因此，本系列会区分两个层次：第一，reads 到 taxon assignment 的分类问题；第二，由分类结果推断样本组成的 profiling 问题。
本系列的直接目标不是在短期内实现一个全面替代 Kraken2 的工具。更合理的目标是：通过 Rust 重实现一个简化但完整的 mini-Kraken2，逐步理解经典 metagenomic classification 的算法细节，并借助 profiling、benchmark 和源码对照，分析性能瓶颈与可能的改进方向。
这一目标可以分解为四个方面：
- 理解 Kraken2 从 reference genomes 构建数据库、从 reads 生成 taxonomic assignment 的完整流程。
- 使用 Rust 实现可验证的核心组件，包括 DNA 编码、canonical k-mer、minimizer、taxonomy LCA、数据库构建和 read 分类。
- 将性能问题落实到具体系统概念，例如 cache line、TLB、page cache、mmap、线程调度、NUMA、分支预测和内存带宽。
- 建立可复现的实验体系，用小数据集、固定命令、明确指标和版本化代码记录每一次优化的效果。
为什么选择 Kraken2
Kraken2 的价值在于其设计高度集中地体现了生物信息学算法和系统性能工程的结合。它的核心思想并不是保存所有 k-mer，而是通过 minimizer 降低数据库规模；数据库不采用普通通用哈希表，而是使用更紧凑、更适合内存访问模式的结构；分类时不是孤立地解释单个 k-mer 命中，而是将一条 read 中多个命中的 taxonomic 信息综合到 taxonomy tree 上。
从学习角度看，Kraken2 具有三个优点。
第一，它的问题定义足够清晰。输入是 reference database 和 FASTQ/FASTA reads，输出是每条 read 的分类结果以及样本层面的 report。这使得每个阶段都可以被测试和比较。
第二，它的性能瓶颈具有代表性。大规模分类器往往不是受限于少量算术运算，而是受限于随机内存访问、哈希表布局、缓存未命中、I/O 解压、线程分配和输出同步。这些问题正好构成操作系统和体系结构学习的实际语境。
第三，它适合逐步复现。可以先写一个正确但低效的版本，例如使用普通 HashMap 存储 minimizer 到 taxon 的映射；随后再逐步引入紧凑表示、批量处理、零拷贝 parser、多线程 pipeline 和更 cache-friendly 的数据布局。
Rust 重实现的角色
Rust 在本系列中不是性能提升的充分条件，而是一种学习和实验工具。仅仅把 C++ 源码逐行翻译为 Rust，并不能保证更快。Kraken2 的主要效率来自算法选择和数据布局，而不是单一语言特性。Rust 的意义在于，它允许在较强类型系统和所有权模型下组织复杂的底层实验，并将 unsafe 边界限制在少数经过验证的热点路径中。
因此，Rust 重实现应当遵循以下原则：
- 先追求可解释的正确性，再追求性能。
- 先实现清晰的 toy version，再阅读并对照 Kraken2 源码。
- 先用普通数据结构建立闭环，再逐步替换为专用结构。
- 对每次优化进行独立 benchmark，避免同时修改多个变量。
- 对 unsafe、SIMD、mmap、并行和自定义内存布局保持审慎态度，以测量结果而不是直觉作为判断依据。
在实现层面，早期版本可以包括以下模块：
FASTA / FASTQ reader
DNA 2-bit encoder
reverse complement
canonical k-mer
minimizer scanner
taxonomy tree
LCA computation
minimizer-to-taxon database
read classifier
classification report
benchmark harness这些模块一旦闭环，就可以构成后续所有性能实验的基础。
系统知识为何不可避免
Kraken2 这样的程序会把许多系统层面的细节暴露出来。对于宏基因组分类而言，数据库通常很大，查询模式又具有大量近似随机访问。因此，性能常常不是由单个循环的算术速度决定，而是由内存层级和数据移动决定。
例如，紧凑哈希表的设计需要理解 cache line、load factor、linear probing 与局部性；输入解析需要理解 buffered I/O、压缩流、内存分配和字节级处理；数据库加载需要理解 mmap、page fault、page cache 与预读；多线程分类需要理解任务划分、锁竞争、false sharing、输出顺序和负载均衡。
在这一背景下，缓存一致性和崩溃一致性可以作为两个具有代表性的系统概念。缓存一致性关注系统正常运行时多个缓存副本是否观察到一致的数据，例如多核 CPU 对同一内存位置的读写是否会产生过期观察。崩溃一致性关注系统在断电或异常停止后，持久化状态是否仍满足文件系统、数据库或应用定义的不变量。这两个概念分别指向运行时共享状态和崩溃后的持久状态；它们虽然不都是 Kraken2 算法本身的核心问题，却能帮助理解现代系统中“数据何时可见”和“数据何时可靠持久化”这两个基础问题。
随着 CXL、DAX、持久内存和内存语义设备的发展，传统的内存、缓存和存储边界正在变得更复杂。对生信工具而言，这些进展未必会立即改变每一个分析流程，但它们会影响未来大数据库、多样本并行分类、内存池化和远端内存访问的系统设计。
预期学习路径
本系列计划按照由简到繁、由算法到系统的顺序展开。
第一阶段是算法骨架。重点解释 k-mer、canonical k-mer、minimizer、spaced seed、taxonomy tree、LCA、read-level voting 和 confidence threshold。这一阶段的目标是写出一个可以处理小型 reference database 和 reads 的 toy classifier。
第二阶段是源码阅读。重点对照 Kraken2 的核心源码，理解输入读取、minimizer 扫描、compact hash table、taxonomy 查询、分类主循环和 report 生成。源码阅读不以逐行注释为目标，而以回答“该实现避免了什么成本”为目标。
第三阶段是系统背景。围绕实际性能现象学习 page cache、mmap、page fault、cache locality、TLB、branch prediction、SIMD、NUMA、线程调度和 I/O pipeline。每个概念都应当回到 Kraken2 或 mini-Kraken2 的某个具体实验中。
第四阶段是性能实验。每个实验只改变一个变量，例如普通 HashMap 与紧凑表的差异、所有 k-mer 与 minimizer 的差异、字符串 parser 与字节 parser 的差异、单线程与多线程的差异、mmap 与读入内存的差异。实验记录应包括假设、数据集、运行命令、时间、内存、profiling 指标和结论。
第五阶段是收束与改进。在已有实现基础上，选择一个边界清晰的改进方向，例如更快的 minimizer scanner、更 cache-friendly 的查询表、零拷贝 FASTQ parser 或 reader-worker-writer pipeline。改进是否成立必须由可复现实验决定。
评价标准
本系列不以“是否超过 Kraken2”作为唯一评价标准。更合适的评价标准包括：
- 是否能够准确解释 Kraken2 的数据库构建和分类路径。
- 是否能够独立实现一个最小可用的分类器。
- 是否能够用 profiling 工具定位主要瓶颈。
- 是否能够解释某个优化为什么有效或无效。
- 是否能够把系统概念与具体代码路径对应起来。
- 是否能够形成可复现的实验记录和技术文档。
这样的评价标准更符合学习型重实现项目的性质。一个教学型 mini-Kraken2 即使功能远少于原工具，也可以在算法理解、工程实践和系统知识积累方面产生实质价值。
后续写作计划
后续文章将从以下问题开始：
- Kraken2 的分类任务究竟是什么：classification 与 profiling 的边界。
- 从 DNA 字符串到 2-bit 编码：为什么底层表示会影响性能。
- canonical k-mer 与 reverse complement：双链 DNA 如何进入统一索引。
- minimizer 的意义：为什么不保存所有 k-mer。
- taxonomy tree 与 LCA：为什么命中结果要被提升到共同祖先。
- 一个最小 toy classifier 的实现。
- Kraken2 源码中的 minimizer scanner。
- compact hash table 与 cache locality。
- FASTQ parser、压缩输入与 I/O pipeline。
- 多线程分类与输出顺序维护。
- mmap、page cache 与大数据库加载。
- 缓存一致性、崩溃一致性与生信工具中的系统边界。
这些文章的共同目标是把一个经典工具拆解为可学习、可实现、可测量的组件。通过这种方式，宏基因组 reads 分类不再只是调用命令行工具得到 report，而是成为理解算法、语言和系统性能之间关系的具体入口。
小结
以 Kraken2 为主线进行学习，关键不在于立即写出一个更快的替代品，而在于建立一条稳定的技术路径：从 reads 分类问题出发，理解 minimizer 和 LCA 等算法结构；通过 Rust 重实现建立可运行的实验对象；再用操作系统和体系结构知识解释性能现象。只要每一篇笔记都对应一个明确问题、一个可运行实现或一个可复现实验，这一系列就能够逐步形成对 metagenomic profiling 和系统性能工程的系统性理解。