Implementation of a replacement policy which uses the clock algorithm. All the cache entries are stored in a circular buffer, called the clock. There is also a clock hand which points to one of the entries in the clock. Each time an entry is accessed, it is marked as recently used. If a new entry is inserted into the cache and the cache is full, the clock hand is moved until it is over a not recently used entry, and that entry is evicted to make space for the new entry. Each time the clock hand sweeps over a recently used entry, it is marked as not recently used, and it will be a candidate for removal the next time the clock hand sweeps over it, unless it has been marked as recently used in the meantime.

To allow concurrent access from multiple threads, the methods in this class need to synchronize on a number of different objects:

CacheEntry objects must be locked before they can be used
accesses to the clock structure (circular buffer + clock hand) should be synchronized on the ArrayList representing the circular buffer
accesses to individual Holder objects in the clock structure should be protected by synchronizing on the holder

To avoid deadlocks, we need to ensure that all threads obtain synchronization locks in the same order. CacheEntry's class javadoc dictates the order when locking CacheEntry objects. Additionally, we require that no thread should obtain any other synchronization locks while it is holding a synchronization lock on the clock structure or on a Holder object. The threads are however allowed to obtain synchronization locks on the clock structure or on a holder while they are locking one or more CacheEntry objects.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private class	ClockPolicy.Holder Holder class which represents an entry in the cache.

Field Summary

Modifier and Type	Field and Description
private final ConcurrentCache	cacheManager The cache manager for which this replacement policy is used.
private final ArrayList<ClockPolicy.Holder>	clock The circular clock buffer which holds all the entries in the cache.
private final AtomicInteger	freeEntries The number of free entries.
private int	hand The current position of the clock hand.
private final AtomicBoolean	isShrinking Tells whether there currently is a thread in the `doShrink()` method.
private static final float	MAX_ROTATION How large part of the clock to look at before giving up in `rotateClock()`.
private final int	maxSize The maximum size of the cache.
private static final int	MIN_ITEMS_TO_CHECK The minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.
private static final float	PART_OF_CLOCK_FOR_SHRINK How large part of the clock to look at before giving up finding an evictable entry in `shrinkMe()`.

Access	Constructor and Description
pack-priv	ClockPolicy(ConcurrentCache the cache manager that requests this policy cacheManager, int the initial capacity of the cache initialSize, int the maximum size of the cache maxSize) Create a new `ClockPolicy` instance.

Method Summary

Modifier and Type	Method and Description
public void	doShrink() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.doShrink. Try to shrink the clock if it's larger than its maximum size.
public void	insertEntry(CacheEntry the entry to insert (must be locked) entry) Implements org.apache.derby.impl.services.cache.ReplacementPolicy.insertEntry. Insert an entry into the cache.
private boolean	Returns: whether or not this entry can be evicted (provided that its `Cacheable` is cleaned first) isEvictable(CacheEntry the entry to check e, ClockPolicy.Holder the holder which holds the entry h, boolean tells whether or not the recently used flag should be cleared on the entry (`true` only when called as part of a normal clock rotation) clearRecentlyUsedFlag) Check if an entry can be evicted.
private ClockPolicy.Holder	Returns: the holder under the clock hand, or `null` if the clock is empty moveHand() Get the holder under the clock hand, and move the hand to the next holder.
private void	removeHolder(int position of the holder pos, ClockPolicy.Holder the holder to remove h) Remove the holder at the given clock position.
private ClockPolicy.Holder	Returns: a holder that we can reuse, or `null` if we didn't find one rotateClock(CacheEntry the entry to insert entry, boolean tells whether evictions are allowed (normally `true` if the cache is full and `false` otherwise) allowEvictions) Rotate the clock in order to find a free space for a new entry.
private void	shrinkMe() Perform the shrinking of the clock.
public int	size() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.size. Get the number of entries allocated in the data structure that holds cached objects.

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

cacheManager	back to summary
private final ConcurrentCache cacheManager The cache manager for which this replacement policy is used.

clock	back to summary
private final ArrayList<ClockPolicy.Holder> clock The circular clock buffer which holds all the entries in the cache. Accesses to `clock` and `hand` must be synchronized on `clock`.

freeEntries	back to summary
private final AtomicInteger freeEntries The number of free entries. This is the number of objects that have been removed from the cache and whose entries are free to be reused without eviction.

hand	back to summary
private int hand The current position of the clock hand.

isShrinking	back to summary
private final AtomicBoolean isShrinking Tells whether there currently is a thread in the `doShrink()` method. If this variable is `true` a call to `doShrink()` will be a no-op.

MAX_ROTATION	back to summary
private static final float MAX_ROTATION How large part of the clock to look at before giving up in `rotateClock()`.

maxSize	back to summary
private final int maxSize The maximum size of the cache. When this size is exceeded, entries must be evicted before new ones are inserted.

MIN_ITEMS_TO_CHECK	back to summary
private static final int MIN_ITEMS_TO_CHECK The minimum number of items to check before we decide to give up looking for evictable entries when rotating the clock.

PART_OF_CLOCK_FOR_SHRINK	back to summary
private static final float PART_OF_CLOCK_FOR_SHRINK How large part of the clock to look at before giving up finding an evictable entry in `shrinkMe()`.

ClockPolicy	back to summary
pack-priv ClockPolicy(ConcurrentCache cacheManager, int initialSize, int maxSize) Create a new `ClockPolicy` instance. Parameters cacheManager:ConcurrentCache the cache manager that requests this policy initialSize:int the initial capacity of the cache maxSize:int the maximum size of the cache

Method Detail

doShrink	back to summary
public void doShrink() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.doShrink. Try to shrink the clock if it's larger than its maximum size.

doShrink

back to summary

public void doShrink()

Implements org.apache.derby.impl.services.cache.ReplacementPolicy.doShrink.

Try to shrink the clock if it's larger than its maximum size.

insertEntry	back to summary
public void insertEntry(CacheEntry entry) throws StandardException Implements org.apache.derby.impl.services.cache.ReplacementPolicy.insertEntry. Insert an entry into the cache. If the maximum size is exceeded, evict a not recently used object from the cache. If there are no entries available for reuse, increase the size of the cache. Parameters entry:CacheEntry the entry to insert (must be locked) Exceptions StandardException: if an error occurs when inserting the entry

insertEntry

back to summary

public void insertEntry(CacheEntry entry) throws StandardException

Implements org.apache.derby.impl.services.cache.ReplacementPolicy.insertEntry.

Insert an entry into the cache. If the maximum size is exceeded, evict a not recently used object from the cache. If there are no entries available for reuse, increase the size of the cache.

Parameters

entry:CacheEntry: the entry to insert (must be locked)

Exceptions

StandardException:: if an error occurs when inserting the entry

isEvictable back to summary

isEvictable	back to summary
private boolean isEvictable(CacheEntry e, ClockPolicy.Holder h, boolean clearRecentlyUsedFlag) Check if an entry can be evicted. Only entries that still are present in the cache, are not kept and not recently used, can be evicted. This method does not check whether the `Cacheable` contained in the entry is dirty, so it may be necessary to clean it before an eviction can take place even if the method returns `true`. The caller must hold the lock on the entry before calling this method. Parameters e:CacheEntry the entry to check h:ClockPolicy.Holder the holder which holds the entry clearRecentlyUsedFlag:boolean tells whether or not the recently used flag should be cleared on the entry (`true` only when called as part of a normal clock rotation) Returns:boolean whether or not this entry can be evicted (provided that its `Cacheable` is cleaned first)

private boolean isEvictable(CacheEntry e, ClockPolicy.Holder h, boolean clearRecentlyUsedFlag)

Check if an entry can be evicted. Only entries that still are present in the cache, are not kept and not recently used, can be evicted. This method does not check whether the Cacheable contained in the entry is dirty, so it may be necessary to clean it before an eviction can take place even if the method returns true. The caller must hold the lock on the entry before calling this method.

Parameters

e:CacheEntry: the entry to check
h:ClockPolicy.Holder: the holder which holds the entry
clearRecentlyUsedFlag:boolean: tells whether or not the recently used flag should be cleared on the entry (true only when called as part of a normal clock rotation)

Returns:boolean

whether or not this entry can be evicted (provided that its Cacheable is cleaned first)

moveHand back to summary

moveHand	back to summary
private ClockPolicy.Holder moveHand() Get the holder under the clock hand, and move the hand to the next holder. Returns:ClockPolicy.Holder the holder under the clock hand, or `null` if the clock is empty

private ClockPolicy.Holder moveHand()

Get the holder under the clock hand, and move the hand to the next holder.

Returns:ClockPolicy.Holder: the holder under the clock hand, or null if the clock is empty

removeHolder	back to summary
private void removeHolder(int pos, ClockPolicy.Holder h) Remove the holder at the given clock position. Parameters pos:int position of the holder h:ClockPolicy.Holder the holder to remove

removeHolder

back to summary

private void removeHolder(int pos, ClockPolicy.Holder h)

Remove the holder at the given clock position.

Parameters

pos:int: position of the holder
h:ClockPolicy.Holder: the holder to remove

rotateClock back to summary

rotateClock	back to summary
private ClockPolicy.Holder rotateClock(CacheEntry entry, boolean allowEvictions) throws StandardException Rotate the clock in order to find a free space for a new entry. If `allowEvictions` is `true`, an not recently used object might be evicted to make room for the new entry. Otherwise, only unused entries are searched for. When evictions are allowed, entries are marked as not recently used when the clock hand sweeps over them. The search stops when a reusable entry is found, or when more than a certain percentage of the entries have been visited. If there are free (unused) entries, the search will continue until a reusable entry is found, regardless of how many entries that need to be checked. Parameters entry:CacheEntry the entry to insert allowEvictions:boolean tells whether evictions are allowed (normally `true` if the cache is full and `false` otherwise) Returns:ClockPolicy.Holder a holder that we can reuse, or `null` if we didn't find one

private ClockPolicy.Holder rotateClock(CacheEntry entry, boolean allowEvictions) throws StandardException

Rotate the clock in order to find a free space for a new entry. If allowEvictions is true, an not recently used object might be evicted to make room for the new entry. Otherwise, only unused entries are searched for. When evictions are allowed, entries are marked as not recently used when the clock hand sweeps over them. The search stops when a reusable entry is found, or when more than a certain percentage of the entries have been visited. If there are free (unused) entries, the search will continue until a reusable entry is found, regardless of how many entries that need to be checked.

Parameters

entry:CacheEntry: the entry to insert
allowEvictions:boolean: tells whether evictions are allowed (normally true if the cache is full and false otherwise)

Returns:ClockPolicy.Holder

a holder that we can reuse, or null if we didn't find one

shrinkMe	back to summary
private void shrinkMe() Perform the shrinking of the clock. This method should only be called by a single thread at a time.

size	back to summary
public int size() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.size. Doc from org.apache.derby.impl.services.cache.ReplacementPolicy.size. Get the number of entries allocated in the data structure that holds cached objects. This number could include empty entries for objects that have been removed from the cache, if those entries are still kept in the data structure for reuse. Returns:int the number of entries allocated in the cache Annotations @Override

size

back to summary

public int size()

Implements org.apache.derby.impl.services.cache.ReplacementPolicy.size.

Doc from org.apache.derby.impl.services.cache.ReplacementPolicy.size.

Get the number of entries allocated in the data structure that holds cached objects. This number could include empty entries for objects that have been removed from the cache, if those entries are still kept in the data structure for reuse.

Returns:int

the number of entries allocated in the cache

Annotations

@Override

org.apache.derby.impl.services.cache back to summary

private Class ClockPolicy.Holder

Class Inheritance

extends Object
implements Callback

java.lang.Object
org.apache.derby.impl.services.cache.ClockPolicy.Holder

All Implemented Interfaces

org.apache.derby.impl.services.cache.ReplacementPolicy.Callback

Holder class which represents an entry in the cache. It maintains a recentlyUsed required by the clock algorithm. The class also implements the Callback interface, so that ConcurrentCache can notify the clock policy about events relevant to the clock algorithm.

Field Summary

Modifier and Type	Field and Description
private CacheEntry	entry Reference to the `CacheEntry` object held by this object.
private boolean	evicted Flag which tells whether this holder has been evicted from the clock.
private Cacheable	freedCacheable Cacheable object from a removed object.
pack-priv boolean	recentlyUsed Flag indicating whether or not this entry has been accessed recently.

Constructor Summary

Access	Constructor and Description
pack-priv	Holder(CacheEntry e)

Method Summary

Modifier and Type	Method and Description
public void	access() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.access. Mark this entry as recently used.
pack-priv synchronized boolean	Returns: `true` if the holder was successfully evicted, `false` otherwise evictIfFree() Evict this holder from the clock if it is not associated with an entry.
public synchronized void	free() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.free. Mark this object as free and reusable.
pack-priv synchronized CacheEntry	Returns: the associated entry getEntry() Returns the entry that is currently associated with this holder.
pack-priv synchronized boolean	Returns: `true` if it has been evicted, `false` otherwise isEvicted() Check whether this holder has been evicted from the clock.
pack-priv synchronized void	setEvicted() Mark this holder as evicted from the clock, effectively preventing reuse of the holder.
pack-priv synchronized void	switchEntry(CacheEntry the entry to associate this holder with e) Switch which entry the holder is associated with.
pack-priv synchronized boolean	Returns: `true` if the holder has been associated with the specified entry, `false` if someone else has taken it or the holder has been evicted from the clock takeIfFree(CacheEntry the entry to associate the holder with (it must be locked by the current thread) e) Associate this holder with the specified entry if the holder is free (that is, not associated with any other entry).

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

entry back to summary

entry	back to summary
private CacheEntry entry Reference to the `CacheEntry` object held by this object. The reference should only be accessed when the thread owns the monitor on this holder. A thread is only allowed to change the reference if it also has locked the entry that the reference points to (if the reference is non-null). This ensures that no other thread can disassociate a holder from its entry while the entry is locked, even though the monitor on the holder has been released.

private CacheEntry entry

Reference to the CacheEntry object held by this object. The reference should only be accessed when the thread owns the monitor on this holder. A thread is only allowed to change the reference if it also has locked the entry that the reference points to (if the reference is non-null). This ensures that no other thread can disassociate a holder from its entry while the entry is locked, even though the monitor on the holder has been released.

evicted	back to summary
private boolean evicted Flag which tells whether this holder has been evicted from the clock. If it has been evicted, it can't be reused when a new entry is inserted. Only the owner of this holder's monitor is allowed to access this variable.

freedCacheable	back to summary
private Cacheable freedCacheable Cacheable object from a removed object. If this object is non-null, `entry` must be `null` (which means that the holder is not associated with any object in the cache).

recentlyUsed	back to summary
pack-priv boolean recentlyUsed Flag indicating whether or not this entry has been accessed recently. Should only be accessed/modified when the current thread has locked the `CacheEntry` object stored in the `entry` field.

Constructor Detail

Holder	back to summary
pack-priv Holder(CacheEntry e)

Method Detail

access back to summary

access	back to summary
public void access() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.access. Mark this entry as recently used. Caller must have locked `entry`.

public void access()

Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.access.

Mark this entry as recently used. Caller must have locked entry.

evictIfFree back to summary

evictIfFree	back to summary
pack-priv synchronized boolean evictIfFree() Evict this holder from the clock if it is not associated with an entry. Returns:boolean `true` if the holder was successfully evicted, `false` otherwise

pack-priv synchronized boolean evictIfFree()

Evict this holder from the clock if it is not associated with an entry.

Returns:boolean: true if the holder was successfully evicted, false otherwise

free back to summary

free	back to summary
public synchronized void free() Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.free. Mark this object as free and reusable. Caller must have locked `entry`.

public synchronized void free()

Implements org.apache.derby.impl.services.cache.ReplacementPolicy.Callback.free.

Mark this object as free and reusable. Caller must have locked entry.

getEntry	back to summary
pack-priv synchronized CacheEntry getEntry() Returns the entry that is currently associated with this holder. Returns:CacheEntry the associated entry

getEntry

back to summary

pack-priv synchronized CacheEntry getEntry()

Returns the entry that is currently associated with this holder.

Returns:CacheEntry: the associated entry

isEvicted back to summary

isEvicted	back to summary
pack-priv synchronized boolean isEvicted() Check whether this holder has been evicted from the clock. Returns:boolean `true` if it has been evicted, `false` otherwise

pack-priv synchronized boolean isEvicted()

Check whether this holder has been evicted from the clock.

Returns:boolean: true if it has been evicted, false otherwise

setEvicted	back to summary
pack-priv synchronized void setEvicted() Mark this holder as evicted from the clock, effectively preventing reuse of the holder. Calling thread must have locked the holder's entry.

switchEntry	back to summary
pack-priv synchronized void switchEntry(CacheEntry e) Switch which entry the holder is associated with. Will be called when we evict an entry to make room for a new one. When this method is called, the current thread must have locked both the entry that is evicted and the entry that is inserted. Parameters e:CacheEntry the entry to associate this holder with

switchEntry

back to summary

pack-priv synchronized void switchEntry(CacheEntry e)

Switch which entry the holder is associated with. Will be called when we evict an entry to make room for a new one. When this method is called, the current thread must have locked both the entry that is evicted and the entry that is inserted.

Parameters

e:CacheEntry: the entry to associate this holder with

takeIfFree back to summary

takeIfFree	back to summary
pack-priv synchronized boolean takeIfFree(CacheEntry e) Associate this holder with the specified entry if the holder is free (that is, not associated with any other entry). Parameters e:CacheEntry the entry to associate the holder with (it must be locked by the current thread) Returns:boolean `true` if the holder has been associated with the specified entry, `false` if someone else has taken it or the holder has been evicted from the clock

pack-priv synchronized boolean takeIfFree(CacheEntry e)

Associate this holder with the specified entry if the holder is free (that is, not associated with any other entry).

Parameters

e:CacheEntry: the entry to associate the holder with (it must be locked by the current thread)

Returns:boolean

true if the holder has been associated with the specified entry, false if someone else has taken it or the holder has been evicted from the clock

pack-priv final Class ClockPolicy

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class ClockPolicy.Holder

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail