设计垃圾回收系统（第一部分）

原文：Design a Garbage Collection System (Part I)

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

我们的系统设计面试系列在过去几个月得到了很多反馈。我很高兴知道，我们的读者觉得有帮助。

我经常给的一个建议是不要把这些文章作为标准答案。系统设计面试问题通常是开放式的，全部是关于分析和交流。讨论中的任何一点都可以根据面试官的偏好进行更深入的研究。

本周，这个问题略有不同，因为它有点低级，但同时也相当有用 - 垃圾回收系统。垃圾回收系统不仅在很多现代编程语言中广泛使用，同样的思想也可以适应其他领域。

你对垃圾回收了解多少？

许多面试官喜欢与候选人讨论语言偏好。有时就像热身讨论，但有时候他们想要更深入。垃圾回收必然会包含在讨论当中，因为它是几乎所有编程语言中最重要的概念之一。

作为一个面试官，我想这样开始讨论，询问“告诉我你对垃圾回收的了解”。这个问题可以让我了解，候选人对这个话题有多熟悉。

请记住，要在面试中表现出色，你不一定需要了解很多垃圾回收的知识，因为面试官关心分析而不是知识。另一方面，了解很多垃圾回收并不意味着你可以轻松通过面试。

回到问题，垃圾回收是一种系统，可以自动回收编程语言中未使用的内存。 Java 是一个最流行的例子。编写 Java 时，你不需要控制如何分配和回收内存。一切都发生在背后。

那么为什么我们需要垃圾回收？很多人可以轻易说出垃圾回收的优点，但是当被问及垃圾回收的缺点时会感到困惑。同样，如果你能很好把握程序的工作，你可以通过分析问题轻松得出好的答案，这不是你需要记住的事实。

垃圾回收的最明显的好处是它使编程更容易。请记住，当我们编写 C ++ 时，我们需要非常小心指针和内存分配（译者注：也可以使用智能指针来避免它）。通过让程序自己处理所有这些，开发人员可以更多关注核心逻辑。

更具体地说，首先垃圾回收有助于开发人员避免几个内存问题，它防止访问悬挂指针，它指向不再存在的对象。其次，它防止释放已经释放的内存区域（双重释放）。最后，它避免了内存泄漏，这意味着无法释放不可访问的内存区域。当开发人员尝试手动管理内存时，所有这些都是常见的缺陷。

那么有什么缺点呢？显然，有许多语言没有像 C++ 那样的内置垃圾回收。

最大的缺点是垃圾回收会消耗计算资源。想一想，垃圾回收不仅需要实现逻辑来回收内存，还要消耗内存来存储对象的状态。在一些朴素的垃圾回收实现中，回收过程甚至可能会阻塞程序。

另一种思考的方式是，如果没有垃圾回收，开发人员可以完全控制内存的使用方式，从而使程序具有更大的灵活性，更容易优化。这就是为什么 C++ 更高效的原因之一。当然，它也容易出错。

那么如何设计垃圾回收系统？试着自己想想这个问题。如果你没有先前的知识，这会更好。我不想跳到解决方案，而是想告诉你如何逐步分析这个问题。

由于垃圾回收系统的本质是回收程序中未使用的内存，所以关键是要确定哪一块内存是未使用的。更具体地说，我们应该搜索不再被引用的变量。

如果考虑程序中的所有对象（变量），就像一个有向图，每个对象引用其他对象，同时也被一些对象引用。因此，那些没有任何引用的，不可到达的对象应该被回收。正如你所看到的，这个大问题已经简化为一个图问题 - 在一个图中找到不可达的节点。

事实上，上述解决方案只是最朴素的方法，被称为标记和扫描。首先，垃圾回收系统执行树的遍历来对象引用，并标记所有访问的对象。在第二阶段，对于所有无法访问的对象，释放它们的内存。

但是系统如何跟踪那些不可达的对象呢？一个简单的方法是保存程序中的所有对象。每当一个新的对象被初始化时，将它添加到池中。

你已经看到了，标记和扫描方法的本质与简单的图的遍历问题没有什么不同。这就是我总是强调基础数据结构/算法的原因，这是所有技术面试问题的基础。

在垃圾回收系统的第二篇文章中，我们将讨论标记和扫描的问题，并与其他实现进行比较。我们还将讨论现代语言中的垃圾回收。