好文翻譯丨深入解讀 V8 引擎的「並發標記」技術

參與翻譯 (6人) : kevinlinkai, Tocy, 琪花億草, 豆豆胡蘿蔔, 焙焙龍, 涼涼_

本文詳細描述了被稱為並發標記的垃圾回收技術。該優化允許 JavaScript 應用在垃圾回收器掃描其堆以查找和標記活動對象時可繼續執行。我們的基準測試顯示，並發標記相比在主線程上標記節省了 60％-70％ 的時間。並發標記是 Orinoco 項目的最後一塊拼圖 - 使用新的多並發和並行垃圾回收機制增量地替換舊的垃圾回收機制的項目。Chrome 64 和 Node.js v10 默認啟用並發標記。

背景

標記是 V8 的 Mark-Compact 垃圾收集器的一個階段。在這個階段中，收集器發現並標記了所有的活動對象。標記從一組已知的活動對象開始，例如全局對象和當前活動函數——所謂的根。收集器將根標記為活動的，並跟隨指針來發現更多的活動對象。收集器繼續標記新發現的對象並跟隨標記指針，直到沒有需要標記的對象為止。在標記結束時，應用程序無法訪問堆中未被標記的對象，並且可以安全的回收。

我們可以將標記認為是圖遍歷。堆上的對象是圖的節點。從一個對象指向另一個對象是圖的邊。從圖中給一個節點，我們可以使用對象隱藏的類找出該節點所有外出邊。

V8 使用每個對象的兩個標記位和一個標記工作表來實現標記。兩個標記位編碼三種顏色：白色（00），灰色（10）和黑色（11）。最初所有的對象都是白色，意味著收集器還沒有發現他們。當收集器發現一個對象時，將其標記為灰色並推入到標記工作表中。當收集器從標記工作表中彈出對象並訪問他的所有欄位時，灰色就會變成黑色。這種方案被稱做三色標記法。當沒有灰色對象時，標記結束。所有剩餘的白色對象無法達到，可以被完全的回收。

需要注意的是，上述標記法僅適用於在標記進行中應用程序暫停的情況。如果我們允許應用程序在標記過程中運行，那麼應用程序可能改變圖並且最終欺騙收集器釋放活動對象。

減少標記暫停

一次執行標記可能需要幾百毫秒才能完成一個大的堆。

這樣長時間的停頓可能會導致應用程序無響應，並導致用戶體驗不佳。在2011年，V8 從 stop-the-world 標記切換到增量標記。在增量標記期間，垃圾收集器將標記工作分解為更小的塊，並且允許應用程序在塊之間運行：

垃圾收集器選擇在每個塊中執行多少增量標記來匹配應用程序的分配速率。一般情況下，這極大地提高了應用程序的相應速度。對內存壓力較大的堆，收集器仍然可能出現長時間的暫停來維持分配。

增量標記不是沒有代價的。應用程序必須通知垃圾收集器關於改變對象圖的所有操作。V8 使用 Dijkstra 風格的 write-barrier 機制來實現通知。在 JavaScript 中，每次表單 object.field = value 的寫操作之後，V8 會插入 write-barrier 代碼。

// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
if (color(object) == black && color(value) == white) {
set_color(value, grey);
marking_worklist.push(value);
}
}

Write-barrier 機制強制不變黑的對象指向白色對象。這也被稱為強三色不變性，保證應用程序不能在垃圾收集器中隱藏活動對象，因此標記結束時的所有白色對象對於應用程序來說都是不可達的，可以安全釋放。

就像早期博客中描述的那樣，增量標記很好的集成了空閑時間垃圾收集調度。Chrome 的 Blink 任務調度程序可以在主線程的空閑時間調度小的增量標記步驟，而不會造成混亂。如果空閑時間可用，該優化效果將會非常好。

由於 Write-barrier 機制的成本，增量標記可能會降低應用程序的吞吐量。通過使用額外的工作線程可以提高吞吐量和暫停時間。有兩種方法可以在工作線程上進行標記：並行標記和並發標記。

並行標記發生在主線程和工作線程上。應用程序在整個並行標記階段暫停。它是 stop-the-world 標記的多線程版本。

並發標記主要發生在工作線程上。當並發標記正在進行時，應用程序可以繼續運行。

下面兩節描述我們如何在 V8 中添加對並行和並發標記的支持。

並行標記

在並行標記的時候，我們可以假定應用都不會同時運行。這大大的簡化了實現，是因為我們可以假定對象圖是靜態的，而且不會改變。為了並行標記對象圖，我們需要讓垃圾收集數據結構是線程安全的，而且尋找一個可以在線程間運行的高效共享標記的方法。下面的示意圖展示了並行標記包含的數據結構。箭頭代表數據流的方向。簡單來說，示意圖省略了堆碎片處理所需的數據結構。

注意，這些線程只能讀取對象圖，而不能修改它。對象的標記位和標記列表必須支持讀寫訪問。

標記工作列表和工作竊取（work stealing）

標記工作列表的實現對性能至關重要，而且它通過在其他線程沒有工作可做的情況下，有多少工作可以分配給他們，來平衡快速線程本地的性能。

要權衡的兩個極端的情況是（a）使用完全並發數據結構，達成最佳共享即所有對象都可以隱式共享，和（b）使用完全線程本地數據結構，沒有對象可以共享，優化線程本地吞吐量。圖6展示了 V8 是如何通過使用一個基於線程本地插入和刪除的段的標記工作列表來平衡這些需求的。一旦一個段滿了，它會被發布到一個可以用來竊取的共享全局池。使用這種方法，V8 允許標記線程在不用任何同步的情況下儘可能長的執行本地操作，而且還處理了當單個線程達成了一個新的對象子圖，而另一個線程在完全耗盡了本地段時飢餓的情況。

並發標記

並發標記允許 JavaScript 在主線程上運行，而工作線程正在訪問堆上的對象。這為潛在的競態數據打開大門。舉個例子：當工作者線程正在讀取欄位時，JavaScript 可能正在寫入對象欄位。競態數據會混淆垃圾回收器釋放活動對象或者將原始值和指針混合在一起。

主線程的每個改變對象圖表的操作將會是競態數據的潛在來源。由於 V8 是具有多種對象布局優化功能的高性能引擎，潛在競態數據來源目錄相當長。以下是高層次故障：

• 對象分配
• 寫對象
• 對象布局變化
• 快照反序列化
• 功能脫優化實現
• 年輕代垃圾回收期間的疏散
• 代碼修補

在以上這些操作上，主線程需要與工作線程同步。同步代價和複雜度是操作而定。大部分操作允許輕量級的同步和院子操作之間的訪問，但是少部分操作需獨佔訪問對象。在下面的小節中我們強調一些有趣的案例。

寫屏障

通過寫入對象欄位導致的數據競爭通過將寫入操作轉變為放寬原子寫入並調整寫入屏障來解決：

// Called after atomic_relaxed_write(&object.field, value);
write_barrier(object, field_offset, value) {
if (color(value) == white && atomic_color_transition(value, white, grey)) {
marking_worklist.push(value);
}
}

與上面的寫屏障進行比較

// Called after `object.field = value`.
write_barrier(object, field_offset, value) {
if (color(object) == black && color(value) == white) {
set_color(value, grey);
marking_worklist.push(value);
}
}

這有兩個變化：

1 color檢查原對象(color(object) == black)操作不存在

2 color值由白色轉變為灰色操作變成原子操作

如果沒有color原對象檢查，寫屏障變得更保守。舉個例子，只要對象存在都會標記他們就算那些對象是無法獲取的。我們刪除了這個檢查以避免在寫操作和寫障礙之間需要昂貴的內存柵欄（memory fence）：

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

沒有內存柵欄（memory fence），color對象載入操作在寫操作之前將會被重排序。如果我們不阻止重排序，寫屏障觀察到grey object color並釋放，而工作線程在沒有看到新值的情況下標記對象。由Dijkstra等人提出的原始寫屏障不會檢查color對象。他們為了簡單起見，但是我們需要他們的正確性

Bailout worklist

某些操作（例如代碼打補丁）需要獨佔訪問該對象。在早期，我們決定避免每個對象的鎖，因為它們可能導致優先順序反轉問題，其中主線程必須等待一個持有該對象鎖的非調度的工作線程。作為鎖定一個對象的替代方案，我們允許工作線程通過訪問該對象來避免這些麻煩。工作線程通過將對象推入Bailout工作清單來完成此功能，該工作清單僅由主線程處理：

工作線程在優化的代碼對象、隱藏類和弱集合上進行處理，因為訪問它們需要加鎖或高開銷的同步協議。

回顧過去，bailout工作清單對增量開發來說是非常有用的。我們開始使用工作線程來處理所有對象類型並逐一添加並發機制。

對象布局更改

對象的欄位可以存儲三種值：標記的指針，標記的小整數（也稱為Smi），或未標記的值，如未裝箱的浮點數。指針標記是一種眾所周知的技術，可以有效地表示未裝箱的整數。在V8中，標記值的最低有效位指示它是指針還是整數。這依賴於指針是字對齊的事實。有關欄位是標記的還是未標記的信息存儲在對象的隱藏類中。

通過將對象轉換為另一個隱藏類，V8中的一些操作將對象欄位從標記變為未標記（反之亦然）。這種對象布局更改對於並發標記是不安全的。如果在工作線程使用舊的隱藏類同時訪問對象時發生更改，則可能會出現兩種類型的錯誤。首先，工作流可能會錯過一個指針，認為這是一個沒有標記的值。使用寫屏障可以防止這種錯誤。其次，工作流可能會將未標記的值視為指針並將其解引用，這會導致無效的內存訪問，通常會導致程序崩潰。為了處理這種情況，我們使用一個在對象標記位上同步的快照協議。該協議涉及兩方面：主線程將對象欄位從標記變為未標記以及工作線程訪問對象。在更改欄位之前，主線程會確保該對象被標記為黑色並將其推入緊急工作清單供以後訪問：

atomic_color_transition(object, white, grey);
if (atomic_color_transition(object, grey, black)) {
// The object will be revisited on the main thread during draining
// of the bailout worklist.
bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

如下面的代碼片段所示，工作線程首先載入對象的隱藏類並使用原子放寬載入操作來快照由隱藏類指定的對象的所有指針欄位。然後它會嘗試使用原子比較和交換操作將對象標記為黑色。如果標記成功，則意味著快照必須與隱藏類一致，因為主線程在更改其布局之前會將對象標記為黑色。

napshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
for (field_offset in pointer_field_offsets(hidden_class)) {
pointer = atomic_relaxed_load(object + field_offset);
snapshot.add(field_offset, pointer);
}
if (atomic_color_transition(object, grey, black)) {
visit_pointers(snapshot);
}

請注意，承受不安全布局更改的被標記為白色對象必須在主線程上標記。不安全的布局變化相對較少，所以這對實際應用程序的性能沒有太大的影響。

把它們放一起

我們將並發標記整合到現有的增量標記基礎設施中。主線程通過掃描根部並填充標記工作表來啟動標記。之後，它會在工作線程中發布並發標記任務。工作線程通過合作排除標記工作表來幫助主線程加快標記進度。偶爾主線程通過處理救援工作表和標記工作表來參與標記。標記工作表變空之後，主線程完成垃圾收集。在最終確定期，主線程重新掃描根部，可能會發現更多的白色對象。這些對象在工作線程的幫助下被並行標記。

結論

我們的真實世界基準測試框架顯示在移動和桌面上每個垃圾回收周期的主線程標記時間分別減少了 65% 和 70% 。

並發標記也減少了 Node.js 中的垃圾收集 jank 。 這點尤其重要，因為 Node.js 從未實現空閑時間垃圾收集調度，因此永遠無法在 non-jank-critical 階段隱藏標記時間。 並發標記在 Node.js v10 中發布。

對於技術達人來說，廣納知識點是進步的源泉。通過閱讀技術文章我們可以學到業務技能，也能了解行業動態。開源中國翻譯頻道旨在每天為用戶推薦並翻譯優質的外網文章。再也不用怕因為英語不過關，被擋在許多技術文章的門外。點擊「了解更多」，獲取往期翻譯文章。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！