[[428240]]

大家好，我卡頌。

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開發出多少新奇玩意兒，底層永遠是這些基礎算法與數據結構。

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