RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s

Evolving graphs in the real world are large-scale and constantly changing as hundreds of thousands of updates may come every second. Monotonic algorithms such as Reachability and Shortest Path are widely used in real-time analytics to gain both static and temporal insights and can be accelerated by incremental computing.Existing streaming systems, such as Differential Dataflow and KickStarter, adopt with the incremental computing model and reach either low latency or high throughput, but unfortunately not both. Particularly, their throughput is only about one thousand updates per second for per-update analysis without mini-batch.We argue that per-update analysis provides the most accurate analysis result and is friendly to latency, so it deserves a better solution with specialized designs. Different from typical entire graph analysis or batch-update incremental analysis, per-update analysis requires both efficient updating and analyzing for each update.This paper presents RisGraph, a real-time streaming system that provides real-time per-update analysis with high throughput. RisGraph addresses the challenge by localized data access and inter-update parallelism. We propose a data structure named Indexed Adjacency Lists, and use sparse arrays and Hybrid Parallel Mode to enable localized data access. To achieve inter-update parallelism, we propose a domain-specific concurrency control mechanism based on the classification of safe updates and unsafe updates.Experiments show RisGraph can ingest millions of updates per second, for graphs with several hundred millions of vertices and billions of edges, and the P999 processing-time latency is within 20 milliseconds. RisGraph achieves orders-of-magnitude improvement on throughput with per-update analysis and also performs better than existing systems with batches of up to 20M updates.