本文翻译自 Pushing and Pulling: Three Reactivity Algorithms，原载于 Hacker News。
引言
作者 Jonathan Frere 在工作中需要构建一个响应式引擎，因此整理了他对响应式系统的理解。这篇文章探讨了构建响应式引擎的三种方式：基于推（push）的响应式、基于拉（pull）的响应式，以及混合的推拉结合（push-pull）模式——这种模式被许多 Web 框架采用。
问题描述
理解响应式最直观的方式是把它想象成电子表格。你有一系列输入单元格，包含初始数据；还有一系列输出单元格，包含最终结果。中间还有很多单元格，包含需要计算以得出最终结果的中间值。
当一个输入单元格变化时，所有依赖它的单元格都需要对这个变化做出响应——这就是所谓的响应式。但在实践中，这只是最基本的要求。构建响应式系统时，我们通常会施加一些额外的要求，让问题变得更加复杂：
- 高效（Efficient）：每个单元格最多重新计算一次，不做任何会立即被丢弃的计算
- 细粒度（Fine-grained）：只更新真正需要更新的单元格，不受影响的单元格保持不变
- 无故障（Glitchless）：所有单元格同时变化，永远不会出现中间计算值已更新但输出单元格仍显示基于旧输入的结果的情况
- 动态（Dynamic）：每次节点更新时，可能会动态添加或移除依赖关系
前两个要求（”高效”和”细粒度”）对性能很重要。想象一个包含数百万个公式单元格的大型电子表格——每次输入变化时重新计算每个单元格将是对资源的巨大浪费。同样，如果可以避免，你不希望多次计算一个单元格的值。一般来说，我们希望做最少的必要工作。
第三个要求（”无故障”）对正确性很重要。我们不希望中间状态是可观察的——如果可能的话，我们可能会遇到无效状态。考虑两个相邻单元格，一个包含国家的 ISO 国家代码（UK、DE、BE 等），另一个包含该国家的全名。我们不希望能够观察到两个单元格彼此不同步的状态。
第四个要求（”动态”）确保我们只在真正需要时才创建依赖关系。这在条件公式中最容易看到，比如 IF(<condition>, slow_calculation(B1))。如果条件为真，这个公式返回（因此依赖于）单元格 B1 的值。但如果条件为假，公式什么都不返回——如果 B1 变化，这个单元格不应该更新。这就是动态依赖——依赖关系只在 <condition> 为真时才存在。
需要注意的是，并非所有响应式系统都需要这些要求。例如，许多简单的响应式系统只需要静态依赖，牺牲一些效率来换取实现简单性。同样，故障只在被观察时才重要，所以一些响应式系统默认会有故障，但如果用户确实需要同步，会提供工具来同步节点。
基于推的响应式（Push-Based Reactivity）
在基于推的响应式中，当一个节点更新时，它会通知（并更新）所有依赖它的节点。我们可以将其可视化为更新被沿着依赖链向下推送，直到到达需要更新的最终节点。
这是一种简单且因此非常常见的方法。一般来说，大多数事件系统、流和可观察对象都遵循这种大致模式。甚至 promises/futures/async/await 也可以被认为是一次性的基于推的响应式树——每个 .then/.map/await 调用都为前一步创建一个监听器，然后当初始 promise 解析时，更新被推送到系统的其余部分。
基于推的响应式的最大优点是它是细粒度的。每次输入变化时，我们只通知那些真正需要更新的依赖项。系统中的其他每个节点都可以保持愉快地无知状态。如果我们有很多彼此独立更新的输入，这很好——我们的电子表格就是一个很好的例子，大多数 GUI 也是如此。
然而，基于推的系统通常效率不是特别高，只有通过额外的工作才能解决这个问题。让我们看一个创建不必要工作的图的示例。
根据我们的基于推的系统，我们更新图中的第一个节点（A）。这向（A）的依赖项推送一个信号，表示它们现在应该更新。在这种情况下，（B）和（C）都会更新。但是，（B）同时依赖于（A）和（C），所以当（C）更新时，（B）需要再次更新，我们丢弃在那里做的任何先前工作。同样，基于对（A）的单次更新，（D）将接收三个不同的更新信号。
如果我们确保始终以特定顺序执行更新，我们可以在某种程度上改进这一点。考虑对上图的不同方法：
- 我们更新（A），并向（B）和（C）推送更新信号
- （B）暂时延迟更新，知道还有其他依赖项需要先更新。同时，（C）更新，并向（B）和（D）推送信号
- （B）现在更新，因为（A）和（C）现在都准备好了。完成后，它向（D）推送信号
- （D）最后更新
在这个版本中，每个节点只更新一次。我们可以这样做，因为我们可以看到整个依赖图，并计算通过它的最优路径。如果我们知道整个图，我们总是可以计算最优路径，但不一定我们总是能知道整个图。
基于推的系统的一部分价值在于每个节点只需要跟踪自己的依赖项和被依赖项，这使得在本地分析每个节点很容易，但作为一个整体分析系统很难。在极端情况下，你可能会根据先前的值动态创建和销毁树中的节点——这对我们的电子表格类比没有意义，但这基本上就是 RxJS 的 switchMap 操作符发生的情况。本质上，我们想要系统中的动态性越多，实现高效更新就越困难，我们越想要高效更新，就越需要预先指定我们的依赖图。
基于推的响应式的另一个挑战是故障。如前所述，故障是指我们能够观察到两个节点彼此不同步的时候。在基于推的响应式中，这很容易实现——在第一个节点更新后但在最终节点更新之前运行的任何代码都有机会”看到”故障。
我们可以通过两种方式避免这种情况。首先，我们可以声明任何观察两个节点的代码必须依赖于这些节点，然后应用我们之前描述的拓扑排序。或者，我们可以声明任何可能能够观察两个节点的代码只能在所有节点完成运行后运行。这两种方法都有效，但同样它们要求我们能够观察完整的依赖树并对所有节点进行拓扑排序。
另一个问题是，在实践中，令人惊讶的是很容易编写隐式观察某些状态而没有适当依赖关系的代码，此时故障再次出现。通常没有简单的方法可以完全防止这些情况的发生，因此需要一定的警惕性来确保一切正常工作。
基于拉的响应式（Pull-Based Reactivity）
如果上面描述的是基于推的响应式，我们可以画出所有事情反向发生的图表，并称之为基于拉的响应式。但这并不一定给我们关于基于拉的响应式实际上是什么的直觉。
在基于推的响应式中，一旦节点完成更新，它就调用其依赖项。因此，在基于拉的响应式中，我们期望每个节点调用其依赖关系。而且因为你需要你的依赖项在你之前更新，我们可以看到这是如何工作的：每个节点更新其所有依赖项，然后更新自己的值。
本质上，基于拉的响应式基本上只是一堆函数调用。我调用一个函数，如果需要，它调用更多函数，然后返回结果。我可以根据需要递归嵌套这些函数，依赖项将自动为我计算。
但这还不是很响应式。我们仍然需要某种方式在状态变化时触发函数重新运行。
最简单的可能系统是我们只是重新运行所有内容。回到我们的电子表格，每次更新单元格时，我们遍历表中的每个单元格并重新计算其值。当一个单元格引用另一个单元格（例如 =B8）时，我们首先计算依赖项的值，然后继续计算初始单元格的值。最终，我们将递归地更新表中的每个单元格。
你可能能够看到这个系统的一些问题，但让我们暂时把它们放在一边，看看我们为什么可能想要这种系统。
第一个好处是让我们的代码无故障要容易得多。每次更改输入时，我们对所有节点进行一次递归传递，将它们更新为新值。只要我们在该传递期间不更改输入，所有节点将看到彼此一致的输入。在像 JavaScript 这样的单线程运行时中，这个条件很容易实现，即使我们引入并发，我们也只需要简单的锁定原语来确保我们在进行输入更改之前等待传递完成。
第二个好处是我们免费获得动态依赖。如果基于拉的响应式只是一个调用栈，那么有条件地调用（即有条件地依赖）某些输入就非常容易。我们不需要维护节点订阅了哪些依赖项的内部列表，反之亦然，我们只是根据需要获取值。
但是有问题——事实上，有两个大问题意味着这种方法往往只在非常特定的情况下效果最好。
第一个问题又是浪费工作。如果单元格 A1 引用 B8，单元格 A2 也引用 B8，那么当我们更新所有单元格时，我们仍然只想评估 B8 一次，然后在 A1 和 A2 中都引用它。我们可以通过缓存来做到这一点——每当我们计算单元格的值时，我们将它存储在某处，然后所有未来的单元格引用可以使用存储的值而不是重新计算。
我不会深入探讨基于拉的响应式中的缓存，但正如著名的格言提醒我们的那样，计算机科学中最难的事情之一是缓存失效。通常，缓存在减少工作方面越高效，缓存失效就变得越困难。所以一个简单的方法可能是代数计数器，每次我们更改任何输入时，所有缓存值立即失效，一个更难的方法可能是所有节点依赖项的 LRU 缓存，我们需要考虑缓存多少条目，以及如何确定相等性。
然而，还有第二个问题需要处理。目前，我们不知道哪些单元格实际上会变化，所以我们要更新所有单元格。实际的基于拉的响应式图表可能看起来更像这样：
理想情况下，我们只更新变化的单元格，其余的保持不变。不幸的是，这证明是令人惊讶地困难。
我们可以稍微改变问题。例如，React 使用基于拉的响应式系统，但可以隔离渲染树中的某些组件，并说”只有这个组件及其所有子组件应该更新”。这意味着不需要重新渲染整个世界，只需要重新渲染给定组件及其子组件。这个机制的工作原理很有趣，但我将在后续文章中探讨，因为这篇文章已经太长了！
一般来说，我们不能只用基于拉的响应式解决这个问题。被更新的输入节点没有信息告诉我们它的依赖项是什么，因此最终哪些输出节点将需要改变。但我们可以尝试不同的方法，我们确实尝试存储该信息。推和拉的组合——某种推拉响应式？
推拉结合的响应式（Push-Pull Reactivity）
推拉响应式之所以得名，是因为它做了两件事：首先我们推，然后我们拉。但是，我们不会做两次相同的事情，我们的推和拉将有不同的目的。
让我们从推开始。考虑一个节点树。如果我们更新其中一个输入节点，我们现在的目标是找出哪些子节点（和输出节点）需要更新。我们实际上不会进行更新，我们只是找出哪些需要更新。
我们可以通过向每个节点添加一个布尔 dirty 标志来实现这一点。如果它被设置为 true，那么这是一个需要重新计算的节点。否则，它是最新的。让我们从所有这些标志都设置为 false 开始——我们有一个最新的树。现在，当我们更新输入节点时，我们可以迭代该节点的所有子节点，并遵循一个简单的算法：
- 如果当前节点已经被标记为 dirty，我们不需要做任何事情，可以跳过它
- 我们将当前节点标记为 dirty
- 如果节点是一个输出节点，我们将它添加到需要更新的输出列表中
- 否则，我们递归访问当前节点的所有子节点，并对它们应用相同的算法
最终，我们将有一个混合 dirty 和 clean 节点的树，其中只有 dirty 节点需要更新。重要的是，与原始的基于推的响应式不同，我们访问节点的顺序不重要。这意味着我们不需要找出通过整个树的最优路径，并且可以使用更简单的递归算法，只要我们确保跳过任何已经被标记为 dirty 的节点。
现在让我们尝试拉。上次，基于拉的响应式的一个问题是我们不知道哪些节点需要更新。但现在我们知道——任何 dirty 输出节点都需要更新。我们在标记节点为 dirty 时甚至还制作了这些节点的列表！
所以现在，对于那些输出节点中的每一个，我们做与拉步骤中相同的事情。但我们向我们的逻辑添加了几个额外的检查：
- 如果我们查看的节点是 clean 的，我们返回该节点的值。我们知道现有值不需要重新计算，因为它没有被标记为 dirty，所以它不在任何更改输入的下游
- 如果我们查看的节点是 dirty 的，我们计算结果，将节点标记为 clean，并将计算结果与节点一起存储
一旦我们完成了推和拉过程，我们将得到一个全部 clean 的节点树，并且我们将更新所有输出节点。
让我们再次看看我们的要求，看看推拉响应式表现如何：
- 高效：当我们推时，我们只访问每个节点一次。当我们拉时，我们再次只访问每个节点一次。这是事情能达到的最高效程度
- 细粒度：当我们推时，我们制作一个恰好需要更新的节点的列表。当我们拉时，我们只重新计算那些节点，让所有其他节点保持不变
- 无故障：因为重新计算在拉步骤期间发生，我们在这里共享基于拉的响应式的相同好处，这意味着如果我们能保证在拉步骤期间不更改任何输入，那么计算必须是无故障的
- 动态：拉总是动态的，正如我们之前讨论的那样。但因为我们需要任何节点的全局排序，拥有动态推步骤也非常容易，因为每个节点只需要保持其上游和下游直接邻居的列表。这种结构通常比维护全局有序列表更容易操作（并且比每次我们想要评估节点时执行新的拓扑排序便宜得多）
很好！
结论
这三个是我熟悉的响应式系统的主要类别——节点从上方信号更新的系统，节点从下方按需更新的系统，以及混合方法。
对于作者使用响应式的目的（主要是 Web/GUI 开发和最近的电子表格引擎工作），推拉响应式是一个非常好的工具。O(n) 的特性使其在应用程序大小增长时保持相当高效（特别是记住那里的 ‘n’ 是需要更新的节点数，这可能是系统中总节点的一个小子集）。它也非常容易理解正在发生什么。
也就是说，它也有自己的问题。例如，这篇文章中的一个假设是可以在单个 tick 中完成整个”拉”逻辑，在输入节点更新之间。如果那不可能，你可能需要将长时间运行的操作转换为在后台更新的状态机，但这通常可能变得复杂。
在撰写本文的过程中，作者最终陷入了各种离题，这些离题最终被删除了，因为它们让一切变得太长和复杂——作者将尝试在未来的后续文章中放一些这些离题，因为它们很有趣。
个人思考
这篇文章对响应式系统的三种实现方式进行了非常清晰的分析。对于前端开发者来说，理解这些概念对于选择合适的框架和工具非常有帮助：
- React 使用基于拉的响应式，通过虚拟 DOM diff 来优化性能，但牺牲了一些细粒度
- Vue 2 使用基于推的响应式（观察者模式），而 Vue 3 转向了推拉结合的方式
- SolidJS 使用细粒度的基于推的响应式，通过编译时优化来避免不必要的更新
- MobX 也是推拉结合的模式，通过 observable 和 computed 来实现高效更新
推拉结合的模式在大多数场景下是最佳选择，因为它兼顾了效率和正确性。但对于特定场景，简单的推或拉模式可能就足够了，而且实现起来更简单。选择哪种方式取决于你的具体需求：是否需要动态依赖？对性能的要求如何？能否接受偶尔的故障？
原文作者 Jonathan Frere，翻译时有所调整以适应中文读者的阅读习惯。