探索Virtual DOM的前世今生

05-21

探索Virtual DOM的前世今生

來自專欄百度外賣前端

作者：百度外賣程亞傑李顯盧培鵬
轉載請標明出處

緣起

在前端開發過程中，對性能產生最大影響的因素莫過於DOM的重排重繪了，React作為前端框架領跑者，為了有效解決DOM更新開銷的問題，採用了Virtual DOM的思路，不僅提升了DOM操作的效率，更推動了數據驅動式組件開發的形成與完善。一旦習慣了數據驅動式開發，再要求我們使用顯式DOM操作開發的話，虐心程度無異於春節返鄉的車票賣完了，只能坐長途輾轉煎熬了。

而VirtualDOM的主要思想就是模擬DOM的樹狀結構，在內存中創建保存映射DOM信息的節點數據，在由於交互等因素需要視圖更新時，先通過對節點數據進行diff後得到差異結果後，再一次性對DOM進行批量更新操作，這就好比在內存中創建了一個平行世界，瀏覽器中DOM樹的每一個節點與屬性數據都在這個平行世界中存在著另一個版本的虛擬DOM樹，所有複雜曲折的更新邏輯都在平行世界中的VirtualDOM處理完成，只將最終的更新結果發送給瀏覽器中的DOM樹執行，這樣就避免了冗餘瑣碎的DOM樹操作負擔，進而有效提高了性能。

如果你已經是熟練使用vue或者react的項目老手，本文將助你一探這些前端框架進行視圖更新背後的工作原理，並且可以一定程度掌握VirtualDOM的核心演算法，即便你還未享受過這些數據驅動的工具帶來的便利，通過閱讀本文，你也將了解到一些當下的前端框架是如何對開發模式產生巨變影響的。同時本文也是我們對相關知識學習的一個總結，難免有誤，歡迎多多指正，並期待大大們的指點。

Diff效率之爭

VirtualDOM是react在組件化開發場景下，針對DOM重排重繪性能瓶頸作出的重要優化方案，而他最具價值的核心功能是如何識別並保存新舊節點數據結構之間差異的方法，也即是diff演算法。毫無疑問的是diff演算法的複雜度與效率是決定VirtualDOM能夠帶來性能提升效果的關鍵因素。因此，在VirtualDOM方案被提出之後，社區中不斷湧現出對diff的改進演算法，引用司徒正美的經典介紹：

最開始經典的深度優先遍歷DFS演算法，其複雜度為O(n^3)，存在高昂的diff成本，然後是cito.js的橫空出世，它對今後所有虛擬DOM的演算法都有重大影響。它採用兩端同時進行比較的演算法，將diff速度拉高到幾個層次。緊隨其後的是kivi.js，在cito.js的基出提出兩項優化方案，使用key實現移動追蹤及基於key的編輯長度距離演算法應用（演算法複雜度為O(n^2)）。但這樣的diff演算法太過複雜了，於是後來者snabbdom將kivi.js進行簡化，去掉編輯長度距離演算法，調整兩端比較演算法。速度略有損失，但可讀性大大提高。再之後，就是著名的vue2.0 把snabbdom整個庫整合掉了。

因此目前VirtualDOM的主流diff演算法趨向一致，在主要diff思路上，snabbdom與react的reconilation方式基本相同。

Diff主要策略

按tree層級diff(level by level)

由於diff的數據結構是以DOM渲染為目標的模擬樹狀層級結構的節點數據，而在WebUI中很少出現DOM的層級結構因為交互而產生更新，因此VirtualDOM的diff策略是在新舊節點樹之間按層級進行diff得到差異，而非傳統的按深度遍歷搜索，這種通過大膽假設得到的改進方案，不僅符合實際場景的需要，而且大幅降低了演算法實現複雜度，從O(n^3)提升至O(n)。

按類型進行diff

無論VirtualDOM中的節點數據對應的是一個原生的DOM節點還是vue或者react中的一個組件，不同類型的節點所具有的子樹節點之間結構往往差異明顯，因此對不同類型的節點的子樹進行diff的投入成本與產出比將會很高昂，為了提升diff效率，VirtualDOM只對相同類型的同一個節點進行diff，當新舊節點發生了類型的改變時，則並不進行子樹的比較，直接創建新類型的VirtualDOM，替換舊節點。

列表diff

當被diff節點處於同一層級時，通過三種節點操作新舊節點進行更新：插入，移動和刪除，同時提供給用戶設置key屬性的方式調整diff更新中默認的排序方式，在沒有key值的列表diff中，只能通過按順序進行每個元素的對比，更新，插入與刪除，在數據量較大的情況下，diff效率低下，如果能夠基於設置key標識盡心diff，就能夠快速識別新舊列表之間的變化內容，提升diff效率。

Virtual DOM不同的實現方式

基於以上的三條diff原則，我們就可以自由選擇Virtual DOM的具體方案，甚至自己動手進行diff實踐，在那之前，讓我們先以Vue中的snabbdom與React中的Reconcile這兩個Virtual DOM的實現方案為對象進行學習。

snabbdom的vnode

在眾多VirtuaDOM實現方案中，snabbdom以其高效的實現，小巧的體積與靈活的可擴展性脫穎而出，它的核心代碼只有300行+，卻已被適用於vue等輕量級前端框架中作為VirtualDOM的主要功能實現。

一個使用snabbdom創建的demo是這樣的：

import snabbdom from snabbdom;import h from snabbdom/h;const patch = snabbdom.init([ require(snabbdom/modules/class), // makes it easy to toggle classes require(snabbdom/modules/props), // for setting properties on DOM elements require(snabbdom/modules/style), // handles styling on elements with support for animations require(snabbdom/modules/eventlisteners), // attaches event listeners]);var vnode = h(div, {style: {fontWeight: bold}}, Hello world);patch(document.getElementById(placeholder), vnode)

在snabbdom中提供了h函數做為創建VirtualDOM的主要函數，h函數接受的三個參數同時揭示了diff演算法中關注的三個核心：節點類型，屬性數據，子節點對象。而patch方法即是用來創建初始DOM節點與更新VirtualDOM的diff核心函數。

function view(name) { return h(div, [ h(input, { props: { type: text, placeholder: Type a your name }, on : { input: update } }), h(hr), h(div, Hello + name) ]); }var oldVnode = document.getElementById(placeholder);function update(event) { const newVnode = view(event.target.value); oldVnode = patch(oldVnode, newVnode);}oldVnode = patch(oldVnode, view());

以上是一個通過input事件觸發VirtualDOM更新的典型app。在h函數中，不光可以為VirtualDOM保存數據屬性，還可以設置事件回調函數，並在其中獲取並處理相關的事件屬性，如update回調中的event對象。通過捕獲事件中創建新的vnode，與舊的vnode進行diff，最終對當前的oldVnode進行更新，並向用戶展示更新結果，他的工作流程如下：

在snabbdom源碼中的核心patch函數中很明顯的體現了VirtualDOM的按類型diff與列表diff的策略：如果patch的新舊節點經過sameVnode判斷不是同一個節點，則進行新節點的創建插入與舊節點的刪除，而sameVnode也即是判斷兩個節點是否有相同的key標識與傳入的帶有節點類型等信息的selector字元串是否相同為依據的：

function sameVnode(vnode1, vnode2) { return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;}

而對相同節點進行新舊diff的主函數patchVnode的實現流程如下，其中oldCh與ch為保存舊的當前節點與將要更新的新節點：

//新的text不存在 if (isUndef(vnode.text)) { if (isDef(oldCh) && isDef(ch)) { if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue); } //舊的子節點不存在，新的存在 else if (isDef(ch)) { //舊的text存在 if (isDef(oldVnode.text)) api.setTextContent(elm, ); //把新的插入到elm底下 addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue); } //新的子節點不存在,舊的存在 else if (isDef(oldCh)) { removeVnodes(elm, oldCh, 0, oldCh.length - 1); } //新的子節點不存在,舊的text存在 else if (isDef(oldVnode.text)) { api.setTextContent(elm, ); }

如果新節點可能是複雜節點而非text節點，則對節點的children進一步diff：先判斷是否存在新節點的children整體新增或刪除的情況，若是則進行批量更新，而新舊節點都包含children列表的情況進行updateChildren處理
如果新舊節點都是text節點，且兩者不同則只進行text更新即可

以下介紹updateChildren的核心diff方式，以舊節點oldCh為當前VirtualDOM狀態，將新節點newCh的變化對oldCh進行更新得到新的VirtualDOM狀態，並記錄新舊節點的startIndex與endIndex兩端同時比較，這樣會比從單向按順序對比的方式更快得到diff結果：

當新舊節點的startVnode與endVnode 各自對應相同時，繼續對比，startVnode與endVnode位置各自向中間移動一位。
發現oldStartVnode，newEndVnode相同時，也就是oldStartVnode成為了新的末端節點，就將oldStartVnode插到oldEndVnode的後一個位置

當oldEndVnode，newStartVnode相同時，也就是oldEndVnode成為了新的頭部節點，就將oldEndVnode插入到oldStartVnode前一個位置

當發現oldCh里沒有當前newCh中的節點，將新節點插入到oldStartVnode的前邊，同時這裡會藉助節點中的key值進行map查找是否在其他位置中有匹配的舊節點，如果有匹配，就對舊節點進行更新，再將其插入到當前的oldStartVnode的前面。

在這一輪對比結束時後，有兩種情況，當oldStartIdx > oldEndIdx，說明舊節點oldCh已經遍歷完。那麼剩下newStartIdx和newEndIdx之間的vnode的新節點就調用addVnodes，批量插入父節點的before節點位置，before很多時候是為null的。addVnodes調用的是insertBefore操作dom節點，我們看看insertBefore的文檔：parentElement.insertBefore(newElement, referenceElement)如果referenceElement為null則newElement將被插入到子節點的末尾。如果newElement已經在DOM樹中，newElement首先會從DOM樹中移除。所以before為null，newElement將被插入到子節點的末尾。
如果newStartIdx > newEndIdx，就是newCh先在第一輪對比中遍歷完。此時oldCh中的oldStartIdx和oldEndIdx之間的vnode是需要被刪除的，調用removeVnodes將它們從dom里刪除。

React的reconcilation

在react的歷史版本中，完成數據節點diff的過程是reconcilation,，當你在一個組件中調用setState時，react會將該組件節點標記為dirty，進行reconcile並得到重新構建的子樹virtual-dom，在工作流結束時重新render帶有dirty標記的節點，如果你是在組件的根節點上進行setState，那麼整個組件樹Virtual DOM都會重新創建，但由於這並不是直接操作真實的DOM，所以實際上產生的影響仍然有限。

在React16的重寫中，最重要的改變時將核心架構改為了代號為Fiber的非同步渲染架構。從本質上看，一個Fiber就是一個POJO對象，一個React Element可以對應一個或多個Fiber節點，Fiber包含著DOM節點與React組件中的所有工作需要的屬性數據。因此雖然React的代碼中其實沒有明確的Virtual DOM概念，但通過對Fiber的設計充分完成了Virtual DOM的功能與機制。

Fiber除了承擔Virtual DOM的工作之外，它真正設計目的是實現一種在前端執行的輕量執行線程，同普通線程一樣共享定址空間，但卻能夠受React自身的Fiber系統調度，實現渲染任務細分，可計時，可打斷，可重啟，可調度的協作式多任務處理的強大渲染任務控制機制。

言歸正傳，儘管Fiber非同步渲染的機制幾乎重寫了整個reconcile的過程，但通過源碼分析可以看到對節點reconcile的思路與16之前版本基本一致：

在react的16.3.1版本中，會在頁面初始化render運行過程中，對應頁面結構創建FiberNode，通過child屬性與siblings屬性分別存放子節點與兄弟節點，同時使用return屬性標記父節點，便於遍歷與修改。Fiber在update的時候，會從原來的Fiber（我們稱為current）clone出一個新的Fiber（稱為alternate）。兩個Fiber diff出的變化（side effect）記錄在alternate上。所以一個組件在更新時最多會有兩個Fiber與其對應，在更新結束後alternate會取代之前的current的成為新的current節點。

這裡略過Fiber複雜的構建過程，我們直接來看在某個組件需要更新時的內部機制，也就是組件中setState方法被調用後，首先會在該組件對應的Fiber節點中設置updateQueue屬性以隊列的形式存儲更新內容，然後從頂端開始對整個Fiber樹開始進行深度遍歷，查找到需要進行更新的Fiber節點，判斷的依據就是該節點是否有updateQueue中的更新內容，如果存在更新，就運行我們熟知的shouldUpdateComponent函數來判斷，shouldUpdateComponent返回為真，就執行componentWillUpdate函數，並根據其節點類型決定按哪種方式進行更新，也就是運行reconcile機制進行diff，如果diff的是component節點，待diff完成之後再運行lifeCycle中的componentDidUpdate函數。

這裡提到，我們在組件中setState之後，React會將其視為dirty節點，在事件流結束後，找出dirty的組件節點並進行diff，值得注意的是，雖然重新render構建一顆新的Virtual DOM樹不會觸碰真正的DOM，這裡也並沒有重新創建新的Fiber樹，取而代之的是在每個Fiber節點中都設置了alternate屬性與current屬性來分別存放用於更新替代與當前的節點版本，只是在重新遍歷整顆樹後找到dirty的節點生成新的Fiber節點用於更新：

正如react官方文檔中描述的一樣，當一個節點需要被更新時（shouldComponentUpdate），下一步則需要對它及其子節點進行shouldComponentUpdate判斷與Reconcile的過程來對節點進行更新，這裡我們可以通過在組件中寫入覆蓋的shouldComponentUpdate函數來決定是否進行更新的邏輯：

Reconcile過程的核心源代碼起始於reconcileChildFiber函數，主要實現方式是：根據傳入組件的類型進行不同的reconcile過程，其中最為複雜的是傳入子組件數組調用reconcileChildrenArray處理的情況。reconcileChildrenArray函數在開始進行新舊子節點數組reconcile時，默認先按index順序進行對比，由於Fiber節點本身沒有設置向後指針，因此React目前沒有採取兩端同時對比的演算法，也就是說每一個同層級別的兄弟Fiber節點只能指向下一個節點。因此在通常情況下，對比過程中react只會調用updateSlot將得到的新Fiber數據按其不同類型直接更新到舊Fiber的位置中。

在按順序對比中，如果使用updateSlot未發現key值不相等的情況，則進行將老節點替換成為新節點，第一輪遍歷完成後，則判斷如果是新節點已遍歷完成，就將剩餘的老節點批量刪除，如果是老節點遍歷完成仍有新節點剩餘，則將新節點批量插入老節點末端，如果在第一輪遍歷中發現key值不相等的情況，則直接跳出以上步驟，按照key值進行遍歷更新，最後再刪除沒有被上述情況涉及的元素，由此可見在列表結構的組件中，添加key值是有助於提升diff演算法效率的。

以下是reconcileChildrenArray函數源代碼：

// react使用flow進行類型檢查function reconcileChildrenArray( returnFiber: Fiber, currentFirstChild: Fiber | null, newChildren: Array<*>, expirationTime: ExpirationTime, ): Fiber | null { let resultingFirstChild: Fiber | null = null; let previousNewFiber: Fiber | null = null; let oldFiber = currentFirstChild; let lastPlacedIndex = 0; let newIdx = 0; let nextOldFiber = null; for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) { // 沒有採用兩端同時對比，受限於Fiber列表的單向結構 if (oldFiber.index > newIdx) { nextOldFiber = oldFiber; oldFiber = null; } else { // 指向下一個舊的兄弟節點 nextOldFiber = oldFiber.sibling; } // 嘗試使用新的Fiber更新舊節點 const newFiber = updateSlot( returnFiber, oldFiber, newChildren[newIdx], expirationTime, );、 //如果在遍歷中發現key值不相等的情況，則直接跳出第一輪遍歷 if (newFiber === null) { if (oldFiber === null) { oldFiber = nextOldFiber; } break; } if (shouldTrackSideEffects) { if (oldFiber && newFiber.alternate === null) { // 【譯】我們找到了匹配的節點，但我們並不保留當前的Fiber,所以我們需要刪除當前的子節點 deleteChild(returnFiber, oldFiber); } } lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 記錄上一個更新的子節點 if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; oldFiber = nextOldFiber; } if (newIdx === newChildren.length) { // 【譯】我們已經遍歷完了所有的新節點，直接刪除剩餘舊節點 deleteRemainingChildren(returnFiber, oldFiber); return resultingFirstChild; } if (oldFiber === null) { // 如果舊節點先遍歷完，則按順序插入剩餘的新節點，這裡受限於Fiber的結構比較繁瑣 for (; newIdx < newChildren.length; newIdx++) { const newFiber = createChild( returnFiber, newChildren[newIdx], expirationTime, ); if (!newFiber) { continue; } lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); if (previousNewFiber === null) { // TODO: Move out of the loop. This only happens for the first run. resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } return resultingFirstChild; } // 【譯】把子節點都設置快速查找的map映射集 const existingChildren = mapRemainingChildren(returnFiber, oldFiber); // 【譯】使用map查找需要保存或刪除的節點 for (; newIdx < newChildren.length; newIdx++) { // 按map查找並創建新的Fiber const newFiber = updateFromMap( existingChildren, returnFiber, newIdx, newChildren[newIdx], expirationTime, ); if (newFiber) { if (shouldTrackSideEffects) { if (newFiber.alternate !== null) { // 【譯】新的Fiber也是一個工作線程，但是如果已有當前的實例，那我們就可以復用這個Fiber, // 我們要從列表中刪除這個新的，避免準備復用的Fiber被刪除 existingChildren.delete( newFiber.key === null ? newIdx : newFiber.key, ); } } // 插入當前更新位置 lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); if (previousNewFiber === null) { resultingFirstChild = newFiber; } else { previousNewFiber.sibling = newFiber; } previousNewFiber = newFiber; } } if (shouldTrackSideEffects) // 【譯】到此所有剩餘的子節點都將被刪除，加入刪除隊列 existingChildren.forEach(child => deleteChild(returnFiber, child)); } //最終返回Fiber子節點列表的第一個節點 return resultingFirstChild; }

結束語：

VirtualDOM的設計是提升前端渲染性能的有效方案，也因此提供了以數據為驅動的前端框架工具的基礎，將我們從DOM的繁瑣操作中解放出來，不同的VirtualDOM方案在diff方面基本基於三條diff原則，具體diff過程則考慮自身運行上下文中的數據結構，演算法效率，組件生命周期與設計來選擇diff實現。例如上文snabbdom的updateChildren執行中使用了兩端同時對比以及根據位置順序進行移動的更新策略，而React則受限於Fiber的單向結構採用按順序直接替換的方式更新，但React優化的組件設計與Fiber的工作線程機制在整體渲染性能方面帶來了效率提升，同時兩者都提供了基於key值進行diff的策略改善方式。

VirtualDOM的設計影響深遠，本文僅對VirtualDOM中的思想與diff實現進行了詳細介紹，此外，如何創建一個VirtualDOM樹，如何將diff結果進行patch更新等內容仍有許多不同的具體實現方式可以進行探索，以及React16的Fiber機制更是在非同步渲染方面上又進了一步，值得我們持續關注與學習。

參考閱讀

diff演算法類：

snabbdom源碼

React-less Virtual DOM with Snabbdom :functions everywhere!

解析 snabbdom 源碼，教你實現精簡的 Virtual DOM 庫

React』s diff algorithm

Snabbdom - a Virtual DOM Focusing on Simplicity - Interview with Simon Friis Vindum

去哪兒網迷你React的研發心得

Fiber介紹類

React Fiber Architecture

如何理解 React Fiber 架構？

React 16 Fiber源碼速覽

How React Fiber can make your web and mobile apps smoother and more responsive

React的新引擎—React Fiber是什麼？