A formal approach to lock escalation

Since database management systems(DBMSs) have limited lock resources, transactions requesting locks beyond the limit must be aborted, degrading the performance abruptly. Lock escalation is considered a solution to this problem. However, existing lock escalation methods have been designed in an ad hoc manner. So, they do not provide a complete solution. In this paper, we propose a formal model of lock escalation. Using the model, we analyze the roles of lock escalation formally and solve the problems of the existing methods systematically. In particular, we introduce the concept of the unescalatable lock that cannot be escalated due to conflicts. We identify that the unescalatable lock is the major cause of exhausting lock resources. We then analyze the reasons why unescalatable locks are generated and propose a new lock escalation method, adaptive lock escalation, which controls lock escalation based on the number of unescalatable locks. Through extensive simulation, we show that adaptive lock escalation significantly outperforms existing methods reducing the number of aborts and the average response time and increasing the throughput to a great extent. Adaptive lock escalation drastically reduces (more than 10 fold) the number of lock resources required to maintain the same level of throughput and average response time. At the same time, the throughput and average response time when using adaptive lock escalation are rather insensitive to the number of lock resources. Existing methods rely on users to estimate this number accurately at system initialization time. Adaptive lock escalation greatly alleviates this burden.