The espace application

Version: 0.2.0

Authors: Fred Youhanaie (fyrlang@anydata.co.uk).

Introduction

espace is an Erlang implementation of the Tuple Spaces (or Linda) paradigm. Details of the paradigm can be found on Wikipedia for Linda and Tuple Spaces.

Another good source that describes the paradigm well is the following paper:

Carriero, Nicholas & Gelernter, David. (1989).
How to Write Parallel Programs: A Guide to the Perplexed.
ACM Computing Surveys. 21. 323-357.

espace allows one to implement parallel algorithms where tasks (worker processes) running concurrently communicate and coordinate through the tuple space.

The basic idea behind tuple spaces is that an application is given a storage pool where tuples are added to it via the out operation, or taken from the pool via the in/inp or rd/rdp operations.

An application created to use this system will have many concurrently active worker processes that look, and optionally, wait for tuples that match a desired pattern. The waiting workers will block until a matching tuple is added to the pool by another worker using the out operation.

The worker processes are started via the espace:worker/1,2 function. A worker can in turn start further workers by further calling worker/1,2.

A typical application will start with a series of out and eval oprations. Some of the worker processes will then, using the in or rd operations, pick the tuples added via the out operations, process them, then out the results. Other worker processes can then pick the results and process them further.

The implementation provides a space for the tuples, currently ETS, along with the six basic operations, eval, out, in, inp, rd and rdp.

eval vs worker

The eval operation, as defined in Linda, is expected to behave the same way as out, with the exception that if there are any expressions in the supplied tuple, they will be replaced with their respective function values before being added to the tuple space.

The espace:eval/1,2 functions in the first implementation of espace had a different behaviour. Initially it would take a {Mod, Fun, Args} triple or a fun expression and spawn a child process to evaluate it. Nothing would be added to the tuple space, unless explicitly included inside the function.

For some time now, the espace:worker/1,2 functions have provided the functionality that the original espace:eval/1,2 used to provide.

We now have a new espace:eval/1,2 function that behaves in a similar manner to the Linda definition. The current eval now takes a tuple, and if the tuple contains any fun expressions, those expressions are evaluated before adding the tuple to the tuple space. The evaluation of the tuple elements is carried out sequentially in a separate child process.

Only two forms of function elements are recognized: A zero arity fun expression, fun () -> expr end, and a tuple with two elements, an N arity fun expression together with a list of length N, {fun (A, B, ...) -> expr end, [expr, expr, ...]}. In the second form, the arity can be zero.

Organization of the Project Modules

espace has been built as an OTP application, espace_app. Multiple instances of the application can run concurrently on the same node without interfering with each other.

The application server can be started with espace:start/1,2. Once the server is running, the client processes can use the espace module to perform any of the six operations. In fact, one can kick off the whole process by calling a purpose written bootstrap function, which can in turn perform out and eval operations.

The top level supervisor started by espace_app is espace_sup. This supervisor manages four gen_servers and one supervisor, as described below:

etsmgr_srv is a gen_server that adds resiliency to the ETS tables, should any of their owner servers restart due to some fault. See the project repo for details.
espace_tspool_srv is a gen_server that manages the out/in/rd/inp/rdp requests. In turn it passes the requests to espace_tspool_srv
espace_tspace_srv maintains the espace_tspace ETS table, the main tuple space pool. If a requested pattern does not exist and the request is a blocking one, i.e. in or rd, then the pattern is forwarded to espace_tspatt_srv. In case of an out request, the tuple is stored in the table, and espace_tspatt_srv is notified so that it can inform all the blocking clients whose requested pattern matches this tuple to retry the in/rd operation.
espace_tspatt_srv maintains the espace_tspatt ETS table, which contains the tuple patterns that worker processes (clients) are blocked on. It receives two types of messages from espace_tspool_srv, unmatched patterns, which, along with the client details, are then added to the espace_tspatt table, and newly added tuples, which are matched against the existing patterns in the table and, if matched, blocked clients are notified.
espace_worker_sup is a supervisor that will create a new child process with the {M,F,A} function supplied with the request. Each worker/1,2 request, is executed within a child process of the simple_one_for_one supervisor. At present, no attempt is made to throttle the number of eval processes.

The ETS Tables

The tuples are kept in a pair of ETS tables.

The first table, espace_tspace has two columns, a unique ref, and the tuple itself. A single gen_server, espace_tspace_srv, handles all accesses to this table.

For the cases where no matching tuple is found for a given pattern, a second ETS table espace_tspatt is used to remember the pattern, the client PID and a unique reference for this specific request. The unique reference will be used by the espace_tspool_srv client side function to block on a receive for that reference.

Each out operation, after inserting the new tuple, will notify espace_tspatt_srv of the new tuple. espace_tspatt_srv which will then scan the blocking clients whose pattern matches the newly added tuple. If a match is found, the waiting client is notified and the client entry is removed from the table.

Once the waiting client receives the notification, it will attempt the rd or in operation again. Note that the client is not handed the tuple, but notified to request it again. If more than one client have waiting patterns that match the tuple, then they will end up competing for it.

Generated by EDoc