Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Analyzing the codebase of Caffeine, a high performance caching library

adriacabeza.github.io

Post reply on HN
Print view View original

51–56 of 56 posts

Re: Analyzing the codebase of Caffeine, a high performance caching library

#51

Post by JanecekPetr »

masklinn wrote: post #16
jedberg wrote: post #12

It 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 wi…

Wouldn’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.

That'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), see it in action e.g. here: https://github.com/ben-manes/caffeine/wiki/Efficiency

Re: Analyzing the codebase of Caffeine, a high performance caching library

#52

Post by masklinn »

JanecekPetr wrote: post #51
masklinn wrote: post #16

Earlier quoted context omitted.

Wouldn’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.

That'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 ), see it in action e.g. here: https://github.com/ben-manes/caffeine/wiki/Efficiency

I know that, but I’m not replying to a comment about caffeine, rather the opposite.

Re: Analyzing the codebase of Caffeine, a high performance caching library

#53

Post by zaphirplane »

hinkley wrote: post #44
dan-robertson wrote: post #40

Earlier quoted context omitted.

Interesting. 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.

When 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…

Tell me more What if other values are looked up deep into the call stack, would that cause actual inconsistency as different values were looked up at different times

Re: Analyzing the codebase of Caffeine, a high performance caching library

#54

Post by unification_fan »

urbandw311er wrote: post #43

Caffeine 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.

Actually, Caffeine is the name of a hello world script I wrote back in the 80s, so...

Re: Analyzing the codebase of Caffeine, a high performance caching library

#55

Post by hinkley »

zaphirplane wrote: post #53
hinkley wrote: post #44

Earlier quoted context omitted.

When 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…

Tell me more What if other values are looked up deep into the call stack, would that cause actual inconsistency as different values were looked up at different times

It can but it’s very hard to catch. It’s like running your database at the wrong isolation level. By the time the bug happens it’s under heavy load and the system is too noisy to catch the real problem. So you have glitches nobody can explain and they just deal with cleanup.

For this and other reasons I think that in addition to Functional Core, Imperative Shell, you want a “square” call tree in your code. Avoid functions with no fanout, and functions with high fanout. Rearrange code that uses the same data to happen as close together as you can, to improve local reasoning. When functions get unwieldy, or deleted code makes them too small, use the b-tree algorithm as inspiration to rebalance the tree.

Refactor when new features change the coupling of the code.

Re: Analyzing the codebase of Caffeine, a high performance caching library

#56

Post by NovaX »

masklinn wrote: post #52
JanecekPetr wrote: post #51

Earlier quoted context omitted.

That'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 ), see it in action e.g. here: https://github.com/ben-manes/caffeine/wiki/Efficiency

I know that, but I’m not replying to a comment about caffeine, rather the opposite.

I 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

Post reply on HN