Staying Out of TTL Hell | Hacker News Reader

Staying Out of TTL Hell

calpaterson.com

134 pointstodsacerdoti48 comments

Another common problem in caching is the "thundering herd". You have a bit of data that is expensive to compute, very frequently requested, and fine to be a little bit stale.

The naive approach is to follow the normal pattern: use the cached version of it's there, and otherwise compute and stick it in the cache with a TTL. The problem arises when you have a fleet of web nodes going at full bore, and the cache expires. If the data takes 10 seconds to compute, then for the whole next 10 seconds, every new request will find the data missing from the cache since it has expired and not yet been replaced, and so each of those requests will take on the expensive and redundant work of repopulating that data.

It can be a performance blip at best, or a total disaster at worst, causing cascading failures and downtime.

One relatively easy solution here is to just have a separate worker process that runs in an interval and preemptively freshens the data in the cache. In this case you can set with no TTL, and web front ends just use whatever they find. You also need to deal gracefully with the rare case where they may find nothing, like in the case of a cold cache boot.

It can also quite easily be solved by using something like nginx's proxy_cache_background_update and/or proxy_cache_lock, depending on wether it's permissible to send stale responses.

Then you could have the cache serve stale content until it's updated, and/or only allow one upstream connection to refresh the cache.

But yeah, unless you allow stale responses or refresh the cache periodically as you suggest, you would still have requests which takes 10 second to complete, but you would at least not crush the upstream service.

This is done in the DNS world too. The unbound[1] resolver can pre-fetch a new record half way through the TTL if enough clients have requested it.

That guarantees that the cache remains hot for records that clients are requesting, but lets unused records expire.

1: https://nlnetlabs.nl/projects/unbound/about/

This runs afoul of the article’s warning to “ Never require a cache hit”

  It's important never to 
  require a cache hit - even
  as a soft requirement.
  Evictions can happen at
  inconvenient times - such
  as when some other part of
  the system is under load - 
  and there mustn't be any
  negative consequences to a
  cache miss

If the cache does empty unexpectedly and that is going to cause your infrastructure to die in a cascade, probably some kind of fallback will be needed.

If you have a result that takes 10 seconds to calculate, and you need to read it faster than that, so you make a background processes to calculate it and keep it updated somewhere, you could argue that it's no longer caching.

It's an asynchronous read model or a projection and it's now just part of your application.

I find that when I'm in a dead-end conversation with people about caching that often they can't accept that pre-calculation and caching are two different concepts, and you conflate them at our peril.

For instance if I look up a value and pass it to three pure functions to ask about it, versus having the 3 functions look up the value and try to share a cache entry.

This is doubly wrong because the final question may see a cache eviction and answer a different question due to changes in the data. Now I may have a situation where True:False:True was not a corner case we cover because it's logically impossible, but it's happening in the code because the last one changed from False to True due to concurrent read and write.

The latter is also harder to test, because it requires mocks instead of manufactured inputs. And at this point the code is using the cache as global, mutable state, instead of semi-local state. Three strikes, you're out.

If the computation of the data takes 10sec and your hammered with request, you should def require a cache hit and return a 500 if there is no cache and do not go the DB or somebackup mechanism.

Caches in web architectures seem to be similar to NUMA style addressing and makes me think that cache invalidations in web should have failovers to an L2 or L3 if the L1 is gone differentiating between an expected invalidation or an unexpected invalidation (Redis down, let’s say). Sometimes in an emergency (security incident, let’s say) all cache items should be invalidated though resulting in said 500 or temporarily unavailable response while the cache is repopulated again and that’s something else that Djikstra would shake his fist angrily at from beyond the grave just the same.

I'd argue in that case, the cache is more of a local read-only DB replica :)

It's a subtle word change, but can communicate the slightly difference architecture and break the reader away from an assumption.

Yeah, I've had a similar thought to that before... as you scale up, the whole "cache" thing is just not a service you can have, because a cache must only speed up the thing being cached, it should ideally have no other visible impacts. As a site scales up and becomes dependent on a cache, it is really not a "cache" anymore, and both terminology and mindset should change as a result.

If your site comes crashing down because the cache went down, it's not a cache anymore and you should use a different mindset in approaching it.

The answer varies depending on a whole lot of relevant numbers that can vary widely, but an example of an answer I have in one of my systems is that I store all the cache queries more persistently than the cache answers. This particular system gets hammered with requests that are mostly the same as last time at certain times but spends a lot of time idle. The numbers work out that if I'm trying to compute the cache during one of my crunches, I need a huge amount of resources for just a couple of minutes, but if I restart the service between these crunches, there's plenty of time to recompute the entire cache before it is necessary with no additional resources. But that's just one particular example of not really being a "cache" anymore suitable in my very particular case.

Varnish has a keep time that allows you to hold a 'dead' object for ttl+X for exactly this reason. You server it for so many seconds whilst under load while a single origin request goes and grabs the data. It's a really solid way to shed load and avoid dropping so many connections at once and then getting slammed on retry.

I once had this situation at an old job, and I ended up working around it by putting a lock around the re-computation: all requests had to wait for the 5-ish seconds while the cache was being refreshed.

In this case, per-request latency wasn't as important as total throughput of the system over time. And the individual requests were small, so building up a queue of unhandled requests wasn't a problem.

I have no idea if this is considered a "good" solution, but it worked well enough for me at the time.

It's a pool, not a cache per se, but the Hikari database connection pool subtracts up to a random amount up to a few percent from each connection's lifetime to avoid a similar problem. If you have a 30 minute lifetime, you spread the expirations (and recreations) over half a minute or so.

Another probabilistic approach is to have an increasing probability of an artificial cache miss as the TTL approaches zero. This forces some unlucky client to refresh it for everybody, avoiding the thundering herd.

We used that technique in Google's DNS cache to fix what had been a monumental herd effect every 30 seconds when the RRs for outlook-com.olc.protection.outlook.com expired.

As the TTL shrinks to a smaller multiple of the time needed to generate the response, this problem becomes magnified.

A two second response with a 10 second TTL could see 20% of the queries all trying to refresh the same cache at once. With a single server you can use promise caching to dedupe such things, with a cluster that's more difficult to avoid.

Background processes are good for spiky traffic, and with reddit and HN around some of us at least have been trained that some information on a page is purely advisory. Do I have 22 upvotes or 28? Give it a couple minutes and try again.

But what that work does is make you look at what the cost is of certain information, and some people are not comfortable with that. With caching you can delude yourself that you're getting a bargain on all of this information overload, even though the worst case scenarios and statistical clumping say you're off your gourd.

Squid had a collapsed forwarding option that can help with the thundering herd. If multiple clients request the same uncached url, it can wait for the first origin request to finish and serve the response to all clients (if cachable). Of course, that backfires if the response was uncachable; so careful configuration is required.

Also works well to combine that with stale-while-revalidate. Yahoo had some squid patches with nifty ways to have a response invalidate other cached urls, but I don't think those made it to the outside world (at least I can't find them now).

> Another common problem in caching is the "thundering herd".

> you have a fleet of web nodes going at full bore, and the cache expires. If the data takes 10 seconds to compute, then for the whole next 10 seconds, every new request will find the data missing from the cache since it has expired and not yet been replaced, and so each of those requests will take on the expensive and redundant work of repopulating that data.

Wait, is the problem that as soon as the cache entry expires everyone requests the new data all at once, overwhelming the backend ("thundering herd"), or is it that requests follow whatever the normal pattern is but the backend doesn't know how to queue them?

TTL will always be Transistor Transistor Logic to me.

That binding has an infinite time to live in my mind.

Same here. I clicked on the link fully expecting a discussion about the transition from TTL to CMOS, or something like that.

Same here. I thought this was going to be how you should be using CMOS instead of TTL to avoid overheating.

Likewise - I thought it might be about how much harder it's getting to source through-hole TTL logic for vintage computer repairs and new hobby builds.

I have just ordered 40 x 74F260 from Poland (I'm in the UK)...for less than some of the people on *bay are charging for 5.

> The simplest strategy is to just never invalidate. Some data doesn't go bad. The contents of CSV upload #42345 won't change. Neither will the HTML conversion of some markdown-formatted product data.

Thats a dangerous assumption to make and while simple at the cache's end might need complicated logic at the frontend. There will always be that use case of a customer that needs the file changed or removed. So instead of invalidating you now need a system to manage references to versioned cached objects.

You can just overwrite the cache with new information when the user replaces a file.

That's update on write, not never invalidate.

You can't, because you design to never invalidate, there is no way to ensure if and when this change is propagated through your entire cache layer (and local caches like browsers). And thus guarantee to the client the change has been made.

I'm not saying it's a bad idea. But often a seemingly simple solution to a complex problem doesn't take the entire complexity of the problem into account. Which is fine if you can consciously make that tradeoff but more often than not will turn into a footgun eventually.

Yes. One danger of infrequently-invalidated or never-invalidated data is that it can turn into a ticking time bomb.

For example you may introduce a bug in the code path for calculating the fresh value that causes an error.

That code may not execute for months and months since the cache is warm and up and running. Until one day it is restarted and you find out the problems it was masking.

Pro tip: don't get greedy with cache TTL, define and enforce a low value that you can tolerate. In many use cases you can easily afford to re-compute once per 5 or 10 or 30 minutes.

We've given up on this whole idea and basically gone for extremely long TTLs (30 days) on our caching layer. We then built the tooling to dump caches after deploys and manually on request. You can dump caches at the application layer, or even down to the specific request param combination layer. It's worth investing a bit into systems.

I have seen systems that use caching so heavily that when the cache is invalidated en masse, they need to bring up extra compute resources to fill it again, because the system under normal load with an empty cache needs so many more resources. Basically the system can no longer function adequately with a cold cache. This is of course a pain to orchestrate.

I suppose regularly clearing out the cache is a way to be sure you aren't in that situation, or at least know it when you become so.

My experience with those systems is one reason that I'm reluctant to take the position of resorting to caching before trying to optimize the underlying code. It makes me want to treat caching as a last resort when I can't feasibly (whether due to time or skill or actual external limits) optimize any further, which is I think a bit different than the attitude OP is suggesting.

The maintenance "cost" of adding a cache layer is in my experience higher than the OP suggests. Failure-to-invalidate/stale cache bugs can be very easy to make and difficult to debug and solve when using a strategy that depends upon invalidation, like 2 and 3 in the OP.

In many cases, such as the CSV one, I think the answer is converting the article's Strategy 1 to the article's Strategy 4 -- cache under a key that has a digest hash of the content in it, so when the content changes, the cache key changes.

If the requestor only knows the filename, now you have to cache the filename to hash lookup.

Then you've just moved the invalidation problem around.

This is a great strategy if the object is controlled by a build process, so your client code already knows what the hash is.

> Now you have to cache the filename to hash lookup.

The OP's "Strategy 4" is basically exactly that, although they describe it a bit confusingly as "namespacing" assuming a sort of hieararchy that we don't have here, without realizing it's more general purpose.

The OP acknowledges that in Strategy 4 "Each logical cache lookup now requires two real lookups - first for the namespace key [in our example lookup the filename to get the digest] and then for the actual key [use the digest to look up the actual content]"

I have more commonly used it when you can have the digest at the ready though, when you can make the requester aware of the digest. The "build time" doesn't necessarily have to be the software build time; I have sometimes put the digest in the database (which the requester has access to, and where it's cheaper to access then the entire content would be), which can then be used to fetch the content from the "cache". I guess this really is two cache lookups across two cache products, considering the database as a cache in that case, but sometimes the database fetch is going to happen naturally anyway.

If every file upload creates a new upload number (which is a common design) and the upload numbers are not exposed to the client then changes and deletions work without any special effort. I guess this is the case the author is talking about.

I'm probably misunderstanding something here, but it seems like this whole article ignores race conditions. For instance, if you 'update on write', how do guarantee that the cache writes don't occur in the wrong order?

e.g. write B write A update cache with A update cache with B

You're just replicated all the usual single machine multi-threading issues when you abandon the ACID happy place by adding a cache...

EDIT: and this is why I would use TTLs even with update on write, folks. And this is why I mostly happily use volatile-lru on multi-purpose redis caches, since everything I'd want to evict has a TTL.

I don't disagree this is a problem but it is so general that it applies everywhere you use multiple backing services.

A classic is sending an email: do you send the notification email before or after committing to the database? If you send after you run the risk of committing to the database and then failing to send the notification email. If you send before you might send the email and then fail to commit.

I would love to have cross database/mailserver/cache/etc transactions but it's implemented nowhere as far as I can see, thought there seems to have been work towards it to the 90s I think they ultimately gave up.

If you agree it's a problem, it'd be great if you'd at least add this onto the tips and pitfalls section. The main claim of the article is get rid of TTLs and "don't give up correctness to gain speed", which seems incorrect to me.

One of the main reasons that TTLs are good is exactly this; if you remove TTLs as you advise, strategy 2 and 3 can have permanently wrong data in the cache, right? This is ... not good?

EDIT: I don't think the email one is a good comparison, either. (a) you have to do this (it's not an optional bonus, as the cache is), and (b) it's perfectly reasonable for critical emails to record in the db whether it's successful or report it elsewhere - you can have multiple states!

If we're just talking notifications in general, I would prefer sending them after commit (i.e. don't tell people until we're sure the action has happened, and wear the possible not telling), though depending on your priorities you may switch it. But I think of this as an external action, NOT something where you're messing with your system's version of the truth.

Fair dos - I will try to add it when I get some time later today.

The email thing is just an example, you might have a preference on how to handle that particular case but hopefully you can recognise the principle I'm getting at.

I don't necessarily agree that this problem is a cache specific issue and I definitely wouldn't start putting random TTLs on things in an attempt to try to hack around it. If anything, that is likely only to make the issue even more baffling for the user if it does occur. And of course you are now back to TTL numberism - how long a TTL should you set? If it really is a realistic concern (and I would suggest it's not for most!) then time to look at having locks somewhere.

Thanks very much for thinking about adding this little caveat - part of the reason I'm keen is that this really is a good list of 'things to think about' re caching, and I'd like to add this one to the pile.

With the TTL advice, why do you think this would make it _more_ baffling for the user? If the choices are 'it's wrong "forever"' or 'it's wrong for 5 minutes', isn't the latter the better one? I'd have to have a compelling reason to cache indefinitely if I knew it might be wrong... admittedly, if there are a lot of writes (where we're most likely to mess the cache up) you're likely to get a new cached value quickly.

In terms of whether this issue is cache specific, I honestly think it is _in this context_ because of the way you've phrased the article: that you can add an external cache to your db accesses and everything is faster without any cost in correctness. It's almost better to think of it as 'I'm adding an entirely new kind of database', and realise that keeping those databases reliably in sync is non-trivial without relaxing your guarantees.

A bunch of databases support XA transactions [1], or otherwise have generic support for 2PC that can be hooked up to an external transaction manager [2].

In theory, we could build support into most systems. It does seem like this idea has lost momentum, though. I am not sure why.

[1] https://en.wikipedia.org/wiki/X/Open_XA

[2] for example, https://www.postgresql.org/docs/13/sql-prepare-transaction.h...

Two-phase commit is out of style because everything is distributed and the Fallacies of Distributed Systems presents several reasons why the 2PC protocols spend most of their effort on error handling and recovery.

Simply put, at scale, something is always failing, so a 2PC setup is always doing recovery.

You write to the database, and have a separate notification-sender that feeds on the database change stream, sends out notifications, and keeps track of which notifications it has sent. If that process crashes, it will re-send one or maybe a few notifications.

I was thinking about how this relates to write-through and write-back in hardware caches, there's an interesting inversion.

In a CPU, the cache is there between the CPU proper, and the RAM.

In a write-through CPU, the RAM is the single record of truth, and the cache exists only to speed up reads of those addresses which are currently cached.

In a write-back CPU there is no single record of truth, it has to be pieced together from the RAM in combination with the cache.

In this Memcache set-up though, the database is the complete record of truth, and the cache is is only ever updated after the database write operation has completed, despite that the Memcache cache is faster than the database.

It seems unlikely a CPU would ever update the RAM without touching the cache, but the equivalent is a possibility here.

It's sad the difference between expiry and eviction isn't explored more fully. There are plenty of posts describing cache eviction strategies that barely touch on expiry issues, and a handful of posts about cache expiry that barely touch on eviction.

Regarding the decorators, there's a reason it's popular: it saves boilerplate. The good news is that it's python, so you can do something like this:

  from pyappcache import RedisCache

  @RedisCache
  def get_slow_thing_v3(thing_id):
      thing = get_slow_thing_from_a_database_layer()
      return thing

  def update_something_slow(thing_id, new_thing):
      get_slow_thing_v3.set_cache(thing_id, new_thing)
      set_thing_in_a_database_layer(new_thing)

One of the examples on invalidating cache on write has the following code, which is buggy. If the DB call fails, then cache cache would have data that was never actually committed. Cache coherency is hard.

  def update_something_slow(thing_id, new_thing):
    my_cache.set_by_str(thing_id, new_thing)
    set_thing_in_a_database_layer(new_thing)

I was hoping this would be about DNS, as I never know what a “good” value for those TTLs are but I’ve read in HN that high is better somewhere and handle changes some other way. I would be interested to learn more about strategies for that.

That could probably go into a whole separate article. But...

The first rule of DNS TTLs is expect some things to not respect them.

If you are changing your records frequently or urgently, set ttl somewhere between 1 minute and 5 minutes. Maybe 15 seconds if it's really a lot, but don't go below that cause things get weird.

Other than that, most things should probably be between an hour to four hours.

If you're paying per query, make ttls longer to reduce your costs. Don't make ttls longer than one or two days.

Also, don't make long chains of cnames and what not, and don't let your responses grow beyond 512 bytes (cause it won't work on some networks), allowing for NAT64 turning your A records into AAAA records. IIRC that means don't return more than 8 A records, but your mileage may vary.

One strategy is to use DNS server software that handles changes for you. Set a time-to-die, and the software will publish a counting down TTL that is the number of seconds left until the time-to-die. Set a start time, and the software won't publish the record until that time has been reached. Have two records with each, and one has a pre-programmed switch over from one thing to another.

* http://jdebp.uk./Softwares/djbwares/guide/commands/tinydns-d...

@author: Small correction:

> One ~people~ reason people don't consider this strategy is that they wrongly worry that the cache will "fill up".

Thanks for the correction. I'm sorry you were downvoted!

Reply on news.ycombinator.com