7 ms·
Analyzing the codebase of Caffeine, a high performance caching library
- quotemstr 2y agoHuh. Their segmented LRU setup is similar to the Linux kernel's active and inactive lists for pages. Convergent evolution in action.
- NovaX 2y agoI tried to reimplement Linux’s algorithm in [1], but I cannot be sure about correctness. They adjust the fixed sizes at construction based on device’s total memory, so it varies if a phone or server. This fast trace simulation in the CI [2] may be informative (see DClock). Segmentation is very common, where algorithms differ by how they promote and how/if they adapt the sizes. [1] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/DClockPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [2] https://github.com/ben-manes/caffeine/actions/runs/13086596566#summary-36518459069 https://github.com/ben-manes/caffeine/actions/runs/130865965...
- synthc 2y agoInteresting deep dive on the internals of Caffeine, a widely used JVM caching library.
- deleted 2y ago[deleted]
- DonHopkins 2y ago[flagged]
- deleted 2y ago[deleted]
- theandrewbailey 2y ago[flagged]
- jupiterroom 2y agoreally random question - but what is used to create the images in this blog post? I see this style quite often but never been able to track down what is used.
- jupiterroom 2y agoi.e these - https://adriacabeza.github.io/img/tinylfu.png https://adriacabeza.github.io/img/tinylfu.png
- syct 2y agoTry this https://excalidraw.com/ https://excalidraw.com/
- deleted 2y ago[deleted]
- atombender 2y agoI suspect they used Excalidraw [1]. It's a nice, quick tool for this kind of sketching, and supports collaborative drawing. [1] https://excalidraw.com/ https://excalidraw.com/
- deleted 2y ago[deleted]
- itishappy 2y agohttps://excalidraw.com/ https://excalidraw.com/ https://d2lang.com/ https://d2lang.com/ https://www.drawio.com/ https://www.drawio.com/ For something a bit lower level, try: https://roughjs.com/ https://roughjs.com/ It's what powers the sketch-like look from many of the sites above.
- homarp 2y agoif you look at the metadata of each png, you will find the application/vnd/excalidraw/json field that contains the image in excalidraw format.
- jedberg 2y agoIt would be interesting to see this on reddit's workload. The entire system was designed around the cache getting a 95%+ hit rate, because basically anything on front page of the top 1000 subreddits will get the overwhelming majority of traffic, so the cache is mostly filled with that. In other words, this solves the problem of "one hit wonders" getting out of the cache quickly, but that basically already happened with the reddit workload. The exception to that was Google, which would scrape old pages, and which is why we shunted them to their own infrastructure and didn't cache their requests. Maybe with this algo, we wouldn't have had to do that.
- masklinn 2y agoWouldn’t one hit wonders still be an issue? They might get evicted relatively fast anyway but assuming an LRU each will still take a cache entry until they go through the entire thing and finally get evicted. Although if that’s your concern you can probably just add a smaller admission cache in front of the main cache, possibly with a promotion memory.
- JanecekPetr 2y agoThat's kind of the idea of Caffeine, it has admission buffers, and it adapts automatically between LRU and LFU. The original algorithm is called Windiw TinyLFU (design https://github.com/ben-manes/caffeine/wiki/Design https://github.com/ben-manes/caffeine/wiki/Design), see it in action e.g. here: https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency
- masklinn 2y agoI know that, but I’m not replying to a comment about caffeine, rather the opposite.
- NovaX 2y agoI think the idea is that the cache is so large that hot data won't be forced out by one-hit wonders. In this 2017 talk [1], the speaker says that Twitter's SLA depends on having a 99.9% hit rate. It is very common to have extremely over provisioned remote caching tier for popular sites. That makes eviction not as important and reducing their operational costs comes by purging expired data more proactively. Hence, memcached switched from away from relying on its LRU to discard expired entries to using a sweeper. Caffeine's approach, a timing wheel, was considered but dormando felt it was too much of an internal change for memcached and the sweeper could serve multiple purposes. [1] https://www.youtube.com/watch?v=kxMKnx__uso https://www.youtube.com/watch?v=kxMKnx__uso
- jbellis 2y agoCaffeine is a gem. Does what it claims, no drama, no scope creep, just works. I've used it in anger multiple times, most notably in Apache Cassandra and DataStax Astra, where it handles massive workloads invisibly, just like you'd want. Shoutout to author Ben Manes if he sees this -- thanks for the great work!
- dstroot 2y agoCodebase has >16k stars on GitHub and only 1 open issue, and 3 open PRs. Never seen that before on a highly used codebase. Kudos to the maintainer(s).
- bean-weevil 2y agoI went through some of the issues to see how aggressively they close them and found this gem: https://github.com/ben-manes/caffeine/issues/1824#issuecomment-2606604996 https://github.com/ben-manes/caffeine/issues/1824#issuecomme...
- ketzo 2y agoDamn, I need that framed over my desk.
- homebrewer 2y agokitty is very close, which is impressive when you remember that the vast majority of the work is done by one guy (Kovid Goyal). https://github.com/kovidgoyal/kitty/issues https://github.com/kovidgoyal/kitty/issues — 0.239% vs 0.137% https://github.com/kovidgoyal/kitty/issues https://github.com/kovidgoyal/kitty/issues — 0.729% vs 0.317% https://github.com/kovidgoyal/kitty/graphs/contributors https://github.com/kovidgoyal/kitty/graphs/contributors
- Lord_Zero 2y agoI haven't looked, but stalebot can make repos look squeaky clean when in reality issues are ignored and then closed without being addressed.
- calpaterson 2y agoSparing everyone else a browse of the bugtracker: the maintainer does not seem to use a bot to autoclose issues. The close issues appeared to be actually closed and it seemed from a quick glance that he actually investigated each filing.
- 2y ago
- nighthawk454 2y agoSeems to be hugged, so here's a cached view https://archive.is/w8yFG https://archive.is/w8yFG https://web.archive.org/web/20250202094451/https://adriacabeza.github.io/2024/07/12/caffeine-cache.html https://web.archive.org/web/20250202094451/https://adriacabe... (images are cached better here)
- thomastay 2y ago> However, diving into a new caching approach without a deep understanding of our current system seemed premature Love love love this - I really enjoy reading articles where people analyze existing high performance systems instead of just going for the new and shiny thing
- dan-robertson 2y agoNear the beginning, the author writes: > Caching is all about maximizing the hit ratio A thing I worry about a lot is discontinuities in cache behaviour (simple example: let’s say a client polls a list of entries, and downloads each entry from the list one at a time to see if it is different. Obviously this feels like a bit of a silly way for a client to behave. If you have a small lru cache (eg maybe it is partitioned such that partitions are small and all the requests from this client go to the same partition) then there is some threshold size where the client transitions from ~all requests hitting the cache to ~none hitting the cache.) This is a bit different from some behaviours always being bad for cache (eg a search crawler fetches lots of entries once). Am I wrong to worry about these kinds of ‘phase transitions’? Should the focus just be on optimising hit rate in the average case?
- hinkley 2y agoI had a team that just did not get my explanations that they had created such a scenario. I had to show them the bus sized “corner case” they had created before they agreed to a more sophisticated cache. That project was the beginning of the end of my affection for caches. Without very careful discipline that few teams have, once they are added all organic attempts at optimization are greatly complicated. It’s global shared state with all the problems that brings. And if you use it instead of the call stack to pass arguments around (eg passing ID instead of User and making everyone look it up ten times), then your goose really is cooked.
- dan-robertson 2y agoInteresting. I hadn’t really thought of global state as being a problem (I mostly think of caches as affecting performance but not semantics but I guess I didn’t really think about cache invalidation/poisoning either). My main worry would be more something like making a cold start very difficult or making things harder to change.
- hinkley 2y agoWhen you design a call tree so that any data used later is passed explicitly down the call tree instead of looked up by ID over and over, then you can be sure that all of the decisions about that data are made on a consistent copy of the data. When you look up the same value 10 times, you not only pollute the flame graphs and call counts which makes proving that a better algorithm is necessary or has any effect much harder, but more importantly, you could get 3 different states and try to make a bunch of updates based on what should be mutually exclusive states in the system. That's the global shared state problem. When you look up a value once and remember it throughout a calculation, it may not be the current state, but at least you have a clean snapshot of the data. Which in situations such as cancelling an account immediately after getting one last discount on a purchase, well, we know which scenario the customer probably meant.
- hinkley 2y agoYears ago I encountered a caching system that I misremembered as being a plugin for nginx and thus was never able to track down again. It had a clever caching algorithm that favored latency over bandwidth. It weighted hit count versus size, so that given limited space, it would rather keep two small records that had more hits than a large record, so that it could serve more records from cache overall. For some workloads the payload size is relatively proportional to the cost of the request - for the system of record. But latency and request setup costs do tend to shift that a bit. But the bigger problem with LRU is that some workloads eventually resemble table scans, and the moment the data set no longer fits into cache, performance falls off a very tall cliff. And not just for that query but now for all subsequent ones as it causes cache misses for everyone else by evicting large quantities of recently used records. So you need to count frequency not just recency.
- YZF 2y agoFor every caching algorithm you can design an adversarial workload that will perform poorly with the cache. Your choice of caching algorithm/strategy needs to match your predicted workload. As you're alluding there's also the question of which resource are you trying to optimize for, if you're trying to minimize processing time that might be a little different than optimizing for bandwidth.
- hinkley 2y agoIf you have to refetch on a cache miss you're going to be doing both. But all optimizations are always playing with the trigraph of cpu time, memory, and IO (with the hidden fourth dimension of legibility), so I don't think you're saying anything that can't be assumed as given. Even among people who tend to pick incorrectly, or just lose track of when the situation has changed.
- YZF 2y agoI understood the OP to have said something along the lines of if we have a fixed cost per object then we should bias towards smaller objects if we want to minimize that cost. And totally legibility and/or simplicity. I'll take something I can reason about and maintain over something more complicated just to eek out a tiny better hit ratio. That said, if you're caching at scale your 0.05% hit ratio can be a big deal. As a matter of personal taste/opinion I also shy away from close loop systems. Feedback makes things complicated in non-intuitive ways. Caffeine seems neat in terms of using feedback to adjust the cache to the workload - as always test with your workloads and pick what is best for your situation.
- urbandw311er 2y agoCaffeine is also the name of a macOS utility to stop the screen going to sleep. Be great if whichever came second could consider a name change.
- unification_fan 2y agoActually, Caffeine is the name of a hello world script I wrote back in the 80s, so...