Askemos Forum

STM locks and byzantine shared state11. February 2007

Patrick Logan has concerns with STM, some comments.

In Patriks posting he asks Why did I start this? - because it's too much work.

Let me add my two Cent anyway.

When you try to actually implement and Askemos system, the idea of STM or simply avoiding locks at all costs will come naturally to you.

The over all style of Askemos programs compares to Erlang or Termite: sequential processes communicating share-nothing messages. (Just to ease getting the picture Askemos/BALL deploys a side effect free subset of Scheme a expression language, but that syntax doesn't matter here.) In contrast to Erlang or Termite processes (called a place in Askemos) are persistent and the malfunction of a minority of physical nodes doesn't harm the system. In other words: Askemos compliant processes are executed stepwise (i.e., in transactions) in byzantine agreement.

These transactions are - as usually - not there, because they are the best abstractions, scaling to thousands of objects. We have them for their legal importance when modelling contracts. Deeds and contracts are the basic values of any Askemos system.

But implementing the thing can easily become a nightmare. If you expose the application developer with all the synchronization work, they will not become productive. So you will naturally end up devising an application language, which doesn't expose you to locking.

Nevertheless, the underlying peer-to-peer network properties somewhat shine through. Updating state is much, much more expensive than read only access. Think of network wide shared state as of STM, which has a read:write ratio above 10000. And recall: in the distributed case there is no hardware facility to support your atomic updates.

Even though I did not dare to implement the peer program lock free (as a non-academic coder, I better behave conservative), enforcing global locks appears to be prohibitive. Imagine the following sequence of actions. The left column spells the "traditional, single host" operation and the right side the minimum amount of IP round trips per operation (assuming the "reliable broadcast" protocol, which, to the best of my knowledge, is the only protocol, which does not deploy probabilistic but unreliable optimizations):

step #action# message trips
1take lock for the place2
2compute transaction0
3agree on transaction's result2
4commit transaction and unlock2

This is a minimum of roughly 3 network round trips. Since business communication is usually sensitive, this is not plain text via UPD, but SSL communication or some such.

Additionally to those 3 round trips, the computation of the transaction is right within the locked time.

If worst comes to worst, some program will lock up an important place. Debugging such situations in a p2p network is plain horror - I can tell you. Let alone, that - for legal reasons - there is no single programmer, who is allowed to access all the hosts simultaneously. A group must "debug by committee" - I'm afraid this could be worse then design by committee.

So here is, where STM and lock free updates fit in well - at the known cost of possibly throwing away computational work and resolving conflicts. But this happens locally and saves network activity. As a result (and adding in that the computation per step should be kept - manually - within half the round trip time) places can update almost once per round trip time.

For a real system talking HTTPS and completely implemented in a safe language (Scheme) we currently get about 3Hz update frequency. Knowing thereby that we planted a lot of horrible quirks into the HTTP code (when we added WebDAV support by a programmer new to that code and not overly experienced at Scheme at that time), we expect, once those are fixed, we save almost another 10ms. So the persistence layer plus safe implementation plus HTTP and SSL cost plus active profiling costs about 3 times compared to the theoretical limit based on raw ping times. We can hope for up to 10Hz update frequency. An locking approach in contrast - while hardly feasible for the debug-by-committee reason - has an upper bound of about 6Hz for the same raw ping time. Persistence and safety not yet added.

Update: see also the related position on mutability of pairs I adopted the R6RS process.

Post replies via login host.

Intro - slides
Askemos Wiki
Publikationen