Terrace: Exploiting Graph Skewness for Blazing Fast Streaming Updates

TL;DR

Terrace is a new dynamic graph system that recognizes a simple truth: not all vertices are created equal. By using a three-level hierarchical storage engine—in-place slots for small vertices, a shared Packed Memory Array for medium ones, and B-trees for "superstars"—it achieves the update speed of streaming systems while matching the query performance of static, optimized frameworks like Ligra.

Problem & Motivation: The "One-Size-Fits-All" Tax

Most real-world graphs (social networks, web graphs) are highly skewed. As shown in the paper's characterization, over 60% of vertices in datasets like LiveJournal have fewer than 10 neighbors, while a few "hub" vertices might have millions.

The Problem:

• Static Systems (like Ligra) use CSR (Compressed Sparse Row). It's incredibly fast to read but requires a full graph rebuild for updates—useless for streaming.
• Dynamic Systems (like Aspen) use trees for everything. While great for updates, traversing a tree for a vertex with only 3 neighbors is "cache-locality suicide." You pay for pointer indirection and non-sequential memory access that you don't actually need.

Terrace’s Insight: Use different data structures for different degree regimes. Save the heavy-duty trees for the hubs, and keep the "small fry" in-place to maximize cache hits.

Methodology: The Hierarchical Triple-Threat

Terrace abandons the uniform approach in favor of a degree-dependent hierarchy:

1. In-Place Level (Degree $\le S$)

Instead of a pointer to a neighbor list, the first few neighbors (up to $S=13$) are stored directly inside the vertex structure.

• Why it works: When a graph traversal visits a low-degree vertex, the neighbors are already in the cache line loaded for the vertex metadata. Zero extra cache misses.

2. Array-Like Level (PMA) (Medium Degree)

For vertices that outgrow the in-place slots but aren't yet "hubs," Terrace uses a Packed Memory Array (PMA).

• Why it works: PMAs maintain sorted order with gaps, allowing for $O({\log }^{2}N)$ updates but offering the scan speed of a standard array. By sharing one PMA among many vertices, Terrace keeps medium-degree neighbors contiguous.

3. Tree-Like Level (B-tree) (High Degree)

For high-degree vertices, Terrace assigns a private B-tree.

• Why it works: At this scale, the cost of one pointer indirection is negligible compared to the cost of scanning thousands of edges. B-trees provide the best balance of search, update, and block-based scan performance.

The Figure above illustrates the three-level design: (left) metadata and in-place slots, (middle) the shared PMA for bulk storage, and (right) the dedicated B-trees.

Experiments: Performance Without Compromise

The authors compared Terrace against Aspen (streaming) and Ligra (static).

Update Throughput

Terrace shines in small-to-medium batch sizes (up to 1M edges), which is the "sweet spot" for most real-world applications like Twitter or Facebook transaction streams.

Query Latency

In algorithms like BFS and PageRank, Terrace significantly outperforms Aspen because it avoids the "pointer-chasing" tax. Remarkably, it even beats the static Ligra in several cases because the in-place optimization reduces the total number of cache misses.

Critical Analysis & Conclusion

Takeaway

Terrace proves that we don't have to choose between "fast updates" and "fast queries." By embracing the physical reality of hardware (cache lines) and the mathematical reality of graphs (skewness), we can build systems that adapt.

Limitations

• Memory Overhead: Terrace uses more memory than Aspen (up to 2x). This is primarily because the PMA and B-trees maintain "empty space" to ensure fast future insertions.
• Deletion Complexity: While insertions are highly optimized, batch deletions in Terrace are currently slower than Aspen, suggesting a need for better "re-balancing" logic between the levels.

Future Outlook

The move toward Hierarchical Graph Containers is likely the future of graph databases. As GNNs and real-time fraud detection become more prevalent, the ability to ingest data while maintaining high-speed traversal will be the primary bottleneck. Terrace provides the blueprint for solving it.