Local cache needs something better than LRU

[xvrl]

e.g. something like CAR (similar to ARC) or LRU-2Q (used by PostgreSQL)

[xvrl]

caffeine cache solves this in #3028 (See https://github.com/ben-manes/caffeine/wiki/Efficiency for details)

[ben-manes]

@xvrl Can we get traces from Druid? It would be interesting to see efficiencies. Chatted about this briefly with @drcrallen (we need a log of key hashes to run through the simulator)

[xvrl]

@ben-manes let me see what I can do. I think our best bet is to turn off local cache on one node and turn on request logging on one of our memcached instances. That should give us equivalent traces without impacting performance too much.

[xvrl]

@ben-manes how much data would you need?

[ben-manes]

That makes sense. It could cause some skew since the memcached is shared and sharded by key, but hopefully pretty close regardless. The other option is to append to an async logger and assuming that it doesn't drop messages too frequently.

The ARC traces are the best I have so far, and they are each around 50 - 100mb gzip'd. The paper reports that they are 1-6 hours or a few days, I guess depending on how active the cache is for that product. Given @drcrallen's description of the concurrency challenges I suspect an hour is plenty if you have such high volumes. I would xz compresses for a much smaller file.

I suspect your workloads have a lot of scans, so it will be interesting to see where the different policies line up. It should also provide some insight of when the caches top out and adding more memory doesn't improve things.