Alice Project


________ Overview ____________________________________________________

Alice supports distributed programming in the form of a number of processes communicating using picklable Alice data structures. In the context of distribution, we speak of sites instead of processes. Sites can open a communication port to make data available to other sites, which serves as an endpoint to establish connections. There are three ways in which sites can establish connections:

The operations mentioned in the following are part of the Remote structure.

________ Tickets _____________________________________________________

The first mechanism in which sites establish connections is the offer-and-take mechanism. A site can explicitly create a distributed reference to one of its data structures using offer:

offer : package -> ticket

Offering opens a communication port on the exporting site (or reuses the existing communications port if it has already been opened). Currently, Alice communications ports take the form of HTTP servers; opening therefore amounts to starting a HTTP server on a TCP/IP port and to listening for incoming connections. offer clones the data structure pickling it into a string, and registers the pickle as a document in the HTTP server under a generated URI. (If the data structure is not picklable, offer raises an exception.)

offer returns a ticket, which is a string denoting a reference to the exported data structure usable from other sites. The string identifies the protocol, the communications port, and the data structure on the site, in the form of a URL. For example:

- val ticket = offer p;
val ticket : string = ""

This ticket can be transferred to other sites, say by email or voice conversation. It could also be stored (for instance, as a pickle) in the web server's document root, to make it possible to be accessed under a well-known URL. Other sites (or the same site) can then obtain the actual package denoted by the ticket using take:

take : ticket -> package

take establishes a connection to the communication port given in the ticket and retrieves, using the HTTP GET method, and unpickles the exported package. For instance:

- val package = take ticket;
val package : package

________ Proxies _____________________________________________________

In what has been presented so far, pickles as transferred between sites could only contain data that was cloned. Proxies extend this mechanism to also allow for function references instead of the functions themselves.

A proxy can be created from any function using the proxy operation:

proxy : ('a -> 'b) -> ('a -> 'b)

Say that a site A evaluates

val f' = proxy f

then f' is a proxy for f, and we call A the home site of f'. An application f x proceeds as follows. A clone x' of x is created using pickling, f is applied to x', returning y (or raising an exception e). y (resp. e) is cloned to yield y' (resp. e'), which is returned (resp. raised) as result of the application f x.

Applications of proxies are always concurrent on the server. Conceptually, they can be considered to happen in the same thread as the application of the proxy, which may actually happen in a thread on a different site.

A proxy is always picklable, independently of whether the function it proxies is picklable or not. If f' is transferred to another site B and applied there, instead of the function f only the proxy f' is transferred, which contains a distributed reference to f. An application of f' causes the cloned argument to be transferred to f's home site A, where f is applied and the result (or exception) cloned and transferred back to B.

In order to conveniently create a proxy module where all functions are proxies in one go, a polymorphic library functor is provided:

Proxy : fct (signature S structure X : S) -> S

Example: Compute server

As an example, say you want to provide a simple compute service. The compute server exports a function which clients can apply to computations that are then executed on the server. We provide both server and client with the signature of the server:

signature COMPUTE_SERVER =
    val apply : ('a -> 'b) * 'a -> 'b

The compute server makes the ticket under which it offers its service available through the local web server. We assume the local server's document root is /docroot/.

structure ComputeServer =
    Remote.Proxy (signature S = COMPUTE_SERVER
                  structure X = (fun apply (f,x) = f x))
val ticket = offer (pack ComputeServer : COMPUTE_SERVER)
val _ = ("/docroot/computeServer",
		     pack (val x = ticket) : (val x : string))

Clients can use this service by acquiring the ticket from the well-known URL http://www/computeServer:

structure Ticket =
    unpack Pickle.load "http://www/computeServer" : (val x : string)
structure ComputeServer = unpack (take Ticket.x) : COMPUTE_SERVER
fun fib (0 | 1) = 1
  | fib n       = fib (n-1) + fib (n-2)
val result = ComputeServer.apply (fib, 30)

In the example, the (expensive) function fib and the argument 30 are cloned to the compute server, where the application is evaluated. The result 1346269 is cloned back to the client.

Example: Chat program

Here is a second example: a minimalistic, yet complete, chat application. It consists of a chat server, to which clients can connect. Again they need to agree on a signature for the server:

signature SERVER =
    val register :  {send : string -> unit} -> unit
    val broadcast : {name : string, message : string} -> unit

Clients can register, after which they will receive all messages sent by other clients, and they can broadcast messages themselves.

Here is the full code for the server component:

val clients = ref nil
fun register client = clients := client :: !clients
fun broadcast {name, message} = (fn {send} => spawn send (name ^ ": " ^ message)) (!clients)

structure Server = (val register = Remote.proxy (Lock.sync (Lock.lock ()) register)
                    val broadcast = Remote.proxy broadcast)
val ticket = Remote.offer (pack Server : SERVER)
val _ = print (ticket ^ "\n")

The server simply keeps a list of registered clients (represented by their send functions), and broadcasting iterates over this list and forwards the message to each. In order to avoid having to wait for each client in turn to receive the message, sending happens asynchronously, using spawn. Moreover, since the client list is stateful, we have to avoid race conditions when several clients try to register at the same time. The exported register function is hence synchronised on a lock.

The code for a client is even simpler:

val [ticket, name] = CommandLine.arguments ()

structure Server = unpack Remote.take ticket : SERVER
val _ = Server.register {send = Remote.proxy print}

fun loop () =
    case TextIO.inputLine TextIO.stdIn of
        NONE => OS.Process.exit OS.Process.success
      | SOME message => (Server.broadcast {name, message}; loop())
val _ = loop ()

It expects the server ticket and a user name on the command line, registers with the server, and simply forwards everything typed by the user to the server (if registered, the user will see his own messages as an echo).

Obviously, this implementation is very Spartanic: there is no notification of other clients connecting or disconnecting, nor is there any error handling. However, the basic principles are there, and enriching the implementation accordingly is largely straightforward.

________ Remote execution ____________________________________________

In the preceding sections, all parties in the distributed application were assumed to be already running. Sometimes applications want to spawn new sites themselves. To do this, Alice provides for remote execution. Given a host and a service, a new site is created on the remote host (using ssh) and the service is run there. Both the spawning and the spawned site open communication ports to connect to each other. Note that communication is done via pickling. This implies that you must be careful not to use sited values in a service! Many interesting structures in (e.g Remote) contain Sited values. In order to use these you would have to link them using on the spawned site.

run : string * component -> package


As an example, consider an application consisting of a manager and a number of identical worker sites, to parallelize a computation. Say that the manager has access to a large database, which the workers need to execute their tasks. This database should reside on the manager and not be cloned to the workers because we expect only few lookups from each worker. The code for the application is outlined below. We first define a structure Database to represent the database, then repackage it as RemoteDatabase for use by workers, using a proxy to ensure that the database stays on the server only. Then follows the implementation of the workers: The signature WORKER states that each worker provides for a function to execute a task. The implementation sketch for MkWorker, which instantiates a worker, shows how this worker would access the database and use local resources of the worker's site to perform a task. A proxy is used to ensure that the task is performed on the worker site (else the implementation of executeTask would be cloned back to the manager site, which would fail anyway because of references to TextIO.print). Then five workers are spawned on different hosts, whereupon the manager can start to attend to its business.

signature DATABASE =
	val lookup : string -> string
structure Database : DATABASE =
	fun lookup key = ...
structure RemoteDatabase : DATABASE =
	val lookup = proxy Database.lookup
signature WORKER =
	val executeTask : (unit -> 'a) -> 'a

val worker =
        import structure TextIO from "x-alice:/lib/system/TextIO"
        import structure Remote from "x-alice:/lib/distribution/Remote"
        include WORKER
        val executeTask = Remote.proxy
            (fn f => ... RemoteDatabase.lookup ... TextIO.print ...)

val hosts = ["fry", "bender", "leela", "zoidberg", "amy"]
val workers = (fn host =>
			    structure Worker =
				unpack run(host, worker) : WORKER
			end) hosts
... (* use workers *) ...

Note that it is essential for the worker component to import the TextIO and Remote structures on the host site, because the used functions are sited resources and thus cannot be pickled and transferred from the original site.

last modified 2007/03/20 16:45