从框架作者角度聊：React调度算法的迭代过程

[zepang]

大家好，我卡颂。

React内部最难理解的地方就是**「调度算法」**，不仅抽象、复杂，还重构了一次。

可以说，只有React团队自己才能完全理解这套算法。

既然这样，那本文尝试从React团队成员的视角出发，来聊聊**「调度算法」**。

什么是调度算法

React在 v16 之前面对的主要性能问题是：当组件树很庞大时，更新状态可能造成页面卡顿，根本原因在于：更新流程是**「同步、不可中断的」**。

为了解决这个问题，React提出Fiber架构，意在**「将更新流程变为异步、可中断的」**。

最终实现的交互流程如下：

1. 不同交互产生不同优先级的更新（比如onClick回调中的更新优先级最高，useEffect回调中触发的更新优先级一般）
2. **「调度算法」**从众多更新中选出一个优先级作为本次render的优先级
3. 以步骤 2 选择的优先级对组件树进行render

在render过程中，如果又触发交互流程，步骤 2 又选出一个更高优先级，则之前的render中断，以新的优先级重新开始render。

本文要聊的就是步骤 2 中的**「调度算法」**。

expirationTime 调度算法

**「调度算法」**需要解决的最基本的问题是：如何从众多更新中选择其中一个更新的优先级作为本次render的优先级？

最早的算法叫做expirationTime 算法。

具体来说，更新的优先级与**「触发交互的当前时间」及「优先级对应的延迟时间」**相关：

// MAX_SIGNED_31_BIT_INT 为最大 31 bit Interger update.expirationTime = MAX_SIGNED_31_BIT_INT - (currentTime + updatePriority);

例如，高优先级更新 u1、低优先级更新 u2 的updatePriority分别为 0、200，则

`MAX_SIGNED_31_BIT_INT - (currentTime + 0) > MAX_SIGNED_31_BIT_INT - (currentTime + 200)

// 即
u1.expirationTime > u2.expirationTime;

`

代表u1优先级更高。

expirationTime 算法的原理简单易懂：每次都选出所有更新中**「优先级最高的」**。

如何表示 “批次”

除此之外，还有个问题需要解决：如何表示**「批次」**？

**「批次」**是什么？考虑如下例子：

`// 定义状态 num
const [num, updateNum] = useState(0);

// ... 某些修改 num 的地方
// 修改的方式 1
updateNum(3);
// 修改的方式 2
updateNum(num => num + 1);

`

两种**「修改状态的方式」**都会创建更新，区别在于：

• 第一种方式，不需考虑更新前的状态，直接将状态num修改为 3
• 第二种方式，需要基于**「更新前的状态」**计算新状态

由于第二种方式的存在，更新之间可能有连续性。

所以**「调度算法」计算出一个优先级后，组件render时实际参与计算「当前状态的值」**的是：

「计算出的优先级对应更新」 + 「与该优先级相关的其他优先级对应更新」

这些相互关联，有连续性的更新被称为一个**「批次」**（batch）。

expirationTime 算法计算**「批次」**的方式也简单粗暴：优先级大于某个值（priorityOfBatch）的更新都会划为同一批次。

const isUpdateIncludedInBatch = priorityOfUpdate >= priorityOfBatch;

expirationTime 算法保证了render异步可中断、且永远是最高优先级的更新先被处理。

这一时期该特性被称为Async Mode。

IO 密集型场景

Async Mode可以解决以下问题：

1. 组件树逻辑复杂导致更新时卡顿（因为组件render变为可中断）
2. 重要的交互更快响应（因为不同交互产生更新的优先级不同）

这些问题统称为CPU 密集型问题。

在前端，还有一类问题也会影响体验，那就是**「请求数据造成的等待」**。这类问题被称为IO 密集型问题。

为了解决IO 密集型问题的，React提出了Suspense。考虑如下代码：

`const App = () => {
  const [count, setCount] = useState(0);

    useEffect(() => {
    const t = setInterval(() => {
      setCount(count => count + 1);
    }, 1000);
    return () => clearInterval(t);
  }, []);

    return (
    <>
      <Suspense fallback={

loading...

}>
        <Sub count={count} />
      
      

count is {count}

    </>
  );
};

`

其中：

• 每过一秒会触发一次更新，将状态count更新为count => count + 1
• 在Sub中会发起异步请求，请求返回前，包裹Sub的Suspense会渲染fallback

假设请求三秒后返回，理想情况下，请求发起前后UI会依次显示为：

`// Sub 内请求发起前

<div class=“sub”>I am sub, count is 0

count is 0

// Sub 内请求发起第 1 秒

loading...

count is 1

// Sub 内请求发起第 2 秒

loading...

count is 2

// Sub 内请求发起第 3 秒

loading...

count is 3

// Sub 内请求成功后

<div class=“sub”>I am sub, request success, count is 4

count is 4

`

从用户的视角观察，有两个任务在并发执行：

1. 请求Sub的任务（观察第一个div的变化）
2. 改变count的任务（观察第二个div的变化）

Suspense带来了**「多任务并发执行」**的直观感受。

因此，Async Mode（异步模式）也更名为Concurrent Mode（并发模式）。

一个无法解决的 bug

那么Suspense 对应更新的优先级是高还是低呢？

当请求成功后，合理的逻辑应该是**「尽快展示成功后的 UI」**。所以Suspense 对应更新应该是高优先级更新。那么，在示例中共有两类更新：

1. Suspense对应的高优 IO 更新，简称u0
2. 每秒产生的低优CPU更新，简称u1、u2、u3等

在expirationTime 算法下：

// u0 优先级远大于 u1、u2、u3... u0.expirationTime >> u1.expirationTime > u2.expirationTime > …

u0优先级最高，则u1及之后的更新都需要等待u0执行完毕后再进行。

而u0需要等待**「请求完毕」**才能执行。所以，请求发起前后UI会依次显示为：

`// Sub 内请求发起前

<div class=“sub”>I am sub, count is 0

count is 0

// Sub 内请求发起第 1 秒

loading...

count is 0

// Sub 内请求发起第 2 秒

loading...

count is 0

// Sub 内请求发起第 3 秒

loading...

count is 0

// Sub 内请求成功后

<div class=“sub”>I am sub, request success, count is 4

count is 4

`

从用户的视角观察，第二个div被卡住了 3 秒后突然变为 4。

所以，只考虑CPU 密集型场景的情况下，**「高优更新先执行」**的算法并无问题。

但考虑IO 密集型场景的情况下，高优 IO 更新会阻塞低优 CPU 更新，这显然是不对的。

所以expirationTime 算法并不能很好支持并发更新。

expirationTime 算法在线 Demo[1]

出现 bug 的原因

expirationTime 算法最大的问题在于：expirationTime字段耦合了**「优先级」与「批次」**这两个概念，限制了模型的表达能力。

这导致高优 IO 更新不会与低优 CPU 更新划为同一**「批次」**。那么低优 CPU 更新就必须等待高优 IO 更新处理完后再处理。

如果不同更新能根据实际情况灵活划分**「批次」**，就不会产生这个bug。

重构迫在眉睫，并且重构的目标很明确：将**「优先级」与「批次」**拆分到两个字段中。

Lane 调度算法

新的调度算法被称为Lane，他是如何定义**「优先级」与「批次」**呢？

对于优先级，一个lane就是一个32bit Interger，最高位为符号位，所以最多可以有 31 个位参与运算。

不同优先级对应不同lane，越低的位代表越高的优先级，比如：

// 对应 SyncLane，为最高优先级 0b0000000000000000000000000000001 // 对应 InputContinuousLane 0b0000000000000000000000000000100 // 对应 DefaultLane 0b0000000000000000000000000010000 // 对应 IdleLane 0b0100000000000000000000000000000 // 对应 OffscreenLane，为最低优先级 0b1000000000000000000000000000000

「批次」则由lanes定义，一个lanes同样也是一个32bit Interger，代表「一到多个 lane 的集合」。

可以用位运算很轻松的将多个lane划入同一个批次：

`// 要使用的批次
let lanesForBatch = 0;

const laneA = 0b0000000000000000000000001000000;
const laneB = 0b0000000000000000000000000000001;

// 将 laneA 纳入批次中
lanesForBatch |= laneA;
// 将 laneB 纳入批次中
lanesForBatch |= laneB;

`

上文提到的Suspense的bug是由于expirationTime 算法不能灵活划定批次导致的。

lanes就完全没有这种顾虑，任何想划定为同一**「批次」**的优先级（lane）都能用位运算轻松搞定。

Lane 算法在线 Demo[2]

总结

**「调度算法」**要解决两个问题：

1. 选取优先级
2. 选取批次

expirationTime 算法中使用的expirationTime字段耦合了这两个概念，导致不够灵活。

Lane 算法的出现解决了以上问题。

参考资料

[1]

expirationTime 算法在线 Demo: https://codesandbox.io/s/usetransition-stop-reacting-passed-props-updates-forked-5e7lh

[2]

Lane 算法在线 Demo: https://codesandbox.io/s/usetransition-stop-reacting-passed-props-updates-zoqm2?file=/src/index.js
https://mp.weixin.qq.com/s/tkEYtRTrZovA4uVrfnNUDQ