[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...
288 karma · joined May 4, 2011
[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...
That was resolved in a follow up paper [1], though Ristretto does not implement this. It is implemented by Caffeine, mentioned briefly in this article, which is popular in the Java ecosystem.
[1] https://dgraph.io/blog/refs/Adaptive%20Software%20Cache%20Ma...
There are also slides from Usenix Fast 20, but the video was not released (relevant [2], full [3])
[1] http://highscalability.com/blog/2019/2/25/design-of-a-modern...
[2] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...
[3] https://drive.google.com/file/d/1oHV8SjrdhSdwgZ6jegJh8Ysrbnz...
A broader but less detailed approach for casual readers are the books "Beautiful Code" and "The Architecture of Open Source Applications".
component = metadata + data
system = metadata processors
This way you can decouple business rules from the model by using metadata to instruct how the entity should be processed. At work we use json schema as our type system to describe our entities, where every instance includes the schemas that it implements. The metadata allows us to render an entity, process it via server-side triggers, store and search, use generic crud routes, etc. In a language like Java, this is the same as using reflection to inspect interfaces and annotations for processing an object.
"So, how does Java feel? Java feels playful and flexible. You can build things with it that are themselves flexible. Java feels deterministic. You feel like it’s going to do what you ask it to do. It feels fairly nonthreatening in that you can just try something and you’ll quickly get an error message if it’s crazy. It feels pretty rich. We tried hard to have a fairly large class library straight out of the box. By and large, it feels like you can just sit down and write code."
Please do not push the programming community towards a tribal, us vs them, hostile environment where one belittles their neighbor. We can have interesting, fun, insightful technical debates! There's no reason to devolve into bigotry to "win" an argument, it's a lot more fun to learn from each other and do cool, new things.
[1] https://www.win.tue.nl/~evink/education/avp/pdf/feel-of-java...
That is odd because when I look at the Java style, DualPivotQuicksort [1], it seems that the language authors did not do that. This is so very strange! Their methods are long, complex, and highly documented. Maybe they must be really incompetent Java programmers? I mean, they did put this obtuse abstraction by hiding it in Arrays. That's super crazy, just look at this monstrosity!!!
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
}
Maybe you need to have an intervention with them? Somehow, in some crazy world, even Java programmers are capable of writing good and efficient code. Its like bad developers might do an awful in job in whatever language they used? Can't be true...[1] https://github.com/openjdk/jdk/blob/master/src/java.base/sha...
[1] https://github.com/vitessio/vitess/pull/7439#issuecomment-77...
To my unexperienced eyes, it seemed like a real PITA mostly because the Go authors insisted on artificial limitations externally, but bypassed them internally. I certainly have not found it hard to make Java fast and the core developers have always been open minded when I've talked to them.
[1] https://github.com/torvalds/linux/blob/ac3a0c8472969a03c0496...
[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...
[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...
[4] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[5] https://github.com/ben-manes/caffeine/blob/master/simulator/...
This shows if the implementation could be a bottleneck and scales well enough, after which the hit rate and other factors are more important than raw throughput. I would rather sacrifice a few nanos on a read than suffer much lower hit rates or have long pauses on a write due to eviction inefficiencies.
[1] https://github.com/ben-manes/caffeine/wiki/Benchmarks#read-1...
[2] https://github.com/ben-manes/caffeine/blob/master/caffeine/s...
In that case, one might be concerned about the hit rates. While FIFO & LRU have been shown to work very well for a remote cache, especially in social network workloads, it is a poor choice in many other cases. Database, search, and analytical workloads are LFU & MRU biased due to record scans. I'd be concerned that Segcache's design is not general purpose enough and relies too heavily on optimizations that work for Twitter's use cases.
Unfortunately as applications have dozens of local caches, they are rarely analyzed and tuned. Instead implementations have to monitor the workload and adapt. Popular local caches can concurrently handle 300M+ reads/s, use an adaptive eviction policy, and leverage O(1) proactive expiration. As they are much smaller, there is less emphasis on minimizing metadata overhead and more on system performance, e.g. using memoization to avoid SerDe roundtrips to the remote cache store. See for example Expedia using a local cache to reduce their db reads by 50% which allowed them to remove servers, hit SLAs, and absorb spikes (at a cost of ~500mb) [1].
[1] https://medium.com/expedia-group-tech/latency-improvement-wi...
The two halves can be any algorithm, but LRU and SLRU were chosen in Caffeine. SLRU uses a probation and protected region (20/80 split) so that on a subsequent hit, the item is moved into the protected region. This more aggressively removes an item that was not used, e.g. inaccurately promoted by TinyLFU due to hash collisions. It is a cheap way to get a good recency/frequency eviction ordering.
The frequency threshold is a direct comparison of the two victims (admission window's and the main region's). If the candidate has a higher estimated frequency than the main's victim then it is admitted, otherwise it is discarded.
The admission window accepts all new items and is placed in front of TinyLFU. TinyLFU implements the doorkeeper, popularity sketch, and reset interval. When reset, the doorkeeper is cleared and the counters are halved.
The optimal admission/main sizes depends on the workload. A LRU-biased workload prefers a large admission window (e.g. blockchain mining), while an MRU/LFU-biased one prefers a smaller window (e.g. loop/scans). The policy is adaptive by using hill climbing to [1] walk the hit rate curve towards the best configuration. The design evolution is described in [2-4].
There is no fast track promotion to the main region. A popular item will end up being promoted. The SLRU ordering and reset interval will age it out if unused. The adaptive sizing will grow or shrink the frequency region based on how effective it is.
Cache admission has not been well studied. While TinyLFU is an admission policy, W-TinyLFU turns it into a promotion strategy by always admitting into the window cache. Prior to TinyLFU, bloom filters were used by CDNs to avoid one-hit wonders from polluting the cache [5]. Afterwards, AdaptSize [6] used entry sizes instead of frequency as an admission criteria. RL-Cache [7] tries to defer to ML to sort it out from a dozen signals. There is a paper under review that optimizes W-TinyLFU for entry size aware eviction.
[1] https://dl.acm.org/doi/10.1145/3274808.3274816
[2] http://highscalability.com/blog/2016/1/25/design-of-a-modern...
[3] http://highscalability.com/blog/2019/2/25/design-of-a-modern...
[4] https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...
[5] https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper...
[6] https://www.usenix.org/conference/nsdi17/technical-sessions/...
I met Kirk McKusick (BSD fame) at Fast'20 where he expressed interest in that for ZFS. We tried introducing the idea to the contributors at FreeBSD, Delphix, and LLNL. There is frustration at ARC being memory hungry and the locking is expensive. Unfortunately while there is interest in replacing ARC, all of our contacts were too busy to explore that option.
You can compare the code of ARC [1], LIRS [2], and DClock [3] to see how similar they are.
ARC obtained a lot of awareness but the hit rate is not that great. It is modestly better than LRU, but very wasteful in metadata overhead. LIRS is much better, except it is complex and the paper is confusing so almost all implementations are broken. DClock seems okayish by borrowing LIRS' ideas, but I think it performs worse in most comparisons.
[1] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[2] https://github.com/ben-manes/caffeine/blob/master/simulator/...
[3] https://github.com/ben-manes/caffeine/blob/master/simulator/...
That implements a custom algorithm, Double Clock, which is inspired by LIRS. This patch touches related code, but not that file where the core algorithm is described. I tried to reimplement it in a simulator for analysis and found its hit rate varied significantly on workloads due to the percent given to LRU/LFU regions being based on machine's total memory capacity [2]. That caused it to do better in MRU/LFU workloads on high memory systems and better at LRU workloads on low-memory systems [3]. Talking to the author and there were other details not documented that might make those regions adaptive. In the end, I gave up trying to understand the page cache and if there was a benefit of switching to an alternative eviction policy. It is well written but very confusing code that seems scattered if not a kernel developer.
[1] https://github.com/torvalds/linux/blob/master/mm/workingset....
[2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42...
[3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...
This is a language construct and not enforced within the byte code. There have historically been reasons to allow final to be ignored, such as serialization. Instead the JIT will optimize and deoptimize based on runtime behavior, allowing it to cover cases where overriding is designed for but not done so in the actual runtime environment. There was a nice presentation on "truly final fields" at the 2018 language summit [1].
[1] https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.15...
[2] http://ranger.uta.edu/~sjiang/pubs/papers/ding16_BP-wrapper....
The approach used in that article is to publish the events into multi-producer/single-consumer queues. When a queue is full, then the batch can be performed under a lock to replay and catch-up the LRU. This way the lock is used to ensure single-writer, but does not suffer lock contention. The ring buffer is lock-free, but the cache itself is not. Lock-free can suffer contention or be more expensive algorithmically than if under a lock, so whichever strategy chosen requires careful consideration of the system performance.
[1] http://highscalability.com/blog/2016/1/25/design-of-a-modern...