Thundering Herds and Promises • Hacker News Board

Re: Thundering Herds and Promises

#31

Post by sbov » Wed, Apr 17, 2019, 10:06 PM UTC

Back when I worked on a similar problem 10 years ago, we solved it by having a quickly expiring memcached key for hitting the database. So if the value wasn't cached, and if that key wasn't there, it would attempt to add that key. If it was added, it would hit the database and cache the result. Otherwise, if that key was there or it didn't successfully add it, it would wait for a short period of time, then re-try the whole process again.

There's other similar problems elsewhere too though. A cold MySQL start is a bitch when you have and rely upon huge amounts of memory for MySQL to service your requests - this is especially noticeable if you have so much traffic you need to cache some results. Back then it would take us about an hour before a freshly spun up MySQL instance could keep up with our regular traffic, even accounting for stuff being cached.

Re: Thundering Herds and Promises

#32

Post by nicwolff » Wed, Apr 17, 2019, 10:22 PM UTC

Instead – and more usefully given how slow some of our backend APIs are – we cache each value twice, under e.g. `key` with a short TTL and `key_backup` with a long TTL.

The first process to miss on `key` renames `key_backup` to `key` (which is atomic and fast on Redis) and goes to the backend for a new value to cache twice and return, while the rest of the herd reads the renamed backup.

Yes, this doubles the total cache size, or equivalently halves the number of keys we have room for. That's a price we're OK with paying to avoid blocking reads while a value is recalculated.

Re: Thundering Herds and Promises

#33

Post by lmeyerov » Wed, Apr 17, 2019, 10:33 PM UTC

mentat wrote: post #29

dragontamer wrote: post #16

Earlier quoted context omitted.

Hmm, the Netflix presentation there seems to make sense superficially though. The key attribute of the "Thundering Herd" problem is the LOOP. The Thundering Herd causes another Thundering Herd... which later causes another Thundering Herd. In the Netflix presentation, the "Thundering Herd" causes all of the requests to time out, which causes two new servers to be added ("automatic scale up"), then everyone tries agai…

Very good point, thanks for clarifying.

System start is indeed a synchronization point, and for limited resources like here, painful and now clpser to the vernacular

Thundering herds can cause escalating and successive failures. That is very much an issue with service start/restart. A bad restart will cause a timeout, another restart, and eventually, restarts on further layers. Imagine all this running above k8s. So yes, this pattern is indeed about one of the failure modes that happen with thundering herds.

Though if your cache needs another cache, that feels like a bad cache. The promise pattern can be done transparently by the cache, coalescing GETs, instead of requiring a user protocol. We do app level caching to stay process-local because latency is fun in GPU land and we are a visual analytics tool... But that is not for the problem shown here.

Re: Thundering Herds and Promises

#34

Post by davinic » Wed, Apr 17, 2019, 10:49 PM UTC

thamer wrote: post #17

In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated reque…

Why block the caller? Subsequent calls will have the same promise returned and notification will happen for all once the promise is resolved.

Re: Thundering Herds and Promises

#35

Post by Johnny555 » Wed, Apr 17, 2019, 11:15 PM UTC

I'm not a developer, but to be honest, thought that's how all non-trivial caching implementations worked -- instead of going directly to the back end or having each one trigger a read from the back end for a cache-miss, all of the threads that want that resource just waited on it to appear in the cache.

Re: Thundering Herds and Promises

#36

Post by [deleted] » Wed, Apr 17, 2019, 11:41 PM UTC

davinic wrote: post #34

thamer wrote: post #17

In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated reque…

Why block the caller? Subsequent calls will have the same promise returned and notification will happen for all once the promise is resolved.

[deleted]

Re: Thundering Herds and Promises

#37

Post by NovaX » Thu, Apr 18, 2019, 2:15 AM UTC

thamer wrote: post #17

In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated reque…

Guava cache's successor, Caffeine [1], handles the asynchronous case. In your scenario, you could set a timeout on the future as the entry will be discarded if the future results in an error.

[1] https://github.com/ben-manes/caffeine/wiki/Population

Re: Thundering Herds and Promises

#38

Post by vhost- » Thu, Apr 18, 2019, 2:26 AM UTC

davinic wrote: post #34

thamer wrote: post #17

In practice there's a bit more to it than what the article describes, especially for a distributed cache: you need to have the Promise auto-expire so that if the machine that's performing the backend read disappears the other readers don't stay stuck forever waiting for it. It's also useful to have a feature in the cache itself that blocks the caller until the Promise has been fulfilled, so as to avoid repeated reque…

Why block the caller? Subsequent calls will have the same promise returned and notification will happen for all once the promise is resolved.

Because then your caller will need to implement something that understands what a promise is instead of just getting a data object it already has to understand. Not only this, but the caller will need to also implement a polling mechanism to keep trying. Put into code:

  func get_value(key):
    value = backend.get(key)
    return value

Is way better than something along these lines:

  func get_value(key):
    while true:
      response = backend.get(key)
      if response.type == "promise":
        sleep duration
        continue
      return response.value

If your service looks like the former, then suddenly your unit tests can use a postgres database, a sqlite database, a rest client... that all implement the same backend.get(key) interface.

Re: Thundering Herds and Promises

#39

Post by horsawlarway » Thu, Apr 18, 2019, 2:43 AM UTC

nicwolff wrote: post #32

Instead – and more usefully given how slow some of our backend APIs are – we cache each value twice, under e.g. `key` with a short TTL and `key_backup` with a long TTL. The first process to miss on `key` renames `key_backup` to `key` (which is atomic and fast on Redis) and goes to the backend for a new value to cache twice and return, while the rest of the herd reads the renamed backup. Yes, this doubles the total ca…

How does this solve your cold start?

What happens if I have a new request come in for which I have no key OR key_backup?

Re: Thundering Herds and Promises

#40

Post by sk5t » Thu, Apr 18, 2019, 4:38 AM UTC

sciurus wrote: post #10

This is how many HTTP caches and CDNs work. The terminology used to describe it is often request collapsing or request coalescing. Some examples: * varnish: https://info.varnish-software.com/blog/hit-for-pass-varnish-... * nginx: http://nginx.org/en/docs/http/ngx_http_proxy_module.html#pro... * fastly: https://docs.fastly.com/guides/performance-tuning/request-co... * cloudfront: https://docs.aws.amazon.com/AmazonClou…

Plain-old-caches and even concurrent-aware maps do this too--several are the cases where I've slapped a Guava or Caffeine cache into place for quick 'n dirty concurrency control and key coalescing, even with a short TTL.