Fast Hybrid Transactional Index with Scalable Phantom Avoidance

Griffin is a hybrid transactional index structure that combines a hash table and B+-tree. The key benefit of Griffin is that it processes single-key operations fast using the hash table. For serializable transactions, Griffin avoids phantoms with precision locking, a technique that protects updates and predicate reads with a lock. Although Griffin performs well under infrequent updates, under update-heavy workloads, the lists of locks kept by precision locking significantly grow in size, causing severe performance degradation. We identify this is because locks are released by only one thread called sync manager, which is also responsible for the heavy task of synchronizing the hash table and B+-tree. As a result, sync manager often fails to release locks as fast as they are acquired, causing the lock lists to grow. We propose a new design for Griffin, Griffin-PPL (Parallel Precision Locking), which prevents the lock lists from growing. Griffin-PPL removes sync manager, the bottlenecking thread, and parallelizes the work of releasing locks and synchronization among all transaction worker threads. To allow for parallelization, we adopt a decentralized data structure for the lock lists. Our evaluation in a microbenchmark shows that under an update-heavy workload (50% inserts, 50% scans), Griffin-PPL exhibits a throughput 6.5x the conventional Griffin architecture, at 64 threads.