聊一聊React 優先級隊列的實現方式
我曾經寫了一本書《JavaScript 核心進階》，我用大量文字篇幅以及配套詳細視頻講解，在《V8 的垃圾回收機制底層算法原理》一文中，跟大家介紹了算法上如何從深度優先遍歷，轉向廣度優先遍歷。以及為什么廣度優先遍歷可以做到任務可中斷而深度優先遍歷做不到。又在《數據結構堆》一文中，跟大家分享了如何利用二叉堆實現優先級隊列。
這可就趕巧了，React 的優先級隊列的實現方式，居然跟我書里里介紹的方法幾乎一樣。
一、React 中的優先級隊列
我們來看一下 React 源碼里是怎么寫的。
在這之前，先瞄一眼二叉堆的可視圖形結構如下。這是一個小頂堆。父節點的數字總是比子節點小。
當我想要插入一個節點時，只能從二叉堆結構的最后一個位置插入。但是他插入進來之后，如果優先級不符合小頂堆/大頂堆的比較規則，則需要調整新節點的位置。因此，新的節點需要跟它的父節點進行優先級的比較，然后根據比較結果調整位置，這個比較可能會發生多次，直到完全符合規則為止。
React 源碼里定義了一個 shftUp 來實現這個邏輯。
function siftUp(heap, node, i) {
var index = i;
while (index > 0) {
var parentIndex = index - 1 >>> 1;
var parent = heap[parentIndex];
if (compare(parent, node) > 0) {
// The parent is larger. Swap positions.
heap[parentIndex] = node;
heap[index] = parent;
index = parentIndex;
} else {
// The parent is smaller. Exit.
return;
}
}
}從邏輯里來看，React 實現的是一個小頂堆。數字越小，優先級越高。
在這個基礎之上，React 又封裝了一個更語義化的 push 方法來完成任務節點的插入。傳入的參數 heap 就是 React 源碼里維護的隊列。
function push(heap, node) {
var index = heap.length;
heap.push(node);
siftUp(heap, node, index);
}當小頂堆最頂部的元素被刪掉之后，二叉堆結構就出現了混亂，我們會首先將樹結構中的最后一個節點，補充到堆頂位置。
補充之后，當前的樹結構多半不符合小頂堆的特性，因此我們需要將新的堆頂的元素與它子元素進行比較，找到最小子元素并與其交換位置，這個行為，我們可以稱之為下沉。這個比較可能會發生多次，至少完全符合規則為止。
react 源碼里也提供了一個下沉的方法
function siftDown(heap, node, i) {
var index = i;
var length = heap.length;
var halfLength = length >>> 1;
while (index < halfLength) {
var leftIndex = (index + 1) * 2 - 1;
var left = heap[leftIndex];
var rightIndex = leftIndex + 1;
// If the left or right node is smaller, swap with the smaller of those.
var right = heap[rightIndex];
if (compare(left, node) < 0) {
if (rightIndex < length && compare(right, left) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
heap[index] = left;
heap[leftIndex] = node;
index = leftIndex;
}
} else if (rightIndex < length && compare(right, node) < 0) {
heap[index] = right;
heap[rightIndex] = node;
index = rightIndex;
} else {
// Neither child is smaller. Exit.
return;
}
}
}有了這個方法之后，刪除節點的封裝就比較簡單了。
function pop(heap) {
if (heap.length === 0) {
return null;
}
var first = heap[0];
var last = heap.pop();
if (last !== first) {
heap[0] = last;
siftDown(heap, last, 0);
}
return first;
}React 還提供了一個工具方法 peek，用于獲取當前的堆頂元素。
function peek(heap) {
return heap.length === 0 ? null : heap[0];
}最關鍵的是優先級的比較方法。非常的簡單，就跟 sort 排序需要的參數長得差不多。
function compare(a, b) {
// Compare sort index first, then task id.
var diff = a.sortIndex - b.sortIndex;
return diff !== 0 ? diff : a.id - b.id;
}從 compare 方法中，我們可以發現，React 的優先級的比較，會先比較 sortIndex，然后比較節點 id。我們可以繼續通過源碼學習他們代表的具體含義來進一步理解這個規則。
二、具體的優先級
React 中，有三套不同的優先級機制：事件優先級、Lane 優先級、Scheduler 優先級。他們可以在特定的場景相互轉換，我們這篇文章主要探討 Scheduler 中的優先級規則是如何設計的，在并發模式中，這是最重要的一個部分，Lane 優先級最終也會轉換為 Scheduler 的優先級
React 內部有一個方法 unstable_scheduleCallback，該方法是專門用來調度任務的。
function unstable_scheduleCallback(priorityLevel, callback, options) {
...
}在這個方法中，新的任務節點會被創建。
var newTask = {
id: taskIdCounter++,
callback: callback,
priorityLevel: priorityLevel,
startTime: startTime,
expirationTime: expirationTime,
sortIndex: -1
};我們可以看到，id 屬性是一個遞增值，這個就比較好理解。
sortIndex 的默認值為 -1，但是他后續的邏輯會因為 startTime 與 currentTime 的比較結果重新賦值。
if (startTime > currentTime) {
// This is a delayed task.
newTask.sortIndex = startTime;
push(timerQueue, newTask);
...
} else {
newTask.sortIndex = expirationTime;
push(taskQueue, newTask);
// wait until the next time we yield.
...
}所以這里的三個時間 startTime currentTime expirationTime 就非常關鍵，我們要去一一搞清楚他們都是干什么的。
先來看看 currentTime 的邏輯。
var currentTime = getCurrentTime();/* eslint-disable no-var */
var getCurrentTime;
var hasPerformanceNow = typeof performance === 'object' && typeof performance.now === 'function';
if (hasPerformanceNow) {
var localPerformance = performance;
getCurrentTime = function () {
return localPerformance.now();
};
} else {
var localDate = Date;
var initialTime = localDate.now();
getCurrentTime = function () {
return localDate.now() - initialTime;
};這里做了一個 performance.now() 與 Date.now() 的兼容處理。可能會涉及到部分同學的知識盲區。這里給大家額外科普一下
perfomance.now() 返回值表示從時間源開始算起，到調用該方法時所經歷的時間。單位是 ms。一般來說，當全局對象是 Window 時，時間源會從創建頁面上下文開始算起。
而 Date.now() 的時間源是從 1970 年 1 月 1 日 00:00:00 (UTC) 開始算起。因此，React 源碼里，會在 JS 邏輯里重新定義一個初始時間源，然后用調用時的當前時間減去初始時間源，這樣他們所表達的含義就基本一致了。
所以，getCurrentTime() 表達的含義為，頁面創建之初，到當前我調用該方法時，這中間經歷的時間（ms）。
我們再來看 startTime 的含義。
他的邏輯如下：
var startTime;
if (typeof options === 'object' && options !== null) {
var delay = options.delay;
if (typeof delay === 'number' && delay > 0) {
startTime = currentTime + delay;
} else {
startTime = currentTime;
}
} else {
startTime = currentTime;
}可以看到，startTime 基本上都是等于 currentTime，不過當 unstable_scheduleCallback 傳入合理的 delay 時，則會在 currentTime 的基礎之上，加上 delay 的值，例如：
unstable_scheduleCallback(NormalPriority, cb, { delay: 2000 });最后我們來看一下 expirationTime 的邏輯，發現他最終的值與 priorityLevel 有關。
var timeout;
switch (priorityLevel) {
case ImmediatePriority:
timeout = IMMEDIATE_PRIORITY_TIMEOUT;
break;
case UserBlockingPriority:
timeout = USER_BLOCKING_PRIORITY_TIMEOUT;
break;
case IdlePriority:
timeout = IDLE_PRIORITY_TIMEOUT;
break;
case LowPriority:
timeout = LOW_PRIORITY_TIMEOUT;
break;
case NormalPriority:
default:
timeout = NORMAL_PRIORITY_TIMEOUT;
break;
}
var expirationTime = startTime + timeout;那我們再往上追溯一下幾個常量的值。
// 表示已經到期，立即執行
var IMMEDIATE_PRIORITY_TIMEOUT = -1;
var USER_BLOCKING_PRIORITY_TIMEOUT = 250;
var NORMAL_PRIORITY_TIMEOUT = 5000;
// 設置一個大值，表示永不過期
var LOW_PRIORITY_TIMEOUT = 10000;
// Tasks are stored on a min heap
var IDLE_PRIORITY_TIMEOUT = maxSigned31BitInt;那么此時任務過期時間 expirationTime 所代表的含義就非常明確了。
這樣，我們再回過頭來去看優先級比較的 sortIndex 邏輯。
if (startTime > currentTime) {
// This is a delayed task.
newTask.sortIndex = startTime;
push(timerQueue, newTask);
...
} else {
newTask.sortIndex = expirationTime;
push(taskQueue, newTask);
// wait until the next time we yield.
...
}我們可以得出如下結論。
首先，sortIndex 值越大，優先級越低。
其次，React 源碼里會維護兩個隊列。
var taskQueue = [];
// Incrementing id counter. Used to maintain insertion order.
var timerQueue = [];當我們在調度一個任務時，如果傳入 delay 值，任務會進入 timerQueue，優先級 由 delay 決定，當 delay 值越大，優先級越低。
如果不傳入 delay， 任務會直接進入 taskQueue，優先級由上面幾個常量值來決定，值越大，優先級越低。
timerQueue 中的任務，會結合 setTimeout，在 delay 結束時 push 到 taskQueue 中。然后根據優先級執行。
閱讀過我在 《JavaScript 核心進階》 中的 Event Loop 章節的同學應該可以聯想到，這里的 timerQueue，跟我們在事件循環里的講的 [[PromiseFulfillReactions]] 隊列非常相似。
這就是 React 的優先級調度器邏輯。
有了這一套基礎邏輯，我們就可以在此基礎之上，非常方便的實現
- 高優先級插隊
- 任務切片
- 任務中斷
- 任務延遲
這里就不再繼續擴展，留給大家去探索。
三、思考
不知道大家有沒有玩過網易的手游陰陽師。一個回合制游戲，這個游戲的戰斗畫場景中，出手順序是按照角色/式神的速度屬性值來決定的，速度越快，越早出手。但是呢，這個游戲還設定了一個非常有意思的機制，那就是他給場上角色設置了一個出手進度條，你速度越快，進度條跑得就越快，誰跑得越快，就越早出手。除此之外，還有很多技能可以提高進度條的進度，也可以有技能擊退別人的進度條。這個機制給 PK 帶來了非常多的新玩法
比如，速度慢的出手優先級，會隨著時間的推移變得越來越高。理解這個現象非常的重要，但是在我們剛才的實現機制中其實已經做到了這一點。因為 getCurrentTime 獲取到的時間，會隨著時間的推移變得越來越大，因此新任務的 currentTime 總比老任務更大，優先級就更低。
又比如，速度快的，可能出手了兩次，速度慢的，都沒機會出手。我們可以用優先出手的式神釋放一個技能去擊退目標的進度條，去降低他的出手優先級。也就是說，我們可以在優先級高的任務邏輯里，擊退低優先級任務的 expirationTime，讓它的優先級進一步變低，這樣它就有可能總是會被高優先級的任務插隊。
因此，我們可以借鑒 react 里的任務調度機制來實現陰陽師戰斗的這個邏輯。
我的解釋可能不那么詳細，不過玩過陰陽師的朋友估計能理解我大概說的是什么，可以思考一下這個機制的具體實現，想清楚了拿下網易的 offer 沒難度！
