Technical report detail

P-Store: Genuine Partial Replication in Wide Area Networks

by Nicolas Schiper, Pierre Sutra, Fernando Pedone

Partial replication is a way to increase the scalability of replicated systems since updates only need to be applied to a subset of the system's sites, thus allowing replicas to handle independent parts of the workload in parallel. In this paper, we propose P-Store, a partial database replication protocol for wide area networks. In P-Store, each transaction T optimistically executes on one or more sites and is then certified to guarantee serializability of the execution. The certification protocol is genuine, it only involves sites that replicate data items read or written by T, and incorporates a mechanism to minimize a convoy effect. P-Store makes a thrifty use of an atomic multicast service to guarantee correctness: no messages need to be multicast during T's execution and a single message is multicast to certify T. This is in contrast to previously proposed solutions that either require multiple atomic multicast messages to execute T, are non-genuine, or do not allow transactions to execute on multiple sites. Experimental evaluations reveal that the convoy effect plays an important role even when one percent of the transactions are global, that is, they involve multiple sites. We also compare the scalability of our approach to a fully replicated solution when the proportion of global transactions and the number of sites vary.

Technical report 2010/03, April 2010

BibTex entry

@techreport{10pstore, author = {Nicolas Schiper and Pierre Sutra and Fernando Pedone}, title = {P-Store: Genuine Partial Replication in Wide Area Networks}, institution = {University of Lugano}, number = {2010/03}, year = 2010, month = apr }