從框架作者角度聊：React調度算法的迭代過程

作者：卡頌 2022-01-10 08:31:29

開發前端算法

在render過程中，如果又觸發交互流程，步驟2又選出一個更高優先級，則之前的render中斷，以新的優先級重新開始render。

大家好，我卡頌。

React內部最難理解的地方就是「調度算法」，不僅抽象、復雜，還重構了一次。

可以說，只有React團隊自己才能完全理解這套算法。

既然這樣，那本文嘗試從React團隊成員的視角出發，來聊聊「調度算法」。

什么是調度算法

React在v16之前面對的主要性能問題是：當組件樹很龐大時，更新狀態可能造成頁面卡頓，根本原因在于：更新流程是「同步、不可中斷的」。

為了解決這個問題，React提出Fiber架構，意在「將更新流程變為異步、可中斷的」。

最終實現的交互流程如下：

不同交互產生不同優先級的更新(比如onClick回調中的更新優先級最高，useEffect回調中觸發的更新優先級一般)
「調度算法」從眾多更新中選出一個優先級作為本次render的優先級
以步驟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可以解決以下問題：

組件樹邏輯復雜導致更新時卡頓(因為組件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(并發模式)。

一個無法解決的bug

那么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[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]

總結

「調度算法」要解決兩個問題：

選取優先級
選取批次

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

責任編輯：姜華來源：魔術師卡頌

React 組件前端