工程与规模#

在 61A 课程中，重点聚焦于程序的正确性。而在 61B 课程中，工程程序成为核心，需要通过权衡从多个选项中做出选择。你所面对的项目规模更大，但仍需遵循诸多要求和规范，例如功能、运行时间等。从事小型项目与从事由你定义任务的大规模、面向设计的程序工作截然不同。学习这种差异的最佳方式是通过经验积累，本次讲座将提供一些示例以及轻量级理论来辅助理解。项目 3 正好为你提供了迎接大规模挑战的机会。

工程的限制

在其他学科领域，我们常常受限于不完美的材料。例如，化学工程师需要关注温度问题，材料科学家需要考虑材料的脆性，土木工程师则需担心混凝土的强度。然而，在计算机科学中，几十年前我们就解决了大部分基础材料限制的问题。以阿波罗任务为例，其总计算能力甚至不如你现在使用的手机。

软件的力量#

早期计算机的使用：早期计算机被用于有限的任务，功能有限，通常被设计来解决特定问题或执行特定计算任务。
ENIAC：作为第一台通用可编程计算机，ENIAC 的速度是当时其他任何设备的 1000 倍。它是一个重要的里程碑，展示了软件和编程的力量，使计算机能够执行广泛的任务，而不仅仅是单一的、预设的功能。
游戏介绍：1999 年发行的 Rollercoaster Tycoon 是一款早期游戏，玩家在游戏中设计游乐园。该游戏的代码 99% 是用汇编语言编写的，只有 1% 是用 C 语言编写的，这体现了当时为了达到性能要求而采取的编程实践，因为游戏被设计为在 66 MHz 的 Intel Pentium CPU 上运行，反映了当时硬件性能的限制以及软件开发者通过使用低级语言来优化性能的方式。
现代视频游戏的需求：如今，大多数视频游戏至少需要 3.5 GHz 的处理速度和 8 GB 的 RAM，而 1996 年时，普通计算机通常只有 8 MB 或 16 MB 的 RAM。平均而言，大多数软件产品并不需要我们今天所拥有的强大计算能力。

软件开发的限制：

单个程序员无法有效管理大型软件系统。
任何一名程序员只需要理解代码库的一部分。

复杂性的定义#

引用：“任何与软件系统结构相关的，使其难以理解和修改的因素” —— John Ousterhout，《软件设计哲学》。
复杂性增加的原因：随着程序变得更加功能丰富，它们的复杂性增加。我们的目标是保持软件简单。
为什么复杂系统需要更多努力来进行小的改进：
- 理解代码如何工作需要更长时间。
- 修复错误变得更加困难。
- 修改功能更加困难。
- 未知的未知：不清楚需要知道什么才能进行修改，这在大型代码库中很常见。

复杂性与功能性的关系

复杂性相对于功能性呈指数级增长。每增加一个新的功能，它都必须以各种方式与所有现有功能交互，形成所有可能的组合。

图示：展示了复杂性（纵轴）与功能性（横轴）之间的关系，曲线显示了随着功能性的增加，复杂性呈指数级增长。

实证证据（Empirical Proof）

以下是 Spotify 工程博客中关于他们软件方法的一个例子。他们拥有超过 10 亿行代码，其中 6000 万行用于生产环境，由数千个组件组成。

图示：图表显示了从 2015 年到 2021 年 Spotify 的工程师数量（绿色）和组件数量（紫色）的增长趋势。组件数量的显著增长反映了软件复杂性的增加。

管理复杂性#

复杂性分为两种：

不可避免（本质）的复杂性：由基本功能引起的固有的、不可避免的复杂性。
可避免的复杂性：我们可以通过选择来解决的复杂性。

针对可避免的复杂性，我们可以：

使代码更简单、更明显：例如在项目 1 中使用哨兵节点。
模块化：
- 抽象：根据某些规范，使用一个模块而无需理解其工作原理的能力。
- 接口：例如 HashMap 和 BSTMap 都是映射（Map）。

战术编程（Tactical Programming）

重点是快速让某事运作起来，利用变通方法。例如：包含许多嵌套 if 语句的代码，用于处理许多难以解释的独立情况。原型、概念验证利用战术编程，目标是展示某事理论上可以工作。然而：

在整体设计上花费的时间很少。
事情因变通方法而变得复杂，以使事情运作。
重构需要时间，可能意味着重新开始，例如要考虑项目 2 的运行时需求和构造函数的规划。
通常，由于缺乏时间，原型最终在现实世界中部署。

战略编程（Strategic Programming）

WARNING
随着时间的推移，你可能会在接下来的几个月、几年甚至几十年里面临越来越多关于流媒体、视频、音乐等方面的问题。当我们思考这些更大规模的项目时，可维护性对我们来说至关重要。

一种不同的编程形式，强调长期策略而非快速修复。目标是以规划时间为代价编写出优雅且能够良好工作的代码。代码应该是：

可维护的。
简单的。
面向未来的。61B 项目有截止日期，之后，你可以将其丢弃。

如果策略不够充分，在继续工作之前需要回到绘图板。这也是为什么我们的项目有 2A/2B 设计文档的原因。

Retool#

Retool 是一家帮助开发者构建内部工具的公司。我在 2022 年秋季作为软件工程师实习生在 Connect 团队工作。

关于我的工作背景，以下是公司的作用：

想象你制作了一个包含大量响应的调查（Google Sheets）。
你想构建一个仪表板来显示常见响应，这包括：
- 一个网站（前端）来显示结果。
- 一个服务器（后端）从资源（Google Sheets）获取数据。
- 两者的维护和开发。
相反，Retool 允许编写与拖放组件相关联的查询。
这种能力的大部分来自于能够连接到几乎任何 API 或数据库。API 是一个用于处理数据的接口，我们不关心其内部工作原理，只要我们可以使用其规范即可。

使用工作流（Case Workflow）

设计资源配置

免责声明：实现资源的方法是在我加入之前就已经决定的，但我需要理解并升级其功能。

目标是设计一个系统，让用户能够指定配置信息，这样 Retool 就可以代表用户连接到资源并检索信息。在我们之前的类比中，这将是一个 Google Sheets 的 URL。

最终的解决方案是构建一个名为 ResourceConfig 的东西，这是一种使用几个参数和常见模式来描述资源属性的方法，以生成输入。听起来很像一个接口！在设计配置时，这利用了模块化和明显性。大多数数据库都有类似的要求，例如主机（host）、端口（port）、名称（name）、连接选项（connection options）。对于没有模式的非数据库资源，我们可以使用属性来自定义元素以接受，从而覆盖默认数据库功能。

图片中还包含了两个数据库的图标，分别是 PostgreSQL 和 MySQL，这可能意味着 ResourceConfig 可以应用于多种数据库类型。

如何确保资源的有效性#

资源验证的重要性：并非所有资源都是有效的。这意味着在创建资源时，需要确保用户提供了所有必要的信息，否则不应允许创建该资源。
Java 的编译器错误预防：Java 语言通过编译器错误来防止编写明知故犯的坏代码。这是一种静态代码分析，确保代码在编译时就符合语言规范。
验证函数：资源配置中包含了一个验证函数，用于确保资源在创建时满足特定的验证条件。
通用验证：即使不知道资源的具体类型，也可以调用验证函数。这是因为验证函数是从接口中保证存在的，例如，任何列表（List）都可以使用 size 方法，无论它是什么类型的列表。

解答：

实施验证机制：在资源创建过程中，实施一个验证机制来检查用户是否提供了所有必要的信息。这可以通过在资源配置中包含一个验证函数来实现。
利用接口：利用接口来定义资源必须实现的方法，如验证函数。这样可以确保无论资源的具体类型如何，都可以调用这些方法来验证资源的有效性。
编译时检查：对于像 Java 这样的语言，可以利用编译器的错误检查来防止编写明知故犯的坏代码。这有助于在开发阶段就发现并修复潜在的问题。
运行时检查：除了编译时检查，还可以在运行时进行额外的检查，确保资源在实际使用前满足所有验证条件。

缺失字段#

当用户输入他们的凭据时，有一个选项可以通过一个示例请求来 测试连接。如果验证函数失败，这个选项会被禁用。我的目标是添加一种方法来跟踪缺失的字段，并对字段进行一些验证。这样，当创建资源失败时，用户可以被告知需要更改什么。

一个战略性问题：我们如何扩展功能以包含这一点？我们需要改变什么？

解决方案和重构#

解决方案是重新思考验证，将其视为通过缺失字段测试的过程。

参数将被循环检查，如果发现有缺失的，相应的“缺失字段”将被添加到列表中。
如果缺失字段的列表为空，则可以测试/创建资源！

字段可以升级以整合和泛化验证。例如，数据库的每个端口号都应该是数字。升级一个字段组件会更新所有使用该组件的地方，类似于对超类的修改会影响所有继承该功能的子类。

测试

在现实世界中进行测试非常重要！没有自动评分器可以用来对解决方案产生信心。

是否会显示正确的缺失字段？
- 对于“模式化”的数据库资源，我编写了一个工具，测试了所有可能的输入和输出组合。如果有模拟资源，这可以进一步扩展。
- 对于其他资源，选择了特定的测试用例并手动编写。

这种模式非常强大——更新工具可以更新所有资源的测试。资源（以及库/依赖项）会不断更新，有时伴随着破坏性变更。这是面向未来的代码。

问题#

我想找出我的项目中哪些版本包含了特定的更改，以比较一些指标，如采用率。其中一些版本很特别——它们已经被部署到现实世界中。你希望你的手机每天都有 5 或 6 次更新吗？苹果和谷歌会定期发布新版本，期间会有小的更改。

TIP
这里不得不提到金丝雀发布了。

Gradescope 只会在给定时间间隔内接收你的一些提交，而不是每一个。它们不会每次有新的提交被内部推送时就发布更新。

一些限制条件#

为了简化：

每次更改都是一个 Git 提交——当你使用 git commit -m "submitting lab1" 并使用 git push origin main 推送时生成的相同的 Git 提交。版本指的是给定分支上最近的 Git 提交。
可以轻松访问所有 Git 提交，这些提交可以在合理的时间内加载到任何计算机上。
提交非常多——缓存结果（即存储每次单独部署中包含哪些提交）是不可行的。
一旦做出更改，我们不会撤销或修改该更改（实际上，我们可以使用 git blame）。

手动拆分提交以包含在内是缓慢的，尤其是当有很多（大约数百万或数十亿个）提交时。

Git 图形说明#

考虑以下提交图，其中箭头指向提交的父项。其中一些是已部署的提交，用绿色标记。哪些已部署的提交包含了提交 C 的更改？C、D、G（只有绿色部分是发布状态的）。

一种方法#

考虑两种编程方法来实现这一目标：

逆向遍历存储父项的提交
- Git 设计用于告诉我们提交的父项（例如通过 git log），这是我们之前做过的。
正向遍历存储父项的提交
- 我们必须获取每一个“结束提交”，然后遍历所有父项，直到我们找到提交 C 中我们正在检查的更改。如果我们没有找到更改，我们只需要在足够逆向遍历以找到所有在提交 C 之前有时间戳的父项的提交后终止。

这种方法可以确保我们找到包含特定更改的所有已部署提交。

方法 2#

这种方法要求我们从给定提交时间之后的所有提交开始逆向工作。实现起来也有点更具挑战性：我们需要时间戳，并且可能有很多分支（每个分支都有自己的结束提交）。

解决方案的修改#

解决方案来自于我们存储数据的方式！我们通常在提交/父项关系中考虑 Git。例如：

commit 33f639487be34f7e6f28e1648834f5cf5c1d5475 4d8c496dcd54e254e0442236b0d17bc5df79a48d
Author: Aniruth Narayanan <aniruth.n@berkeley.edu>
Date:   Fri Sep 15 11:10:50 2023 -0700

如果边的方向被反转呢？那样的话，可以从提交开始向前进行广度优先搜索（BFS），以找到包含它的部署。这可以通过使用邻接表来实现，而不是只存储一个（或两个）父项，因为一个提交只能有一个父项（如果是合并提交，则有两个），但它可以有无限多的子项。

解决方案#

我们可以加入更多基于时间的优化来限制搜索，但这里是大致的思路：

以相反的顺序构建一个 Git 提交图，存储从提交到子提交列表的映射。
生成一组已部署的提交（与图分开）。为什么我可能想要使用集合而不是列表？运行时间！HashSet 给我提供了摊销的常数时间复杂度，而不是使用 LinkedList 或 ArrayList 来检查是否包含某个元素。
从输入提交开始进行广度优先搜索（BFS），并检查遍历到的提交是否在已部署的提交中。这里可能有多个输入提交，并且仅计算步骤 3。

这要快得多！不再需要手动搜索！明显且模块化！这个问题本身是一个更大项目中的子问题，这个大项目更容易解决。

总结和要点#

61B 概念和知识在现实世界场景中是适用的。
好的代码不仅仅是能工作的代码。
代码复杂性随着功能性的增加而增加，并带来维护挑战。
在你的类中实践良好的设计原则。
测试对于对你的代码有信心是必要的。
现实世界会给你模糊的问题和松散定义的限制条件；你有责任理解这些问题，然后在考虑权衡的情况下利用你的技能选择最佳解决方案。

附录#

敏捷开发

一文明白蓝绿部署、滚动部署、灰度发布、金丝雀发布