jdbm.helper

Class LRUCache<K,V>

java.lang.Object

jdbm.helper.LRUCache<K,V>

public class LRUCache<K,V>
extends java.lang.Object

This class implements a versioned lru cache. Entries in the cache are identified with a key. When clients get a reference to the an entry, they point to the same object. Hence when the client wants to update and put a new version of the entry to the cache, he should not modify the object it got through the get interface (might copy on write). As new versions of the entries are put, cache maintains the previous versions of the entry. CLients specify the version of the cache entry they want to read. Clients are supposed to update the minimum read version the clients might request so that cache can purge older versions of data. For now, this class assumes clients make sure that put operations are serialized.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	LRUCache.CacheEntry
private static class	LRUCache.EntryState
private class	LRUCache.LRU

Field Summary

Fields

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 Summary

Constructors

Constructor and Description
LRUCache(EntryIO<K,V> entryIO, int cacheSize)

Method Summary

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()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

LOG

private static final org.slf4j.Logger LOG

A logger for this class

buckets

private java.util.List<LRUCache.CacheEntry>[] buckets

Array of hash buckets

latches

private java.util.concurrent.locks.Lock[] latches

Array of latches protecting buckets

numBuckets

private final int numBuckets

Power of two number of buckets

LOG_BUCKET_PER_LATCH

private static final int LOG_BUCKET_PER_LATCH

Log of number of hash buckets each latch protects

See Also:

Constant Field Values

NUM_LRUS

private static final int NUM_LRUS

Number of lrus

See Also:

Constant Field Values

MIN_ENTRIES

private static final int MIN_ENTRIES

Min number of entries

See Also:

Constant Field Values

MAX_WRITE_SLEEP_TIME

private static final long MAX_WRITE_SLEEP_TIME

Max sleep time(in ms) for writes in case of cache eviction failure

See Also:

Constant Field Values

lrus

LRUCache.LRU[] lrus

lru list

lruRandomizer

java.util.Random lruRandomizer

Random number generator used for randomizing access to LRUS

numEntries

private java.util.concurrent.atomic.AtomicInteger numEntries

current number of cache entries

maxEntries

private final int maxEntries

maximum number of entries

entryIO

private final EntryIO<K,V> entryIO

Callback used to initialize entries not in cache

minReadVersion

private long minReadVersion

minimum version cache has to satisfy during reads

cacheGets

private long cacheGets

Stats to keep track of cache gets

cacheMisses

private long cacheMisses

Stats to keep track of cache hits for cache gets

cachePuts

private long cachePuts

Stats to keep track of cache puts

cachePutSleeps

private long cachePutSleeps

Stats to keep track of # of times writes sleep for free cache entry

Constructor Detail

LRUCache

public LRUCache(EntryIO<K,V> entryIO,
                int cacheSize)

Method Detail

advanceMinReadVersion

public void advanceMinReadVersion(long minVersion)

Called as the minimum version that readers will use advances. This lets cache get rid of the older versions of entries.

Parameters:

minVersion - mimimum version that will be read from the cache

put

public void put(K key,
                V value,
                long newVersion,
                Serializer serializer,
                boolean neverReplace)
         throws java.io.IOException,
                CacheEvictionException

Updates the entry identified with the key with the new value.

Parameters:

key - identifier of the entry

value - new value of the entry

newVersion - version of the new value

serializer - used in case of IO

neverReplace - true if caller wants to always keep the entry in cache

Throws:

IOException, - CacheEvictionException

java.io.IOException

CacheEvictionException

get

public V get(K key,
             long version,
             Serializer serializer,
             boolean neverReplace)
      throws java.io.IOException

Finds and returns the entry corresponding to the given key and version.

Parameters:

key - the identifier for the entry

version - version the caller want to read

serializer - used in case of IO

neverReplace - true if entry is never synced to disk( entry wont be read from disk if not found in memory )

Returns:

value read

Throws:

java.io.IOException

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

putNewVersion

private 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

Creates a new version of the given entry with the given new version.

Parameters:

entry - entry for which a new version will be created

key - identifier for the entry

value - new value for the entry

newVersion - new version of the entry

hashIndex - hash bucket index which covers the enrtry

latch - lock covering the entry

serializer - used in case of IO

neverReplace - true if most recent version of entry should be kept in memory all the time

Throws:

java.io.IOException

CacheEvictionException

searchChainForVersion

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. Cache is responsible is for maintaining the versions of entries that readers might still be interested in.

Parameters:

head - head of the version chain

version - version the caller wants to read at

Returns:

value found.

doWaitForStateChange

private void doWaitForStateChange(LRUCache.CacheEntry entry,
                                  java.util.concurrent.locks.Lock latch)

Wait for the state change to happen. Usually used to wait for another thread to complete the IO.Latch covering the entry is held at the entry.

Parameters:

entry - cache entry for which we do the wait

latch - latch which covers the bucket the entry corresponds to

doRead

private void doRead(LRUCache.CacheEntry entry,
                    java.util.concurrent.locks.Lock latch,
                    Serializer serializer)
             throws java.io.IOException

Does read the value for the given entry. At entry, latch is held. It is dropped during the read and regotten after a successful read.

Parameters:

entry - entry for which we will do the read

latch - latch protecting the entry to which the bucket belongs

serializer - used in case of IO

Throws:

java.io.IOException

findNewEntry

private LRUCache.CacheEntry findNewEntry(K key,
                                         int latchIndex)
                                  throws CacheEvictionException

Finds a victim entry to be replaced by the given key.

Parameters:

key - identifier which we try to put into the cache

latchIndex - index of the currently held hash bucket lock

Returns:

Throws:

CacheEvictionException

hash

private int hash(K key)