Steven Schlansker <stevenschlansker <at> gmail.com> writes:
> On Jun 30, 2015, at 11:14 AM, Vladimir Sitnikov wrote:
>
> Final note, is a ConcurrentLinkedHashMap actually the data structure we
> should be using? The "linked" part enforces that the removal strategy is
> not LRU, it is actually FIFO. So an incoming query may evict the oldest
> entry, which could very well be the most used entry. Maybe this is not a
> problem in practice but I thought I'd point it out.
CLHM evicts by LRU. Java's LinkedHashMap may be configured in either insertion
order (FIFO) or access order (LRU). The concurrent version provides only the
access order as it is intended to be used as a cache. So the eviction is
smart, as much as an LRU can be.
CLHM is really easy to shade (as many do), fork (as some do), and is pretty
tiny. An LRU policy is surprisingly tricky to implement fully concurrently,
because every read is in fact a write. This is solved by borrowing an idea
from Postgres - the write ahead log. The reads are recorded cheaply and
replayed in batches so that reads and writes may operate concurrently.
The successor project, Caffeine, includes a design document that describes a
similar approach, with some additional optimizations. Also see the benchmarks.
That cache is heavier (JAR size) due to providing a richer feature set.
Cheers,
Ben (author)
https://github.com/ben-manes/caffeine/wiki/Design
https://github.com/ben-manes/caffeine/wiki/Benchmarks