【nodejs原理&;源碼雜記（8）】Timer模塊與基于二叉堆的定時器（nodejs 原理）

示例代碼托管在：http://www.github.com/dashnowords/blogs

博客園地址：《大史住在大前端》原創博文目錄

華為云社區地址：【你要的前端打怪升級指南】

【nodejs原理&源碼雜記（8）】Timer模塊與基于二叉堆的定時器一.概述二. 數據結構2.1 鏈表2.2 二叉堆三. 從setTimeout理解Timer模塊源碼3.1 timers.js中的定義3.2 Timeout類定義3.3 active(timeout)3.4 定時器的處理執行邏輯3.5 實例分析四. 小結

一.概述

Timer模塊相關的邏輯較為復雜，不僅包含JavaScript層的實現，也包括C++編寫的與底層libuv協作的代碼，想要完整地看明白是比較困難的，本章僅以setTimeout這個API的實現機制為主線，講述源碼中的JavaScript相關的實現部分，這部分只需要一些數據結構的基本知識就可以理解。

二. 數據結構

setTimeout這個API的實現基于兩類基本數據結構，我們先來復習一下相關的特點。對數據結構知識比較陌生的小伙伴可以參考【野生前端的數據結構基礎練習】系列博文自行學習，所有的章節都有示例代碼。

2.1 鏈表

鏈表是一種物理存儲單元上非連續的存儲結構，存儲元素的邏輯順序是由鏈表中的指針鏈接次序來決定的。每一個節點包含一個存放數據的數據域和存放下一個節點的指針域（雙向鏈表中指針數量為2）。鏈表在插入元素時的時間復雜度為O(1)（因為只影響插入點前后的節點，無論鏈表有多大），但是由于空間不連續的特點，訪問一個未排序鏈表的指定節點時就需要逐個對比，時間復雜度為O(n)，比數組結構就要慢一些。鏈表結構也可以根據指針特點分為單向鏈表,雙向鏈表和循環鏈表，Timer模塊中使用的鏈表結構就是雙向循環鏈表,Node.js中源碼的底層數據結構實現都是獨立的，鏈表的源碼放在lib/internal/linkedlist.js：

'use strict';

function init(list) {

list._idleNext = list;

list._idlePrev = list;

}

// Show the most idle item.

function peek(list) {

if (list._idlePrev === list) return null;

return list._idlePrev;

}

// Remove an item from its list.

function remove(item) {

if (item._idleNext) {

item._idleNext._idlePrev = item._idlePrev;

}

if (item._idlePrev) {

item._idlePrev._idleNext = item._idleNext;

}

item._idleNext = null;

item._idlePrev = null;

}

// Remove an item from its list and place at the end.

function append(list, item) {

if (item._idleNext || item._idlePrev) {

remove(item);

}

// Items are linked ?with _idleNext -> (older) and _idlePrev -> (newer).

// Note: This linkage (next being older) may seem counter-intuitive at first.

item._idleNext = list._idleNext; //1

item._idlePrev = list;//2

// The list _idleNext points to tail (newest) and _idlePrev to head (oldest).

list._idleNext._idlePrev = item;//3

list._idleNext = item;//4

}

function isEmpty(list) {

return list._idleNext === list;

}

鏈表實例初始化了兩個指針，初始時均指向自己，_idlePrev指針將指向鏈表中最新添加進來的元素，_idleNext指向最新添加進來的元素，實現的兩個主要操作為remove和append。鏈表的remove操作非常簡單，只需要將刪除項前后的元素指針加以調整，然后將被刪除項的指針置空即可，就像從一串鎖鏈中拿掉一節，很形象。

源碼中的idlePrev和idleNext很容易混淆，建議不用強行翻譯為“前后”或者“新舊”，（反復記憶N次都記不住我也很無奈），直接按對應位置來記憶就可以了，愛翻譯成什么就翻譯成什么。

源碼中的鏈表實現并沒有提供指定位置插入的方法，append( )方法默認只接收list和item兩個參數，新元素會被默認插入在鏈表的固定位置，這與它的使用方式有關，所以沒必要實現完整的鏈表數據結構。append稍微復雜一些，但是源碼中也做了非常詳細的注釋。首先需要確保插入的元素是獨立的（也就是prev和next指針都為null），然后再開始調整，源碼中的鏈表是一個雙向循環鏈表，我們調整一下源碼的順序會更容易理解，其實插入一個元素就是要將各個元素的prev和next兩個指針調整到位就可以了。先來看_idlePrev指針鏈的調整， 也就是指針調整代碼中標記為2和3的語句：

item._idlePrev = list;//2

list._idleNext._idlePrev = item;//3

這里可以把list看作是一個prev指針連接起來的單向鏈表，相當于將新元素item按照prev指針的指向添加到list和原本的list._idleNext指向的元素中間，而1和4語句是調整了反方向的next指針鏈：

item._idleNext = list._idleNext; //1

list._idleNext = item;//4

調整后的鏈表以next指針為依據就可以形成反方向的循環鏈表，然后只需要記住list._idleNext指針指向的是最新添加的項就可以了。

如上圖所示，next和prev分別可以作為鏈表的邏輯順序形成循環鏈。

2.2 二叉堆

源碼放在lib/internal/priority_queue.js中，一些博文也直接翻譯為優先隊列，它們是抽象結構和具體實現之間的關系，特性是一致的。二叉堆是一棵有序的完全二叉樹，又以節點與其后裔節點的關系分為最大堆和最小堆。完全二叉樹的特點使其可以很容易地轉化為一維數組來存儲，且不需要二外記錄其父子關系，索引為i的節點的左右子節點對應的索引為2i+1和2i+2(當然左右子節點也可能只有一個或都不存在)。Node.js就使用一維數組來模擬最小堆。源碼基本上就是這一數據結構和“插入”，“刪除”這些基本操作的實現。

堆結構的使用最主要的是為了獲得堆頂的元素，因為它總是所有數據里最大或最小的，同時堆結構是一個動態調整的數據結構，插入操作時會將新節點插入到堆底，然后逐層檢測和父節點值的相對大小而“上浮”直到整個結構重新變為堆；進行移除操作（移除堆頂元素也是移除操作的一種）時，需要將堆尾元素置換到移除的位置，以維持整個數據結構依然是一棵完全二叉樹，然后通過與父節點和子節點進行比較來決定該位置的元素應該“上浮”或“下沉”，并遞歸這個過程直到整個數據結構被重建為堆。相關的文章非常，本文不再贅述（可以參考這篇博文【二叉堆的添加和刪除元素方法】，有動畫好理解）。

三. 從setTimeout理解Timer模塊源碼

timer模塊并不需要手動引入，它的源碼在/lib/timers.js目錄中，我們以這樣一段代碼來看看setTimeout方法的執行機制：

setTimeout(()=>{console.log(1)},1000);

setTimeout(()=>{console.log(2)},500);

setTimeout(()=>{console.log(3)},1000);

3.1 timers.js中的定義

最上層方法的定義進行了一些參數格式化，將除了回調函數和延遲時間以外的其他參數組成數組（應該是用apply來執行callback方法時把這些參數傳進去），接著做了三件事，生成timeout實例，激活實例，返回實例。

3.2 Timeout類定義

Timeout類定義在【lib/internal/timers.js】中：

初始化了一些屬性，可以看到傳入構造函數的callback,after,args都被記錄下來，可以看到after的最小值為1ms，Timeout還定義了一些原型方法可以先不用管，然后調用了initAsyncResource( )這個方法，它在實例上添加了[async_id_symbol]和[trigger_async_id_symbol]兩個標記后，又調用了emitInit( )方法將這些參數均傳了進去，這個emitInit( )方法來自于/lib/internal/async_hooks.js，官方文檔對async_hook模塊的解釋是：

The?async_hooks?module provides an API to register callbacks tracking the lifetime of asynchronous resources created inside a Node.js application.

它是一個實驗性質的API，是為了Node.js內部創建的用于追蹤異步資源生命周期的模塊，所以推測這部分邏輯和執行機制關系不大，可以先擱在一邊。

3.3 active(timeout)

獲得了timeout實例后再回到上層函數來，接下來執行的是active(timeout)這個方法，它調用的是insert( item, true, getLibuvNow()),不難猜測最后這個方法就是從底層libuv中獲取一個準確的當前時間，insert方法的源碼如下：

首先為timeout實例添加了開始執行時間idleStart屬性，接下來的邏輯涉及到兩個對象，這里提前說明一下：timerListMap是一個哈希表，延時的毫秒數為key，其value是一個雙向鏈表，鏈表中存放著timeout實例，所以timerListMap就相當于一個按延時時間來分組存放定時器實例的Hash+linkedList結構，另一個重要對象timerListQueue就是上面講過的優先隊列（后文使用“二叉堆”這一概念）。

這里有一個小細節，就是將新的定時器鏈表加入二叉堆時，比較函數是自定義傳入的，在源碼中很容易看到compareTimersLists ( )這個方法使用鏈表的expiry屬性的值進行比較來得到最小堆，由此可以知道，堆頂的鏈表總是expiry最小的，也就是說堆頂鏈表的__idlePrev指向的定時器，就是所有定時器里下一個需要觸發回調的。

接下來再來看看active( )函數體的具體邏輯，如果有對應鍵的鏈表則獲取到它（list變量），如果沒有則生成一個新的空鏈表，然后將這個鏈表添加進二叉堆，跳過中間的步驟，在最后可以看到執行了：

L.append(list,?item);

這個L實際上是來自于前文提過的linkedList.js中的方法，就是將timeout實例添加到list鏈表中，來個圖就很容易理解了：

中間我們跳過了一點邏輯，就是在新鏈表生成時執行的:

if(nextExpiry > expiry){

scheduleTimer(msecs);

nextExpiry = expiry;

}

nextExpiry是timer模塊中維護的一個模塊內的相對全局變量，這里的expiry是新鏈表的下一個定時器的過期時間（也就是新鏈表中唯一一個timeout實例的過期時間）,這里針對的情況就是新生成的定時器比已存在的所有定時器都要更早觸發，這時就需要重新調度一下，并把當前這個定時器的過期時間點設置為nextExpiry時間。

這個scheduleTimer( )使用internalBinding('timers')引入的，在lib/timer.cc中找到這個方法：

void ScheduleTimer(const FunctionCallbackInfo& args) {

auto env = Environment::GetCurrent(args);

env->ScheduleTimer(args[0]->IntegerValue(env->context()).FromJust());

}

再跳到env.cc:

void Environment::ScheduleTimer(int64_t duration_ms) {

if (started_cleanup_) return;

uv_timer_start(timer_handle(), RunTimers, duration_ms, 0);

}

可以看到這里就將定時器的信息和libuv的事件循環聯系在一起了，libuv還沒有研究，所以這條邏輯線暫時到此為止。再回到之前的示例，當三個定時器都添加完成后，內存中的對象關系基本是下面的樣子：

3.4 定時器的處理執行邏輯

至此我們已經將定時器的信息都存放好了，那么它是如何被觸發的呢？我們找到node.js的啟動文件lib/internal/bootstrap/node.js284-290行，可以看到，在啟動函數中，Node.js通過調用setTimers( )方法將定時器處理函數processTimers傳遞給了底層，它最終會被用來調度執行定時器，processTimers方法由lib/internal/timers.js中提供的getTimerCallbacks(runNextTicks) 方法運行得到，所以聚焦到/lib/internal/timers.js中：

推測libuv每次需要檢查是否有定時器到期時都會運行processTimers( )方法，來看一下對應的邏輯，一個無限循環的while語句，直到二叉堆的堆頂沒有任何定時器時跳出循環并返回0。在循環體內部，會用堆頂元素的過期時間和當前時間相比，如果list.expiry更大，說明時機未到還不需要執行，把它的過期時間賦值給nextExpiry然后返回（返回邏輯先不細究）。如果邏輯執行到471行，說明堆頂元素的過期時間已經過了，ranAtLeastOneList這個標記位使得這段邏輯按照如下方式運行：

1.獲取到一個expiry已經過期的鏈表,首次向下執行時`ranAtLeastOneList`為false，則將其置為true，然后執行`listOnTimeout()`這個方法;

2.然后繼續取堆頂的鏈表，如果也過期了，再次執行時，會先執行`runNextTicks()`，再執行`listOnTimeout()`。

我們按照邏輯順序，先來看看listOnTimeout( )這個方法，它有近100行（我們以上面3個定時器的實例來看看它的執行邏輯）：

function listOnTimeout(list, now) {

const msecs = list.msecs; //500 , 500ms的鏈表在堆頂

debug('timeout callback %d', msecs);

var diff, timer;

let ranAtLeastOneTimer = false;

while (timer = L.peek(list)) { ?//取鏈表_idlePrev指向的定時器，也就是鏈表中最先到期的

diff = now - timer._idleStart; ?//計算當前時間和它開始計時那個時間點的時間差，

// Check if this loop iteration is too early for the next timer.

// This happens if there are more timers scheduled for later in the list.

// 原文翻譯：檢測當前事件循環對于下一個定時器是否過早，這種情況會在鏈表中還有其他定時器時發生。

// 人話翻譯：就是當前的時間點只需要觸發鏈表中第一個500ms定時器，下一個500ms定時器還沒到觸發時間。

// ? ? ? ? 極端的相反情況就是由于阻塞時間已經過去很久了，鏈表里的N個定時器全都過期了，都得執行。

if (diff < msecs) {

//更新鏈表中下一個到期定時器的時間記錄，計算邏輯稍微有點繞

list.expiry = Math.max(timer._idleStart + msecs, now + 1);

list.id = timerListId++;

timerListQueue.percolateDown(1);//堆頂元素值發生更新，需要通過“下沉”來重構“堆”

debug('%d list wait because diff is %d', msecs, diff);

return; //直接結束了

}

//是不是貌似見過這段，先放著等會一塊說

if (ranAtLeastOneTimer)

runNextTicks();

else

ranAtLeastOneTimer = true;

// The actual logic for when a timeout happens.

L.remove(timer);

const asyncId = timer[async_id_symbol];

if (!timer._onTimeout) {

if (timer[kRefed])

refCount--;

timer[kRefed] = null;

if (destroyHooksExist() && !timer._destroyed) {

emitDestroy(asyncId);

timer._destroyed = true;

}

continue;

}

emitBefore(asyncId, timer[trigger_async_id_symbol]);

let start;

if (timer._repeat) //這部分看起來應該是interval的邏輯，interval底層實際上就是一個重復的timeout

start = getLibuvNow();

try {

const args = timer._timerArgs;

if (args === undefined)

timer._onTimeout(); ?//設置定時器時傳入的回調函數被執行了

else

timer._onTimeout(...args);

} finally {

if (timer._repeat && timer._idleTimeout !== -1) {

timer._idleTimeout = timer._repeat;

if (start === undefined)

start = getLibuvNow();

insert(timer, timer[kRefed], start);//interval的真實執行邏輯，重新獲取時間然后插入到鏈表中

} else if (!timer._idleNext && !timer._idlePrev) {

if (timer[kRefed])

refCount--;

timer[kRefed] = null;

if (destroyHooksExist() && !timer._destroyed) {

emitDestroy(timer[async_id_symbol]);

timer._destroyed = true;

}

}

}

emitAfter(asyncId);

}

//這塊需要注意的是，上面整個邏輯都包在while(timer = L.peek(list)){...}里面

// If `L.peek(list)` returned nothing, the list was either empty or we have

// called all of the timer timeouts.

// As such, we can remove the list from the object map and

// the PriorityQueue.

debug('%d list empty', msecs);

// The current list may have been removed and recreated since the reference

// to `list` was created. Make sure they're the same instance of the list

// before destroying.

// 原文翻譯：當前的list標識符所引用的list有可能已經經過了重建，刪除前需要確保它指向哈希表中的同一個實例。

if (list === timerListMap[msecs]) {

delete timerListMap[msecs];

timerListQueue.shift();

}

}

3.5 實例分析

代碼邏輯因為包含了很多條件分支，所以不容易理解，我們以前文的實例作為線索來看看定時器觸發時的執行邏輯：

程序啟動后，processTimer( )方法不斷執行，第一個過期的定時器會在堆頂的500ms定時器鏈表（下面稱為500鏈表）中產生，過期時間戳為511。

假設時間戳到達600時程序再次執行processTimer( )，此時發現當前時間已經超過nextExpiry記錄的時間戳511，于是繼續向下執行進入listOnTimeout(list, now)，這里的list就是哈希表中鍵為500的鏈表，now就是當前時間600，進入listOnTimeout方法后，獲取到鏈表中最早的一個定時器timer,然后計算diff參數為600-11=589, 589 > 500， 于是繞過條件分支語句，ranAtLeastOneTimer為false也跳過（跳過后其值為true），接下來的邏輯從鏈表中刪除了這個timer，然后執行timer._onTimeout指向的回調函數，500鏈表只有一個定時器，所以下一循環時L.peek(list)返回null，循環語句跳出，繼續向后執行。此時list依然指向500鏈表，于是執行刪除邏輯，從哈希表和二叉堆中均移除500鏈表，兩個數據結構在底層會進行自調整。

processTimer( )再次執行時，堆頂的鏈表變成了1000ms定時器鏈表（下面稱為1000鏈表），nextExpiry賦值為list.expiry，也就是1001，表示1000ms定時器鏈表中下一個到期的定時器會在時間戳超過1001時過期，但時間還沒有到。下面分兩種情況來分析：

1.時間戳為1010時執行processTimer( )

時間來到1010點，processTimer( )被執行，當前時間1010大于nextExpiry=1001，于是從堆頂獲取到1000鏈表，進入listOnTimeout( )，第一輪while循環執行時的情形和500鏈表執行時是一致的，在第二輪循環中，timer指向1000鏈表中后添加的那個定時器，diff的值為 1010 - 21 = 989,989 < 1000 ,所以進入if(diff < msecs)的條件分支，list.expiry調整為下一個timer的過期時間1021，然后通過下沉來重建二叉堆（堆頂元素的expiry發生了變化），上面的實例中只剩了唯一一個鏈表，所以下沉操作沒有引發什么實質影響，接著退出當前函數回到processTimer的循環體中，接著processTimer里的while循環繼續執行，再次檢查棧頂元素，時間還沒到，然后退出，等時間超過下一個過期時間1021后，最后一個定時器被觸發，過程基本一致，只是鏈表耗盡后會觸發listOnTimeout后面的清除哈希表和二叉堆中相關記錄的邏輯。

總結一下，鏈表的消耗邏輯是，從鏈表中不斷取出peek位置的定時器，如果過期了就執行，如果取到一個沒過期的，說明鏈表里后續的都沒過期，就修改鏈表上的list.expiry屬性然后退回到processTimer的循環體里，如果鏈表耗盡了，就將它從哈希表和二叉堆中把這個鏈表刪掉。

2.時間戳為1050時執行processTimer( )

假如程序因為其他原因直到時間為1050時才開始檢查1000鏈表，此時它的兩個定時器都過期了需要被觸發，listOnTimeout( )中的循環語句執行第一輪時是一樣的，第二次循環執行時，跳過if(diff < msecs)的分支，然后由于ranAtLeastOneTimer標記位的變化，除了第一個定時器的回調外，其他都會先執行runNextTicks( )然后再執行定時器上綁的回調，等到鏈表耗盡后，進入后續的清除邏輯。

我們再來看一種更極端的情況，假如程序一直阻塞到時間戳為2000時才執行到processTimer(此時3個定時器都過期了，2個延遲1000ms，1個延遲500ms，堆頂為500ms鏈表)，此時processTimer( )先進入第一次循環，處理500鏈表，然后500鏈表中唯一的定時器處理完后，邏輯回到processTimer的循環體，再進行第二輪循環，此時獲取到堆頂的1000鏈表，發現仍然需要執行，那么就會先執行runNextTicks( )，然后在處理1000鏈表，后面的邏輯就和上面時間戳為1050時執行processTimer基本一致了。

至此定時器的常規邏輯已經解析完了，還有兩個細節需要提一下，首先是runNextTicks( )，從名字可以推測它應該是執行通過process.nextTick( )添加的函數，從這里的實現邏輯來看，當有多個定時器需要觸發時，每個間隙都會去消耗nextTicks隊列中的待執行函數，以保證它可以起到“盡可能早地執行”的職責，對此不了解的讀者可以參考上一篇博文【譯】Node.js中的事件循環，定時器和process.nextTick。

四. 小結

timer模塊比較大，在了解基本數據結構的前提下不算特別難理解，setImmediate( )和process.nextTick( )的實現感興趣的讀者可以自行學習，想要對事件循環機制有更深入的理解，需要學習C++和libuv的相關原理，筆者尚未深入涉獵，以后有機會再寫。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。