Ben Vandiver, Hari Balakrishnan, Barbara Liskov, Samuel Madden
ACM SOSP, Stevenson, WA, October 2007
This paper describes the design, implementation, and evaluation of a replication scheme to handle Byzantine faults in transaction processing database systems. The scheme compares answers from queries and updates on multiple replicas which are unmodified, off-the-shelf systems, to provide a single database that is Byzantine fault tolerant. The scheme works when the replicas are homogeneous, but it also allows heterogeneous replication in which replicas come from different vendors. Heterogeneous replicas reduce the impact of bugs and security compromises because they are implemented independently and are thus less likely to suffer correlated failures.
The main challenge in designing a replication scheme for transaction
processing systems is ensuring that the different replicas execute
transactions in equivalent serial orders while allowing a high degree
of concurrency. Our scheme meets this goal using a novel concurrency
control protocol, commit barrier scheduling (CBS). We have
implemented CBS in the context of a replicated SQL database, HRDB
(Heterogeneous Replicated DB), which has been tested with unmodified
production versions of several commercial and open source databases
as replicas. Our experiments show an HRDB configuration that can
tolerate one faulty replica has only a modest performance overhead
(about 17% for the TPC-C benchmark). HRDB successfully masks
several Byzantine faults observed in practice and we have used it to
find a new bug in MySQL.
[PDF (284KB)]
Bibtex Entry:
@inproceedings{vandiver2007tolerating,
author = "Ben Vandiver and Hari Balakrishnan and Barbara Liskov and Samuel Madden",
title = "{Tolerating Byzantine Faults in Transaction Processing Systems Using Commit Barrier Scheduling}",
booktitle = {ACM SOSP},
year = {2007},
month = {October},
address = {Stevenson, WA}
}