Update Propagation Protocols For Replicated Databases

Yuri Breitbart       K. V. Raghavan       Rajeev Rastogi
Bell Labs       University Of Wisconsin       Bell Labs
yuri@research.bell-labs.com       raghavan@cs.wisc.edu       rastogi@research.bell-labs.com

S. Seshadri*       Avi Silberschatz
Bell Labs       Bell Labs
seshadri@research.bell-labs.com       avi@research.bell-labs.com

Abstract

Replication is often used in many distributed systems (e.g., distributed data warehouses and web sites) to provide a higher level of performance, reliability and availability. Lazy replica update protocols, which propagate updates to replicas through independent transactions after the original transaction commits, have become popular with database vendors due to their superior performance characteristics. However, if lazy protocols are used indiscriminately, they can result in non-serializable executions. In this paper, we propose two new lazy update protocols that guarantee serializability but impose a much weaker requirement on data placement than earlier protocols for ensuring serializability. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to relax all requirements on data placement. The extension is a hybrid protocol that propagates as many updates as possible in a lazy fashion. We implemented our protocols on the Datablitz database system product developed at Bell Labs. We also conducted an extensive performance study which showed that our protocol outperforms existing protocols over a wide range of workloads.