Automating the detection of snapshot isolation anomalies

Abstract

Snapshot isolation (SI) provides significantly improved concurrency over 2PL, allowing reads to be non-blocking. Unfortunately, it can also lead to non-serializable executions in general. Despite this, it is widely used, supported in many commercial databases, and is in fact the highest available level of consistency in Oracle and Post-greSQL. Sufficient conditions for detecting whether SI anomalies could occur in a given set of transactions were presented recently, and extended to necessary conditions for transactions without predicate reads. In this paper we address several issues in extending the earlier theory to practical detection/correction of anomalies. We first show how to mechanically find a set of programs which is large enough so that we ensure that all executions will be free of SI anomalies, by modifying these programs appropriately. We then address the problem of false positives, i.e., transaction programs wrongly identified as possibly leading to anomalies, and present techniques that can significantly reduce such false positives. Unlike earlier work, our techniques are designed to be automated, rather than manually carried out. We describe a tool which we are developing to carry out this task. The tool operates on descriptions of the programs either taken from the application code itself, or taken from SQL query traces. It can be used with any database system. We have used our tool on two real world applications in production use at IIT Bombay, and detected several anomalies, some of which have caused real world problems. We believe such a tool will be invaluable for ensuring safe execution of the large number of applications which are already running under SI.