Shifting Transaction Isolation on Graphs: From Systems to Data

Processing long-running read-write transactions on graphs is an open challenge, primarily due to the need for serializability to maintain basic structural consistency of graphs. We identify that a fundamental impediment to a solution arises from the homogeneous database-wide notion of transaction isolation developed for relations, which fails to capture the heterogeneous consistency semantics on graphs. We propose Ddi, a notion of fine-grained isolation for graph transactions that advocates per-operation isolation allocation. It extracts concurrency for graph transactions that traditional isolation cannot, by assigning one or multiple isolation levels to each traversal operation, while maintaining graph consistency as serializability does. We develop formal semantics for Ddi and prove the consistency guarantees of its transaction schedules. We also develop DD-OCC, an optimistic concurrency control protocol for Ddi isolation, and implement it on a state-of-the-art graph storage. Experiments over LDBC graphs confirm the effectiveness of Ddi.