5 ms·

How key-based cache expiration works

212 points by Thibaut 15y ago

whichdan 15y ago
How do they pull the memcached key with the latest timestamp? Is there a memcached equivalent of "SELECT value FROM memcached WHERE key LIKE 'prefix%' ORDER BY key DESC LIMIT 1;"?
- dhh 15y ago
  See step 6. The view is pulling the cache key straight from the domain model. It relies on being the informed as well about changes in its children to do that, which is what the setup in step 5 is about.
  - Loic 15y ago
    Do am I wrong or you still hit the DB for each model object? But of course you save all the complex rendering (possibly SELECT for children) from the key, right?
    - ludwigvan 15y ago
      Not necessarily I believe, that one can be cached and invalidated manually.
    - dhh 15y ago
      You hit the DB for the top-level. So in step 6, we'll always hit the db for the latest project, but we will not hit the db for the todolists or the todos of those todolists if the project cache is fresh. So you save the render plus any db calls that would be triggered as part of that render.
      - hasenj 15y ago
        So simple yet so brilliant! I can't believe I didn't think of this before. My initial reaction after I skimmed the post was "uhh, so you still hit the db? what's the point?" Thanks for sharing this! I definitely want to implement something similar for my future projects!
tomstuart 15y ago
It's good to see this written up somewhere. The technique is widely known in the Rails community but I haven't seen it explained in one place. (For example, the Rails API documentation and guides don't even mention that the cache helper can take an Active Record instance as the key, so you'd be hard pressed to discover this technique without reading the Action Pack source.) As DHH says, the upside is that it's simple and, as long as you get the cascading updates right, makes sure you don't ever show stale content. There are a couple of downsides. Firstly, once a fragment becomes invalid, it's not regenerated until the next request that needs it, so someone somewhere gets a slow[er] page load; even worse, if yours is a large public site with lots of long-tail pages, that "someone" is likely to be the Googlebot, and the slower page times might adversely affect your search ranking. You could ameliorate this by having some kind of automated process for periodically pre-warming certain parts of the cache after certain kinds of update, but that can get difficult to maintain. Secondly, this technique is very conservative: the goal is to invalidate all fragments which might have been affected by an update, rather than only the fragments which actually have been. (It's less brute-force than the even simpler "invalidate the entire cache every time any record is updated" strategy, but it's making a similar trade-off.) This works well for an application like Basecamp where the hierarchical presentation of the data matches its hierarchical organisation at the model level, but is more problematic in applications with lots of different ways of presenting the same underlying data; if you have lots of cached representations of projects which don't actually include any information about the child todo lists or todos, then tough shit, those are all going to be invalidated when a single todo is updated, and you'll have to spend (page load) time waiting for them to be regenerated. In principle you can get around this by having multiple timestamps per model to represent different kinds of update, but again that's more difficult to manage correctly over time. An interesting alternative approach is James Coglan's experimental Primer (https://github.com/jcoglan/primer https://github.com/jcoglan/primer), which dynamically tracks which Active Record instances & attributes are used during the generation of a cached fragment, and then actively invalidates that cache when any of those attributes change. The downside to Primer is that it's more complex, not production-ready, and may contain traces of magic.
- yxhuvud 15y ago
  Best writeup on the topic of caching in rails that I've seen is http://broadcastingadam.com/2011/05/advanced_caching_in_rails http://broadcastingadam.com/2011/05/advanced_caching_in_rail...
bobobjorn 15y ago
I assume this has the effect that memcached is always full. How do you know when the hot cache is starting to fill memcached? Ie, how do you know when your cache memory is closing up to beeing to small?
- ars 15y ago
  You probably calculate the ratio of hot requests vs cold ones. Or in other words, the cache miss ratio.
  - bobobjorn 15y ago
    But that wont show anything until it most likely already is to late. You dont realy want that value to ever go down, then you already have customers with a worse experience, and when that starts, it goes very fast down the hill.
DodgyEggplant 15y ago
It sounds really impressive, smart, innovative UI and underlying architecture. 37 signals did it again! What is the minimum requirements of a team, programmers/skills/time, to get into such a project and actually deliver?
- DodgyEggplant 15y ago
  Why the downvote? It looks like a very promising attitude, but one has to consider if this added complexity is feasible for a smaller or less experienced shop. The input is important.
  - nkohari 15y ago
    My guess is that the parent is getting downvoted because it's so dense with hero worship that it turns my stomach.
  - randomdata 15y ago
    Perhaps because the caching methodology in the article has been advocated to Rails developers for several years now? It was a good refresher for those who have forgotten or are new to Rails (or web development in general), but to call it innovative is going a little far.
StavrosK 15y ago
I was thinking the other day, wouldn't it be easyish and optimal to specify/calculate all the data that is used to generate a fragment, store the information in a tree, and invalidate the parents when a node changes. This would only invalidate data that needs to be invalidated, and it doesn't sound too hard to implement... Does it exist anywhere? What are downsides I haven't thought of?
- qwerki 15y ago
  not being an expert in this field, one hazard that comes to mind is that a key look up could turn into a tree traversal problem, which defeats the purpose of having a cache in the first place..
mattgreenrocks 15y ago
Is there a way to pull this off when the fragments in question are JSON?
- dhh 15y ago
  If you use something like jbuilder to build your JSON, then this exact same technique will work just as well.
Sujan 15y ago
Sounds... different than the caching I knew before. Problem is, I don't know Rails at all. Can anyone explaing this in non-rails speech for me? (Links are fine, of course)
- asmala 15y ago
  The general gist of it is that you store HTML snippets (e.g. a todo, a list containing, or a project containing lists) in some quick storage medium (in this case Memcached). Each snippet is stored under and accessed by a key that uniquely identifies the version saved (object type + ID + update timestamp). When a new version is cached, the old version stays in the cache, unused, until it is eventially dropped out by Memcached. Now all you need to do is to ensure that whenever an object or its children change, you update their timestamp (the "touch" part), and if you make a changes to the code, you increment the version key for said cache piece. This way new requests will not hit old cached content.
  - Sujan 15y ago
    Ok, so the first interesting part is that instead of caching the result of a database request we cache the complete rendered result. And the bigger rendered parts are just constructed by combining the smaller (also cached) parts, right? How does the application learn which version an element is at right now? Don't you have to call the database to find out?
    - asmala 15y ago
      Correct on all accounts. You will still need to query the database at least for the parent object being rendered. The time saved is shaved off from the rendering time.
    - getsat 15y ago
      If you're rendering an object, you've likely already fetched it from the DB. Rails models (by default) will have a created_at and updated_at datetime columns that are automatically set and updated for you, and you can use them for exactly what is shown in the article.
tszming 15y ago
I haven't heard people talk about this for a long time.. http://code.google.com/p/memcached/wiki/NewProgrammingTricks#Namespacing http://code.google.com/p/memcached/wiki/NewProgrammingTricks... Anyway, if you use this method, you would expect to have long key, so base64 or binary protocol would be useful.
alexgartrell 15y ago
I work on memcache at Facebook, and cache invalidation is a hard, hard problem. It's easy to think that we just overlooked this trivial fix, but the reality is that this just doesn't solve all possible cache consistency problems. Namely, how do you deal with racing writes where the clocks are skewed? How do you deal with multiple copies of the same data in different caches (different data centers, for example). What about axe-murdering your top level db because that data is inherently uncacheable using this scheme? I'm not trying to hate on the post at all, I think it's awesome that product people are thinking about this problem, and the more of them that do the better the world is going to be for guys like me. I just want them to continue to think hard about it :)
- mkramlich 15y ago
  good points. but to be fair most problems become hard, hard problems when your site operates at large, large scale. for small traffic sites, caching architecture is easy and most of the subtle vulnerabilities don't manifest. background: i've been a senior staff engineer at Orbitz and i did a lot of work on the caches at Cheaptickets.com
tomfakes 15y ago
I read the initial post about this on Friday morning and spend the rest of the day adding this caching scheme to my almost finished Rails app. In addition, I added the pjax system to my app. In less than 1 day of work, my app feels significantly more responsive to user commands.

212 points by Thibaut 15y ago

How do they pull the memcached key with the latest timestamp? Is there a memcached equivalent of "SELECT value FROM memcached WHERE key LIKE 'prefix%' ORDER BY key DESC LIMIT 1;"?

dhh 15y ago
See step 6. The view is pulling the cache key straight from the domain model. It relies on being the informed as well about changes in its children to do that, which is what the setup in step 5 is about.
- Loic 15y ago
  Do am I wrong or you still hit the DB for each model object? But of course you save all the complex rendering (possibly SELECT for children) from the key, right?
  - ludwigvan 15y ago
    Not necessarily I believe, that one can be cached and invalidated manually.
  - dhh 15y ago
    You hit the DB for the top-level. So in step 6, we'll always hit the db for the latest project, but we will not hit the db for the todolists or the todos of those todolists if the project cache is fresh. So you save the render plus any db calls that would be triggered as part of that render.
    - hasenj 15y ago
      So simple yet so brilliant! I can't believe I didn't think of this before. My initial reaction after I skimmed the post was "uhh, so you still hit the db? what's the point?" Thanks for sharing this! I definitely want to implement something similar for my future projects!

tomstuart 15y ago

It's good to see this written up somewhere. The technique is widely known in the Rails community but I haven't seen it explained in one place. (For example, the Rails API documentation and guides don't even mention that the cache helper can take an Active Record instance as the key, so you'd be hard pressed to discover this technique without reading the Action Pack source.) As DHH says, the upside is that it's simple and, as long as you get the cascading updates right, makes sure you don't ever show stale content. There are a couple of downsides. Firstly, once a fragment becomes invalid, it's not regenerated until the next request that needs it, so someone somewhere gets a slow[er] page load; even worse, if yours is a large public site with lots of long-tail pages, that "someone" is likely to be the Googlebot, and the slower page times might adversely affect your search ranking. You could ameliorate this by having some kind of automated process for periodically pre-warming certain parts of the cache after certain kinds of update, but that can get difficult to maintain. Secondly, this technique is very conservative: the goal is to invalidate all fragments which might have been affected by an update, rather than only the fragments which actually have been. (It's less brute-force than the even simpler "invalidate the entire cache every time any record is updated" strategy, but it's making a similar trade-off.) This works well for an application like Basecamp where the hierarchical presentation of the data matches its hierarchical organisation at the model level, but is more problematic in applications with lots of different ways of presenting the same underlying data; if you have lots of cached representations of projects which don't actually include any information about the child todo lists or todos, then tough shit, those are all going to be invalidated when a single todo is updated, and you'll have to spend (page load) time waiting for them to be regenerated. In principle you can get around this by having multiple timestamps per model to represent different kinds of update, but again that's more difficult to manage correctly over time. An interesting alternative approach is James Coglan's experimental Primer (https://github.com/jcoglan/primer https://github.com/jcoglan/primer), which dynamically tracks which Active Record instances & attributes are used during the generation of a cached fragment, and then actively invalidates that cache when any of those attributes change. The downside to Primer is that it's more complex, not production-ready, and may contain traces of magic.

yxhuvud 15y ago
Best writeup on the topic of caching in rails that I've seen is http://broadcastingadam.com/2011/05/advanced_caching_in_rails http://broadcastingadam.com/2011/05/advanced_caching_in_rail...

bobobjorn 15y ago

I assume this has the effect that memcached is always full. How do you know when the hot cache is starting to fill memcached? Ie, how do you know when your cache memory is closing up to beeing to small?

ars 15y ago
You probably calculate the ratio of hot requests vs cold ones. Or in other words, the cache miss ratio.
- bobobjorn 15y ago
  But that wont show anything until it most likely already is to late. You dont realy want that value to ever go down, then you already have customers with a worse experience, and when that starts, it goes very fast down the hill.

DodgyEggplant 15y ago

It sounds really impressive, smart, innovative UI and underlying architecture. 37 signals did it again! What is the minimum requirements of a team, programmers/skills/time, to get into such a project and actually deliver?

DodgyEggplant 15y ago
Why the downvote? It looks like a very promising attitude, but one has to consider if this added complexity is feasible for a smaller or less experienced shop. The input is important.
- nkohari 15y ago
  My guess is that the parent is getting downvoted because it's so dense with hero worship that it turns my stomach.
- randomdata 15y ago
  Perhaps because the caching methodology in the article has been advocated to Rails developers for several years now? It was a good refresher for those who have forgotten or are new to Rails (or web development in general), but to call it innovative is going a little far.

StavrosK 15y ago

I was thinking the other day, wouldn't it be easyish and optimal to specify/calculate all the data that is used to generate a fragment, store the information in a tree, and invalidate the parents when a node changes. This would only invalidate data that needs to be invalidated, and it doesn't sound too hard to implement... Does it exist anywhere? What are downsides I haven't thought of?

qwerki 15y ago
not being an expert in this field, one hazard that comes to mind is that a key look up could turn into a tree traversal problem, which defeats the purpose of having a cache in the first place..

mattgreenrocks 15y ago

Is there a way to pull this off when the fragments in question are JSON?

dhh 15y ago
If you use something like jbuilder to build your JSON, then this exact same technique will work just as well.

Sujan 15y ago

Sounds... different than the caching I knew before. Problem is, I don't know Rails at all. Can anyone explaing this in non-rails speech for me? (Links are fine, of course)

asmala 15y ago
The general gist of it is that you store HTML snippets (e.g. a todo, a list containing, or a project containing lists) in some quick storage medium (in this case Memcached). Each snippet is stored under and accessed by a key that uniquely identifies the version saved (object type + ID + update timestamp). When a new version is cached, the old version stays in the cache, unused, until it is eventially dropped out by Memcached. Now all you need to do is to ensure that whenever an object or its children change, you update their timestamp (the "touch" part), and if you make a changes to the code, you increment the version key for said cache piece. This way new requests will not hit old cached content.
- Sujan 15y ago
  Ok, so the first interesting part is that instead of caching the result of a database request we cache the complete rendered result. And the bigger rendered parts are just constructed by combining the smaller (also cached) parts, right? How does the application learn which version an element is at right now? Don't you have to call the database to find out?
  - asmala 15y ago
    Correct on all accounts. You will still need to query the database at least for the parent object being rendered. The time saved is shaved off from the rendering time.
  - getsat 15y ago
    If you're rendering an object, you've likely already fetched it from the DB. Rails models (by default) will have a created_at and updated_at datetime columns that are automatically set and updated for you, and you can use them for exactly what is shown in the article.

tszming 15y ago

I haven't heard people talk about this for a long time.. http://code.google.com/p/memcached/wiki/NewProgrammingTricks#Namespacing http://code.google.com/p/memcached/wiki/NewProgrammingTricks... Anyway, if you use this method, you would expect to have long key, so base64 or binary protocol would be useful.

alexgartrell 15y ago

I work on memcache at Facebook, and cache invalidation is a hard, hard problem. It's easy to think that we just overlooked this trivial fix, but the reality is that this just doesn't solve all possible cache consistency problems. Namely, how do you deal with racing writes where the clocks are skewed? How do you deal with multiple copies of the same data in different caches (different data centers, for example). What about axe-murdering your top level db because that data is inherently uncacheable using this scheme? I'm not trying to hate on the post at all, I think it's awesome that product people are thinking about this problem, and the more of them that do the better the world is going to be for guys like me. I just want them to continue to think hard about it :)

mkramlich 15y ago
good points. but to be fair most problems become hard, hard problems when your site operates at large, large scale. for small traffic sites, caching architecture is easy and most of the subtle vulnerabilities don't manifest. background: i've been a senior staff engineer at Orbitz and i did a lot of work on the caches at Cheaptickets.com

tomfakes 15y ago

I read the initial post about this on Friday morning and spend the rest of the day adding this caching scheme to my almost finished Rails app. In addition, I added the pjax system to my app. In less than 1 day of work, my app feels significantly more responsive to user commands.