<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-text-flowed" style="font-family: -moz-fixed;
font-size: 12px;" lang="x-western">Hi,
<br>
<br>
within the context Cloud-TM project we have developed a new
partial replication algorithm (corresponding to distribution mode
of Infinispan) that guarantees serializability in a very scalable
fashion. We have called the algorithm GMU, Genuine Multiversion
Update Serializability, and we've integrated it into Infinispan
(5.0.0).
<br>
<br>
The source code is available on github:
<br>
<br>
<a class="moz-txt-link-freetext"
href="http://github.com/cloudtm/infinispan-5.0.0.SERIALIZABLE">http://github.com/cloudtm/infinispan-5.0.0.SERIALIZABLE</a>
<br>
<br>
GMU's key features are:
<br>
<br>
1. unlike any other partial replication protocol we are aware of,
GMU is the first distributed multi-versioned based partial
replication protocol that does not rely on a single global clock
in order to determine consistent snapshots. Conversely, the
protocol guarantees to involve only the nodes that maintain data
accessed by a committing transaction T (a property that is known
in literature as "genuineness"). This is a property that is
crucial, in our opinion, to achieve high scalability.
<br>
<br>
2. read-only tranasctions are never aborted, and do not need to be
validated at commit time, making them very fast. Read-only
transactions are guaranteed to observe a consistent snapshot of
the data using a novel mechanism based on vector clocks. Note that
in order to achieve this results we integrated in ISPN a
multiversion concurrency control, very similar to the one used in
PostgreSQL or JVSTM, that maintains multiple data item versions
tagged with scalars per each key.
<br>
<br>
3. The consistency guarantees ensured by GMU are a variant of
classic 1-Copy-Serialiability (1CS), and, more precisely,
"extended update serializable" (EUS). You can check the tech.
report in attach for more details on this, but, roughly speaking,
US guarantees that update transactions execute according to 1CS.
Concurrent read-only transactions, instead, may observe the
updates generated by two <b class="moz-txt-star"><span
class="moz-txt-tag">*</span>non-conflicting<span
class="moz-txt-tag">*</span></b> update transactions in
different order.
<br>
In practice, we could not think of any realistic application for
which the schedules admitted by US would represent an issue, which
leads us to argue that US is, in practical settings, as good as
1CS, but brings the key advantage of allowing way more scalable
(genuine) implementations.
<br>
<br>
We have evaluated GMU performance using up to 20 physical machines
in our in-house cluster, and in 40 VMs in the FutureGrid (and we
are currently trying to use more VMs in FutureGrid to see if we
can make it scale up to hundreds of machines... we'll keep you
posted on this!) with the YCSB (<a class="moz-txt-link-freetext"
href="https://github.com/brianfrankcooper/YCSB/wiki">https://github.com/brianfrankcooper/YCSB/wiki</a>)
and TPC-C benchmarks.
<br>
<br>
Our experimental results show that in low conflict scenarios, the
protocol performs as good as the existing Repeatable Read
implementation... and actually, in some scenarios, even slightly
better, given that GMU spares the cost of saving the values read
in the transactional context, unlike the existing Repeatable Read
implementation.
<br>
<br>
In high contention scenarios, GMU does pay a higher toll in terms
of aborts, but it still drastically outperform classic non-genuine
MVCC implementations as the size of the system grows. Also, we've
a bunch of ideas on how to improve GMU performance in high
contention scenarios... but that's another story! <span
class="moz-smiley-s3" title=";-)"></span>
<br>
<br>
You find the technical report at this url:<br>
<br>
<a class="moz-txt-link-freetext" href="http://www.inesc-id.pt/ficheiros/publicacoes/7549.pdf">http://www.inesc-id.pt/ficheiros/publicacoes/7549.pdf</a><br>
<br>
Comments are more than welcome of course! <br>
<br>
Cheers,
<br>
<br>
Paolo
<br>
<br>
-- <br>
<br>
Paolo Romano, PhD<br>
Coordinator of the Cloud-TM ICT FP7 Project (<a class="moz-txt-link-abbreviated" href="http://www.cloudtm.eu">www.cloudtm.eu</a>)<br>
Senior Researcher @ INESC-ID (<a class="moz-txt-link-abbreviated" href="http://www.inesc-id.pt">www.inesc-id.pt</a>)<br>
Invited Professor @ Instituto Superior Tecnico (<a class="moz-txt-link-abbreviated" href="http://www.ist.utl.pt">www.ist.utl.pt</a>)<br>
Rua Alves Redol, 9<br>
1000-059, Lisbon Portugal<br>
Tel. + 351 21 3100300<br>
Fax + 351 21 3145843<br>
Webpage <a class="moz-txt-link-freetext" href="http://www.gsd.inesc-id.pt/~romanop">http://www.gsd.inesc-id.pt/~romanop</a><br>
</div>
</body>
</html>