Caffeine ソースコード解釈 - キャッシュ有効期限の削除に関連するアルゴリズム

[[410588]]

この記事はWeChatの公開アカウント「Muscular Coder」から転載したもので、著者はZou Xueです。この記事を転載する場合は、Muscle Coder の公開アカウントにご連絡ください。

導入：

前回の記事では、Caffeine のフレームワーク部分を例を使って説明しました。この記事では、引き続き、キャッシュの有効期限に関するアルゴリズム部分を例を使って説明し、guava キャッシュの設計とどのように異なるかを確認します。

使用例:

同じ例を使い続けますが、まずは PUT と GET から始めましょう。ワークフローを理解すれば、キャッシュの有効期限のロジックも自然にわかるようになります。

 //初期化
Cache<String, String> キャッシュ = Caffeine.newBuilder().maximumSize(100)
  .expireAfterWrite(1, TimeUnit.SECONDS).build();
 //置く
キャッシュに格納します。 "a" 、 "b" 。
 //得る
 システム.out.println (cache.getIfPresent( "a" ));

グアバは期限が切れて保存中に除去されますが、カフェインも同様でしょうか?

置く/取得:

ほとんどの場合、境界付きキャッシュが作成され、put メソッドは BoundedLocalCache のこのメソッドに入ります: put(K key, V value, boolean notificationWriter, boolean onlyIfAbsent)。キャッシュに前の要素が含まれていない場合は、次のコードが実行されます。

 // キャッシュから前の値を取得する
Node<K, V> の事前データ= data.get(nodeFactory.newLookupKey( key ));
 if (事前== null ) {
  // prior = nullは前の要素が存在しないことを意味します
  //要素が存在しないため、キーと値に基づいて新しいノードを作成する必要があります
  // ここでのnull判断は、ロジックのこの部分の外側の層がループであるということです。ループを使用する理由は、後続の非同期操作が成功することを保証する必要があるためです。
  if (ノード == null ) {
    //新しいノードを作成する
    ノード = nodeFactory.newNode(キー, keyReferenceQueue(),
        値、valueReferenceQueue()、newWeight、now);
    //有効期限戦略のノードの初期時間を設定する
    setVariableTime(ノード、expireAfterCreate(キー、値、現在));
    setAccessTime(ノード、現在);
    setWriteTime(ノード、現在);
  }
  （notifyWriter && hasWriter()）の場合{
   .............................
  } else { //キーがまだ書き込まれていない場合
      //新しく作成されたノードをデータに書き込む
事前= data.putIfAbsent(node.getKeyReference(), ノード);
    if (事前== null ) {
      //値がまだ存在しない場合は、afterWrite操作を実行し、AddTaskタスクを実行します
      afterWrite(新しい AddTask(ノード、新しい重み));
戻る ヌル;
    }
  }
 }

一貫性コードがたくさんあるため、最初に中国語のコメントを読むだけで済みます。コードから、書き込みキャッシュ操作は比較的単純であることがわかります。新しいノードを作成してデータに書き込み、最後に afterWrite をトリガーして null を返します。

afterWrite メソッドは最後のステップで何を実行しますか?

まず、AddTask とは何かを見てみましょう。

最終クラス AddTask は Runnable を実装します {
    最終的なNode<K, V>ノード;
    最終的なint の重量; 
 
    AddTask(Node<K, V> ノード、 int重み) {
      this.weight = 重量;
      ノードをコピーします。
    }
 ...............................
 }

AddTask は実行可能なインターフェイスを実装します。つまり、追加操作が完了した後、追加タスクが非同期で実行されます。これが、AddTask と guava の最大の違いです。非同期です。まずは同期部分を終わらせましょう。結局のところ、put 操作が null を返す前に実行する必要があります。afterWrite メソッドは次のとおりです。

 void afterWrite(実行可能なタスク) {
 if (buffersWrites()) {
 ( int i = 0; i < WRITE_BUFFER_RETRIES; i++) {
    （writeBuffer().offer(タスク)）の場合{
      //書き込み後のスケジュールをトリガーする
      スケジュール後に書き込み();
戻る;
    }
    スケジュールされたDrainBuffers();
  }
  ..........
 }それ以外{
  スケジュール後に書き込み();
 }
 }

上記のコードから、このメソッドは書き込み後のスケジュールをトリガーし、最終的にdrainBuffersTaskを非同期的に実行します。このタスクは、キャッシュ内の各ノードのステータスを整理して処理します。

 void スケジュールドレインバッファ() {
  （drainStatus() >= PROCESSING_TO_IDLE）の場合{
戻る;
  }
  if (evictionLock.tryLock()) {
    試す {
      //ステータスを取得
ドレインステータス
      // 3つの状態のみが許可されます
      ドレインステータス >= PROCESSING_TO_IDLE の場合 {
戻る;
      }
      処理中からアイドル状態に移行します。
      //メモリ調整タスクdrainBuffersTaskを非同期に呼び出す
      executor()。drainBuffersTaskを実行します。
    } キャッチ (Throwable t) {
      logger.log(レベル.WARNING、 「メンテナンス タスクの送信時に例外がスローされました」 、t);
      メンテナンス(/* 無視されます */ null );
    ついに
      削除ロックを解除します。
    }
  }
 }

上記の手順から、put プロセスは次のようになります。最初に要素をキャッシュに書き込み、次にスケジュールをトリガーします。スケジュールは、アイドル状態とビジー状態に基づいて非同期の dockBuffersTask を実行するかどうかを決定します。

get のプロセスは put のプロセスと似ています。get はキーの使用方法を変更し、有効期限の結果に影響を与えるため、最終的には、drainBuffersTask をトリガーしてメンテナンスメソッドを実行し、キャッシュをクリーンアップする可能性があります。

 void メンテナンス(@Nullable 実行可能なタスク) {
  処理中からアイドル状態に移行します。 
 
  試す {
    //読み取りキャッシュを取り出す
    バッファをドレインします。
  //書き込みキャッシュを空にする
    バッファをドレインします。
    タスクがnullの場合
      タスクを実行します。
    } 
   
    //キー参照を除外する
    キー参照を排出します。
    //値参照を除外する
    ドレイン値参照();
    //期限切れのエントリ
    エントリの有効期限が切れます。
    //エントリを削除
    エントリを削除します。
  ついに
    ドレインステータス() が PROCESSING_TO_IDLE の場合 || casDrainStatus(PROCESSING_TO_IDLE, IDLE) の場合 {
      lazySetDrainStatus(必須);
    }
  }
 }

データ構造

前の記事では、Caffeine がすべてのデータを格納するために ConcurrencyHashMap を使用することについて説明しましたが、このセクションでは主に有効期限の削除戦略で使用されるデータ構造について説明します。書き込み有効期限は writeOrderDeque を使用しますが、これは比較的単純なのでこれ以上の説明は必要ありません。読み取り有効期限は比較的複雑で、W-TinyLFU の構造とアルゴリズムを使用します。

インターネット上には、W-TinyLFU 構造を紹介する記事がたくさんあります。ぜひチェックしてみてください。ここでは、主にソースコードから分析します。一般的には、accessOrderEdenDeque、accessOrderProbationDeque、accessOrderProtectedDeque の 3 つの両端キューを使用します。両端キューを使用する理由は、LRU アルゴリズムをサポートする方が便利だからです。

accessOrderEdenDeque は eden 領域に属し、データの 1% をキャッシュし、残りの 99% はメイン領域にキャッシュされます。

accessOrderProbationDeque はメイン領域に属し、メインのデータの 20% をキャッシュします。この部分はコールドデータであり、すぐに削除されます。

accessOrderProtectedDeque はメイン領域に属し、メインのデータの 20% をキャッシュします。この部分はホットデータであり、キャッシュ全体のメインメモリ領域です。

まず消去法のエントリを見てみましょう。

 void evictEntries() {
  if (!evicts()) {
戻る;
  }
  //まずedn領域から削除
int候補 = evictFromEden();
  //edenによって削除されたデータはメインエリアに入り、その後メインエリアから削除されます
  evictFromMain(候補者);
 }

accessOrderEdenDeque は、W-TinyLFU の W(window) に相当します。最新の書き込みデータの参照を格納します。LRU 消去を使用します。ここでのデータは主にバーストトラフィックの問題に対処するために使用されます。消去されたデータは accessOrderProbationDeque に入ります。コードは次のとおりです。

 intエデンからの退去() {
 int候補 = 0;
  ノード<K, V> ノード = accessOrderEdenDeque().peek();
  edenWeightedSize() が edenMaximum() より大きい場合
    // 保留中の操作によりサイズが調整されます 正しい体重を反映する
    if (ノード == null ) {
      壊す;
    } 
 
    ノード<K, V> next = node.getNextInAccessOrder();
    （node.getWeight() != 0）の場合{
      ノードを初期化します。
      // まずエデンエリアから削除
      accessOrderEdenDeque().remove(ノード);
      //削除されたデータはメインエリアの試用キューに追加されます
      accessOrderProbationDeque() にノードを追加します。
      候補者++; 
 
      edenWeightedSize を遅延設定します (edenWeightedSize() - node.getPolicyWeight());
    }
    ノード =次;
  } 
 
候補者を返す。
 }

データが試用キューに入った後、次のコードの実行を続けます。

 void evictFromMain( int候補) {
 int被害者キュー = PROBATION;
  ノード<K, V>犠牲者 = accessOrderProbationDeque().peekFirst();
  ノード<K, V> 候補 = accessOrderProbationDeque().peekLast();
  (weightedSize() > maximum()) の場合 {
    //候補者を追い出そうとするのをやめ、常に被害者を優先する
    （候補者数 == 0）の場合{
      候補 = null ;
    } 
 
    //保護されたキューとエデンキューから削除を試みる
    if ((候補 == null ) && (犠牲者 == null )) {
      if (victimQueue == PROBATION) {
        被害者 = accessOrderProtectedDeque().peekFirst();
        被害者キュー = 保護されています;
続く;
      }そうでない場合 (victimQueue == PROTECTED) {
        被害者 = accessOrderEdenDeque().peekFirst();
        被害者キュー = EDEN;
続く;
      } 
 
      // 保留中の操作によりサイズが調整されます 正しい体重を反映する
      壊す;
    } 
 
    //重みがゼロのエントリをスキップする
    被害者がnullの場合、victim.getPolicyWeight() は 0 になります。
      被害者 = 被害者.getNextInAccessOrder();
続く;
    }そうでない場合 ((候補 != null ) && (candidate.getPolicyWeight() == 0)) {
      候補 = 候補.getPreviousInAccessOrder();
      候補者--;  
続く;
    } 
 
    //エントリが1 つだけ存在する場合はすぐに削除します
    被害者がnullの場合
      候補者--;  
      ノード<K, V> evict = 候補;
      候補 = 候補.getPreviousInAccessOrder();
      evictEntry(evict, RemovalCause.SIZE , 0L);
続く;
    }そうでない場合 (候補 == null ) {
      ノード<K, V> evict =victim;
      被害者 = 被害者.getNextInAccessOrder();
      evictEntry(evict, RemovalCause.SIZE , 0L);
続く;
    } 
 
    // エントリが収集された場合はすぐに削除します
    K 被害者キー = 被害者.getKey();
    K 候補キー = 候補.getKey();
    被害者キーがnullの場合
      ノード<K, V> evict =victim;
      被害者 = 被害者.getNextInAccessOrder();
      evictEntry(evict, RemovalCause.COLLECTED, 0L);
続く;
    }そうでない場合 (候補キー == null ) {
      候補者--;  
      ノード<K, V> evict = 候補;
      候補 = 候補.getPreviousInAccessOrder();
      evictEntry(evict, RemovalCause.COLLECTED, 0L);
続く;
    } 
 
    // 候補の重みが最大値を超えた場合は直ちに排除する
    （候補.getPolicyWeight() > 最大値()）の場合{
      候補者--;  
      ノード<K, V> evict = 候補;
      候補 = 候補.getPreviousInAccessOrder();
      evictEntry(evict, RemovalCause.SIZE , 0L);
続く;
    } 
 
    //最も頻度の低いエントリを削除します
    候補者--;  
    // コア アルゴリズムは次のとおりです。試用期間の先頭と末尾から 2 つのノードを取得し、それらの頻度を比較します。頻度の小さい方が削除されます。
    if (admit(候補キー、被害者キー)) {
      ノード<K, V> evict =victim;
      被害者 = 被害者.getNextInAccessOrder();
      evictEntry(evict, RemovalCause.SIZE , 0L);
      候補 = 候補.getPreviousInAccessOrder();
    }それ以外{
      ノード<K, V> evict = 候補;
      候補 = 候補.getPreviousInAccessOrder();
      evictEntry(evict, RemovalCause.SIZE , 0L);
    }
  }
 }

上記のコードのロジックは、probation の先頭と末尾から 2 つのノードを取得し、頻度を比較することです。頻度の小さい方が削除されます。末尾の要素は、前の部分で eden から削除された要素です。2 段階のロジックを組み合わせると、次のようになります。eden キューで lru によって削除された「候補」が、probation キューで lru によって削除された「排除」と比較されます。敗者は実際にキャッシュから削除されます。比較ロジックを見てみましょう。

ブール値の承認(K 候補キー、K 被害者キー) {
 int被害者の頻度 = 頻度スケッチ()。頻度(被害者キー);
 int候補周波数 = 周波数スケッチ()。周波数(候補キー);
  //候補の頻度が高い場合は、排除された候補を排除する
  （候補者の頻度＞被害者の頻度）の場合{
戻る 真実;
    //追い出されたものの頻度が候補のものより高く、候補の頻度が5以下の場合、追い出されたものは
  }それ以外の場合 (候補頻度 <= 5) {
    // 最大頻度は15で、履歴を古くなるようにリセットすると7に半分になります。攻撃は
    // ホットな候補者がホットな犠牲者のために拒否されるという悪用。ホットな候補者の閾値は
    // 候補者はランダム承認の数を減らしてヒット率への影響を最小限に抑えます。
戻る 間違い;
  }
  //ランダム排除
intランダム = ThreadLocalRandom.current ().nextInt() ;
 ((ランダム & 127) == 0)を返します。
 }

候補者と排除される人の頻度を、frequencySketch から取得します。候補者の頻度が高い場合は、排除される人を排除します。排除される人の頻度が候補者の頻度より高く、候補者の頻度が 5 以下の場合は、排除される人を排除します。最初の 2 つの条件が満たされない場合は、排除される人をランダムに排除します。

protectedDeque はプロセス全体に効果がないことがわかりましたか? ほとんどのデータを保存するメインメモリ領域としてどのように機能するのでしょうか?

 //onAccessメソッドはこのメソッドをトリガーします
void 再順序付けプロバクション(Node<K, V> ノード) {
  if (!accessOrderProbationDeque(). contains (node)) {
    //エントリの古いアクセスを無視します もはや存在しない
戻る;
  }そうでない場合 (node.getPolicyWeight() > mainProtectedMaximum()) {
戻る;
  } 
 
  mainProtectedWeightedSize を長くすると、 mainProtectedWeightedSize() と node.getPolicyWeight() が返されます。
 //まずは試用期間から外す
 accessOrderProbationDeque().remove(ノード);
 //保護対象に追加
  accessOrderProtectedDeque() にノードを追加します。
  ノードをProtectedにする
 
  mainProtectedMaximum は、次の式で定義されます。
 //保護から削除
  mainProtectedWeightedSize が mainProtectedMaximum より大きい場合、
    降格されたノード<K, V> = accessOrderProtectedDeque().pollFirst();
    if (降格 == null ) {
      壊す;
    }
    降格.makeMainProbation();
    //試用期間に追加
    accessOrderProbationDeque()を追加します(降格) 。
    メインの保護された重み付けサイズ -= node.getPolicyWeight();
  } 
 
  mainProtectedWeightedSize を遅延設定します。
 }

データがアクセスされ、保護状態にある場合、データは保護状態に移動され、同時に、データは保護状態から削除され、lru を通じて保護状態に置かれます。

このように、データフローのロジックは完全に接続されています。新しいデータは Eden に入り、LRU によって Probation に排除され、Probation で LRU によって排除されたデータと使用頻度を競います。勝った場合は、引き続き Probation に留まります。失敗した場合は、直接排除されます。このデータにアクセスすると、Protected に移動されます。他のデータにアクセスすると、lru を通じて保護から保護対象に削除される可能性があります。

小さなLFU

従来の LFU では、一般的にキーと値の形式を使用して各キーの頻度を記録します。利点は、データ構造が非常にシンプルで、キャッシュ自体のデータ構造で再利用できることです。頻度を記録するには、属性を追加するだけです。欠点は、頻度属性が多くのスペースを占有することです。しかし、頻度が圧縮された方法で保存されている場合はどうでしょうか。頻度が占めるスペースは確かに削減できますが、別の問題が発生します。圧縮されたデータから対応するキーの頻度を取得するにはどうすればよいでしょうか。

TinyLFU のソリューションはビットマップ方式に似ています。キーをハッシュしてビットインデックスを取得し、そのインデックスを使用して頻度を見つけます。ただし、ビットマップには 0 と 1 の 2 つの値しかないため、頻度が非常に大きくなる可能性があります。これをどのように処理しますか? さらに、ビットマップの使用には非常に大きなスペースが必要です。この問題をどのように解決しますか?

TinyLFU は、最大データサイズ設定に従って long 配列を生成し、4 つの long の 4 ビットに頻度値を保存します (4 ビットは 15 を超えません)。頻度値を取得するときは、4 つのうち最小の値が取得されます。

Caffeine は、15 を超える周波数を非常に高いものと見なし、ホットデータと見なすため、それらの保存には 4 ビットしか必要ありません。Long は 8 バイトと 64 ビットなので、16 の周波数を保存できます。ハッシュ値を取得し、それを左に 2 桁シフトしてから、ハッシュを 4 回追加します。この方法では、16 のうち 13 を使用できるため、使用率が高くなります。おそらく、16 すべてを使用できるより優れたアルゴリズムがあるでしょう。

パブリックvoid 増分(@Nonnull E e) {
    初期化されていない場合
戻る;
    } 
 
 intハッシュ = spread(e.hashCode());
 int開始 = (ハッシュ & 3) << 2; 
 
    // ループ展開によりスループットが500 万オペレーション/秒向上します
int index0 = indexOf(hash, 0); //indexOf もハッシュメソッドですが、tableMask によって範囲が制限されます。
 int index1 = indexOf(ハッシュ、1);
 int index2 = indexOf(ハッシュ、2);
 int index3 = indexOf(ハッシュ、3); 
 
    ブール値 added = incrementAt(index0, start);
    追加 |= incrementAt(index1, start + 1);
    追加 |= incrementAt(index2, start + 2);
    追加 |= incrementAt(index3, start + 3); 
 
    //データ書き込み回数がデータ長に達したらリセットする
    if (追加 && (++サイズ== サンプルサイズ)) {
      リセット();
    }
  }

対応するビット位置の 4 ビット Int 値に 1 を加算します。

ブール増分( int i, int j) {
 intオフセット = j << 2;
  ロングマスク = (0xfL << オフセット);
  //15に達すると、その数はそれ以上増加しなくなります
  if ((テーブル[i] & マスク) != マスク) {
テーブル[i] += (1L << オフセット);
戻る 真実;
  }
戻る 間違い;
 }

値を取得する方法は、4 つのハッシュを介して取得し、最小値を取得することです。

公共  int頻度(@Nonnull E e) {
  初期化されていない場合
0を返します。
  } 
 
 intハッシュ = spread(e.hashCode());
 int開始 = (ハッシュ & 3) << 2;
 int頻度 = Integer.MAX_VALUE ;
  //4つのハッシュ
( int i = 0; i < 4; i++)の場合{
整数 インデックス= indexOf(ハッシュ、i);
    // 4ビットのInt値を取得する
整数  count = ( int ) ((テーブル[インデックス] >>> ((start + i) << 2)) & 0xfL);
    //最小値を取得する
    頻度 = Math.min (頻度、カウント);
  }
返品頻度;
 }

データの書き込み数がデータ長に達すると、その数は半分になります。このプロセス中に一部のコールドデータが 0 にリセットされ、ハッシュの競合が減少します。

 void リセット() {
整数 カウント= 0;
 ( int i = 0; i <テーブル.length; i++) {
 count += Long.bitCount(テーブル[i] & ONE_MASK);
テーブル[i] = (テーブル[i] >>> 1) & RESET_MASK;
  }
サイズ= (サイズ>>> 1) - (カウント>>> 2);
 }