從理念到 LRU 算法實現，起底未來 React 異步開發方式

大家好，我卡頌。

React源碼內部在實現不同模塊時用到了多種算法與數據機構（比如調度器使用了小頂堆）。

今天要聊的是數據緩存相關的LRU算法。內容包含四方面：

• 介紹一個React特性

• 這個特性和LRU算法的關係

• LRU算法的原理

• React中LRU的實現

一切的起點：Suspense

在React16.6 引入了Suspense和React.lazy，用來分割組件代碼。

對於如下代碼：

import A from './A';
import B from './B';

function App() {
  return (
    <div>
      <A/>
      <B/>
    </div>
  )
}

經由打包工具打包後生成：

• chunk.js（包含A、B、App組件代碼）

對於首屏渲染，如果B組件不是必需的，可以將其代碼分割出去。只需要做如下修改：

// 之前
import B from './B';
// 之後
const B = React.lazy(() => import('./B'));

經由打包工具打包後生成：

• chunk.js（包含A、App組件代碼）

• b.js（包含B組件代碼）

這樣，B組件代碼會在首屏渲染時以jsonp的形式被請求，請求返回後再渲染。

爲了在B請求返回之前顯示佔位符，需要使用Suspense：

// 之前，省略其餘代碼
return (
  <div>
    <A/>
    <B/>
  </div>
)
// 之後，省略其餘代碼
return (
  <div>
    <A/>
    <Suspense fallback={<div>loading...</div>}>
      <B/>
    </Suspense>
  </div>
)

B請求返回前會渲染<div>loading.。.</div>作爲佔位符。

可見，Suspense的作用是：

在異步內容返回前，顯示佔位符（fallback 屬性），返回後顯示內容

再觀察下使用Suspense後組件返回的JSX結構，會發現一個很厲害的細節：

return (
  <div>
    <A/>
    <Suspense fallback={<div>loading...</div>}>
      <B/>
    </Suspense>
  </div>
)

從這段JSX中完全看不出組件B是異步渲染的！

同步和異步的區別在於：

• 同步：開始 -> 結果

• 異步：開始 -> 中間態 -> 結果

Suspense可以將包裹在其中的子組件的中間態邏輯收斂到自己身上來處理（即Suspense的fallback屬性），所以子組件不需要區分同步、異步。

那麼，能不能將Suspense的能力從React.lazy（異步請求組件代碼）推廣到所有異步操作呢？

答案是可以的。

resource 的大作爲

React倉庫是個monorepo，包含多個庫（比如react、react-dom），其中有個和Suspense結合的緩存庫 —— react-cache，讓我們看看他的用處。

假設我們有個請求用戶數據的方法fetchUser：

const fetchUser = (id) => {
  return fetch(`xxx/user/${id}`).then(
    res => res.json()
  )
};

經由react-cache的createResource方法包裹，他就成爲一個resource（資源）：

import {unstable_createResource as createResource} from 'react-cache';

const userResource = createResource(fetchUser);

resource配合Suspense就能以同步的方式編寫異步請求數據的邏輯：

function User({ userID }) {
  const data = userResource.read(userID);

    return (
    <div>
      <p>name: {data.name}</p>
      <p>age: {data.age}</p>
    </div>
  )
}

可以看到，userResource.read完全是同步寫法，其內部會調用fetchUser。

背後的邏輯是：

1. 首次調用userResource.read，會創建一個promise（即fetchUser的返回值）

2. throw promise

3. React內部catch promise後，離User組件最近的祖先Suspense組件渲染fallback

4. promise resolve後，User組件重新render

5. 此時再調用userResource.read會返回resolve的結果（即fetchUser請求的數據），使用該數據繼續render

從步驟 1 和步驟 5 可以看出，對於一個請求，userResource.read可能會調用 2 次，即：

• 第一次發送請求、返回promise

• 第二次返回請求到的數據

所以userResource內部需要緩存該promise的值，緩存的key就是userID：

const data = userResource.read(userID);

由於userID是User組件的props，所以當User組件接收不同的userID時，userResource內部需要緩存不同userID對應的promise。

如果切換 100 個userID，就會緩存 100 個promise。顯然我們需要一個緩存清理算法，否則緩存佔用會越來越多，直至溢出。

react-cache使用的緩存清理算法就是LRU算法。

LRU 原理

LRU（Least recently used，最近最少使用）算法的核心思想是：

如果數據最近被訪問過，那麼將來被訪問的幾率也更高

所以，越常被使用的數據權重越高。當需要清理數據時，總是清理最不常使用的數據。

react-cache 中 LRU 的實現

react-cache的實現包括兩部分：

• 數據的存取

• LRU 算法實現

數據的存取

每個通過createResource創建的resource都有一個對應map，其中：

• 該map的key爲resource.read(key)執行時傳入的key

• 該map的value爲resource.read(key)執行後返回的promise

在我們的userResource例子中，createResource執行後會創建map：

const userResource = createResource(fetchUser);

userResource.read首次執行後會在該map中設置一條userID爲key，promise爲value的數據（被稱爲一個entry）：

const data = userResource.read(userID);

要獲取某個entry，需要知道兩樣東西：

• entry對應的key

• entry所屬的resource

LRU 算法實現

react-cache使用**「雙向環狀鏈表」**實現LRU算法，包含三個操作：插入、更新、刪除。

插入操作

首次執行userResource.read(userID)，得到entry0（簡稱n0），他會和自己形成環狀鏈表：

此時first（代表最高權重）指向n0。

改變userID props後，執行userResource.read(userID)，得到entry1（簡稱n1）：

此時n0與n1形成環狀鏈表，first指向n1。

如果再插入n2，則如下所示：

可以看到，每當加入一個新entry，first總是指向他，暗含了LRU中新的總是高權重的思想。

更新操作

每當訪問一個entry時，由於他被使用，他的權重會被更新爲最高。

對於如下n0 n1 n2，其中n2權重最高（first指向他）：

當再次訪問n1時，即調用如下函數時：

userResource.read(n1對應userID);

n1會被賦予最高權重：

刪除操作

當緩存數量超過設置的上限時，react-cache會清除權重較低的緩存。

對於如下n0 n1 n2，其中n2權重最高（first指向他）：

如果緩存最大限制爲 1（即只緩存一個entry），則會迭代清理first.previous，直到緩存數量爲 1。

即首先清理n0：

接着清理n1：

每次清理後也會將map中對應的entry刪掉。

完整 LRU 實現見 react-cache LRU

總結

除了React.lazy、react-cache能結合Suspense，只要發揮想象力，任何異步流程都可以收斂到Suspense中，比如React Server Compontnt、流式SSR。

隨着底層React18在年底穩定，相信未來這種同步寫法的開發模式會逐漸成爲主流。

不管未來React開發出多少新奇玩意兒，底層永遠是這些基礎算法與數據結構。

真是樸素無華且枯燥......

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ku488qaebddk1RUMwKi4cg