[PATCH] mod_cache: support caching of streamed responses

[Brian Pane <br...@apache.org>]

This patch allows mod_cache to cache a response that isn't
all contained in the first brigade sent through cache_in_filter().
(This scenario happens, for example, with reverse-proxy requests,
CGIs, and various app server connectors.)

Can someone familiar with the caching code please scrutinize
the patch and send comments?  There's one known problem with
the code (details below), but it's otherwise ready for review.

The way it works is:

  * If the first call to cache_in_filter() includes an EOS,
    the operation is unchanged: put the response in the cache (
    assuming it meets all the other cacheability criteria) and
    pass the brigade to the next filter.

  * If the brigade passed to cache_in_filter() doesn't have an
    EOS, though, the filter now makes a copy of the brigade and
    passes the original on to the next filter.  In subsequent
    calls, cache_in_filter() continues buffering up copies of
    the buckets while streaming the response on to the next
    filter in the chain.  Once it finally sees an EOS, it
    concatenates the setaside buckets into a single brigade
    for storage in the cache.  It then streams the last bit
    of the output to the next filter.

  * If the response contains any bucket with length==-1 (an
    unread pipe bucket, for example), the filter doesn't attempt
    to cache it.  (It's probably possible to add support for
    this in the future.)

The one thing that's missing is a check to avoid setting aside
too much data.  If the total size of the setaside buckets would
exceed the maximum object size for the cache, cache_in_filter()
should immediately discard the setaside buckets and give up on
caching the response.  What's the right way to implement this
check?  It looks like the max object size is a property of each
specific cache implementation (mod_mem_cache, mod_disk_cache).
The first solution that comes to mind is to make each cache
implementation provide a callback function that says whether
it's willing to cache an object of size X.  Is there a cleaner
solution?

-Brian

Re: [PATCH] mod_cache: support caching of streamed responses

[Ian Holsman <ia...@apache.org>]

Brian Pane wrote:
> Graham Leggett wrote:
> 
>>> For the expiration case, there's a much easier solution than 
>>> shadowing the
>>> incomplete response.  Add a new state for cache entries: 
>>> "being_updated."
>>> When you get a request for a cached object that's past its expiration 
>>> date,
>>> set the cache entry's state to "being_updated" and start retrieving 
>>> the new
>>> content.  Meanwhile, as other threads handle requests for the same 
>>> object,
>>> they check the state of the cache entry and, because it's currently 
>>> being
>>> updated, they deliver the old copy from the cache rather than 
>>> dispatching
>>> the request to the backend system that's already working on a different
>>> instance of the same request.  As long as the thread that's getting 
>>> the new
>>> content can replace the old content with the new content atomically, 
>>> there's
>>> no reason to make any other threads wait for the new content.
>>
>>
>>
>> Hmmm... ok, not a bad idea, however I see a few hassles though.
>>
>> What if a user force-reloads the page. In theory the cached copy 
>> should be expired immediately - but here we don't, because shadow 
>> threads need to access the cached content in the meantime.
> 
> 
> 
> I actually think we *shouldn't* expire the cached copy in this
> case.  I want the server, rather than the client, to be able to
> decide whether to expire a cache entry.  If the client gets to
> dictate the expiration semantics, then we're vulnerable to a
> DoS attack (all a malicious client would need to do is start
> submitting lots of requests that invalidate cache entries).
> 
this is not RFC compliant, so some people will prefer RFC compliance.
to give the more sane (imho ;-) use case, we have a directive which
will ignore the client cache request.

>> Also - there will be a load spike until the first page is cached (in 
>> the case where no previous cache existed).
> 

> 
> 
> Yep.  I think the ideal solution would be to combine this
> technique with shadowing support.  Then mod_cache could do
> one of four things depending on the cache state:
>  * cache hit, normal case: deliver the object from cache
>  * cache hit, while another thread is updating: deliver the old object
>  * cache miss, normal case: go retrieve the content
>  * cache miss, while another thread is updating: shadow the response in 
> progress
> 
>> What happens if an attempt to update an expired cached page hangs? The 
>> proxy could find itself serving stale content for a long time while a 
>> timeout occurs.
> 
> 
> 
> One solution is to add a timestamp for the "being updated" flag.
> If another thread sees that the flag is set but the timestamp is
> more than 'n' seconds old, that thread sets the timestamp to the
> current time and tries to retrieve the object itself.  (This
> logic just needs to be atomic so that we don't end up with multiple
> threads all deciding to retrieve the content at once.)

I was actually thinking that we could use another priority queue
and a seperate thread(s) to call the back end, limiting the amount of 
traffic which can ever get to the backend at all.
> 
>>>  * It's going to take a while to make the shadowing work
>>>    (due to all the race conditions that have to be addressed).
>>
>>
>>
>> I don't see any significant race conditions though.
>>
>> All that needs to happen is that all cached responses are 
>> readable-from-the-cache the moment they are created, rather than the 
>> moment the download is complete. A flag against the cache entry marks 
>> it as "still busy". If this flag is set, shadowed threads know to keep 
>> waiting for more data appearing in the cache. If the flag is not set, 
>> the shadow thread is a normal CACHE_OUT case, and finishes up the 
>> request knowing it to be complete.
> 
> 
> 
> The race conditions arise in cases where, for example, we find out
> halfway through a streamed request that it isn't cacheable after all
> because it's just exceeded the max cache size.  Therefore we won't
> be caching this response permanently, but we do need to keep the
> buffered buckets around until all threads that are shadowing the
> response have finished using those buckets.  And then, after the
> last of those threads finishes using the data, we need to delete
> the saved brigade.  But if the response is *really* large, we can't
> keep the whole thing in memory until the last thread finishes
> delivering it.  Instead, we'd have to incrementally delete buckets
> from the start of the brigade as all the threads finish dealing
> with each one.  (And keep new threads from shadowing the response
> from the moment when we first delete a bucket.)  This can all be
> done with reference counts and careful synchronization, but it's
> going to be challenging to debug.
> 
> Brian
> 
> 

Re: [PATCH] mod_cache: support caching of streamed responses

[Brian Pane <br...@apache.org>]

Graham Leggett wrote:

>> For the expiration case, there's a much easier solution than 
>> shadowing the
>> incomplete response.  Add a new state for cache entries: 
>> "being_updated."
>> When you get a request for a cached object that's past its expiration 
>> date,
>> set the cache entry's state to "being_updated" and start retrieving 
>> the new
>> content.  Meanwhile, as other threads handle requests for the same 
>> object,
>> they check the state of the cache entry and, because it's currently 
>> being
>> updated, they deliver the old copy from the cache rather than 
>> dispatching
>> the request to the backend system that's already working on a different
>> instance of the same request.  As long as the thread that's getting 
>> the new
>> content can replace the old content with the new content atomically, 
>> there's
>> no reason to make any other threads wait for the new content.
>
>
> Hmmm... ok, not a bad idea, however I see a few hassles though.
>
> What if a user force-reloads the page. In theory the cached copy 
> should be expired immediately - but here we don't, because shadow 
> threads need to access the cached content in the meantime.


I actually think we *shouldn't* expire the cached copy in this
case.  I want the server, rather than the client, to be able to
decide whether to expire a cache entry.  If the client gets to
dictate the expiration semantics, then we're vulnerable to a
DoS attack (all a malicious client would need to do is start
submitting lots of requests that invalidate cache entries).

> Also - there will be a load spike until the first page is cached (in 
> the case where no previous cache existed).


Yep.  I think the ideal solution would be to combine this
technique with shadowing support.  Then mod_cache could do
one of four things depending on the cache state:
  * cache hit, normal case: deliver the object from cache
  * cache hit, while another thread is updating: deliver the old object
  * cache miss, normal case: go retrieve the content
  * cache miss, while another thread is updating: shadow the response in 
progress

> What happens if an attempt to update an expired cached page hangs? The 
> proxy could find itself serving stale content for a long time while a 
> timeout occurs.


One solution is to add a timestamp for the "being updated" flag.
If another thread sees that the flag is set but the timestamp is
more than 'n' seconds old, that thread sets the timestamp to the
current time and tries to retrieve the object itself.  (This
logic just needs to be atomic so that we don't end up with multiple
threads all deciding to retrieve the content at once.)

>>  * It's going to take a while to make the shadowing work
>>    (due to all the race conditions that have to be addressed).
>
>
> I don't see any significant race conditions though.
>
> All that needs to happen is that all cached responses are 
> readable-from-the-cache the moment they are created, rather than the 
> moment the download is complete. A flag against the cache entry marks 
> it as "still busy". If this flag is set, shadowed threads know to keep 
> waiting for more data appearing in the cache. If the flag is not set, 
> the shadow thread is a normal CACHE_OUT case, and finishes up the 
> request knowing it to be complete.


The race conditions arise in cases where, for example, we find out
halfway through a streamed request that it isn't cacheable after all
because it's just exceeded the max cache size.  Therefore we won't
be caching this response permanently, but we do need to keep the
buffered buckets around until all threads that are shadowing the
response have finished using those buckets.  And then, after the
last of those threads finishes using the data, we need to delete
the saved brigade.  But if the response is *really* large, we can't
keep the whole thing in memory until the last thread finishes
delivering it.  Instead, we'd have to incrementally delete buckets
from the start of the brigade as all the threads finish dealing
with each one.  (And keep new threads from shadowing the response
from the moment when we first delete a bucket.)  This can all be
done with reference counts and careful synchronization, but it's
going to be challenging to debug.

Brian

Re: [PATCH] mod_cache: support caching of streamed responses

[Graham Leggett <mi...@sharp.fm>]

Brian Pane wrote:

> Sure, by that metric, it's a waste of time: the current code can't even
> cache responses that arrive in multiple brigades, which is a prerequisite
> for shadowing incomplete requests.  But so what?  The cache is very much a
> work in progress; we should judge it by where the code is going, not where
> it is today.

True, but we need to ensure we don't make design decisions now that make 
certain features impossible to implement. The old cache code worked 
pretty well, but had some flaws that only a rewrite and redesign could 
fix. We shouldn't not try implement something only because it is hard :)

> For the expiration case, there's a much easier solution than shadowing the
> incomplete response.  Add a new state for cache entries: "being_updated."
> When you get a request for a cached object that's past its expiration date,
> set the cache entry's state to "being_updated" and start retrieving the new
> content.  Meanwhile, as other threads handle requests for the same object,
> they check the state of the cache entry and, because it's currently being
> updated, they deliver the old copy from the cache rather than dispatching
> the request to the backend system that's already working on a different
> instance of the same request.  As long as the thread that's getting the new
> content can replace the old content with the new content atomically, 
> there's
> no reason to make any other threads wait for the new content.

Hmmm... ok, not a bad idea, however I see a few hassles though.

What if a user force-reloads the page. In theory the cached copy should 
be expired immediately - but here we don't, because shadow threads need 
to access the cached content in the meantime.

Also - there will be a load spike until the first page is cached (in the 
case where no previous cache existed).

What happens if an attempt to update an expired cached page hangs? The 
proxy could find itself serving stale content for a long time while a 
timeout occurs.

>  * It's going to take a while to make the shadowing work
>    (due to all the race conditions that have to be addressed).

I don't see any significant race conditions though.

All that needs to happen is that all cached responses are 
readable-from-the-cache the moment they are created, rather than the 
moment the download is complete. A flag against the cache entry marks it 
as "still busy". If this flag is set, shadowed threads know to keep 
waiting for more data appearing in the cache. If the flag is not set, 
the shadow thread is a normal CACHE_OUT case, and finishes up the 
request knowing it to be complete.

Shadow support was anticipated in the original design for the current 
cache, so should be pretty easy to implement.

>  * In the meantime, I need a solution for caching responses
>    that don't arrive all in a single brigade.  I'd like to
>    get this added now, and not wait for the shadowing support.

Shadowing depends on multiple brigades being cachable, not the other way 
around, so definitely go ahead with the work on multiple brigades.

Regards,
Graham
-- 
-----------------------------------------
minfrin@sharp.fm 
	"There's a moon
					over Bourbon Street
						tonight..."

Re: [PATCH] mod_cache: support caching of streamed responses

[Brian Pane <br...@apache.org>]

Graham Leggett wrote:

> Brian Pane wrote:
>
>> In the "shawowing" case, we'd also need a way for all the requests
>> reading from the same incomplete cache entry to block if they reach
>> the end of the incomplete cached brigade without seeing EOS.  I guess
>> we could do this by adding a condition variable to every incomplete
>> entry in the cache, so that the threads shadowing the request could
>> block if they'd sent all the data available so far.  And then the
>> thread that was actually retrieving the resource would signal the
>> condition variable each time it added some more data to the cache
>> entry.
>>
>> But that's way too complicated. :-)
>>
>> What do you think about the following as a low-tech solution:
>>
>> * Keep the current model of only putting complete responses in
>>  the cache (at least for now).
>
>
> This was exactly how the old cached worked - which would mean we just 
> rewrote the cache to have exactly the same design flaws as the old 
> cache did, which is a big waste of time.


Sure, by that metric, it's a waste of time: the current code can't even
cache responses that arrive in multiple brigades, which is a prerequisite
for shadowing incomplete requests.  But so what?  The cache is very much a
work in progress; we should judge it by where the code is going, not where
it is today.

> This problem causes an annoying race condition: when a cached object 
> expires, for a short time from expiry to cache-complete all requests 
> go through to the backend. This causes load spikes, which on expensive 
> backends can be really annoying (it has been reported so in the past).


For the expiration case, there's a much easier solution than shadowing the
incomplete response.  Add a new state for cache entries: "being_updated."
When you get a request for a cached object that's past its expiration date,
set the cache entry's state to "being_updated" and start retrieving the new
content.  Meanwhile, as other threads handle requests for the same object,
they check the state of the cache entry and, because it's currently being
updated, they deliver the old copy from the cache rather than dispatching
the request to the backend system that's already working on a different
instance of the same request.  As long as the thread that's getting the new
content can replace the old content with the new content atomically, there's
no reason to make any other threads wait for the new content.

> A key design feature of the new cache was to allow "shadowing" to be 
> possible, ie a partially cached response would be servable by other 
> cache threads/processes, thus solving this problem.


Shadowing is an important feature to add (although the technique
described above may reduce the need for it somewhat).  But:

  * It's going to take a while to make the shadowing work
    (due to all the race conditions that have to be addressed).

  * In the meantime, I need a solution for caching responses
    that don't arrive all in a single brigade.  I'd like to
    get this added now, and not wait for the shadowing support.
    The code for supporting caching of streamed responses
    will give us a foundation for shadowing in the future.

Brian

Re: [PATCH] mod_cache: support caching of streamed responses

[Graham Leggett <mi...@sharp.fm>]

Brian Pane wrote:

> In the "shawowing" case, we'd also need a way for all the requests
> reading from the same incomplete cache entry to block if they reach
> the end of the incomplete cached brigade without seeing EOS.  I guess
> we could do this by adding a condition variable to every incomplete
> entry in the cache, so that the threads shadowing the request could
> block if they'd sent all the data available so far.  And then the
> thread that was actually retrieving the resource would signal the
> condition variable each time it added some more data to the cache
> entry.
> 
> But that's way too complicated. :-)
> 
> What do you think about the following as a low-tech solution:
> 
> * Keep the current model of only putting complete responses in
>  the cache (at least for now).

This was exactly how the old cached worked - which would mean we just 
rewrote the cache to have exactly the same design flaws as the old cache 
did, which is a big waste of time.

This problem causes an annoying race condition: when a cached object 
expires, for a short time from expiry to cache-complete all requests go 
through to the backend. This causes load spikes, which on expensive 
backends can be really annoying (it has been reported so in the past). A 
key design feature of the new cache was to allow "shadowing" to be 
possible, ie a partially cached response would be servable by other 
cache threads/processes, thus solving this problem.

Regards,
Graham
-- 
-----------------------------------------
minfrin@sharp.fm 
	"There's a moon
					over Bourbon Street
						tonight..."

Re: [PATCH] mod_cache: support caching of streamed responses

[Brian Pane <br...@apache.org>]

Graham Leggett wrote:

> Bill Stoddard wrote:
>
>> Adding a callback/hooks sounds okay.  An additional problem to 
>> consider is
>> when a frequently requested resource does not return an EOS in the firet
>> brigade and it turns out to be too large for the cache. We need a 
>> negative
>> cache (what else would you call it?) to prevent mod_cache from 
>> attempting to
>> cache the same object over and over. If the object is too large, 
>> create a
>> negative cache entry.  Consult the negative cache when the response is
>> received to determine if mod_cache should even attempt caching.
>
>
> In the original design (not sure what it is now) the memory cache code 
> set aside a whole lot of brigades, and each brigade was simply added 
> to the cached brigade set.
>
> In order to ensure there was enough memory, the original design 
> limited memory caching to requests with a Content-Length header, ie a 
> predetermined length. Thinking about this some more this isn't even 
> necessary, as the cache could simply keep adding brigades to the 
> cache, and should the length of the brigades cached so far exceed a 
> certain value, it could simply toss away the entire set aside set of 
> brigades and remove the cache_in filter, thus ditching the cache attempt.
>
> The only problem with this is with requests that are "shadowing" this 
> request. ie a subsequent request that has requested a resource half in 
> the cache already and still being fetched. If the leading thread 
> ditched the caching attempt, the shadowing threads might get confused 
> as the data they are sending just got ripped out from under them. What 
> might be possible is for some intelligence to be built in to only 
> throw away buckets that are not due to be shadowed. All in all though 
> it is still easier to mandate that only objects with a predetermined 
> length can be memory cached.


In the "shawowing" case, we'd also need a way for all the requests
reading from the same incomplete cache entry to block if they reach
the end of the incomplete cached brigade without seeing EOS.  I guess
we could do this by adding a condition variable to every incomplete
entry in the cache, so that the threads shadowing the request could
block if they'd sent all the data available so far.  And then the
thread that was actually retrieving the resource would signal the
condition variable each time it added some more data to the cache
entry.

But that's way too complicated. :-)

What do you think about the following as a low-tech solution:

* Keep the current model of only putting complete responses in
  the cache (at least for now).

* Add a new config parameter to mod_cache:
    CacheMaxStreamingBuffer <bytes>
  This would set the maximum amount of content that mod_cache
  would setaside on a streaming request in anticipation of
  being able to cache it.  The default would be zero.  For
  general use, it could be tuned to a smaller value than the
  max object size for the mem_cache or disk_cache.  E.g., if
  the server is using a mem_cache with a 2MB max object size,
  and a proxied response produces a 2.1MB file, buffering and
  then discarding the first 2MB on each request would be bad.
  But if one could set the limit on buffering for streamed
  responses to a more reasonable number, like 100KB, then
  buffering and discarding that much data wouldn't be much of
  a problem.

I think this new parameter to limit the amount of setaside
data would be complementary to a negative cache: the negative
cache reduces the probability that mod_cache will buffer up
a streamed response that can't be cached, while the buffering
limit reduces the cost of buffering and discarding a noncacheable
streamed response that wasn't caught by the negative cache.

Brian

Re: [PATCH] mod_cache: support caching of streamed responses

[Graham Leggett <mi...@sharp.fm>]

Bill Stoddard wrote:

> Adding a callback/hooks sounds okay.  An additional problem to consider is
> when a frequently requested resource does not return an EOS in the firet
> brigade and it turns out to be too large for the cache. We need a negative
> cache (what else would you call it?) to prevent mod_cache from attempting to
> cache the same object over and over. If the object is too large, create a
> negative cache entry.  Consult the negative cache when the response is
> received to determine if mod_cache should even attempt caching.

In the original design (not sure what it is now) the memory cache code 
set aside a whole lot of brigades, and each brigade was simply added to 
the cached brigade set.

In order to ensure there was enough memory, the original design limited 
memory caching to requests with a Content-Length header, ie a 
predetermined length. Thinking about this some more this isn't even 
necessary, as the cache could simply keep adding brigades to the cache, 
and should the length of the brigades cached so far exceed a certain 
value, it could simply toss away the entire set aside set of brigades 
and remove the cache_in filter, thus ditching the cache attempt.

The only problem with this is with requests that are "shadowing" this 
request. ie a subsequent request that has requested a resource half in 
the cache already and still being fetched. If the leading thread ditched 
the caching attempt, the shadowing threads might get confused as the 
data they are sending just got ripped out from under them. What might be 
possible is for some intelligence to be built in to only throw away 
buckets that are not due to be shadowed. All in all though it is still 
easier to mandate that only objects with a predetermined length can be 
memory cached.

Regards,
Graham
-- 
-----------------------------------------
minfrin@sharp.fm 
	"There's a moon
					over Bourbon Street
						tonight..."

RE: [PATCH] mod_cache: support caching of streamed responses

[Bill Stoddard <bi...@wstoddard.com>]

> This patch allows mod_cache to cache a response that isn't
> all contained in the first brigade sent through cache_in_filter().
> (This scenario happens, for example, with reverse-proxy requests,
> CGIs, and various app server connectors.)
>
> Can someone familiar with the caching code please scrutinize
> the patch and send comments?  There's one known problem with
> the code (details below), but it's otherwise ready for review.
>
> The way it works is:
>
>   * If the first call to cache_in_filter() includes an EOS,
>     the operation is unchanged: put the response in the cache (
>     assuming it meets all the other cacheability criteria) and
>     pass the brigade to the next filter.
>
>   * If the brigade passed to cache_in_filter() doesn't have an
>     EOS, though, the filter now makes a copy of the brigade and
>     passes the original on to the next filter.  In subsequent
>     calls, cache_in_filter() continues buffering up copies of
>     the buckets while streaming the response on to the next
>     filter in the chain.  Once it finally sees an EOS, it
>     concatenates the setaside buckets into a single brigade
>     for storage in the cache.  It then streams the last bit
>     of the output to the next filter.
>
>   * If the response contains any bucket with length==-1 (an
>     unread pipe bucket, for example), the filter doesn't attempt
>     to cache it.  (It's probably possible to add support for
>     this in the future.)
>
> The one thing that's missing is a check to avoid setting aside
> too much data.  If the total size of the setaside buckets would
> exceed the maximum object size for the cache, cache_in_filter()
> should immediately discard the setaside buckets and give up on
> caching the response.  What's the right way to implement this
> check?  It looks like the max object size is a property of each
> specific cache implementation (mod_mem_cache, mod_disk_cache).
> The first solution that comes to mind is to make each cache
> implementation provide a callback function that says whether
> it's willing to cache an object of size X.  Is there a cleaner
> solution?
>
> -Brian

Adding a callback/hooks sounds okay.  An additional problem to consider is
when a frequently requested resource does not return an EOS in the firet
brigade and it turns out to be too large for the cache. We need a negative
cache (what else would you call it?) to prevent mod_cache from attempting to
cache the same object over and over. If the object is too large, create a
negative cache entry.  Consult the negative cache when the response is
received to determine if mod_cache should even attempt caching.

Bill


>
>