读：三种响应式算法的推拉权衡
目录
Jonathan Frere 在 原文 里把三种响应式算法（push、pull、push-pull）摆在一起比了个遍。为什么响应式系统的实现方式这么多，到底哪种好？这事得从四个约束的取舍说起。
响应式系统的四个约束
原文拿电子表格举例。表格里有输入单元格、中间计算单元格和输出单元格。某个输入一变，依赖它的所有单元格都得跟着变，这就是响应式。
不过「跟着更新」只是最低要求。现实里的响应式系统往往还得满足四个约束。
- *高效（Efficient）*，每个单元格最多重算一次。已经算过的结果不丢弃，也不重复计算会被覆盖的中间值。
- *细粒度（Fine-grained）*，只更新真正受影响的单元格，没变的一律不动。
- *无毛刺（Glitchless）*，所有单元格同时更新，外部观察者看不到中间不一致的状态。原文举了个例子，相邻两个单元格一个存国家代码（UK、DE、BE），另一个存国家全称。如果更新过程中能看到代码已变、全称却还没跟着变，那就是出现了毛刺（glitch，指可观察到的瞬时不一致）。
- *动态依赖（Dynamic）*，依赖关系本身可以变化。比如
IF(condition, B1)这样的条件公式，condition 为真时依赖 B1，为假时不依赖。B1 变了，但 condition 为假的公式不该被触发更新。
Push 推式响应
Push 算法的机制很直白。一个节点更新完，主动通知所有依赖它的节点，更新沿着依赖链一路推下去。大多数事件系统、流（stream）、observable 都是这个套路。promise/future/async-await 也能看成一次性的推式响应树，每个 .then 或 await 都是在监听上一步，初始 promise resolve 时把更新一路推到链尾。
Push 最大的好处是天然满足 细粒度 。每次输入变化只通知真正依赖它的节点，别的节点压根不用知道发生了什么。适合输入频繁独立变化的场景（电子表格、GUI）。
但 push 有两个核心问题。
效率问题
设想下面这张依赖图。A 变了，B 依赖 A 和 C，C 也依赖 A，D 依赖 B 和 C。
A 变化时先通知 B 和 C。B 依赖 A 和 C，可这时 C 还没更新，B 可能先拿旧的 C 算一次。等 C 更新完再通知 B，B 只能重算，第一次的结果白扔了。D 更惨，A 才变了一次，D 可能收到三次更新通知。
办法是按特定顺序更新。先更新 A，通知 B 和 C。B 发现自己还有另一个依赖 C 没动，先等着。C 更新完通知 B 和 D。B 看到两个依赖都就绪，更新，再通知 D。D 最后更新。这样每个节点只更新一次。
要做到这点，算法需要看到整张依赖图，算出最优更新顺序。这个顺序叫 *拓扑排序（topological sort）*。它把图里的节点排成一个线性序列，每个节点在序列中只出现一次，而且排在它所有依赖的后面。比如 B 依赖 A 和 C，那 A 和 C 必须排在 B 前面。这样从头到尾走一遍，每个节点只访问一次，访问它的时候它依赖的节点都已经更新过了。
不过这里有个根本矛盾。push 的价值在于每个节点只需掌握自己的直接依赖者，局部决策容易，全局分析难。系统一旦有了动态依赖（前面说的那种，依赖关系随运行时值变化，比如 IF 条件为真才依赖某个单元格），全局拓扑排序就变得昂贵甚至不可能。
毛刺问题
只要代码运行在第一个节点更新之后、最后一个节点更新之前，就可能看到不一致的中间状态。
Pull 拉式响应
把 push 的图反过来就是 pull。每个节点主动调用它的依赖来取值。更新自己之前得先让依赖更新，所以其实它就是 *一个递归的函数调用栈*。我调一个函数，函数内部按需调更多函数，最后返回结果。
但纯函数调用还不算响应式，缺一个触发机制，也就是状态变化时怎么触发函数重跑。
最简单的系统每次输入变化就重算一切。回到电子表格的例子就是，改一个单元格就把表格里所有单元格从头算一遍。遇到引用其他单元格（比如 =B8=）就先递归算 B8 的值，再接着算自己。最后所有单元格都更新到最新值。
这种暴力重算有两个明显的好处。
无毛刺
每次输入变化只做一轮递归遍历，只要遍历过程中不改输入，所有节点看到的输入都是一致的。单线程运行时（比如 JavaScript）天生满足这点，因为递归遍历在调用栈上一口气跑完，中间没有别的代码能插进来修改输入。多线程环境下另一个线程可能恰好在你遍历到一半时改了输入，解决办法是加锁，遍历开始时锁住输入，遍历结束后解锁，其他想改输入的线程排队等锁释放就行。
天然支持动态依赖
既然 pull 其实就是函数调用栈，条件调用（也就是条件依赖）就是写个 if 的事。不用维护订阅列表，需要哪个值就去取。
但暴力 pull 有个大问题。
浪费计算
A1 和 A2 都引用 B8 的话，一轮更新里 B8 会被算两次。一个解决办法是把算过的单元格缓存起来，后续引用直接用缓存值。但缓存失效又是一个难题。简单方案用 generation counter，每次改输入就清空全部缓存，一了百了但浪费多。复杂方案用 LRU 缓存（LRU 是最近最少使用策略，缓存满了先淘汰最久没访问的条目），但需要考虑两个问题。一是缓存设多大，太小命中率低老得重算，太大占内存。二是相等性判断，比如两个单元格引用的是同一个值但用了不同的对象引用，缓存怎么知道它们是同一个东西。两种方案也能混用，计算成本低的节点不缓存，计算成本高的节点上重型缓存策略。
此外，暴力重算需要更新所有节点，可现实是大部分节点其实可能都没变。最好是只更新真正受影响的节点。但纯 pull 系统里，输入节点不知道谁依赖自己，没法判断影响范围。这是 pull 算法靠自己解不开的死结。
Push-Pull 推拉混合
push 和 pull 各有硬伤。push 效率差又难避免毛刺，pull 不知道该更新谁。原文的第三种方案两边的好处都要，push 阶段干标记，pull 阶段干重算。
Push 阶段，标记脏节点
给每个节点加一个 *dirty 标志（脏标记）*，true 代表要重算，false 代表已经是最新。初始全是 false，整棵树干干净净。
当某个输入节点变化，从它出发递归遍历下游节点，对每个节点做下面几件事。
- 如果已经是 dirty，跳过（之前标记过了）。
- 标记为 dirty。
- 如果是输出节点（叶子节点），加入一个待更新列表。
- 否则递归处理它的所有下游节点。
遍历完会得到一棵 dirty 和 clean 节点混着的树，只有 dirty 节点需要更新。
关键在于这个 push 阶段不关心访问顺序。纯 push 要拓扑排序，这里只要该标记的都标记到就行，顺序无所谓。所以算法简单，递归遍历加 dirty 检查就够了。
Pull 阶段，按需重算
现在知道哪些输出节点需要更新了（push 阶段收集的待更新列表）。对每个待更新的输出节点，执行和纯 pull 一样的递归拉取，但加两个检查。
- 如果当前节点是 clean，直接返回缓存值。它不需要重算，因为不在任何变更输入的下游。
- 如果当前节点是 dirty，重算，标记为 clean，缓存结果。
pull 结束后，整棵树全部 clean，所有输出节点更新完毕。
Push-Pull 为什么满足四个约束
一项一项对照。
- 先说 *高效*。push 阶段每个节点最多访问一次（dirty 检查会跳过已经标记过的），pull 阶段同样每个节点最多重算一次（clean 检查用上缓存），整体是 O(n)，n 是受影响节点数。
- 细粒度 也靠得住，push 阶段精确收集了需要更新的节点列表，pull 阶段只重算这些节点，其余完全不动。
- 无毛刺 方面，重算发生在 pull 阶段，和纯 pull 一样，只要 pull 期间不改输入，就不会出现可观察的不一致。
- 动态依赖 呢，pull 天生支持（前面讲过）。push 阶段也不需要全局拓扑排序，每个节点只要维护直接上下游邻居列表，动态增删依赖很轻松。
四个约束全满足，push-pull 的魅力就在这。
总结
原文比较的三种算法可以归到一张矩阵里。
| 算法 | 高效 | 细粒度 | 无毛刺 | 动态依赖 |
|---|---|---|---|---|
| Push | 难（需拓扑排序） | 天然满足 | 难（需全局同步） | 与效率冲突 |
| Pull | 难（缓存失效） | 不能（不知影响范围） | 天然满足 | 天然满足 |
| Push-Pull | O(n) 满足 | 满足 | 满足 | 满足 |
push 和 pull 各有两个天生短板，互相补不上。push-pull 用两阶段分离，把「谁需要更新」交给 push（补上 pull 不知影响范围的短板），把「怎么算」交给 pull（补上 push 效率和毛刺的短板）。