具有“对象过期”的对象高速缓存数据结构

Question

Java 中哪种数据结构最适合实现内存中对象缓存，其中对象具有单独的过期时间？

基本上对于缓存，我可以使用提供 put 和 get 方法的 Map（其中键可以是字符串），并使用“时间戳”+“对象”对的有序列表来管理过期时间。因此，清理线程可以检查第一个列表条目，并在其过期时间过后删除该对象。 （删除第一个元素应该在 O(1) 时间内）

Answer 1

您所描述的构建基本上是我的 ExpiringMap。还有其他类似的实现，例如 Guava（请参阅 CacheBuilder) - 尽管我不认为它像 ExpiringMap 那样支持每个条目过期。

Answer 2

缓存框架现在已经相当成熟：

• EhCache：http://ehcache.org/
• Memcached：http://memcached.org/

但是，如果您坚持重新发明轮子，请记住考虑内存利用率。我经常看到实施不当的缓存 (HashMap) 实际上会导致内存泄漏。

请参阅 Cowan 的答案：Java 的WeakHashMap 和缓存：为什么它引用键，而不是值？

Answer 3

我会考虑使用现有的库，例如 ehcache。

但是，如果您想编写自己的线程，我不会使用后台线程，除非您需要它，因为它会增加复杂性。相反，我会让前台线程删除过期的条目。

如果您只需要 LRU 缓存，我会使用 LinkedHashMap。但是，如果您想要定时过期，我会使用带有 PriorityQueue 的 HashMap （这样您就可以检查下一个过期条目是否已过期）

Answer 4

Guava Cachebuilder ：

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
       .maximumSize(10000)
       .expireAfterWrite(10, TimeUnit.MINUTES)
       .removalListener(MY_LISTENER)
       .build(
           new CacheLoader<Key, Graph>() {
             public Graph load(Key key) throws AnyException {
               return createExpensiveGraph(key);
             }
           });

由于 WeekHashmap 不适合缓存，但您始终可以使用 Map> ，其值符合 GC 的周引用条件。

最重要的是，我们始终将 EhCache 、Memcached 和 coherence 作为流行的选择。

Answer 5

我认为你的决定是正确的。
确切地说，我会使用 HashMap。

Answer 6

正如前面的答案中提到的，最好使用流行的内存缓存之一，如 EhCache、Memcached 等。

但是正如您希望通过自己的缓存实现它一样，该缓存具有对象过期功能且时间复杂度较低，我尝试像这样实现它 - （非常感谢任何测试评论/建议）..

public class ObjectCache<K, V> {

    private volatile boolean shutdown;
    private final long maxObjects;
    private final long timeToLive;
    private final long removalThreadRunDelay;
    private final long objectsToRemovePerRemovalThreadRun;
    private final AtomicLong objectsCount;
    private final Map<K, CacheEntryWrapper> cachedDataStore;
    private final BlockingQueue<CacheEntryReference> queue;
    private final Object lock = new Object();
    private ScheduledExecutorService executorService;

    public ObjectCache(long maxObjects, long timeToLive, long removalThreadRunDelay, long objectsToRemovePerRemovalThreadRun) {
        this.maxObjects = maxObjects;
        this.timeToLive = timeToLive;
        this.removalThreadRunDelay = removalThreadRunDelay;
        this.objectsToRemovePerRemovalThreadRun = objectsToRemovePerRemovalThreadRun;
        this.objectsCount = new AtomicLong(0);
        this.cachedDataStore = new HashMap<K, CacheEntryWrapper>();
        this.queue = new LinkedBlockingQueue<CacheEntryReference>();
    }

    public void put(K key, V value) {
        if (key == null || value == null) {
            throw new IllegalArgumentException("Key and Value both should be not null");
        }
        if (objectsCount.get() + 1 > maxObjects) {
            throw new RuntimeException("Max objects limit reached. Can not store more objects in cache.");
        }
        // create a value wrapper and add it to data store map
        CacheEntryWrapper entryWrapper = new CacheEntryWrapper(key, value);
        synchronized (lock) {
            cachedDataStore.put(key, entryWrapper);
        }
        // add the cache entry reference to queue which will be used by removal thread
        queue.add(entryWrapper.getCacheEntryReference());
        objectsCount.incrementAndGet();
        // start the removal thread if not started already
        if (executorService == null) {
            synchronized (lock) {
                if (executorService == null) {
                    executorService = Executors.newSingleThreadScheduledExecutor();
                    executorService.scheduleWithFixedDelay(new CacheEntryRemover(), 0, removalThreadRunDelay, TimeUnit.MILLISECONDS);
                }
            }
        }
    }

    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key can not be null");
        }
        CacheEntryWrapper entryWrapper;
        synchronized (lock) {
            entryWrapper = cachedDataStore.get(key);
            if (entryWrapper != null) {
                // reset the last access time
                entryWrapper.resetLastAccessedTime();
                // reset the reference (so the weak reference is cleared)
                entryWrapper.resetCacheEntryReference();
                // add the new reference to queue
                queue.add(entryWrapper.getCacheEntryReference());
            }
        }
        return entryWrapper == null ? null : entryWrapper.getValue();
    }

    public void remove(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key can not be null");
        }
        CacheEntryWrapper entryWrapper;
        synchronized (lock) {
            entryWrapper = cachedDataStore.remove(key);
            if (entryWrapper != null) {
                // reset the reference (so the weak reference is cleared)
                entryWrapper.resetCacheEntryReference();
            }
        }
        objectsCount.decrementAndGet();
    }

    public void shutdown() {
        shutdown = true;
        executorService.shutdown();
        queue.clear();
        cachedDataStore.clear();
    }

    public static void main(String[] args) throws Exception {
        ObjectCache<Long, Long> cache = new ObjectCache<>(1000000, 60000, 1000, 1000);
        long i = 0;
        while (i++ < 10000) {
            cache.put(i, i);
        }
        i = 0;
        while(i++ < 100) {
            Thread.sleep(1000);
            System.out.println("Data store size: " + cache.cachedDataStore.size() + ", queue size: " + cache.queue.size());
        }
        cache.shutdown();
    }

    private class CacheEntryRemover implements Runnable {
        public void run() {
            if (!shutdown) {
                try {
                    int count = 0;
                    CacheEntryReference entryReference;
                    while ((entryReference = queue.peek()) != null && count++ < objectsToRemovePerRemovalThreadRun) {
                        long currentTime = System.currentTimeMillis();
                        CacheEntryWrapper cacheEntryWrapper = entryReference.getWeakReference().get();
                        if (cacheEntryWrapper == null || !cachedDataStore.containsKey(cacheEntryWrapper.getKey())) {
                            queue.poll(100, TimeUnit.MILLISECONDS); // remove the reference object from queue as value is removed from cache
                        } else if (currentTime - cacheEntryWrapper.getLastAccessedTime().get() > timeToLive) {
                            synchronized (lock) {
                                // get the cacheEntryWrapper again just to find if put() has overridden the same key or remove() has removed it already
                                CacheEntryWrapper newCacheEntryWrapper = cachedDataStore.get(cacheEntryWrapper.getKey());
                                // poll the queue if -
                                // case 1 - value is removed from cache
                                // case 2 - value is overridden by new value
                                // case 3 - value is still in cache but it is old now
                                if (newCacheEntryWrapper == null || newCacheEntryWrapper != cacheEntryWrapper || currentTime - cacheEntryWrapper.getLastAccessedTime().get() > timeToLive) {
                                    queue.poll(100, TimeUnit.MILLISECONDS);
                                    newCacheEntryWrapper = newCacheEntryWrapper == null ? cacheEntryWrapper : newCacheEntryWrapper;
                                    if (currentTime - newCacheEntryWrapper.getLastAccessedTime().get() > timeToLive) {
                                        remove(newCacheEntryWrapper.getKey());
                                    }
                                } else {
                                    break; // try next time
                                }
                            }
                        }
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private class CacheEntryWrapper {
        private K key;
        private V value;
        private AtomicLong lastAccessedTime;
        private CacheEntryReference cacheEntryReference;

        public CacheEntryWrapper(K key, V value) {
            this.key = key;
            this.value = value;
            this.lastAccessedTime = new AtomicLong(System.currentTimeMillis());
            this.cacheEntryReference = new CacheEntryReference(this);
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public AtomicLong getLastAccessedTime() {
            return lastAccessedTime;
        }

        public CacheEntryReference getCacheEntryReference() {
            return cacheEntryReference;
        }

        public void resetLastAccessedTime() {
            lastAccessedTime.set(System.currentTimeMillis());
        }

        public void resetCacheEntryReference() {
            cacheEntryReference.clear();
            cacheEntryReference = new CacheEntryReference(this);
        }
    }

    private class CacheEntryReference {
        private WeakReference<CacheEntryWrapper> weakReference;

        public CacheEntryReference(CacheEntryWrapper entryWrapper) {
            this.weakReference = new WeakReference<CacheEntryWrapper>(entryWrapper);
        }

        public WeakReference<CacheEntryWrapper> getWeakReference() {
            return weakReference;
        }

        public void clear() {
            weakReference.clear();
        }
    }
}