Efficient Processing of Client Transactions in Real-Time | Distributed and Parallel Databases Skip to main content
Springer Nature Link
Log in

Efficient Processing of Client Transactions in Real-Time

  • Published:
Distributed and Parallel Databases Aims and scope Submit manuscript

Abstract

In traditional client-server databases, a transaction and its requisite data have to be colocated at a single site for the operation to proceed. This has usually been achieved by moving either the data or the transaction. However, the availability of high-bandwidth networking options has led users of today's systems to expect real-time guarantees about the completion time of their tasks. In order to offer such guarantees in a client-server database system, a transaction should be processed by any means that allows it to meet its deadline. To this end, we explore the option of moving both transactions and data to the most promising sites for successful completion. We propose a load-sharing framework that oversees the shipment of data and transactions so as to increase the efficiency of a cluster consisting of a server and a number of clients. Here, efficiency is defined as the percentage of transactions successfully completed within their deadlines by the cluster. The suitability of a client for processing a transaction is measured with respect to the availability of the transaction's required data in its local cache. In addition to the load-sharing algorithm, we use the concept of grouped locks, along with transaction deadline information, in order to schedule the movement of data objects in the cluster in a more efficient manner. We evaluate the real-time processing performance of the client-server architecture using detailed experimental testbeds. Our evaluation indicates that it is possible, in many situations, to achieve better performance than a centralized system.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Abbott and H. Garcia-Molina, "Scheduling real-time transactions: Aperformance evaluation," ACMTrans-actions on Database Systems, vol. 17, no. 3, 1992.

  2. S. Abiteboul, V. Vianu, B. Fordham, and Y. Yesha, "Relational transducers for electronic commerce," in Proceedings of ACM Symposium on Principles of Database Systems, Seattle, WA, June 1998.

  3. Akamai.com, "Internet infrastructure service: An essential component for business success on the internet," http://www.akamai.com/en/html/services/white paper library.html, 2001.

  4. M. Aron, P. Druschel, and W. Zwaenepoel, "Cluster reserves: A mechanism for resource management in cluster-based network servers," in Proceedings of ACM-SIGMETRICS Conference, Santa Clara, CA, June 2000.

  5. S. Banerjee and P. Chrysanthis, "Data sharing and recovery in gigabit-networked databases," in Proceedings of the Fourth International Conference on Computer Communications and Networks, Las Vegas, NV, September 1995.

  6. K. Baumartner, R. Kling, and B. Wah, "Implementation of GAMMON: An efficient load balancing strategy for a local computer system," in Proceedings of the International Conference on Parallel Processing, Aug. 1989, vol. 2, pp. 77–80.

    Google Scholar 

  7. A. Bestavros, "Load profiling: A methodology for scheduling real-time tasks in a distributed system," in Proceedings of the IEEE International Conference on Distributed Computing Systems, Baltimore, MD, USA, May 1997.

  8. A. Bestavros and D. Spartiotis, "Probabilistic job scheduling for distributed real-time applications," in Pro-ceedings of the First IEEE Workshop on Real-Time Applications, New York, NY, USA, May 1993.

  9. W. Bolosky, J. Douceaur, D. Ely, and M. Theimer, "Feasibility of serverless distributed file system deployed on an existing set of desktop PCs," in Proceedings of ACM-SIGMETRICS Conference, Santa Clara, CA, June 2000.

  10. F. Bonomi and A. Kumar, "Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler," IEEE Transactions on Computers, vol. 39, no 10, pp. 1232–1250, 1990.

    Google Scholar 

  11. A. Bouguettaya, B. Benatallah, L. Hendra, M. Ouzzani, and J. Beard, "A dynamic architecture for organizing and querying web-accessible databases," IEEE Transaction on Knowledge and Data Engineering, vol. 12, no. 5, pp. 779–801, Sept./Oct. 2000.

    Google Scholar 

  12. M. Carey, M. Franklin, M. Livny, and E. Shekita, "Data caching tradeoffs in client-server DBMSarchitecture," in Proceedings of the 1991 ACM SIGMOD Conference, Denver, CO, May 1991.

  13. R. Cattell, Object Data Management: Object-Oriented and Extended Relational Database Systems, Addison Wesley: Reading, MA, 1991.

    Google Scholar 

  14. D. Chatziantoniou, "Ad hoc OLAP: Expression and evaluation," in Proceedings of the 15th International Conference on Data Engineering, IEEE Computer Society: Sydney, Austrialia, March 1999.

    Google Scholar 

  15. Y. Chow and W. Kohler, "Models for dynamic load balancing in a heterogenous multiple processor system," IEEE Transactions on Computers, vol. 28, no. 5, pp. 334–361, 1979.

    Google Scholar 

  16. A. Delis and N. Roussopoulos, "Performance comparison of three modern DBMS architectures," IEEE Trans-actions on Software Engineering, vol. 19, no. 2, pp. 120–138, 1993.

    Google Scholar 

  17. D. DeWitt, D. Maier, P. Futtersack, and F. Velez, "A study of three alternative workstation-server architectures for object-oriented database systems," in Proceedings of the 16th International Conference on Very Large Data Bases, 1990, pp. 107–121.

  18. D. Eager, E. Lazowska, and J. Zahorjan, "Adaptive load sharing in homogeneous distributed systems," IEEE Transactions on Software Engineering, vol. 12, no. 5, pp. 662–675, 1986.

    Google Scholar 

  19. A. Gal, S. Kerr, and J. Mylopoulos, "Information services on the web: Building and maintaining domain models," International Journal of Cooperative Information Systems, vol. 8, no. 4, pp. 227–254, 1999.

    Google Scholar 

  20. J. Huang, J. Stankovic, D. Towsley, and K. Ramamritham, "Experimental evaluation of real-time transaction processing," in Proceedings of the 10th Real-Time Systems Symposium, Santa Monica, CA, December 1989.

  21. T. Johnson and D. Shasha, "2Q: Alowoverhead high performance buffer management replacement algorithm," in Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, Sept. 1994, pp. 439–450

  22. V. Kalogeraki, A. Delis, and D. Gunopulos, "Peer-to-peer architectures for scalable, efficient and reliable media services," in Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS'03), Nice, France, April 2003.

  23. V. Kalogeraki, P.M. Melliar-Smith, and L.E. Moser, "Dynamic migration algorithms for distributed object systems," in 21st IEEE International Conference on Distributed Computing Systems, Phoenix, AZ, April 2001.

  24. V. Kanitkar and A. Delis, "Acase for real-time client-server databases," in Proceedings of the 2nd International Workshop on Real-Time Databases, Burlington, VT, USA, Sept. 1997.

  25. V. Kanitkar and A. Delis, "Site selection for real-time client request handling," in Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, Austin, TX, USA, May/June 1999.

  26. B. Kao and H. Garcia-Molina, "Subtask deadline assignment for complex distributed soft real-time tasks," in Proceedings of the 14th IEEE International Conference on Distributed Computing Systems, Poznan, Poland, June 1994.

  27. A. Keller and J. Basu, "Apredicate-based caching scheme for client-server database architectures," The VLDB Journal, vol 5, no. 1, pp. 35–47, 1996.

    Google Scholar 

  28. C. Lamb, G. Landis, J. Orenstein, and D. Weinreb, "The objectStore database system," Communications of the ACM, vol. 34, no. 10, 1991.

  29. S. Lee, C. Yang, S. Tseng, and C. Tsai, "A cost-effective scheduling with load balancing for multiprocessor systems," in Proceedings of the Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, Beijing, China, May 2000.

  30. V. Lortz, K. Shin, and J. Kim, "MDARTS: A multiprocessor database architecture for hard real-time systems," IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 4, pp. 621–644, 2000.

    Google Scholar 

  31. S. Milliner, A. Bouguettaya, and M.P. Papazoglou, "A scalable architecture for autonomous feterogeneous Database Interactions," In Proceedings of 21th International Conference on Very Large Data Bases, Morgan Kaufmann: Zurich, Switzerland, September 1995.

    Google Scholar 

  32. M. Mutka and M. Livny, "The available capacity of a privately owned workstation Environment," Performance Evaluation, vol. 12, no. 4, pp. 269–284, 1991.

    Google Scholar 

  33. S. Nural, P. Koksal, F. Ozcan, and A. Dogac, "Query decomposition and processing in multidatabase systems," in Proceedings of the OODBMSSymposium of the European Joint Conference on Engineering Systems Design and Analysis, July 1996.

  34. E. Panagos, A. Biliris, H. Jagadish, and R. Rastogi, "client-based logging for high performance distributed architectures." in Proceedings of the 12th International Conference on Data Engineering, New Orleans, LA, USA, Feb.-March 1996, pp. 344–351.

  35. K. Ramamritham, "Allocation and scheduling of complex periodic tasks," in Proceedings of the 10th IEEE International Conference on Distributed Computing Systems, Paris, France, 1990.

  36. K. Ramamritham, "Real-time databases," Distributed and Parallel Databases, vol. 1, no. 2, pp. 199–226, 1993.

    Google Scholar 

  37. K. Ramamritham, "Where do deadlines come from and where do they Go?" International Journal of Database Management, vol. 7, no. 2, pp. 4–10, Spring 1996.

    Google Scholar 

  38. K. Ramamritham, J. Stankovic, and P. Shiah, "Efficient scheduling algorithms for real-time multiprocessor systems," IEEE Transactions on Parallel and Distributed Systems, vol. 1, no. 2, 1990.

  39. N. Roussopoulos and H. Kang, "Principles and techniques in the design of ADMS±," IEEE Computer, vol. 19, no. 2, pp. 19–25, 1986.

    Google Scholar 

  40. L. Rudolph, M. Slivkin-Allalouf, and E. Upfal, "A simple load balancing scheme for task allocation in parallel machines," in ACM Symposium on Parallel Algorithms and Architectures, July 1991.

  41. J. Santos, R. Muntz, and B. Ribeiro-Neto, "Comparing random data allocation and data stripping in multimedia servers," in Proceedings of ACM-SIGMETRICS Conference, Santa Clara, CA, June 2000.

  42. T. Sellis, "Intelligent caching and indexing techniques for relational database systems," Information Systems, vol. 13, no. 2, pp. 175–185, 1988.

    Google Scholar 

  43. T. Sellis, "Multiple-query optimization," ACM Transactions on Database Systems, vol. 13, no. 1, 1988.

  44. D. Shasha, F. Llirbat, E. Simon, and P. Valduriez, "Transaction chopping: Algorithms and performance studies," ACM Transactions on Database Systems, vol. 20, no. 3, pp. 325–363, 1995.

    Google Scholar 

  45. K. Shin and Y. Chang, "Load sharing in distributed real-time systems with state-change broadcasts," IEEE Transactions on Computers, vol. 38, no. 8, pp. 1124–1142, 1989.

    Google Scholar 

  46. K. Shin and C. Hou, "Analytical models of adaptive load sharing schemes in distributed real-time systems," IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 7, pp. 740–761, 1993.

    Google Scholar 

  47. K. Shin and C. Hou, "Design and evaluation of effective load sharing in distributed real-time systems," IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 7, pp. 704–719, 1994.

    Google Scholar 

  48. V. Shkapenyuk and T. Suel, "Design and implementation of a high-performance distributed web crawler," in IEEE International Conference on Data Engineering, San Jose, CA, 2002.

  49. J. Stankovic, K. Ramamritham, and S. Cheng, "Evaluation of a flexible task scheduling algorithm for distributed hard real-time systems," IEEE Transactions on Computers, vol. 34, no. 12, pp. 1130–1143, 1985.

    Google Scholar 

  50. M. Stonebraker, P. Aoki, W. Litwin, A. Pfeffer, A. Sah, J. Sidell, C. Staelin, and A. Yu, "Mariposa: Awide-area distributed database system," The VLDB Journal, vol. 5, no. 1, 1996.

  51. T. Suen and J. Wong, "Efficient task migration algorithm for distributed systems," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 4, pp. 488–499, 1992.

    Google Scholar 

  52. A. Thomasian, "Concurrency control: Methods, performance, and analysis," ACM Computing Surveys, vol. 30, no. 1, pp. 70–119, 1998.

    Google Scholar 

  53. O. Torbjornsen and S. Bratsberg, "Designing an ultra highly available DBMS," in Proceedings of ACM-SIGMOD Conference, Dallas, TX, May 2000.

  54. Y. Wang and L. Rowe, "Cache consistency and concurrency control in a client/cerver DBMS architecture," in Proceedings of the 1991 ACM SIGMOD Conference, Denver, CO, May 1991.

  55. K. Wilkinson and M. Neimat, "Maintaining consistency of client-cached data," in Proceedings of the 16th International Conference on Very Large Data Bases, Brisbane, Australia, August 1990, pp. 122–133.

  56. M. Xiong and K. Ramamritham, "Deriving deadlines and periods for real-time transactions," in Proceedings of the 20th Real-Time Systems Symposium, Phoenix, AZ, Dec. 1999.

  57. P. Yu, K. Wu, K. Lin, and S. Son, "On real-time databases: Concurrency control and scheduling," Proceedings of IEEE, Special Issue on Real-Time Systems, vol. 8, no. 1, 1994, pp. 140–157.

    Google Scholar 

  58. Y. Zhang, H. Kameda, and K. Shimizu, "Adaptive bidding load balancing algorithms in heterogeneous dis-tributed systems," in Proceedings of the Second International Workshop on Modeling, Analysis, and Simula-tion of Computer and Telecommunication Systems, 1994.

Download references

Author information

Authors and Affiliations

  1. Akamai Technologies Inc., 8 Cambridge Center, Cambridge, MA, 02139, USA

    Vinay Kanitkar

  2. Department of CIS, Polytechnic University, Brooklyn, NY, 11201, USA

    Alex Delis

Authors
  1. Vinay Kanitkar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alex Delis
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kanitkar, V., Delis, A. Efficient Processing of Client Transactions in Real-Time. Distributed and Parallel Databases 17, 39–74 (2005). https://doi.org/10.1023/B:DAPD.0000045367.53244.c1

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:DAPD.0000045367.53244.c1

Search

Navigation