[NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

This is just a prototype.  But I'm already seeing 50% speed improvements
in a limited benchmark... that's on static requests across loopback (no
keepalive).  I'm comparing against apache-nspr. 

I think this technique offers even more improvement for folks building
sites which require server-side negotiation (or just multiviews mapping to
single files so you can hide the extension), authentication (in many
forms), or proxying.  I'm fairly confident that if we use this technique
then we wouldn't be restricting the generality of apache.  In fact I think
this is a more simple way to look at server configuration. 

Anyhow, 50% isn't bad for several hours of hacking...

The source is at http://www.arctic.org/~dgaudet/apache/2.0/flow-00.tar.gz.
The README is copied below.

Feel free to suggest better terminology.  I chose the term "flow" because
of a particular method of doing high speed routing with packet filtering
in which the hardware is capable of very simple pattern matching against
packets.  When a packet doesn't match any of the patterns it is punted
to software and processed "slowly".  Software hopefully will be able to
add a pattern to the hardware cache to allow future packets in the same
"flow" of data to match at the hardware level.

Dean

HTTP FLOWS

A "flow" is a pattern that maps a request to a response.  At a minimum the
pattern includes a URL.  More complex patterns are possible, such as
patterns involving the various "Accept" headers, a Cookie header, or an
Authorization header. 

Pattern matching is very simple -- only exact matches are supported.

Patterns can be broken into three categories (possibly more):

    - object -- mapping URLs to filenames
    - negotiation -- distinguishing multiple mappings for the same URL
    - authorization -- permitting or forbidding a request based on the
	presence or absence of headers

In the interest of efficiency authorization patterns will be
shared between multiple flows.  It is easiest to think of this as an
implementation of the <Directory> containers.  If an entire tree /private
is protected by Basic auth, then there will be an authorization pattern
corresponding to /private.  Conceptually the pattern is essentially
a list of permitted Authorization headers, and request containing an
Authorization header in the list is permitted.

It is not feasible in general to pre-calculate all the flows for
a website.  In fact that's not interesting.  What is interesting is
dynamic calculation of flows.  Let's call a "flow cache" a set of flows
that describe a subset of the responses for a website.  If a flow is
in the cache then we know for certain what to respond with, and we can
immediately send the response without further processing.  If a flow
isn't in the cache then we need to perform more expensive processing,
and while doing that we may add a flow to the cache to handle future
requests matching similar patterns.

Consider this httpd.conf fragment:

    DocumentRoot /www/htdocs

    <Directory /www/htdocs/private>
	BrowserMatch Mozilla/2 go_away
	order allow,deny
	allow from all
	deny from env=go_away
    </Directory>

The directory container blocks access by User-Agent's containing
"Mozilla/2".  (Or something like that, can't be bothered to look up
the syntax.)

Initially the flow cache is empty.

Suppose we get a request for "/".  The flow processor can't find any
match, so it punts.  The full request processing is performed -- this is
pretty much the same as the current Apache API.  During this process we
calculate that the url "/" maps to the file "/www/htdocs/index.html",
and there are no alternatives to negotiate, and no authorization
to restrict access.  So we insert a flow with the pattern "/ ->
/www/htdocs/index.html" into the flow cache.

Actually we wouldn't quite insert that.  If we're running on WIN32
we'd insert a pattern "/" -> file_handle, where file_handle is an open
read-only handle for /www/htdocs/index.html.  This way we could call
TransmitFile directly.  Similarly on unix we'd use mmap().  Or maybe we'd
actually map it to a database object cached in memory... it's essentially
a mapping to a handler and an object.  Also as part of this map we insert
cached content-length, last-modified, and content-type values used to
build the response headers.

Similar when we get requests for "/logo.gif", or "/warez.txt" we can
insert them into the cache.

When a request comes for "/private/" we have to build an authentication
pattern.  An auth pattern is a list of headers and the values they must
match.  Suppose this first request for "/private/" comes from a mozilla/2
client.  We build an auth pattern for <Directory /www/htdocs/private>,
indicating that User-Agent must match one of {} ... must match an empty
list.  i.e. it will never match.  We will also build the "/private/"
-> /www/htdocs/private/index.html mapping, and it will refer to the
<Directory /www/htdocs/private> auth pattern.

If we then get a request for "/private/" from a "Lynx/2.6 libwww-FM/2.14"
client, it won't match in the flow cache.  But we will permit
it during the full request processing... and then we can insert
"Lynx/2.6 libwww-FM/2.14" into the User-Agent list for <Directory
/www/htdocs/private>.  Subsequent requests from that same user agent
to /private/ will match in the flow-cache and be served without full
processing.

We can continue this way, adding urls such as "/private/part.gif",
and "/private/memo.html".  They all share the same auth pattern, which
means they share updates to the list of permitted User-Agents.

Similar techniques can be used to build negotiation patterns.  We take
the simple approach in every case.  Rather than cache complex expressions
(such as the list of all negotiation possibilities for an object, with
q-values and whatever else), we cache the exact set of headers which are
acceptable and match them.  Anything which doesn't match goes through
the full processing (and that will insert a record to help match the
next time).  Similar to auth patterns, some effort should be put into
"coalescing" negotiation patterns.

For example, Navigator sends the same Accept/Accept-Language headers
on almost every request (the exact contents can be modified by the
user...).  We only need to recognize that set of headers, and then
any server negotiation involving those headers can refer to the
common pattern.

It's my feeling that a large percentage of requests fit into the above
mold.  There's some obvious extensions too, such as negative caching --
for example, a pattern denying an IP address could be a map to an error
handler and an error code.

WHY WHY WHY?

Why do we want to do all this?  Speed.  The prototype implementation
here is 40% to 50% faster than apache-nspr... this was with a hardwired
test across loopback, but without keep-alive.

Here's two reasons I can think of for the speed increase:

- Simplistic hand coded parser.  The parser doesn't handle all cases,
  it shouldn't have to.  It bails to the full request parser in any
  case it can't handle.  In fact it's so simple that it doesn't
  even have buffered i/o -- if the request isn't in the first packet
  sent from the client it bails and passes it down to full request
  parsing.

- Fewer threads.  The prototype has two threads.  One accepts
  connections, reads requests, and parses them.  The other handles
  sending responses.  Fewer threads means fewer context switches.
  But more importantly it means less memory required for things such
  as stacks... and that results in less L1/L2 cache impact... which
  can have a dramatic effect on performance.

CAVEATS

The prototype has a pre-seeded flow cache.  In practice there are
locking issues involved with seeding the flow cache.  Using a message
queue will allow us to batch updates and hopefully incur less locking
overhead.

The prototype and the discussion above don't deal with cache coherency.
This is an area I'm still working on.  A rough first approximation is
to flush the entire cache periodically.  There's a bunch of other
options... each pattern has different criteria for coherency.

Obviously doing this will require API changes, and configuration language
changes.  The above example would be extremely difficult to "compile"
into the form required for the flow cache.  But I think we can make a
user-friendly language that is easily compilable into flows on the fly.

Re: [NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

On Sun, 7 Jun 1998, Ben Laurie wrote:

> Dean Gaudet wrote:
>
> > Well the flow cache contains only URLs that have been seen before.  It
> > would be the module's responsibility to either negatively cache the URL
> > (indicating it should always bounce to full processing), or to cache the
> > URL along with an auth pattern that has exactly the set of allowed
> > headers.
> 
> Well, yes, but that isn't what you saud. You said this:
> 
> "We can continue this way, adding urls such as "/private/part.gif", and
> "/private/memo.html".  They all share the same auth pattern, which means
> they share updates to the list of permitted User-Agents."
> 
> I'm saying you can't, in general, know this. I think!

No, not in complete generality.  But we lose nothing by adding a
restriction that says "if the same directory containers apply to two URLs,
then their auth information is equivalent".  That doesn't restrict what
people can do, it just structures how they do it. 

If a module author wants to write some directive that amounts to "protect
this one file in this special way", they can.  But they shouldn't -- they
don't have to, because we already provide the <Directory> and <File>
primitives which can be used to restrict protection to that one file.  If
the author were to code using our primitives things work fine.

Of course auth could be a convoluted function of the URL and a header.  If
that's the case the module could build a container for each url and it
would look like unshared auth.  Or the module could be deemed incompatible
with flows and no flows would be cached.  They take the performance
penalty.  We can give modules the choice to let a URL be flow cached or
not... if the module knows that the URL has weird auth properties then it
should reject attempts to flow cache it. 

> > If a request comes in with a header Foobar that's not listed in the auth
> > pattern it's bounced... so suppose we have a way for the core to ask the
> > question "hey, anyone interested in the Foobar header?"  If nobody speaks
> > up, the core can put the header into the auth pattern saying "any value
> > acceptable".  This is what I expect to happen by default with things such
> > as User-Agent.
> 
> Snag is, you are still assuming headers are orthogonal. I don't see that
> this is the case, in general. OK, you can try to impose it as a
> condition of using the architecture, but I think it will be difficult to
> enforce (against accidental breakage) and even more difficult to debug
> when non-orthogonality slips in.
> 
> Perhaps I worry too much.

No no I worried about that for a long time too... but after studying
HTTP/1.1 again, case by case, I convinced myself that headers are
orthogonal.  Perhaps we can't flow cache extensions to HTTP/1.1, but I'm
OK with that.  We'll still have a completely general back-end... the
front-end needs only to recognize that it's in over its head and bounce
the request.

What I'm worried about more right now is memory blowup... like I really
don't want to have to do case insensitive comparisons.  I am cursing the
definition of "literal" in RFC2068 -- case-insensitive, that is a total
waste of time... and it's not even consistent, methods such as GET are
case-sensitive.  So if we cache "Accept: image/*", we may later also cache
"Accept: IMAGE/*"... and you can imagine all the other permutations.

Case isn't the only thing that can cause blowup... I'm suggesting that we
cache "Accept: text/*" and "Accept: text/html, text/*" separately.  And
with my current implementation I'd say we would cache "Accept: text/*" and
"Accept: text/* " separately -- notice the extra space in the second one.

> I agree that you can go a long way with this kind of stuff before "too
> big" becomes a real issue. Assuming, that is, that you have at least a
> mildly complex config. If my config consists only of a DocumentRoot,
> we're doing a great deal of work to no real affect!

Well... a DocumentRoot only config would have only one auth section... and
a pretty light one at that... yeah we could be doing more work than plain
old apache does.

I'm thinking that for header names we can use a tool like gperf to
generate a perfect hash.  We could ignore non-HTTP/1.1 headers until a
module says "the header Foobar is important".  It's not unreasonable to
ask modules to indicate to the core what headers they're interested in.
(It is unreasonable to store data in a header name... like X-Comment-1,
X-Comment-2, ... I don't care if a module wants to do that and cause
"auth" to happen... they can just not have any flow caching.)

Consider a typical request from navigator... it has:  Accept,
Accept-Charset, Accept-Language, Connection, Host, and User-Agent.  If
you're not using multiviews, you don't have negotiation, so we'll end up
ignoring all Accept-Foo headers.  Connection we have to deal with.  Host
is part of the URL.  The only "auth" type header in this request is
User-Agent... and in the auth pattern we'd see that any User-Agent is
acceptable. 

Maybe later we'd get requests containing From or Via, and we'd have other
light lookups for them too. 

Now, apache's current code when it sees these goes off and does getword()s
which copy the header name (and contents) out of the input buffer into
memory.  Then that gets put into a linear table.  This happens for all
headers, whether they're interesting or not.  In my prototype I tried to
never copy anything out of the input buffer -- instead I build up a list
of a_substrings which are just start/end pointers.  I'm planning on not
having nul-terminated strings in the front end, because it is just not
worth it to copy things just for the nul-termination.

Compared to apache's current code I think the flow cache would still be a
win on a DocumentRoot-only server.  We can improve the core though. 

Dean

Re: [NEWTOY] flow-00

[Ben Laurie <be...@algroup.co.uk>]

Dean Gaudet wrote:
> 
> On Sun, 7 Jun 1998, Ben Laurie wrote:
> 
> > Dean Gaudet wrote:
> >
> > [snip loads of cool stuff]
> >
> > > We can continue this way, adding urls such as "/private/part.gif",
> > > and "/private/memo.html".  They all share the same auth pattern, which
> > > means they share updates to the list of permitted User-Agents.
> >
> > Thus makes me nervous. How do you know they share the same auth pattern?
> 
> Hmm.  Ignore .htaccess files for now (not too hard to pull into this
> scheme).  Let U be the set of all dir/loc/file containers.  Remember that
> dir/loc/file have an ordering.  During merge we construct a subset S of U.
> Since the containers are ordered, S uniquely identifies the containers
> that apply to this request... and any other request that has the same S
> can share the same auth pattern.
> 
> We need an efficient representation for S.
> 
> For .htaccess files we parse and cache them as we see them (this is
> caching in the back-end webserver).  This lets us assign them to the
> universe U, and lets us build auth patterns based on them.  If the
> htaccess cache needs to have a record removed, we need to update the flow
> cache...

I'm with you up to this point. Just about.

> > Suppose I have a module installed that does cunning auth based on the
> > URL in a way that doesn't use Directory/Location et al.? Or that
> > processes any headers in a non-orthogonal way.
> 
> Well the flow cache contains only URLs that have been seen before.  It
> would be the module's responsibility to either negatively cache the URL
> (indicating it should always bounce to full processing), or to cache the
> URL along with an auth pattern that has exactly the set of allowed
> headers.

Well, yes, but that isn't what you saud. You said this:

"We can continue this way, adding urls such as "/private/part.gif", and
"/private/memo.html".  They all share the same auth pattern, which means
they share updates to the list of permitted User-Agents."

I'm saying you can't, in general, know this. I think!

> If a request comes in with a header Foobar that's not listed in the auth
> pattern it's bounced... so suppose we have a way for the core to ask the
> question "hey, anyone interested in the Foobar header?"  If nobody speaks
> up, the core can put the header into the auth pattern saying "any value
> acceptable".  This is what I expect to happen by default with things such
> as User-Agent.

Snag is, you are still assuming headers are orthogonal. I don't see that
this is the case, in general. OK, you can try to impose it as a
condition of using the architecture, but I think it will be difficult to
enforce (against accidental breakage) and even more difficult to debug
when non-orthogonality slips in.

Perhaps I worry too much.

> 
> > And - small cache. At what point does the cost of searching the cache
> > exceed the cost of evaluating things in the standard way?
> 
> Right.  I'm not sure.  All strings are opaque objects in this cache --
> since patterns are simple exact matches (or a wildcard "anything matches")
> we can aggressively hash the strings.  The flow "engine" doesn't need to
> analyse any string contents, it only needs to hash things.  So it's really
> just a standard string -> integer lookup problem.
> 
> Suppose we used B trees (or extensible hashes, doesn't matter).  What I'm
> thinking is to have a single B tree for each header that contains the
> union of all the values in all the auth patterns (this is an optimization
> to save memory, localize data, and amortize the cost of tree maintenance).
> The B tree is a mapping from string to unique integer.  Then the auth
> patterns are each a set of acceptable integers.
> 
> But you're right, this is where I need to improve the prototype next...

I agree that you can go a long way with this kind of stuff before "too
big" becomes a real issue. Assuming, that is, that you have at least a
mildly complex config. If my config consists only of a DocumentRoot,
we're doing a great deal of work to no real affect!

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/

WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

Re: [NEWTOY] flow-00

[Ben Laurie <be...@algroup.co.uk>]

Dean Gaudet wrote:
> 
> Oh it may be obvious, but I tend to think of the Request-URI and the
> client IP address as "headers"... and in that sense anything I've said
> about headers (for storage/matching/whatever) applies to them.

Well, it was obvious to me, at least, but it never hurts to point out
your assumptions.

> The flow engine would not perform any DNS lookups.  So it can't "deny from
> *.mil" for example.  But it can deny from specific IP addresses... so the
> back-end does the lookup and inserts an IP address into the auth record.
> 
> I can't figure out a way to support rfc1413 crud at the flow level, it is
> a per-connection value that is expensive to calculate.  I've been ignoring
> it.  Hey Doug, can you give us a brief overview on how the DCE stuff works
> -- is it similar to rfc1413 in that when you get a connection you have to
> go do an expensive lookup to determine who the connection is?
> 
> And I suppose I should look at digest auth... I have a suspicion my
> current model doesn't handle it...  and I'm not familiar enough with SSL
> either to know if there's something inexpensive that can be cached in the
> front-end.

Digest auth is just a way of checking that someone has entered a
particular password. The particular string they use to prove that will
vary with time, which may cause you a problem, but if you cache the
password they need to check against, that would be all the info needed
(at least, for the kind of digest auth I'd implement - i.e. one that
didn't rely on state in the server).

SSL. Hmm. Well, if client certs are used, they will remain the same if
the session ID is the same, so you could cache stuff based on the
session ID (reusing session IDs is a considerable performance
improvement, too). If client certs are not used, there isn't anything
interesting to say about the connection anyway.

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/

WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

Re: [NEWTOY] flow-00

[Ben Laurie <be...@algroup.co.uk>]

Dean Gaudet wrote:
> 
> On Sun, 7 Jun 1998, Ben Laurie wrote:
> 
> > Dean Gaudet wrote:
> > > Too bad digest auth doesn't quite fit the entire mold.  The flow engine
> > > would have to do the digest calculations for each (affected) request in
> > > order to gain any benefits.  I was hoping to avoid the need to extend the
> > > code of the flow engine -- I want it to be exclusively data driven... oh
> > > well.
> >
> > The digest only changes when the nonce changes. Since the obvious thing
> > to do is to make nonces survive for a certain amount of time, the digest
> > could be cached until it expired, at which point the cache gets
> > discarded, a new nonce is generated (coincidentally) and when the
> > response comes back, the new response can be cached. Or am I missing
> > something?
> 
> The digest is a function of (username, password, nonce, Request-Method,
> Request-URI)... so we'd have to cache a digest for each user for each
> url... we couldn't share the auth pattern like we can for basic auth.
> Users tend not to re-request the same URL frequently enough for it to be
> worth the effort of saving their digest for that url.  That's why I was
> suggesting we'd have to calculate the digest on the fly.

Agreed.

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/

WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

Re: [NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

On Sun, 7 Jun 1998, Ben Laurie wrote:

> Dean Gaudet wrote:
> > Too bad digest auth doesn't quite fit the entire mold.  The flow engine
> > would have to do the digest calculations for each (affected) request in
> > order to gain any benefits.  I was hoping to avoid the need to extend the
> > code of the flow engine -- I want it to be exclusively data driven... oh
> > well.
> 
> The digest only changes when the nonce changes. Since the obvious thing
> to do is to make nonces survive for a certain amount of time, the digest
> could be cached until it expired, at which point the cache gets
> discarded, a new nonce is generated (coincidentally) and when the
> response comes back, the new response can be cached. Or am I missing
> something?

The digest is a function of (username, password, nonce, Request-Method,
Request-URI)... so we'd have to cache a digest for each user for each
url... we couldn't share the auth pattern like we can for basic auth. 
Users tend not to re-request the same URL frequently enough for it to be
worth the effort of saving their digest for that url.  That's why I was
suggesting we'd have to calculate the digest on the fly.

Dean

Re: [NEWTOY] flow-00

[Ben Laurie <be...@algroup.co.uk>]

Dean Gaudet wrote:
> 
> On Sun, 7 Jun 1998, Dean Gaudet wrote:
> 
> > [rfc1413, DCE, SSL ...]
> 
> Excuse me while I think out loud...  I just realised that these systems
> all share a common property -- there is some out of band processing that
> can occur before any HTTP processing happens.  Maybe they can be built as
> an i/o layer.  So the flow engine actually accept()s a socket that's been
> slightly processed by another layer first (i.e. ssl).  The other layer may
> have some out-of-band information to communicate... but I think I'm OK to
> think of it all has a "header".

I agree.

> Too bad digest auth doesn't quite fit the entire mold.  The flow engine
> would have to do the digest calculations for each (affected) request in
> order to gain any benefits.  I was hoping to avoid the need to extend the
> code of the flow engine -- I want it to be exclusively data driven... oh
> well.

The digest only changes when the nonce changes. Since the obvious thing
to do is to make nonces survive for a certain amount of time, the digest
could be cached until it expired, at which point the cache gets
discarded, a new nonce is generated (coincidentally) and when the
response comes back, the new response can be cached. Or am I missing
something?

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/

WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

Re: [NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

On Sun, 7 Jun 1998, Dean Gaudet wrote:

> [rfc1413, DCE, SSL ...]

Excuse me while I think out loud...  I just realised that these systems
all share a common property -- there is some out of band processing that
can occur before any HTTP processing happens.  Maybe they can be built as
an i/o layer.  So the flow engine actually accept()s a socket that's been
slightly processed by another layer first (i.e. ssl).  The other layer may
have some out-of-band information to communicate... but I think I'm OK to
think of it all has a "header". 

Too bad digest auth doesn't quite fit the entire mold.  The flow engine
would have to do the digest calculations for each (affected) request in
order to gain any benefits.  I was hoping to avoid the need to extend the
code of the flow engine -- I want it to be exclusively data driven... oh
well.

Dean

Re: [NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

Oh it may be obvious, but I tend to think of the Request-URI and the
client IP address as "headers"... and in that sense anything I've said
about headers (for storage/matching/whatever) applies to them. 

The flow engine would not perform any DNS lookups.  So it can't "deny from
*.mil" for example.  But it can deny from specific IP addresses... so the
back-end does the lookup and inserts an IP address into the auth record.

I can't figure out a way to support rfc1413 crud at the flow level, it is
a per-connection value that is expensive to calculate.  I've been ignoring
it.  Hey Doug, can you give us a brief overview on how the DCE stuff works
-- is it similar to rfc1413 in that when you get a connection you have to
go do an expensive lookup to determine who the connection is?

And I suppose I should look at digest auth... I have a suspicion my
current model doesn't handle it...  and I'm not familiar enough with SSL
either to know if there's something inexpensive that can be cached in the
front-end. 

Dean

Re: [NEWTOY] flow-00

[Dean Gaudet <dg...@arctic.org>]

On Sun, 7 Jun 1998, Ben Laurie wrote:

> Dean Gaudet wrote:
> 
> [snip loads of cool stuff]
> 
> > We can continue this way, adding urls such as "/private/part.gif",
> > and "/private/memo.html".  They all share the same auth pattern, which
> > means they share updates to the list of permitted User-Agents.
> 
> Thus makes me nervous. How do you know they share the same auth pattern?

Hmm.  Ignore .htaccess files for now (not too hard to pull into this
scheme).  Let U be the set of all dir/loc/file containers.  Remember that
dir/loc/file have an ordering.  During merge we construct a subset S of U. 
Since the containers are ordered, S uniquely identifies the containers
that apply to this request... and any other request that has the same S
can share the same auth pattern. 

We need an efficient representation for S. 

For .htaccess files we parse and cache them as we see them (this is
caching in the back-end webserver).  This lets us assign them to the
universe U, and lets us build auth patterns based on them.  If the
htaccess cache needs to have a record removed, we need to update the flow
cache... 

> Suppose I have a module installed that does cunning auth based on the
> URL in a way that doesn't use Directory/Location et al.? Or that
> processes any headers in a non-orthogonal way.

Well the flow cache contains only URLs that have been seen before.  It
would be the module's responsibility to either negatively cache the URL
(indicating it should always bounce to full processing), or to cache the
URL along with an auth pattern that has exactly the set of allowed
headers. 

If a request comes in with a header Foobar that's not listed in the auth
pattern it's bounced... so suppose we have a way for the core to ask the
question "hey, anyone interested in the Foobar header?"  If nobody speaks
up, the core can put the header into the auth pattern saying "any value
acceptable".  This is what I expect to happen by default with things such
as User-Agent.

> And - small cache. At what point does the cost of searching the cache
> exceed the cost of evaluating things in the standard way?

Right.  I'm not sure.  All strings are opaque objects in this cache --
since patterns are simple exact matches (or a wildcard "anything matches")
we can aggressively hash the strings.  The flow "engine" doesn't need to
analyse any string contents, it only needs to hash things.  So it's really
just a standard string -> integer lookup problem.

Suppose we used B trees (or extensible hashes, doesn't matter).  What I'm
thinking is to have a single B tree for each header that contains the
union of all the values in all the auth patterns (this is an optimization
to save memory, localize data, and amortize the cost of tree maintenance).
The B tree is a mapping from string to unique integer.  Then the auth
patterns are each a set of acceptable integers. 

But you're right, this is where I need to improve the prototype next... 

Dean

Re: [NEWTOY] flow-00

[Ben Laurie <be...@algroup.co.uk>]

Dean Gaudet wrote:

[snip loads of cool stuff]

> We can continue this way, adding urls such as "/private/part.gif",
> and "/private/memo.html".  They all share the same auth pattern, which
> means they share updates to the list of permitted User-Agents.

Thus makes me nervous. How do you know they share the same auth pattern?
Suppose I have a module installed that does cunning auth based on the
URL in a way that doesn't use Directory/Location et al.? Or that
processes any headers in a non-orthogonal way.

[more snippage]

> WHY WHY WHY?
> 
> Why do we want to do all this?  Speed.  The prototype implementation
> here is 40% to 50% faster than apache-nspr... this was with a hardwired
> test across loopback, but without keep-alive.
> 
> Here's two reasons I can think of for the speed increase:
> 
> - Simplistic hand coded parser.  The parser doesn't handle all cases,
>   it shouldn't have to.  It bails to the full request parser in any
>   case it can't handle.  In fact it's so simple that it doesn't
>   even have buffered i/o -- if the request isn't in the first packet
>   sent from the client it bails and passes it down to full request
>   parsing.
> 
> - Fewer threads.  The prototype has two threads.  One accepts
>   connections, reads requests, and parses them.  The other handles
>   sending responses.  Fewer threads means fewer context switches.
>   But more importantly it means less memory required for things such
>   as stacks... and that results in less L1/L2 cache impact... which
>   can have a dramatic effect on performance.

And - small cache. At what point does the cost of searching the cache
exceed the cost of evaluating things in the standard way?

Cheers,

Ben.

-- 
Ben Laurie            |Phone: +44 (181) 735 0686| Apache Group member
Freelance Consultant  |Fax:   +44 (181) 735 0689|http://www.apache.org/
and Technical Director|Email: ben@algroup.co.uk |
A.L. Digital Ltd,     |Apache-SSL author     http://www.apache-ssl.org/
London, England.      |"Apache: TDG" http://www.ora.com/catalog/apache/

WE'RE RECRUITING! http://www.aldigital.co.uk/recruit/

Re: [NEWTOY] flow-00

["James H. Cloos Jr." <cl...@jhcloos.com>]

I love this list.

All you have to do is think about something hard enough for a while
and someone comes up with a cool name for it and does the work for
you. :)

Anyway, this concept, when fleshed out, eliminaties many -- if not
most -- of the reasons to stick a Squid accelerator in front of an
Apache server.  Some reasons remain (eg one box fronting many) but
not too many.

-JimC
-- 
James H. Cloos, Jr.
<cl...@jhcloos.com>