If caffeine can support weight based evication?

[xiguashu]

Caffeine now supports weight based capacity, but the weight actually does not affect the evication. It's common that different elements in one cache have quite different costs to load, and i think elements with high cost should have some priority during the evication.

[ben-manes]

An eviction aware weight-based policy was explored in the paper Lightweight Robust Size Aware Cache Management. It showed that there was a modest hit rate benefit by taking it into account the entry's relative size. This hasn't been adopted due to personal time, the complexity in aggregating entries to evict due to concurrency, and that these scenarios are not common on the JVM.

A latency-aware policy is still an immature research topic and I've shared my ideas in the past. Unfortunately there are very few workload traces to evaluate and, iirc, those papers often had to create synthetic ones. This means they are likely overfit, may generalize poorly, and could suffer from adversarial workloads or edge cases that the authors didn't imagine. I often read papers on capacity based policies that use a modest range of workloads and the proposed algorithm fails badly on a wider variety, so a feature dearth in data isn't one that makes sense to offer yet.

The approach that I've proposed is to estimate the running latency distribution to derive a per-entry score relative to the average. That might use the exponential weighted moving average or exponential smoothing to help approximate the mean latency and the variance / standard deviation from it. This way one could compute the normalization (z-score, min/max), e.g. how many standard deviations the entry's load time is from the average, as a floating point value between -1.0 and +1.0, which we could map into a step-wise integer (discrete intervals). This could be used by the admission filter which determine the candidate entry's value relative to the victim to decide which to retain, where we currently rely on the aged frequency (0 to 15). By multiplying the frequency and latency scores, a popular entry that is fast to retrieve could be compared to an infrequent entry that is slow to load, and the cache predict which is more useful to keep. The attractiveness of this approach is that it is simple statistical math with low cpu and space overhead, stays relevant to the recently observed workload, and minimizes the impact of outliers.

I like the above idea and I think it could work, but there are a lot of choices on which formulas to use and data would determine if one variant worked better than another. If you are interested in this feature then gathering data sets is the first hurdle where need some help.

[xiguashu]

I have taken your suggestion and made a cost-aware plan to optimize the average access time of the cache(rather than hit rate). I use frequency * cost / weight as the score of the admission filter, aiming to items with more loading cost and smaller weight can be reserved more likely. And also, I adjust the goal of the hill-climbing algorithm to cost-hit-rate(cost hit ratio = total cost of the hit items / total cost of all requests).
I evaluated the effect of my plan in our production cases, and it does bring obvious optimization in average access time. There are the test result of my cases:

[ben-manes]

Cool. That's something that @gilga1983 and @NadavKeren would probably be interested in.

[ben-manes]

Unfortunately I don’t think so because there is very little data, here only an experience report. There’s no way to know if it will be worse in other workloads. The alternative is to expose internals for others to experiment, but that encourages bad usages. I have to juggle a lot of usages and variety of users, so something that I can’t adequately support or confidently advise on is not a good approach. Ideally we would have many samples from a range of workload types, simulate our ideas, and then promote it to the core with ample tests.

Of course I am happy to see forks and others explore ideas. This library is mature so that’s hopefully low risk to start from, and I tried to make it friendly to hack on (primarily the simulator, but clearly you figured out the rest). If you want to pursue this separately then you have my support.

[xiguashu]

Fine. Thank you for your insights.

[ben-manes]

If you want to share traces and contribute to the simulator that would certainly be appreciated. Sorry that I don't see how to bring in experimental features into a mature library until we have enough knowledge to be confident it is a benefit.

cc'ing a few other cache library authors who might find it an interesting topic to explore
@bitfaster @tatsuya6502 @maypok86 @Yiling-J

[Yiling-J]

@xiguashu I think it might be worth considering making the window part a cost-aware LRU if you want to further improve your code. Since the window size is adaptive, a large window would make the cache behave more like LRU, where optimizing the admission filter for cost wouldn’t provide much benefit. However, if you make the window cost-aware, it could also improve performance in LRU workloads.

[ben-manes]

I got notified by SNIA about Google Thesios's disk traces, which includes the column simulated_latency:

Latency (server-level) in seconds from arrival time to response time at the server. For cache miss read, the value is adjusted by a simulator. For cache hit or write, the value is from real measurement from the original trace.

They obfuscate the data to avoid PII / IP leakages, but is otherwise representative.

@xiguashu you might try seeing how it performs in those workloads. They are 400mb each, so you don't need to run the whole data set and just try a handful of subtraces to ensure consistent results.