public class LRUCache<K,V>
extends java.lang.Object
| Modifier and Type | Class and Description |
|---|---|
private class |
LRUCache.CacheEntry |
private static class |
LRUCache.EntryState |
private class |
LRUCache.LRU |
| Modifier and Type | Field and Description |
|---|---|
private java.util.List<LRUCache.CacheEntry>[] |
buckets
Array of hash buckets
|
private long |
cacheGets
Stats to keep track of cache gets
|
private long |
cacheMisses
Stats to keep track of cache hits for cache gets
|
private long |
cachePuts
Stats to keep track of cache puts
|
private long |
cachePutSleeps
Stats to keep track of # of times writes sleep for free cache entry
|
private EntryIO<K,V> |
entryIO
Callback used to initialize entries not in cache
|
private java.util.concurrent.locks.Lock[] |
latches
Array of latches protecting buckets
|
private static org.slf4j.Logger |
LOG
A logger for this class
|
private static int |
LOG_BUCKET_PER_LATCH
Log of number of hash buckets each latch protects
|
(package private) java.util.Random |
lruRandomizer
Random number generator used for randomizing access to LRUS
|
(package private) LRUCache.LRU[] |
lrus
lru list
|
private static long |
MAX_WRITE_SLEEP_TIME
Max sleep time(in ms) for writes in case of cache eviction failure
|
private int |
maxEntries
maximum number of entries
|
private static int |
MIN_ENTRIES
Min number of entries
|
private long |
minReadVersion
minimum version cache has to satisfy during reads
|
private static int |
NUM_LRUS
Number of lrus
|
private int |
numBuckets
Power of two number of buckets
|
private java.util.concurrent.atomic.AtomicInteger |
numEntries
current number of cache entries
|
| Constructor and Description |
|---|
LRUCache(EntryIO<K,V> entryIO,
int cacheSize) |
| Modifier and Type | Method and Description |
|---|---|
void |
advanceMinReadVersion(long minVersion)
Called as the minimum version that readers will use advances.
|
private void |
doRead(LRUCache.CacheEntry entry,
java.util.concurrent.locks.Lock latch,
Serializer serializer)
Does read the value for the given entry.
|
private void |
doWaitForStateChange(LRUCache.CacheEntry entry,
java.util.concurrent.locks.Lock latch)
Wait for the state change to happen.
|
private LRUCache.CacheEntry |
findNewEntry(K key,
int latchIndex)
Finds a victim entry to be replaced by the given key.
|
V |
get(K key,
long version,
Serializer serializer,
boolean neverReplace)
Finds and returns the entry corresponding to the given key and version.
|
private int |
hash(K key) |
void |
put(K key,
V value,
long newVersion,
Serializer serializer,
boolean neverReplace)
Updates the entry identified with the key with the new value.
|
private void |
putNewVersion(LRUCache.CacheEntry entry,
K key,
V value,
long newVersion,
int hashIndex,
java.util.concurrent.locks.Lock latch,
Serializer serializer,
boolean neverReplace)
Creates a new version of the given entry with the given new version.
|
private V |
searchChainForVersion(LRUCache.CacheEntry head,
long version,
boolean neverReplace)
Searches the given version for the entry that can satisfy the read with the
given version and returns the value of that entry.
|
java.lang.String |
toString() |
private static final org.slf4j.Logger LOG
private java.util.List<LRUCache.CacheEntry>[] buckets
private java.util.concurrent.locks.Lock[] latches
private final int numBuckets
private static final int LOG_BUCKET_PER_LATCH
private static final int NUM_LRUS
private static final int MIN_ENTRIES
private static final long MAX_WRITE_SLEEP_TIME
LRUCache.LRU[] lrus
java.util.Random lruRandomizer
private java.util.concurrent.atomic.AtomicInteger numEntries
private final int maxEntries
private long minReadVersion
private long cacheGets
private long cacheMisses
private long cachePuts
private long cachePutSleeps
public void advanceMinReadVersion(long minVersion)
minVersion - mimimum version that will be read from the cachepublic void put(K key, V value, long newVersion, Serializer serializer, boolean neverReplace) throws java.io.IOException, CacheEvictionException
key - identifier of the entryvalue - new value of the entrynewVersion - version of the new valueserializer - used in case of IOneverReplace - true if caller wants to always keep the entry in cacheIOException, - CacheEvictionExceptionjava.io.IOExceptionCacheEvictionExceptionpublic V get(K key, long version, Serializer serializer, boolean neverReplace) throws java.io.IOException
key - the identifier for the entryversion - version the caller want to readserializer - used in case of IOneverReplace - true if entry is never synced to disk( entry wont be read from disk if not found in memory )java.io.IOExceptionpublic java.lang.String toString()
toString in class java.lang.Objectprivate void putNewVersion(LRUCache.CacheEntry entry, K key, V value, long newVersion, int hashIndex, java.util.concurrent.locks.Lock latch, Serializer serializer, boolean neverReplace) throws java.io.IOException, CacheEvictionException
entry - entry for which a new version will be createdkey - identifier for the entryvalue - new value for the entrynewVersion - new version of the entryhashIndex - hash bucket index which covers the enrtrylatch - lock covering the entryserializer - used in case of IOneverReplace - true if most recent version of entry should be kept in memory all the timejava.io.IOExceptionCacheEvictionExceptionprivate V searchChainForVersion(LRUCache.CacheEntry head, long version, boolean neverReplace)
head - head of the version chainversion - version the caller wants to read atprivate void doWaitForStateChange(LRUCache.CacheEntry entry, java.util.concurrent.locks.Lock latch)
entry - cache entry for which we do the waitlatch - latch which covers the bucket the entry corresponds toprivate void doRead(LRUCache.CacheEntry entry, java.util.concurrent.locks.Lock latch, Serializer serializer) throws java.io.IOException
entry - entry for which we will do the readlatch - latch protecting the entry to which the bucket belongsserializer - used in case of IOjava.io.IOExceptionprivate LRUCache.CacheEntry findNewEntry(K key, int latchIndex) throws CacheEvictionException
key - identifier which we try to put into the cachelatchIndex - index of the currently held hash bucket lockCacheEvictionExceptionprivate int hash(K key)