The rapid growth of real-time analytics—ranging from fraud detection to social media monitoring—has spurred the development of specialized Dynamic Graph Storage (DGS) engines. These systems are designed to handle high-frequency updates while simultaneously supporting complex analytical queries. However, the research landscape has become fragmented, with various systems prioritizing different trade-offs without a common basis for comparison.
This paper provides a critical "reality check" for DGS designs. By stripping away implementation-specific optimizations and evaluating core techniques on a level playing field, the authors reveal significant overheads in modern transactional approaches.
The Fragmented Landscape of Dynamic Graph Storage
Existing DGS systems often target specific performance goals. For instance, systems like Aspen focus on fast edge insertions, while LiveGraph and Teseo prioritize transactional consistency through Multi-Version Concurrency Control (MVCC). Until now, benchmarking these systems was difficult because they were often treated as "black boxes."
It was previously unclear whether performance gains stemmed from superior data structures or more efficient low-level locking strategies. This study aims to isolate these factors to understand the true cost of dynamic graph management.
A Unified Framework for Evaluation
To systematically evaluate DGS designs, the researchers developed a DGS Sandbox. This framework re-implements the core techniques of five major systems (LiveGraph, Sortledton, Teseo, Aspen, and LLAMA) within a unified 7,800-line C++ codebase. The framework relies on a two-level abstraction:
- Global Abstraction: Manages timestamps, serializability, and transaction orchestration.
- Local Abstraction: Handles the physical layout of vertex and neighbor tables.
This decomposition allows for isolating specific variables, such as the choice of neighbor index or the concurrency control protocol, while maintaining a consistent environment for hardware-level profiling using CPU counters.
Key Insights: The Cost of Flexibility
The study's findings highlight several critical trade-offs that often go unnoticed in high-level algorithmic analysis:
- The "Fine-Grained" Tax: Many modern systems use per-edge MVCC to ensure consistency. However, the overhead of checking version metadata for every neighbor during a scan leads to massive performance degradation—often up to 11x slower than static formats.
- Hardware Neglect: DGS designs optimized for Big-O complexity frequently ignore cache locality. Segmented structures (like skip lists) cause significantly more cache and DTLB misses than simple continuous arrays, leading to CPU pipeline stalls.
- The Batching Sweet Spot: While coarse-grained methods (like Aspen) are inefficient for single-edge updates due to snapshotting costs, they outperform fine-grained methods once batch sizes exceed 256 updates by avoiding heavy lock contention.
Performance and Memory Benchmarks
The evaluation across eight diverse real-world datasets revealed a staggering "CSR Gap." The Compressed Sparse Row (CSR) format remains the gold standard for static graph performance, and DGS systems struggle to close the distance:
- Memory Overhead: DGS methods consume 3.3x to 10.8x more memory than CSR, largely due to version chains and "empty slots" reserved for fast inserts.
- Query Throughput: Static CSR consistently outperforms the best dynamic systems by 2.4x to 11.0x.
- Scan Efficiency: Continuous storage layouts (e.g., LiveGraph) are significantly faster than segmented indexes (e.g., Teseo) because they leverage hardware prefetchers and SIMD vectorization.
Conclusion and Future Directions
The study serves as a roadmap for the next generation of graph systems. The authors suggest that the community should move away from per-edge versioning toward "medium-grained" approaches that group updates. Furthermore, there is a clear need for "hardware-aware" containers that balance update flexibility with the cache-friendly memory layouts of static formats. By focusing on the "mechanical sympathy" between software and modern CPU architectures, future DGS designs can bridge the performance gap with static storage.
Summary updated