استفاده از تاریخ اجرا در برنامه ریزی معاملات پایگاه داده زمان واقعی

Real-time database systems support data processing needs of real-time systems where transactions have time constraints. Here we consider repetitively executed transactions, and assume that execution histories are logged. A well-known priority assignment technique called earliest-deadline-first is biased towards short transactions in which short transactions have better chances of completing their executions within their deadlines. We introduce the notion of “fair scheduling” in which the goal is to have “similar” completion ratios for all transaction classes (short to long in sizes). We propose priority assignment techniques that overcome the biased scheduling and show that they work via extensive simulation experiments.

Real-time databases are databases with real-time properties. Real-time databases are first conceptualized to serve the data processing needs of real-time systems. Real-time systems are those used in digital control, manufacturing, telecommunications, signal processing, command and control systems [1], [2], [3] and [4]. In simple term, the distinguishing difference of these systems is that the tasks in these systems have to be completed on a timely-basis [5]. Since processes and transactions in real-time systems are time constrained, databases that serve these systems also need to consider the same time constraints. Typical database management systems are only concerned with the logical correctness of data; processing times of queries, execution times of transactions are not strictly controlled in traditional database systems as it is required in real-time systems. Therefore, the research in real-time database systems is initiated to address the time dimension of the data in real-time systems and the timely processing of tasks in database systems. Previous work in real-time database systems typically deals with the problem of maximizing the system throughput via priority-based scheduling methods, and/or admission and load control techniques. System throughput can, for example, be the number of database transactions that are completed within their given time constraints usually in the form of time deadlines. In real-time systems some tasks are executed repeatedly. Unlike a computer system, which is a general-purpose computing machine, a real-time system solves a specific problem. This could be, for example, controlling the breaking system automatically in an automobile when the car is running; or for example, collection of weather data from scattered nodes of a wireless sensor network. Therefore, most tasks in real-time systems are routine and executed repeatedly, but not necessarily periodically. Therefore, there is a need to address the issue of repeated execution of tasks, or as called in database terminology “transactions”, in real-time database systems. In this paper, we consider the processing of transactions that are executed repeatedly in real-time database systems. Transactions in database systems do not have predictable execution times like the tasks in real-time systems. Data in database systems are accessed by many transactions concurrently. To preserve database consistency and the correctness of transactions, database systems employ strict concurrency control techniques while processing transactions, such as the two-phase locking method. These concurrency control techniques put transactions into waiting mode during conflicting access to the data and this in the end makes the transaction execution prediction an impossible job. Therefore, estimation of transaction execution time is not a feasible approach in predictive scheduling of transactions in real-time database systems. Instead, we assume the use of “transaction execution histories” of repeated transactions towards enhancing the systems throughput. Previous work in real-time database systems research focused mainly on priority assignment techniques for optimized scheduling transactions. Most performance studies use earliest-deadline-first (EDF) policy for priority assignment [6]. EDF assigns a higher priority value to a transaction with an earlier deadline so that transactions with earlier deadlines have the advantage of accessing data first against transactions with later deadlines that are concurrently accessing the same data. The logic behind is that transactions with later deadlines have more time to process their work within their time deadlines, and by assigning higher priorities to transactions with earlier deadlines, overall system throughput (i.e., the number of transactions that meet their deadlines, or successful transactions) can be increased. Although EDF has been shown to improve the average success ratio of the system (fraction of transactions completing successfully within their deadline), it discriminates against longer transactions under overload conditions [7], [8] and [9]. We propose priority assignment techniques that consider the biased nature of EDF, and attempt to eliminate the discriminatory behavior by adjusting the priorities using transaction execution history information. Two basic pieces of data that are kept in transaction execution histories are the transaction completion ratio and the transaction completion time. The completion ratio of a transaction is the fraction of successfully completed executions out of all executions of the transaction. Priority assignment techniques based on completion ratios of transactions assign higher priorities to transactions with low completion ratios such that the completion ratios of such transactions can be improved in successive runs. We call this approach “fair scheduling” where the goal is to obtain “similar” completion ratios for repeatedly executed transactions. The other group of priority assignment techniques we propose utilize the completion time of a transaction. In this approach, the probability of completion for a transaction within a given time quota is estimated using the completion time history (mean and variance), and transactions with lower completion probabilities are assigned higher priority values to adjust the bias towards short transactions. Haritsa et al. points out the need for load control in RTDBMSs [7]. EDF policy, by assigning higher priority values to transactions with earlier deadlines, determines the execution order of transactions. However, in overload conditions, the performance of the system degrades due to assigning higher priorities to transactions that are close to missing their deadlines (and most likely they will not be able to complete on time) and these high-priority transactions waste system resources and cause the delay of other transactions that may otherwise be able to meet their deadlines. Accordingly, in this paper, we also propose admission and load control techniques for scheduling repeating transactions based on execution histories. Admission control algorithms that we propose are based on the “risk of overspending the time quota”. A dynamically adjusted system risk bound variable is used in deciding the admission of new transactions. Load control in this system is done by changing the system risk bound variable value depending on the system performance. To our knowledge, our work is the first comprehensive work on the utilization of execution histories of real-time transactions for priority assignment and load control in RTDBMSs. Research interest in real-time database systems has been slow recently. However, with the advances in Internet and distributed computing, timely processing of transactions is becoming an essential requirement in many application areas such as e-commerce, mobile computing, and online data processing systems. Therefore, a renewed interest in real-time (web-based) database systems research is expected. Techniques presented in this paper can be utilized in e-commerce and distributed Internet applications for better transaction processing performance. For example, applications in real-time stock market analysis and online trading can employ these methods to increase the response times as well as the reliability of estimations and approximate results. In the next section, we model the transaction processing environment we are dealing with. In Section 3, load and execution history-based priority assignment techniques we propose are presented. Section 4 deals with the admission and load control strategies for real-time transactions with execution histories. Evaluation of the developed techniques via simulation is presented in Section 5. Related work in real-time database systems is given in Section 6. Some application areas of our proposed techniques are discussed in Section 7, and we conclude in Section 8.

We have proposed a number of priority assignment techniques based on the execution histories of real-time transactions with a “fair scheduling” goal. Scheduling techniques, we developed are based on two categories: those utilizing the completion ratios of transactions, and those that are based on the completion probability estimation. We developed a detailed simulation system using a discrete-event simulation development kit called SimPack. Our simulation system operates as a complete real-time database system with major concurrency control techniques and by implementing transaction processing modules. We tested our proposed algorithms and techniques extensively in this system and presented comparative results with evaluations. Admission and load control algorithms we developed are also tested and the results are presented here. The contribution of this paper is as follows: we showed through experiments that earlier developed scheduling and priority assignment techniques are biased towards short transactions favorably; short transactions have better chances of completing their work on time (within their deadlines) under well-established priority assignment and scheduling techniques. When the transactions are repetitive and the transaction execution histories are logged, we showed that better priority assignment techniques and scheduling techniques can be developed to overcome the bias towards short transactions. One of the priority assignment techniques we proposed which is using past timely completion ratios of transactions, namely LCEDF, performs better than other techniques in terms of giving similar throughput values (completion ratios) for different transaction classes (in length). Admission and load control policies we proposed also improves the throughput considerably (up to 10% higher success ratios) under overload conditions in conjunction with the proposed priority assignment techniques. All of the techniques we developed can be employed in applications where there is need for real-time computation and real-time response. Internet applications in particular can benefit greatly. As a continuation of this work, we will develop a case study employing our techniques in a real distributed application that will be implemented using web services for interoperability. Recent developments in the Internet and distributed computing, and increased activitiy in e-commerce, mobile networks, and databases are destined to be showcase areas for real-time database researchers and practitioners [30] and [1]. This is due to the fact that all of these applications utilize databases in the back-end and timely processing is very essential for almost all applications when end users and interconnected systems are expecting results in “internet time”. We consequently expect a renewed interest in real-time databases research area.