介绍
LRU（或最近最少使用）是一种高速缓存逐出策略，其中，如果高速缓存大小已达到最大分配容量，则将逐出高速缓存中最近最少访问的对象。同样，缓存中的对象可以由应用程序中的多个线程访问，因此，缓存具有良好的内置同步机制非常重要。本文介绍了具有LRU逐出策略的基于Java的缓存的实现；但从根本上适用于任何编程语言。
背景
很多时候，开发人员将缓存框架嵌入到他们的应用程序中，例如Ehcache（这是用于通用内存缓存的出色库）。但是，在没有自由使用此类框架或库的情况下，情况有时会发生变化。例如轻量级Java应用程序或移动应用程序的情况，这些应用程序旨在以最小的内存占用量运行（或者有时由于交付截止日期，因此没有多余的时间来学习和配置第三方缓存框架并部署到生产环境中）。在这些时候，可以使用这种简单，轻量级的LRUCache类，并且具有足够的单元测试覆盖率，因此可以大量依赖缓存。
本文介绍了使用ConcurrentHashMap和双链表数据结构通过LRU策略实现高速缓存 。使用LinkedHashMap可以实现相同的效果，但是默认情况下它不是线程安全的（也许在下一篇文章中，我将使用LinkedHashMap提交）。
设计
在设计基于LRU的缓存之前，我们需要了解缓存的一些重要属性：
应该为O操作按O(1)顺序提供最小延迟
支持并发读/写访问
缓存限制应设置为固定大小（就对象数而言）
将新对象插入到缓存中应该总是成功的，并且将由键（唯一）标识
对象驱逐策略应预先定义，在这种情况下为LRU！
考虑以上5个属性，可以使用Java的ConcurrentHashMap（满足属性1-4）和简单的Doubly-Linked-List（满足属性5）来实现简单的LRU缓存。
使用ConcurrentHashMap-保存对象并通过键访问它们，以便访问时间为O（1）顺序，提供并发访问，可以设置大小限制，并且可以使用键访问对象。
双链表（DLL）维护指向相同对象（在映射中）的指针。该DLL帮助我们实现了LRU逐出策略，其中，经常访问的对象将位于尾端，而最少访问的对象将朝列表的开头。将新对象插入缓存时，如果缓存已达到其最大容量，则会触发LRU逐出。基本上从DLL中，将删除头节点（这是最近最少使用的对象），并将其从映射中删除。
流程图
将对象添加到缓存 put(K k, V v)
从缓存中获取对象 get(K k)
使用代码
LRU缓存实现是通过实现LRUCache<K, V>对泛型起作用的类来实现的。此缓存对象由关键字标识， K-唯一可标识的参数（首选不可变对象）和V-值可以是任何类型的自定义对象。如果对另一个对象重复了一个键，则缓存将用较新的对象替换较旧的对象。
对象实例化：
// 1.通过传递初始存储容量（在下面的示例中为10）创建一个新的LRUCache实例
LRUCache<String, String> cache = new LRUCache<String, String>(10);使用put(K k, V v) 方法将对象插入缓存
//插入10个要缓存的对象
for(int i=1; i<=10; i++) {
cache.put(String.format("key-%d", i), String.format("value-%d", i));
}使用方法打印缓存中对象的实用程序方法 printCache()（将按照从最近访问到最近访问的对象的顺序打印）
//打印缓存对象
cache.printCache();使用相应的密钥获取存储在缓存中的对象的方法 get(K k)
//访问第一个对象并打印缓存
cache.get("key-1");
//访问key-1后打印缓存
cache.printCache();改进之处
LRUCache类非常基础，缺少其他功能，例如从缓存中删除对象。如果LRUCache类实现Cache接口，则将是一个好主意，以便使用不同的收回策略可以实现多种缓存实现。可以考虑的其他一些驱逐可能是：
先进先出
随机LRU
已排序（基于某些排序顺序）
兴趣点
阅读Java的ConcurrentHashMap-如果您在多线程环境中运行，它的性能和常规HashMap相比，具有出色的功能。有多种缓存逐出策略，例如最近使用（MRU），最小计数草图，生存时间等，所有这些都有特定的用例。LRU是最常用的驱逐策略，可以解决我们的大多数需求。
在过去的几年中，由于大量数据的应用，缓存框架和分布式缓存的使用有所增长。当内存有限，将存储的对象分布在多个节点上并且必须在此分布上应用逐出，保存大对象和二进制数据等情况时，应用这些逐出策略的挑战变得非常有趣。REDIS和Memcache是2个众所周知的分布式缓存服务器用过的。REDIS提供了比普通缓存更多的功能，它是具有磁盘持久性选项的数据结构缓存。
在当前的实现中，使用简单的简单类来实现基于LRU的缓存并使用键值对存储对象。
在此实现的下一个迭代中，计划是构建一个具有各种功能的简单缓存库，例如添加POJO对象，支持Set接口。除了Factory模式外，还可以创建各种缓存并外部化缓存策略（如LRU，MRU，基于时间的等）。
完整代码
package io.howto;
import java.util.concurrent.ConcurrentHashMap;
/**
* LRUCache: Class to cache objects based on LRU (Least Recently Used) cache eviction strategy,
* wherein if the cache size has reached the maximum allocated capacity, the
* least recently used objects in the cache will be evicted.
* <p>
* See the runner function(a.k.a main(...)) to see the working.
*
* @param <K>
* @param <V> <p>
* Date: 14/Nov/2019
* </p>
* @author 高效码农
*/
public final class LRUCache<K, V> {
/**
* A doubly-linked-list implementation to save objects into the hashmap
* as key-value pari.
*
* @param <K>
* @param <V>
* @author sunil
*/
private static class Node<K, V> {
private V value;
private K key;
private Node<K, V> next, prev;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return value.toString();
}
}
/**
* The maximum number of elements that can be cached, should be set during instantiation
* time.
*/
private final int maxCapacity;
/**
* Use {@linkplain ConcurrentHashMap} here to maintain the cache of objects.
* Also this offers thread safe access of the cache.
*/
private ConcurrentHashMap<K, Node<K, V>> map;
/**
* A key-value representation of the cache object identified by a cache key.
* This is actually a doubly-linked list which maintains the most recently accessed
* objects (read/write) at the tail-end and the least read objects at the head.
*/
private Node<K, V> head, tail;
public LRUCache(int maxCapacity) {
this(16, maxCapacity);
}
public LRUCache(int initialCapacity, int maxCapacity) {
this.maxCapacity = maxCapacity;
if (initialCapacity > maxCapacity)
initialCapacity = maxCapacity;
map = new ConcurrentHashMap<>(initialCapacity);
}
/**
* Removes a node from the head position doubly-linked list.
*
* @param node
*/
private void removeNode(Node<K, V> node) {
if (node == null)
return;
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
}
/**
* Offers a node to the tail-end of the doubly-linked list because
* it was recently read or written.
*
* @param node
*/
private void offerNode(Node<K, V> node) {
if (node == null)
return;
if (head == null) {
head = tail = node;
} else {
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
}
}
/**
* Adds a new object to the cache. If the cache size has reached it's capacity,
* then the least recently accessed object will be evicted.
*
* @param key
* @param value
*/
public void put(K key, V value) {
if (map.contains(key)) {
Node<K, V> node = map.get(key);
node.value = value;
removeNode(node);
offerNode(node);
} else {
if (map.size() == maxCapacity) {
System.out.println("maxCapacity of cache reached");
map.remove(head.key);
removeNode(head);
}
Node<K, V> node = new Node<K, V>(key, value);
offerNode(node);
map.put(key, node);
}
}
/**
* Fetches an object from the cache (could be null if no such mapping exists).
* If the object is found in the cache, then it will be moved to the tail-end of the
* doubly-linked list to indicate that it was recently accessed.
*
* @param key
* @param value
*/
public V get(K key) {
Node<K, V> node = map.get(key);
removeNode(node);
offerNode(node);
return node != null ? node.value : null;
}
/**
* Utility function to print the cache objects.
*/
public void printCache() {
Node<K, V> curr = head;
while (curr != null) {
System.out.print(curr.value + " -> ");
curr = curr.next;
}
System.out.println();
}
/**
* Runner program to test the LRU cache
*
* @param args
*/
public static void main(String[] args) {
/**
* 1. create LRUCache of initial capacity 10
* 2. insert 10 objects to cache
* 3. print the cache objects
* 4. access the first object and print the cache
* 5. insert new objects to cache
* 6. print the cache and observe that the least recently used
* objects are evicted
*/
// 1. initiate the cache with capacity 10
LRUCache<String, String> cache = new LRUCache<String, String>(10);
// 2. insert 10 objects to cache
for (int i = 1; i <= 10; i++) {
cache.put(String.format("key-%d", i), String.format("value-%d", i));
}
// 3. print the cache objects
System.out.println("printing cache:");
cache.printCache();
// 4. access the first object and print the cache
cache.get("key-1");
System.out.println("printing cache after accessing key-1:");
cache.printCache();
// 5. insert new objects to cache
for (int i = 11; i <= 15; i++) {
cache.put(String.format("key-%d", i), String.format("value-%d", i));
}
// 6. print the cache and observe that the least recently used objects are evicted
System.out.println("printing cache after adding new objects:");
cache.printCache();
}
}
评论已关闭