問題タブ [lru]

（まず第一に、私の英語はあまり上手ではありません、お願いします）

私たちが知っているように、memcached は遅延有効期限を提供し、スラブ内の LRU データを「置き換え」ますが、これがどのように行われるかはよくわかりません。たとえば、スラブがいっぱいで、このスラブ内の一部のデータの有効期限が切れている場合、データがスラブに追加されるとどうなりますか?

1. memcached は期限切れのデータを見つけて、それらを追加されたデータに置き換えますか、または
2. LRU データを置き換えるか、または
3. それは何か他のことをしますか？

私の知る限り、遅延有効期限は、memcached が各スラブから期限切れのデータを積極的に削除するのではなく、期限切れのエントリのキーが参照されたときに期限切れのエントリのみを削除するようなものです。これは資源の無駄ですよね？

メモリ アドレスを格納する非常に単純な LRU キャッシュを実装する必要があります。

• これらのアドレスの数は (実行時に) 固定されています。
• 最後に使用されたアドレスのみに関心があります (他の要素の順序は気にしません)。
• 各アドレスには対応するインデックス番号 (単純な整数) がありますが、これは一意ではなく、変更される可能性があります。

実装は、可能な限り少ないオーバーヘッドで実行する必要があります。各アドレスに加えて、関連する情報構造 (インデックスを含む) もあります。

私の現在のアプローチはstd::list、アドレス/情報のペアを格納するために a を使用しており、boost::unordered_multimapこれはインデックスとリストの関連する反復子の間のマッピングです。

次の例は、私の製品コードとは関係ありません。これは、理解を深めるためのものであることに注意してください。

次の3つのコンポーネントで構成されるデータがあります。

• a_path
• a_key
• a_value =f(a_path, a_key)

a_value計算に費用がかかるので、あまり計算したくないです。理想的な世界では、それはそれが変化するときだけです。したがって、このキャッシュの要件は次のとおりです。

• 最大サイズを構成可能なLRUキャッシュ
• キーオン(a_path, a_key)
• 年齢に基づいてエントリを期限切れにする機能（たとえば、1時間ごとに再計算します）
• に基づいてエントリを期限切れにする機能expiry_func(a_path, a_key)

私のグーグルはここで私を失敗させました。「elispLRUcache」を検索してもJavaサイトがたくさん見つかります。

ページ フォールトまたはキャッシュ ミスが発生した場合、Least Recent Used (LRU)、First in Fist Out (FIFO)、またはランダム置換アルゴリズムのいずれかを使用できます。私が疑問に思っていたのは、将来のキャッシュ ミス/ページ フォールトの可能性が最も低い、最高のパフォーマンスを提供するのはどれですか?

アーキテクチャ: Coldfire プロセッサ

新しい Android クラスLruCacheはスレッドセーフですか? Java doc は次のように述べています。

このクラスはスレッドセーフです。キャッシュで同期することにより、複数のキャッシュ操作をアトミックに実行します。

彼らは、スレッドセーフではないと言うつもりでしたか? クラスがスレッドセーフである場合、なぜ同期する必要があるのでしょうか?

ありがとう！

JavaのLinkedHashMapのようなPerlのデータ構造はありますか？

またはPerlのLRUデータ構造

更新：@TLP基本的にハッシュテーブルデータ構造が必要ですが、キーの順序を維持したり、リスト内のキーを処理した後にキーを削除したりすることもできます。

Update：@ccheneson Tie :: IxHash 1つは私が望むものではないようです、最も古いキーをPOPしたいのですが、tie :: ixHashは最新のキーをポップアップします、Tie :: IxHashで最も古いキーと値のペアを取得するにはどうすればよいですか？キュー構造（およびハッシュ構造も、最も簡単な方法でキーを見つけたい）が欲しいのですが、新しいキーと値のペアが入り続け、最も古いキーを処理し続け、最も古いキーを削除します。

Update：@ FMc Tie :: IxHashは私が必要としているものであり、Tie :: IxHash-> Shift（）はキューポップを実行しますTie :: IxHash-> Push（）はキュープッシュを実行します。これはハッシュ構造であり、キーを簡単に見つけることができます。

皆さんありがとう。

最近使用したキャッシュを設計するにはどうすればよいですか？

あなたがいくつかのアイテムを訪れたとしましょう。これらのアイテムを保持するためのデータ構造を設計する必要があります。各アイテムは、最後に訪問した時間に関連付けられています。

アイテムにアクセスするたびに、データ構造でそのアイテムを確認してください。アイテムがキャッシュにある場合は、その訪問時間を更新します。それ以外の場合は、キャッシュに挿入します。キャッシュサイズは固定されています。キャッシュサイズがいっぱいの場合は、最も古いアイテムを削除してください。

私の解決策：

1. マップを使用<item、visitTime>

2. 初期化：マップをf（visitTime）で降順に並べ替えます。O（nlg n）

3. アイテムにアクセスした場合は、マップでO（lg n）を使用してアイテムを検索します。

4. マップにある場合は、時刻O（1）を更新します。マップO（lg n）を並べ替えます。

5. そうでない場合は、マップに挿入してから並べ替えます。O（lg n）

6. マップサイズ>固定サイズの場合、最後の要素O（1）を削除します。

別の解決策：

1. ハッシュテーブルを使用<item、visitTime>

2. O（n lgn）で並べ替えます。

3. アイテムが訪問された場合、O（1）を使用してタルブでアイテムを検索します。

4. テーブルにある場合は、時刻O（1）を更新します。テーブルO（n lg n）を並べ替えます。

5. そうでない場合は、テーブルに挿入してから並べ替えます。O（n lg n）

6. テーブルサイズ>固定サイズの場合、最後の要素O（1）を削除します。

より良い解決策はありますか？の上） ？

誰かが Redis LRU ベースのエビクション/削除の内部について知っていますか?

古い (あまり使用されていない) キーが最初に削除されることを Redis はどのように保証しますか (揮発性キーがなく、TTL の有効期限を設定していない場合)?

Redis には、キーの削除に使用するサンプル サイズを管理する構成パラメーター「maxmemory-samples」があることは確かです。そのため、サンプル サイズを 10 に設定すると、10 個のキーがサンプリングされ、その中から最も古いキーが削除されます。

私が知らないのは、これらのキーを完全にランダムにサンプリングするのか、それとも「古い/あまり使用されていない世代」に相当するものから自動的にサンプリングできるメカニズムがあるのか​​ ということです?

メモリ使用量に制限のあるlruキャッシュを使用しています。lruキャッシュには、ハッシュマップとリンクリストの2つのデータ構造が含まれています。ハッシュマップはキャッシュオブジェクトを保持し、リンクリストはキャッシュオブジェクトのアクセス順序の記録を保持します。Javaオブジェクトのメモリ使用量を判断するために、オープンソースツールであるClassmexerエージェントを使用します。Classmexerエージェントは、http： //www.javamex.com/classmexer/にある単純なJavaインストルメンテーションエージェントです。

http://sizeof.sourceforge.net/でSizeOfという名前の別のツールを試します。

問題は、パフォーマンスが非常に高いことです。オブジェクトサイズを測定するための1回の操作の時間コストは約1.3秒であり、非常に低速です。これにより、キャッシングのメリットをゼロにすることができます。

生きているときにJavaオブジェクトのメモリサイズを測定する他の解決策はありますか？

ありがとう。

キャッシングの最初のレイヤーをAndroidアプリに実装することを考えています。確かにOOM例外を回避するためにSoftReferencesを検討していましたが、Androidがこれらを「早すぎる」解放する方法についての記事がたくさんあるので、android.util.LruCacheキャッシュを調べることにしました。

質問：実際のデバイスに合わせて適切にサイズを変更するにはどうすればよいですか？LRUキャッシュが実際のソリューションであり、SoftReferencesではないことは非常に良いことのように思えますが、OOM Exceptionsを避けたい場合は、メガバイト単位のハードリファレンスを使用するのは非常に危険です。あなたが私に尋ねるなら、それはただ危険です。とにかく、これが唯一の選択肢のようです。getMemoryClassを調べて、実際のデバイス上のアプリのヒープサイズを調べていました（+キャッシュのサイズを変更する前に空きヒープサイズを確認しました）。ベースラインは16メガバイトで問題ないように聞こえますが、デバイス（たとえば、昔はG1）が約5メガバイトのヒープサイズ（Eclipse MATによる）のOOM例外をスローするのを見てきました。G1が非常に古いことは知っていますが、重要なのは、私の経験が、ドキュメントに記載されている16メガベースのベースラインと実際には一致していないということです。だらか、私' m合理的に取得できる最大のものが必要な場合、LRUキャッシュをどのようにスケールアップする必要があるかが完全にわかりません。（8メガで満足し、低スペックのデバイスでは1メガで十分です）

ヒントをありがとう。

編集：私が参照しているAndroid LRUキャッシュクラス：http：//developer.android.com/reference/android/util/LruCache.html