5 ms·

I'm not very familiar with go but one thing I don't understand is why the caches need to be distributed. I wonder, why not just have one cache per thread?

jitl 8y ago
That requires N times more memory, where N is the number of threads. 32x more memory??
- northwindfoo 8y ago
  Right, fair enough. I only thought of that after I posted. Not used to thinking that memory is limited lol The author did indicate that they had problems with oom and memory eviction so it probably is a memory limited use case.
- Twirrim 8y ago
  Given the Zipf distribution, I wonder if just a small LRU cache per thread might not be a terrible thing? Juggling caches on databases is a challenging thing, and there has been some back-and-forth on best practices. MySQL for the longest time shipped with a query cache. As of MySQL 5.7.20 it was deprecated, and has now been removed in MySQL 8, largely because it was as likely to hurt you badly as help you, particularly with correctly sized InnoDB buffering.
  - NovaX 8y ago
    Zipf is a little idealistic. It is perfect for a quick analysis as the base case that a cache should excel at. Unfortunately LRU doesn't because it can be easily polluted. (examples: https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency) A database will often scan many records which would flush an LRU. Postgres uses small LRU buffer caches in your per-thread model, backed by a larger LRU-like cache. The buffer caches are easily flushed by scans, but protect the shared cache from this noise. That shared cache could probably benefit from a smarter policy and this is an on going topic.
- andonisus 8y ago
  This is assuming that all threads need a global view of the data. When this is not the case, it is sufficient to have many async goroutines ingest on a channel and fill their own local map, lock-free. This is our general strategy for high-performance streaming routines.
tpetry 8y ago
Cache invalidation is pretty hard if you need to clear data from local caches for every thread.
scottlamb 8y ago
You're probably imagining an async, thread-per-core model. One cache per thread might be reasonable then (although having more, smaller caches decreases hit rate, so might fail their requirement #5). Go programs are written in a synchronous, thread-per-request model. You'd end up with _tons_ of small, very cold caches and a miserable hit rate. You could approximate the former in Go by just having an array of N caches and picking from them randomly. This is similar to their "lock striping" with less contention (no stripe is a hot spot) but a lower hit rate.
- jadbox 8y ago
  This was wonderfully simple and concise. Thank you.

jitl 8y ago

That requires N times more memory, where N is the number of threads. 32x more memory??

northwindfoo 8y ago
Right, fair enough. I only thought of that after I posted. Not used to thinking that memory is limited lol The author did indicate that they had problems with oom and memory eviction so it probably is a memory limited use case.
Twirrim 8y ago
Given the Zipf distribution, I wonder if just a small LRU cache per thread might not be a terrible thing? Juggling caches on databases is a challenging thing, and there has been some back-and-forth on best practices. MySQL for the longest time shipped with a query cache. As of MySQL 5.7.20 it was deprecated, and has now been removed in MySQL 8, largely because it was as likely to hurt you badly as help you, particularly with correctly sized InnoDB buffering.
- NovaX 8y ago
  Zipf is a little idealistic. It is perfect for a quick analysis as the base case that a cache should excel at. Unfortunately LRU doesn't because it can be easily polluted. (examples: https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/ben-manes/caffeine/wiki/Efficiency) A database will often scan many records which would flush an LRU. Postgres uses small LRU buffer caches in your per-thread model, backed by a larger LRU-like cache. The buffer caches are easily flushed by scans, but protect the shared cache from this noise. That shared cache could probably benefit from a smarter policy and this is an on going topic.
andonisus 8y ago
This is assuming that all threads need a global view of the data. When this is not the case, it is sufficient to have many async goroutines ingest on a channel and fill their own local map, lock-free. This is our general strategy for high-performance streaming routines.

tpetry 8y ago

Cache invalidation is pretty hard if you need to clear data from local caches for every thread.

scottlamb 8y ago

You're probably imagining an async, thread-per-core model. One cache per thread might be reasonable then (although having more, smaller caches decreases hit rate, so might fail their requirement #5). Go programs are written in a synchronous, thread-per-request model. You'd end up with _tons_ of small, very cold caches and a miserable hit rate. You could approximate the former in Go by just having an array of N caches and picking from them randomly. This is similar to their "lock striping" with less contention (no stripe is a hot spot) but a lower hit rate.

jadbox 8y ago
This was wonderfully simple and concise. Thank you.