关于javascript:从框架作者角度聊React调度算法的迭代过程

大家好，我卡颂。

React外部最难了解的中央就是 调度算法，不仅形象、简单，还重构了一次。

能够说，只有 React 团队本人能力齐全了解这套算法。

既然这样，那本文尝试从 React 团队成员的视角登程，来聊聊 调度算法。

欢送退出人类高质量前端框架群，带飞

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

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

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

不同交互产生不同优先级的更新（比方 onClick 回调中的更新优先级最高，useEffect回调中触发的更新优先级个别）
调度算法 从泛滥更新中选出一个 优先级 作为本次 render 的优先级
以步骤 2 抉择的 优先级 对组件树进行render

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

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

调度算法 须要解决的最根本的问题是：如何从泛滥更新中抉择其中一个更新的 优先级 作为本次 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。

Async Mode能够解决以下问题：

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

这些问题统称为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={<div>loading...</div>}>
        <Sub count={count} />
      </Suspense>
      <div>count is {count}</div>
    </>
  );
};

其中：

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

假如申请三秒后返回，现实状况下，申请发动前后 UI 会顺次显示为：

// Sub 内申请发动前
<div class=“sub”>I am sub, count is 0</div>
<div>count is 0</div>

// Sub 内申请发动第 1 秒
<div>loading...</div>
<div>count is 1</div>

// Sub 内申请发动第 2 秒
<div>loading...</div>
<div>count is 2</div>

// Sub 内申请发动第 3 秒
<div>loading...</div>
<div>count is 3</div>

// Sub 内申请胜利后
<div class=“sub”>I am sub, request success, count is 4</div>
<div>count is 4</div>

从用户的视角察看，有两个工作在并发执行：

申请 Sub 的工作（察看第一个 div 的变动）
扭转 count 的工作（察看第二个 div 的变动）

Suspense带来了 多任务并发执行 的直观感触。

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

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

当申请胜利后，正当的逻辑应该是 尽快展现胜利后的 UI。所以 Suspense 对应更新 应该是 高优先级更新。那么，在示例中共有两类更新：

Suspense对应的高优 IO 更新，简称u0
每秒产生的低优 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</div>
<div>count is 0</div>

// Sub 内申请发动第 1 秒
<div>loading...</div>
<div>count is 0</div>

// Sub 内申请发动第 2 秒
<div>loading...</div>
<div>count is 0</div>

// Sub 内申请发动第 3 秒
<div>loading...</div>
<div>count is 0</div>

// Sub 内申请胜利后
<div class=“sub”>I am sub, request success, count is 4</div>
<div>count is 4</div>

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

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

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

所以 expirationTime 算法 并不能很好反对并发更新。

expirationTime 算法在线 Demo

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

这导致 高优 IO 更新 不会与 低优 CPU 更新 划为同一批次。那么 低优 CPU 更新 就必须期待 高优 IO 更新 解决完后再解决。

如果不同更新能依据理论状况灵便划分批次，就不会产生这个bug。

重构火烧眉毛，并且重构的指标很明确：将 优先级 与批次拆分到两个字段中。

新的调度算法被称为 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

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

选取优先级
选取批次

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

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

关于javascript:从框架作者角度聊React调度算法的迭代过程

什么是调度算法

expirationTime 调度算法

如何示意“批次”

IO 密集型场景

一个无奈解决的 bug

呈现 bug 的起因

Lane 调度算法

总结