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).