The KIPS Transactions:PartD (정보처리학회논문지D)

Korea Information Processing Society (한국정보처리학회)
권호 표지

A Concurrency Control Technique Using Optimistic Atomic Broadcast In Replicated Database Systems

중복 데이터베이스 시스템에서 낙관적인 원자적 방송을 이용한 동시성제어 기법

  • Published : 2001.10.01
Download PDF
⟨ Previous Next ⟩

Abstract

To process transactions in fully replicated database, an atomic broadcast is mainly used. In this case of using atomic broadcast, transactions can be delayed because of the coordinating step among servers before processing the transaction. In this paper, we propose an algorithm to resolve the problem of transaction delay. In the proposed algorithm, the transactions are processed by using the optimistic method. The operations of a transaction are performed in the site that it is submitted and its write operations its updates atomically in all replicated sites. Since the serializability of transaction is ensured by checking the sequence number of transactions in the completion-inspection step.

중복 데이터베이스 시스템에서 트랜잭션을 처리하기 위해서 원자적 방송이 주로 사용된다. 그런데 원자적 방송을 사용할 경우에는 트랜잭션을 처리하기 전에 먼저 서버들 사이에 조정단계가 선행되어야 하므로 트랜잭션 지연과 같은 문제점이 있다. 이 논문에서는 원자적 방송을 사용하여 트랜잭션을 처리할 경우에 발생되는 트랜잭션 지연문제를 해결할 수 있는 알고리즘을 제안한다. 이를 위해서 제안된 알고리즘에서 트랜잭션은 낙관적인 방법을 이용하여 처리하고, 판독연산은 트랜잭션이 제출된 사이트에서 수행된다. 그리고 기록연산은 중복된 모든 사이트에서 원자적으로 갱신이 이루어지도록 한다. 이렇게 함으로써 각 사이트의 클라이언트가 지역 데이터베이스에 제출한 연산을 모든 사이트에서 독립적으로 수행할 수 있게 되어 병행성이 향상되고 트랜잭션의 지연이 방지된다. 또한 트랜잭션이 직렬가능성은 완료 검사 단계에서 트랜잭션의 순서번호를 검사함으로서 보장되도록 한다.

Keywords

References

  1. D. Agrawal, G. Alonso, A. E. Abbadi, 'Exploiting Atomic Broadcast in Replicated Databases,' Inprocedings of EuroPar(EuroPar'97), Passau(Germany), 1997 https://doi.org/10.1109/ICDCS.1998.679498
  2. P. Bernstein, V. Hadzilacos, N. Goodman, Concurrency Control and Recovery in Database System, Addison Weslay, 1987
  3. B. Kemme, Gustavo Alonso, 'A Suite of Database Replication Protocols Based on Group Communication Primitive,' In Proceedings of the 18th International Conference on Distributed Computing Systems(ICDCS), Amsterdam, The Netherlands, May, 1998
  4. B. Kemme, Fernando Pedone, 'Processing Transactions over Optimistic Atomic Broadcast Protocols,' In Proceedings of the International Conference on Distributed Computing Systems, Austin Texas, June, 1999 https://doi.org/10.1109/ICDCS.1999.776544
  5. Fernando Pedone, A.Schiper, 'Optimistic Atomic Broadcast,' In Proceedings of the 16th International Symposium on Distributed Computing, DISC '98, WDAG, September, 1998
  6. M. Wiesmann, Fernando Pedone, A. Schiper, B. Kemme, and G.Alonso, 'Understanding Replication in Databases and Distributed Systems,' In Proceedings of 20th International Conference on Distributed Computing Systems(ICDCS '2000), pp.264-274, 2000 https://doi.org/10.1109/ICDCS.2000.840959
  7. J. Gray, P. Helland, D. Shasha, 'The Dangers of Replication and a Solution,' in Proc. of the ACM SIGMOD, pp.568-574, 1996
  8. P. A. Benstein, N. Goodman, 'An Algorithm for Concurrency Control and Recovery in Replicated Distributed Database,' ACM Trans. on Database Systems, Vol.9, pp.596-615, 1984 https://doi.org/10.1145/1994.2207
  9. J. Gray, P. Homan, H. Korth, and R.Obermark, 'A Strawman Analysis of the Probability of Wait and Deadlock,' Technical Report RJ2131, IBM San Jose Research Laboratory, 1981
  10. B. Kemme, Fernando Pedone, Gustavo Alonso, Andre Schoper, 'Using Optimistic Atomic Broadcast in Transaction Processing System,' Technical Report, Department of Computer Science, ETH Zurich, March, 1999
  11. B. Kemme, and G. Alonso. 'A Suite of Database Replication Protocols Based on Group Communication Primitives,' In Proceedings of the 18th International Conference on Distributed Computing System(ICDCS), Amsterdam, The Netherlands, May, 1998 https://doi.org/10.1109/ICDCS.1998.679498
  12. A. Schiper and M. Raynal. 'From Group Communication to Transaction in Distributed Systems,' Communications of the ACM, pp.84-87, April, 1996 https://doi.org/10.1145/227210.227230
  13. Yuri Breitbart and Henry F.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 https://doi.org/10.1145/263661.263681
  14. P. Chundi, D. J. Rosenkratz, and S. S. Ravi, 'Deferred Updates and Data Placement in Distributed Databases,' In Proceedings of the Twelveth International Conference on Data Engineering, New Orleans Louisiana, 1996 https://doi.org/10.1109/ICDE.1996.492196
  15. J. N. Gray and A. Reuter, 'Transaction Processing : Concepts and Techniques,' Morgan Kaufmann, 1993
  16. H. T. Kung and J. T. Robinson. 'On Optimistic Methods for Concurrency Control, ACM Transactions on Database Systems,' Vol.6, No.2, pp.213-226, June, 1981 https://doi.org/10.1145/319566.319567
  17. R. Agrawal, M. Carey, and M. Livny. 'Concurrency Control Performance Modelling : Alternatives and Implications,' ACM Transactions on Database Systems, Vol.12, No.4, pp.609-954, December, 1987 https://doi.org/10.1145/32204.32220
  18. D. Agrawal, A. El Abbadi, and R. Steinke. 'Epidemic Algorithms in Replicated Database,' In Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Tucson (USA), May, 1997
  19. Fernando Pedone, Rachid Guerraoui, Andre Schiper, 'The Database State Machine Approach,' Technical Reports SSC/1999/008, Ecole Polytechnique Federal de Lausanne, Switzerland, March, 1999