3 つのヒープ内キャッシュアルゴリズム (ソースコードと設計アイデア付き)

トレードオフを最もよく反映するコンピュータシステムのテクノロジといえば、それはキャッシュです。高速コンポーネントと低速コンポーネント間の速度差を調整するには、中間キャッシュ層を追加することが、この競合を解決する最も効果的なソリューションです。

[[325756]]

その中でも、JVM ヒープキャッシュはキャッシュシステムの重要な部分であり、最も一般的に使用されるアルゴリズムは FIFO/LRU/LFU です。

FIFO は、先入れ先出しの単純なキューです。
LRU は Least Recently Used の略で、最も長く使用されていないデータが最初に削除されます。それは時間の次元です。
LFU は最も最近使用されていないデータであり、アクセス回数が最も少ないデータが最初に削除されます。それは統計的な次元です。

有効期限もキャッシュの重要な機能だからです。したがって、これら 3 つのキャッシュアルゴリズムを設計する場合、有効期限を保存するための追加のストレージスペースが必要になります。

以下では、これら 3 つのキャッシュアルゴリズムの動作と設計のポイントについて説明しますが、現時点では高同時実行環境は考慮されていません。

先入れ先出し

先入れ先出し。キャッシュ容量がいっぱいの場合、最初にキャッシュに追加されたデータが最初に削除されます。これを実装するには、内部的にキューを使用できます。

操作する

Object get(key): 保存されたデータを取得します。データが存在しないか期限が切れている場合は null が返されます。
void put(key, value, expireTime): キャッシュに追加します。このキーがすでに存在するかどうかに関係なく、新しいキーとして扱われます (古いキーは削除されます)。十分なスペースがない場合は、期限切れのキーが削除されます。スペースがない場合は、キャッシュに追加された最も古いキーが削除されます。有効期限が指定されていない場合は、自動的に期限切れになることはありません。
通常の FIFO とは異なり、キーに有効期限を持たせることができるので、この問題を設計する際にはこれに注意する必要があります。（インタビューのポイントでもある、アルゴリズムよりもデザイン重視）

普通の FIFO は誰でも簡単に書けると思いますが、有効期限を考慮すると、設計時にさらに考慮が必要になります。次の例は、同時実行環境を考慮しない FIFO 設計です。

デザインのアイデア

1) 通常の hashMap を使用してキャッシュデータを保存します。

2) キーの有効期限特性を保存するには、追加のマップが必要です。この例では、TreeMap を使用し、「残りの生存時間」をキーとして取り、TreeMap のソート特性を活用します。

パブリッククラス FIFOCache { 
   
    // アクセス時間でソートし、すべてのキーと値を保存します
    プライベート最終 Map<String,Value> CACHE = new LinkedHashMap<>(); 
   
    //期限切れデータ、有効期限のあるキーのみ保存 
    // 現時点では並行性を考慮していないため、同時に重複するキーはないと考えられます。変更された場合、値はsetによって置き換えられます。  
    プライベート最終 TreeMap<Long, String> EXPIRED = new TreeMap<>(); 
   
    プライベート最終int容量; 
   
パブリックFIFOCache( int容量) {
        this.capacity = 容量;
    } 
   
パブリックオブジェクト get(文字列キー) {
        //
        値 value = CACHE.get( key );
        値 == nullの場合
戻る ヌル;
        } 
   
        //有効期限が含まれていない場合
        long 期限切れ = value.expired;
        long now = System.nanoTime();
        //期限切れ
        if (期限切れ > 0 && 期限切れ <= 現在) {
            CACHE.remove(キー);
            EXPIRED.remove(期限切れ);
戻る ヌル;
        }
戻り値.値;
    } 
   
 public void put(文字列キー、オブジェクト値) {
        put(キー,値,-1);
    } 
   
   
 public void put(String key ,Object value, int seconds) {
        //容量が足りない場合は期限切れのデータを削除する
        （容量< CACHE.size ()）の場合{
            long now = System.nanoTime();
            //期限切れのものがあればすべて削除します
            イテレータ<Long> iterator = EXPIRED.keySet().iterator();
            (イテレータ.hasNext()) の間 {
                長い_key = iterator.next ();
                // 期限が切れていたり、容量がまだオーバーフローしている場合は削除します
                if (_key > now) {
                    壊す;
                }
                // 期限切れのキーを一度にすべて削除する 
                文字列 _value = EXPIRED.get(_key);
                CACHE.remove(_value);
                イテレータを削除します。
            }
        } 
   
        //容量がまだ不十分な場合は、最も早くアクセスされたデータを削除します
        容量 < CACHE.size () の場合 {
            イテレータ<String> iterator = CACHE.keySet().iterator();
            (iterator.hasNext() && 容量 < CACHE.size ()) の場合 {
                文字列 _key = iterator.next ();
                値 _value = CACHE.get(_key);
                長い有効期限 = _value.expired;
                期限切れ > 0 の場合 {
                    EXPIRED.remove(期限切れ);
                }
                イテレータを削除します。
            }
        } 
   
        //このキーがすでに存在する場合は、古いデータを削除します
        現在の値= CACHE.remove(キー);
        現在の有効期限がnull の場合、現在の有効期限が 0 より大きい場合
            EXPIRED.remove(現在の.expired);
        }
        //有効期限が指定されている場合
        if(秒数 > 0) {
            long expireTime = expiredTime(秒);
            EXPIRED.put(expireTime,キー);
            CACHE.put(キー、新しい値(expireTime、値));
        }それ以外{
            CACHE.put(キー、新しい値(-1、値));
        } 
   
    } 
   
    プライベートlong expiredTime( int expired) {
 System.nanoTime() + TimeUnit.SECONDS.toNanos(期限切れ)を返します。
    } 
   
パブリックvoid 削除(文字列キー) {
        値 value = CACHE.remove( key );
        値 == nullの場合
戻る;
        }
        long 期限切れ = value.expired;
        期限切れ > 0 の場合 {
            EXPIRED.remove(期限切れ);
        }
    } 
   
   
    クラス値{
        long expired; //有効期限、ナノ秒
        オブジェクトの値。
        値(有効期限切れ,オブジェクト値) {
            this.expired = 期限切れ;
            this.value = 値;
        }
    }
 }

LRU

最も最近使われていないキャッシュは、最も一般的に使用されているキャッシュアルゴリズムおよび設計スキームの 1 つです。その削除戦略は、「キャッシュ (ページ) がいっぱいになると、最も最近使われていないデータが最初に削除されます」というものです。利点は、設計と使用が簡単で、適用可能なシナリオの範囲が広いことです。アルゴリズムは、leetcode 146 (LRU キャッシュ) を参照できます。

操作する

Object get(key): キャッシュからキーに対応するデータを取得します。キーの有効期限が切れている場合は、キーを削除して null を返します。
void put(key, value, expired): kv を設定します。容量が不足している場合は、LRU 置換アルゴリズムに従って「最も長い未使用キー」を削除します。期限切れのキーは LRU に従って最初に削除されることに注意してください。期限切れのキーがない場合は、期限切れでないキーが LRU に従って削除されます。有効期限が設定されていない場合は、自動的に期限切れにならないものとみなされます。
ここでの重要な設計は、従来の LRU とは異なる有効期限機能です。

デザインのアイデア

LRU の基本的なアルゴリズムを理解する必要があります。キーに対応するアクセス時間は、put または get が実行されるたびに更新される必要があります。キーの最新のアクセス時間を保存し、それを並べ替えることができるデータ構造が必要です。
有効期限機能が含まれているため、有効期限付きのキーを追加のデータ構造に保存する必要があります。
並行操作は現時点では考慮されません。空間の複雑さと時間の複雑さのバランスをとるようにしてください。
この質問は、純粋なアルゴリズムの質問というよりも、むしろ設計に関する質問です。

この質問のコードは基本的に FIFO と同じですが、唯一の違いは get() メソッドです。LRU の場合、get メソッドはアクセス時間をリセットする必要があります (つまり、キャッシュ内の順序を調整します)。

パブリックオブジェクト get(文字列キー) {
    //
    値 value = CACHE.get( key );
    値 == nullの場合
戻る ヌル;
    } 
   
    //有効期限が含まれていない場合
    long 期限切れ = value.expired;
    long now = System.nanoTime();
    //期限切れ
    if (期限切れ > 0 && 期限切れ <= 現在) {
        CACHE.remove(キー);
        EXPIRED.remove(期限切れ);
戻る ヌル;
    }
    //FIFOと比較して、順序リセットを増やす
    CACHE.remove(キー);
    CACHE.put(キー、値);
戻り値.値;
 }

LFU

最も最近使用されていない、キャッシュ容量がいっぱいになった場合は、アクセス回数が最も少ない要素を削除します。アクセス回数が同じ複数の要素がある場合は、アクセスが最も長い要素を削除します。設計要件については、leetcode 460 (LFU キャッシュ) を参照してください。

パブリッククラスLFUCache{ 
   
    //kv を保存するためのメイン コンテナ
    プライベート Map<String, Object> keyToValue = new HashMap<>(); 
   
    //各kの訪問回数を記録する
    プライベート Map<String, Integer > keyToCount = new HashMap<>(); 
   
    //同じ回数キーリストにアクセスし、アクセス回数でソートし、値は同じアクセス回数のキーリストになります。
    プライベート TreeMap< Integer 、LinkedHashSet<String>> countToLRUKeys = new TreeMap<>(); 
   
    プライベートint容量; 
   
パブリックLFUCache( int容量) {
        this.capacity = 容量;
        // 初期化、デフォルトアクセスは1回、主に次の問題を解決するため
    } 
   
パブリックオブジェクト get(文字列キー) {
        if (!keyToValue.containsKey(キー)) {
戻る ヌル;
        } 
   
        タッチ(キー);
 keyToValue.get(キー)を返します。
    } 
   
    /**
     *キーにアクセスした場合は、そのアクセス回数を調整する必要があります。
     * @paramキー 
     */
    プライベートvoid touch(文字列キー) {
整数  count = keyToCount.get(キー);
        keyToCount.put( key , count + 1); //訪問回数を増やす
        //元の訪問回数リストから削除
        countToLRUKeys.get(カウント).remove(キー); 
   
        //キー統計リストへの呼び出しの最小回数が空の場合、統計への呼び出し回数を削除します
        countToLRUKeys.get( count ) .size () == 0 の場合
            countToLRUKeys.remove(カウント);
        } 
   
        //次に、このキーの統計を管理リストに追加します
        LinkedHashSet<String> countKeys = countToLRUKeys.get( count + 1);
        countKeys がnullの場合
            countKeys = 新しい LinkedHashSet<>();
            countToLRUKeys.put( count + 1, countKeys);
        }
        countKeys.add (キー);
    } 
   
パブリックvoid put(文字列キー、オブジェクト値) {
        （容量<= 0）の場合{
戻る;
        } 
   
        keyToValueにkey( key )が含まれる場合
            keyToValue.put(キー, 値 );
            タッチ(キー);
戻る;
        }
        //容量を超えたら、訪問回数が最も少ない要素を削除します
        ( keyToValue.size () >= 容量) の場合 {
            Map.Entry< Integer 、LinkedHashSet<String>> entry = countToLRUKeys.firstEntry();
            イテレータ<String> it = entry.getValue().iterator();
            文字列evictKey = it.next ();
            削除します。
            if (!it.hasNext()) {
                countToLRUKeys.remove(エントリのキーを取得します());
            }
            keyToCount.remove(evictKey);
            keyToValue.remove(evictKey); 
   
        } 
   
        keyToValue.put(キー, 値 );
        keyToCount.put(キー、1);
        LinkedHashSet<String> キー = countToLRUKeys.get(1);
        キーがnullの場合
            キー = 新しい LinkedHashSet<>();
            countToLRUKeys.put(1,キー);
        }
        keys.add (キー);
    }
 }

終わりこの記事では、キャッシュ構築への道筋を大まかに把握するために、3 つの基本的なキャッシュアルゴリズムを比較します。

よりユーザーフレンドリーなキャッシュについては、Guava の実装を参照してください。これら 3 つのコードテンプレートがお役に立てば幸いです。

著者について: Sister Taste (xjjdog)、プログラマーが寄り道をすることを許可しない公開アカウント。インフラストラクチャと Linux に重点を置きます。 10 年間のアーキテクチャと 1 日あたり数千億のトラフィックを基に、私たちはお客様とともに高並行性の世界を探求し、新たな体験をお届けします。

<<: AIがクラウドコンピューティングを再定義し、ビジネス効率を向上させる方法

>>: クラゲのように見える7cmのガジェットは、実際にはチーターに似た最速のソフトロボットです