<p>Caffeine does not implement LRU as its cache eviction policy.  Instead, Caffeine uses a policy called <a href="http://arxiv.org/pdf/1512.00727.pdf" rel="noreferrer">TinyLFU</a>.  The Caffeine documentation includes a page on <a href="https://github.com/ben-manes/caffeine/wiki/Efficiency" rel="noreferrer">Efficiency</a>, which discusses the rationale for this design choice.  Quoting that page:</p>

<blockquote>
  <p><code>TinyLfu</code> relies on a frequency sketch to probabilistically estimate the historic usage of an entry.</p>
</blockquote>

<p>Since Caffeine does not in fact implement LRU, I don't think you can reliably expect it to exhibit strict LRU behavior when you inspect the entries in the cache.</p>

<p>If you absolutely must have LRU behavior, then the JDK standard <a href="http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html" rel="noreferrer"><code>LinkedHashMap</code></a> is a good, straightforward choice.  You would need to subclass it and override <a href="http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html#removeEldestEntry(java.util.Map.Entry)" rel="noreferrer"><code>removeEldestEntry</code></a> with logic to signal when the cache has grown larger than you want it.  If multi-threaded usage is necessary, then you'll need to wrap operations with appropriate synchronization.</p>

<p>Caffeine was heavily inspired by the <a href="https://code.google.com/p/guava-libraries/wiki/CachesExplained" rel="noreferrer">Guava Cache</a>, which similarly provides concurrent access and has approximate LRU behavior.  A quick test of your code against the Guava cache shows similar results.  I am not aware of any standard library that would provide predictable, externally observable LRU results and true concurrent access without a coarse-grained lock.</p>

<p>You might reconsider whether it's really a requirement to have strict, externally observable LRU results.  By its nature, a cache is fast temporary storage to provide optimized lookups.  I would not expect program behavior to change drastically dependent on whether the cache implements strict LRU, an approximation of LRU, LFU, or some other eviction policy.</p>

<p>This prior question also has a great discussion of LRU cache options in Java.</p>

<p><a href="https://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java-6">How would you implement an LRU cache in Java?</a></p>
LRU with Caffeine
<p>I'm trying to use Caffeine as LRU cache, so entries that were added first will be evicted first.
Ran this code:</p>

<pre><code>final Cache&lt;Object, Object&gt; map = Caffeine.newBuilder()
            .maximumSize(10)
            .initialCapacity(10)
            .build();

for (long i=0; i&lt;20;i++) {
        map.put(i, i);
}

map.cleanUp();
System.out.println(map.ge.getAllPresent(map.asMap().keySet()));
</code></pre>

<p>Which prints :</p>

<pre><code>{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 19=19}
</code></pre>

<p>But I expected </p>

<pre><code>{10=10, 11=11, 12=12, 13=13, 14=14, 15=15, 16=16, 17=17, 18=18, 19=19}
</code></pre>

<p>What am I doing wrong?</p>