Java Caching Benchmarks 2016 - Part 2

The work on improving my old Java Caching Benchmarks continues. This post takes a closer look at the aspect of eviction efficiency. For this comparison we take Guava and EHCache2 and compare them to the new kids on the block, Caffeine and cache2k.

How (not) to benchmark

To simulate a real cache scenario an obvious approach would be to construct a benchmark like this:

    Cache<Integer, Integer> cache = ....
    int[] trace = ...
    for (int i = 0; i < trace.length; i++) {
      Integer value = cache.get(trace[i]);
      if (value == null) {
        Thread.sleep(10);
        cache.put(i, i);
      }
    }

The idea is to have an array of cache keys and request the keys from the cache. The array represents either some random pattern or real cache operations recorded from an application. If the value is not available from the cache, it is a cache miss and the value needs to be computed or loaded from a database. To simulate the miss penalty we sleep for 10 milliseconds.

Of course, Thread.sleep is unreliable and will produce jitter, especially in the area of 10 milliseconds. But that is not the point. Let’s say we had chosen 10 milliseconds because the average latency of a database access in our infrastructure is 10 milliseconds. But what happens if we don’t query a local database but an external web service and have 300 milliseconds latency? If we benchmarked with a higher simulated latency, clearly the throughput of the cache that achieves a better hit rate would get better, too.

The performance effect of a cache miss inside the JVM and the local machine can vary per scenario, too. The value might be computed inside the VM, the data may be retrieved from a local SSD or the request goes over the network. We cannot simulate or try out all these variations. For our benchmarks the idea is to isolate the different aspects. In this blog post I will focus on the efficiency of the eviction algorithm. In the next blog post I will take a deeper look at the runtime overhead of eviction.

The Caches

In this benchmark run we focus on these cache implementations:

Google Guava Cache, Version 19, default settings
EHCache, Version 2.10.1, default settings
Caffeine, Version 2.3.0, default settings
cache2k, Version 0.26-BETA, default settings

The JVM settings and hardware are irrelevant for this benchmark, since we focus on the efficiency of the eviction algorithm and not on the runtime performance.

Caffeine needs two special setup parameters for the benchmark:

    int maxSize = ...
    Caffeine.newBuilder()
      .maximumSize(maxSize)
      .executor(Runnable::run)
      .initialCapacity(_maxElements)
      ...

With the executor parameter the eviction happens within the same thread. If this weren’t specified, the eviction would be delayed and the cache would hold more than the configured maximum size, thus leading to wrong results. With the initialCapacity parameter Caffeine is instructed to collect data for the eviction algorithm right from the beginning. Setting this parameter is a courtesy to Caffeine, because otherwise Caffeine cannot perform well for very short traces.

Why are Hazelcast, Infinispan or XY-Cache not included? Because I currently focus on cache implementations that are optimised for use in the local JVM heap. The benchmark concentrates on the effects inside a single VM.

Eviction Algorithms

Guava and EHCache use LRU. Caffeine uses a recently invented algorithm called Window-TinyLFU. Cache2k uses an improved and optimised version of the Clock-Pro algorithm.

Still, LRU (least recently used) is the most used eviction algorithm today. It is simple and easy to implement and achieves quite useful results. Another algorithm is LFU (least frequently used). Instead of deciding based on the recency it decides based on the frequency. Entries that were accessed more often will be kept. Although yielding better performance for some workloads, LFU is not useful as a universal algorithm.

On the other hand LRU, not addressing the frequency aspect, is problematic, too. For example a scan over the whole data set will sweep out entries in the cache that were frequently accessed before and after.

Caffeine and cache2k use modern algorithms that address both aspects, the recency and the frequency. The basic idea is to detect entries accessed more frequently and protect them in a hot set, while evicting entries only seen once faster than LRU would do.

Only cache2k uses an algorithm that allows fully concurrent access. To achieve that, no temporal information about the access is recorded, only an access counter is incremented.

Going into more detail here is beyond this article. For more information the various papers are the best source.

Traces, Traces, Traces

To compare the cache efficiency we use different access patterns and run them against a cache implementation with a specific size limit. For this article I used traces from four different sources.

The traces Cpp, Glimpse, Multi2 and Sprite come from the authors of these papers:

J. Kim, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim, “A Low-Overhead, High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References”, 4th Symposium on Operating System Design & Implementation, October 2000.
D. Lee, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho and C. Kim, “On the Existence of a Spectrum of Policies that Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies”, Proceeding of 1999 ACM SIGMETRICS Conference, May 1999.

All these traces are short and have limited practical value today. These traces are used in a lot of papers about cache eviction algorithms. That is why I always run them and compare the results to the outcomes of the papers.

The OLTP trace was used within the ARC paper:

Nimrod Megiddo and Dharmendra S. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache,” USENIX Conference on File and Storage Technologies (FAST 03), San Francisco, CA, pp. 115-130, March 31-April 2, 2003.

The traces UmassFinancial and UmassWebsearch are available from the UMass Trace Repository.

All traces from the sources above are disk I/O traces, which means all traces contain a sequence of disk block numbers. The block size used in these traces is usually 512 bytes. But the access pattern of a Java object cache is different from that of a disk buffer in an operating system. We need to be aware of this mismatch when comparing Java caches with these traces.

To fill the gap of missing middleware traces, Web07, Web12, OrmAccessBusy and OrmAccessNight are traces from a Java application provided by headissue GmbH. The traces are made public in the cache2k benchmark project on GitHub. As far as I know, these are the only publicly available access traces of a Java application.

The Graphs

The graphs show the achieved hit rate for a cache implementation with a specified cache size. The cache implementations LRU and CLOCK are reference implementations from the cache2k-benchmark package.

OPT is a hypothetical cache implementation that can see into the future and only evicts entries that will never be used again or whose reuse is farthest away. This is also known as Belady’s algorithm. To calculate OPT the simulator code of Caffeine is used.

RAND is the simplest eviction algorithm possible. It selects the eviction candidate at random. The result shown is actually not from ‘perfect random’, but from a realistic cache implementation. The evicted entry is chosen by a forward moving pointer inside the cache hash table.