LRUアルゴリズムの概念から実装まで、React非同期開発の未来

[[428240]]

みなさんこんにちは、カソンです。

React ソース コードは、さまざまなモジュールを実装するためにさまざまなアルゴリズムとデータ構造を使用します (たとえば、スケジューラは小さなトップ ヒープを使用します)。

本日は、データ キャッシュに関連する LRU アルゴリズムについてお話します。コンテンツには次の 4 つの側面が含まれます。

• React機能の紹介
• この機能とLRUアルゴリズムの関係
• LRUアルゴリズムの原理
• ReactでのLRUの実装

エントリーから実践までを網羅すると言ってもいいくらい、内容が盛りだくさん。気に入ってコレクションしてゆっくり消費するのがおすすめです。

すべてが始まった場所：サスペンス

コンポーネント コードを分割するために、React 16.6 で Suspense と React.lazy が導入されました。

次のコードの場合:

 Aをインポート  './A' ;
 Bをインポート  './B' ; 
 
関数App() {
戻る（
    <div>
      <あ/>
      <B/>
    </div>
  ）
 }

パッケージング ツールでパッケージ化した後、以下が生成されます。

chunk.js (A、B、App コンポーネント コードが含まれています)

最初の画面レンダリングでは、コンポーネント B が不要な場合は、そのコードを分割できます。次の変更を加えるだけです:

 // 前に
Bをインポート  './B' ;
 // 後
const B = React.lazy(() => import( './B' ));

パッケージング ツールでパッケージ化した後、以下が生成されます。

• chunk.js (A および App コンポーネント コードが含まれています)
• b.js (B コンポーネント コードを含む)

このように、最初の画面がレンダリングされるときに、B コンポーネントのコードが jsonp 形式でリクエストされ、リクエストが返された後にレンダリングされます。

B リクエストが返される前にプレースホルダーを表示するには、Suspense を使用する必要があります。

 // 前に、残りのコードを省略します
戻る（
  <div>
    <あ/>
    <B/>
  </div>
 ）
 // その後、残りのコードを省略します
戻る（
  <div>
    <あ/>
    <Suspense fallback={<div>読み込み中...</div>}>
      <B/>
    </サスペンス>
  </div>
 ）

<div> の読み込み中。B リクエストが返される前にレンダリングされます。 .</div> をプレースホルダーとして使用します。

Suspense の役割は次のようになります。

非同期コンテンツが返される前にプレースホルダー（フォールバック属性）を表示し、返された後にコンテンツを表示する

Suspense を使用した後にコンポーネントによって返される JSX 構造を見ると、非常に強力な詳細が見つかります。

戻る（
  <div>
    <あ/>
    <Suspense fallback={<div>読み込み中...</div>}>
      <B/>
    </サスペンス>
  </div>
 ）

この JSX からは、コンポーネント B が非同期にレンダリングされるかどうかを知る方法はありません。

同期と非同期の違いは次のとおりです。

• 同期: 開始 -> 結果
• 非同期: 開始->中間状態->結果

Suspense は、ラップされたサブコンポーネントの中間状態ロジックを自分自身に収束させて処理できるため (つまり、Suspense のフォールバック プロパティ)、サブコンポーネントは同期と非同期を区別する必要がありません。

では、サスペンスの機能は、React.lazy (非同期リクエスト コンポーネント コード) からすべての非同期操作に拡張できるのでしょうか?

答えはイエスです。

リソースの偉大な成果

React リポジトリは、複数のライブラリ (react、react-dom など) を含むモノレポです。その中には、Suspense と組み合わせたキャッシュ ライブラリ react-cache があります。その使い方を見てみましょう。

ユーザーデータを要求するメソッド fetchUser があるとします。

 const fetchUser = (id) => {
戻る  (`xxx/ user /${id}`)を取得します。次に(
    res => res.json()
  ）
 };

react-cache の createResource メソッドでラップすると、リソースになります。

インポート{unstable_createResourceをcreateResourceとして}   'react-cache' ; 
 
ユーザーリソースを作成します。

リソースを Suspense と組み合わせて使用​​することで、非同期データ要求のロジックを同期的に記述できます。

関数 ユーザー({ ユーザーID }) {
  const データ = userResource.read (ユーザーID); 
   
戻る（
    <div>
      <p>名前: {data.name } </p>
      <p>年齢: {data.age}</p>
    </div>
  ）
 }

ご覧のとおり、userResource.read は完全に同期的に書き込まれ、fetchUser は内部的に呼び出されます。

この背後にあるロジックは次のとおりです。

1. userResource.read の最初の呼び出しは、promise (fetchUser の戻り値) を作成します。
2. 約束を投げる
3. Reactがpromiseをキャッチした後、Userコンポーネントに最も近いSuspenseコンポーネントがフォールバックをレンダリングします。
4. プロミスが解決した後、Userコンポーネントが再レンダリングされる
5. この時点で、userResource.readを再度呼び出すと、解決の結果（つまり、fetchUserによって要求されたデータ）が返され、そのデータを使用してレンダリングが続行されます。

ステップ 1 と 5 から、1 つのリクエストに対して userResource.read が 2 回呼び出される可能性があることがわかります。

• 初めてリクエストを送信し、Promiseを返す
• 要求されたデータの2回目の返却

したがって、promise の値は userResource 内にキャッシュする必要があり、キャッシュ キーは userID です。

 const data = userResource.read (ユーザーID) ;

userID は User コンポーネントのプロパティであるため、User コンポーネントが異なる userID を受け取った場合、異なる userID に対応する promise を userResource 内にキャッシュする必要があります。

100 個のユーザー ID を切り替えると、100 個のプロミスがキャッシュされます。明らかに、キャッシュをクリーニングするアルゴリズムが必要です。そうしないと、キャッシュはオーバーフローするまでどんどん占有されてしまいます。

react-cache で使用されるキャッシュ クリーニング アルゴリズムは LRU アルゴリズムです。

LRU原則

LRU（最近最も使われていない）アルゴリズムの中心的な考え方は次のとおりです。

データが最近アクセスされた場合、将来もアクセスされる可能性が高くなります。

したがって、頻繁に使用されるデータほど、その重みは高くなります。データを消去するときは、常に最も使用頻度の低いデータを消去してください。

react-cacheでのLRUの実装

react-cache の実装は 2 つの部分で構成されます。

• データアクセス
• LRUアルゴリズムの実装

データアクセス

createResource によって作成された各リソースには、対応するマップがあります。

• このマップのキーは、resource.read(key) が実行されたときに渡されるキーです。
• マップの値は、resource.read(key) が実行された後に返されるプロミスです。

userResource の例では、createResource は実行後にマップを作成します。

ユーザーリソースを作成します。

userResource.read が初めて実行されると、userID をキー、promise を値とするデータがマップに設定されます (エントリと呼ばれます)。

 const data = userResource.read (ユーザーID) ;

エントリーするには、次の 2 つのことを知っておく必要があります。

• エントリ対応キー
• エントリが属するリソース

LRUアルゴリズムの実装

react-cache は、「双方向循環リンク リスト」を使用して、挿入、更新、削除の 3 つの操作を含む LRU アルゴリズムを実装します。

挿入操作

初めて userResource.read(userID) が実行されると、entry0 (略して n0) が取得され、それ自体と循環リンク リストを形成します。

このとき、first（最も高い重みを表す）はn0を指します。

userID プロパティを変更した後、userResource.read(userID) を実行して entry1 (略して n1) を取得します。

このとき、n0 と n1 は循環リンク リストを形成し、最初に n1 を指します。

n2を挿入すると、次のようになります。

新しいエントリが追加されるたびに、first は常にそのエントリを指していることがわかります。これは、新しいエントリが常に LRU で高い重みを持つという考えを暗示しています。

更新操作

エントリがアクセスされるたびに、そのエントリは使用されているため、その重みは最高に更新されます。

次の n0 n1 n2 の場合、n2 の重みが最も高くなります (最初に n2 を指します)。

n1 に再度アクセスする場合、つまり次の関数が呼び出される場合:

 userResource.read (n1はuserIDに対応します) ;

n1に最も高い重みが与えられます。

削除操作

キャッシュの数が設定された上限を超えると、 react-cache は重みの低いキャッシュをクリアします。

次の n0 n1 n2 の場合、n2 の重みが最も高くなります (最初に n2 を指します)。

最大キャッシュ制限が 1 の場合 (つまり、1 つのエントリのみがキャッシュされる場合)、キャッシュ数量が 1 に達するまで first.previous が繰り返しクリーンアップされます。

つまり、まずn0をクリーンアップします。

次にn1をクリーンアップします。

各クリーンアップの後、マ​​ップ内の対応するエントリが削除されます。

完全なLRU実装については、 react-cache LRU を参照してください。

要約する

Suspense と組み合わせることができる React.lazy や react-cache 以外にも、React Server Component やストリーミング SSR など、想像力次第であらゆる非同期処理を Suspense に統合することができます。

年末までに基盤となるReact18が安定してくると、今後はこの同期開発モデルが徐々に主流になっていくのではないかと考えています。

将来 React がどれだけ多くの新しいガジェットを開発しても、基礎となるレイヤーは常にこれらの基本的なアルゴリズムとデータ構造になります。

本当に地味でつまらないです…