Graph Database Integrity: Bridging the ACID Gap in LDBC Benchmarking

TL;DR

Performance benchmarks are often a "race to the bottom" where systems sacrifice correctness for speed. This paper introduces a specialized ACID compliance test suite for the LDBC Social Network Benchmark (SNB-I). By utilizing implementation-agnostic client-side checks, the authors provide a way to verify if a graph database actually delivers the isolation and atomicity it promises—preventing "apples-to-oranges" comparisons where a fast but "broken" system appears superior to a robust one.

Problem & Motivation: The Illusion of Safety

In the database world, the ACID properties (Atomicity, Consistency, Isolation, Durability) are the bedrock of trust. However, verifying these properties in graph databases is notoriously difficult because:

1. Model Mismatch: Existing tests (like TPC-C) assume relational tables and SQL, whereas graph databases deal with nodes, edges, and properties.
2. API Limitations: Modern systems often use stored procedures or restricted query languages (Cypher, Gremlin) rather than interactive lock-based sessions.
3. Hidden Trade-offs: Many vendors claim "Snapshot Isolation" or "Serializability," but under high contention, these guarantees often crumble.

Without a standardized test suite, a database could "cheat" in a benchmark by disabling expensive isolation checks to achieve higher throughput, leading to unfair comparisons.

Methodology: Implementation-Agnostic Verification

The core innovation lies in designing tests that don't care how the database works internally. Instead, they observe the history of versions from the client's perspective.

1. Atomicity Testing

The suite checks if transactions are truly all-or-nothing. For instance, Atomicity-RB (Rollback) attempts a transaction that updates a node and then intentionally triggers a constraint violation (like a duplicate ID). The test then verifies that none of the partial updates are visible in the graph.

2. Isolation Testing: Detecting the "Vanishing" Transaction

The authors focus heavily on 10 isolation anomalies. One of the most sophisticated is Observed Transaction Vanishes (OTV).

• The Intuition: If a reader sees part of a transaction's update (e.g., node A updated), it should never "lose" that information in a subsequent read within the same transaction.
• The Implementation: They use a 4-node cycle structure. A writer updates all nodes in the cycle. If a reader sees a new version of node A but then reads an old version of node B later, the transaction has "vanished," indicating a failure in atomic visibility.

Figure 1: The core LDBC SNB schema used for testing, extended with versioning properties.

Experiments: Real-World System Performance

The authors stress-tested Neo4j, Memgraph, Dgraph, JanusGraph, and PostgreSQL. The results were revealing:

• Neo4j (3.5 & 4.1): Marketed as "Read Committed," but actually passed tests for stronger isolation levels (Monotonic Atomic View). However, Neo4j 4.1 failed the Lost Update (LU) test, showing a regression or a nuance in its new architecture.
• Dgraph & Memgraph: Successfully maintained their "Snapshot Isolation" claims across most tests.
• JanusGraph: Struggled significantly. When backed by Cassandra, it failed multiple isolation checks due to "stale reads," proving that it is not yet suitable for high-integrity transactional workloads.

Table 1: Comparison of database systems across 10 isolation anomalies (G0 to WS).

Depth Analysis & Conclusion

This paper shifts the focus of database benchmarking from pure speed to safety-adjusted performance.

Takeaways:

• The "Half-Circle" Warning: In the results table, the "½" symbol indicates that an anomaly was not strictly observed but the system's architecture (like lock-based blocking) might prevent the test from running concurrently enough to trigger it.
• Implementation Matters: The fact that PostgreSQL (a mature RDBMS) experienced 60% abort rates during Lost Update tests compared to graph-native systems highlights the different cost-benefit profiles of lock-based vs. multi-version concurrency control (MVCC).

Limitations:

The tests are currently "lightweight" to minimize benchmark overhead. While they catch common failures, they might miss rare race conditions that only appear under extreme distributed stress. Future work involving distributed consistency (handling network partitions and clock skew) will be the next frontier for this test suite.

Final Thought: If you are choosing a graph database for financial or mission-critical data, throughput is a secondary metric; the ability to pass this ACID suite is the primary requirement.