17.3 最小版本选择算法

确定了语义化版本（17.2）后，还剩最后一问：当依赖图里各模块要求同一个依赖的不同版本时，到底选哪个版本？Go 的答案是一个反直觉、却异常简洁的算法,最小版本选择 （Minimal Version Selection, MVS）。它是 Go 模块最具特色、也最值得玩味的设计：别家包管理器把这件事做成了一个需要约束求解器的难题，Go 却把它压成了一遍图遍历。本节先把规则讲清，再看它为何能这么简单，最后把它放回整个领域的谱系里，看清它究竟换走了什么、换来了什么。

17.3.1 选「满足要求的最低版本」

MVS 的规则简单到令人意外：对每个依赖，选所有要求中最高的那个最低要求,换句话说，选择 能满足所有模块要求的最低版本。先用本书一贯的小例子建立直觉。你的程序直接要求 C ≥ v1.2; 依赖 A 要求 C ≥ v1.3;依赖 B 要求 C ≥ v1.1。三个要求里最高的下限是 v1.3,MVS 就选 C v1.3。注意这里的关键：哪怕此刻 C 已经发布了 v1.9，MVS 也不选 v1.9,它只选「满足所有要求的最低版本」，即 v1.3。

把这条规则放进一张真实的依赖图，就是 Go 官方文档采用的例子。主模块要求 A ≥ v1.2、B ≥ v1.2; A v1.2 要求 C ≥ v1.3;B v1.2 要求 C ≥ v1.4;而 C v1.3 与 C v1.4 都要求 D ≥ v1.2。MVS 从主模块出发，沿 require 边走遍整张图，为每个模块记下「见过的最高要求」：

flowchart TD
    Main["主模块 main<br/>require A≥v1.2, B≥v1.2"]
    A["A v1.2<br/>require C≥v1.3"]
    B["B v1.2<br/>require C≥v1.4"]
    C13["C v1.3<br/>require D≥v1.2"]
    C14["C v1.4<br/>require D≥v1.2"]
    D["D v1.2"]
    Main --> A
    Main --> B
    A --> C13
    B --> C14
    C13 --> D
    C14 --> D
    classDef chosen fill:#dff0d8,stroke:#3c763d,stroke-width:2px;
    classDef skipped fill:#f2dede,stroke:#a94442,stroke-dasharray:4 3;
    class A,B,C14,D chosen;
    class C13 skipped;

图上每个方框，对应磁盘上一份 go.mod。主模块的那份只写明它直接依赖的下限，其余要求散落在各依赖自己的 go.mod 里，MVS 沿边把它们逐一读出：

// 主模块 main 的 go.mod（只声明直接依赖的最低版本）
module example.com/main

go 1.26

require (
    example.com/A v1.2.0
    example.com/B v1.2.0
)

// example.com/[email protected] 的 go.mod 里：require example.com/C v1.3.0
// example.com/[email protected] 的 go.mod 里：require example.com/C v1.4.0
// example.com/C 的两个版本里都：    require example.com/D v1.2.0

对 C，图里出现了两个要求 v1.3 与 v1.4，取最大值得 v1.4;对 D，要求是 v1.2。最终构建列表（build list）是 A v1.2、B v1.2、C v1.4、D v1.2。请注意：C 与 D 在仓库里可能早有更高的版本，但「没有任何模块要求它们」，MVS 就不会去选,选出来的恰是「满足所有要求的、各模块版本号最低的那一组」。这份列表可以用 go list -m all 当场看到：

1
2
3
4
5
6
$ go list -m all
example.com/main
example.com/A v1.2.0
example.com/B v1.2.0
example.com/C v1.4.0   # 取 v1.3 与 v1.4 的最大值
example.com/D v1.2.0

算法的全部，到此说尽：遍历依赖图，对每个模块收集所有对它的版本要求，取其中的最大值（即最高的下限）。没有回溯、没有约束求解器、没有 SAT,就是一遍图遍历取最大。写成伪代码，核心不过十几行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// MVS 构建列表（速写）：遍历依赖图，对每个模块取要求中的最高版本
func buildList(main module) map[path]version {
    selected := map[path]version{}        // 每个模块当前选中的版本
    queue := []module{main}               // 待访问的模块版本
    for len(queue) > 0 {
        m := queue[0]; queue = queue[1:]
        for _, req := range requires(m) { // 读 m 的 go.mod 里的 require
            if req.version > selected[req.path] { // 取最大下限
                selected[req.path] = req.version
                queue = append(queue, req)       // 该版本的子图也要并进来
            }
        }
    }
    return selected
}

它还有一个朴素的等价描述：把整张「粗构建列表」（图上一切可达的模块版本）算出来，再对每个模块只保留出现过的最高版本。两种说法选出的是同一组版本。

17.3.2 一条规则，四种操作

人们常误以为 MVS 只是「算一次构建列表」。Cox 在原文里其实把日常的版本操作都统一在了同一条规则之下，它们都是「改一下图，再跑一遍取最大」：

构建列表（build list）：默认操作，如上，从主模块遍历取最高要求。耗时随模块数线性增长。
升级全部（go get -u）：在跑 MVS 之前，给图里每条边都加上「指向各依赖最新版」的新边，再取最大。于是构建列表整体抬到最新。
升级单个（go get [email protected]）：只给主模块加一条指向目标版本的边，把该版本的子图并进来，再取最大。升一个模块，只会顺带升它确实需要的传递依赖，不会无端惊动别的。
降级单个（go get [email protected]）：反过来，从图里删掉所有高于目标的版本，并连带删掉那些「要求被删版本」的模块（它们可能与降后的依赖不兼容），再取最大。降级是升级的对偶。

四种操作共用一个内核：先按意图微调依赖图，再跑同一个「取最高下限」的遍历。这种「一条规则覆盖全部场景」的统一感，本身就是 MVS 简洁性的一部分。

17.3.3 为何「最小」反而更好

「选最低版本」听起来很怪,别的包管理器都倾向选最新的。但 MVS 选最小，恰恰带来三个关键好处，也正对应 17.1 列出的三个难题：

可重现（reproducible）：构建结果只取决于各模块 go.mod 里写明的要求,这些要求是固定的，所以选出的版本也是确定的。同一份 go.mod，今天和明年算出的构建列表完全一样，不会因为「今天 C 又发了个新版」而漂移。因此 Go 不需要 lock 文件来锁版本：go.mod 自身就是版本的唯一真相来源。go.sum 只负责校验下载内容的完整性（存的是各版本的加密哈希），它在版本选定之后才参与，不决定选哪个版本。这一点常被混淆，值得记牢：选版本看 go.mod，验内容看 go.sum。
高可信（high-fidelity）：选的是各模块作者明确测试过、明确要求过的版本，而非一个可能没人测过的、刚发布的最新版。库被编译时所对的依赖版本，正是其作者当初构建时所用的那一组，只有在被别处的更高要求「逼着」时才上抬。升级因此是显式的（你改 go.mod 才会升），而非构建时悄悄发生。Cargo、npm 这类「默认取最新可行版」的系统，恰恰相反：一次 update 就可能把从未一起测过的代码组合进来。
简单（simple）：一遍取最大，没有 NP-hard 的求解、没有求解器那种「换台机器、换个版本就给出不同解」的不可预测性。算法可预测，结果可解释,出了问题，你能用纸笔把它推回去。

Russ Cox 的洞见可以浓缩成一句：别人用复杂求解器去找「最新的可行版本」，而 MVS 用最简单的算法去找「最稳的可行版本」。 它把「要不要用新版本」这个决定权，从「构建工具的自动行为」交还给「开发者的显式选择」。这是一种深刻的价值观转向,确定性与可信，优先于自动取新。值得一提的是「最小」并不意味着「陈旧」：当你想要新版本，go get 一句话就升，工具会把「使用新版本」这个答案明明白白地还给你，由你决定何时接受。

17.3.4 一点理论：它为什么能这么快

愿意往下看的读者，这里给出 MVS 简单性的形式根据；不想深入的读者可以跳过本小节，主线不依赖它。一般的依赖求解问题（要在大量「版本兼容性」约束下找一组可行赋值）等价于布尔可满足性（boolean satisfiability, SAT），是 NP 完全的,这正是 npm、Cargo、pip、apt 背后那类求解器要面对的复杂度，最坏情况下需要指数级搜索，且解可能不唯一。

MVS 之所以躲开了这堵墙，是因为它把问题约束成了 SAT 里几个可在多项式时间内求解的子类。 Cox 证明：构建列表问题本身是 NL 完全（非确定对数空间）的，可经图可达性在线性时间内求解。升级操作对应的公式是 Horn 公式（每个子句至多一个正文字），其「令尽量少的模块为真」的最小解唯一;降级对应 对偶 Horn 公式（dual-Horn），其「令尽量少的模块为假」的最小解也唯一。线性时间、解唯一、可重现,三者同源于这个被刻意收窄的约束形态。

这也解释了 MVS 为何拒绝某些看似有用的扩展。比如「条件排除某版本」会在公式里引入析取（disjunction），破坏 Horn / 对偶 Horn 的形态，把问题打回 NP 完全。Go 因此只允许主模块的 go.mod 使用 exclude 与 replace（依赖自己说了不算），正是为了不让任何一方把这份「可在多项式时间内求解」的良好性质破坏掉。简单不是疏忽，是被严格守护的一项不变量。

17.3.5 极简背后的前提

MVS 能如此简单，归根到底是因为前面铺好的两块基石（17.2）。

其一，语义化版本的兼容性约定。MVS 假设「同一主版本内，高版本兼容低版本」，所以「取满足要求的最高下限」总是安全的,不会因为把某个依赖从 v1.3 抬到满足别处要求的 v1.4 而破坏兼容。若没有这条约定，「取最高下限」就可能选出一个不兼容的版本，整个算法的安全性便不复存在。

其二，语义化导入版本（semantic import versioning）。不兼容的主版本拥有不同的导入路径、是不同的包、能在同一次构建里共存，所以 MVS 永远不必在「两个不兼容版本里二选一」,那种最难、最容易引发求解爆炸的情况，已被路径规则在更早的阶段消解掉了。MVS 面对的，永远只是「同一兼容族里挑一个够高的」，而这正是取最大值能胜任的。

换言之，MVS 的极简，建立在「前面用强约束把难题提前解决了」之上,这正是 17.2 所说「复杂度前移」的回报：把难核搬到设计约定里，留给运行期算法的就只剩一句取最大。

17.3.6 别家怎么做：谱系与演进

把 MVS 放回整个领域看，它的位置相当独特。主流包管理器几乎清一色选择了「求解器 + 锁文件」的路线：npm、Yarn、Cargo、pip（新解析器）、Bundler、apt 都内置某种 SAT 或 PubGrub 式的求解器，默认在满足约束的前提下取最新可行版，再把求解结果固化进一份 lock 文件（package-lock.json、 Cargo.lock、Gemfile.lock）以求可重现。代价是双重的：manifest 与 lock 的二元冗余需要同步，以及求解器在边角情形下的不可预测与偶发的指数耗时。

Go 反其道而行：不取最新，而取「满足要求的最低」;不用求解器，而用一遍遍历;不要 lock 文件，因为 go.mod 加上确定性算法本身就够。可重现性从「把一次求解结果存下来」变成了「算法本身就确定」。这是两种关于依赖管理的不同哲学，而非简单的好坏之分：求解器路线换取了「自动贴近最新」的便利， MVS 路线换取了「可重现、可预测、可解释」的确定性。Cox 自己也承认，MVS 是用「牺牲一点自动取新」换来「极大简化」的一次审慎赌注。

演进上，MVS 由 Russ Cox 于 2018 年初在 vgo 系列文章中提出，随 Go 1.11（2018）以实验形态进入工具链，Go 1.16（2021）起默认开启模块模式。Go 1.17（2021）引入模块图剪枝（module graph pruning）：自此 go.mod 为每个「提供了被传递导入的包」的模块都写上显式 require（常带 // indirect 注记），使 go 命令无需加载整张传递依赖图就能跑 MVS，把大型项目的图遍历成本进一步压低。剪枝不改变 MVS 的选择语义，只让它在工程规模上更省。

至于前沿，依赖管理仍有未尽的张力。MVS 给出可重现与可预测，但它不主动告知「你依赖的某版本存在已知漏洞」,安全升级要靠 govulncheck 与生态工具（如 Dependabot）在 MVS 之外推动，由开发者显式改 go.mod 落地。如何在「确定性优先」与「及时获得安全修复」之间取得平衡，是这套体系仍在演化的方向；而「选最低」与「催升级」两股力量如何协作，也正是 Go 模块生态当下实践的活跃议题。

17.3.7 小结

MVS 是观察 Go 设计哲学的绝佳样本：面对一个别人用复杂手段（SAT 求解）解决的问题，Go 先用强约束（语义化导入版本）把问题的难核去掉，再用一个简单到极致的算法（取最大下限）收尾,既得到了可重现、可信、可预测的结果，又把实现与心智负担压到最低。简单不是能力的妥协，而是把复杂度安置到了正确位置的结果,这句贯穿全书的话，在 MVS 上得到了又一次印证。下一节（17.4）将回到历史现场，看 MVS 所代表的 vgo 路线，是如何在与 dep 的方案之争中胜出并成为今天的 Go 模块的。

延伸阅读的文献

Russ Cox. Minimal Version Selection. 2018. https://research.swtch.com/vgo-mvs （MVS 的原始设计文档：算法、四种操作、复杂度证明，与「为何最小更好」的完整论证）
The Go Authors. Go Modules Reference: Minimal version selection. https://go.dev/ref/mod#minimal-version-selection （官方规范，含 A/B/C/D 构建列表示例）
Russ Cox. Go & Versioning（vgo 系列总目）. 2018. https://research.swtch.com/vgo （语义化导入版本、最小版本选择、模块协议的整体设计）
The Go Authors. Module graph pruning（go.mod 与 Go 1.17 剪枝）. https://go.dev/ref/mod#graph-pruning （MVS 在大型依赖图上的工程优化）
Natalie Weizenbaum. PubGrub: Next-Generation Version Solving. 2018. https://medium.com/@nex3/pubgrub-2fb6470504f （求解器路线的代表，对照 MVS 的另一条道路）
本书 17.1 依赖管理的难点、17.2 语义化版本管理、 17.4 vgo 与 dep 之争.