[FoRK] taxonomy of composition and coordination (thinking out loud...)
Stephen D. Williams
sdw at lig.net
Mon Dec 14 18:43:56 PST 2009
Jeff Bone wrote:
> Really, the difficulty here is in really rounding out e.g. Rohit's
> work on similar issues to capture all the critical dimensions of
> composition and coordination. Such a taxonomic set of features would
> be useful (academically, and perhaps practically) in its own right,
> but my goal is really more along the lines of understanding how to
> make composition as easy as e.g. pipes but more general and flexible,
> for use in my own pet project and for my own understanding.
I've thought and talked about working on an "upgrade" for the Unixen
shell also. On a completely different level, I did an architecture and
design solving the composition problem a few years ago - something like
a confluence of grid/HPC, map/reduce, P2P, SOA, etc. The goal of that
system was very loose coupling, i.e. fully decoupled "tools" as
contrasted with half-decoupled SOA/SOAP and most other systems. Among
other things, I combined the ideas of Unix filter tools with a
macro-level rule engine that controlled flow via message (data blob)
metadata pattern matching and a distributed pull work queue with
bidding, timeout, and resilient re-execution, operating on an immutable
temporal distributed datastore. Each compute node was normally also a
> I.e., what *is* it that makes reuse in e.g. the shell so easy, and so
> hard everywhere else, and how can we generalize that and make it even
Shell programs generally don't know about each other and are not
integrated with each other. They are input+args+algorithm = output(s).
I see these next steps: structured interchange (typed graphs,
OGDL+types, etc.), option for complex communication connections (managed
by the shell, just like piping is, not the tool/process, should include
both pipeline, bidirectional pipeline, and more complex options -
mux/demux, etc.), option for complex communication architecture in
addition to pipelines (arbitrary networks, map/reduce, services), option
to be either a process or thread or method (pseudo-thread in a message
architecture), and various kinds of efficient context. Memcached is one
kind of context. Databases of various kinds are another. There should
also be one or more flexible event / metadata matching, filtering, and
mapping capabilities. It should be possible to do zero copy as much as
possible. It should be possible to avoid serialization and parsing to a
large extent (esXML/esDOM etc). Perhaps swizzling should be integral.
Scoping should be pervasive. Transactions should be possible at a
number of levels, or globally, or scoped in various ways (esXML/esDOM
for the memory/process, etc.). This is not the same as fully-general
transactional memory, but rather a generational / delta data structure
that is directly modifiable.
> It seems that there are several potential dimensions of composition:
> (1) is there some kind of reified "connection" or channel between
> communicating components? (Vs. "just" messaging.)
Most components shouldn't know about anything more than the data needed
to complete some operation, i.e. grep etc. Communication channels should
generally be async, pipelined, message oriented, multi-channel
underneath, reliable but fail-fast best effort unless otherwise
indicated (i.e. a "tee"-like component might create a persistent queue
that could support auto-recovery). The "shell" should normally do all
communication addressing and handling. The tool/component should have
even less I/O handling than Unixen tools.
> (2) do all components support the same set of interfaces?
There should be a few standard types and then the ability to have
specialized / arbitrary connector interfaces for 'external' use.
> (3) is communication synchronous (blocking, implying return value) or
> async (non-blocking, no rv per se)
Async should be preferred, sync for simplicity. Return value / result
processing should normally be by another step, with context as needed.
It could be the same tool/thread or another (bidirectional messages, etc.)
> (4) is there flow control, and how is it handled?
The "shell", which handles most "normal" communication, should enforce
various policies, buffering, flushes, memory management, etc.
> (5) do components know each other by name? What kinds of names are
Normally they don't know each other at all! Fully decoupled if and when
possible. Coupling is the job of the shell, just like Unix. RPC-like
"side" communication should be handled in one or more
pattern/filter/type ways which can be mapped efficiently (and
semi-statically) by the shell. Exceptions of course, just like popen()
now. At least that is the goal.
For real world, that doesn't solve much.
> (6) if not name-based coupling, what? (channels; generative
> dispatch; ...?)
The shell (and sometimes the tool) does deal in names / handles of some
kind. URL/URIs, etc. There are several reasonable alternatives.
> (7) what's the relationship between the transport-level metaphors and
> the higher-level ones?
> (8) sharing of state, mutability of data, etc.
Shared nested context in scopes, transactions, and mutable / immutable
> etc. (Again, not presenting this as a complete set, or consistent.
> Just thinking out loud...)
> BTW, thanks to Sean for reminding me about QNX. Thinking about
> explicit element-wise node addressing has generated some interesting
> questions / ideas over the last 24 hours...
> In particular, one of the things I've wrestled with for a while now is
> formalizing the notion of a UNIX-like process. What is it, exactly?
> The sort of rough definition I've been working from is that it's a
> partial function from streams, args, etc. (i.e. tuple of (stdio, fds,
> env, args)) to same (sans args, plus return value). The curried
> function is reified by providing e.g. args and env, then yields a
> function from streams to streams + argv. That's not really
> satisfactory. In particular return values are a problem. I'm sure
> it's in the more general literature, but (aha moment!) pure functions
> with return values can be modeled in the pi-calculus with uniqueness
> types as processes that have a one-shot return value channel.
Since a "UNIX-like process" can mean anything, I try to think in terms
of prototypical tool-types. A "Unix filter" is a pretty clear choice.
In "UFng" (above), it should support bidirectional (and more)
communication paradigms. In a large set of those cases, the key to
modeling the interaction is context. Whether it is a thread waiting on
a synchronous RPC or a pseudo-thread (i.e. some data structure
representing a logical context that will be materialized in a thread
later), the state of that part of a program is the context of the
communication. So, a web application communication stack could be:
Bidirectional pipeline: (|| could indicate bidir, or it could be
inferred by the tool, or command line... Here, it would make sense for
tcp to indicate to the shell that it needed a new real or session
context (which could be a pipeline channel) fork of the rest of the
pipeline. -C is context ID.)
tcp -L -h lig.net -p 80 || tls server.key || supertee -t http -o
http.log || apachetool -C lig.net -p /date -c "date" -p "/urlshortener"
-c "urlshort -C lig.net"
Or unwrapped and paired via context:
tcp -C lig.net -L -h lig.net -p 80 | tls -C lig.net server.key |
supertee -t http -o httpin.log | apachetool -C lig.net -p /date -c
"date" -p "/urlshortener" -c "urlshort -C lig.net" | supertee -t http -o
httpout.log | tls -C lig.net server.key | tcp -C lig.net -L -h lig.net -p 80
The first is clearly nicer most of the time, however the latter allows
more complex relationships in process / data flow. One other major
option is to simply name each endpoint with each command as a discrete
definition, allowing the shell to stitch them together arbitrarily.
tcp --ID TCP -O TLS
tls --ID TLS -I TCP -O SUPERTEE
Ideally, you use the first style for much of the time, only resorting to
the other two (or more) options for the outlier cases. And you allow
use of all methods in the same "command line".
However, this only solves simple situations where components are already
mostly pipeline ready because of their inputs/outputs. You can get
pretty far by supporting various levels of metadata tagging of the
stream, interaction between tools once they have been connected (content
and encoding negotiation, etc.), and data scoping. A la esXML/esDOM,
the idea is to create a writable view (via a copy on write layer when
transactional) into a larger object / graph space. In pipelines like
above, it could be done via a scope operator.
More of a language is needed to handle the rest.
Note in all of the above, the data need not be constantly copied,
parsed, or serialized. Likewise, each tool can be a process, thread, or
function call, both local and remote in various senses, where network
remote requires some already-present service perhaps.
> More thinking out loud...
I hear you.
More information about the FoRK