HOME JOURNALS CONTACT

Information Technology Journal

Year: 2013 | Volume: 12 | Issue: 24 | Page No.: 8435-8445
DOI: 10.3923/itj.2013.8435.8445
A Distributed Algorithm for SI Transactions Serializability in Cloud Computing
Huang Bin, Peng Yuxing and Peng Xiaoning

Abstract: There are well known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that individually maintain consistency. Until now, there are some ways to prevent these anomalies only in single computer and there are not the corresponding solving methods in cloud computing. This paper describes our PDCC algorithm to detect cycles in a snapshot isolation dependency graph and abort transactions to break the cycle in cloud computing. The algorithm ensures serializable executions for SI transactions in cloud computing. Based on the transaction concurrency control of Percolator, we have implemented our algorithm in an open source cloud database system (HBase) and our performance study shows that PDCC throughput and scalability are good.

Fulltext PDF

How to cite this article
Huang Bin, Peng Yuxing and Peng Xiaoning, 2013. A Distributed Algorithm for SI Transactions Serializability in Cloud Computing. Information Technology Journal, 12: 8435-8445.

Keywords: Cloud computing, transaction, SI and dependency graph

REFERENCES
  • Adya, A., 1999. Weak consistency: A generalized theory and optimistic implementations for distributed transactions. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA., USA.

  • Adya, A., B. Liskov and P. O'Neil, 2000. Generalized isolation level definitions. Proceedings of the 16th International Conference on Data Engineering, February 29-March 3, 2000, San Diego, CA., USA., pp: 67-78.

  • ANSI, 1992. Database language-SQL. American National Standard X3.135-1992, November 1992. http://www.itl.nist.gov/div897/ctg/dm/sql_info.html.

  • Cooper, B.F., R. Ramakrishnan, U. Srivastava, A. Silberstein and P. Bohannon et al., 2008. PNUTS: Yahoo!'s hosted data serving platform. Proc. VLDB Endowment, 1: 1277-1288.
    Direct Link    

  • Berenson, H., P. Bernstein, J. Gray, J. Melton, E. O'Neil and P. O'Neil, 1995. A critique of ANSI SQL isolation levels. ACM SIGMOD Rec., 24: 1-10.
    CrossRef    

  • Peng, D. and F. Dabek, 2010. Large-scale incremental processing using distributed transactions and notifications. Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, October 4-6, 2010, Vancouver, Canada, pp: 1-15.

  • Brewer, E.A., 2000. Towards robust distributed systems. Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, July 16-19, 2000, Portland, OR., USA., pp: 7-.

  • Chang, F., J. Dean, S. Ghemawat, W.C. Hsieh and D.A. Wallach et al., 2006. Bigtable: A distributed storage system for structured data. Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, November 6-8, 2006, Incline Village, Nevada, USA., pp: 205-218.

  • Fekete, A., E. O'Neil and P. O'Neil, 2004. A read-only transaction anomaly under snapshot isolation. ACM SIGMOD Rec., 33: 12-14.
    CrossRef    

  • Fekete, A., 2005. Allocating isolation levels to transactions. Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, June 13-17, 2005, Baltimore, MD., USA., pp: 206-215.

  • Fekete, A., D. Liarokapis, E. O'Neil, P. O'Neil and D. Shasha, 2005. Making snapshot isolation serializable. ACM Trans. Database Syst., 30: 492-528.
    CrossRef    

  • Fekete, A., S.N. Goldrei and J.P. Asenjo, 2009. Quantifying isolation anomalies. Proc. VLDB Endowment, 2: 467-478.
    Direct Link    

  • DeCandia, G., D. Hastorun, M. Jampani, G. Kakulapati and A. Lakshman et al., 2007. Dynamo: Amazon's highly available key-value store. Proceedings of 21st ACM SIGOPS Symposium on Operating Systems Principles, October 14-17, 2007, Stevenson, WA, USA, pp: 205-220.

  • Vo, H.T., C. Chen and B.C. Ooi, 2010. Towards elastic transactional cloud storage with range query support. Proc. VLDB Endowment, 3: 506-514.
    Direct Link    

  • Levandoski, J.J., D.B. Lomet, M.F. Mokbel and K.K. Zhao, 2011. Deuteronomy: Transaction support for cloud data. Proceedings of the 5th Biennial Conference on Innovative Data Systems Research, January 9-12, 2011, Asilomar, CA., USA., pp: 123-133.

  • Cahill, M., U. Rohm and A. Fekete, 2008. Serializable isolation for snapshot databases. Proceedings of the ACM SIGMOD International Conference on Management of Data, June 9-12, 2008, Vancouver, Canada, pp: 729-738.

  • Cahill, M., U. Rohm and A. Fekete, 2009. Serializable isolation for snapshot databases. ACM Trans. Database Syst., Vol. 34, No. 4.
    CrossRef    

  • Alomari, M., M. Cahill, A. Fekete and U. Rohm, 2008. The cost of serializability on platforms that use snapshot isolation. Proceedings of the IEEE 24th International Conference on Data Engineering, April 7-12, 2008, Cancun, Mexico, pp: 576-585.

  • Helland, P., 2007. Life beyond distributed transactions: An apostate's opinion. Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research, January 7-10, 2007, Asilomar, CA., USA., pp: 132-141.

  • Gilbert, S. and N. Lynch, 2002. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 3: 51-59.
    CrossRef    Direct Link    

  • Das, S., S. Agarwal, D. Agrawal and A.E. Abbadi, 2010. ElasTraS: An elastic, scalable and self managing transactional database for the cloud. UCSB Computer Science Technical Report 2010-04, University of California, Santa Barbara, CA., USA., pp: 1-14.

  • Das, S., D. Agrawal and A.E. Abbadi, 2009. ElasTraS: An elastic transactional data store in the cloud. Proceedings of the Workshop on Hot Topics in Cloud Computing, June 14-19, 2009, San Diego, CA., USA., pp: 1-5.

  • Das, S., D. Agrawal and A.E. Abbadi, 2010. G-store: A scalable data store for transactional multi key access in the cloud. Proceedings of the 1st ACM Symposium on Cloud Computing, June 10-11, 2010, Indianapolis, IN., USA., pp: 163-174.

  • Revilak, S., P.E. O'Neil and E.J. O'Neil, 2011. Precisely serializable snapshot isolation (PSSI). Proceedings of the IEEE 27th International Conference on Data Engineering, April 11-16, 2011, Hannover, Germany, pp: 482-493.

  • Jorwekar, S., A. Fekete, K. Ramamritham and S. Sudarshan, 2007. Automating the detection of snapshot isolation anomalies. Proceedings of the 33rd International Conference on Very Large Data Bases, September 23-28, 2007, University of Vienna, Austria, pp: 1263-1274.

  • Vogels, W., 2009. Eventually consistent. Commun. ACM-Rural Eng. Dev., 52: 40-44.
    CrossRef    

  • Wei, Z., G. Pierre and C.H. Chi, 2009. Scalable transactions for web applications in the cloud. Proceedings of the 15th International Euro-Par Conference, August 25-28, 2009, Delft, The Netherlands, pp: 442-453.

  • Zhang, C. and H. De Sterck, 2011. HBaseSI: Multi-row distributed transactions with global strong snapshot isolation on clouds. Scalable Comput.: Pract. Experience, 12: 209-226.
    Direct Link    

  • Zhang, C. and H. De Sterck, 2010. Supporting multi-row distributed transactions with global snapshot isolation using bare-bones HBase. Proceedings of the 11th IEEE/ACM International Conference on Grid Computing, October 25-28, 2010, Brussels, Belgium, pp: 177-184.

    • © Science Alert. All Rights Reserved