"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog


Saturday, May 10, 2003

Scaling Tuple Spaces

One of the masters of simplicity in software, Graham Glass, writes...

another awesome bit of software technology is Linda, the tuple spaces architecture by David Gelernter. like Lisp, it provides a simple set of primitives with great expressive power. but i don't think that the Linda approach scales well. the remove() primitive requires some degree of locking that is not suited for distributed environments.

Voyager itself was a simple and awesome software technology. Congratulations to Graham for that as well as Glue and the upcoming Gaia. I'd be interested in his thoughts on Linda-like systems for the Internet.

The most significant adjustment in scaling Linda to the Internet that comes to my mind is to redefine blocking operations to be non-blocking. So 'in' (i.e. remove) would not block until a match is found. Maybe there would be a timeout, but the window would be fairly short and so may just be meaningless at Internet scale.

For these non-blocking polling operations, some rationale has to be assigned to an ethernet-like (but larger distance and time scale) backoff policy. Not unlike the RSS situation with polling. But the surprise with Ethernet is that the pipes continue to get faster and conflicts are not the problem people envisioned.

The alternative is to use a cloud-like mechanism for scalable trigger/notification. Eric Hanson has been designing these for relational databases at UFL.

Another aspect of this is the number of simultaneous users of a single tuple space. Scaling out a tuple space is fairly simple... create more spaces. Work has been done to replicate spaces, but in general I'd look for opportunities to simply partition scenarios and participants across distinct spaces. That must be the 80 percent or greater situation at least.

Reliability of messaging would have to take into account that the connection itself does not (and probably should not) implement guaranteed delivery of just one copy of the message. This is where some wisdom has to go into message design and higher-level domain-specific protocols. Less of an issue as the Internet evolves into its next incarnation, but this is the simplest approach for the next N years.

You can add your thoughts to the TupleSpaceScalability wiki page.

No comments:

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.