You are viewing a plain text version of this content. The canonical link for it is here.
Posted to general@commons.apache.org by gs...@apache.org on 2003/09/17 09:04:28 UTC
svn commit: rev 39 - commons/serf/trunk/docs
Author: gstein
Date: Sat Jan 4 16:37:13 2003
New Revision: 39
Added:
commons/serf/trunk/docs/processing.txt
Log:
ka-thunk!
Added: commons/serf/trunk/docs/processing.txt
==============================================================================
--- (empty file)
+++ commons/serf/trunk/docs/processing.txt Sat Jan 4 16:37:13 2003
@@ -0,0 +1,475 @@
+Last modified at [$Date: 2003/01/05 00:37:13 $] -*-text-*-
+
+
+NOTES ON (A PROPOSED) PROCESSING MODEL
+--------------------------------------
+
+This is a quite transcription of some of the ideas generated during
+the ApacheCon back in November 2002. It deals with a new bucket model
+(elimination of brigades) and a new filtering model (elimination of
+most types of filters). The hope is a simpler processing model which
+can also more easily support zero-copy data processing, network
+pushback, flexible content management, etc.
+
+
+BUCKET/BRIGADE SIMPLIFICATION
+-----------------------------
+
+The idea here is to eliminate the bucket brigade and move to passing
+single buckets around. A particular bucket type is an "aggregate"
+bucket, or "list" bucket. It refers to a list of sub-buckets,
+representing the linear flattening of those buckets.
+
+Note the aggregate could be implemented where another aggregate may be
+a child, or it could "pre-flatten" that child into itself, thus
+maintaining just one level of child buckets.
+
+This model should help to avoid the complexity of dealing with two
+types of structures that we see in httpd: brigades and traversing
+brigades to operate on buckets. The data model here is a "single
+bucket". The notion of aggregate buckets is encapsulated behind the
+bucket type's vtable of operations.
+
+As a quick check of validity, we can look at the brigade-based APIs
+present in apr_buckets.h:
+
+APR_BRIGADE_EMPTY
+ bucket->len == 0 (this gets a bit more difficult if ->len == 1)
+
+APR_BRIGADE_FIRST
+APR_BRIGADE_LAST
+APR_BRIGADE_FOREACH
+APR_BRIGADE_NEXT
+APR_BRIGADE_PREV
+ n/a
+
+APR_BRIGADE_INSERT_HEAD
+APR_BRIGADE_INSERT_TAIL
+APR_BRIGADE_PREPEND
+APR_BRIGADE_CONCAT
+ construct a new aggregate bucket of two items
+
+APR_BUCKET_INSERT_BEFORE
+APR_BUCKET_INSERT_AFTER
+ kind of n/a. split the bucket at pos=N and reassemble via an
+ aggregate bucket.
+
+APR_BUCKET_REMOVE
+ kind of n/a. split at pos=N and pos=M and reassemble the outer
+ pieces via an aggregate.
+
+apr_brigade_create
+ create whatever bucket
+
+apr_brigade_destroy
+ just destroy the bucket
+
+apr_brigade_cleanup
+ kind of n/a. probably replace with bucket destruction.
+
+apr_brigade_split
+apr_brigade_partition
+ split the bucket
+
+apr_brigade_consume (not actually imp'd)
+ buckets will have this as part of their standard vtable API
+
+apr_brigade_length
+ bucket->len
+ (haven't thought how to handle the read_all flag here...)
+
+apr_brigade_flatten
+apr_brigade_pflatten
+ n/a? a bucket read doesn't necessarily return "all" of a bucket's
+ data (think an aggregate wanting to return only whatever is in the
+ first bucket)
+
+ maybe a vtable API? e.g. a different read style
+
+apr_brigade_split_line
+ been thinking that a bucket read could say "give me a line". and
+ there are a couple read methods: peek or consume
+
+apr_brigade_to_iovec
+ a particular bucket-read style?
+
+apr_brigade_vputstrs
+apr_brigade_write
+apr_brigade_writev
+apr_brigade_puts
+apr_brigade_putc
+apr_brigade_putstrs
+apr_brigade_printf
+apr_brigade_vprintf
+ imp a new helper function around a bucket->append(bucket) API. we
+ may also want bucket->append_bytes(buf, len) API
+
+
+THE NEW BUCKETS
+---------------
+
+These will be very similar in style to current buckets. The bucket
+will have a "type" pointer which will contain type-based information
+and a vtable.
+
+Bucket lengths will have a custom type:
+
+ typedef apr_int64_t serf_csize_t; /* serf's content size type */
+
+Note these are not based on platform specifics. This implies that (on
+certain platforms) a bucket might not be able to hold everything that
+a user wants to throw at it (think: spooling 10G from a socket to a
+file in a 32-bit filesystem; the socket is fine, but the file is
+toast).
+
+Some random notes:
+
+* Buckets have a non-destructive read ("peek") and a destructive read
+ ("consume"). The latter is an optimization to avoid
+ read/split/destroy triples. The non-destructive read can take an
+ offset. In the case of an aggregate, the offset allows for reading
+ "further into" the aggregate bucket. The destructive read does not
+ require an offset -- you can only consume from the front.
+
+* Reading has some basic types: read N bytes, read a line, and read an
+ iovec. you can also read for a specific bucket type, such as "give
+ me a FILE bucket". This allows a network layer to attempt
+ sendfile-based optimizations.
+
+ It isn't clear whether to read for a bucket type and then tear apart
+ that bucket for the descriptor, or to have read "styles" which are
+ distinct from buckets. e.g. "give me a descriptor [into this
+ standard read structure] if you have it"
+
+ Read negotiation would be nice: a heap bucket *could* return a file
+ descriptor, but if the caller is also fine with a ptr/len pair, then
+ the bucket should prefer the latter.
+
+* One particular read style is to read header/trailer iovecs and a
+ file descriptor (to match the semantics of apr_socket_sendfile).
+
+* There should probably be a non-destructive read operation that
+ "scans" for a particular bucket/read type. This allows a client to
+ say "give me the HTTP headers" and the (aggregate) bucket will find
+ that within its child buckets.
+
+* Ref-counting buckets are probably still important. The notion of an
+ underlying, shared mmap, pipe, file, or socket object is still
+ important. When a bucket gets split, another reference to that
+ underlying object is created.
+
+* Pipe and socket buckets should have a notion of "data not ready" in
+ the sense that they have previously been split() and the *other*
+ bucket needs to read its data before "this" bucket can read its
+ own. For example, you split A into a 1k bucket B and an unbounded
+ bucket C. reading from C returns "not ready" until B's 1k of data
+ has been read. This implies some level of coordination between the
+ two buckets.
+
+ Destroying buckets becomes a bit more tricky: if bucket B has not
+ read its data, should it read it at destruction time? It is entirely
+ possible that only B is being thrown out, and C still wants to stick
+ around. Alternatively, both buckets will be destroyed so B should
+ not do any reading. This is easily solved: B already has a pointer
+ to C to enable it to say "I'm done reading, you've got the pipe
+ now". That same pointer can be used to tell C "skip N bytes before
+ reading." Now, when C is asked to read, it will skip N bytes, then
+ do the read. But if C is also being destroyed, then it just goes
+ away. (of course, C may need to notify somebody also)
+
+ This coordination comes into play at the HTTP connection/request
+ level. The connection will have a socket bucket, which eventually
+ gets split at the HTTP request boundary (into socket bucket R and
+ socket bucket C). If the request is thrown away before reading the
+ body (bucket R), then R will notify C to skip N bytes. Of course, if
+ the request was chunked, then more work is necessary to consume the
+ request.
+
+* Buckets are not required to be thread-safe. We may want the type
+ descriptor to mention thread safety, though:
+
+ 1. not thread-safe
+ 2. thread-safe for reading
+ 3. thread-safe for read/write
+
+ Using buckets of type 2 or 3 for a cache would be ideal. If it is
+ type 2, then you instantiate the bucket on a single thread, but when
+ it is "ready" it can be moved into a multithread environment for
+ reading.
+
+ Buckets must not have "thread affinity". The application may want to
+ use the buckets on multiple threads.
+ ### if some bucket types *will* have thread affinity, then maybe we
+ ### want a flag in the bucket type to denote this
+
+* Buckets should be tagged with notions of content type, charset and
+ charset encoding, language, etc. Essentially, these are equivalent
+ to HTTP's Content-* headers.
+
+ For this, a hash table would be nice. We should extend the hash API
+ to allow lookups based on a hash key (so we don't have to perform
+ the hash function; this turns lookups in simple array lookups). The
+ hash keys can then be predefined token values for common content
+ metadata:
+
+ #define SERF_CONTENT_TYPE 1009
+ #define SERF_CONTENT_ENCODING 3001 /* charset is implied */
+ #define SERF_CONTENT_LANG 5003
+ #define SERF_CONTENT_MD5 7001 /* precomputed MD5 hash */
+
+ Note that primes are used to help the hashing function which applies
+ a modulus against the hash table size.
+
+ Arbitrary metadata can be inserted into the bucket's metadata hash
+ table. The hash table starts as NULL and is lazily created.
+
+ To avoid memory explosion, we may want to consider moving some
+ critical content metadata "out" of the hash and into bucket members
+ or find some way to share metadata hashes across buckets. For
+ example, the system might have a registry of descriptors:
+
+ 0: text/plain, iso-8859-1, en
+ 1: text/html, iso-8859-1, en
+ 2: text/html, utf-8, en
+ 3: text/html, utf-8, fr
+
+ The buckets can then keep a simple integer index into this shared
+ registry.
+
+* Buckets should have a notion of lifetime. Since this is presumably
+ built on APR's memory system, this lifetime would be denoted by a
+ pool. This takes over the role of the brigade's pool.
+
+ A NULL value for the pool could imply one of two things: immortal or
+ transient.
+ ### I'm not sure if it can mean "either" or whether one meaning
+ ### should be decided, and which of the two that would be. there is
+ ### also the notion of heap-based: I exist until you kill me.
+
+ Note that the brigade "compressed" the number of cleanups that had
+ to be registered with a pool. We want to be very careful about
+ registering cleanups for each and every bucket. If we find that we
+ must register cleanups for certain bucket types, then we should also
+ find a way to have the aggregate bucket coalesce those. (although by
+ the time you've registered a cleanup, you've already consumed pool
+ memory which cannot be reused; a reusable memory system for bucket
+ cleanups may be necessary if it comes to that)
+
+ ### much of this is based on where buckets are allocated from. it
+ ### probably continues to make sense to use a bucket allocator
+ ### system and to alloc them from the heap.
+
+* Buckets have an "append" function which takes another bucket. The
+ vtable slot can refer to a default function which simply aggregates
+ the two buckets. However, a HEAP bucket may have overallocated, may
+ detect the new bucket is a HEAP bucket, too, and can coalesce the
+ two buckets.
+
+* Buckets have an "append_bytes" function to append raw bytes. Like
+ the append function, a default is provided which simply copies the
+ bytes into the heap and aggregates the two buckets. Specific bucket
+ types may copy the bytes into themselves.
+
+ It would probably be a good idea to somehow denote the lifetime of
+ the bytes which are passed. "immortal" bytes probably should not be
+ copied. "transient" bytes should always be copied.
+
+ ### a simplification may be that this function always copies the
+ ### bytes. that is just part of its semantics. if you want to more
+ ### finely manage the copy behavior, then wrap a bucket around the
+ ### bytes first.
+
+????
+
+
+NEW STYLE FILTERS
+-----------------
+
+The filters as implemented by Apache httpd are not used. Instead, the
+idea is to "wrap" a bucket with a new bucket which implements the
+filter algorithm.
+
+
+ NETWORK <---/ reads /---------\
+ |
+ +--------------------------+
+ | HTTP chunker |
+ | +---------------------+ |
+ +--+ C-L +-+
+ | +----------------+ |
+ +--+ GZIP +-+
+ | +-----------+ |
+ +--+ SSI +-+
+ | +------+ |
+ +--+ File +-+
+ +------+
+
+In this example, the output layer loops while consuming data from the
+bucket and writing it to the network (and optimizing with sendfile()
+when it can get a file descriptor).
+
+Note that the network layer is reading/writing. This is a "pull data,
+write to network" style rather than something pushing data at the
+network. However, this *can* be viewed as a push style. Somebody
+pushed a single bucket ("HTTP chunker") at the network layer. The
+network decides whether it can sendfile or whether it needs to consume
+the bucket, dumping that to the output socket.
+
+It is entirely reasonable to assume that an upstream "handler" is
+pushing a bunch of buckets at the network layer. For each bucket
+pushed (since we deal with one bucket at a time), that bucket is
+wrapped with the SSI, GZIP, C-L, and chunker buckets. The question
+arises on how to share context across those new buckets (e.g. the SSI,
+GZIP, and C-L buckets all need to share data; the chunker doesn't, but
+it would be nice to consolidate).
+
+The answer is that only a single bucket may be "pushed". That bucket
+can implement the complex features of the "handler". As it is read, it
+cycles across each of the various parts that make up its entire
+content. Of course, the bucket that is pushed could be an aggregate of
+many other buckets which are reading from databases, the filesystem,
+and inserting constant text and metadata between them.
+
+An important point to note is that this model represents an
+asynchronous "pull" model rather than the simpler "push" model. The
+network layer pulls data and drops it onto the network. There isn't a
+"handler" which pushes data through a filter chain to the
+network. This certainly alters the programming style: something like
+ap_fprintf() is not possible; the handler has to generate the data up
+front (placing it all into a bucket) or it must implement a state
+machine which generates successive bits/varieties of data.
+
+Network pushback is established at the network layer; if congestion
+occurs, the layer will not read (consume) data from the bucket as
+fast. The network layer will also request "appropriate" chunks of
+data. For example, these chunk sizes could be some multiple of the
+network's MTU.
+
+(this is also where read negotiation comes in; it would be nice if the
+ network layer could say "give me up to N bytes immediately" and the
+ bucket says "here are M bytes sitting in memory" knowing the rest of
+ the (requested) N bytes is sitting on disk ready for a sendfile)
+
+
+ESTABLISHING THE "FILTER" BUCKETS
+---------------------------------
+
+It is important to note that, unlike httpd's filter chains, this chain
+is not passing data along. It is passing buckets which represent
+computed data. One bucket comes in, is possibly wrapped or otherwise
+manipulated, and one bucket exits.
+
+The httpd filter style could "allow" a filter to pass *multiple*
+buckets to the "next" filter via repeated calls, rather than sticking
+to the desired "one in, one out" methodology. Thus, the processing
+algorithm looks more like:
+
+ bucket = handler_execute(request)
+ for filter in request.filters + conn.filters + global_filters:
+ bucket = filter.process(bucket)
+ network_deliver(bucket)
+
+This enforces the desired style.
+
+One potential problem with this algorithm is where the handler or the
+filters generate "all" of the content. This could overwhelm the memory
+of the machine. Instead, the bucket should retain enough state to
+generate the content on demand rather than up front. The network
+throttling occurs through "how fast do I request more" rather than
+"how fast can I push it down the filter stack".
+
+As a result, buckets should be made easily implementable. For example,
+mod_autoindex should not generate the entire page up front. It should
+have a bucket keyed to the results of the opendir(). Each time you
+read, you can format another directory entry and its data. If the
+developer could easily create the directory-traversal bucket (and
+possibly a "directory entry" bucket), then we would have a higher
+assurance of bounding the memory used.
+
+It is undefined how that list of filters (the function to do the
+bucket in/out wrapping/processing) is established. The simple fact is
+that something will pull them together. Note that the assembly of
+filters can be based on matching up the bucket's content-type (and
+other fields) against specific filters. For example, a filter could
+say "I only take ascii/plain data, and I generate application/x-gzip
+data").
+
+
+CLASSIC FILTER STYLE
+--------------------
+
+The classic httpd style of filters *is* still possible. Rather than
+passing a brigade, we just pass a single bucket instead. The setup
+could also allow for multiple passings [for a single request]. This
+style would also have simple data buckets rather than the more complex
+processing buckets described above.
+
+
+PUSH VS PULL
+------------
+
+Push is described as "synchronous". Something does its work and pushes
+data "down" to the network layer. As more data is generated, it is
+pushed at the network layer.
+
+Pull is described as "asynchronous". As the network is ready for more
+data, it requests the data-to-send from some input system.
+
+Both have work with a bounded memory set based on network
+congestion. The async model is a bit harder to develop because of the
+need to implement new bucket types.
+
+However: note that the async model actually scales better. The network
+layer could be multiplexing 1000 connections with 1000 buckets. In the
+synchronous style, you would have 1000 threads of execution pushing
+data down at the network until the client has consumed all of the data
+(across its 9600 baud link!). Those 1000 threads can be avoided by
+doing a "set aside" of all the pushed data and having a multiplexor
+pick up tat setaside data. But note that the setaside data and that
+model is right back to the async model!
+
+Thus, the pull model has more potential, although it can be a bit more
+difficult to program against. (thus the need for creative thinking on
+how to make it easier; e.g. a standard StateMachine bucket that helps
+with construction these new bucket types)
+
+Certain types of processing become much easier in the pull model. The
+SSI bucket can read as much as necessary from its child bucket rather
+than having to deal with incoming data which represents only partial
+tags or other directives. The SSI bucket would still need a state
+machine because it probably doesn't want to process "too much" all at
+one time. But that state machine will be radically simpler.
+
+
+APPLICATION MODEL
+-----------------
+
+A client application that is operating in a request/response fashion
+(such as an HTTP-based client) uses logic like this:
+
+ req_bucket = build_request()
+ resp_bucket = connection.get_response(req_bucket)
+
+The request bucket has the proper layers to construct an HTTP request,
+which is then fed into the connection. The response bucket also has
+the proper layers to read and parse the HTTP response.
+
+An HTTP server would be something like this:
+
+ req_bucket = connection.read_request()
+ resp_bucket = process_request(req_bucket)
+ connection.write_response(resp_bucket)
+
+The process_request() function reads the HTTP information out of the
+req_bucket and dispatches to the appropriate handler, which returns a
+bucket corresponding to the (raw) response. The function then wraps
+that up with the appropriate buckets (e.g. apply filter buckets) and
+returns that, where it gets fed into the connection.
+
+Note that the bucket is the base unit for requests and
+responses. These can be passed to a multiplexing network handler. The
+application could build a bunch of request buckets and feed them as a
+group to a handler to shove them all into the socket (HTTP
+pipelining). Similarly, the server could collect a number of responses
+and process them all at once (multiplex the delivery of many responses
+from a single thread).