写点什么

iOS Pod Update 指数级变慢?看 Flutter 新一代仲裁算法 Pubgrub 如何解

  • 2021 年 12 月 02 日
  • 本文字数:9335 字

    阅读完需:约 31 分钟

iOS Pod Update 指数级变慢?看 Flutter 新一代仲裁算法 Pubgrub 如何解


作者:洪尉(洪茶)


如果你是一名 iOS 程序员,或者你对包管理技术感兴趣,推荐你阅读本文。你可以了解到 iOS 版本仲裁的底层原理、它的潜在性能风险 、以及如何预防 Pod update 的性能恶化,从而对 CocoaPods 有更深入的理解。此外,你还能了解到应用在 Flutter 的新一代的版本仲裁算法 Pubgrub,以及不同技术栈依赖管理策略的差异,从而对包管理技术领域有更全面的理解。

Pod Update 慢了 8 倍!!!

周五晚上,帅帅在 iOS 群求助:“我主工程跑 Pod update,一直卡着不动,有人遇到过吗?好奇怪!CPU 被 Ruby 进程占满,但没有任何网络请求。”小明看了帅帅的截图,回了一句:“我遇到过,这是正常的,CocoaPods 在做处理依赖”。帅帅只好无奈地接受了漫长的等待。


第二天早上,我看到昨晚群里的消息,觉得有点奇怪,于是打开终端尝试更新 Pod 环境,任务运行后一直卡了很久。


根据运行日志,Pod 更新总共耗时 872S,其中“版本仲裁”过程耗时 810 秒。下一步,我切到旧版本进行对比测试,旧版本"版本仲裁"耗时 120S,其他阶段时间差不多,也就是说新版本“版本仲裁”恶化验证,相比旧版本耗时涨了 8 倍!


接着我使用二方法对比各个 commit,最后发现其中一个 commit 导致了“版本仲裁”变慢,它增加了几个模块的依赖,这会改变主工程间接依赖的关系,从而改变 CocoaPods 版本仲裁的搜索顺序。因为 CocoaPods 输出的日志不包含版本仲裁的过程,需要进一部分析 Cocapods 的源码逻辑。


[CP cost] prepare :0.002s

[CP cost] resolve_dependencies :810.734s

[CP cost] download_dependencies :20.774s

...

[CP cost] Total :872.28s

分析版本仲裁的底层逻辑

打印依赖冲突的搜索路径

CocoaPods 版本仲裁功能基于 Molinillo 实现,需要分析和调试 Molinillo 源码。不了解依赖仲裁工具的读者请先查看文末《附录 2:依赖仲裁工具的职责》


首现下载 Molinillo 和 CocoaPods 源码到本地路径,然后修改 Gemfile 文件的依赖声明,将版本依赖修改为本地路径依赖。


gem 'molinillo', :path=>'/.../Molinillo'gem 'cocoapods', :path=>'/.../CocoaPods'
复制代码


版本仲裁的入口代码在 resolution.rb 文件的 Resolver 函数,为了分析仲裁时详细搜索路径,我将仲裁过程处理的包名和未处理的需求数量都通过日志打印出来。


def resolve  # 初始化依赖图和依赖栈  start_resolution  while state    break if !state.requirement && state.requirements.empty?    indicate_progress     # 打印当前未处理的需求的数量    puts "BT:requirements.length" + state.requirements.length    # 打印当前需求的模块名    puts "BT:requirement" + state.requirement    if state.respond_to?(:pop_possibility_state) # DependencyState      state.pop_possibility_state.tap do |s|        if s          states.push(s)          activated.tag(s)              end      end    end    # 处理栈顶的模块声明    process_topmost_state  end  # 遍历依赖图  resolve_activated_specsensure  end_resolutionend
复制代码


出现冲突后 Cocopod 会调用 create_conflict 函数处理,我同样将仲裁过程处理的包名和未处理的需求数量都打印出来。


def create_conflict(underlying_error = nil)  vertex = activated.vertex_named(name)  locked_requirement = locked_requirement_named(name)  requirements = {}  unless vertex.explicit_requirements.empty?    requirements[name_for_explicit_dependency_source] = vertex.explicit_requirements  end  requirements[name_for_locking_dependency_source] = [locked_requirement] if locked_requirement  vertex.incoming_edges.each do |edge|    (requirements[edge.origin.payload.latest_version] ||= []).unshift(edge.requirement)  end
activated_by_name = {} activated.each { |v| activated_by_name[v.name] = v.payload.latest_version if v.payload } # 打印当前冲突的模块名 puts "BT:conflict_name" + name # 打印当前未处理的冲突 puts "BT:conflict-requirements" puts requirements conflicts[name] = Conflict.new( requirement, requirements, vertex.payload && vertex.payload.latest_version, possibility, locked_requirement, requirement_trees, activated_by_name, underlying_error )end
复制代码

对比恶化前后的差异

接下来,我分别在新版本 7.42.0 和旧版本 7.41.0 执行 Pod 更新,然后对比两个版本仲裁过程的日志。根据实验结果,耗时主要集中在 Triver 的版本仲裁


进行 Triver 仲裁时,Molinillo 先选择最新版本 1.1.18.2,因为 1.1.18.2 会引发冲突,Molinillo 会从高版本开始逐步向下选择另一个版本,最终一直遍历到 1.0.14.23 才没有冲突。最终 7.41.0 版本环境的 Triver 版本仲裁总共用时 7 分钟;7.42.0 版本环境的 Triver 版本仲裁总共用时 1 分钟。


指数级恶化的根本原因

恶化的原因是 Triver/API 引发了依赖冲突。依赖图中有一个模块 Triver,它是被其他模块间接依赖的。Triver 有多个 subspec,其中有一个 subspec 是 Triver/API 。Triver/API 依赖了 MtopSDK 模块,并声明了 MtopSDK 的最小版本。Triver 最新的版本是 1.1.18.2,它需要依赖 MtopSDK 2.5.1.0 以上的版本,而主工程 Podfile 声明 MtopSDK 为 2.2.2.3 的固定版本,因此出现了依赖冲突。

仲裁变慢的 3 个因素


依赖冲突导致 56 次回溯检查


Triver 前面 56 个版本都会导致 MtopSDK 的版本冲突,那么 Molinillor 要进行 56 次回溯才能仲裁成功。


Molinillor 进行版本仲裁时,会优先取新版本。如果新版本不满足条件,会按顺序递减选择低版本,直到版本约束能匹配为止。Molinillor 开始递减匹配 Triver 的低版本,一直找到第 56 个版本才符合条件。Triver 的第 56 个版本是 1.0.14.23,它依赖 MtopSDK 的最小版本是 2.0.1.3,这个约束和 Podfile 声明的 2.2.2.3 版本不冲突,因此 Triver 的仲裁的结果是 1.0.14.23。


CocoaPods Subspec 机制导致跨层级回溯


Triver/API 是 Subspec 描述的,它是 Triver 的一个子模块,Triver/API 的版本由 Triver 决定。当 Triver/API 产生冲突时,依赖图会先回溯到上一层 Triver,重新选择另一个 Triver 的版本。


DFS 遍历导致回溯时大量重复检查


Molinillor 使用的遍历方式是 DFS(深度优先算法)。Molinillor 会构建一个依赖图,依赖图的每个节点代表一个模块。它会用 DFS 遍历依赖图的每个节点,对所有模块进行版本仲裁。当 Triver/API 产生冲突时,依赖图会先回溯到上一层 Triver,重新选择 Triver 的版本。但 Triver 有 8 个子模块,如果 Triver/API 子模块遍历排序靠后,就需要等待其它子模块完成深度遍历。有些子模块比如 Triver/AppContainer,它依赖链路很长,深度遍历耗时会更久。


恶化前后回溯复杂度对比


Triver/API 版本仲裁的时间复杂度可以表示为 56mO(n),m 是 Triver 遍历子模块时 Triver/API 的遍历排序,n 是 Triver 子模块依赖树的节点数。


根据遍历过程的日志,恶化前 Triver/API 遍历排序是第 2,排在 Triver/ZCache 之后。恶化后 Triver/API 遍历排序是第 5,排在 Triver/AppContainer 、Triver/ZCache、Triver/TinyShop、Triver/Monitor 之后。


恶化前每次回溯的节点数是 6 个,恶化后每次回溯的节点数量 24 个,Triver 的仲裁时间也从 1 分钟涨到 8 分钟


优化方法

优化方案是在 Podfile 声明 Triver 固定版本,声明固定版本的模块不需要进行版本仲裁,从而避免依赖冲突后反复回溯搜索耗费大量时间。

iOS 版本仲裁算法 Molinillo

包管理器是现代编程语言一个重要的组成部分。包管理器的核心就是版本仲裁算法,即怎样确保每个安装包的版本可以满足所有的依赖需求。包管理器会先获取主工程直接依赖和传递依赖的所有包,然后找到所有依赖都满足的版本组合。


包管理器的仲裁策略差异很大,不过通仲裁策略都有各自的优缺点。js 很少几乎没有依赖冲突,但有有著名的 node_module 依赖地狱,Android 依赖编译不过,但运行时会各种莫名奇怪的 Crash,iOS 经常被嘲笑因为依赖问题编译不过,但稳定性会更好。具体可以查看文末 《附录 1:不同语言版本仲裁策略的差异》


iOS 的包管理器是 Cocoapods,Cocoapods 的版本仲裁功能是 Molinillo 实现的,Molinillo 是老一代的版本仲裁算法,PubGrub 则是新一代的版本仲裁算法。老一代的版本仲裁算法有两个明显缺点,第一个缺点是版本冲突遍历效率差,另一个缺点是仲裁失败的错误日志不清晰。本文开头的案例就是踩到第一个问题的坑。


Molinillo 算法的核心是基于回溯 (Backtracking) 和 向前检查 (forward checking),如果有兴趣了解 Molinillo 的代码设计可以查看Molinillo官方介绍,或者这篇源码解析文章


下面介绍 Molinillo 仲裁的核心逻辑。如果以主工程作为根节点,所有依赖加起来会形成一个依赖图。每个结点都代表一个包,每个包有不同的版本,同一个包的不同版本声明的依赖可能不一样。Molinillo 使用深度遍历法遍历依赖图的每个包,每个包只选择一个版本。因为每个版本的依赖会有差异,所以每次选择都代表走了一条路。(如下图所示)



正如上文所分析的仲裁变慢案例,遍历过程中,Molinillo 会构建一个 版本组合(a 1.0,b1.1,.....)。在依赖图的不同结点里,如果出现了两个相悖的依赖约束(a > 2.2,a = 1.8),就会产生依赖冲突。


根据下图所示,当子节点 C 出现依赖冲突时,Molinillo 会回溯到它的父节点 B,重新选择父结点 B 的另一个版本,然后重新遍历它的子节点。如果父结点有许多子节点,深度遍历其他子节点也带来 M 倍耗时,M 是深度遍历 B 子节点经过的所有节点数量。 父节点 B 的新版本可能声明了子节点 C 新的约束条件,这样就解决了子节点 C 的依赖冲突问题。


然而,有时候会出现父结点结点多个版本都会导致子节点冲突,此时 Molinillo 会不断重选父结点的版本。这会带来 N 倍工作,N 是选择的父节点版本数量。 最不幸的情况下,Molinillo 选择父节点 B 的所有可用版本,后续子节点 C 都会有冲突。此时 Molinillo 会继续回溯到父节点 B 的父父节点 A,重新选择父父节点 A 的新版本,再重新遍历它的子节点。此时 Molinillo 可能会重复进入死胡同,比如之前选过 B 1.3,现在又重新选择一次。


新一代版本仲裁算法 Pubgrub

包管理版本仲裁是一个 NP-hard 问题,NP-hard 问题表示可能没有算法可以在所有情况下有效解决它。上文介绍了 iOS 采用的 Molinillo 算法,它在依赖冲突是处理效率会比较低。Pubgrub 的出现就是为了解决仲裁效率低的问题,它在老一代版本仲裁的基础上进行优化,可以大幅提升版本冲突时的处理效率,Pubgrub 也被称为新一代版本仲裁算法。


Pubgrub 提出了全新的冲突解决思路,想要了解所有细节的读者可以阅读作者的文章或者Dart-lang的文档下面是我会解读 Pubgrub 核心的逻辑。


遇到版本冲突时,Pubgrub 会使用算法推导出版本冲突的根本原因,它用 Incompatibility(不兼容)来表示。上文有介绍过,版本冲突时仲裁工具会一直回溯父结点,然后重新遍历原走过的路径。重新遍历时,Pubgrub 会利用“Incompatibility”过滤掉会存在冲突的路径,从而避免再次进入死胡同。我们可以理解为 Pubgrub 会利用冲突的关系,推导出一组不兼容的版本约束,然后就利用这个不兼容约束进行剪枝。


下面介绍 Pubgrub 优化的算法细节。Pubgrub 将包之间的版本依赖关系抽象为 Term 和 Incompatibility 两个要素,Term 表示一个包的版本约束,Incompatibility 表示一组不兼容的关系。抽象为要素以后,Pubgrub 就可以方便地进行数学公式推导,从而把包之间复杂的依赖关系归纳为简单的不兼容组合。

Term

Pubgrub 运行的基本单元是一个 Term,Term 代表一个关于包的声明,声明给定的包版本可能是对的或错的。例如,如果我们选择 foo 1.2.3 ,那么 foo ^1.0.0 就是真的 Term;如果我们选择 foo 2.3.4 ,那么 foo ^1.0.0 就是假的 Term。相反的,如果选择了 foo 1.2.3 ,那么 not foo ^1.0.0 则为假,如果选择了 foo 2.3.4 或者根本没有选择 foo 版本,那 not foo ^1.0.0 则为真。


为了表示一组 Term 和一个 Term 的关系,Pubgrub 定义了 satisfies(满足)、contradicts(矛盾)、inconclusive(不确定是否满足)三个概念。


  • satisfies: 给定一组 Terms S 和一个 Term t,当且仅当 S 是 t 的子集时,S 和 t 的关系可以表示为 S satisfies t,例如 {foo >=1.0.0, foo <2.0.0} satisfies foo ^1.0.0。

  • contradicts: 给定一组 Terms S 和一个 Term t,当且仅当 S 和 t 完全不相交时,S 和 t 的关系可以表示为 S contradicts t ,例如 foo ^1.5.0 contradicts not foo ^1.0.0 。

  • inconclusive:给定一组 Terms S 和一个 Term t,当 S 是 t 的真超集时,S 和 t 的关系可以表示为 S inconclusive for t ,例如 foo ^1.0.0 inconclusive for foo ^1.5.0 。


Terms 也可以通过集合符合来表示并集:foo ^1.0.0 ∪ foo ^2.0.0 is foo >=1.0.0 <3.0.0.交集:foo >=1.0.0 ∩ not foo >=2.0.0 is foo ^1.0.0.差集:foo ^1.0.0 \ foo ^1.5.0 is foo >=1.0.0 <1.5.0 备注:以上采用 ISO 31-11 标准符号进行集合操作

Incompatibility

Pubgrub 定义了一个概念“incompatibility”,“incompatibility”表示一组不能完全成立的 Terms。


例如, incompatibility {foo ^1.0.0, bar ^2.0.0} 表示 foo ^1.0.0 和 bar ^2.0.0 不兼容, 所以如果版本仲裁得到的解决方案里包含了 foo 1.1.0 和 bar 2.0.2,那这个解决方案是无效的。


上文介绍了,一组 Terms 和一个 Term 的关系有 satisfies、contradicts、inconclusive for。incompatibility 表示一组不能完全成立的 Terms。“terms”和“incompatibility”有 4 个种关系。给定一个 incompatibility I,一组 terms S。如果 S 满足 I 中的每一项,我们说 S satisfies I。如果 S 至少与 I 中的一项矛盾,那么 S 与 I contradicts。如果 S 满足除 I 项中除了仅有一项之外的所有项,并且对于仅有的这一项是不确定的,我们说 S“almost satisfies”I,我们仅有的这一项为“unsatisfied term”。


incompatibility 的来源是包的依赖声明。例如“foo ^1.0.0 依赖于 bar ^2.0.0”是一组依赖关系,它表示为 incompatibility 就是 {foo ^1.0.0, not bar ^2.0.0}。又例如主工程声明了依赖 foo <1.3.0 ,它表示为 incompatibility 就是 {not foo <1.3.0} 。以上的 incompatibility 被称为“external incompatibility”,它们来自于 root 工程或包的依赖描述。


Pubgrub 遍历工程的依赖图会遇到海量的依赖关系,这些依赖关系会转化为大量的“external incompatibility”。如果“external incompatibility”以离散的个体存在,并不能帮组 Pubgrub 提高仲裁过程选择版本的效率。反之,如果可以将离散的“external incompatibility”聚合成一个 incompatibility 组合,Pubgrub 就可以快速判断哪些包的版本会产生冲突。


冲突解决期间,Pubgrub 会利用基础等式和集合公式,将导致版本冲突的两个 incompatibility 推导为一个新的 incompatibility,聚合出来的 incompatibility 被称为“derived(派生的) incompatibility”,推导出来的“derived incompatibility”会做为包版本选择的判断依据。


解决冲突期间,Pubgrub 会进行回溯并重新搜索状态空间,Pubgrub 可以利用“terms”和“incompatibility”的关系,判断当前搜索路径是否有问题,从而避免重复地搜索状态空间里同一个死胡同。

Conflict Resolution

Pubgrub 会维护一个版本组合数组,记录遍历过程选择的每个包和版本,仲裁成功后这个数组就是解决方案。遍历时,Pubgrub 会校验当前包版本组合是否有不兼容,如果存在不兼容,说明继续遍历会进入死胡同,放弃继续遍历下一级节点,重新选择当前包的版本,直到没有不兼容为止。遍历完成后,当前包版本组合作为最终的解决方案。


这个算法可以避免仲裁工具重复走进同一个死胡同,大幅提高版本冲突时搜索的效率。这就像地图软件提供的封路反馈功能,用户通过反馈互通信息,向地图软件反馈某段路走不通。当其用户再导航时,导航算法会自动避开这条死胡同。


下面介绍 Pubgrub 推导不兼容性的算法,要理解它的推导过程需要掌握逻辑学的基础知识。


它使用一个基础等式:如果给定任何 “(a or b) and (not a or c)” 为真,那么可以推导出 “(b or c)” 也为真。然后将这个逻辑等式使用“不兼容性”概念来描述:如果给定任何“不兼容性{t,q} and 不兼容性{not t,r}” 为真,那么可以推导出 “不兼容性{q,r} 为真”。


在版本仲裁场景中,我们可以将 t、q、r 理解为是某个包的版本约束。实际场景中,包的约束经常有差异,比如“包 A > 1.0”和“包 A > 2.0”,我们可以将同一个包不同的约束称为 t1、t2。


于是可以得到下面等式:给定任何“不兼容性{t1,q} and 不兼容性{t2,r}” 为真,那么可以推导出 “不兼容性{q,r,t1 ∪ t2} 为真”。如果加一个条件 "t1 不是 t2 的超集“,那就可以将结论简化为“不兼容性{q,r} 为真”。


举个例子:



上图是一个版本冲突的例子。root 工程声明了模块 M 的版本约束,传递依赖链中,模块 C 也声明的“模块 M”的版本约束。下面介绍一下 Pubgrub 的算法是怎样避免二次进入死胡同。


  • 根据上图得到依赖条件 1:root 工程 依赖 模块 M=2.0。“依赖条件 1”可以转化为 不兼容性 1 {not “模块 M=2.0”, root}

  • 根据上图得到依赖条件 2:“模块 C 小于等于 3.2 的版本都依赖”模块 M<1.5”。“依赖条件 2”可以转化为 不兼容性{not “模块 M<1.5”,模块 C<=3.2},再推导为 不兼容性 2{模块 M>=1.5 ,模块 C<=3.2}

  • 根据上图得到依赖条件 3:“模块 B 1.3”依赖于”模块 C<3.2“,可以转化为 不兼容性{not “模块 C<3.2”,模块 B=1.3} ,再推导为 不兼容性 3{模块 C>3.2,模块 B=1.3}


根据基础等式,可以将 不兼容性 1 和不兼容性 2 推导为“不兼容性{not ”模块 M=2.0“ ∪ 模块 M>=1.5,root,模块 C<=3.2}”,再简化得到 不兼容性 4{root,模块 C<=3.2}


已知 不兼容性 4 和不兼容性 3 ,根据基础等式可以推导出不兼容性{模块 C>3.2 ∪ 模块 C>3.2,root,模块 B=1.3},简化得到=> 不兼容性 5{root,模块 B=1.3}


有了 不兼容性 5{root,模块 B=1.3} ,Pubgrub 重新搜索路径时就不会选择模块 B 的 1.3 版本,从避免第二次走进死胡同。

iOS 包管理最佳实践

1、主工程 Podfile 管理中间件和三方库


Triver 是阿里集团的一个中间件,如果中间件和三库在 Podfile 声明具体版本,就可以减轻 Molinillo 的仲裁的压力,使得版本仲裁速度保持稳定。


2、内部模块只声明依赖不声明版本约束


大型项目的功能复杂,壳工程会依赖大量内部和外部的 SDK。alibaba iOS 工程总共有 140 的内部模块,300 多个集团或第三方的模块。团队维护内部模块,模块之间相依赖会比较多。如果模块的依赖过多限制版本范围,很容易造成版本冲突。最佳实践是模块依赖不允许声明固定版本,只允许声明大于某个版本。


3、主工程 Podfile 声明所有模块的固定版本


很多项目习惯声明 module>xxx 版本,这样每次都会下载最新的版本。我们很难保证三方库模块管理非常严格,每次都是兼容性升级,像这样频繁升级容易工程环境会稳定。后果也很严重,轻则工程编译不过,重则出现线上问题。


除此之外,为了提升编译速度,iOS 的模块通常会做成静态库,壳工程构建时不需要编译模块的代码,只需要链接静态库。OC 的二进制格式是 Mach-O,Mach-O 文件只记录类的符号,不记录函数的符号。如果模块 A 调用了模块 B 的函数 X,函数 X 被删掉后,主工程工程构建不会报错,但运行时会 crash。因此,如果一个模块声明了模糊的版本限定,版本会被自动升级,如果升级了不兼容的版本,会带来不确定的风险。

总结

本文介绍了 Cocopods 版本仲裁的问题,当开发者更新 cocopods 环境时,如果出现版本冲突,Cocopods 版本仲裁的速度会很慢。当某个包声明的版本约束和其他节点冲突,Cocopods 回溯到上父节点的包,然后 DFS 搜索父节点所有可用版本,直到绕开子节点的版本冲突冲突为止。如果父节点的可用版本都不符合条件,还需要继续回溯到父节点的父节点,依次类推直到搜索完依赖图的所有可能性。大型工程的依赖图异常复杂,包的数量有四五百个,每个包有几十个版本,每个版本的差异又很大,遇到复杂的场景时回溯搜索会很慢。


基于此,本文还介绍了新一代的版本仲裁算法 Pubgrub,Pubgrub 的出现就是为了解决上一代版本仲裁算法效率低的问题。Pubgrub 目前已经应用到 Dart 和 SwiftPM 的包管理中,Pubgrub 作者设计了全新的算法,可以有效避免依赖检索过程重复进入死胡同,进而大幅度提升版本仲裁的效率。iOS 开发者会经常更新 cocopods,如果这个过程很慢,会严重损害团队的开发体验和开发效率。


最后,本文介绍了一种包管理策略,使用这种策略可以减轻 Cocopods 版本仲裁的工作,从而避免陷入版本冲突的死胡同里。这个策略有三步,第一步是禁止在团队私有 SDK 声明依赖包的版本约束;第二步是主工程的 Podfile 文件声明所有的依赖包版本约束;第三步是 Podfile 只声明包的固定版本,不声明包区间版本。

附录 1:不同语言版本仲裁策略的差异

iOS 的包管理工具是 Cocopods,Cocopods 采用严格模式,不允许任何形式的版本冲突。Cocopods 发现依赖冲突立马报错并停止下载模块,等待开发者解决冲突后才能重新继续。这种策略可以规避运行时的风险。但它却增加了工程管理的成本,如果工程的版本声明混乱,编译时很容易报错。


Android 的包管理工具是 Maven,Maven 对依赖冲突有更高的容忍度。Maven 工程如果出现依赖冲突,它会根据最小路径的方式选择模块版本.这种策略可以避免编译时的错误,开发不需要花时间处理依赖冲突。但它增加了运行时的稳定性风险,运行时可能会有执行到不存在的符号,最后报 NoSuchMethodError 错误。


下图是 Mave 的最小路径原则策略:



前端常用的包管理工具是 npm,前端开发从来不会遇到包冲突的问题。npm 利用语言特性实现依赖包隔离,这是一种冗余换取稳定的策略。当 npm 工程里出现传递依赖冲突时,各个节点会保留自己依赖的版本。这种策略可以避免依赖仲裁的冲突错误,运行时稳定性也高。但它会导致依赖地狱,包大小也会膨胀。


下图是 npm 的依赖冗余策略:


附录 2:依赖仲裁工具的职责

各技术栈包管理工具的依赖仲裁算法不一样,Cocopod 使用 Molinillo 进行依赖仲裁,Dart 和 SwiftPM 用使用的是 PubGrub。要了解依赖仲裁变慢的具体原因,需要分析 Molinillo 的源码。在此之前,先简单回顾一下依赖仲裁工具的职责。依赖仲裁工具主要有两个职责,一个是判断依赖循环,另一个是找到没有冲突的模块版本组合。


判断依赖循环


包管理工具无法处理带有循环依赖的工程,所以它需要判断工程中是否存在循环会依赖。包管理工具会对工程依赖做数学建模,建模后会形成一个依赖图,然后判断这个依赖图是否 DAG。



找到没有冲突的依赖组合


举个简单的例子例子,App 声明模块 M 是 2.6 版本,然后又通过模块 A 间接依赖了模块 B。因为模块 B 没有声明具体版本,Cocoapods 选择了模块 B2.0 版本,但模块 B 的 2.0 版本依赖 3.2 以上的模块 M 版本,这个签名 App 声明的 2.6 版本冲突了,因此不能选择模块 B3.2 版本。Cocoapods 会重新选择模块 B 其他版本,最后发现模块 B1.0 版本没有冲突。



参考材料

  • Pubgrub 官方文档:https://github.com/dart-lang/pub/blob/master/doc/solver.md

  • Molinillo 官方文档:https://github.com/CocoaPods/Molinillo/blob/master/ARCHITECTURE.md

  • Molinillo 依赖校验源码解析:https://looseyi.github.io/post/sourcecode-cocoapods/07-cocoapods-molinillo/

  • 常用集合符号:https://www.shuxuele.com/sets/symbols.html


关注【阿里巴巴移动技术】微信公众号,每周 3 篇移动技术实践 &干货给你思考!

发布于: 2021 年 12 月 02 日阅读数: 7
用户头像

还未添加个人签名 2018.07.07 加入

阿里巴巴移动&终端技术官方账号。

评论

发布
暂无评论
iOS Pod Update 指数级变慢?看 Flutter 新一代仲裁算法 Pubgrub 如何解