Design of a Modern Cache (2016)
highscalability.com
Design of a Modern Cache (2016)
1–10 of 11 posts
Re: Design of a Modern Cache (2016)
#2Down for me (ERR_TOO_MANY_REDIRECTS), mirror: https://archive.ph/KBK1a
Re: Design of a Modern Cache (2016)
#3The post introducing Ristretto, a similar Go cache is also a great technical read: https://dgraph.io/blog/post/introducing-ristretto-high-perf-...
Re: Design of a Modern Cache (2016)
#4Down for me (ERR_TOO_MANY_REDIRECTS), mirror: https://archive.ph/KBK1a
Probably too much load, should've implemented a modern cache for this page
Re: Design of a Modern Cache (2016)
#5The post introducing Ristretto, a similar Go cache is also a great technical read: https://dgraph.io/blog/post/introducing-ristretto-high-perf-...
It's weird how long it's taken golang to get a serious concurrent cache. It still does not appear that this one allows for time-based eviction (write or last access).
Re: Design of a Modern Cache (2016)
#6Part 2 covers adaptivity and expiration. [1]
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...
Re: Design of a Modern Cache (2016)
#7Is any of this applicable to designing a CPU cache?
Re: Design of a Modern Cache (2016)
#8Down for me (ERR_TOO_MANY_REDIRECTS), mirror: https://archive.ph/KBK1a
It's kinda funny when the website talking about high availability becomes ... not available.
Re: Design of a Modern Cache (2016)
#9The post introducing Ristretto, a similar Go cache is also a great technical read: https://dgraph.io/blog/post/introducing-ristretto-high-perf-...
It's weird how long it's taken golang to get a serious concurrent cache. It still does not appear that this one allows for time-based eviction (write or last access).
Golang's concurrency primitives work against the grain here, as far as the design of high performance caches. Ristretto resorts to using sync.Pool as a sloppy queue mechanism to log gets, which apparently works but is not part of the official semantics, and may prove brittle in the future. It's also just sadly still far off from what's possible using bare metal techniques in c.
I have a design I'm working on that I think may rival or surpass Ristretto, though it also benefits greatly from immutability. The TL;DR is a power of two choices hash table, where each bucket holds a couple cache lines of count-min-sketch approximations similar to TinyLFU, as well as a few value slots, and uses a bucket local counter reset mechanism. It should run very fast due to minimal contention, but the open question is what negative impacts a bucket local reset might have. My response to this is simple and conservative: I'm oversizing the count-min-sketch vectors and counters slightly for some breathing room.
Re: Design of a Modern Cache (2016)
#10Is any of this applicable to designing a CPU cache?
I doubt it.
1. The only thing I know about CPU Caches is associativity, which is implemented with help of tags. Tags can be whatever size the CPU designer desired, 6-bits, 9-bits, 12-bits.
2. There are other physical issues involved: fan-in, fan-out. Basically, the amount of things a wire can support is finite, limited by the amount of electricity later components use. While not the focus of CPU design, physical issues like this are likely still an issue (while they're probably fully abstracted out by the time you reach webpage caches).
3. CPU caches are organized very differently. Cache lines in particular mean that CPUs really access RAM in 64-byte blocks.