Hacker News Reader

Comment by taeric | Hacker News Reader

Using a cache as an example feels off. I mean, yes. To a large degree, machine learning is fancy statistics done by the computer. And, to a large degree, caching is keeping the data that is statistically most likely to be accessed again.

However, my understanding is the classic algorithms for caching have yet to lose to the new machine learning ones. Has that changed?

View on HN

Classic caching algorithms like LRU use only last access time as a feature. You are correct that ML based on only that one feature won’t be much different than LRU. However, most of the time, data items have metadata that can be used as features, for example, image size and type. With this additional metadata ML algorithms can do a lot better than LRU that is only using access patterns. Also, think about how image content (sports car, an attractive person, etc) could predict if this image it likely to be accessed in the future.

I think some caching algorithms are a bit smarter than just LRU. Though, that is typically as much in having multiple caches as it is anything else.

More importantly, I know this is claimed a lot. But I thought the last few explorations of the idea I saw did not actually see fancier algorithms win. Indeed, the best strategy from my memory was random spreading of the data with an almost random replacement strategy. I think some of the win there was just the low overhead of the bookkeeping, but it was still one of the better bets.

(This is all off the table, of course, if you know what the access pattern will be. Then, by all means, set things up accordingly.)

To add to Vlad's comment above: The major win was in being able to create a simple API which inherently computes update -> cache invalidation probability taking into account the semantics of the item being cached and its relevance to the query. To be able to do this explicitly via heuristics leads to bespoke effort for each new and modified query.

With Spiral, we were able to approach this top down as a classification problem.

e.g.

If you have a cached query for "Friends that liked my post", the Spiral classifier quickly learns that "Post Last Viewed At" or "Post Last Modified At" is not relevant to this via the feedback from the caching code.

Pre-spiral, this was expressed via a curated blacklist/whitelist which had to be recreated if the query characteristics changed.

I think this makes sense. My mental model would have been viewing this as a sharding style concern. Where different sized and topic items would be to effectively different caches. With hit rates determining the size of each cache.

That said, I think I see where I was mistaken in thinking that was an odd example. It was literally the example. Not just a random pedagogical one.

To that end, thanks for sharing! Cool stuff.

Reply on news.ycombinator.com