最频繁访问驻留缓存算法

在搜索系统中，如何缓存搜索最频繁的1000个搜索结果？自定制的精准短文本搜索服务项目代码

 

本文利用了ConcurrentHashMap和AtomicLong实现了线程安全且支持高并发的最频繁访问驻留缓存算法，除了缓存功能，还提供了缓存状态查询接口，非常实用。

 

比如，在搜索管理界面可看到如下缓存状态：

 

缓存状态

 

最大缓存数量: 1000
当前缓存数量: 11
驱逐缓存次数: 0
命中缓存次数: 6
未命中缓存次数: 11
缓存命中比例: 35.294117 %

 

搜索缓存命中情况(11)

序号 搜索关键词 缓存命中次数

1	L	3
2	LYB	2
3	LY	1
4	LANGYB	0
5	X	0
6	LANG	0
7	XL	0
8	LAN	0
9	XLF	0
10	LANGY	0
11	XLFD	0

 

实现代码如下：

 

import java.util.Collections;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 最频繁访问驻留缓存算法
 * Created by ysc on 7/18/16.
 */
public class ConcurrentLRUCache<K, V> {
    private int maxCacheSize;
    private Map<K, CacheItem<V>> cache = new ConcurrentHashMap<>();
    private AtomicLong totalEvictCount = new AtomicLong();
    private AtomicLong hitCount = new AtomicLong();
    private AtomicLong notHitCount = new AtomicLong();

    public ConcurrentLRUCache(int maxCacheSize) {
        cache = new ConcurrentHashMap<>(maxCacheSize, 1, 10);
        this.maxCacheSize = maxCacheSize;
    }

    public String getStatus(){
        StringBuilder status = new StringBuilder();

        long total = hitCount.get()+notHitCount.get();

        status.append("最大缓存数量: ").append(maxCacheSize).append("\n")
                .append("当前缓存数量: ").append(getActualCacheSize()).append("\n")
                .append("驱逐缓存次数: ").append(totalEvictCount.get()).append("\n")
                .append("命中缓存次数: ").append(hitCount.get()).append("\n")
                .append("未命中缓存次数: ").append(notHitCount.get()).append("\n")
                .append("缓存命中比例: ").append(total == 0 ? 0 : hitCount.get()/(float)total*100).append(" %\n");

        return status.toString();
    }

    public String getKeyAndHitCount(){
        StringBuilder status = new StringBuilder();
        AtomicInteger i = new AtomicInteger();

        cache.entrySet().stream().sorted((a,b)->b.getValue().getCount()-a.getValue().getCount()).forEach(entry->status.append(i.incrementAndGet()).append("\t").append(entry.getKey()).append("\t").append(entry.getValue().getCount()).append("\n"));

        return status.toString();
    }

    public int getMaxCacheSize() {
        return maxCacheSize;
    }

    public int getActualCacheSize() {
        return cache.size();
    }

    public Map<K, CacheItem<V>> getCache() {
        return Collections.unmodifiableMap(cache);
    }

    public AtomicLong getTotalEvictCount() {
        return totalEvictCount;
    }

    public long getHitCount() {
        return hitCount.longValue();
    }

    public long getNotHitCount() {
        return notHitCount.longValue();
    }

    public void put(K key, V value){
        if(cache.size() >= maxCacheSize){
            // evict count
            int evictCount = (int)(maxCacheSize*0.1);
            if(evictCount < 1){
                evictCount = 1;
            }
            totalEvictCount.addAndGet(evictCount);
            cache.entrySet().stream().sorted((a,b)->a.getValue().getCount()-b.getValue().getCount()).limit(evictCount).forEach(entry->cache.remove(entry.getKey()));
            return;
        }
        cache.put(key, new CacheItem<V>(value, new AtomicInteger()));
    }

    public V get(K key){
        CacheItem<V> item = cache.get(key);
        if(item != null){
            item.hit();
            hitCount.incrementAndGet();
            return item.getValue();
        }
        notHitCount.incrementAndGet();
        return null;
    }

    private static class CacheItem<V>{
        private V value;
        private AtomicInteger count;

        public CacheItem(V value, AtomicInteger count) {
            this.value = value;
            this.count = count;
        }

        public void hit(){
            this.count.incrementAndGet();
        }

        public V getValue() {
            return value;
        }

        public int getCount() {
            return count.get();
        }
    }

    public static void main(String[] args) {
        ConcurrentLRUCache<Integer, Integer> cache = new ConcurrentLRUCache<>(5);
        for(int i=0; i<9; i++){
            cache.put(i, i);
            if(i%2==0){
                for(int j=0; j<i+2; j++){
                    cache.get(i);
                }
            }
        }
        System.out.println(cache.getStatus());
        System.out.println(cache.getKeyAndHitCount());
    }
}

 

运行代码控制台输出如下：

 

最大缓存数量: 5
当前缓存数量: 5
驱逐缓存次数: 2
命中缓存次数: 30
未命中缓存次数: 0
缓存命中比例: 100.0 %

1	8	10
2	6	8
3	4	6
4	2	4
5	0	2