React 開發者一定要知道的底層機制 — React Fiber Reconciler
前一篇文章「成為 Software Engineer 半年後的小回顧 — 我遇到的困難與反思」有提到會減少撰寫技術文章的頻率，不過這次剛好要準備在公司內部的技術分享，想說反正都已經花時間準備簡報了，再多花一點時間寫成文章好像也不錯，所以這次應該不算是打臉自己啦！
React 自從 v16 以後就推出了 React Fiber 這個全新的底層架構，React 底層使用 fiber 架構重構後才得以實現一些 features 例如 Concurrent Mode 與 Suspense Data Fetching，雖然這些功能都還在實驗階段，但我想未來勢必會成為 React 穩定的 features，可以看出 React Fiber 對於整個 React 生態圈的重要性。我認為要變成一個更好的開發者，嘗試去理解框架底層的 source code 實踐與嘗試 reverse engineering 的過程是非常有幫助的。其實關於 React Fiber 的學習資源應該不少，這篇文章中我想按照自己的步調與理解嘗試介紹 React Fiber 的運作機制，不會到太過深入，但相信能對 React Fiber 的運作機制有基本的了解，那我們就開始吧！
文章大綱
What is React Fiber ?
React Reconciler
Why fiber use linked list to walk component tree ?
Overview of fiber reconciler algorithm
What fiber bring for the future ?
What is React Fiber ?
曾經寫過 class component 的 React 開發者應該都經歷過 React 16 所帶來的巨變 — 也就是 React Hooks，基本上大大的改變了開發的模式。然而除了明顯可以看見的程式碼風格改變以外，其實 React 也在這時針對內部的實作與架構進行了重構，也就是 React Fiber Architecture，這個架構也是 React 未來許多功能例如 Concurrent Mode 得以實踐的基礎。
（補充：其實 React Hooks 得以實現也是因為 React 使用 fiber架構重構喔！）
以宏觀的角度來看 React Fiber 指的是 source code 經過重構後的一種全新架構， 不過如果以狹義的角度來看，fiber 其實是一個擁有許多特定屬性的 JavaScript 物件，長得像下面這樣：
而 fiber 也代表著「An unit of work for React to process」，也許有點抽象難懂，但目前為止我們先停在這裡，隨著文章段落的推進我們會對 fiber 有更加深入的理解。
What can fiber do ?
重構後的 React Fiber 架構改變了什麼？我覺得可以將重點放在兩個地方上：
- Animation 動畫
- Responsiveness 反應能力
從上面這張 gif 可以明顯的做出對比，左邊是 fiber 以前的架構，右邊則是在 fiber 架構下的體驗，可以發現動畫的流暢度差了非常多，至於反應能力（例如 mouse hover 等 event）則可以到以下兩個版本的範例網站看看差別：
當然在一般的應用下是不會有這麼明顯的差別的，以上的範例都是刻意為之的，但當你的應用非常複雜並且非常吃效能時，以上的狀況就有可能會發生。
fiber 架構可以達成這樣的改變主要可以歸因於：
- fiber 可以將頁面渲染的任務切分成 chunks
- 不同的任務可以經過 prioritize 區分優先級
- 任務可以暫停，之後再繼續執行（這也是將任務分優先級的目的，當做到一半出現更高優先級的任務的時候，會希望可以先暫停目前工作的執行，等處理完高優先及任務後再回來繼續執行）
- 可以重複使用之前的 work，也可以將不需要的 work 丟棄掉
現代的 web 應用中最想要避免的無非是兩種糟糕的使用者體驗 — 「頁面卡頓」與「沒有內容的白屏畫面」，會造成這兩種問題的原因很大的機會是出自於 CPU 的瓶頸（元件層級深且複雜、耗性能的運算、設備本身 CPU 性能不足…等等）與 IO 的瓶頸（網路請求），而 react fiber 就是為了解決這些問題而誕生的架構。
JSX -> React Element -> Fiber Node
React 開發者自然對於 JSX 語法十分熟悉，React 在背後會呼叫 React.createElement這個 function 來將 JSX 中的 elements 轉換成 React Elements。
從上圖可以知道 React Element 也是一個 JavaScript 的物件，記載了 element 的一些 properties 例如 type、key、props 等等，在 fiber 架構下，react 還會透過呼叫 createFiberFromTypeAndProps 這個 function 將 React Elements 轉換成 Fiber Nodes。
我們可以歸納一下到目前為止對於 fiber 的認知：
- 會形成一個由 fiber nodes 串連起來的 tree（我們都知道在寫 component 的時候是樹狀結構，理所當然由它轉換而來的 React Elements 與接著由 React Elements 再次轉換而成的 fiber nodes 也會是樹狀結構）
- fiber node 其實也代表了 React Element，但它涵蓋了更多屬性
- fiber = unit of work for react to process
- React Fiber 會經過兩階段的處理過程：1. Render Phase（非同步）2. Commit Phase（同步）
各位會比較疑惑的應該是最後一點，這在稍後會進一步說明。
React Reconciliation
談到 React 怎麼更新我們的畫面，大家應該都知道 React 透過 Virtual DOM 還有 Diff 演算法算出畫面中實際需要更新的部分，比對更新前後 virtual DOM 的差異之後，再去更動真實的 DOM，有效減少渲染的次數 ，而這個 Diff 的過程也被稱作 reconciliation。
React 實作了一個「啟發式 (heuristic)演算法」將原本需要 O(n³) 的 diff 流程壓到了 O(n)，靠的是兩個假設：
- 兩個不同類型的 element 會產生出不同的 tree。
- 開發者可以通過 key prop 來指出哪些 child elements 在不同的 render 下可以保持不變。
會提到 React Reconciliation 是因為 fiber 的出現最主要改變的就是 React 的 Reconciliation 流程，這稍後會再進階說明。如果對於啟發式演算法有興趣的朋友可以參考我同事 Ken 的簡報。
在 fiber 架構以前 React 渲染頁面時主要會經過兩個階段：
- Reconciler — 負責找出需要變動的元件，也就是上面提到的演算法，這個階段可以再細分成兩個 stage：render phase 與 commit phase。在 render phase 這個階段 React 會更新數據生成新的 Virtual DOM，然後通過 Diff 演算法，找出需要更新的元素，放到 update queue 中，最後得到新的 update queue，commit phase 這個階段 React 會遍歷 update queue ，將其中需要的變更「一次性」更新到 DOM 上。
- Renderer — 負責將變化的元件渲染到畫面上。熟悉 React 生態系的開發者應該聽過可以使用 React 來開發除了網頁以外的應用，例如 React Native 可以用來開發手機 App、react-360 可以用來開發 VR 應用，這其實是因為 React 將 reconciliation 等核心實作在 react core library 當中，實際上如何渲染到應用上則交由不同 renderer 來處理，這也是「大前端時代」得以實現的契機之一。如果對於其他 React 相關的 renderer 有興趣，可以參考 awesome react renderers 這個 github repo。
在 fiber 架構出現以後，多了一個 scheduler 的機制。為什麼多了 scheduler ? 前面有提到 fiber 讓任務可以切分成 chunks 並且可以區分優先級，因此在 fiber 架構後還會經過一層 scheduler 來調度工作，而 reconciler 這個步驟的運作機制也經過調整，等等會再說明。
Old Reconciler — Stack
在 React15 及以前，Reconciler 採用遞迴的方式創建 virtual DOM (熟悉 functional component 的話應該可以了解這個概念，我們是透過呼叫 component 的 function 來得到要 return 的元件，這個過程遇到子元件就得再去呼叫子元件的 function，於是形成 call stack 的結構)，遞迴的過程是不能中斷且是同步的，如果元件樹的層級很深，遞迴會佔用 main thread 很多時時間，這會產生相應的一些問題例如造成頁面卡頓、使用者的事件沒有回應…等等。
為了解決這個問題，React 想要將這種遞迴且無法中斷的更新 refactor 成非同步且可以中斷的更新，而曾經依靠遞迴的 Virtual DOM 資料結構明顯是沒辦法滿足這個條件的，於是全新的 React Fiber 架構就因此誕生了。所以通常在 React 16 之後的 Reconciler 也被稱作 Fiber Reconciler，而 Virtual DOM 這個名詞 React 官方也有提到說為了怕搞混，在 fiber 架構出現後會盡量避免使用這個名詞。我認為可以看成 React Fiber 一樣要創建一個虛擬的樹狀結構，但是結構跟以前的 Virtual DOM tree 版本已經不一樣了，所以通常會稱作 fiber tree 以免使開發者搞混。
Why fiber use linked list to walk component tree ?
這個標題其實就已經直接破梗了，在 fiber 架構下是使用 linked list 這個資料結構來遍歷 component tree 的，這個小段落會提到在 fiber 架構出現前 react 是如何遍歷 component tree 的，以及以前的方式有哪些缺點導致要使用 fiber 重構，最後是為什麼使用 linked list 的方式可以解決之前的問題。
如果對於 Linked List 這個資料結構完全不理解的朋友可以參考我同事 PJ 的文章。
What does browser do in 1 frame ?
在正式進入主題之前，首先我們要先回顧一下瀏覽器在一幀裡面都做了些什麼事，為什麼呢？稍後就知道了。
我們都知道頁面的内容都是一幀接著一幀繪製出来的，browser 的 frame rate (fps, frame per second) 代表瀏覽器一秒可以繪製多少幀。原則上一秒繪製的幀數越多，畫質也就越細緻。目前瀏覽器的解析度大多是 60 fps，每一幀大約耗費 16.6ms 左右（1000ms / 60）。那在這一幀（16.6ms） 中 browser 經歷了哪些流程並做了哪些工作呢？
從上面兩張圖來看，大致上可以歸納出瀏覽器在一幀內會經歷這些過程：
- 接受使用者的 input event (click, keypress 等事件)
- 執行事件的 callback
- 執行 rAF (RequestAnimationFrame)
- 頁面的 layout 與樣式計算
- 繪製渲染頁面
- 執行 rIC (RequestIdleCallback)
最後一步的 rIC 事件不是每一幀結束都會執行，只有在一幀的 16.6ms 中做完了前面的流程並且還有剩餘的時間才會執行。(關於 rIC 我在了解 SWR 的運作機制，How this async state manager works ?這篇文章也有稍微提到過，其實 SWR 的 cache revalidation 機制就是透過 rIC 與 rAF 來達成的)
不過要特別注意的是，如果有剩餘的時間可以執行 rIC，那麼下一幀就需要在 rIC 的 callback 執行結束後才能繼續渲染，所以建議在 rIC 不要執行一些耗時的操作，如果太久沒有將控制權交還給 browser，將會影響下一幀的渲染，導致畫面出現卡頓或對於事件的延遲反應。
Render Phase
剛剛有提過在 Fiber Reconciler 有兩個階段 — render phase 與 commit phase，我們現在主要 focus 在第一個階段 render phase，React 在 render phase 到底做了哪些事呢？
- retrieves the children from the component
- updates state and props
- calls lifecycle hooks
- compares them to the previous children and figures out the DOM updates that need to be performed
嗯…那有什麼問題嗎？
React 會以「同步」的方式走過整個 component tree 並且做一些相對應的 work，這邊的 work 指的是前面提及的比如說更新 state 與 props、執行一些 lifecycle method、比較更新前後的差異找出需要更新 DOM 的節點…等等。
如果這些工作所耗費的時間超過 16ms，就有可能會造成「掉幀」的狀況，使用者看到的畫面就有可能是非常卡頓與不流暢的，這對於前端應用來說當然是需要盡量避免的狀況。
那有沒有什麼方法可以解決這個問題呢？這時剛剛提到的 rIC 與 rAF 就派上用場啦！
rAF, rIC to the rescue
剛剛其實就有提過 rAF 與 rIC 在瀏覽器一幀的執行時間點，React core team 想到可以利用 rAF 與 rIC 來執行 reconciler render phase 的這些任務，於是 React 將一些高優先級的任務比如說 animation 放到 rAF 去處理，而一些比較低優先級的任務例如 network I/O 的工作就放到 rIC 去處理。不過 React core team 發現 rIC 有一些比較不穩定的問題，首先是瀏覽器的支援度，再來是他們發現 rIC 的觸發頻率其實是不穩定的，比如說當切換 tab 的時後有機會讓前一個 tab 的 rIC 被觸發的機會降低，所以 React 其實有自己實作一個叫 react-scheduler 的 package，除了實作 rIC 的 polyfill 以外也做了一些客製化的調整，它的任務便是調整任務的優先級，讓高優先級的任務會優先進入 reconciler 的階段。
這樣的方式看似美好，其實存在一個巨大的問題，就是 render phase 的這些任務沒辦法被拆分（這邊是指 fiber 架構以前），react 會同步的遍歷 component tree （像左下方這段 code 一樣，執行的結果會形成 一個 call stack，React 需要等到這個 call stack 清空後(也就是所有 function 都執行且 return 後)才有辦法做下一件事）
另外這樣的方式如果是 component tree 層級比較深得時候也會讓 call stack 變的非常肥大，讓空間複雜度大大提升。
rIC 跟 rAF 雖然強大，但會因為以上這個特性受到一些限制：
- 在前面提過 rIC 跟 rAF 執行耗時的工作都有機會延遲下一幀的執行
- rIC 跟 rAF 其實可以讓開發者自己控制 timeout 或者是足夠的時間超過一個標準才執行任務，不過能做到這點的前提是任務要可以拆分，這樣在下一幀才知道要從何繼續，這以目前的 call stack 架構是無法做到的。
看來 React 有必要改變架構，讓 tree traversal 這個過程變得可以暫停或繼續，並且防止 call stack 不停的增長。也因此才有了標題提到的 React Fiber 將原來的 stack 架構改為使用 Linked List 架構來遍歷 component tree 並執行 reconciliation。
Fiber Linked List traversal
接下來就來看看 React Fiber 架構下的 linked list traversal 演算法是怎麼運作的，首先要先知道三個關於 fiber node 之間 relationship 的名詞 — child、 sibling、 return。 child 就是子節點，sibling 則是兄弟節點，而 return 則指向父節點，這個演算法的特點是每個節點都只會有各一個 child、sibling 與 return 。
以上圖為例，一般我們會認為 div 有三個 children，分別是 h1、h2 與 h3，但在 fiber 架構下只會把第一個 children 當作 child，其他 children 則使用 child 的 sibling 來記錄，並且透過 return 指回 parent node。
How React Process A Fiber Tree ?
現在我們知道 fiber node 之間的 relationship 了，那 React 在 fiber 架構下究竟是如何遍歷一個 fiber tree 的呢？
有以下兩個規則：
- 深度優先搜尋 (DFS)
- child -> 自身 -> sibling
這邊直接舉例可能會比較好懂
這個 component tree 的架構是最上層有一個 A 節點，A 節點下有三個 children B-1、B-2 與 B-3，其中 B-2 下層還有子節點，以此類推。在上圖中節點間的關係是以剛剛介紹過的 fiber relationship 連結在一起的，因此我們可以把上圖看作是一個「Fiber Tree」。
React 在遍歷 fiber tree 的時候，會有「begin」與 「complete」兩個步驟，並分別會執行一些函式。以走訪樹狀結構來說，我們必須先「begin」父層元件才能接著走訪到它的子元件，「complete」子元件後才能回到父元件並且「complete」這個父元件。前面有提到 fiber tree 的 traversal 會是 DFS，並且順序是 Child -> 自身 -> Sibling，以上圖來說，如果黃色閃電代表 begin，綠色勾勾代表 complete 的話，整個走訪 Fiber Tree 的過程會是這樣的。
這個遍歷樹狀結構的過程是透過在 React source code 中被稱作「workLoop」的 while 迴圈實現的，而非以往 recursion 的方式
這麼做的好處是當我們每次執行工作 (work) 並遍歷 fiber tree 的節點時就不會導致 call stack 不停的增長，linked list 的結構也讓我們可以記住目前執行到哪一個節點，讓整個過程可以暫停與繼續。
Overview of fiber reconciler algorithm
前面已經多次提及 Fiber Reconciler 有兩個階段：render phase 與 commit phase，而剛剛的段落都是聚焦在 render phase，探討 react 如何遍歷 fiber tree 並得出需要改變的 DOM 節點，現在我們來跑一次完整的 reconciler 流程並且做一個總結，看看 React 在 render phase 與 commit phase 到底都做了哪些工作，並對整個 reconciler 流程有初步的認知。
不過在這之前需要先介紹一些先備知識：
Pre-required knowledge — Current & Work In Progress Tree
React 在第一次 render 時會按照前述從 JSX 轉換成 React Element，再接著形成一個 fiber tree，而在之後如果有 state 更新等事件需要經過 reconciler diff 演算法得知要更新的節點時會建立一個 workInProgress 的 fiber tree ，react 會把這個workInProgress tree 與原本的 current tree 做 diff 比較，得出要執行的 side effect， 等 workInProgress tree 完成後就會把他替換成 current tree。
前面提過的 React 的 workLoop 其實就是一個創建 workInProgress tree 的過程。
Pre-required knowledge — Side Effect
剛剛有提到 workInProgress tree 會與原本的 current tree 做 diff 比較，得出要執行的「 side effect」，不知道大家對於 side effect 這個詞有沒有感到疑惑，到底什麼是 side effect？
以 React 來說主要的 side effect 有兩種：
- DOM 操作
- calling lifecycle method
這些 side effect 會在 reconciler 的 commit phase 以「同步」的方式執行
我們已經知道 fiber 其實就是一個 javascript 的 object，在 fiber 裡面其實有一個叫做 effectTag 的 property 來紀錄這個節點需要執行哪些 side effect ，然後會放入由 React 定義好的 effect tag 常數
Pre-required knowledge — Effect List
在 workInProgress tree 形成之後且與 current tree 進行 diff 比較後，fiber tree 中的幾個需要執行 side effect 的節點(記錄於 effectTag property)間會建立一條單向鏈結串列結構的 effect list，未來要執行這些 side effects 的時候就可以直接 traverse 這個鏈結串列而不用再遍歷整個 fiber tree 找出哪些 fiber nodes 需要執行 side effect。
Run through the process
具備先備知識後就可以來跑跑看整個 reconciler 的流程囉！
在第一次頁面渲染時會透過開發者撰寫的 JSX 語法轉換成 react elements，再轉換成 fiber nodes，並形成一個 fiber tree。
後來假設 component 的 state 發生改變，導致重新 re-render，就會重新跑一次剛剛的流程，不同的是這次會由帶有 side effects 的 fiber nodes 形成 workInProgress tree，並與 current fiber tree 做 diff 比較得出需要執行的 side effects 列表，也就是 effect list，並將 workInProgress tree 替換成 current tree。
以上這些步驟都是在 render phase 以非同步的方式執行。
另外在 render phase 也會執行一些 React 提供的 lifecycle method (如上圖)，不過因為這些 lifecycle method 是在 render phase 以非同步的方式執行，因此應該盡量避免寫一些會造成 side effect 的操作，例如說 DOM 元件的操作，以免產生一些非預期的結果。
我們可以把 render phase 的主要目的想成需要產出
- 一個 fiber tree
- 一個 effect list
產出 fiber tree 與 effect list 後，render phase 的工作到這裡就差不多告一段落了，接下來就輪到 commit phase 了。React 在 render phase 的時候就已經建立出了一個單向鏈結串列結構的 effect list，在 commit phase 的時候會「同步的」遍歷這個 effect list 並且執行對應的 side effects。
這個階段必須要是要是同步的原因是「更新真實的 DOM 節點」這個操作需要一氣呵成不能中斷，否則會造成使用者視覺上的不連貫。所以可以歸納出在 render phase 的改變使用者是看不到的，必須等到 commit phase 才會看到畫面產生實際的改變。
而 React component 中的一些 life cycle method 則會在 commit 階段執行，這邊的 life cycle method 就可以執行一些 side effect 例如 DOM 操作或是 subscription…等等。
What fiber brings for the future ?
大家一定都聽過 react fiber 是 react 未來很多 features 可以實現的基礎，最知名的應該就是 concurrent mode 的 asynchronous rendering 與 suspense 的 data fetching，而這些 features 看起來都已經是未來必定會實現的功能了，今天就不花篇幅說明這些。
我在網路上看到有人提出一點可能性，自己覺得蠻有意思的，在今天的內容中我們可以歸納出 react fiber reconciler 的最終目標其實就是得到 commit phase 要執行的 effect list，中間的過程(render phase)既然是可以拆分且非同步執行的，那是不是有機會透過多個 web worker + react reconciler 達到平行執行來提升整體效能？這個可能性我認為還蠻值得去思考與期待的。(當然 web worker 不是所有效能問題的銀彈，還有太多太多問題需要考慮，這邊只是提出一個可能性讓大家思考而已。)
結論
我一直深信花時間去了解更底層的實踐過程，對於一項技術的掌握度是會大幅提升的。身為 React 開發者，我們一定都聽過 React 16 時改為使用 fiber 架構，但也許不是每個人都會去研究它背後運作的原理。當我自己花時間去理解後，頓時有種打通任督二脈的感覺，瞬間理解之前令我感到困惑的許多眉眉角角，也對於 React 未來的演進有了些方向與期待。當然要透過一篇文章就介紹完 React Fiber 還是太困難了，這邊只能做個簡單的 Intro，希望有幫助到正在閱讀的你，最後也非常推薦有興趣與耐心的朋友一起去探索看看 React 的 Source Code 喔！
References & 圖片來源
https://zhuanlan.zhihu.com/p/390409316
