Java资料网推荐从零开始手写redis（18）缓存淘汰算法 FIFO 优化这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

项目简介

大家好，我是老马。

Cache 用于实现一个可拓展的高性能本地缓存。

有人的地方，就有江湖。有高性能的地方，就有 cache。

v1.0.0 版本

以前的 FIFO 实现比较简单，但是 queue 循环一遍删除的话，性能实在是太差。

于是想到引入一个 Set 存储有哪些 key，改成下面的方式：

package com.github.houbb.cache.core.support.evict.impl;

import com.github.houbb.cache.api.ICacheContext;
import com.github.houbb.cache.core.model.CacheEntry;
import com.github.houbb.cache.core.support.evict.AbstractCacheEvict;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 丢弃策略-先进先出
 * @author binbin.hou
 * @since 0.0.2
 */
public class CacheEvictFifo<K,V> extends AbstractCacheEvict<K,V> {

    /**
     * queue 信息
     * @since 0.0.2
     */
    private final Queue<K> queue = new LinkedList<>();

    /**
     * 避免数据重复加入问题
     * @since 1.0.1
     */
    private final Set<K> keySet = new HashSet<>();

    @Override
    public CacheEntry<K,V> doEvict(ICacheContext<K, V> context, final K newKey) {
        CacheEntry<K,V> result = null;

        // 超过限制，执行移除
        if(isNeedEvict(context)) {
            K evictKey = queue.remove();
            keySet.remove(evictKey);
            // 移除最开始的元素
            V evictValue = doEvictRemove(context, evictKey);
            result = new CacheEntry<>(evictKey, evictValue);
        }

        return result;
    }

    @Override
    public void updateKey(ICacheContext<K, V> context, K key) {
        if (!keySet.contains(key)) {
            queue.add(key);
            keySet.add(key);
        }
    }

}

这里虽然可以解决 fifo 的删除问题，但是内存有点浪费。

而且这样其实顺序也太对，每次还是需要更新 queue 的位置。

我们把结构继续调整一下，用其他的数据结构来替代。

v1.0.1 实现

其他的方式

方案	数据结构	内存开销	实现难度	是否推荐
Queue + Set	两个结构	较大	简单	❌
LinkedHashSet	单结构	小	简单	✅ 推荐
LinkedHashMap	Map+链表	中等	中等	✅ 可选

实现

简单起见，我们使用 LinkedHashSet 来实现。

package com.github.houbb.cache.core.support.evict.impl;

import com.github.houbb.cache.api.ICacheContext;
import com.github.houbb.cache.core.model.CacheEntry;
import com.github.houbb.cache.core.support.evict.AbstractCacheEvict;

import java.util.*;

/**
 * 丢弃策略-先进先出
 * @author binbin.hou
 * @since 0.0.2
 */
public class CacheEvictFifo<K,V> extends AbstractCacheEvict<K,V> {

    /**
     * queue 信息
     * @since 0.0.2
     */
    private final Set<K> accessOrder = new LinkedHashSet<>();;

    @Override
    public CacheEntry<K,V> doEvict(ICacheContext<K, V> context, final K newKey) {
        CacheEntry<K,V> result = null;

        // 超过限制，执行移除
        if(isNeedEvict(context)) {
            Iterator<K> iterator = accessOrder.iterator();
            K evictKey = iterator.next();
            V evictValue = doEvictRemove(context, evictKey);
            iterator.remove();

            // 移除最开始的元素
            result = new CacheEntry<>(evictKey, evictValue);
        }

        return result;
    }

    @Override
    public void updateKey(ICacheContext<K, V> context, K key) {
        accessOrder.remove(key);
        accessOrder.add(key);
    }

}

这样我们的目标算是达成了，实现了内存和性能的平衡。

拓展信息

开源矩阵

下面是一些缓存系列的开源矩阵规划。

名称	介绍	状态
resubmit	防止重复提交核心库	已开源
rate-limit	限流核心库	已开源
cache	手写渐进式 redis	已开源
lock	开箱即用的分布式锁	已开源
common-cache	通用缓存标准定义	已开源
redis-config	兼容各种常见的 redis 配置模式	已开源
quota-server	限额限次核心服务	待开始
quota-admin	限额限次控台	待开始
flow-control-server	流控核心服务	待开始
flow-control-admin	流控控台	待开始

手写 Redis 系列

java从零手写实现redis（一）如何实现固定大小的缓存？

java从零手写实现redis（三）redis expire 过期原理

java从零手写实现redis（三）内存数据如何重启不丢失？

java从零手写实现redis（四）添加监听器

java从零手写实现redis（五）过期策略的另一种实现思路

java从零手写实现redis（六）AOF 持久化原理详解及实现

java从零手写实现redis（七）LRU 缓存淘汰策略详解

java从零开始手写redis（八）朴素 LRU 淘汰算法性能优化

java从零开始手写redis（九）LRU 缓存淘汰算法如何避免缓存污染

java从零开始手写redis（十）缓存淘汰算法 LFU 最少使用频次

java从零开始手写redis（十一）缓存淘汰算法 COLOK 算法

java从零开始手写redis（十二）过期策略如何实现随机 keys 淘汰

java从零开始手写redis（十三）redis渐进式rehash详解

java从零开始手写redis（十四）JDK HashMap 源码解析

java从零开始手写redis（十四）JDK ConcurrentHashMap 源码解析

java从零开始手写redis（十五）实现自己的 HashMap

java从零开始手写redis（十六）实现渐进式 rehash map

java从零开始手写redis（十七）v1.0.0 代码重构+拓展性增强

java从零开始手写redis（十八）缓存淘汰算法 FIFO 优化

文章来源:https://www.cnblogs.com/houbbBlogs/p/18944602
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！