Abstract Awelon Virtual Machines

I’m still working towards Wikilon, a wiki-based development environment and initial software platform for the Awelon project. The design is still fluid, and has taken me in some interesting and unconventional directions on the ‘development environment’ side.

On the ‘software platform’ side, I was contemplating a filesystem model, for long-lived data and applications. But I was concerned: how do developers disentangle their app from the filesystem? So I shifted to Wikilon hosting abstract virtual machines (AVMs) that host applications. AVMs provide boundaries for entanglement, forcing developers to address latency, concurrency, and disruption. This week, I decided I don’t want the heavy weight of a filesystem in every AVM. AVM state is now just a value, and a trie value is a decent model of a filesystem if developers want to use one. The development of VCache makes it entirely feasible to model filesystem-sized values containing gigabytes of data.

I selected message passing as a basis for communication between AVMs. I’m not fond of message passing, but ease of implementation and integration with existing systems sold it to me anyway.

Some interesting differences between AVMs and other message passing systems:

  • AVMs cleanly separate state from behavior. The behavior of an AVM is a pure function of the form `(InMessage, State) → (OutMessages, State)`. All messages travel through this function. This separation makes live programming easy: bind behavior to a Wikilon dictionary, such that edits affect behaviors in real-time. Similarly, we can apply a structure editor to browse and directly manipulate state.
  • Every message carries a capability-secure context: every InMessage is a (Context, Content) pair while every OutMessage is a (Capability, Content) pair, where the capability is an ADT that keeps context opaque to the sender. An AVM is (usually) given a pure function `self :: Context → Capability` so that it can construct capabilities needed for query-response and other feedback patterns. An AVM constructs ad-hoc, fine-grained capabilities on the fly.
  • AVMs cannot create/spawn/fork/etc. new AVMs as a primitive. However, AVMs may host other AVMs hierarchically, using context to route messages. AVMs tend to centralize a lot of state under just a few objects, which has many advantages for debugging. That said, spawning can be modeled in terms of a capability to ask another machine to host an AVM.
  • A friendly scheduler is specified. Messages between AVMs are implicitly grouped into batches. Output messages resulting from a batch are sorted into a new batch for each target AVM. Batches are processed atomically, and messages within each batch preserve order. Batches between machines also preserve order, using timestamps. Thus, developers don’t need to think about worst cases for non-determinism.
  • A ‘common capabilities’ concept is also supported. For example, if access to UTC time is provided by a capability, and we send this capability to a remote host, said host may recognize this capability as a common one and provide a local implementation. This is discretionary; the host may instead send the message across the network to get UTC time at the origin. This mechanism is highly extensible: time, random numbers, high performance matrix multiplication, HTTP access, multi-homing, etc. can be modeled this way.
  • I’ll make a reasonable effort at timely, reliable delivery of messages, but I won’t guarantee delivery. If a message cannot be delivered easily, I’ll drop it. If a message has a much larger latency than physically expected, I’ll drop it. Dropping messages allows a simple and scalable implementation in the face of varying connectivity, congestion, migration, administration that might take a machine offline, etc.. AVMs can react intelligently to network conditions via special capabilities that can report delivery status or provide alternate behaviors. Developers are encouraged to explicitly model mailboxes and tuple spaces and other robust offline delivery mechanisms where needed.
  • In addition to state and behavior, every AVM has a ‘signal :: Context’ value. This value is used by the hosting environment to get an AVM running (an ‘init’ signal) or support graceful shutdown (a ‘stop’ signal) or indicate other concerns (e.g. low power) or to inject information about the environment or the Self function. Basically, it’s an initial capability. It provides an extensible set of generic AVM methods.
  • At the toplevel, AVMs will be given global names – a secure hash of a public key – with routing based on a distributed hashtable. This makes it easy to create tons of fine-grained AVMs, to move them across physical systems, and to secure them against man-in-the-middle attacks without relying on a central naming service. If developers want common names, e.g. similar to domain names, these might be supported via NameCoin and similar protocols. (I’d rather avoid depending on ICANN or CAs.)

As with other message-passing systems, effects are modeled in terms of sending messages to resources masquerading as machines. Access to Redis, S3, AMQP, XMLHttpRequest, sockets, user interfaces, etc. could be modeled this way. Though I’ll initially focusing on just whatever I need for web services and web sockets.

Addendum: to emphasize a few points

I really love the simple, pure, non-monadic nature of the step function.

This sort of straight-line code is easy to express in a first-order manner. It is abundantly clear to developers that nothing happens – no output, no new input, no progress – unless the function terminates. It is clear that developers cannot wait on a message in response to a send unless they model waiting in a higher layer abstraction. The loop itself is clearly separated from state, which simplifies both live programming and visualization or direct manipulation of machine state.

I believe AVMs will prove highly scalable, and this is greatly aided by their purely functional nature and clear simplicity. Read-only messages are easy to parallelize. If we notice (by comparing before and after states) that many messages are read-only, we can heuristically switch to parallel modes and use compare-and-swap or other rework models to resolve read-write conflicts. Developers can leverage this by dividing AVMs for read-mostly loads or arranging for a single writer to avoid read-write conflicts. This sort of parallelism is highly scalable, e.g. can be implemented through replicating the entire abstract machine. Read-write messages are more difficult to parallelize. But if we have expensive computations distributed across small partitions of state, we can use pure parallelism to be processing many updates at one time. Normal sharding techniques also apply.

The real challenge will be to make these AVMs competitively efficient, i.e. by developing an effective compilers or JIT for Awelon Bytecode, leveraging annotations for memoization, etc..

Advertisements
This entry was posted in Concurrency, Modularity, Open Systems Programming, Security, State. Bookmark the permalink.

10 Responses to Abstract Awelon Virtual Machines

  1. floatxz says:

    When you say “Access to Redis, S3, AMQP, XMLHttpRequest, sockets, user interfaces, etc. could be modeled this way”, how do you mean? Like if the behavior of an AVM is a pure function of the form `(InMessage, State) → (OutMessages, State)`, then if you access redis would that be something like for example `Redis(AppendToKey, State) → (OutMessage, State)`, where AppendToKey is the redis APPEND command to append some data to a key. In this case, what would then the input and output state be and what would OutMessage be? Would State be for example the URL to the redis server plus a timestamp?

    • dmbarbour says:

      I can implement effectful resources that implement the same message protocol as AVMs. This is what I meant by “masquerading as machines”.

      In case of a Redis adapter, the InMessage might be (“APPEND”, ((keyString, valString), reply)), where “APPEND” is the context, and ‘reply’ is where Redis sends the asynchronous response. (If we want optional replies, we could model this too.) There are, of course, a lot of other ways to model Redis adapters. We could model multiple Redis instances. We could provide a monadic subprogram to execute, rather than individual commands. And so on. But the Redis adapter is not a purely functional AVM.

      To correct a potential point of confusion, the `OutMessages` on the right is plural. Currently, I’m just encoding it as a list of messages (in reverse send order). To receive a reply, an InMessage must explicitly contain a send-reply-to field, much as we’d see in Actors model.

      • floatxz says:

        I see. I thought maybe you wanted all AVMs to be purely functional, but perhaps it’s difficult to do in a very useful way.

      • dmbarbour says:

        All AVMs are purely functional. But resource adapters are neither purely functional nor AVMs. 🙂

      • dmbarbour says:

        As an extended point: this design makes it very easy to transparently mock any resource in a purely functional manner, for testing purposes. And with a simple stateful pubsub service like Redis, I could probably implement the whole thing. However, it is certainly the case that some services (such as remote control of a drone) inherently cannot be pure.

  2. floatxz says:

    Can’t anything be pure, depending on how you see it? If you have a function for moving the drone up for example, it could be move(offset, drone) → (status, drone), where offset is an offset vector for where the drone should move from its current position and drone is an id of the drone and a timestamp.

    Because time always flows, the input (drone) can never be the same twice, every time you call the function it applies to the drone at that specific instant in time. You would have to think of functions as something that can not only run on computers, but also on other machines, so move is a function that run on the drone and every time you run the move function, it returns a new version of the machine it runs on (the drone, now at a new location at a new time) in addition to a status message for the computer.

    • dmbarbour says:

      There is concurrent influence on the drone’s behavior: your movement command, winds, obstacles, collision avoidance algorithms. Even if we just simulate the drone in a closed system, these elements are awkward to express or view as hidden elements of a drone’s state, and would hinder modeling the drone as a linear object or value.

      Also, when ‘time’ becomes implicit, purity usually fails because evaluation takes time and suddenly expression results depend implicitly on evaluation order. This can be mitigated with an explicit model of time, but then we have a lot more difficulty aligning the drone’s time with the program’s time (this is the problem FRP systems address).

      • floatxz says:

        True. I suppose in the case of Redis you could make it purely functional, for example to add something to a set you’d have something like SADD(redisServer, myset, “Hello”) → (result, redisServer), where redisServer is a linear type representing the redis server.

        Each time some program do a change to the redis server, it would “take” the redisServer and other programs would have to wait for a new version of redisServer with the change performed to be returned before they could perform new changes.

  3. Pingback: Command Language for Awelon | Awelon Blue

  4. Pingback: Wikilon Dictionary Applications | Awelon Blue

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s