[[428240]]

大家好，我卡頌。

React源碼內(nèi)部在實(shí)現(xiàn)不同模塊時用到了多種算法與數(shù)據(jù)機(jī)構(gòu)(比如調(diào)度器使用了小頂堆)。

今天要聊的是數(shù)據(jù)緩存相關(guān)的LRU算法。內(nèi)容包含四方面：

• 介紹一個React特性
• 這個特性和LRU算法的關(guān)系
• LRU算法的原理
• React中LRU的實(shí)現(xiàn)

可以說是從入門到實(shí)現(xiàn)都會講到，所以內(nèi)容比較多，建議點(diǎn)個贊收藏慢慢食用。

一切的起點(diǎn)：Suspense

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

對于如下代碼：

import A from './A'; 
import B from './B'; 
 
function App() { 
  return ( 
    <div> 
      <A/> 
      <B/> 
    </div> 
  ) 
} 

經(jīng)由打包工具打包后生成：

chunk.js(包含A、B、App組件代碼)

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

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

經(jīng)由打包工具打包后生成：

• 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的作用是：

在異步內(nèi)容返回前，顯示占位符(fallback屬性)，返回后顯示內(nèi)容

再觀察下使用Suspense后組件返回的JSX結(jié)構(gòu)，會發(fā)現(xiàn)一個很厲害的細(xì)節(jié)：

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

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

同步和異步的區(qū)別在于：

• 同步：開始 -> 結(jié)果
• 異步：開始 -> 中間態(tài) -> 結(jié)果

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

那么，能不能將Suspense的能力從React.lazy(異步請求組件代碼)推廣到所有異步操作呢?

答案是可以的。

resource的大作為

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

假設(shè)我們有個請求用戶數(shù)據(jù)的方法fetchUser：

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

經(jīng)由react-cache的createResource方法包裹，他就成為一個resource(資源)：

import {unstable_createResource as createResource} from 'react-cache'; 
 
const userResource = createResource(fetchUser); 

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

function User({ userID }) { 
  const data = userResource.read(userID); 
   
  return ( 
    <div> 
      <p>name: {data.name}</p> 
      <p>age: {data.age}</p> 
    </div> 
  ) 
} 

可以看到，userResource.read完全是同步寫法，其內(nèi)部會調(diào)用fetchUser。

背后的邏輯是：

1. 首次調(diào)用userResource.read，會創(chuàng)建一個promise(即fetchUser的返回值)
2. throw promise
3. React內(nèi)部catch promise后，離User組件最近的祖先Suspense組件渲染fallback
4. promise resolve后，User組件重新render
5. 此時再調(diào)用userResource.read會返回resolve的結(jié)果(即fetchUser請求的數(shù)據(jù))，使用該數(shù)據(jù)繼續(xù)render

從步驟1和步驟5可以看出，對于一個請求，userResource.read可能會調(diào)用2次，即：

• 第一次發(fā)送請求、返回promise
• 第二次返回請求到的數(shù)據(jù)

所以userResource內(nèi)部需要緩存該promise的值，緩存的key就是userID：

const data = userResource.read(userID); 

由于userID是User組件的props，所以當(dāng)User組件接收不同的userID時，userResource內(nèi)部需要緩存不同userID對應(yīng)的promise。

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

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

LRU原理

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

如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高

所以，越常被使用的數(shù)據(jù)權(quán)重越高。當(dāng)需要清理數(shù)據(jù)時，總是清理最不常使用的數(shù)據(jù)。

react-cache中LRU的實(shí)現(xiàn)

react-cache的實(shí)現(xiàn)包括兩部分：

• 數(shù)據(jù)的存取
• LRU算法實(shí)現(xiàn)

數(shù)據(jù)的存取

每個通過createResource創(chuàng)建的resource都有一個對應(yīng)map，其中：

• 該map的key為resource.read(key)執(zhí)行時傳入的key
• 該map的value為resource.read(key)執(zhí)行后返回的promise

在我們的userResource例子中，createResource執(zhí)行后會創(chuàng)建map：

const userResource = createResource(fetchUser); 

userResource.read首次執(zhí)行后會在該map中設(shè)置一條userID為key，promise為value的數(shù)據(jù)(被稱為一個entry)：

const data = userResource.read(userID); 

要獲取某個entry，需要知道兩樣?xùn)|西：

• entry對應(yīng)的key
• entry所屬的resource

LRU算法實(shí)現(xiàn)

react-cache使用「雙向環(huán)狀鏈表」實(shí)現(xiàn)LRU算法，包含三個操作：插入、更新、刪除。

插入操作

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

此時first(代表最高權(quán)重)指向n0。

改變userID props后，執(zhí)行userResource.read(userID)，得到entry1(簡稱n1)：

此時n0與n1形成環(huán)狀鏈表，first指向n1。

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

可以看到，每當(dāng)加入一個新entry，first總是指向他，暗含了LRU中新的總是高權(quán)重的思想。

更新操作

每當(dāng)訪問一個entry時，由于他被使用，他的權(quán)重會被更新為最高。

對于如下n0 n1 n2，其中n2權(quán)重最高(first指向他)：

當(dāng)再次訪問n1時，即調(diào)用如下函數(shù)時：

userResource.read(n1對應(yīng)userID); 

n1會被賦予最高權(quán)重：

刪除操作

當(dāng)緩存數(shù)量超過設(shè)置的上限時，react-cache會清除權(quán)重較低的緩存。

對于如下n0 n1 n2，其中n2權(quán)重最高(first指向他)：

如果緩存最大限制為1(即只緩存一個entry)，則會迭代清理first.previous，直到緩存數(shù)量為1。

即首先清理n0：

接著清理n1：

每次清理后也會將map中對應(yīng)的entry刪掉。

完整LRU實(shí)現(xiàn)見react-cache LRU

總結(jié)

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

隨著底層React18在年底穩(wěn)定，相信未來這種同步寫法的開發(fā)模式會逐漸成為主流。

不管未來React開發(fā)出多少新奇玩意兒，底層永遠(yuǎn)是這些基礎(chǔ)算法與數(shù)據(jù)結(jié)構(gòu)。

真是樸素?zé)o華且枯燥......