Pick & Mix Isolation Levels: Mixed Serialization Graph Testing

Abstract

Concurrency control is an integral component in achieving high performance in many-core databases. Implementing serializable transaction processing efficiently is challenging. One approach, serialization graph testing (SGT) faithfully implements the conflict graph theorem by aborting only those transactions that would actually violate serializability (introduce a cycle), thus maintaining the required acyclic invariant. Alternative approaches, such as two-phase locking, disallow certain valid schedules to increase throughput, whereas SGT has the theoretically optimal property of accepting all and only conflict serializable schedules. Historically, SGT was deemed unviable in practice due to the high computational costs of maintaining an acyclic graph. Research has however overturned this historical view by utilising the increased computational power available due to modern hardware. Furthermore, a survey of 24 databases suggests that not all transactions demand conflict serializability but different transactions can perfectly settle for different, weaker isolation levels which typically require relatively lower overheads. Thus, in such a mixed environment, providing only the isolation level required of each transaction should, in theory, increase throughput and reduce aborts. The aim of this paper is to extend SGT for mixed environments subject to Adya’s mixing-correct theorem and demonstrate the resulting performance improvement. We augment the YCSB benchmark to generate transactions with different isolation requirements. For certain workloads, mixed serialization graph testing can achieve up to a 28% increase in throughput and a 19% decrease in aborts over SGT.