3

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

 2 years ago
source link: https://segmentfault.com/a/1190000041268486
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

大家好，我卡颂。

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={<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>

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

  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</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

出现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

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

  1. 选取优先级

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

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK