从零开始手写redis（18）缓存淘汰算法 FIFO 优化
<h1 id="项目简介">项目简介</h1><p>大家好，我是老马。</p>
<p>Cache 用于实现一个可拓展的高性能本地缓存。</p>
<p>有人的地方，就有江湖。有高性能的地方，就有 cache。</p>
<h1 id="v100-版本">v1.0.0 版本</h1>
<p>以前的 FIFO 实现比较简单，但是 queue 循环一遍删除的话，性能实在是太差。</p>
<p>于是想到引入一个 Set 存储有哪些 key，改成下面的方式：</p>
<pre><code class="language-java">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);
}
}
}
</code></pre>
<p>这里虽然可以解决 fifo 的删除问题，但是内存有点浪费。</p>
<p>而且这样其实顺序也太对，每次还是需要更新 queue 的位置。</p>
<p>我们把结构继续调整一下，用其他的数据结构来替代。</p>
<h1 id="v101-实现">v1.0.1 实现</h1>
<h2 id="其他的方式">其他的方式</h2>
<table>
<thead>
<tr>
<th>方案</th>
<th>数据结构</th>
<th>内存开销</th>
<th>实现难度</th>
<th>是否推荐</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>Queue + Set</code></td>
<td>两个结构</td>
<td>较大</td>
<td>简单</td>
<td>❌</td>
</tr>
<tr>
<td><code>LinkedHashSet</code></td>
<td>单结构</td>
<td>小</td>
<td>简单</td>
<td>✅ 推荐</td>
</tr>
<tr>
<td><code>LinkedHashMap</code></td>
<td>Map+链表</td>
<td>中等</td>
<td>中等</td>
<td>✅ 可选</td>
</tr>
</tbody>
</table>
<h2 id="实现">实现</h2>
<p>简单起见，我们使用 LinkedHashSet 来实现。</p>
<pre><code class="language-java">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);
}
}
</code></pre>
<p>这样我们的目标算是达成了，实现了内存和性能的平衡。</p>
<h1 id="拓展信息">拓展信息</h1>
<h2 id="开源矩阵">开源矩阵</h2>
<p>下面是一些缓存系列的开源矩阵规划。</p>
<table>
<thead>
<tr>
<th style="text-align: left">名称</th>
<th style="text-align: left">介绍</th>
<th style="text-align: left">状态</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: left">resubmit</td>
<td style="text-align: left">防止重复提交核心库</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">rate-limit</td>
<td style="text-align: left">限流核心库</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">cache</td>
<td style="text-align: left">手写渐进式 redis</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">lock</td>
<td style="text-align: left">开箱即用的分布式锁</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">common-cache</td>
<td style="text-align: left">通用缓存标准定义</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">redis-config</td>
<td style="text-align: left">兼容各种常见的 redis 配置模式</td>
<td style="text-align: left">已开源</td>
</tr>
<tr>
<td style="text-align: left">quota-server</td>
<td style="text-align: left">限额限次核心服务</td>
<td style="text-align: left">待开始</td>
</tr>
<tr>
<td style="text-align: left">quota-admin</td>
<td style="text-align: left">限额限次控台</td>
<td style="text-align: left">待开始</td>
</tr>
<tr>
<td style="text-align: left">flow-control-server</td>
<td style="text-align: left">流控核心服务</td>
<td style="text-align: left">待开始</td>
</tr>
<tr>
<td style="text-align: left">flow-control-admin</td>
<td style="text-align: left">流控控台</td>
<td style="text-align: left">待开始</td>
</tr>
</tbody>
</table>
<h1 id="手写-redis-系列">手写 Redis 系列</h1>
<p>java从零手写实现redis（一）如何实现固定大小的缓存？</p>
<p>java从零手写实现redis（三）redis expire 过期原理</p>
<p>java从零手写实现redis（三）内存数据如何重启不丢失？</p>
<p>java从零手写实现redis（四）添加监听器</p>
<p>java从零手写实现redis（五）过期策略的另一种实现思路</p>
<p>java从零手写实现redis（六）AOF 持久化原理详解及实现</p>
<p>java从零手写实现redis（七）LRU 缓存淘汰策略详解</p>
<p>java从零开始手写redis（八）朴素 LRU 淘汰算法性能优化</p>
<p>java从零开始手写redis（九）LRU 缓存淘汰算法如何避免缓存污染</p>
<p>java从零开始手写redis（十）缓存淘汰算法 LFU 最少使用频次</p>
<p>java从零开始手写redis（十一）缓存淘汰算法 COLOK 算法</p>
<p>java从零开始手写redis（十二）过期策略如何实现随机 keys 淘汰</p>
<p>java从零开始手写redis（十三）redis渐进式rehash详解</p>
<p>java从零开始手写redis（十四）JDK HashMap 源码解析</p>
<p>java从零开始手写redis（十四）JDK ConcurrentHashMap 源码解析</p>
<p>java从零开始手写redis（十五）实现自己的 HashMap</p>
<p>java从零开始手写redis（十六）实现渐进式 rehash map</p>
<p>java从零开始手写redis（十七）v1.0.0 代码重构+拓展性增强</p>
<p>java从零开始手写redis（十八）缓存淘汰算法 FIFO 优化</p><br><br>
来源：https://www.cnblogs.com/houbbBlogs/p/18944602
頁:
[1]