ben-manes / caffeine / 2239
99%

Ran 02 Feb 2018 11:26PM UTC

Jobs 1

Files 66

Run time 4s

Badge

pending completion

Build # 2239

Build Type

travis-ci

Committed by

Commit Message

Change Caffeine default cache size to 64

Caffeine uses a ConcurrentHashMap under the hood. The way this works is that there are a number of bins, and the bins contain nodes (which contain 0 or more k/v pairs).

When I do a compute or computeIfAbsent, I look for the bin my node should be in, and if it does not exist, I put a placeholder bin there, compute, and then put the value there. If it does exist, I lock the bin, do whatever checks I need to do, put the value if necessary and unlock.

When I am done, I grow the map if necessary (generally increasing it by powers of 2).

Caffeine's default map size is 0, which cases the ConcurrentHashMap to be created with no table. This is cheap, but has the drawback of Caffeine starting off with only 2 buckets.

The issue here is that when I do a computeIfAbsent call, it synchronizes with every other computeIfAbsent call currently in progress (a bigger problem if the compute function is expensive).

For a pathological case, if all of my keys are ending up in one bucket, they will linearize (and end up in either a linked list or a red-black tree). This is expected, and one would anticipate the ConcurrentHashMap to compensate, and indeed it immediately tries to.

However, in order to transfer the node to a new table, (so far as I can read) it joins the synchronization bandwagon which is currently trying to add data to the node. Eventually the transfer should be able to happen (although I suppose synchronization is unfair?), but until this is the case, the transfer cannot complete.

So, this means that you can get some pretty brutal throughput characteristics if you dump a load of contention onto a Caffeine cache with no warmup period.

For example, if I have 1000 threads try and concurrently hammer the same Caffeine loading cache, sleeping for 100ms in their loading function, I get throughput of roughly 10 writes a second. This eventually will grow, but it will take a very long time.

In our case, this ended up with something approaching a deadlock; a low-capacity cache (we think almost empty, with only a few historical inputs) received concurrently some small number of unexpectedly expensive requests between 0 and 60, which each took (say) a minute. In general the system is easily able to deal with such requests - the cache deduplicates such requests, and there are only a few queries that could take this long. However, in this case they caused us to enter a death spiral; they locked all the buckets and stopped any of the other (far cheaper) requests from being served.

To compensate for this, this PR presizes the cache to 64 elements. It uses something like 256 additional bytes of memory for each cache created, but pretty much removes this pathological case.

Hope this makes sense! I may have misunderstood some stuff about ConcurrentHashMap here though.

Pull Request Pull Request #218: Change Caffeine default cache size to 64

Run Details

5715 of 6095 relevant lines covered (93.77%)

0.94 hits per line

Uncovered Existing Lines

Lines	Coverage	∆	File
5	94.1	-0.25%	caffeine/src/main/java/com/github/benmanes/caffeine/cache/BoundedLocalCache.java
13	85.19	-6.88%	caffeine/src/main/java/com/github/benmanes/caffeine/SingleConsumerQueue.java

Jobs

ID	Job ID	Ran	Files	Coverage
2	2239.2 (GROUP=tests)	02 Feb 2018 11:26PM UTC	66	93.77	Travis Job 2239.2

Source Files on build 2239

Coverage	∆	File	Lines	Relevant	Covered	Missed	Hits/Line