You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by "Akins, Brian" <Br...@turner.com> on 2005/08/17 21:37:03 UTC
[PATCH] mod_disk_cache deterministic tempfiles
The current 2.1 mod_disk_cache allows any number of workers to be actively
trying to cache the same object. This is because of the use of
apr_file_mktemp.
This patch makes the tempfiles the same per cache object rather than
"random". I basically added a temp_file() that mimics data_file() and
header_file().
This way only one thread is trying to cache that object and avoids a
"thundering herd." The other threads fail the EXCL flag, and serve like
normal.
RE: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Sergio Leonardi <sl...@etnoteam.it>.
Hi all
I'm thinking to a possible solution to these problems, let me know if this
makes sense. Please note I may suggest things that are already implemented
because I had no time to extensively study the module yet.
Cache module can be splitted in two parts to implement a producer-consumer
model:
1 - mod_cache: should be the "front end" module, the one which accepts
requests and serve contents from the cache
2 - mod_cache_requester: should be the "back end" module, the one which
accepts requests from mod_cache whenever he needs to regenerate the pages;
it will make use of regeneration timeouts that will be discussed further
Up to this point there is no news, let me go deeper.
Whenever mod_cache needs a page generation it contacts mod_cache_requester
inserting data needed into a 2-levels priority queue:
level 1: this is reserved for requests generated by browsers
level 2: this is reserved for requests generated by internal cache
regeneration (i.e. because expiration time is approaching)
In the data structure used we can put all incoming requests for the same URL
in the same "request block" (in a way simil to file system drivers) just to
keep track of how many processes/threads requested it in order to contact
them whenever content generation has been completed.
For each request block:
1 - mark this request block as "generating" instead of "waiting for
generation"
2 - take the first highly prioritized request for this request block
3 - use a configurable default overall generation timeout and a default
block-by-block generation timeout (this can lead to a longer timeout if
content data bytes is continuing to be served by the back end); this latter
is useful for "heavy" content
4 - perform the request to the back end using the above default timeouts
5 - back end response header can contain some "special" variable that can be
used to update above timeout values before serving content data (in order to
allow specific pages to have different timeout values, up to back end
programmer/administrator); if it contains, set these values and remove
special variables from the response header
6 - put the content in the cache
7 - contact each thread/process of mod_cache telling that content is ready
to be served
If timeout occurs between steps 4 - 6:
1 - contact the only thread/process that generated current request of this
request block (the one selected in step 2) giving up
2 - remove this request from this request block
3 - if request block is empty remove it from the queue and exit
4 - if request block is not empty mark the request block as "waiting for
generation", giving to other requests of the same block a chance to be
generated
NOTE 1: Obviously by default level 1 is processed "before" level 2 (or they
can use 2 separate connection pools to the back end, but the first one
should be greater).
NOTE 2: If a request is generated at level 2 and is not served before
content expires, it can happen that a browser asks for the content and
generates a level 1 request for the content. This can be managed by
"escalating" the original request from level 2 to level 1 (using browser's
request data instead of the ones used by internal regeneration).
What do you think about it?
It could be a way to limit requests to the back end in terms of:
- number of requests: avoiding back end saturation during load peaks
- duplicate requests: avoiding back end saturation during regeneration time
Please forget it if I told something OT.
Bye
Sergio
-----Original Message-----
From: Colm MacCarthaigh [mailto:colm@stdlib.net]
Sent: giovedì 18 agosto 2005 20.10
To: dev@httpd.apache.org
Subject: Re: [PATCH] mod_disk_cache deterministic tempfiles
On Thu, Aug 18, 2005 at 02:00:52PM -0400, Brian Akins wrote:
> Colm MacCarthaigh wrote:
>
> >So mtime not being recent is no-indication of death, it could easily be
> >a trickling download.
>
> True. But, if the files mtime has not changed in 120 seconds (for
> example) the download is probably hung?
120 second stalls arn't uncommon, and there are plenty of overloaded
servers and terrible CGI's that have those kind of response times. A
major use of mod_cache to solve just that problem, but any approach
- no matter what number of seconds you pick - will always introduce
inefficiency.
If you pick a value that is too low, you'll never cache slow-to-serve
content. If you pick a value that is too high, you'll end up sending a
lot of requests to the (already slow) backend.
There might be a solution in using the scoreboard.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Thu, Aug 18, 2005 at 02:00:52PM -0400, Brian Akins wrote:
> Colm MacCarthaigh wrote:
>
> >So mtime not being recent is no-indication of death, it could easily be
> >a trickling download.
>
> True. But, if the files mtime has not changed in 120 seconds (for
> example) the download is probably hung?
120 second stalls arn't uncommon, and there are plenty of overloaded
servers and terrible CGI's that have those kind of response times. A
major use of mod_cache to solve just that problem, but any approach
- no matter what number of seconds you pick - will always introduce
inefficiency.
If you pick a value that is too low, you'll never cache slow-to-serve
content. If you pick a value that is too high, you'll end up sending a
lot of requests to the (already slow) backend.
There might be a solution in using the scoreboard.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Colm MacCarthaigh wrote:
> So mtime not being recent is no-indication of death, it could easily be
> a trickling download.
True. But, if the files mtime has not changed in 120 seconds (for
example) the download is probably hung?
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Thu, Aug 18, 2005 at 01:39:18PM -0400, Brian Akins wrote:
> >Dead process is solveable with IPC, the existing locking schemes should
> >be enough for this. The hard problem I think is when a backend has
> >stalled. Can't think of an easy fix for that case.
> >
>
> When you stat the temp file, if its older than x seconds, delete it. x
> is configurable. It's that simple.
I don't think that it is. The write()'s to the actual file arn't going
to occur very often because both reading from the CGI/proxy-backend is
buffered as is writing the file to disk. (and they should be, or the
general case would become much slower).
So mtime not being recent is no-indication of death, it could easily be
a trickling download.
And then the same thing is going to happen to the current request, and
so on and so on and you're going to end up not caching the very requests
that would benefit the most from being cached.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <ba...@web.turner.com>.
Colm MacCarthaigh wrote:
>
>
> Dead process is solveable with IPC, the existing locking schemes should
> be enough for this. The hard problem I think is when a backend has
> stalled. Can't think of an easy fix for that case.
>
When you stat the temp file, if its older than x seconds, delete it. x
is configurable. It's that simple.
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Thu, Aug 18, 2005 at 10:07:29AM -0700, Justin Erenkrantz wrote:
> Okay. I see what you mean now.
>
> If the interval is configurable via a directive, then yes that makes sense.
> This could be done independently of deterministic tempfiles.
It could, though it would require using a seperate locking mechanism.
> (I hope this means you volunteer to write the patch!)
Unless someone beats me too it.
> However, using deterministic tempfiles means that there's a possibility of
> a 'deadlock' - in that a response will never be updated because of a stuck
> or dead process. I've not seen a feasible strategy to resolve this issue.
Dead process is solveable with IPC, the existing locking schemes should
be enough for this. The hard problem I think is when a backend has
stalled. Can't think of an easy fix for that case.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
--On August 18, 2005 9:24:57 AM +0100 Colm MacCarthaigh <co...@stdlib.net>
wrote:
> On Wed, Aug 17, 2005 at 03:17:41PM -0700, Justin Erenkrantz wrote:
>> > Content definitely should not be served from the cache after it has
>> > expired imo. However I think an approach like;
>> >
>> > if((now + interval) > expired) {
>> > if(!stat(tmpfile)) {
>> > update_cache_from_backend();
>> > }
>> > }
>> >
>> > ie "revalidate the cache content after N-seconds before it is due to be
>> > expired" would have the same effect, but avoid serving stale content.
>> >
>> > Does that make sense?
>>
>> Um, isn't that what we already do? -- justin
>
> No :-) Right now, once the cache entity stops being considered fresh,
> each worker that gets a request will fetch it, store it to their own
> tmpfile and race to be first to rename it.
>
> With the above approach, there could be some kind of user-configurable
> interval before expiry, say 10 minutes in this example. So, the first
> request that happens within that 10 minute interval would re-validate
> the cache entity.
>
> If it doesn't need to be fetched and gets a not-modified, we just
> "touch" the cache entity and go on our merry way.
>
> If it does need to be fetched then a deterministic tmpfile ensures that
> no other worker bothers to fetch it at the same time, they can serve
> from the cache in the meantime - which still hasn't expired.
>
> If after the 10 minutes the content still isn't there, the user should
> have set a better value for "interval", and we've no choice but to start
> fetching the content per-request until something writes a cache file.
Okay. I see what you mean now.
If the interval is configurable via a directive, then yes that makes sense.
This could be done independently of deterministic tempfiles. (I hope this
means you volunteer to write the patch!)
However, using deterministic tempfiles means that there's a possibility of a
'deadlock' - in that a response will never be updated because of a stuck or
dead process. I've not seen a feasible strategy to resolve this issue.
In the case of fetching before expiration, the 'lock' can be 'advisory' -
after expiration, it can fall back to the current case. -- justin
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Wed, Aug 17, 2005 at 03:17:41PM -0700, Justin Erenkrantz wrote:
> >Content definitely should not be served from the cache after it has
> >expired imo. However I think an approach like;
> >
> > if((now + interval) > expired) {
> > if(!stat(tmpfile)) {
> > update_cache_from_backend();
> > }
> > }
> >
> >ie "revalidate the cache content after N-seconds before it is due to be
> >expired" would have the same effect, but avoid serving stale content.
> >
> >Does that make sense?
>
> Um, isn't that what we already do? -- justin
No :-) Right now, once the cache entity stops being considered fresh,
each worker that gets a request will fetch it, store it to their own
tmpfile and race to be first to rename it.
With the above approach, there could be some kind of user-configurable
interval before expiry, say 10 minutes in this example. So, the first
request that happens within that 10 minute interval would re-validate
the cache entity.
If it doesn't need to be fetched and gets a not-modified, we just
"touch" the cache entity and go on our merry way.
If it does need to be fetched then a deterministic tmpfile ensures that
no other worker bothers to fetch it at the same time, they can serve
from the cache in the meantime - which still hasn't expired.
If after the 10 minutes the content still isn't there, the user should
have set a better value for "interval", and we've no choice but to start
fetching the content per-request until something writes a cache file.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
--On August 17, 2005 9:52:32 PM +0100 Colm MacCarthaigh <co...@stdlib.net>
wrote:
> Content definitely should not be served from the cache after it has
> expired imo. However I think an approach like;
>
> if((now + interval) > expired) {
> if(!stat(tmpfile)) {
> update_cache_from_backend();
> }
> }
>
> ie "revalidate the cache content after N-seconds before it is due to be
> expired" would have the same effect, but avoid serving stale content.
>
> Does that make sense?
Um, isn't that what we already do? -- justin
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Colm MacCarthaigh wrote:
> ie "revalidate the cache content after N-seconds before it is due to be
> expired" would have the same effect, but avoid serving stale content.
>
> Does that make sense?
>
Yes. cool. +1.
Thanks!
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Wed, Aug 17, 2005 at 04:11:01PM -0400, Brian Akins wrote:
> I have the thought that we could also serve files that have "recently
> expired" (recent being configurable) if the object was being cached.
> Psudocode:
>
> if(expired < (now - recent)) {
Content definitely should not be served from the cache after it has
expired imo. However I think an approach like;
if((now + interval) > expired) {
if(!stat(tmpfile)) {
update_cache_from_backend();
}
}
ie "revalidate the cache content after N-seconds before it is due to be
expired" would have the same effect, but avoid serving stale content.
Does that make sense?
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Graham Leggett wrote:
> This is very cool. On my list of things to do was to handle something
> similar for serving from the cache as well - again to avoid a thundering
> herd against backend servers while a file is being cached.
I have the thought that we could also serve files that have "recently
expired" (recent being configurable) if the object was being cached.
Psudocode:
if(expired < (now - recent)) {
if(stat(tmpfile) {
if(mtime_is_resonable) {
serve_old_file;
} else {
unlimk(tempfile)
}
}
}
This would also allow only one request through to "refresh" the object
and protect against a "hung" worker (bad backend server, database, whatever)
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Graham Leggett <mi...@sharp.fm>.
Brian Akins wrote:
> Only way I can think of this is to keep trying to seek until file gets
> renamed. Maybe not very efficient.
Thing is, compared to the total hits to a server, those hits that were
slightly less efficient while serving an "in flight" object would be a
tiny fraction of the total hits, so we could probably get away with
being slightly less efficient on one specific URL for a short amount of
time.
Regards,
Graham
--
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Graham Leggett <mi...@sharp.fm>.
Justin Erenkrantz wrote:
>> For a disk cache it would be tricky to discern between a cached file
>> that is half there due to a sudden httpd exit, and a cached file that is
>> half there because a proxy or CGI backend is blocking.
> Exactly. This is why I've avoided this functionality. I don't think it
> can be implemented effectively or efficiently.
I don't think this is a problem that needs complex error handling at all.
In the current situation, if the backend stalls, one frontend client
will stall. If the in flight cache object is shared, then if the backend
stalls, more than one frontend client will stall. This is a lesser evil
than the current behaviour, where thundering herd hits the backend every
time a resource expires, which in the case of typical news sites, is
once every sixty seconds.
In both cases, at least one client will eventually get impatient and
force reload that particular resource. This will invalidate the in
flight object, and the cache process is retried again.
If the proxy gets impatient and times out the backend, it will
invalidate the in flight object, and signal to the frontend to close the
connections. The clients will simply try refetch the object, something
they would have to do anyway.
> I absolutely dislike the idea of stalling a request because another
> worker/thread *might* be fetching it. We should never purposely stall a
> request because another worker *might* have a request outstanding.
In this case it's not "might", it's "almost always". Any connection
already faces the very small possiblity that it might hang. That very
small possiblity increasing in chance by a few simultaneous connections
is still a minimal risk than the certainty of thundering herd.
Regards,
Graham
--
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Justin Erenkrantz <ju...@erenkrantz.com>.
--On August 17, 2005 9:29:05 PM +0100 Colm MacCarthaigh <co...@stdlib.net>
wrote:
> Why bother renaming the file for such an implementation? If a
> half-cached file can be served from, and this handled properly, the
> rename would no longer make any sense :)
>
> For a disk cache it would be tricky to discern between a cached file
> that is half there due to a sudden httpd exit, and a cached file that is
> half there because a proxy or CGI backend is blocking.
Exactly. This is why I've avoided this functionality. I don't think it
can be implemented effectively or efficiently.
I absolutely dislike the idea of stalling a request because another
worker/thread *might* be fetching it. We should never purposely stall a
request because another worker *might* have a request outstanding.
> One solution that avoids that may be to create random uuid at httpd
> start time, and store that in every cache object. That way the caching
> layer can determine if the half-cached file on disk belongs to a
> "current" instance of httpd - and we assume it's in-flight - or if it
> belongs to a previous instance of httpd, and we assume it's leftover
> from a sudden death.
It doesn't handle the case when a sibling died. -- justin
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Colm MacCarthaigh wrote:
> On Wed, Aug 17, 2005 at 04:33:24PM -0400, Brian Akins wrote:
>
>>True.
>>
>>But like Graham said, ultimately, I don't think it's worth it.
>
>
> I got the opposite from what Graham said, but may have mis-read.
>
Or i did...
>
> Depends on the environment. For a proxy, being able to serve in-flight
> content to multiple requesters is considered a major feature.
>
> If 10 proxy clients request the latest service-pack at the same time,
> is it going to be faster or slower to have 10 upstream requests or
> 1 pooled?
Sure. It really depends upon the exact application. In most reverse
proxy situations, it probably wouldn't help as much as what I proposed.
In "normal" proxy, it could reap huge rewards.
some pseudo code:
if(stat(tempfile)) {
if(size - lastoffset > 0) {
newbucket(lastoffset, size - lastoffset);
lastoffset = size;
} else {
/*sleep? evil I know....*/
}
}
If the correct size was stored in the header file (it's there, don't
know if it's correct), then you could just compare it to stat. That way
you wouldn't need temp files as you suggested earlier.
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Wed, Aug 17, 2005 at 04:33:24PM -0400, Brian Akins wrote:
> True.
>
> But like Graham said, ultimately, I don't think it's worth it.
I got the opposite from what Graham said, but may have mis-read.
> Not to be biased, but I think my idea of serving "recently" expired
> objects would also avoid the thundering herd. As long as recent and the
> timeout were reasonable, it should be very efficient.
Depends on the environment. For a proxy, being able to serve in-flight
content to multiple requesters is considered a major feature.
If 10 proxy clients request the latest service-pack at the same time,
is it going to be faster or slower to have 10 upstream requests or
1 pooled?
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Colm MacCarthaigh wrote:
> Why bother renaming the file for such an implementation? If a
> half-cached file can be served from, and this handled properly, the
> rename would no longer make any sense :)
True.
But like Graham said, ultimately, I don't think it's worth it.
Not to be biased, but I think my idea of serving "recently" expired
objects would also avoid the thundering herd. As long as recent and the
timeout were reasonable, it should be very efficient.
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Colm MacCarthaigh <co...@stdlib.net>.
On Wed, Aug 17, 2005 at 04:13:37PM -0400, Brian Akins wrote:
> Graham Leggett wrote:
> The disk cache might be a
> >bit more involved, but the idea would be the same.
>
> Only way I can think of this is to keep trying to seek until file gets
> renamed. Maybe not very efficient.
Why bother renaming the file for such an implementation? If a
half-cached file can be served from, and this handled properly, the
rename would no longer make any sense :)
For a disk cache it would be tricky to discern between a cached file
that is half there due to a sudden httpd exit, and a cached file that is
half there because a proxy or CGI backend is blocking.
> Or maybe a hash/queue/something that kept track of "in-flight" objects.
> But, this would be per process, unless you did it in dbm or something.
One solution that avoids that may be to create random uuid at httpd
start time, and store that in every cache object. That way the caching
layer can determine if the half-cached file on disk belongs to a
"current" instance of httpd - and we assume it's in-flight - or if it
belongs to a previous instance of httpd, and we assume it's leftover
from a sudden death.
--
Colm MacCárthaigh Public Key: colm+pgp@stdlib.net
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Brian Akins <br...@turner.com>.
Graham Leggett wrote:
The disk cache might be a
> bit more involved, but the idea would be the same.
Only way I can think of this is to keep trying to seek until file gets
renamed. Maybe not very efficient.
Or maybe a hash/queue/something that kept track of "in-flight" objects.
But, this would be per process, unless you did it in dbm or something.
Just thinking out load...
--
Brian Akins
Lead Systems Engineer
CNN Internet Technologies
Re: [PATCH] mod_disk_cache deterministic tempfiles
Posted by Graham Leggett <mi...@sharp.fm>.
Akins, Brian wrote:
> The current 2.1 mod_disk_cache allows any number of workers to be actively
> trying to cache the same object. This is because of the use of
> apr_file_mktemp.
>
> This patch makes the tempfiles the same per cache object rather than
> "random". I basically added a temp_file() that mimics data_file() and
> header_file().
>
> This way only one thread is trying to cache that object and avoids a
> "thundering herd." The other threads fail the EXCL flag, and serve like
> normal.
This is very cool. On my list of things to do was to handle something
similar for serving from the cache as well - again to avoid a thundering
herd against backend servers while a file is being cached.
Basically the cache could serve from a half cached file, serving the
data as the cache file grows. In the mem cache case this is trivial, as
a simple flag saying "still busy" can indicate whether an EOF on a
cached file is actually the EOS or whether the stream should back off
for a bit, and try read some more a bit later. The disk cache might be a
bit more involved, but the idea would be the same.
Regards,
Graham
--