この記事では、Redis の LRU (Least Recent Used) について紹介します。
Redis ビデオ チュートリアル ]
Linux オペレーティング システムはスワップを表示できます。 through free -m Size: \
redis.conf ファイルの構成項目の概略図: \
この記事では LRU についてのみ説明し、LFU は含まれません、LFU については次の記事で説明します) を提供し、次の条件を満たすキーを削除します。古いものに別れを告げ、新しいものを歓迎する条件。
maxmemory-policy 排除ポリシー:
ランダムなランダム削除では、メモリ領域を削除して解放するためにいくつかのキーをランダムに選択するだけで済みます。ttl の有効期限は短く、ttl のサイズとキーを比較することによって最初にキーが削除されます。小さな ttl 値は削除されます。メモリ領域を解放するだけです。
4. LRU アルゴリズムの実装
package com.lizba.redis.lru;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;
/**
* <p>
* LRU简单实现
* </p>
*
* @Author: Liziba
* @Date: 2021/9/17 23:47
*/
public class SimpleLru {
/** 数据缓存 */
private ConcurrentHashMap<string> cacheData;
/** 访问顺序记录 */
private ConcurrentLinkedDeque<string> sequence;
/** 缓存容量 */
private int capacity;
public SimpleLru(int capacity) {
this.capacity = capacity;
cacheData = new ConcurrentHashMap(capacity);
sequence = new ConcurrentLinkedDeque();
}
/**
* 设置值
*
* @param key
* @param value
* @return
*/
public Object setValue(String key, Object value) {
// 判断是否需要进行LRU淘汰
this.maxMemoryHandle();
// 包含则移除元素，新访问的元素一直保存在队列最前面
if (sequence.contains(key)) {
sequence.remove();
}
sequence.addFirst(key);
cacheData.put(key, value);
return value;
}
/**
* 达到最大内存，淘汰最近最少使用的key
*/
private void maxMemoryHandle() {
while (sequence.size() >= capacity) {
String lruKey = sequence.removeLast();
cacheData.remove(lruKey);
System.out.println("key: " + lruKey + "被淘汰！");
}
}
/**
* 获取访问LRU顺序
*
* @return
*/
public List<string> getAll() {
return Arrays.asList(sequence.toArray(new String[] {}));
}
}复制代码</string></string></string>package com.lizba.redis.lru;
/**
* <p>
* 测试最近最少使用
* </p>
*
* @Author: Liziba
* @Date: 2021/9/18 0:00
*/
public class TestSimpleLru {
public static void main(String[] args) {
SimpleLru lru = new SimpleLru(8);
for (int i = 0; i <strong></strong>テスト結果: \<p><strong></strong></p><p> 上記のテスト結果から、最初に追加された key0 と key1 が削除され、最後に追加されたキーもシーケンスの先頭に保存された最新のキーであることがわかります。 <img src="https://img.php.cn/upload/image/775/594/750/163409191823487Redis%E3%81%AELRU%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC%E3%81%97%E3%81%9F%E8%A8%98%E4%BA%8B" title="163409191823487RedisのLRUアルゴリズムを詳しく解説した記事" alt="RedisのLRUアルゴリズムを詳しく解説した記事">このソリューションを通じて、LRU アルゴリズムは簡単に実装できますが、欠点も非常に明らかです。このソリューションでは、キー アクセス シーケンスを保存するために追加のデータ構造を使用する必要があるため、Redis のメモリ消費量が増加し、それ自体がメモリの最適化: この解決策は大量のメモリを消費しますが、これは明らかに実現不可能です。 </p><p></p><h2 data-id="heading-4">5. Redis のおおよその LRU </h2><p>この状況に対応して、Redis は近似 LRU アルゴリズムを使用しますが、最近最も使用頻度の低いキーを削除する点では完全に正確ではありませんが、全体的な精度も高くなります。保証されています。 <br>近似 LRU アルゴリズムは非常に単純です。Redis キー オブジェクトには、最新のアクセスのシステム タイムスタンプを格納するために 24 ビットが追加されます。クライアントがキー書き込み関連のリクエストを Redis サーバーに送信すると、次のことがわかります。メモリが maxmemory に達すると、遅延削除がトリガーされ、Redis サービスはランダム サンプリングを通じて条件を満たす 5 つのキーを選択します (このランダム サンプリング <strong>allkeys-lru</strong> はすべてのキーからランダムにサンプリングされることに注意してください。 ##volatile-lru<strong>有効期限が設定されたすべてのキーからランダムにサンプリングされます)、キー オブジェクトに記録されている最新のアクセス タイムスタンプと比較し、メモリがまだ十分でない場合は、これら 5 つのキーのうち最も古いキーを削除します続けてこのステップを繰り返します。 </strong><br></p><p>5 は Redis のデフォルトのランダム サンプリング値のサイズであり、redis.conf の maxmemory_samples を通じて構成できることに注意してください。 <strong></strong>## 上記のランダム LRU アルゴリズムに関して、Redis はテスト精度のデータ チャートを公式に提供しています。 </p><p><img src="https://img.php.cn/upload/image/866/655/134/163409192913128Redis%E3%81%AELRU%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC%E3%81%97%E3%81%9F%E8%A8%98%E4%BA%8B" title="163409192913128RedisのLRUアルゴリズムを詳しく解説した記事" alt="RedisのLRUアルゴリズムを詳しく解説した記事"></p>#最上位層の明るい灰色は、削除されたキーを示します。図図 1 は、標準的な LRU アルゴリズムの削除の概略図です。<p><strong>中央の濃い灰色のレイヤーは、削除されていない古いキーを表します。</strong></p>一番下の薄緑色のレイヤーは、最近アクセスされたキーを表します。 key の LRU アルゴリズムよりも正確です。これは、Redis3.0 が maxmemory_samples と同じサイズの消去プールを追加するためです。キーが消去されるたびに、プール内で削除待ちのキーを比較し、最終的に最も古いキーを削除します 実際には、削除対象に選択されたキーをまとめて比較し、その中で最も古いキーを削除します。
LRU アルゴリズムは使いやすそうに見えますが、エリミネーション 1 時間前には 2 つのキー A と B が同じであったなど、不合理な箇所もあります。 Redis に時間が追加されます。A は最初の 49 分間に 1,000 回アクセスされましたが、最後の 11 分間はアクセスされませんでした。B は、この時間の 59 分間に 1 回のみアクセスされました。この時点で LRU アルゴリズムが使用されている場合、 Redis サンプリングによって A、B がすべて選択され、A が除外される場合、これは明らかに不合理です。 このような状況を受けて、Redis 4.0 では、最も使用頻度の低い LFU アルゴリズム (Leastfrequency used) が追加されました。このアルゴリズムは、LRU よりも合理的です。除去アルゴリズムについては、以下で一緒に学習します。必要に応じて、私のコラムに注目してください。
以上がRedisのLRUアルゴリズムを詳しく解説した記事の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
