关于Cache(缓存)的那些事

最近看一些文章这个也说,哪个也说,所以对其中感兴趣;

缓存是一种存储在内存中,可以快速定位查找数据的数据结构,并且一个缓存算法是包含了冷数据淘汰的机制的。

其特点则是,快速、高效。

呵呵,我相信大家经常在工作的过程中,使用memcached,redis等等,这些今天暂且搁下,后面有时间再提;

相信大家提及到缓存,不仅知道Memcached等还会了解到一些算法,如LRU,等,今天就一一讨论;

LRU

先来个算法,大家看看,最简单写法:

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Copyright (c) 三月,03,2017 彭秦进 (ashang.peng@aliyun.com)
 * <p>
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * <p>
 * http://www.apache.org/licenses/LICENSE-2.0
 * <p>
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

public class MyLRU extends LinkedHashMap {
    public MyLRU(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        if (this.size() > 100) {
            return true;
        } else {
            return false;
        }
    }

}

当然还有其他的写法,自行Google.

我也主要介绍下原理:

LRU-Least Recently Used 的缩写,即近期最少使用算法,一般会使用 双向链表 按照访问顺序对缓存数据进行排序,当满足一定条件后可以将链表中最少使用的数据从缓存中剔除出去。
在Java中,从1.4开始提供了java.util.LinkedHashMap类来帮助我们简单的实现LRU缓存算法。

  • 继承java.util.LinkedHashMap
  • 通过构造函数定义java.util.LinkedHashMap#accessOrder为true,即链表排列顺序为访问顺序(默认为false,即插入顺序)
  • 覆盖java.util.LinkedHashMap的removeEldestEntry方法
    • JDK会在向该Map中put数据时会调用该方法
    • 如果返回true,则会将存在时间最长的数据剔除

上面是个简单算法;

但是

  • 从Java1.8java.util.LinkedHashMap#afterNodeAccess源码可以看出,当读取一个缓存数据之后,访问顺序链表将会发生重排。
  • 由于缓存的特性,所以他必须是全局变量,当并发量比较大的情况下,缓存作为临界资源在发生重排时势必加锁,使对链表的变更操作由异步转换为同步操作。

FIFO算法

除掉上面说的LRU外,还有先进先出等;这个就比较简单;

  利用一个双向链表保存数据,当来了新的数据之后便添加到链表末尾,如果Cache存满数据,则把链表头部数据删除,然后把新的数据添加到链表末尾。在访问数据的时候,如果在Cache中存在该数据的话,则返回对应的value值;否则返回-1。如果想提高访问效率,可以利用hashmap来保存每个key在链表中对应的位置。

FIFO虽然实现很简单,但是命中率很低,实际上也很少使用这种算法。

实现方法可以和LRU想类似,只不过进行排序的时间指的不是最后使用时间,而是创建时间,这里就不花篇幅赘述.

 

除特别注明外,本站所有文章均为duzhi原创,转载请注明出处来自https://www.duzhi.me/article/1865.html

联系我们

******

在线咨询:点击这里给我发消息

邮件:ashang.peng#aliyun.com

QR code