[infinispan-dev] CloudTM: Additional Atomic broadcast based replication mechanism integrated in Infinispan

[Bela Ban]

On 4/16/11 10:47 PM, Paolo Romano wrote:
> Hi,
>
> at INESC-ID, we have just finished brewing another (full) replication
> protocol for Infinispan, in the context of the Cloud-TM project. The
> credits go to Pedro Ruivo, a Msc student working in our group, who
> developed this as part of his thesis work.
>
> Like the current Infinispan's 2PC-based replication mechanism, also this
> is a multi-master scheme in which transactions are executed locally by
> any node and without any coordination among replicas till the commit phase.
>
> Rather than using 2PC, however, this scheme scheme relies on a single
> Atomic broadcast (AB, a.k.a. total order broadcast) to disseminate
> transactions' writesets while ensuring totally ordered delivery of
> messages across the various nodes.
>
> The replication scheme is, in fact, quite simple. Upon delivery of the
> AB with the writeset of a transaction, we ensure that each replica
> executes the following operations in the order established by the AB layer:
> - acquiring locks on the writeset, possibly stealing the lock from any
> locally running transaction (and flagging it as aborted)
> - performing a write-skew check (in case Infinispan is configured to do
> this check)
> - applying the writeset
> - release the locks.


Using atomic broadcasts instead of 2PC to disseminate updates is 
something I always thought was a good idea !
(I think something similar has been implemented in the context of a 
research project at ETH Zurich in Gustavo Alonzo's group (with Postgresql))

I think your performance results show that this schema results in fewer 
(lock) collisions and faster updates - despite the sequencer approach 
used. This *might* even be faster with a token based total order protocol...


> ABcast can be implemented in many many ways, but for simplicity we used
> the sequencer based implementation available in JGroups. This scheme is
> quite simple:
> - upon an atomic broadcast, the message is simply broadcast to all nodes
> - upon receipt of the message, however, the nodes do not deliver it
> immediately to the application layer (Infinispan in this case). Instead,
> a special node (e.g. the one with lesser id in the group), namely the
> sequencer, broadcasts back the order in which processes should deliver
> this message.
> - finally, the nodes deliver the atomic broadcast message in the order
> specified by the sequencer.
>
> The main advantage of this replication mechanism is that it avoids
> distributed deadlocks, which makes its performance way better at high
> contention


+1


  (note that local deadlocks may still occur, as Infinispan's
> encounter locking scheme does not prevent them. But these are much more
> rare as the number of "contending" threads is much lower).
> Further, locks are held shorter with respect to 2PC.


Exactly !


>  With 2PC, the
> cohort nodes, maintain the locks on behalf of the coordinator, since the
> reception of the prepare and until they receive the commit message. This
> encompasses a round trip (collecting votes from all cohorts, and sending
> back the decision). With the ABcast scheme, instead, the locks acquired
> on behalf of remote transactions, are held only for the time strictly
> required to writeback locally.
> Finally the sequencer is, in fact, a privileged node, as it can commit
> transactions much faster than the other nodes, as it can self-assign the
> order in which transactions need to be processed.


This is something I haven't thought about yet. JGroups itself doesn't 
re-arrange the total order; it basically establishes it on a 
first-come-first-serve basis. But you're right, arranging incoming 
requests into a different total order might make sense. Example: if you 
have P1, R2, P2, P3, R2, it might make sense to package {P1 and P2} and 
{R1 and R2} together, to make this even more efficient... Interesting !



>  This may not be very
> fair at high contention rate, as it gets higher chances of committing
> transactions, but does make it MUCH faster overall.


Agreed. Compare it to java.util.concurrent reentrant locks: fairness 
slows down this implementation, so IMO non-fairness is ok as long as 
there is no starvation.



> - To bundle or not to bundle?, page 4: the throughput results shown in
> page 1 have actually a little trick :-P We used "some" bundling ONLY in
> the case of transactions spanning 100K data items. We noticed that w/o
> bundling, the commit time duration of the AB-based scheme got way
> lousier and experimented with a few bundling values till we got decent
> performance (See plot at page 4). This is explainable since with 100K
> keys, being the contention low, less transactions get aborted along
> their execution. This means that more transaction reach the commit
> phase, and, in its turn, more atomic broadcasts hit the network layer,
> and more load for the sequencing node. Bundling, as you can see in page
> 4, makes the trick however. We did not retry the tests with the other
> protocols with and w/o bundling, as this would have been very time
> consuming. BTW, I believe that the results would not have been very
> different.


Did you apply bundling at the configuration level, or per message ? Not 
sure if you know about the ability to override bundling on a per-message 
basis: the NO_BUNDLE flag set in a message overrides the bundling 
configuration, and a message with such a flag set is sent immediately.



> Let me open a small parenthesis about bundling: this can be an extremely
> effective weapon, but manual configuration is a bid headache and
> extremely time consuming. I believe that it would be very useful to have
> some self-tuning mechanism for it in JGroups. In fact, we've recently
> got very nice results using Reinforcement-learning to tackle this
> problem (well, to be precise, not really the same problem, but a very
> similar one):
>
> http://www.inesc-id.pt/ficheiros/publicacoes/7163.pdf


I'll take a look. In the context of ergonomics, I've been wanting to set 
the max_bundle_time value dynamically, so this input is certainly helpful !


> ...but I've implemented the prototype of this solution in Appia, as I
> knew it much better than JGroups. What do you think about integrating a
> similar mechanism in JGroup's ergonomics?


+1. Definitely something I've been wanting to do...




-- 
Bela Ban
Lead JGroups / Clustering Team
JBoss