Seminars at the Faculty of Informatics

Mrs. Vaide Narvaez, Wednesday May 6th, 2009 at 14:00, SI-006

The dissertation committee is composed of:

  • Prof. Fernando Pedone, UniversitÓ della Svizzera italiana, Lugano (advisor)
  • Prof. Mehdi Jazayeri, UniversitÓ della Svizzera italiana, Lugano (internal member)
  • Prof. Antonio Carzaniga, UniversitÓ della Svizzera italiana, Lugano (internal member)
  • Prof. Ricardo JimÚnez-Peris, Universidad PolitÚcnica de Madrid, Spain (external member)
  • Prof. Bettina Kemme, McGill University, MontrÚal, Canada (external member)
  • Prof. Rui Oliveira, Universidade do Minho, Portugal (external member)



Performance and high-availability are the crucial factors in the development of nowadays distributed database systems. Both of these challenges are commonly addressed by means of the same technique, database replication. The overall throughput of the system is increased by leveraging parallel computation on different sites, and in case of replica failures, availability is improved by redirecting requests to operational replicas. However, providing transparent database replication is not an easy task. Although database replicas should be as independent of each other as possible for performance and availability reasons, some synchronization is required to provide data consistency.

This thesis is about non-intrusive (or middleware) database replication protocols. More specifically, this thesis focuses on the development of practical replication protocols that use off-the-shelf database engines, take advantage of group communication primitives, cope with failures of system components, behave correctly, and, by exploiting the specific characteristics of the application, achieve high performance.

In the first part of this thesis we address the following problem:á non-intrusive database replication protocols cannot obtain fine-grained information about transactions due to limited access to the database engine internals. We make three contributions in this part. The first contribution is the Multiversion Database State Machine, a middleware extension of the Database State Machine, a kernel-based replication approach. The Multiversion Database State Machine assumes predefined, parameterized transactions. The particular data items accessed by a transaction depend on the transaction's type and the parameters provided by the application program when the transaction is instantiated. The second contribution of this thesis is a technique to bypass the extraction and propagation of readsets and writesets in non-intrusive replication protocols. We present the SQL Inspector, a tool capable to automatically identify conflicting transactions before their actual execution by partially parsing them. The performance of the Multiversion Database State Machine can be further improved if transactions execute at carefully chosen database sites. Thus, the third contribution of this thesis is the conflict-aware load-balancing techniques. To keep the abort rate low despite the coarse granularity of non-intrusive replication protocols, conflict-aware load-balancing techniques attempt to reduce the number of conflicting transactions executing on distinct database sites and seek to increase the parallelism among replicas.

In the second part of this thesis we investigate correctness criteria for replicated databases from the client's perspective. We study the performance cost of ensuring stronger consistency degrees in the context of three middleware replication protocols: primary-backup, optimistic update-everywhere and BaseCON, a non-intrusive replication protocol that takes advantage of workload characterization techniques to increase the parallelism in the system. BaseCON makes use of total-order broadcast primitives to provide strong consistency and fault-tolerance. A lightweight scheduler interposed between clients and the database replicas allows the system to adapt easily to the correctness criterion required and serves as a load-balancer for read-only transactions.

In the last part of this thesis we address the problem of partial replication. In particular, we investigate the effects of distributed transactions on the abort rate of such systems. Our contribution in this area is a probabilistic model of transaction abort rates for two different concurrency control mechanisms: lock- and version-based. The former models the behavior of a replication protocol providing one-copy-serializability; the latter models snapshot isolation.