Critical Section support...

[Neil]

Wanted to start a discussion primarily discussing how we provide
critical sections across Swarm.

I think that we should use Software Transactional Memory (STM) to deal
with creating critical sections across the Swarm.

STM has two major overheads, we have to make a copy of all data we
read - and defer the writes back over the original copy, and that we
have to perform a commit stage on completion of the critical section.

With Swarm, as data is distributed across multiple computers anyway,
the first overhead is negated. We will have to request the data from
another machine and make a copy of it on our local machine. Since the
copying overhead is the major performance limitation of STM, the only
overhead we really need to concern ourselves with is performing a
commit stage.

This is basically how I see the system working.

Node A wishes to start a critical section.

From now on each read/write to any other locations have to be altered.
On the first read of a new location, we have to cache that object on
our local machine. Any future reads of this location must return the
local cached object. Any write to a location must be witheld, and
stored on our machine until the end of the critical section. When we
write to a remote object, we have to remember the previous value of
that object (for the commit phase).

Node A wishes to complete a critical section.

Now we need to iterate over each object we read/wrote to within our
critical section, and check if the original value of the remote object
is the same as the one we seen. EG. if we read x as 3, and x is now 4,
then some other thread has modified x while we were performing a
transaction, and we have to abort any changes that we made (by
throwing and exception probably).

The only issue I see with this is that we are going to have to lock
objects during the commit phase, have one global lock for the commit
phase, or use a two-phase commit step by asking each remote object to
get ready to commit, wait for their responses, then actually perform
the commit.

I hope this is not too mind numbingly confusing, trying my best to
simply lay out how I think we should deal with critical sections.

I am plugging STM because after writing a system to use it on the Cell
Microprocessor (heterogeneous processor, distributed memory) I can see
the benefits of using STM across distributed systems also. I have a
paper I wrote about my project with a summary of the STM system I
built if anyone is interested, http://www.neil-henning.co.uk/STMCellPaper.pdf

Please bug me with any questions as well! I realise my explanations
are not that good at times.

-Neil.

[Rick R]

I think you and I have differing definitions of Critical Sections, but for the general case of multiple node shared access to resources, I like the idea of STM. Also, Akka actors support a distributed STM already. We can either use Akka, or be heavily inspired by it :)

Even though I'm already a believer, I'll read your paper today. In the meantime, here is is a slightly differing view.
http://www.codecommit.com/blog/scala/improving-the-stm-multi-version-concurrency-control

I've always understood Critical Sections to be completely exclusive. Thus, locking out all other agents in a system is one way to guarantee consistency, but it is the most heavy handed. I think the STM model might be more beneficial in the general case, but we should allow people to create critical sections if needs be. Probably based on the MVar concept. There is a really great write up of this in Scala by Example.

[Neil]

For me a critical section is one or more statements in a language
where you want to ensure that the whole lot is performed atomically,
or not at all!

I read that article you suggested, and it is on one machine so
inherently suffers from one of the problems with these pseudo-STM is
that they don't make a copy of variables that they are accessing.
Since we have data distributed throughout the system though we are
already having to make copies, so I think that by implementing a cache
of foreign data (by putting some checks into the Location methods) we
can do this.

I will take a look at the MVar concept though, not familiar with
that :)

Seems to me though that there are very few changes we would need to
make to get a functioning (if not a tad slow) STM system to work, and
then build into that alot of fail safes for nodes that disappear but
also rework the operations so that we get some speed-up!

I am going to try write some basic examples over the next week to let
us have a test-bed of basic functionality we would need for critical
section support.

-Neil.

On Oct 20, 2:37 pm, Rick R <rick.richard...@gmail.com> wrote:
> I think you and I have differing definitions of Critical Sections, but for
> the general case of multiple node shared access to resources, I like the
> idea of STM. Also, Akka actors support a distributed STM already. We can
> either use Akka, or be heavily inspired by it :)
>
> Even though I'm already a believer, I'll read your paper today. In the

> meantime, here is is a slightly differing view.http://www.codecommit.com/blog/scala/improving-the-stm-multi-version-...

[Rick R]

I agree that we should allow read-only copies all over the system. The trick is what is the most efficient algorithm for managing writes and distributing the associated updates (if at all).

Project Darkstar takes this approach, but they use a coarse lock, simply because they are dealing with the latency of TCP/IP.  I agree in this case, whatever requires the least amount of messages (both serial and parallel) is the winner.

I'm not sure if there has been research done on which protocols (mvcc, vs stm vs central lock vs ...) require the least amount of messages.  I know that this has been thoroughly explored in the realm of paxos, outside of that, I would assume such research exists, but I don't know where.

[Bayani Portier]

The biggest question about distributed read systems, is latency to update.

 

You wind up with an asynchronous process problem, and you will have to manage race condition violations either by locking variables (which will need to be updated to a central controller, or pushed out to the multiple instances).

 

If you are gathering seed information, you will need to be careful of the temporal nature of the variables, as essentially, you are taking a memento of the state, rather than a reference.

 

Have to run to a meeting now, but I just wanted to write this down so that we don't forget to discuss.

 

-b

[Neil]

We don't need a centralised lock to perform locking, could always use
one of the distributed locking mechanisms (most of them are based on
Lamport Logical Clocks if I remember correclty).

Even if we had an STM system we would need some form of locking - at
least the ability to propose changes, wait for a response, them commit
changes.

STM negates the normal race conditions you would expect from mutual
exclusion, you don't need to ensure locks are taken in order for one
thing. The other major boon for STM is that it is easier to get decent
performance, whereas with mutual exclusion you are forced to fine-
grain your locks to get the optimal performance.

-Neil.

On Oct 20, 10:45 pm, Bayani Portier <bayani.port...@gmail.com> wrote:
> The biggest question about distributed read systems, is latency to update.
>
> You wind up with an asynchronous process problem, and you will have to
> manage race condition violations either by locking variables (which will
> need to be updated to a central controller, or pushed out to the multiple
> instances).
>
> If you are gathering seed information, you will need to be careful of the
> temporal nature of the variables, as essentially, you are taking a memento
> of the state, rather than a reference.
>
> Have to run to a meeting now, but I just wanted to write this down so that
> we don't forget to discuss.
>
> -b
>
>
>
> On Wed, Oct 21, 2009 at 2:56 AM, Rick R <rick.richard...@gmail.com> wrote:
> > I agree that we should allow read-only copies all over the system. The
> > trick is what is the most efficient algorithm for managing writes and
> > distributing the associated updates (if at all).
>
> > Project Darkstar takes this approach, but they use a coarse lock, simply
> > because they are dealing with the latency of TCP/IP.  I agree in this case,
> > whatever requires the least amount of messages (both serial and parallel) is
> > the winner.
>
> > I'm not sure if there has been research done on which protocols (mvcc, vs
> > stm vs central lock vs ...) require the least amount of messages.  I know
> > that this has been thoroughly explored in the realm of paxos, outside of
> > that, I would assume such research exists, but I don't know where.
>

[Bayani Portier]

I've read a bit on this now, and from what I see, we should probably consider temporal optimistic locking.

 

Basically a read lock is taken out on a variable, and when a write is performed, it will notify the process of a change in the variable. The process can then decide if it needs to ignore/ roll back to sub process / relaunch itself.

 

What are your thoughts on this?

 

-b

[Neil]

That sounds like a plan to me to be honest! It should give us enough
performance for very little overhead.

What we want to be able to do is cache reads to a variable locally,
that's the main thing in terms of performance as we won't have to
constantly update a remote object each time.

My only issue thus far is how to implement this without needs scala
language extensions or the like. I think if we access objects through
the Location class, we can put in checks before the object is
returned.

-Neil.

[Rick R]

That sounds like exactly what we need. I like the libertarian approach to decentralization.

From an implementation standpoint, we could just have a pub/sub system for the object updates. The subscription would be optional, so as to allow for optimizations where possible. Such a system then allows every node to be a database authority on some objects, rather than having a centralized database.

[Bayani Portier]

Here's an interesting paper on distributed locking.

 

http://www98.griffith.edu.au/dspace/bitstream/10072/6631/1/20864.pdf

 

-b

[Razie]

I’m a little confused by this thread…these are generic distributed
programming concepts and issues, applicable when a centralized piece
of code accesses remote objects…or distributed pieces of code access
remote objects. I don’t think they should be solved in any special way
for the swarm…if you need to enlist a bunch of local objects in a
distributed transaction monitor, so be it – no special “swarm” changes
needed…?

The point of the swarm is to get the code to move – there are in
essence no remote objects, since the code moves to them when it needs
them. It will not take the other pieces with it, except some locally
aggregated data (local vals/vars).

Critical section is a misnomer in this case: http://en.wikipedia.org/wiki/Critical_section
simply because when the swarm is local to a piece of data, it will
contend with local code not just other swarms, so classic locks must
be used.

Do you mean this is trying to deal with a scenario like this: code
reads local data on node 1 and moves on to node 2. Meanwhile, the data
on node 1 has changed and now our image is incorrect, especially if
the code now moves back to read it again?

This is a transactionality/consistency question: all the resources
must concur when the code completes. There’s a bunch of pessimistic
and a bunch of optimistic implementations, all dealing with Einstein’s
universally proven lack of synchronization between distant observers.
However, when adapting these to the swarm, there’s some issues:

1. while the code is co-located with the data, you would use local
means to ensure consistency of the data, i.e. synchronized() critical
sections or other locks, for the duration of the local access
2. while the code is away,
a. You can’t notify a piece of code of remote data changes – it’s not
a BPEL with asynchronous handlers…it’s just a piece of sequential
statements…maybe you could inject exceptions into it – hmm, maybe…but
that will mess up its stack trace (execution state)…
b. You do not know ahead of time what remote data you need (to acquire/
lock all resources)…you discover that as the code runs its course
through its if/else branches…
c. You can’t leave lingering remote locks, to pessimistically lock the
data…unless you start requiring and relying on other 3rd party
objects: the distributed lock managers.

Since data access is encapsulated in Ref(), we could simply track the
version of the data we read and, when the data has changed (the local
nodes will make sure the version changes) we’ll notice that upon re-
reading. Or, at the end, in a very 2PC manner, re-check all versions…
just before a “commit”.


Also, about local locks: we probably need a “with” block – just like
the delimited continuations, we need to mark the places in the code
where we use a local data:

with (ref) { // context is local and may place lock
… // context may move to different node
} // context has to move back to release the local lock

Although – in my point 2.b) I figured that local locks should not
linger as the swarm/context moves, so maybe in the “with” section, the
code gets really mad if you try to move it? Does this make the with()
{…} a critical section in the sense that the swarm doesn’t move?

with (ref) { // context is local and may place lock
… // context may NOT move to different node – what does it do if it
needs to?
} // context release the local lock and the MAY move

Cheers,
Razie