基于Java的轻量级缓存组件，实现LRU、LFU、FIFO等缓存清除算法_java实现lru缓存工具类

该组件使用简单、可靠

类图如下：

例如：

        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache(
                "testCache", 2, DawnSimpleCache.LRU, 1F);
        // 设置缓存数据
        dawnSimpleCache.setCache("test1", "xxx", 200, TimeUnit.SECONDS);
        // 从缓存获取数据
        dawnSimpleCache.getFromCache("test1");
1
2
3
4
5
6

    /**
     * 构造
     *
     * @param name            缓存名称
     * @param maxSize         最大的缓存数量
     * @param strategy        缓存策略，LRU_LFU 1, LFU 2, FIFO 3
     * @param clearProportion 清除的比重，0-1之间
     */
    public DawnSimpleCache(String name, int maxSize, int strategy, double clearProportion) 
1
2
3
4
5
6
7
8
9

该组件实现了以下算法

• LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。

• LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，
  那么在将来一段时间内被使用的可能性也很小。

• FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。

• LRU_LFU 综合 LRU 和 LFU 的优点，但是计算较复杂

核心代码如下：

DawnCache

/**
 * DAWN 缓存通用接口
 *
 * @author hengyumo
 * @since 2021-06-06
 */
public interface DawnCache {

    /**
     * 从缓存中取值
     *
     * @param key 键
     * @return Pair<Boolean, Optional < ?>>, Boolean是标识位，标识是否缓存中存在这个Key
     * 该设计是为了避免空值时出现缓存穿透的可能
     */
    Pair<Boolean, Optional<?>> getFromCache(String key);

    /**
     * 删除某个前缀开头的键对应的那些缓存
     *
     * @param keyPrefix 键的前缀
     * @return 删除的数量
     */
    int deleteCache(String keyPrefix);

    /**
     * 设置缓存
     *
     * @param key        键
     * @param value      值
     * @param timeToLive 有效时间，0时为永久
     * @param timeUnit   有效时间的单位
     */
    void setCache(String key, Object value, long timeToLive, TimeUnit timeUnit);

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

DawnSimpleCache

package cn.hengyumo.dawn.core.cache.types;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;
import org.springframework.data.util.Pair;
import org.springframework.util.Assert;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;

/**
 * 使用 Java 内置的 MAP 实现的缓存组件，适用于一些轻量级缓存
 *
 * @author hengyumo
 * @since 2021-06-06
 */
@Slf4j
public class DawnSimpleCache implements DawnCache {

    @AllArgsConstructor
    @Getter
    @Setter
    private static class CacheHitInfo {
        // 缓存启用时间
        private long startTime;
        // 最后一次使用时间
        private long lastTime;
        // 命中次数
        private long hitCount;
        // 计分
        private double score;
        // 存活次数
        private int liveCount;
    }
    
    private static class MyPair<E1, E2> {
        private final Object[] objects = new Object[2];
        
        private MyPair(){}
        
        public static <E1,E2> MyPair<E1,E2> of(E1 e1, E2 e2) {
            MyPair<E1, E2> pair = new MyPair<>();
            pair.objects[0] = e1;
            pair.objects[1] = e2;
            return pair;
        }
        public void setFirst(E1 e1) { 
            objects[0] = e1;
        }
        public void setSecond(E2 e2) { 
            objects[1] = e2;
        }
        public E1 getFirst() {
            //noinspection unchecked
            return (E1) objects[0];
        }
        public E2 getSecond() {
            //noinspection unchecked
            return (E2) objects[1];
        }
    }

    /**
     * 最大数量的默认值，200
     */
    public final static int MAX_SIZE = 200;

    /*
    LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。
    LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，
                                那么在将来一段时间内被使用的可能性也很小。
    FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。
    
    LRU_LFU 综合 LRU 和 LFU 的优点，但是计算较复杂
     */
    public final static int LRU = 1;

    public final static int LFU = 2;

    public final static int FIFO = 3;

    public final static int LRU_LFU = 4;

    /**
     * 默认清除之后剩下的比重 0.8
     */
    public final static float DEFAULT_CLEAR_PROPORTION = 0.8F;

    /**
     * 默认的缓存置换策略，LFU，使用次数最少的缓存将会被优先置换
     */
    public final static int DEFAULT_STRATEGY = LRU_LFU;

    /**
     * 保存缓存数据
     */
    private final Map<String, Object> cache;

    /**
     * 保存缓存对应的过期时间
     */
    private final Map<String, Long> cacheExpireRecord;

    /**
     * 记录缓存的最后一次命中时间，LRU支持（最近最少使用的会被优先淘汰）
     */
    private List<MyPair<String, Long>> cacheHitListForLru;

    /**
     * 记录缓存的命中次数，LFU 支持（最近最不经常使用的会优先被淘汰）
     */
    private List<MyPair<String, Long>> cacheHitListForLfu;

    /**
     * 一个先进先出队列，FIFO 支持（最先缓存的数据会优先被淘汰）
     */
    private List<String> cacheHitListForFifo;

    /**
     * LRU_LFU支持
     */
    private List<MyPair<String, CacheHitInfo>> cacheHitListForLruLfu;

    /**
     * 缓存名称
     */
    private final String name;

    /**
     * 对象的最大数量
     */
    private final int maxSize;

    /**
     * 使用的缓存置换策略
     */
    private final int strategy;

    /**
     * 缓存清除所有过期数据之后，仍超出最大大小时，执行策略进行清除的清除比重
     */
    private final double clearProportion;

    /**
     * 默认构造函数，MAX_SIZE 1000、DEFAULT_STRATEGY LRU
     */
    public DawnSimpleCache() {
        this.cache = new ConcurrentHashMap<>();
        this.cacheExpireRecord = new ConcurrentHashMap<>();
        this.maxSize = MAX_SIZE;
        this.strategy = DEFAULT_STRATEGY;
        this.clearProportion = DEFAULT_CLEAR_PROPORTION;
        this.name = this.getClass().getSimpleName() + System.currentTimeMillis();
        applyStrategy();
    }

    /**
     * 构造
     *
     * @param name            缓存名称
     * @param maxSize         最大的缓存数量
     * @param strategy        缓存策略，LRU_LFU 1, LFU 2, FIFO 3
     * @param clearProportion 清除的比重，0-1之间
     */
    public DawnSimpleCache(String name, int maxSize, int strategy, double clearProportion) {
        this.cache = new ConcurrentHashMap<>();
        this.cacheExpireRecord = new ConcurrentHashMap<>();
        this.name = name;
        this.maxSize = maxSize;
        this.strategy = strategy;
        Assert.isTrue(clearProportion > 0 && clearProportion <= 1, "清除的比重在0<x<=1之间");
        this.clearProportion = clearProportion;
        applyStrategy();
    }

    // 应用设置的缓存清除策略
    private void applyStrategy() {
        switch (this.strategy) {
            case LRU -> cacheHitListForLru = new LinkedList<>();
            case LFU -> cacheHitListForLfu = new LinkedList<>();
            case FIFO -> cacheHitListForFifo = new LinkedList<>();
            case LRU_LFU -> cacheHitListForLruLfu = new LinkedList<>();
        }
    }

    private void collectHitInfoForLru(String key) {
        MyPair<String, Long> aPair = null;
        Iterator<MyPair<String, Long>> iterator = cacheHitListForLru.iterator();
        for (int i = 0; i < cacheHitListForLru.size(); i++) {
            MyPair<String, Long> pair = iterator.next();
            if (pair.getFirst().equals(key)) {
                aPair = pair;
                // 更新最近使用时间
                pair.setSecond(System.currentTimeMillis());
                break;
            }
        }
        if (aPair == null) {
            MyPair<String, Long> newPair = MyPair.of(key, System.currentTimeMillis());
            cacheHitListForLru.add(newPair);
        }
    }

    private void collectHitInfoForLfu(String key) {
        MyPair<String, Long> aPair = null;
        Iterator<MyPair<String, Long>> iterator = cacheHitListForLfu.iterator();
        for (int i = 0; i < cacheHitListForLfu.size(); i++) {
            MyPair<String, Long> pair = iterator.next();
            if (pair.getFirst().equals(key)) {
                aPair = pair;
                // 缓存命中次数 + 1
                pair.setSecond(pair.getSecond() + 1);
                break;
            }
        }
        if (aPair == null) {
            MyPair<String, Long> newPair = MyPair.of(key, 1L);
            cacheHitListForLfu.add(newPair);
        }
    }

    private void collectHitInfoForFifo(String key) {
        // 如果没找到则加到最后
        boolean found = cacheHitListForFifo.stream()
                .anyMatch(x -> x.equals(key));
        if (!found) {
            cacheHitListForFifo.add(key);
        }
    }

    private void collectHitInfoForLruLfu(String key) {
        MyPair<String, CacheHitInfo> aPair = null;
        Iterator<MyPair<String, CacheHitInfo>> iterator = cacheHitListForLruLfu.iterator();
        for (int i = 0; i < cacheHitListForLruLfu.size(); i++) {
            MyPair<String, CacheHitInfo> pair = iterator.next();
            if (pair.getFirst().equals(key)) {
                aPair = pair;
                // 更新信息
                CacheHitInfo cacheHitInfo = pair.getSecond();
                cacheHitInfo.setHitCount(cacheHitInfo.getHitCount() + 1);
                cacheHitInfo.setLastTime(System.currentTimeMillis());
                break;
            }
        }
        if (aPair == null) {
            CacheHitInfo cacheHitInfo = new CacheHitInfo(
                    System.currentTimeMillis(),
                    System.currentTimeMillis(),
                    1L, 0F, 0);
            MyPair<String, CacheHitInfo> newPair = MyPair.of(key, cacheHitInfo);
            cacheHitListForLruLfu.add(newPair);
        }
    }

    // 执行缓存的命中信息收集
    private synchronized void collectHitInfoForStrategy(String key) {
        switch (this.strategy) {
            case LRU -> collectHitInfoForLru(key);
            case LFU -> collectHitInfoForLfu(key);
            case FIFO -> collectHitInfoForFifo(key);
            case LRU_LFU -> collectHitInfoForLruLfu(key);
        }
    }

    // 清除缓存，从左到右
    private synchronized <T> void clearCache(Iterator<T> iterator, Function<T, String> function, int clearSize) {
        for (int i = 0; i < clearSize; i++) {
            String key = function.apply(iterator.next());
            this.removeCache(key);
        }
    }

    private void clearWithLru(int clearSize) {
        int cacheSize = cache.size();
        // 针对最近使用时间从低到高进行排序
        cacheHitListForLru.sort(Comparator.comparingLong(MyPair::getSecond));
        // 清除对应的缓存
        clearCache(cacheHitListForLru.iterator(), MyPair::getFirst, clearSize);
        // 最后边的数据最近使用，所以，去头即可
        cacheHitListForLru = cacheHitListForLru.subList(clearSize, cacheSize);
    }

    private void clearWithLfu(int clearSize) {
        int cacheSize = cache.size();
        // 针对使用次数从低到高进行排序
        cacheHitListForLfu.sort(Comparator.comparingLong(MyPair::getSecond));
        // 清除对应的缓存
        clearCache(cacheHitListForLfu.iterator(), MyPair::getFirst, clearSize);
        // 最后边的数据使用最频繁，所以，去头即可
        cacheHitListForLfu = cacheHitListForLfu.subList(clearSize, cacheSize);
    }

    private void clearWithFifo(int clearSize) {
        int cacheSize = cache.size();
        // 清除对应的缓存
        clearCache(cacheHitListForFifo.iterator(), x -> x, clearSize);
        // 最左边的数据最先进入，所以去头
        cacheHitListForFifo = cacheHitListForFifo.subList(clearSize, cacheSize);
    }

    private void clearWithLruLfu(int clearSize) {
        int cacheSize = cache.size();
        // 计算得分、排序
        cacheHitListForLruLfu.forEach(x -> {
            CacheHitInfo cacheHitInfo = x.getSecond();
            // 得分，命中次数 / 最后一次命中至今的毫秒数
            // LRU_LFU耗时：60622 write：299 read：5000 del：100 score：16.49566164098842
            // 得分，命中次数 ^ 2 / 最后一次命中至今的毫秒数
            // LRU_LFU耗时：54182 write：267 read：5000 del：100 score：18.456313904986896
            // LRU_LFU耗时：57845 write：285 read：5000 del：100 score：17.287578874578614
            // 得分，命中次数 ^ 3 / 最后一次命中至今的毫秒数
            // LRU_LFU耗时：57157 write：282 read：5000 del：100 score：17.495669821719126
            // 得分，命中次数 ^ 4 / 最后一次命中至今的毫秒数
            // LRU_LFU耗时：59370 write：293 read：5000 del：100 score：16.843523665150748

            // 得分，命中次数 ^ 0.5 / 最后一次命中至今的毫秒数
            // LRU_LFU耗时：55969 write：276 read：5000 del：100 score：17.867033536421946
            // LRU_LFU耗时：58623 write：289 read：5000 del：100 score：17.05815123756887
            double a = Math.pow((double) cacheHitInfo.getHitCount(), 2);
            cacheHitInfo.setScore((a / (double) ((System.currentTimeMillis() - cacheHitInfo.getLastTime()))));
            cacheHitInfo.setLiveCount(cacheHitInfo.getLiveCount() + 1);
        });
        // 针对得分从低到高进行排序
        cacheHitListForLruLfu.sort(Comparator.comparingDouble(x -> x.getSecond().getScore()));
        // 清除对应的缓存
        clearCache(cacheHitListForLruLfu.iterator(), MyPair::getFirst, clearSize);
        // 最后边的数据使用最频繁，所以，去头即可
        cacheHitListForLruLfu = cacheHitListForLruLfu.subList(clearSize, cacheSize);
    }

    // 执行缓存清除策略
    private synchronized void clearWithStrategy(int clearSize) {
        switch (this.strategy) {
            case LRU -> clearWithLru(clearSize);
            case LFU -> clearWithLfu(clearSize);
            case FIFO -> clearWithFifo(clearSize);
            case LRU_LFU -> clearWithLruLfu(clearSize);
        }
    }

    // 清除缓存命中记录，连同缓存数据
    private synchronized void removeCacheAndCacheHit(String key) {
        switch (this.strategy) {
            case LRU -> cacheHitListForLru.removeIf(x -> x.getFirst().equals(key));
            case LFU -> cacheHitListForLfu.removeIf(x -> x.getFirst().equals(key));
            case FIFO -> cacheHitListForFifo.removeIf(x -> x.equals(key));
            case LRU_LFU -> cacheHitListForLruLfu.removeIf(x -> x.getFirst().equals(key));
        }
        removeCache(key);
    }

    @Override
    public synchronized Pair<Boolean, Optional<?>> getFromCache(String key) {
        boolean cacheContainsKey = true;
        Object value = null;
        Long expireTime = cacheExpireRecord.get(key);
        // 如果存在这个Key
        if (expireTime != null) {
            // 如果数据已经过期，此处使用了延迟删除，只有查询发现过期了才会删除
            // 0L是特殊的，它代表永不过期
            if (expireTime != 0L && expireTime < System.currentTimeMillis()) {
                log.info("SIMPLE CACHE {}缓存过期：{}", name, key);
                removeCacheAndCacheHit(key);
                cacheContainsKey = false;
            } else {
                // 从缓存中获取数据
                value = cache.get(key);
                collectHitInfoForStrategy(key);
            }
        } else {
            cacheContainsKey = false;
        }
        return Pair.of(cacheContainsKey, Optional.ofNullable(value));
    }

    private synchronized void maxSizeExpireCheck() {
        Set<String> keys = cacheExpireRecord.keySet();
        Set<String> keysDel = new HashSet<>();
        for (String key : keys) {
            Long expireTime = cacheExpireRecord.get(key);
            if (expireTime != 0L && expireTime < System.currentTimeMillis()) {
                log.info("SIMPLE CACHE {}缓存过期：{}", name, key);
                keysDel.add(key);
            }
        }
        // 遍历这些Key，依次清除
        keysDel.forEach(this::removeCacheAndCacheHit);
        // 清除之后还是超出最大大小，则进行清除，只留下配置的缓存大小：maxSize * clearProportion
        if (cache.size() > maxSize) {
            clearWithStrategy((cache.size() - maxSize)
                    + (int) (maxSize * (1 - clearProportion)));
        }
    }

    private void removeCache(String key) {
        cacheExpireRecord.remove(key);
        cache.remove(key);
        log.info("SIMPLE CACHE {}缓存清除：{}", name, key);
    }

    @Override
    public synchronized int deleteCache(String keyPrefix) {
        Set<String> keys = new HashSet<>();
        // 先查到以这个前缀开头的所有Key
        cache.forEach((k, v) -> {
            if (k.startsWith(keyPrefix)) {
                keys.add(k);
            }
        });
        // 遍历这些Key，依次清除
        keys.forEach(this::removeCacheAndCacheHit);
        return keys.size();
    }

    @Override
    public synchronized void setCache(String key, Object value, long timeToLive, TimeUnit timeUnit) {
        cache.put(key, value);
        // 记录失效时间
        if (timeToLive <= 0L) {
            cacheExpireRecord.put(key, 0L);
        } else {
            cacheExpireRecord.put(key, System.currentTimeMillis() + timeUnit.toMillis(timeToLive));
        }
        collectHitInfoForStrategy(key);
        if (cacheExpireRecord.size() > maxSize) {
            maxSizeExpireCheck();
        }
    }

    public synchronized int getCacheSize() {
        return cache.size();
    }

    public String getName() {
        return name;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getStrategy() {
        return strategy;
    }

    public double getClearProportion() {
        return clearProportion;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454

测试代码

package cn.hengyumo.dawn.example;

import cn.hengyumo.dawn.core.cache.types.DawnSimpleCache;
import org.junit.Assert;
import org.junit.Test;
import org.springframework.data.util.Pair;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.Random;
import java.util.concurrent.TimeUnit;

public class DawnSimpleCacheTest {

    @Test
    public void simpleTest() throws InterruptedException {
        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache();
        dawnSimpleCache.setCache("test", "xxx", 2, TimeUnit.SECONDS);
        Pair<Boolean, Optional<?>> value = dawnSimpleCache.getFromCache("test");
        Assert.assertTrue(value.getFirst());
        Assert.assertTrue(value.getSecond().isPresent());
        String val = (String) value.getSecond().orElse(null);
        Assert.assertEquals("xxx", val);
        Thread.sleep(2000);
        value = dawnSimpleCache.getFromCache("test");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
        dawnSimpleCache.setCache("test", "xxx", 2, TimeUnit.SECONDS);
        dawnSimpleCache.deleteCache("test");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
    }

    @Test
    public void testLru() throws InterruptedException {
        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache(
                "testCache", 2, DawnSimpleCache.LRU, 1F);
        dawnSimpleCache.setCache("test1", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test1");

        dawnSimpleCache.setCache("test2", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test2");
        Thread.sleep(2000);
        dawnSimpleCache.getFromCache("test1");

        dawnSimpleCache.setCache("test3", "xxx", 200, TimeUnit.SECONDS);
        // 这时 test2 应该被清除
        Pair<Boolean, Optional<?>> value = dawnSimpleCache.getFromCache("test2");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
        Assert.assertEquals(2, dawnSimpleCache.getCacheSize());
    }

    @Test
    public void testLfu() {
        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache(
                "testCache", 2, DawnSimpleCache.LFU, 1F);
        dawnSimpleCache.setCache("test1", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test1");

        dawnSimpleCache.setCache("test2", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test2");
        dawnSimpleCache.getFromCache("test1");
        dawnSimpleCache.getFromCache("test2");

        dawnSimpleCache.setCache("test3", "xxx", 200, TimeUnit.SECONDS);

        // 这时 test3 应该被清除
        Pair<Boolean, Optional<?>> value = dawnSimpleCache.getFromCache("test3");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
        Assert.assertEquals(2, dawnSimpleCache.getCacheSize());
    }

    @Test
    public void testFifo() {

        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache(
                "testCache", 2, DawnSimpleCache.FIFO, 1F);
        dawnSimpleCache.setCache("test1", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test1");

        dawnSimpleCache.setCache("test2", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test2");
        dawnSimpleCache.getFromCache("test1");
        dawnSimpleCache.getFromCache("test2");

        dawnSimpleCache.setCache("test3", "xxx", 200, TimeUnit.SECONDS);

        // 这时 test1 应该被清除
        Pair<Boolean, Optional<?>> value = dawnSimpleCache.getFromCache("test1");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
        Assert.assertEquals(2, dawnSimpleCache.getCacheSize());
    }

    @Test
    public void testLruLfu() throws InterruptedException {

        DawnSimpleCache dawnSimpleCache = new DawnSimpleCache(
                "testCache", 2, DawnSimpleCache.LRU_LFU, 1F);
        dawnSimpleCache.setCache("test1", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test1");
        dawnSimpleCache.setCache("test2", "xxx", 200, TimeUnit.SECONDS);
        dawnSimpleCache.getFromCache("test2");
        dawnSimpleCache.getFromCache("test1");
        Thread.sleep(2000);
        dawnSimpleCache.getFromCache("test2");

        dawnSimpleCache.setCache("test3", "xxx", 200, TimeUnit.SECONDS);

        // test1 3 / 2, test2 3/ 0.., test3 1/0..
        // 这时 test1 应该被清除
        Pair<Boolean, Optional<?>> value = dawnSimpleCache.getFromCache("test1");
        Assert.assertFalse(value.getFirst());
        Assert.assertFalse(value.getSecond().isPresent());
        Assert.assertEquals(2, dawnSimpleCache.getCacheSize());
    }

    @Test
    public void performanceTest() throws InterruptedException {
        // 查询次数
        int readSize = 5000;
        int dataSize = 1000;
        double hot = 0.05;  // 50
        double delProportion = 0.05;
        // 0.51
        double clearProportion = (hot / (hot + (1 - hot) * hot));
        // 二八定律 dataSize * 0.2 + dataSize * 0.8 * 0.2 = dataSize * 0.36 / 0.56
        // 189
        int maxSize = (int) ((int) (dataSize * (hot + (1 - hot) * hot)) / clearProportion);
        // 0.2 / 0.36 = 0.56 缓存中的热数据占比
        int expire = 300_000;
        long searchTime = 200L;
        Random random = new Random(System.currentTimeMillis());
        StringBuilder sb = new StringBuilder();
        List<DawnSimpleCache> cacheList = new ArrayList<>(4);
        cacheList.add(new DawnSimpleCache(
                "LRU", maxSize, DawnSimpleCache.LRU, clearProportion));
        cacheList.add(new DawnSimpleCache(
                "LFU", maxSize, DawnSimpleCache.LFU, clearProportion));
        cacheList.add(new DawnSimpleCache(
                "FIFO", maxSize, DawnSimpleCache.FIFO, clearProportion));
        cacheList.add(new DawnSimpleCache(
                "LRU_LFU", maxSize, DawnSimpleCache.LRU_LFU, clearProportion));
        for (DawnSimpleCache cache : cacheList) {
            long start = System.currentTimeMillis();
            int read = 0;
            int write = 0;
            int del = 0;
            for (int i = 0; i < readSize; i++) {
                double r = random.nextDouble();
                // 删除的可能性
//                if (r < delProportion) {
                if (i % 50 == 1) { // 1/50
                    cache.deleteCache("key" + random.nextInt(dataSize));
                    del ++;
                }
                int index;
                // 80 % 的 查询集中在 20%的数据
                if (r < (1 - hot)) {
                    index = random.nextInt((int) (dataSize * hot));
                } else {
                    index = (int) (dataSize * hot) + random.nextInt((int) (dataSize * (1 - hot)));
                }
                Pair<Boolean, Optional<?>> value = cache.getFromCache("key" + index);
                read ++;
                if (!value.getFirst()) {
                    // 模拟没查到缓存时重新设置
                    Thread.sleep(searchTime);
                    cache.setCache("key" + index, index, expire, TimeUnit.MILLISECONDS);
                    write ++;
                }
            }

            long time = System.currentTimeMillis() - start;
            sb.append(cache.getName())
                    .append("耗时：").append(time)
                    .append(" write：").append(write)
                    .append(" read：").append(read)
                    .append(" del：").append(del)
                    // 快了多少倍
                    .append(" score：").append((double) (read * searchTime)/ (double) time)
                    .append('\n');
        }
        System.out.println("\n\n" + sb);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190