The espace application

Copyright © 2017-2021 Fred Youhanaie

Version: 0.7.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 and eval operations, or taken from the pool via the in/inp and 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/eval operations.

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 fun 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, however, an empty arg list, [], must accompany the function.

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 the three gen_servers, as described below:

The ETS Tables

The tuples are kept in a pair of ETS tables.

The first table, espace_tspace has two columns, an integer, and the tuple itself. All access to the table is handled by a single server, espace_tspace_srv.

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 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 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. This waiting and the subsequent notification occurs inside the espace client code. If more than one client have waiting patterns that match the new tuple, then they may end up competing for it. However, since the ETS table is an ordered_set, the notification will be performed in a first come (blocked) first served (notified) manner.

The Operation Counters

For each running instance of espace a set of counters are maintained. Each set consists of six counters, one for each espace operation. The counters are increments whenever the operation is requested. Note that each eval will increment two counters, eval and out.

The functions for the operation counters can be found in the espace_util module and have the prefix opcount_. However, only two of them are meant for general use, opcount_counts/0,1 and opcount_reset/0,1. The former will return a map of the operation/count pairs, while the latter will reset the counts to zero.

The persistent term records

In order to provide better visibility of the internal workings of an espace instance, as well as simplifying some of the code, a set of persistent_term records are maintained for each active instance.

The functions for manipulating the terms can be found in the espace_util module and are prefixed pterm_. The terms are created during the instance startup, and removed during the instance shutdown.

The keys are of the form {espace, Inst :: atom(), Key :: atom()}, where Inst is the instance name, and Key specifies the particular term. The current keys are listed below:

  1. espace_sup, espace_tspace_srv, espace_tspatt_srv and etsmgr_srv identify the registered server names.
  2. tspace_tabid and tspatt_tabid contain the ETS table ids.
  3. opcounters identifies the reference for the counters module.
  4. espace_tspace and espace_tspatt identify the table names for the etsmgr instance.


Generated by EDoc