Performance analysis of a real-time database with optimistic concurrency control

For a real-time shared-memory database with Optimistic Concurrency Control (OCC), an approximation for the transaction response-time distribution and thus for the deadline miss probability is obtained. Transactions arrive at the database according to a Poisson process. There is a limited number of CPUs that can handle transactions in parallel. TransactIons have soft deadlines, and the probability of data conflicts is equal for all transactions. The response time of a transaction consists of possible waiting time (if at arrival all CPUs are occupied) plus a number of execution runs (due to the occurrence of conflicts). In this study, we analyze the case where the execution time of all transactions is constant. Although in practice execution times are never really constant, it is important to analyze this simplifying constant case first, before trying to analyze more general execution-time distributions. We model the real-time database (RTDB) with OCC by a multi-server queueing system with a very special kind of feedback. The probability that a transaction is fed back for a rerun depends on the number of transactions that has committed during its execution. Numerical experiments, which compare the approximative analysis with simulation, show that the analysis provides a good and very fast approximation for the response-time distribution and thus for the percentage of transactions that meets its deadline. We also discuss how the model and the analysis can be extended such that more realistic assumptions, e.g. non-uniform data access, several transaction types, and general execution-time distributions, can be handled.