React Fiber 是 React 16 之后推出的新架构，而 Reconciliation 是 React 的 Diff 算法，Fiber 和 Reconciliation 都是 React 的核心机制。因此了解和认识其核心机制的运作以及原理，对我们今后高效使用 React 大有裨益。

React Diff 算法

1. DOM, Virtual DOM, Fiber

1.1 DOM

在 DOM 树上，当有很多 DOM 节点元素需要更新时，浏览器会重新渲染所有的样式和 HTML 元素。

1.2 Virtual DOM

Virtual DOM 的出现就是为了解决这一问题，Virtual DOM 是真实 DOM 的模拟，真实 DOM 树由真实的 DOM 元素组成，而 Virtual DOM 树是由 Virtual DOM 元素（即 React Element）组成。当 React 组件状态发生变化时，会产生一个新的 Virtual DOM 树，然后 React 会利用 diff 算法对新旧两棵 Virtual DOM 树进行比较，找到差异，并将差异更新到真实的 DOM 树上，从而完成 DOM 节点元素的更新。

React Element:

export type ReactElement = {|
  $$typeof: any,
  type: any,
  key: any,
  ref: any,
  props: any,
  // ReactFiber
  _owner: any,
  ...
|};

1.3 Fiber 对象

每个 React Element 被创建的同时，都会创建一个 fiber node （fiber node 为 fiber 对象的实例）与之相关联。

Fiber 对象是一个数据结构，用于保存组件状态、组件对应的 DOM 信息、以及工作任务。值得注意的是，和 react element 不一样，fiber node 不需要在每次页面状态更新时都重新创建一遍。在执行 Reconciliation 算法期间，组件 render 方法所返回的 react element 信息都会被合并到对应的 fiber node 中。

Fiber 对象：

export type Fiber = {|
    tag: WorkTag;
    key: null | string;
    type: any;
    stateNode: any;
    updateQueue: mixed;
    memoizedState: any;
    memoizedProps: any,
    pendingProps: any;
    nextEffect: Fiber | null,
    firstEffect: Fiber | null,
    lastEffect: Fiber | null,
    return: Fiber | null;
    child: Fiber | null;
    sibling: Fiber | null;
    ...
|};

2. React 核心工作流

任务调度器 Scheduler: 决定组件渲染的优先级
协调器 Reconciler: 比较并找出新旧两棵 Virtual DOM 树的差异，并把差异告诉 Renderer
渲染器 Renderer: 将差异更新到真实 DOM上

组件 ———> 任务调度器（Scheduler）决定高优先级任务———> 调和器（Reconciler）新旧两棵 Virtual DOM 树差异比较———> 渲染器（Renderer）———> 将差异更新到真实 DOM 树上

3. Reconciliation

在使用 React 时，组件会被渲染成一棵 React Element 树，当组件状态发生变化时，组件会被再次渲染并生成一棵新的不同的 React Element 树。此时，React 会使用 Diff 算法去高效地更新真实的 DOM 树。这个 Diff 算法就是 Reconciliation 算法。

Reconciliation 算法主要做了两件事：

找出两棵 React Element 树的差异
将差异更新到真实 DOM 树上

3.1 Stack Reconciler 栈调和器

React 15.x 以及之前的版本的 Reconciliation 算法都采用了 Stack Reconciler 来实现，但这个时期的栈调和器存在一些缺陷，例如不能暂停渲染任务、不能切分任务、无法有效平衡组件更新渲染和动画相关任务的执行顺序（即不能划分任务的优先级，这可能会导致重要任务卡顿和动画掉帧等问题）。

3.2 Fiber Reconciler

Fiber Reconciler 解决了一些 Stack Reconciler 中的固有问题，在 React 16 版本推出了全新的 Reconciliation 算法调和器——Fiber 调和器来替代栈调和器。Fiber Reconciler 会利用 Scheduler （调度器）来帮忙处理组件的渲染和更新工作。此外，每棵 react element tree 都有一棵对应的 fiber node tree。在 diff 两棵 react element tree 的差异时，Fiber Reconciler 会基于 fiber node tree 来使用 diff 算法，通过 fiber node 的 return, child, sibling 等属性能更方便地遍历 fiber node tree，从而更高效地完成 diff 算法。

3.3 Fiber Reconciler 优点

能够把可中断的任务切片处理
能够调整任务优先级，重置并复用任务
可以在父子组件任务间前进后退切换任务
render 方法可以返回多个元素（即数组）——Fragments
支持异常边界处理

4. Reconciliation 工作流程

前面也提到了 Reconciliation 主要有两个作用：找出两棵 react element tree 的差异、将差异更新到真实 DOM 。

4.1 找出两棵 VDOM 树的差异

4.1.1 三大策略

在对比两棵 VDOM 树的差异上，React 制定了三个策略：

只对同级的 react element 进行对比，如果一个 DOM 节点在新旧两棵树上处于不同的层级，那么 React 不会尝试复用它
两个不同类型的 DOM 节点（即 type 字段不同），React 也不会尝试复用它，而是会销毁旧有类型的 DOM 节点及其子孙节点，并新建最新类型的 DOM 节点及其子孙节点
通过 key 属性来判断哪些同级多个元素在渲染更新后能保持稳定。示例如下：
1
2
3
4
5
6
7
8
9
10
11
// 更新前
<div>
<p key="qianduan">前端</p>
<h3 key="nodejs">NodeJS</h3>
</div>

// 更新后
<div>
<h3 key="nodejs">NodeJS</h3>
<p key="qianduan">前端</p>
</div>
如果没有 key 属性，React 会认为节点类型变更，因此会销毁并重建新类型的节点。

但是如果加上 key 属性，React 则可以通过 key 属性判断对应节点是否存在，从而可以复用相应节点，在上面的示例中，两个节点都可以复用，只需要互换下位置即可。

4.1.2 Diff 具体过程

在对比同级节点时，有以下两种情况：

同级只有一个节点
同级有多个节点

同级只有一个节点：

对比新旧两节点的类型，

若类型 type 和 key （若无 key，则看 index）相同，则复用该节点，然后仅对比并更新有改变的属性。
若类型 type 和 key （若无 key，则看 index）有一个不相同，则会销毁原来的节点及其子孙节点，并重建一个新的节点及其子孙节点。

同级有多个节点：

当同级有多个节点时，需要处理以下3种情况：

节点更新（类型和属性更新）
节点新增和删除
节点位置移动

对于同级多个节点的 Diff，一定属于以上三种情况。同时，React 官方团队发现，在日常开发中，相对于增加、删除和位置移动，更新组件发生的频率更高，所以 React 的 Diff 算法会有闲判断并处理节点的更新。

对于同级的多个节点，我们可以将其看作是一个链表（原因是：同级的 react element 的 fiber node 会通过 sibling 字段链接成一个单向链表）。Diff 算法将会对同级节点链表进行2次遍历：

第一轮遍历：完成节点更新（即节点对应的 DOM 可以复用，只需要更新一些属性）
第二轮遍历：对节点进行新增、删除和移动操作

第一轮遍历

遍历旧虚拟 DOM （react element tree）同级节点链表和新虚拟 DOM 同级链表，从第一个节点开始遍历，判断新、旧节点的类型（type）和 key 是否相同，如果 type 和 key 都相同，则说明对应的 DOM 节点可以复用
如果这个节点对应的 DOM 可以复用，则移动到下一组新旧节点，并判断它们的 type 和 key 是否相同，如果相同则表示对应的 DOM 可以复用，继续重复此步骤2，否则进入步骤3或4.
如果判断此组新旧节点对应的 DOM 不可以复用，则结束第一轮遍历
如果新同级节点链表遍历完成，或者旧同级节点链表遍历完成，则也结束遍历

第一轮遍历结束之后，有两种可能的情况：

在步骤三结束：此时新旧同级节点链表都没有遍历完成
在步骤四结束：此时新旧节点链表中有一个没有遍历完成
- 2.1 如果是新节点链表没有遍历完成，则说明需要新增节点，因此即将要新增的节点会被打上一个Placement的标签（即newFiber.flags = Placement）
- 2.2 如果是旧同级节点链表没有遍历完成，则说明需要删除节点，因此即将要删除的节点会被打上Deletion的标签（即returnFiber.flags |= Deletion）
- 2.3 新旧同级节点链表都遍历完了

第二轮遍历

如果是第一种结果：

说明新旧同级节点链表都没有遍历完，这意味着有的节点在这次更新中可能出现位置变动、删除、或者出现新增的节点。首先判断是否是节点位置移动，在遍历新同级节点链表时，为了能够快速在旧同级节点链表中找到对应的旧节点，React 会将旧同级节点链表中还没被处理过的节点以 map 的形式存放起来，将其的 key 作为 map 的 key，fiber node 作为对应的 value，这个 map 就是 existingChildren

步骤一：

existingChildren 的作用是：在第二轮遍历中，帮助快速查找旧同级节点链表中是否存在具有相同 key 和 type 的旧同级节点，从而判断该节点对应的 DOM 是否可以复用

如果遍历到的新同级节点 A 的 key 在 existingChildren 中，则表明旧同级节点链表中存在一个相同 key 的旧同级节点 A1，接着继续判断它们的 type 是否相同：
- 如果 type 也相同，则说明该节点对应的 DOM 节点可以复用，只是位置发生了改变
- 如果 type 不同，则说明该节点对应的 DOM 不可复用，需要删除原来的节点并重新创建插入一个新的节点
如果遍历到的新同级节点 A 的 key 不在 existingChildren 中，则表明在旧同级节点链表中找不到和 A 的 key 相同的旧同级节点 A1，那么说明 A 是一个新增的节点

步骤二：

在判断出是要移动旧节点还是要删除原节点并新增新节点之后，需要进行具体的操作，即如何实现移动和删除新增，删除和新增比较简单，下面具体解释一下如何处理节点的位置变化。

处理节点位置变化主要有两点：

哪个节点需要右移？
向右移动到哪个位置？

要想明确上面这两点，首先需要找到一个参考点（即在其左边需要右移，在其右边则不需要）。React 使用 lastPlacedIndex 这个变量来存放参考点，lastPlacedIndex 表示当前最后一个可复用的节点，对应在旧同级节点链表中的索引，初始值为0。

在遍历剩下的新同级节点链表时，每一个新节点会通过 existingChildren 找到对应的旧节点（如有的话），然后就可以得到旧节点的索引 oldIndex。接下来会和 lastPlacedIndex 做比较并进行判断：

如果 oldIndex >= lastPlacedIndex，那么就表示该复用节点不需要移动位置，同时将 lastPlacedIndex 的值更新为 oldIndex。
如果 oldIndex < lastPlacedIndex，那么就表示该复用节点需要向右移动，同时将该节点移动到上一个遍历到的新节点的后面（注：此时不需要更新 lastPlacedIndex）

步骤三：

当第二轮遍历结束时，React 就知道要从旧同级节点链表变成新同级节点链表需要进行哪些节点的哪些操作。这些操作（work）即移动、删除、新增，会存放到各节点对应的 fiber node 中。在渲染阶段（Render phase），React 会读取并执行这些操作，从而完成 DOM 节点的更新。

4.2 将差异更新到真实 DOM，完成 UI 的更新

经过上面的 Diff 之后，每个 react element 自身的更新任务（work）都存放在其对应的 fiber node 中。

在渲染阶段，Reconciliation 会从 fiber node tree 最顶端的节点开始，重新对整棵 fiber node tree 进行深度优先遍历，处理树中的每一个 fiber node，处理 fiber node 中存储的 work。其中，遍历一次 fiber node tree 并执行其中的 work 的过程称为一次 work loop。

注：React 开发者做了一个优化，即 Effect List。React 会跳过那些已经处理过的 fiber node，只会去处理那些未完成 work 的 fiber node。例如，如果在组件树的深层中更新了某个 state，那么虽然 React 还是会从 fiber node tree 的顶部的节点开始遍历，但它会跳过前面的父节点，直接走到发生 state 变更的子节点。

当 work loop 结束之后（即遍历完整棵 fiber node tree之后），就会进入 commit 阶段（Commit Phase）。在 commit 阶段，React 会去更新真实 DOM 树，从而完成 UI 的更新渲染。

参考

参考自掘金文章——轻烤 React 核心机制：React Fiber 与 Reconciliation

二进制的流浪

React进阶之路——Diff算法详解