Yuri Breitbart
Rajeev Rastogi
ABSTRACT
Replication is often used in many distributed systems 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. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to eliminate 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 shows that our protocols outperform existing protocols over a wide range of workloads.
- ABKW98.Todd Anderson, Yuri Breitbart, Henry E Korth, and Avishai Wool. Replication, consistency and practicality: Are these mutually exclusive? In Procs. of ACM SIGMOD International Conf. on Management of Data, Seattle, WA, 1998. Google Scholar
Digital Library
- BK97.Yuri Breitbart and Henry E Korth. Replication and consistency: Being lazy helps sometimes. In Proceedings of the ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems, Tucson, Arizona, 1997. Google ScholarDigital Library
- BKRSS98.Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, and Avi Silberschatz. Update propagation algorithms for replicated database systems. Technical R,,~port BL0112370-981028-11TM, Bell Labs, Oc~:ober 1998.Google Scholar
- BLRSSS97.Phil Bohannon, Daniel Lieuwen, Rajeev Rastogi, S. Seshadri, Avi Silberschatz, and S. Sudarshan. The architecture of the dali main memory storage manager. Multimedia Tools and Applications, 4(2), March 1997. Google ScholarDigital Library
- CRR96.P. Chundi, D. J. Rosenkratz, and S. S. Ravi. Deferred updates and data placement in distributed databases, in Proceedings of the Twelvet,~ International Conference on Data Engineering, New Orleans, Louisiana, 1996. Google ScholarDigital Library
- ENRS97.Guy Even, Joseph (Seffi) Naor, Satish Rao, and Baruch Schieber. Fast approximate graph partitioning algorithms. In Proceedings of the 8th A CM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, 1997. Google ScholarDigital Library
- GHKO81.J. Gray, E Homan, H. Korth, and R. Oberrnack. A strawman analysis of the probability of wait and deadlock. Technical Report RJ2131, }BM San Jose Research Laboratory, 1981.Google Scholar
- GHOS96.J. Gray, Pat Helland, Patrick O'Neil, and i)ennis Shasha. The dangers of replication and a solution, in Proceedings of the ACM SIG~'OD Conference, Montreal, Quebec, Canada, 1996. Google ScholarDigital Library
- GJ79.M.R. Garey and D. S. Johnson. Computers and Intractabili~.: A Guide to the TheoO' of NP- Completeness. W.H. Freeman, San Francisco, California, 1979. Google ScholarDigital Library
- LMT90.T. Leighton, F. Makedon, and S. TragouJas. Approximation algorithms for vlsi partitioxfing problems. In IEEE International Symposiun~ on Circuits and Systems, 1990.Google ScholarCross Ref
- SK80.Avi Silberschtaz and Zvi Kedem. Consistency in hierarchical database systems. Journal oj'the ACM, 27(1), January 1980. Google ScholarDigital Library
- ST97.H.D. Simon and S-H. Teng. How goocl is recursive bisection. SIAM Journal of Scien.'ific Computing, 1997. Google ScholarDigital Library
Index Terms
- Update propagation protocols for replicated databates
Recommendations
Update propagation protocols for replicated databates
Replication is often used in many distributed systems 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 ...
Update Propagation of Replicated Data in Distributed Spatial Databases
DEXA '99: Proceedings of the 10th International Conference on Database and Expert Systems ApplicationsWhen spatial objects are replicated at several sites in the network, the updates of a long transaction in a specific site should be propagated to the other sites for maintaining the consistency of replicated spatial objects. If any two or more ...
Comments