3:47 p.m.
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.
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 (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. 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 may not be very
fair at high contention rate, as it gets higher chances of committing
transactions, but does make it MUCH faster overall.
Concerning blocking scenarios in case of failures. Just like 2PC is
blocking in case of crashes of a node coordinating a transaction, this
replication scheme is also blocking, but this time in case of crashes of
the sequencer. The comparison in terms of liveness guarantees seem
therefore quite fair. (Note that it would have been possible to make
this replication mechanism non-blocking, at the cost of one extra
communication step. But we opted not to do it, to compare protocols more
fairly).
To evaluate performance we ran the same kind of experiments we used in
our recent mail where we evaluted a Primary backup-based replication
scheme. All nodes only do write operations, transactions of 10
statements, one of which being a put. Accesses are uniformly distributed
to 1K, 10K, 100K data items. Machines are 8cores, 8GB RAM, radargun is
using 10 threads per ndoe.
Summary of results (see attached pdf):
- Throughput, page 1: the plots show significant speedups. Especially at
high contention, where 2PC stumbles upon very frequent distributed
deadlocks. Note that we enabled deadlock detection in all experiments
running 2PC.
- Abort rate, page 2: abort rates are similar in both protocols (note
the logscale on y-axis). But the AB-based solution, avoiding deadlocks,
detects the need to abort transactions much faster than 2PC.
- Average Commit duration, page 3: at high contention, 2PC trashes due
to deadlocks (despite the deadlock detection mechanism), and this is
reflected in the Avg. commit duration as well. In the other cases (10K
and 100K keys), where there is less contention, the commit duration of
the two protocols is similar (see next).
- 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.
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
...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?
Back to replication: we are now working on a similar solution for
partial replication (a.k.a. distribution in Infinispan).
I'll keep you posted on our progresses!
Cheers,
Paolo
PS: The code is available on GitHUB, if you want to take a look at it:
https://github.com/cloudtm/infinispan/tree/abcast_replication