You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Graham Leggett <mi...@sharp.fm> on 2010/10/23 17:48:53 UTC
Optimising ap_location_walk()
Hi all,
I am looking to improve per-request performance when you have an
environment with many (thousands of) Location sections, and looking at
ap_location_walk(), it looks like it is currently doing a simple
linear search of locations on every request, which is far from ideal.
Ideally, I'd like to create an index of the location sec_dir and
sec_url array, by creating a tree of hashtables that will allow us to
drill down to the relevant locations as quick as possible. This will
also allow us to pre-merge many of the configurations at startup,
instead of just at runtime (obviously because .htaccess is parsed at
runtime we won't completely eliminate merging, but we will minimise it).
If we're careful about what pools we use on startup, we can also free
a lot of the memory used in the initial configuration scan, keeping a
copy of the merged config, instead of a copy of each location's configs.
Regards,
Graham
--
Re: Optimising ap_location_walk()
Posted by Stefan Fritsch <sf...@sfritsch.de>.
On Saturday 23 October 2010, Graham Leggett wrote:
> Ideally, I'd like to create an index of the location sec_dir and
> sec_url array, by creating a tree of hashtables that will allow us
> to drill down to the relevant locations as quick as possible.
That sounds like a good idea. You need to be careful to preserve the
order of the Location sections, however.
> This will also allow us to pre-merge many of the configurations at
> startup, instead of just at runtime (obviously because .htaccess
> is parsed at runtime we won't completely eliminate merging, but we
> will minimise it).
>
> If we're careful about what pools we use on startup, we can also
> free a lot of the memory used in the initial configuration scan,
> keeping a copy of the merged config, instead of a copy of each
> location's configs.
Even if you don't worry about freeing memory, merging some of the
configs before forking the childs may save some memory because the
merged configs will be shared among the childs.
Re: Optimising ap_location_walk()
Posted by Graham Leggett <mi...@sharp.fm>.
On 24 Oct 2010, at 3:50 PM, Stefan Fritsch wrote:
> I am probably missing the obvious, but how do you intend to do the
> hash lookup? Given that <Location /app> also matches the dir /
> application, you may have to do N lookups for an url of length N.
Each location is parsed per whole directory, so the idea was to create
a tree of directories, so we're proportional to the depth of the tree,
not the numbers of locations.
> Have you considered using a trie or a binary search tree?
Not yet, but I will definitely take a look.
Regards,
Graham
--
Re: Optimising ap_location_walk()
Posted by Stefan Fritsch <sf...@sfritsch.de>.
On Sun, 24 Oct 2010, Graham Leggett wrote:
> I'm not keen to change the semantics at all, I'd rather like to speed up the
> array lookup from the linear search we do now.
>
> I went on a hunt for efficient string prefix matching algorithms, but that's
> led me into some heavy computer science theory where the bulk of the work was
> on prefix matching IP addresses rather than strings (which seems to be a
> problem that's received more attention).
>
> I think the hashtable approach would be reasonable, given that we have the
> option to pre-create the index at startup post_config.
I am probably missing the obvious, but how do you intend to do the hash
lookup? Given that <Location /app> also matches the dir /application, you
may have to do N lookups for an url of length N.
Have you considered using a trie or a binary search tree?
Re: Optimising ap_location_walk()
Posted by Graham Leggett <mi...@sharp.fm>.
On 23 Oct 2010, at 6:57 PM, Nick Kew wrote:
> Nice idea if you can come up with a clean design.
>
> We have a bit of a history of optimisation leading to breakage.
> It might be easier if combined with revisiting the semantics of
> subrequests and - especially - internal redirects. But that's going
> to have knock-on effects on a lot of core features, such as
> mod_dir, mod_alias, etc.
I'm not keen to change the semantics at all, I'd rather like to speed
up the array lookup from the linear search we do now.
I went on a hunt for efficient string prefix matching algorithms, but
that's led me into some heavy computer science theory where the bulk
of the work was on prefix matching IP addresses rather than strings
(which seems to be a problem that's received more attention).
I think the hashtable approach would be reasonable, given that we have
the option to pre-create the index at startup post_config.
Regards,
Graham
--
Re: Optimising ap_location_walk()
Posted by Nick Kew <ni...@webthing.com>.
On 23 Oct 2010, at 16:48, Graham Leggett wrote:
> Hi all,
>
> I am looking to improve per-request performance when you have an environment with many (thousands of) Location sections, and looking at ap_location_walk(), it looks like it is currently doing a simple linear search of locations on every request, which is far from ideal.
>
> Ideally, I'd like to create an index of the location sec_dir and sec_url array, by creating a tree of hashtables that will allow us to drill down to the relevant locations as quick as possible. This will also allow us to pre-merge many of the configurations at startup, instead of just at runtime (obviously because .htaccess is parsed at runtime we won't completely eliminate merging, but we will minimise it).
>
> If we're careful about what pools we use on startup, we can also free a lot of the memory used in the initial configuration scan, keeping a copy of the merged config, instead of a copy of each location's configs.
Nice idea if you can come up with a clean design.
We have a bit of a history of optimisation leading to breakage.
It might be easier if combined with revisiting the semantics of
subrequests and - especially - internal redirects. But that's going
to have knock-on effects on a lot of core features, such as
mod_dir, mod_alias, etc.
--
Nick Kew
Re: Another day, another veto (Was: Optimising ap_location_walk())
Posted by Graham Leggett <mi...@sharp.fm>.
On 25 Oct 2010, at 11:51 AM, William A. Rowe Jr. wrote:
>> Wow, the very first contribution to the discussion is a veto, and
>> you've vetoed code that
>> doesn't even exist yet. Crickey, the *ideas* behind what code might
>> be attempted haven't
>> been fleshed out yet and you're already waving a veto around.
>
> No, I voted against a concept (of throwing everything against the
> wall at once),
> that wasn't even a veto.
-1 in ASF speak is a veto. When people mention -1 without it being a
veto, they declare it so in brackets. Me personally, I just say "I
disagree" and leave it at that so there is no opportunity for confusion.
> If you can find 3 +1's, I already asserted that I'd reverse that
> position,
> as my primary issue is a lack of review.
A lack of review on a piece of code that doesn't exist yet, within a
discussion that hasn't finished yet, based on research that hasn't
been concluded yet.
The reason I initiated this discussion was that I was hoping that
people would highlight the potential impact of making a change here.
Obviously it's at the core, obviously it needs to be done carefully,
obviously servers with few locations cannot suffer for the benefit of
servers with many. In my experience with the httpd code, most
optimisations are really simple, and involve minimal code changes, a
testament to the careful design that has gone into this code at the
start. I see no reason why future code changes should be any
different. I am dismayed that people who would contribute to this
discussion are scared off by a waving veto.
> Right now, I'm staring at development in mod_cache that makes no
> sense,
> other than bandaids and bubblegum over operational flaws, while we
> have
> underlying logic between the datastore provider that thinks httpd, and
> the mod_cache protocol module which is dealing with storage questions.
> And you are asking to refactor *what* next? Eeek!
If you don't understand how the cache works, *ask*.
I designed the thing in the first place. I wrote mod_proxy for v2.0
from scratch in a Swedish hotel room when the filter stack first
appeared, and I took the original 1.3 cache out of mod_proxy into a
separate filter based framework, while others fleshed mod_cache out
until it worked. Can it be done better? Yes, thus the recent work on it.
For us, one of the world's biggest global media networks serving an
audience of tens of millions of people every hour, mod_cache sits in
front of our restful service layer, amongst many other places. We
learned three key things from this experience:
- Many developers for the web don't know what RFC2616 caching is.
Unlike us, starting out when the net ran slower than morse code, some
developers have never encountered a slow net connection before, and
have never had to know or care about a cache. We went on an education
drive, demonstrated the orders of magnitude improvement in speed that
HTTP caching offers in a restful environment, and now our developers
can't get enough of it.
- All the HTTP caches we tried, those built into load balancers, those
built into dedicated proxy servers, and mod_cache, have common edge
case bugs in them, particularly the notorious "leaking 304" problem
caused when developers don't take care of the caching headers they
send with a 304 Not Modified from their RFC2616 conditional request
supporting service. mod_cache's key bugs have been fixed, and it is
now fully RFC2616 compliant, not just selectively so.
- The httpd filter stack rocks, hard. The fact that we can now
selectively insert mod_cache anywhere in the filter stack, rocks even
harder. By "rocks" I mean "saves an enormous amount of money".
If you don't believe the mod_cache provider API is correct, then
identify specific things about the API you do not believe are correct
and allow me to fix them for you. Hand waving descriptions like
"bubblegum" and "operational flaws" are entirely unhelpful and
contribute nothing towards fixing the problems you believe exist.
Understand that wholesale massive reorganisation of the cache will
very likely not get the review it requires, just as you've pointed out
for ap_location_walk(), so distill them down into discrete changes
that can be applied in simple to understand patches.
Anything that involves making mod_cache.h's public interface smaller,
a big +1 to that. We can always refactor the cache internally at a
future date, we can't change a public API after 2.4 has been branched
(until v2.6, obviously). Anything that identifies functions we are
exporting unnecessarily, +1 to that too.
And if we can do the same thing on the excessively-public mod_proxy.h
header, +1 to that too.
> What I was trying to say, however untactfully, is that I wouldn't be
> very
> supportive of the same approach to core code. And reading the rest
> of your
> reply, I think we are of the same mind.
>
> FWIW I didn't conflate anything, I understood each of the aspects of
> the
> proposal you put forward as "one change". If you can break down your
> proposal into digestible pieces, I'll support any demonstrable
> worthwhile
> piece you put forward. I'm simply asking for no repeats of the
> current
> state of cache/proxy/ldap/etc etc. And I don't really think you
> disagree.
>
> Pick a piece to discuss, and I'm happy to respond.
Will follow this up in the original thread.
Regards,
Graham
--
Re: Another day, another veto (Was: Optimising ap_location_walk())
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On 10/25/2010 4:35 AM, Graham Leggett wrote:
> On 25 Oct 2010, at 12:18 AM, William A. Rowe Jr. wrote:
>
>> Consider this a pre -1 until enough eyes have
>> asserted that they have reviewed such a sandbox and declared it an improvement.
>
> Wow, the very first contribution to the discussion is a veto, and you've vetoed code that
> doesn't even exist yet. Crickey, the *ideas* behind what code might be attempted haven't
> been fleshed out yet and you're already waving a veto around.
No, I voted against a concept (of throwing everything against the wall at once),
that wasn't even a veto.
If you can find 3 +1's, I already asserted that I'd reverse that position,
as my primary issue is a lack of review.
Right now, I'm staring at development in mod_cache that makes no sense,
other than bandaids and bubblegum over operational flaws, while we have
underlying logic between the datastore provider that thinks httpd, and
the mod_cache protocol module which is dealing with storage questions.
And you are asking to refactor *what* next? Eeek!
What I was trying to say, however untactfully, is that I wouldn't be very
supportive of the same approach to core code. And reading the rest of your
reply, I think we are of the same mind.
FWIW I didn't conflate anything, I understood each of the aspects of the
proposal you put forward as "one change". If you can break down your
proposal into digestible pieces, I'll support any demonstrable worthwhile
piece you put forward. I'm simply asking for no repeats of the current
state of cache/proxy/ldap/etc etc. And I don't really think you disagree.
Pick a piece to discuss, and I'm happy to respond.
Another day, another veto (Was: Optimising ap_location_walk())
Posted by Graham Leggett <mi...@sharp.fm>.
On 25 Oct 2010, at 12:18 AM, William A. Rowe Jr. wrote:
> There are four factors here; 1) location matching, 2) merge caching,
> 3) premerging,
> and 4) path lookups. You've conflated these in a way that really
> concerns me.
No Bill, you've just conflated them. The rest of us are simply
discussing possibilities at this point, and I would appreciate it if
we could bring the discussion to a conclusion in a civil fashion.
> Consider this a pre -1 until enough eyes have
> asserted that they have reviewed such a sandbox and declared it an
> improvement.
Wow, the very first contribution to the discussion is a veto, and
you've vetoed code that doesn't even exist yet. Crickey, the *ideas*
behind what code might be attempted haven't been fleshed out yet and
you're already waving a veto around. Somehow what started as possible
ways for indexing a really inefficient lookup in an efficient way has
suddenly ballooned into a "massive reorganisation".
You've been asked before many times and you are now being asked yet
again, please please please stop playing the veto card. It is
destructive, demoralising, patronising, and chases potential
contributors away from this project.
I have no problem with a sandbox *if* the discussion turns towards a
major reorganisation. I don't have a problem with holding off until
httpd v3.0 *if* it turns out the discussion leads towards a major
change in semantics.
But lets have the discussion first please!
> Biting off all four at once will probably be a good way to attract
> insufficient
> review of the changes.
100% correct, which is why I had no intention of doing it. We are
short enough of reviewers as it is.
Regards,
Graham
--
Re: Optimising ap_location_walk()
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On 10/23/2010 10:48 AM, Graham Leggett wrote:
> Hi all,
>
> I am looking to improve per-request performance when you have an environment with many
> (thousands of) Location sections, and looking at ap_location_walk(), it looks like it is
> currently doing a simple linear search of locations on every request, which is far from
> ideal.
>
> Ideally, I'd like to create an index of the location sec_dir and sec_url array, by
> creating a tree of hashtables that will allow us to drill down to the relevant locations
> as quick as possible. This will also allow us to pre-merge many of the configurations at
> startup, instead of just at runtime (obviously because .htaccess is parsed at runtime we
> won't completely eliminate merging, but we will minimise it).
>
> If we're careful about what pools we use on startup, we can also free a lot of the memory
> used in the initial configuration scan, keeping a copy of the merged config, instead of a
> copy of each location's configs.
There are four factors here; 1) location matching, 2) merge caching, 3) premerging,
and 4) path lookups. You've conflated these in a way that really concerns me.
The requisite changes and improvements to merge caching and introduction of pre-merging
have me very concerned, because of the current state of other recently 'improved' code,
including cache, proxy and even ldap abstractions. I am not hopeful for a usable API
to all of this, although it both very much needed and an improved design would be most
welcome. I'd be very happy to have my concerns alleviated in a proof-of-concept
sandbox.
To the specific three issues;
1) I concur that <Location > should follow the hierarchical structure of http
resources. /app matching /application was always wrong. <LocationMatch >
can clearly preserve this behavior when it is desired. So Location should
pick up the precise mechanics of Directory matching. Sortation, too can be
very misleading in a world of Include'd sections; <LocationMatch > again
can preserve the arbitrary merging behavior when desired.
2) Merge caching API is absolutely fair game for improvement, but only to the
degree that it is an improvement. Recent API's don't seem to demonstrate
effective functional design and segregation. Looking forward to a solid
design proposal before this moves forward.
3) Predicated on the above, premerging is a lovely idea in theory and non-trivial
in practice. An effective design would facilitate premerges of groups (say
for example, <Directory />, <Directory /foo> and <Directory /foo/bar) but
back off as intervening merges occur; for example, some other <If > section
is triggered within the <Directory /foo> scope. The gains might be less than
you are expecting, but even combining the current config to the merged pair
of <Directory /> to <Directory /foo> could save cycles, if the search logic
were sufficiently optimal.
4) The hashtable is likely to be less efficient than a tree structure. The
number of hash constructions alone will be suboptimal; take a look at the
hashes applied in socache, which completely fall over on ASCII input.
I am very concerned that sufficient review occurs for such massive reorganization,
it took several years for the last thorough pass at optimization was fully
inspected small flaws were resolved. As Nick points out, this aspect of the design
is critical to httpd's operation. Consider this a pre -1 until enough eyes have
asserted that they have reviewed such a sandbox and declared it an improvement.
Biting off all four at once will probably be a good way to attract insufficient
review of the changes. So one approach might be;
1) refactor <Directory > to demonstrate that trees or hashes are more efficient
than the current segments lookup.
2) improve the optimization API to make more efficient use of premerges.
3) refactor <Location > to approximate <Directory >, perhaps abstracting these
both into common and reusable code.
4) demonstrate post-config premerges offer performance improvements without
sacrificing significant startup penalties.
That's only one way to dice up the problem, but I strongly suggest you dice it up
in the manner that makes the most sense to you. In any case, it isn't suitable
for presentation as a mongo-patch applied at trunk :)
I remain concerned that recent API's aren't really reusable, e.g. mod_disk_cache's
familiarity with the protocol. I'm strongly pondering a -1 to shipping 2.4.0 with
mod_cache.h presented as a public API (in any shared include/ tree). So I hope you
understand my hesitation about encouraging wholesale refactorings without seeing
some proof of usability. That said, the config section logic needs love, and if
someone is willing to offer that and demonstrate it in a sandbox, I will review it.
In all likelyhood, my vote will be that this won't belong in 2.4 or 3.0 (the 'next'
release) but in a subsequent major release.
Whenever this is refactored, recycling the "server dir" concept into just an
ordinary "dir" (a module may have more than one config section, of course, so
per-server variables are never merged per-dir), with one API, premerging for
virtual servers just as with the proposed premerging for location and directory,
would be a really valuable simplification.
Bill