| 2023-05-01
规模化编程
在谷歌，成千上万的软件工程师共同贡献于一个拥有数十亿行代码的单一代码库，该库储存在一个名为 Piper 的系统中，包含共享库、生产服务、实验性程序、诊断和调试工具——基本上包含所有与代码有关的东西。
所有的开发人员几乎可以查看所有的代码（仅有极少数代码才有权限设置）。这种开放的管理方式非常强大。
例如，当一个工程师不确定如何使用某个库（lib）时，他可以通过搜索找到使用这个库的示例代码，而且这个示例代码通常都是生产环境正在使用的代码。另外，这种开放方式允许热心人对整个库中执行重要的更新，无论是迁移到更新的 API ，还是遵循诸如 Python 3 或 Go 泛型之类的语言的更新。
然而，代码并非免费的：它的生产成本很高，而且还需要花费一定的工程时间来维护。如果想避免以后更大的修改成本，这种维护工作很难忽视。
但是，如果让需要维护的代码能更少呢？这么多行的代码真的有必要吗？
规模化代码删除
任何大型项目都会积累死代码：总会有一些不再需要的模块，或者一些早期开发中使用但已经多年未运行的程序。事实上，整个项目被创建、一段时间运行后，就不再有用了。有时它们会被清理掉，但清理需要时间和精力，而且往往不容易证明它们值得这种投资。
然而，这些未被删除的死代码仍会产生成本：自动化测试系统并不知道应该停止运行那些对死代码的自动化测试用例；执行大规模迁移任务（如升级到 python 3 ）的人可能并不知道迁移这些代码毫无意义，因为它们根本不会运行。
要是能够自动清理死代码，那多好呀？
几年前，在谷歌苏黎世工程生产力团队的年度黑客马拉松活动中，人们开始思考这个问题。
Sensenmann 项目（以德语中代表死亡化身的词汇命名）非常成功。它每周提交超过 1000 个删除变更清单，并且迄今已经删除了谷歌所有C++代码的近 5 %。
它的目标很简单（至少在原理上是这样的）：自动识别死代码，并发送代码审查请求（“变更清单”）以将其删除。
什么可以删除？
Google 的构建系统 Blaze（你可以认为，它是开源项目 Bazel 的谷歌内部版本）可以帮确认这一点。因为bazel 是通过一致且可访问的方式来表示二进制目标、库、测试、源文件等之间的依赖关系的。所以，通过 Bazel 能够构建出一个完整依赖关系图。这就能找到未链接到任何二进制文件的库，并提出删除建议。
然而，这只是这个问题中的一小部分。还有一些问题要解决。比如，那些二进制文件呢？所有一次性的数据迁移程序，以及针对废弃系统的诊断工具？如果它们不被删除，那么它们所依赖的所有库也将被保留。
了解程序是否有用的唯一真正方法是检查它们是否被运行，因此对于内部二进制文件（在 Google 的数据中心或员工使用的工作站上运行的程序）来说，当它运行时，就会记录一个日志条目，记录一下执行时间和具体的二进制文件名。通过聚合这些数据，就可以获得 Google 内部每个二进制文件的存活信号。如果一个程序很长时间没有使用，就可以试发送一个删除变更列表。
什么不可以删除？
当然，也有例外情况：有些程序代码只是作为如何使用 API 的示例；有些程序是没有办法生成日志信号的，因为它们并不是二进制方式执行的。当然，还有很多其他例外情况。删除这些代码可能会带来负面影响。
所以，，拥有一个白名单列表系统非常重要，这样可以标记例外情况，避免向人们发送不必要的变更列表。
考虑下面这个简单的情况。有两个二进制文件，每个二进制文件都依赖于自己的库，以及一个第三个共享库。忽略源文件和其他依赖项，我们可以得到这样的结构：
如果 main1 是活跃的程序，而 main2 最后一次使用是一年以前，我们可以通过构建树传播活跃信号，标记 main1 以及它所依赖的所有内容为活跃状态。剩下的可以被删除；由于 main2 依赖于 lib2 ，我们希望在同一次更改中删除这两个目标：
然而，真正的生产代码是有对应的单元测试的，这些单元测试的构建任务是依赖于它所测试的生产代码的。这让上面的图变得复杂了:
尽管 lib2 从未被“真正”执行，但是，测试基础设施将运行所有这些测试，包括 lib2_test 。这意味着我们无法将测试运行视为“活跃”信号：如果这样做，我们会认为 lib2_test 也是活跃的，这将使 lib2 也会永远保留。这样一来，我们就只能清理那些未经测试的代码了，这会严重影响我们的努力成果。
我们真正想要的是，每个测试都与它测试的库共享命运。我们可以通过使库和它的测试相互依赖来实现这一点，从而在图中创建循环：
这将每个库及其测试转换为一个强连通分量。我们可以采用之前相同的技术，标记“存活”的节点，然后寻找需要删除的“死亡”节点集合，可以使用 Tarjan 的强连通分量算法来处理循环。
Tarjan算法（Tarjan’s algorithm）是一种在有向图中寻找强连通分量的常见算法，由美国计算机科学家 Robert Tarjan 于1972年提出。该算法通过深度优先搜索遍历图，利用栈（stack）来保存搜索过程中的节点，根据访问时间和在栈中的情况，判断节点所在的强连通分量。Tarjan算法的时间复杂度为O(|V|+|E|)，其中|V|和|E|分别是图的顶点数和边数。
然而，在考虑测试与它们所测试的库之间的关系时，情况可能并不总是那么简单。在上面的例子中，有一个简单的命名约定可以让我们将测试与库进行匹配，但很遗憾，我们不能在一般情况下依赖这种启发式方法，因为这并不总是成立。
考虑以下两种情况：
在左边的例子中，我们有一个 LZW 压缩算法的实现，作为单独的压缩和解压缩库。测试实际上测试了它们两个，以确保数据在被压缩和解压缩后不会出现损坏。在右边，我们有一个 web_test，测试我们的 web 服务器库；它使用一个 URL 编码库来支持，但实际上并没有测试 URL 编码本身。在左边，我们希望将 LZW 测试和两个 LZW 库视为一个连接的组件，但在右边，我们希望排除 URL 编码器，并将 web_test 和 web_lib 视为连接的组件。
尽管需要不同的处理，但这两种情况具有相同的结构。在实践中，我们可以鼓励工程师将像 url_encoder_lib 这样的库标记为“仅用于测试”（即仅用于支持单元测试），这有助于在 web-test 情况下；否则，我们目前的方法是使用测试和库名称之间的编辑距离来选择最可能与给定测试相匹配的库。能够识别像 LZW 示例这样的情况，即一个测试和两个库，可能涉及处理测试覆盖数据，并且尚未被探索。
专注于用户…
虽然死代码删除的最终受益者是软件工程师自己，其中许多人感激有助于保持项目整洁的任何帮助，但并不是每个人都喜欢接收自动化变更列表，尝试删除他们编写的代码。这就是项目中社交工程方面的重要性，它与软件工程一样重要。
自动代码删除对许多工程师来说是一个陌生的概念，就像 20 年前引入单元测试一样，许多人都会抵制它。改变人们的想法需要时间和精力，还需要仔细的沟通。
Sensenmann 的沟通策略有三个主要部分。首要的是变更说明，因为它们是审核人员首先看到的。它们必须简洁明了，但必须提供足够的背景，以便所有审阅人员都能做出判断。这是一个难以平衡的问题：如果太短，许多人将找不到他们所需的信息；如果太长，就会得到一堵没有人愿意阅读的大量文本。支持文件和常见问题解答的标记良好的链接可以在这方面提供帮助。
第二部分是支持文件。简洁和清晰的措辞在这里也是至关重要的，良好的可导航结构也是必不可少的。不同的人需要不同的信息：一些人需要保证在源代码控制系统中，删除可以回滚；有些人需要指导如何最好地处理错误的变更，例如修复对构建系统的误用。通过仔细的思考和用户反馈的迭代，支持文件可以成为一个有用的资源。
第三部分是处理用户反馈。有时这可能是最困难的部分：反馈更频繁地是负面的而不是正面的，有时需要头脑冷静和良好的外交手腕。然而，接受这样的反馈是改进系统的最佳方法，让用户更满意，从而避免将来出现负面反馈。
编辑距离（Edit distance），也称 Levenshtein 距离，是衡量两个字符串差异的度量标准。它是指将一个字符串转换为另一个字符串所需的最少编辑操作次数，包括插入、删除、替换三种基本操作。
例如，字符串"cat"和"hat"之间的编辑距离是1，因为只需要将第一个字符串的"c"替换为"h"即可。又如，字符串"book"和"books"之间的编辑距离是1，因为只需要在第一个字符串的结尾添加一个"s"即可。
编辑距离在自然语言处理、数据挖掘和计算机科学等领域中被广泛应用，例如在拼写检查、搜索引擎、机器翻译和基因序列比对等方面。
向前、向上发展
自动删除代码可能听起来很奇怪：编写代码成本高昂，通常被认为是一项资产。但是，未使用的代码会浪费时间和精力，无论是在维护还是清理它。一旦代码库达到一定规模，就开始投入工程时间自动化清理过程。在 Google 的规模下，据估计，自动代码删除已经为公司节省了数十倍的维护成本。
实现这一过程需要解决技术和社会问题。虽然在这两个方面都取得了很多进展，但仍未完全解决。随着改进的不断推进，删除的接受度也在增加，自动删除变得越来越有影响力。这种投资并不适用于每个地方，但如果你有一个巨大的单一代码库，也许这也是值得考虑的。至少在 Google，将 C++ 维护负担减少 5％ 是一大胜利。
原文作者： Phil Norman 原文链接：Sensenmann: Code Deletion at Scale 发表时间： Friday, April 28, 2023