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

In recent years, several incremental graph computing models (McSherry et al., 2013; Shi et al., 2016; Sengupta et al., 2016; Vora et al., 2017) are proposed, which work well on monotonic algorithms. Among them, KickStarter (Vora et al., 2017) and Differential Dataflow (Murray et al., 2013; McSherry et al., 2013) are state-of-the-art representatives. KickStarter proposes an incremental graph computing model for monotonic algorithms, while Differential Dataflow presents a generalized incremental model without graph-awareness. They effectively shorten the processing time of monotonic algorithms from a few seconds to milliseconds when updating a single edge on power-law graphs with billions of edges, such as social networks (Mislove et al., 2007), web graphs (Albert et al., 1999), and financial graphs (Qiu et al., 2018).

However, for graph analytics of Internet-scale, the performance of existing systems still have a large gap to fulfill the throughput requirement which would demand ingesting hundreds of thousands of updates every second. KickStarter and Differential Dataflow can handle only about one thousand updates per second if they analyze every time the graph changes (per-update analysis). They rely on batching to trade latency for higher throughput, benefiting from larger concurrency and lower overheads. Moreover, they provide a batch-update mode to further optimize throughput, which reduces the frequency of analyzing and produces only one aggregated final result for each batch.

Unfortunately, the high throughput of KickStarter and Differential Dataflow relies on large batches and amplifies latency, even if batch-update mode is enabled. We take Breadth-First Search (BFS) on Twitter-2010 (Leskovec and Krevl, 2014) as an example. To meet 20 ms latency requirement (real-time analysis (Qiu et al., 2018)), the throughput of these systems is only about 1K ops/s. To provide throughput of 100K ops/s, they need to batch more than 20K updates, and the average processing time grows to more than 150 ms. Therefore, existing streaming graph systems cannot simultaneously fulfill latency and throughput requirements by batching.

Meanwhile, batch-update mode processes a batch of updates as a whole, skipping intermediate states which are potentially useful in some scenarios such as financial fraud detection (Qiu et al., 2018) and transaction conformity (Barga et al., 2007; Meehan et al., 2015).

Compared to batching, per-update analysis is friendly to latency, produces up-to-date results, and provides the most accurate and detailed information. It only leaves one open question: how to provide high throughput in per-update analysis.

A per-update system faces challenges of combining two kinds of workloads in a fine-grained manner for each update, which include modifying the graph structure and incrementally analyzing based on the updated graph. Different from batch-update systems (Cheng et al., 2012; Sengupta et al., 2016; Vora et al., 2017; Sheng et al., 2018; Mariappan and Vora, 2019), per-update analysis does not ingest multiple updates as a whole or analyzes them together. Therefore, per-update systems cannot reuse existing techniques designed for batching or benefit from batched updates, such as amortizing overheads across multiple updates.

The goal of high throughput and low latency requires the system to efficiently conduct both kinds of workloads. When modifying the graph, it needs to apply each update to a data structure and provide an updated graph ready for analysis in a short time. To enable real-time analysis for each update, the system requires a graph-aware design that leverages the locality of individual updates, rather than that utilizes the typical technique of entire graph scanning. Besides, it requires a new mechanism to enable parallelism for per-update processing, which is also important to achieve high throughput without batching.

We propose two guiding ideas to address the challenge, localized data access and inter-update parallelism.

The idea of localized data access comes from the observation that commonly used graph-aware techniques for graph streaming systems still require unnecessary entire graph scans (Sengupta et al., 2016; Vora et al., 2017; Kumar and Huang, 2019; Mariappan and Vora, 2019). If we can avoid these scans by only accessing the necessary vertices affected by updates, we will gain much better performance, thus we propose to use data structures called Indexed Adjacency Lists and sparse arrays to enable localized accesses.

We further improve throughput by processing updates in parallel (inter-update parallelism) while maintaining the per-update semantics to applications. We propose an algorithm to identify updates that can be safely executed in parallel and execute the rest of updates one by one to keep low latency, as well as atomicity, isolation, and correctness of per-update analysis.

We summarize our contributions as follows.

• •

  We propose a data structure for graphs named Indexed Adjacency Lists, which provides efficient analytical performance and supports microsecond-level updates. It consists of a dynamic array of arrays and indexes of edges, to store edges in a continuous memory layout and also ensure average O(1) time complexity for each update (Section 3.1).

• •

  During incremental computing, we track active vertices and updated results with sparse arrays to eliminate redundant overheads of scanning all the vertices and achieve localized data access. For better analytical performance, we further propose Hybrid Parallel Mode, which adaptively uses edge-parallel and vertex-parallel strategies through a linear classifier (Section 3.2).

• •

  We propose a domain-specific concurrency control mechanism to support parallelism among multiple updates with low overheads, thus improve throughput. It leverages the incremental model and intermediate data structures to identify non-conflicting updates before processing them (Section 4).

Based on the above core ideas, we design and implement a real-time graph streaming system for monotonic algorithms called RisGraph. For graphs with hundreds of millions of vertices and billions of edges, RisGraph can ingest millions of updates per second on a single commodity machine for monotonic algorithms like Breadth-First Search (BFS), Single Source Shortest Path (SSSP), Single Source Widest Path (SSWP) and Weakly Connected Component (WCC). Meanwhile, RisGraph ensures that more than 99.9% updates can be processed within 20 milliseconds without breaking per-update analysis semantics. It provides 2-4 orders of magnitude improvement over existing solutions for per-update analysis. Besides, it performs better than KickStarter and Differential Dataflow in batch-update scenarios with up to 20M updates per batch.

RisGraph focuses on monotonic algorithms. Monotonic algorithms employ intermediate values to monotonically approximate and finally reach accurate results from initial values. After applying edge insertions, computing can start from current results instead of initial values. These results are valid intermediate values and save computation by giving a closer approximation. KickStarter (Vora et al., 2017) further discovers that all known monotonic graph algorithms, such as Reachability, Shortest Path, Weakly Connected Components, Widest Path, and Min/Max Label Propagation, can be incrementally computed by maintaining a dependency tree (or forest). The dependency tree shows a vertex’s result depends on its parent and the edge between them. Deleting an edge on the dependency tree will invalidate the subtree rooted at the destination. Trimmed approximation technique proposed by KickStarter can generate valid approximations for invalidated vertices.

RisGraph adopts the dependency tree model and the trimmed approximation technique. Similar to KickStarter, RisGraph provides user-friendly API to describe monotonic algorithms as shown in the upper part of Table 1. init_val defines initial values for each vertex. gen_next uses an edge and its source vertex to generate a next possible value for its destination vertex. need_upd decides whether a vertex’s value should be updated. Table 2 shows implementation of Breadth-First Search, Single Source Shortest Path, Single Source Widest Path and Weakly Connected Component.

RisGraph supports vertex/edge insertions and deletions, with guarantees of correctness, atomicity, isolation and per-update analysis semantics. For each operation, RisGraph responds with a view of the results afterwards. Result views are versioned snapshots maintained by RisGraph, to enable consistent read operations on different vertices. Optionally, RisGraph provides durability with write-ahead logs (WAL) and also sequential consistency for better user-friendliness. Besides single edge/vertex updates, RisGraph can also handle transactions (see Section  4).

The lower part of Table 1 lists RisGraph’s Interactive API. Users call ins / del_edge and ins / del_vertex to send updates to RisGraph. txn_updates is the API to describe a transaction or an atomic batch of updates, which is a contiguous sub-sequence of a stream that must be treated as an indivisible unit (Meehan et al., 2015). After RisGraph processes an update or a transaction, it will return a version ID of the result snapshot. Users can get consistent results and dependency trees according to the version ID and vertex ID by get_value and get_parent. RisGraph supports querying the current version (get_current_version) and vertices that have been modified in any specific version (get_modified_vertices). RisGraph holds historical snapshots for each session, and requires users to actively report the latest unused versions for garbage collections (GC). release_history marks previous snapshots before its version ID as no longer used for its session.

Figure 2 shows an example of detecting suspicious users by Shortest Path algorithm. Two interactive API calls generate three result versions. At the bottom, Algorithm API calls incrementally maintain the shortest path to Vertices 4 and 5. The example also shows that detailed information provided by per-update analysis is important. It is able to find Vertex 4 suspicious when an edge is inserted in Version 1 under per-update analysis. However, it would miss the detection with batch-update mode if the system skips Version 1 and only checks Version 2.

According to the incremental computing model, the results of all vertices only depend on the edges on the dependency tree. Since each vertex has at most one parent in the dependency tree, there are at most $\left|V\right|$ (number of vertices) edges on the tree, rather than $\left|E\right|$ (total edges in the graph). The other edges are irrelevant to the results, therefore, the modification of these edges will not change any result.

This fact inspires us and leads to a natural question, how much the updates will change the results. We analyze four algorithms (BFS, SSSP, SSWP and WCC) on ten graphs listed in Table 4. We also vary the number of initially loaded edges ($\left|E\right|$), including 10%, 50% and 90% of edges, to show the effect of the average degree ($\left|E\right|\mathbin{/}\left|V\right|$). The method of generating updates and varying degrees is the same as the evaluation in Section 6. Table 4 also enumerates the roots selection and the percentage of visited vertices from the root for BFS, SSSP and SSWP with 90% edges.

We find that only a small part of updates change the results for most cases, as shown in Table 4. The proportion of updates which modify the results is less than 20% in 115 combinations of algorithms and datasets (120 experiments in total). In 100/120 experiments, the proportion is less than 10%. 77/120 experiments show that less than 5% updates modify results.

The observation guides us to propose a domain specific concurrency control mechanism for monotonic algorithms to avoid tracing memory accesses. We name the updates which do not change any results as safe updates. Correspondingly, unsafe updates modify results or the dependency tree. If we identify safe updates and only process them in parallel, not only can we preserve the correctness of per-update analysis, but also improve the throughput.

Figure 8 shows an example of safe updates and unsafe updates. Dark red arc arrows in the figure represent the dependency tree of the selected monotonic algorithm. Formally, given a directed graph $G=(V,E)$ and the current dependency tree $T=(V_{T},E_{T})$, an update to the graph is considered safe if and only if it fits in the following categories:

All other types of updates are unsafe. In summary, the classification only depends on updating edges, sources and destinations. The classification of updates is light-weight in RisGraph because it does not require any scanning.

Then we design an epoch loop schema, which takes advantage of the parallelism brought by classification to improve throughput and ensure correctness. In each epoch, RisGraph processes all safe updates in parallel first and then handles all unsafe updates one by one. Figure 9 shows RisGraph’s epoch loop schema when processing updates from multiple sessions. There are six updates from three asynchronous sessions in the figure. RisGraph classifies the updates into safe (S), unsafe (U), and next-epoch (N). After an unsafe update, all updates in the same session are next-epoch updates, which means they should be re-classified in the next epoch because any unsafe operation could modify the results and change classifications of updates behind it. RisGraph processes multiple safe updates in parallel, exploiting inter-update parallelism. In contrast, RisGraph handles unsafe updates one by one and performs parallel incremental computing (intra-update parallelism) for each update.

For better user-friendliness, RisGraph guarantees updates from a session will be executed by the same order of the updates and provides sequential consistency. However, it may lead to starvation. If some sessions keep producing safe updates, RisGraph will make unsafe updates starved. In order to solve the starvation and also provide predictable processing time, we design a scheduler for RisGraph. RisGraph’s scheduler controls the size of each epoch, and try to satisfy the user’s desired tail latency (processing-time latency (Karimov et al., 2018)) as much as possible, which is discussed in Section 5.

In our experiments (Section 6.2), RisGraph’s throughput is 14.1$\times$ better than the throughput without the inter-update parallelism, while the 99.9th percentile (P999) latency is under 20 ms. The results show that the epoch loop schema, inter-update parallelism, and scheduler can effectively optimize RisGraph’s throughput.

We have shown that RisGraph can support the situation where all updates are single vertex or edge updates, and only one algorithm is online in the system at a time. Sometimes, users also expect the support of transactions or atomic batches containing multiple updates and also running multiple algorithms at the same time. To support write transactions, we classify and process updates of a transaction as a whole. A write-only transaction is safe only when all of its write operations are safe, such as a transaction consisting of inserting a vertex $v_{4}$ and deleting the edge $\langle v_{2},v_{3}\rangle$ in Figure 8. As for read-write transactions, although they are not typical for streaming systems, RisGraph can still support them by treating them as unsafe transactions and processing them individually by blocking other sessions (just long-term unsafe updates in the epoch loops).

Similar to write-only transactions, when maintaining multiple algorithms simultaneously, an update is safe only when it is safe for every algorithm. The proportion of safe updates would decrease with larger transactions or more algorithms, which reduces the throughput brought from the inter-update parallelism. Compared with updates without being packed into transactions, RisGraph’s throughput reduces by 51.1% on average when the size of each transaction is 16. In any case, even if all transactions or updates are unsafe, localized data access can still provide thousands of times throughput of existing systems.

RisGraph proposes Indexed Adjacency Lists. Each vertex maintains its outgoing edges in an dynamic array (doubling capacity when full). Adjacency lists store directed edges, consist of the destination vertex IDs, the weight of each edge and the number of duplicated edges (the destination and the weight are both the same). RisGraph also stores a transpose graph required by the incremental model. Each vertex, whose degree is greater than a threshold, also contains an index, which represents the location of the edge in the list. The key of an edge is a pair of its destination vertex ID and its weight. The threshold provides a trade-off between memory consumption and lookup performance. We search it in the power of two to maximize performance divided by the square root of the memory usage (more performance-oriented). In our implementations, the threshold is 512. Users can search a better threshold based on their data, hardware, and requirements.

When inserting an edge, RisGraph first checks whether the edge exists in adjacency lists from edge indexes. If the edge exists, RisGraph only modifies the number of duplicated edges; otherwise RisGraph appends the new edge to the adjacency list and updates the index. For deleting an edge, RisGraph modifies the number of edges after searching from indexes. RisGraph keeps tomb (deleted) edges first, and recycle them and their indexes when doubling the adjacency list. RisGraph recycles the vertex IDs of deleted vertices into a pool. When inserting vertex, RisGraph either uses an ID from the recycling pool or assigns a new vertex ID.

RisGraph uses Hash Table¹¹1Implemented by Google Dense Hashmap (https://bit.ly/3rWs6yr) and MurmurHash3 as the default indexes to obtain the average $\text{O}(1)$ time complexity of insertions and deletions. There are also many alternative data structures that can replace Hash Table for indexes, such as BTree and ARTree (Leis et al., 2013) (the adaptive radix tree). According to the theoretical complexity and our experiments, the performance of Hash Table is the best in general. To maximize performance, we choose Hash Table by default although it is non-optimal in memory consumption. RisGraph can also utilize other data structures for indexes if the memory capacity is a constraint.

RisGraph stores dependency trees by parent pointer trees (Wikipedia contributors, 2019). Similar to KickStarter, each vertex maintains at most one bottom-up pointer to its parent on the dependency tree. It is efficient to classify updates by checking whether the updating edge is a bottom-up pointer on the dependency tree with parent pointer trees. During computing, modifications on parent pointer trees are also more lightweight than top-down pointer trees. With top-down pointers, updating the value of a vertex requires locking three vertices. On the contrary, parent pointer trees lock or atomically update the modified vertex only once.

The history store consists of a doubly-linked list from new versions to old versions for each vertex, and sparse arrays for each version to trace modifications of the results. Linked lists are similar to version chaining in multi-versioned databases, which are generally efficient in practice (Wu et al., 2017).

The history store only maintains short-term historical information, to provide consistent snapshots of the results. Every second, RisGraph chooses the latest useless version among versions released by every session, marks the version and the previous versions as garbage, and then aggressively recycles them from sparse arrays. For linked lists, RisGraph performs lazy garbage collection, which means RisGraph only recycles garbage from the tail of a vertex’s linked list when a new version updates this vertex.

RisGraph chooses sparse arrays to store active vertices and converts them to bitmaps only when performing pull operations (checking all incoming edges for each vertex). We create a separate sparse array for each thread, which helps eliminating the overhead of synchronization and contention among multiple threads.

For push operations, we propose a hybrid mode supported by a linear regression based classifier to adaptively choose the proper edge-parallel or vertex-parallel mode. In our implementation, we train the classifier based on UK-2007 dataset, and it works well on other graphs. In our evaluation, the hybrid mode reduces RisGraph’s computing time by 24.2% compared to vertex-parallel only mode, showing the effectiveness of the classifier. Users can also train the classifier by their datasets and algorithms. Online training would bring additional overhead, so we choose to fix the parameters first and leave online training as our future work.

The purpose of the scheduler in RisGraph is to avoid starvation and also to achieve the highest possible throughput automatically under an expected tail latency. Avoidance of starvation has been discussed in Section 4, so we focus on how the scheduler improves throughput while maintaining the latency demand.

The scheduler would first try to pack as many safe updates in an epoch-loop as possible to maximize throughput. It may break the latency constraint without a latency control, so the scheduler uses two heuristics to abort parallel execution of safe updates and turns to process unsafe updates. One is when the waiting time of the earliest unsafe update in the queue almost exceeds the target latency. In our implementation, we set the target latency to 0.8 times the user-specified latency limitation. Another one is when the number of unprocessed unsafe updates reached a dynamic threshold. RisGraph adjusts the threshold based on historical information. If the proportion of qualified updates (under the latency limitation) is higher than the target after the last adjustment, the scheduler will slowly increase the threshold. Otherwise, if the proportion is lower than the goal, the scheduler will quickly decrease the threshold. In our implementation, the initial threshold is the number of physical threads, and RisGraph adjusts the threshold every three epoch-loops. RisGraph increases the threshold by 1% each time, and when decreasing, adjusts the threshold by 10%. Since the scheduler is self-adjusting, it can support various algorithms and datasets.

In our experiments, the scheduler can meet the latency requirement, and get a good trade-off between latency and throughput.

In our evaluation, RisGraph can ingest up to millions of updates per second and provide per-update incremental analysis, thanks to localized data access and inter-update parallelism. Its performance surprises us and prompts us to study how each update modifies the results. We use affected area (Fan et al., 2011; Fan et al., 2017) (AFF) as a tool to model computing costs. The affected area is the area modified or inspected (accessed) by an update.

Incremental computing assumes that the affected area of each update is relatively small compared to the entire graph. Several incremental graph computing models (McSherry et al., 2013; Shi et al., 2016; Sengupta et al., 2016; Vora et al., 2017) can accelerate monotonic algorithms in practical, but they still lack sufficient discussion and analysis of affected areas.

We try to give some mathematical bounds of affected areas. Because of the variety of graphs, updates, and algorithms, to mathematically bound affected areas for general monotonic algorithms is challenging. We only find a preliminary, yet optimistic bound based on an assumption. We assume that updating edges are uniformly sampled from all edges in the graph.

Consider a directed graph $G=(V,E)$ and a rooted tree in the graph $T=(r,V_{T},E_{T}),r\in V_{T}\subset V,E_{T}\subset E$, in which edges point from parents to children. The rooted tree represents the dependency tree of monotonic algorithms. For any vertex $i\in V$, we define $T_{i}=(V_{i},E_{i})$, where $(V_{i},E_{i})$ is the subtree of $T$ rooted at $i$ if $i\in V_{T}$, and $(\varnothing,\varnothing)$ otherwise. The size of $T_{i}$ is denoted by $|T_{i}|=|V_{i}|$, satisfying $0\leq|T_{i}|\leq|V_{T}|\leq|V|$.

For any directed edge $e=(i,j)$ in $G$, let $\text{AFFV}_{e}=\vmathbb{1}_{e\in E_{T}}|T_{j}|$ and $\text{AFFE}_{e}=\vmathbb{1}_{e\in E_{T}}\sum_{k\in V_{j}}d_{k}$ ($d_{k}$ is the total degree of $k$ in $G$, and $\vmathbb{1}$ is the indicator function), respectively representing the upper bound of vertices that need to be modified after $e$ is inserted or removed, and edges related to these vertices. $\text{AFFV}_{e}$ bounds the area modified by $e$, and $\text{AFFE}_{e}$ bounds the area inspected by $e$.

When $e$ is sampled uniformly from the edge set $E$, the mean AFFV can be written as:

where $\operatorname{\mathrm{dep}}_{v}$ is the depth of $v$ in $T$ (the distance between $v$ and $r$), $D_{T}$ is the diameter (the length of the longest path) of $T$, and $\overline{d}\geq 1$ is the mean degree of $G$. So that $\overline{\mathrm{AFFV}}$ could be bounded by $D_{T}/\overline{d}$. In power-law graphs, $D_{T}$ is often small (Milgram, 1967; Cohen and Havlin, 2003; Leskovec et al., 2005; Leskovec et al., 2010). And in evolving graphs, $D_{T}$ will decrease while $\overline{d}$ will increase over time, according to Densification Laws and Shrinking Diameters (Leskovec et al., 2005).

Similarly, the mean AFFE can be calculated as:

which can also be bounded by $D_{T}$.

The results above guarantee mathematically that if we choose edges randomly for each update, only few vertices will be modified in average, and few vertices and edges will be accessed to perform the post-update analysis, thus showing the efficiency of incremental monotonic algorithms on power-law graphs.

Existing hierarchical algorithms (Sanders and Schultes, 2005; Nannicini and Liberti, [n.d.]; Wang et al., 2019) can efficiently limit the computing into a small neighbouring area for non-power-law graphs such as roadmaps. However, they cannot deal with power-law graphs efficiently because of hubs in power-law graphs. RisGraph focus on taking one step forward to support power-law graphs efficiently based on incremental computing. Meanwhile, RisGraph can also handle per-update incremental analysis on non-power-law graphs.

We evaluate RisGraph with the USA road network (Rossi and Ahmed, 2015), which is a non-power-law roadmap. There are 23.9M vertices and 28.9M edges in the USA dataset, and the experimental setup is the same as Section 6.1. The throughput is 26.7K ops/s for BFS, 4.10K ops/s for SSSP, 154K ops/s for SSWP, and 10.4K ops/s for WCC.

A large number of systems (Low et al., 2010; Gonzalez et al., 2012; Kyrola et al., 2012; Shun and Blelloch, 2013; Gonzalez et al., 2014; Zhu et al., 2015; Zhu et al., 2016; Ai et al., 2017; Maass et al., 2017; Wang et al., 2017; Shi et al., 2018; ZhangYunming et al., 2018; Mukkara et al., 2018; Lin et al., 2018; Chen et al., 2019; Vora, 2019) focus on graph computing with static graphs. These systems are designed for efficient graph analytics on entire graphs, but they suffer from ETL overheads with evolving graphs.

Graph databases (neo, [n.d.]; tit, [n.d.]; ori, [n.d.]; ara, [n.d.]; Bronson et al., 2013; Sun et al., 2015; Gurajada et al., 2014; Dubey et al., 2016; Carter et al., 2019) mainly target transactional workloads, which rarely query and modify a large number of vertices or edges. Some recent work (Jindal et al., 2015; Kimura et al., 2017; Fan et al., 2015; Zhao and Yu, 2017; Zhu et al., 2020) propose to optimize analytical workloads in graph databases as well. Several graph computing engines (Prabhakaran et al., 2012; Han et al., 2014; Miao et al., 2015; Macko et al., 2015; Iyer et al., 2016; Vora et al., 2016; Then et al., 2017; Kumar and Huang, 2019) are also designed to support evolving graphs. These systems can handle graph update workloads. However, they are limited by recomputing on entire graphs for analytical workloads due to lack of incremental computing.

Several generalized streaming systems, such as Storm (noa, [n.d.]a) and Flink (Katsifodimos and Schelter, 2016), allow users to incrementally process unbounded streams. Spark Streaming (Zaharia et al., 2013) utilizes small batches to handle streaming data and provide second-scale latency. It is not easy for users to develop incremental iterative graph algorithms based on these systems, such as monotonic algorithms. Differential Dataflow (McSherry et al., 2013), together with Naiad (Murray et al., 2013), carries out a generalized computational model that supports executing iterative and incremental computations with low latency. However, general-purpose systems lose opportunities to specialize and optimize for graph workloads.

Kineograph (Cheng et al., 2012) and GraphInc (Cai et al., 2012) are systems that enable incremental computation for graph mining. Qiu et al. (Qiu et al., 2018) design a real-time streaming system called GraphS for cycle detection. These systems lack support for monotonic algorithms like shortest path. Tornado (Shi et al., 2016) processes user queries by branching the execution and computing results incrementally while ingesting graph structure updates. However, it might lead to incorrect results in the presence of edge deletions when maintaining some monotonic algorithms such as WCC and SSWP (Vora et al., 2017).

KickStarter (Vora et al., 2017) provides correct incremental computation for monotonic algorithms by tracing dependencies and trimmed approximations. GraPU (Sheng et al., 2018) accelerates batch-update monotonic algorithms by components-based classification and in-buffer precomputation. GraphIn (Sengupta et al., 2016) incorporates an I-GAS model that processes fixed-size batches of updates incrementally. GraphBolt (Mariappan and Vora, 2019) proposes a generalized incremental model to handle non-monotonic algorithms like Belief Propagation, but involves more overheads than KickStarter for monotonic algorithms. These systems support monotonic algorithms, but all of them are designed for batch-update analysis. RisGraph targets per-update analysis to provide milliseconds tail-latency and detailed information in comparison.