From: Young Hyun <youngh@...>
Date: 2007-02-13T04:58:43+09:00
Subject: Re: TupleSpace performance (TupleBag really)

On Feb 7, 2007, at 9:21 AM, Mark Alexander Friedgan wrote:

> We've been trying to come up with a better implementation of TupleBag
> but have not had much luck so far.  Has anyone else done this?

This is probably as good a time as any to mention to the wider Ruby  
community that I've been working on a new implementation of a tuple  
space in Ruby, completely independent of the standard  
implementation.  My implementation currently searches a list to do  
template matching, but it's on my to-do list to research and  
implement more scalable data structures and algorithms.

The most general form of template matching is actually quite  
challenging to implement, and to achieve scalability, I'll have to  
impose some restrictions.  The current DRb-based Rinda is extremely  
flexible in what values can be in tuples, but in my implementation,  
I'll most likely require that all tuple components be scalars-- 
numbers, strings, etc.  You can use YAML to store more complex  
structures (opaquely to the tuple space), but arbitrary user objects,  
regular expressions, and class names (e.g., take [String, 5,  
Integer]) won't be allowed directly as tuple components.  This is a  
trade-off, but one that I think most applications using a tuple space  
can live with.  This restriction makes the problem more amendable to  
techniques developed in the fields of databases, data analysis (e.g.,  
clustering algorithms to partition the space), machine learning, etc.

I have a working, though unreleased, distributed tuple-space  
implementation right now and written in Ruby.  It doesn't use DRb at  
all; it uses a custom wire protocol over SSL (with validation of  
client and server certificates).  It supports a good many features  
beyond the standard tuple space; namely, multiple tuple space  
regions, local and global scopes (two-level hierarchy of tuple  
spaces), private one-to-one and group communication, region  
privileges, and a "monitor" operation (the read_all operation returns  
all available matching tuples; the monitor operation returns all  
available and future matching tuples).  Additionally, my  
implementation allows processes to pass file descriptors over the  
local tuple space (which, by definition, is confined to a given host,  
and so communication takes place over a Unix domain socket).

More information on my implementation is available in my talk slides at

   http://www.caida.org/publications/presentations/2006/ 
young_wide0611_ark/

The design of the tuple space is being driven by the needs of CAIDA's  
next-generation distributed network measurement infrastructure named  
Archipelago.

I hope to release the code under the GPL, with the client library  
under the LGPL.  There's no clear time table for code release.  It's  
also going to be months down the line before I can work on  
implementing scalable matching in earnest, since other work has  
higher priority.

  --Young