Eviction: fix performance issue when removing many entries

Removing many entries from a cache with eviction is very slow. The reason
for this is that the internal data structure of ConcurrentLinkedQueue
(used to track concurrent cache hits) degenerates to a very large linked
list caontaining only null-entries.

The effect can be reproduced with ConcurrentLinkedQueue as follows:

  ConcurrentLinkedQueue<Integer> q = new ConcurrentLinkedQueue();
  q.add(-1);
  for (int i = 0; i < 1000000; i++) {
    q.add(i);
    q.remove(i);
  }

Note that this insuspicious looking loop takes more than 40 minutes for a
million items.

In EvitionPolicy.onEntryRemove(), do not remove entries from the concurrent
accessQueue. This is futile anyway, as EvictionPolicy.onEntryHit() and
Segment.get() are not synchronized, so the removed entry can be re-added
at any time after returning from onEntryRemove().

When processing enqueued cache hits in EvictionPolicy.execute(), ignore
entries that have already been removed. For LRU, use LinkedHashMap.get()
instead of put() to achieve this. LIRS already checks entry.isResident(),
so no change is necessary.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: fix lost cache hits in eviction algorithms

EvictionPolicy.execute() drops concurrent cache hits that happen between
processing and clearing the accessQueue. As a result, 'hot' entries may be
evicted before 'cold' entries.

In LRU and LIRS algorithms, process the accessQueue using atomic poll()
operations rather than iteration followed by clear().

Note: accessQueueSize doesn't have to be in sync with the actual queue
size, it is just a hint when the next lazy processing is necessary. Thus,
resetting this to 0 without synchronizing all getters is OK.

The test only covers LRU, as it is much easier to predict.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: process cache hits in correct order

Segment.put() doesn't process enqueued cache hits unless the cache is full.
As a result, newly added entries may be evicted before 'cold' entries.
Luckily, only the last MAX_BATCH_SIZE (64) cache hits are affected by this.

Process enqueued cache hits before adding new entries even if the cache is
not yet full.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: remove batchQueueSizeThreshold

EvictionPolicy.onEntryHit() uses a smaller value than thresholdExpired() to
decide whether enqueued cache hits should be processed. The effect of this
is that Segment.attemptEviction() will unnecessarily try to acquire the
Segment lock, and then do nothing (as thresholdExpired() is still false).

Change EvictionPolicy.onEntryHit() so that it only returns true if the
actual threshold has been reached.

Remove the artificially small batchQueueSizeThreshold members and the now
unnecessary thresholdExpired() API.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: fix eviction APIs that cannot evict anything

An eviction algorithm (or page replacement algorithm, when talking about
virtual memory) decides which entry to remove when a new entry is added
while the cache is full. Accessing a resident entry (i.e. a cache hit)
_does_ _not_ lead to removal / eviction of existing entries, it only
modifies the order in which entries will be evicted on future additions.

(In other words: An algorithm that needs to remove / evict entries on a
cache hit is by definition not an eviction algorithm).

Fix EvitionPolicy and related APIs so that cache hits cannot return a set
of evicted entries.

Note: LIRS.pruneStack() previously added non-resident entries to the set
of entries to evict. This is not necessary for two reasons:

1. Non-resident entries are not resident (i.e. not in the cache), its not
possible to evict something that's not there.

2. LIRSHashEntry.nonResident() removes entries from the stack (and the
HIR queue) before marking them non-resident, so its impossible to encounter
such entries on the stack.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: use strategy pattern

The idea of using a strategy is to eliminate special casing in the rest of
the code.

Remove EvictionPolicy.strategy() and if-conditions using it.

Also prevent calling eviction listeners with empty evicted sets.

Signed-off-by: Karsten Blees <blees@dcon.de>
Eviction: factor out BP-Wrapper logic

One of the nice properties of the BP-Wrapper batching technique is that it
works independently of the actual eviction algorithm.

Factor out the duplicate BP-Wrapper implementations from the LRU / LIRS
classes into a separate EvictionPolicy that can wrap any EvictionPolicy.

Signed-off-by: Karsten Blees <blees@dcon.de>