`

How to set up a simple LRU cache using LinkedHash

阅读更多
How to set up a simple LRU cache using LinkedHashMap

Caches

Caches are a simple way to improve the performance of an application that reads data from a "slow" source such as files on disk or rows of data from a database table, but may need to re-read the same data multiple times. The idea is simple: instead of discarding the data after using it, keep it in memory so that it doesn't have to be re-read later.

For example, a simple way to organize this for files might be to create a HashMap that maps the file names to objects containing the file data. When your application needs a particular file it first checks the map to see if it already has the data; if it doesn't, it reads the file and places it in the map in case it needs it again later.

LRU caches

The problem with this simple method is that your application could use a vast amount of memory. Once read in, a file is in the cache for the lifetime of the application whether or not it is ever used again. For an application such as a server that is intended to stay up and running for weeks or months at a time, this is probably not acceptable.

What's needed is a cache that automatically discards entries that haven't been accessed for some time so as to limit the amount of space being used. Such as cache is called an LRU Cache. LRU stands for "Least Recently Used", which refers to the policy of removing the oldest, or least-recently used entries to make space for new data.

LRU caches have a maximum number of data items that they will hold and these items are usually arranged in a list. When an item is added to the cache, and every time it is accessed after that, it is automatically moved to the head of the list. If the cache is full and a slot is required for a new item, the cache makes room by discarding the entry at the tail of the list - the least-recently used item.

The java.util.LinkedHashMap class

LinkedHashMap is a subclass of java.util.HashMap that adds a couple of useful features. One is that by default the iteration order reflects the order that entries are added to the map, rather than the rather haphazard order of a HashMap.

The other feature - the one we're interested in here - is that LinkedHashMap has an option to use access-order instead of insertion order, and includes a way to remove the least-recently accessed entries automatically. This makes it well suited for creating LRU caches.

Creating a cache class

The simplest way to create a cache using LinkedHashMap is to extend it. Here is an example:
public class Cache extends
    LinkedHashMap
{
  private final int capacity;

  public Cache(int capacity)
  {
    super(capacity + 1, 1.1f, true);
    this.capacity = capacity;
  }

  protected boolean removeEldestEntry(Entry eldest)
  {
    return size() > capacity;
  }
}

Note that the constructor takes as an argument the maximum number of entries we want a Cache object to hold. The superclass constructor has three arguments: the initial capacity of the map, the load factor, and a boolean argument that tells the LinkedHashMap constructor to keep entries in access order instead of the default insertion order. (See the java.util.HashMap API documentation for a description of the initial capacity and load factor.) In this case we set the initial capacity to be one more than our required cache size - this is because new entries are added before any are removed, so for example if we want to hold 100 entries the cache will actually contain 101 for an instant when new data is added. Setting the load factor to 1.1 ensures that the rehashing mechanism of the underlying HashMap class isn't triggered - this isn't a vital point but helps a little with efficiency at run-time.

The removeEldestEntry() method overrides a default implementation in LinkedHashMap and is where we determine the policy for removing the oldest entry. In this case, we return true when the cache has more entries than our defined capacity.

Using the cache

Using the cache is simple - just use a suitable key to access the cache; if the data is in the cache we can read it from there. If it's not there we pull it from the slow medium and add it to the cache so that it's in place if needed later:
    Cache cache = new Cache(100);
    // ...

    String filename = "file.txt";
    String filedata = (String) cache
        .get(filename);
    if (filedata == null)
    {
      // Read filedata from file system here...
      cache.put(filename, filedata);
    }

How does it perform?

Our basic implementation should work just fine but we may need to know how effective it is in a given application. One measure of how well a cache is performing is Hit Rate, which tells us how many cache accesses are "hits" - that is, how many times the required data was found in the cache for a given number of accesses. Hit rate is usually expressed as a percentage - a hit rate above 80% is usually pretty good.

We can add a few things to our Cache class to make it possible to monitor performance so that we can tune the cache by setting an optimum size. We need a counter for the number of accesses and another for the number of hits. We will need getter methods to allow us to retrieve those values after the cache has been running for a time, and finally we must override the get() method to update the counts. Here is our Cache class complete with these new members:
public class Cache extends
    LinkedHashMap
{
  private final int capacity;
  private long accessCount = 0;
  private long hitCount = 0;

  public Cache(int capacity)
  {
    super(capacity + 1, 1.1f, true);
    this.capacity = capacity;
  }

  public Object get(Object key)
  {
    accessCount++;
    if (containsKey(key))
    {
      hitCount++;
    }
    Object value = super.get(key);
    return value;
  }

  protected boolean removeEldestEntry(Entry eldest)
  {
    return size() > capacity;
  }

  public long getAccessCount()
  {
    return accessCount;
  }

  public long getHitCount()
  {
    return hitCount;
  }
}

One point to note is that calls to the containsKey() method don't update the access counts; we may want to override that method also, so that the hit rate isn't skewed by code such as this:
    if (cache.containsKey(filename))
    {
      filedata = (String) cache
          .get(filename);
    }
    else
    {
      // Read filedata from file system here...
      cache.put(filename, filedata);
}
分享到:
评论

相关推荐

    最近最少使用cache,提取leveldb的lru cache部分,增加过期时间,过期失效

    LRU (Least Recently Used) 缓存是一种常用的内存管理策略,用于存储系统中,当内存空间有限时,根据数据的访问频率和时间来决定哪些数据应该被替换或淘汰。在数据库系统,如LevelDB中,LRU缓存被用来提高数据读取...

    算法面试通关40讲完整课件 57-58 LRU Cache

    LRU (Least Recently Used) Cache 是一种常用的缓存淘汰策略,广泛应用于计算机系统,包括操作系统、数据库和编程语言的设计中。在面试中,理解和熟练掌握LRU Cache的实现原理及其实现方式是至关重要的。 首先,LRU...

    LRU Cache的简单C++实现

     LRU Cache是一个Cache的置换算法,含义是“近少使用”,把满足“近少使用”的数据从Cache中剔除出去,并且保证Cache中第一个数据是近刚刚访问的,因为这样的数据更有可能被接下来的程序所访问。  LRU的应用比较...

    SimpleLRUCache

    **简单最近最少使用缓存(SimpleLRUCache)** 在计算机科学中,缓存是一种用于存储经常访问数据的机制,以提高系统性能。最近最少使用(LRU, Least Recently Used)是缓存替换策略的一种,当缓存空间满时,会优先...

    erlang lru cache module

    Erlang LRU Cache 模块是一个用于实现Least Recently Used(最近最少使用)缓存策略的工具。LRU缓存是一种常见的数据结构,它在内存有限的情况下,通过淘汰最近最少使用的数据来保持缓存的容量。在Erlang中,这个...

    PyPI 官网下载 | backports.functools_lru_cache-1.3.tar.gz

    《PyPI上的backports.functools_lru_cache-1.3.tar.gz:Python高效缓存技术解析》 在Python编程中,高效的代码执行是至关重要的,特别是在处理大量数据或者需要频繁重复计算的场景下。PyPI(Python Package Index)...

    Android性能优化一 : 1.The Magic of LRU Cache (100 Days of Google Dev)

    谷歌官方视频

    LRU更新Cache

    LRU(Least Recently Used)缓存更新策略是一种广泛应用于计算机系统中的内存管理技术,尤其是在操作系统、数据库系统和编程语言的缓存实现中。LRU的基本思想是:当内存空间有限时,最近最少使用的数据应该优先被...

    Lru Cache java代码

    LruCache的java代码实现,是从android代码中抽取出来的

    LRU-Cache:通过Node.js实现LRU缓存

    const lru = require ( 'LRU-Cache' ) ; 。放 capacity -列表容量,不允许0,默认值:1000 maxAge节点将在maxAge ms内自行销毁 const cache = new lru ( { capacity : 100 } ) ; cache . set ( 'test_key' , 123 ) ...

    backports.functools_lru_cache-1.5.tar

    python源码安装包backports.functools_lru_cache-1.5.tar 解压后python setup.py install 进行安装

    LRU-update-Cache-.zip_LRU cache

    LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间T,当须淘汰一个页面时,选择现有页面中T值最大的,即最近最久没有访问的页面。这是...

    java 缓存 cache lru 实例

    java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例 java 缓存 cache lru 实例

    backports.functools_lru_cache

    在发布的Python 3.3中的functools.lru_cache的反向。 用法 考虑使用此技术导入“ lru_cache”函数: try: from functools import lru_cache except ImportError: from backports.functools_lru_cache import lru_...

    lru-cache-2.5.0.zip

    LRU Cache(Least Recently Used 缓存)是一种常见的数据结构,用于存储有限数量的数据,并在内存容量达到上限时,优先淘汰最近最少使用的数据。在IT领域,LRU Cache被广泛应用于缓存系统,如数据库查询缓存、操作...

    javalruleetcode-LRU_cache:LRU_cache

    LRU_cache (Leetcode 146) 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作:get 和 set。 get(key) – 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 set(key, value) – ...

    Python中双向链表的实现及LRU Cache应用详解(包含详细的完整的程序和数据)

    内容概要:本篇文章详细介绍了双向链表的概念、结构及其实现方法,并附带了一个复杂的例子——最少最近使用缓存(LRU Cache)的具体实现实验案例,有助于理解该数据结构的运作方式及应用潜力。 适合人群:适用于对...

    LRU-cache:用JS实现的LRU缓存

    #LRU缓存通过Node JS中的链接列表和哈希映射实现要运行,请先将存储库克隆到桌面git clone https://github.com/Teaflavored/LRU-cache然后导航到LRU-cache文件夹并运行node testingLRUCache.js

    node-lru:nodejs实现的lru缓存

    Node LRU Cache 基于Nodejs开发的LRU Cache, 兼有缓存超时清除功能 usage var options = { expires: 5 * 60 * 1000, capacity: 5 }; var LRU = require('node-lru'); var cache = new LRU(2);//var cache = new ...

    lru-cache-node:具有最近使用策略的节点的照明快速缓存管理器

    lru-cache-node 具有最近使用策略的节点的照明快速缓存管理器。 具有LRU策略的节点的超快速缓存。 缓存将继续添加值,直到达到maxSize为止。 之后,它将开始从缓存中弹出最近最少使用/访问的值,以便设置新值。 支持...

Global site tag (gtag.js) - Google Analytics