Design of a Modern Cache (2016) | Hacker News Reader

Design of a Modern Cache (2016)

highscalability.com

74 pointscaldito10 comments

Open articleView on HN

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

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

Down for me (ERR_TOO_MANY_REDIRECTS), mirror: https://archive.ph/KBK1a

Probably too much load, should've implemented a modern cache for this page

It's kinda funny when the website talking about high availability becomes ... not available.

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

The CHERI project have some bug trackers on designing real CPU caches.

Or implementing, perhaps. The design is almost simple but getting everything right is very hard.

Reply on news.ycombinator.com