20,961 讀數

打破程序执行中的公理

经过 Nikita Vetoshkin9m2023/10/24

太長; 讀書

作者是一位经验丰富的软件工程师，分享了他们从顺序代码到分布式系统的旅程的见解。他们强调，采用非序列化执行、多线程和分布式计算可以提高性能和弹性。虽然它带来了复杂性，但这是一个发现和增强软件开发能力的旅程。

犯新错误

我担任软件工程师已有大约 15 年了。在我的职业生涯中，我学到了很多东西，并将这些知识应用于设计和实现（有时会逐步淘汰或保持原样）许多分布式系统。一路走来，我犯了很多错误，而且现在仍然在犯。但由于我的主要关注点是可靠性，我一直在回顾我的经验和社区，寻找尽量减少错误频率的方法。我的座右铭是：我们绝对必须尝试犯新的错误（不那么明显，更复杂）。犯错误没关系——这就是我们学习、重复的方式——令人悲伤和沮丧。

这可能就是数学一直让我着迷的地方。不仅因为它优雅简洁，而且因为它的逻辑严密性可以防止错误。它迫使您思考当前的背景，您可以依赖哪些假设和定理。事实证明，遵循这些规则是卓有成效的，您会得到正确的结果。确实，计算机科学是数学的一个分支。但我们通常实践的是软件工程，一个非常独特的东西。我们将计算机科学的成就和发现应用于实践，同时考虑到时间限制和业务需求。该博客尝试将半数学推理应用于计算机程序的设计和实现。我们将提出一个不同执行机制的模型，提供一个框架来避免许多编程错误。

出身卑微

当我们学习编程并迈出第一个尝试性（或大胆）步骤时，我们通常从一些简单的事情开始：

编程循环，进行基本算术并在终端中打印结果
解决数学问题，可能在 MathCAD 或 Mathematica 等特殊环境中

我们获得肌肉记忆，学习语言语法，最重要的是，我们改变了我们的思考和推理方式。我们学习阅读代码，假设它是如何执行的。我们几乎从不从阅读语言标准开始，并仔细阅读其“内存模型”部分 - 因为我们还没有能力完全理解和利用这些标准。我们练习反复试验：我们确实在第一个程序中引入了逻辑和算术错误。这些错误教会我们检查我们的假设：这个循环不变式是否正确，我们可以通过这种方式比较数组元素的索引和长度（你把这个-1放在哪里）？但如果我们没有看到某种错误，通常我们会隐含地内化一些错误不变量系统强制并提供给我们。

即这个：

代码行始终以相同的顺序（序列化）进行评估。

这个假设允许我们假设接下来的命题是正确的（我们不打算证明它们）：

评估顺序在执行之间不会改变
函数调用总是返回

数学公理允许在坚实的基础上推导和构建更大的结构。在数学中，我们有带有 4+1 假设的欧几里得几何。最后一篇说：

平行线保持平行，不相交或发散

几千年来，数学家们试图证明这一点，并从前四项中推导出来。事实证明这是不可能的。我们可以用替代方案代替这种“平行线”假设，并得到不同类型的几何形状（即双曲和椭圆），这开辟了新的前景，并且被证明是适用和有用的。毕竟我们自己的星球表面并不平坦，我们必须在 GPS 软件和飞机航线等中考虑到这一点。

改变的必要性

但在此之前，让我们停下来问一下最常见的工程问题：为什么要麻烦呢？如果程序完成了它的工作，就很容易支持、维护和发展，为什么我们首先要放弃这种可预测顺序执行的舒适不变量呢？

我看到两个答案。第一个是性能。如果我们能让我们的程序运行速度提高一倍或类似——只需要一半的硬件——这就是一项工程成就。如果使用相同数量的计算资源，我们可以处理 2 倍（或 3、4、5、10 倍）的数据 - 它可能会打开同一程序的全新应用程序。它可以在你口袋里的手机上运行，而不是在服务器上运行。有时我们可以通过应用巧妙的算法或用性能更高的语言重写来提高速度。是的，这些是我们要探索的第一个选择。但它们有一个限度。架构几乎总是胜过实现。摩尔定律最近表现不佳，单个CPU的性能增长缓慢，RAM性能（主要是延迟）落后。因此，工程师自然开始寻找其他选择。

第二个考虑因素是可靠性。大自然是混乱的，热力学第二定律不断地与任何精确、连续和可重复的事物作对。比特翻转、材料退化、电源耗尽、电线被切断，阻碍了我们的程序执行。保持连续且可重复的抽象成为一项艰巨的工作。如果我们的程序能够经受住软件和硬件故障的考验，我们就可以提供具有竞争性业务优势的服务——这是我们可以开始解决的另一项工程任务。

有了目标，我们就可以开始使用非序列化方法进行实验。

执行线程

让我们看一下这段伪代码：

```

def fetch_coordinates(poi: str) -> Point:

…

def find_pois(center: Point, distance: int) -> List[str]:

…

def get_my_location() -> Point:

…
def fetch_coordinates(p) - Point:
…

def main():

me = get_my_location()

for point in find_pois(me, 500):
loc = fetch_coordinates(point)
sys.stdout.write(f“Name: {point} is at x={loc.x} y={loc.y}”)

我们可以从头到尾阅读代码，并合理地假设“find_pois”函数将在“get_my_location”之后调用。在获取下一个 POI 后，我们将获取并返回第一个 POI 的坐标。这些假设是正确的，可以建立一个心理模型，对程序进行推理。

让我们想象一下我们可以让我们的代码非顺序执行。我们可以通过多种方法在语法上做到这一点。我们将跳过语句重新排序的实验（这就是现代编译器和 CPU 所做的）并扩展我们的语言，以便我们能够表达新的函数执行机制：同时甚至在平行下相对于其他功能。换言之，我们需要引入多执行线程。我们的程序函数在特定环境中执行（由操作系统设计和维护），现在我们对可寻址虚拟内存和线程（一个调度单元，可以由 CPU 执行的东西）感兴趣。

线程有不同的风格：POSIX 线程、绿色线程、协程、goroutine。细节差异很大，但归根结底都是可以执行的。如果多个功能可以同时运行，则每个功能都需要自己的调度单元。这就是多线程的由来，而不是一个，我们有多个执行线程。某些环境（MPI）和语言可以隐式创建线程，但通常我们必须使用 C 中的“pthread_create”、Python 中的“threading”模块类或 Go 中的简单“go”语句显式地执行此操作。通过一些预防措施，我们可以使相同的代码大部分并行运行：

 def fetch_coordinates(poi, results, idx) -> None: … results[idx] = poi def main(): me = get_my_location() points = find_pois(me, 500) results = [None] * len(points) # Reserve space for each result threads = [] for i, point in enumerate(find_pois(me, 500)): # i - index for result thr = threading.Thread(target=fetch_coordinates, args=(poi, results, i)) thr.start() threads.append(thr) for thr in threads: thr.wait() for point, result in zip(points, results): sys.stdout.write(f“Name: {poi} is at x={loc.x} y={loc.y}”)

我们实现了性能目标：我们的程序可以在多个 CPU 上运行，并随着内核数量的增长而扩展，完成速度更快。我们必须问的下一个工程问题：成本是多少？

我们有意放弃了串行化和可预测的执行。有无双射函数+时间点和数据之间。在每个时间点，正在运行的函数与其数据之间始终存在一个映射：

下一个结果是，这次一个函数可以在另一个函数之前完成，下一次可能会以另一种方式完成。这种新的执行机制会导致数据竞争：当并发函数处理数据时，这意味着应用于数据的操作顺序是未定义的。我们开始遇到数据竞争并学习使用以下方法处理它们：

关键部分：互斥体（和自旋锁）
无锁算法（最简单的形式在上面的代码片段中）
种族检测工具
ETC

至此，我们至少发现了两件事。首先，访问数据的方式有多种。一些数据是当地的（例如函数作用域变量）并且只有我们可以看到（并访问它），因此它始终处于我们离开它的状态。但是，某些数据是共享的或偏僻的。它仍然驻留在我们的进程内存中，但我们使用特殊的方式来访问它，它可能会不同步。在某些情况下，为了使用它，我们将其复制到本地内存中以避免数据竞争 - 这就是为什么 == 。克隆（） == 在 Rust 中很流行。

当我们继续这样的推理时，其他技术（例如线程本地存储）自然就会出现。我们刚刚在我们的编程工具带中添加了一个新的小工具，扩展了我们通过构建软件可以实现的目标。

然而，我们仍然可以依赖一个不变量。当我们从线程获取共享（远程）数据时，我们总是能得到它。不存在某些内存块不可用的情况。如果后备物理内存区域出现故障，操作系统将通过终止进程来终止所有参与者（线程）。这同样适用于“我们的”线程，如果我们锁定了互斥体，我们就不可能失去锁定，并且必须立即停止我们正在做的事情。我们可以依赖这个不变量（由操作系统和现代硬件强制执行），即所有参与者要么死要么活。所有人都有共同的命运：如果进程（OOM）、操作系统（内核错误）或硬件遇到问题 - 我们所有的线程将不再一起存在，而不会产生外部残留的副作用。

发明一个过程

需要注意的一件重要事情。我们是如何通过引入线程来迈出第一步的？我们分开了，分叉了。我们引入了多个调度单元，而不是一个调度单元。让我们继续应用这种不共享的方法，看看效果如何。这次我们复制进程虚拟内存。这就是所谓的“生成进程” 。我们可以运行程序的另一个实例或启动其他现有实用程序。这是一个很好的方法：

重用具有严格边界的其他代码
运行不受信任的代码，将其与我们自己的内存隔离

几乎全部==现代浏览器==以这种方式工作，因此他们能够运行从互联网下载的不受信任的 Javascript 可执行代码，并在您关闭选项卡时可靠地终止它，而无需关闭整个应用程序。

这是我们通过放弃共享命运不变性和不共享虚拟内存并制作副本而发现的另一种执行机制。副本不是免费的：

操作系统需要管理内存相关的数据结构（维护虚拟->物理映射）
某些位可能已共享，因此进程会消耗额外的内存

挣脱束缚

为什么停在这里？让我们探讨一下我们还可以在哪些地方复制和分发我们的程序。但为什么首先要进行分布式呢？在许多情况下，手头的任务可以使用一台机器来解决。

我们需要分布式逃避共同的命运原则，以便我们的软件停止依赖于底层遇到的不可避免的问题。

仅举几例：

操作系统升级：我们有时需要重新启动机器
硬件故障：它们发生的频率比我们想象的要高
外部故障：电源和网络中断是一个问题。

如果我们复制一个操作系统，我们称之为虚拟机，可以在物理机上运行客户的程序并在其上构建庞大的云业务。如果我们使用两台或多台计算机并在每台计算机上运行我们的程序 - 我们的程序甚至可以在硬件故障后继续存在，提供 24/7 服务并获得竞争优势。大公司很久以前就走得更远，现在互联网巨头在不同的数据中心甚至大陆上运行副本，从而使程序能够抵御台风或简单的停电。

但这种独立性是有代价的：旧的不变量没有得到执行，我们只能靠自己。不用担心，我们不是第一批。有很多技术、工具和服务可以帮助我们。