Subscribe Now Subscribe Today
Research Article
 

A Distributed Algorithm for SI Transactions Serializability in Cloud Computing



Huang Bin, Peng Yuxing and Peng Xiaoning
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
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.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  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.

DOI: 10.3923/itj.2013.8435.8445

URL: https://scialert.net/abstract/?doi=itj.2013.8435.8445
 

REFERENCES

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

2:  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
CrossRef  |  

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

4:  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  |  

5:  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  |  

6:  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
Direct Link  |  

7:  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-

8:  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

9:  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  |  

10:  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
CrossRef  |  

11:  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  |  

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

13:  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
CrossRef  |  

14:  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  |  

15:  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
Direct Link  |  

16:  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
CrossRef  |  

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

18:  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
CrossRef  |  

19:  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
Direct Link  |  

20:  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  |  

21:  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.

22:  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
Direct Link  |  

23:  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
CrossRef  |  

24:  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
CrossRef  |  

25:  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
Direct Link  |  

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

27:  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
CrossRef  |  

28:  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  |  

29:  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
CrossRef  |  

©  2021 Science Alert. All Rights Reserved