示例代碼托管在: "http://www.github.com/dashnowords/blogs" 博客園地址: "《大史住在大前端》原創博文目錄" 華為雲社區地址: "【你要的前端打怪升級指南】" [TOC] 一.概述 模塊相關的邏輯較為複雜,不僅包含JavaScript層的實現,也包括C++編 ...
目錄
示例代碼托管在:http://www.github.com/dashnowords/blogs
博客園地址:《大史住在大前端》原創博文目錄
華為雲社區地址:【你要的前端打怪升級指南】
一.概述
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<Value>& 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
的相關原理,筆者尚未深入涉獵,以後有機會再寫。