您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

3种堆内缓存算法

时间:2020-05-12 13:57:06  来源:  作者:

要说计算机系统里,什么技术把 tradeoff 体现的淋漓尽致,那肯定是缓存无疑。为了协调高速部件和低速部件的速度差异,加入一个中间缓存层,是解决这种冲突最有效的方案。

其中,JVM堆内缓存是缓存体系中重要的一环,最常用的有 FIFO / LRU / LFU 三种算法。

  1. FIFO 是简单的队列,先进先出。
  2. LRU 是最近最少使用,优先移除最久未使用的数据。是 时间维度 。
  3. LFU 是最近最不常用,优先移除访问次数最少的数据。是 统计维度 。

由于过期也是缓存的一个重要特点。所有在设计这三种缓存算法时,需要额外的存储空间去存储这个过期时间。

以下将讨论这三种缓存算法的操作和设计要点,但 暂未考虑高并发环境 。

FIFO

先进先出,如果缓存容量满,则优先移出最早加入缓存的数据;其内部可以使用队列实现。

3种堆内缓存算法

 

操作

  • Object get(key):获取保存的数据,如果数据不存在或者已经过期,则返回null。
  • void put(key,value,expireTime):加入缓存。 无论此key是否已存在,均作为新key处理(移除旧key);如果空间不足,则移除已过期的key,如果没有,则移除最早加入缓存的key。过期时间未指定,则表示永不自动过期。
  • 注意,我们允许key是有过期时间的,这一点与普通的FIFO有所区别,所以在设计此题时需要注意。(也是面试考察点,偏设计而非算法)

普通的FIFO或许大家都能很简单的写出,增加了过期时间的考虑之后,在设计时需要多考虑。如下示例,为暂未考虑并发环境的FIFO设计。

设计思路

1)用普通的hashMap保存缓存数据。

2)需要额外的map用来保存key的过期特性,例子中使用了TreeMap,将“剩余存活时间”作为key,利用TreeMap的排序特性。

public class FIFOCache {
  
    //按照访问时间排序,保存所有key-value
    private final Map<String,Value> CACHE = new LinkedHashMap<>();
  
    //过期数据,只保存有过期时间的key
    //暂不考虑并发,我们认为同一个时间内没有重复的key,如果改造的话,可以将value换成set
    private final TreeMap<Long, String> EXPIRED = new TreeMap<>();
  
    private final int capacity;
  
    public FIFOCache(int capacity) {
        this.capacity = capacity;
    }
  
    public Object get(String key) {
        //
        Value value = CACHE.get(key);
        if (value == null) {
            return null;
        }
  
        //如果不包含过期时间
        long expired = value.expired;
        long now = System.nanoTime();
        //已过期
        if (expired > 0 && expired <= now) {
            CACHE.remove(key);
            EXPIRED.remove(expired);
            return null;
        }
        return value.value;
    }
  
    public void put(String key,Object value) {
        put(key,value,-1);
    }
  
  
    public void put(String key,Object value,int seconds) {
        //如果容量不足,移除过期数据
        if (capacity < CACHE.size()) {
            long now = System.nanoTime();
            //有过期的,全部移除
            Iterator<Long> iterator = EXPIRED.keySet().iterator();
            while (iterator.hasNext()) {
                long _key = iterator.next();
                //如果已过期,或者容量仍然溢出,则删除
                if (_key > now) {
                    break;
                }
                //一次移除所有过期key
                String _value = EXPIRED.get(_key);
                CACHE.remove(_value);
                iterator.remove();
            }
        }
  
        //如果仍然容量不足,则移除最早访问的数据
        if (capacity < CACHE.size()) {
            Iterator<String> iterator = CACHE.keySet().iterator();
            while (iterator.hasNext() && capacity < CACHE.size()) {
                String _key = iterator.next();
                Value _value = CACHE.get(_key);
                long expired = _value.expired;
                if (expired > 0) {
                    EXPIRED.remove(expired);
                }
                iterator.remove();
            }
        }
  
        //如果此key已存在,移除旧数据
        Value current = CACHE.remove(key);
        if (current != null && current.expired > 0) {
            EXPIRED.remove(current.expired);
        }
        //如果指定了过期时间
        if(seconds > 0) {
            long expireTime = expiredTime(seconds);
            EXPIRED.put(expireTime,key);
            CACHE.put(key,new Value(expireTime,value));
        } else {
            CACHE.put(key,new Value(-1,value));
        }
  
    }
  
    private long expiredTime(int expired) {
        return System.nanoTime() + TimeUnit.SECONDS.toNanos(expired);
    }
  
    public void remove(String key) {
        Value value = CACHE.remove(key);
        if(value == null) {
            return;
        }
        long expired = value.expired;
        if (expired > 0) {
            EXPIRED.remove(expired);
        }
    }
  
  
    class Value {
        long expired; //过期时间,纳秒
        Object value;
        Value(long expired,Object value) {
            this.expired = expired;
            this.value = value;
        }
    }
}

LRU

least recently used,最近最少使用,是目前最常用的缓存算法和设计方案之一,其移除策略为“当缓存(页)满时,优先移除最近最久未使用的数据”,优点是易于设计和使用,适用场景广泛。算法可以参考leetcode 146 (LRU Cache)。

操作

  • Object get(key):从cache中获取key对应的数据,如果此key已过期,移除此key,并则返回null。
  • void put(key,value,expired):设置k-v,如果容量不足,则根据LRU置换算法移除“最久未被使用的key”。 需要注意,根据LRU优先移除已过期的keys,如果没有,则根据LRU移除未过期的key。如果未设定过期时间,则认为永不自动过期。
  • 这里的设计关键是过期时间特性,这与常规的LRU有所不同。

设计思路

  • LRU的基础算法,需要了解;每次put、get时需要更新key对应的访问时间,我们需要一个数据结构能够保存key最近的访问时间且能够排序。
  • 既然包含过期时间特性,那么带有过期时间的key需要额外的数据结构保存。
  • 暂时不考虑并发操作;尽量兼顾空间复杂度和时间复杂度。
  • 此题仍然偏向于设计题,而非纯粹的算法题。

此题代码与FIFO基本相同,唯一不同点为get()方法,对于LRU而言,get方法需要重设访问时间(即调整所在cache中顺序)

public Object get(String key) {
    //
    Value value = CACHE.get(key);
    if (value == null) {
        return null;
    }
  
    //如果不包含过期时间
    long expired = value.expired;
    long now = System.nanoTime();
    //已过期
    if (expired > 0 && expired <= now) {
        CACHE.remove(key);
        EXPIRED.remove(expired);
        return null;
    }
    //相对于FIFO,增加顺序重置
    CACHE.remove(key);
    CACHE.put(key,value);
    return value.value;
}

LFU

最近最不常用,当缓存容量满时,移除 访问次数 最少的元素,如果访问次数相同的元素有多个,则移除最久访问的那个。设计要求参见leetcode 460( LFU Cache)

public class LFUCache {
  
    //主要容器,用于保存k-v
    private Map<String, Object> keyToValue = new HashMap<>();
  
    //记录每个k被访问的次数
    private Map<String, Integer> keyToCount = new HashMap<>();
  
    //访问相同次数的key列表,按照访问次数排序,value为相同访问次数到key列表。
    private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>();
  
    private int capacity;
  
    public LFUCache(int capacity) {
        this.capacity = capacity;
        //初始化,默认访问1次,主要是解决下文
    }
  
    public Object get(String key) {
        if (!keyToValue.containsKey(key)) {
            return null;
        }
  
        touch(key);
        return keyToValue.get(key);
    }
  
    /**
     * 如果一个key被访问,应该将其访问次数调整。
     * @param key
     */  
    private void touch(String key) {
        int count = keyToCount.get(key);
        keyToCount.put(key, count + 1);//访问次数增加
        //从原有访问次数统计列表中移除
        countToLRUKeys.get(count).remove(key);
  
        //如果符合最少调用次数到key统计列表为空,则移除此调用次数到统计
        if (countToLRUKeys.get(count).size() == 0) {
            countToLRUKeys.remove(count);
        }
  
        //然后将此key的统计信息加入到管理列表中
        LinkedHashSet<String> countKeys = countToLRUKeys.get(count + 1);
        if (countKeys == null) {
            countKeys = new LinkedHashSet<>();
            countToLRUKeys.put(count + 1,countKeys);
        }
        countKeys.add(key);
    }
  
    public void put(String key, Object value) {
        if (capacity <= 0) {
            return;
        }
  
        if (keyToValue.containsKey(key)) {
            keyToValue.put(key, value);
            touch(key);
            return;
        }
        //容量超额之后,移除访问次数最少的元素
        if (keyToValue.size() >= capacity) {
            Map.Entry<Integer,LinkedHashSet<String>> entry = countToLRUKeys.firstEntry();
            Iterator<String> it = entry.getValue().iterator();
            String evictKey = it.next();
            it.remove();
            if (!it.hasNext()) {
                countToLRUKeys.remove(entry.getKey());
            }
            keyToCount.remove(evictKey);
            keyToValue.remove(evictKey);
  
        }
  
        keyToValue.put(key, value);
        keyToCount.put(key, 1);
        LinkedHashSet<String> keys = countToLRUKeys.get(1);
        if (keys == null) {
            keys = new LinkedHashSet<>();
            countToLRUKeys.put(1,keys);
        }
        keys.add(key);
    }
}

End

本文力求比较三个基本的缓存算法,以便对缓存建设之路有一个比较笼统的感觉。

更加易用的cache,可以参考guava的实现。谨希望这三个代码模版,能够对你有所帮助。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条