TuskFlow: An Efficient Graph Database for Long-Running Transactions

Download PDF

Abstract

Mammoth transactions, which involve long-running operations that access many items, are common in graph workloads. Graph analytics tasks, including pattern matching and graph algorithms, can generate large read-write operations that impact signi!cant portions of data, which makes their execution challenging under strict isolation guarantees. Consequently, we face an apparent trade-off between ensuring high isolation and achieving high performance, forcing users to choose between the two. In this work, we present Tuskflow, an experimental graph database based on Neo4j, designed to e#ciently handle mammoth transactions on graphs (the technique is applicable to other models such as relational) while maintaining existing transactional semantics. Tuskflow employs a deterministic protocol that safely reorders regular transactions around mammoths within an epoch. Our protocol supports parallel mammoth execution inspired by graph-parallel algorithms. To minimize con$icts with regular transactions, Tuskflow introduces query- and workload-aware optimizations, including graph entity tagging and partitioning. Our experiments demonstrate that, unlike traditional protocols like two-phase locking or MVCC, Tuskflow avoids blocking write transactions and improves tail latency by up to 45X