Page MenuHomeSoftware Heritage

Reduce RAM usage in graph API endpoints
Closed, ResolvedPublic


In my latest benchmarks I noticed RAM usage being huge when calling endpoints methods. After some investigation this is because of Traversal inner big arrays visited and nodeParent that are used to keep track of information during traversals:

public class Traversal {
	  /** Graph used in the traversal */
	  Graph graph;
	  /** Boolean to specify the use of the transposed graph */
	  boolean useTransposed;
	  /** Graph edge restriction */
	  AllowedEdges edges;
	  /** Bit array storing if we have visited a node */
	  LongArrayBitVector visited;
	  /** LongBigArray storing parent node id for each nodes during a traversal */
	  long[][] nodeParent;
	  /** Number of edges accessed during traversal */
	  long nbEdgesAccessed;


These arrays are allocated every time we create a new Endpoint (for the benchmark this is at most 2 times, but the two arrays combined take up to ~100GB of RAM).

One solution would be to move the definitions up to the higher Graph class, which is only instantiated once. However this is problematic if we want to use multiple threads to query the graph.

Event Timeline

haltode triaged this task as High priority.Aug 14 2019, 9:26 PM
haltode created this task.
haltode created this object in space S1 Public.
haltode updated the task description. (Show Details)Aug 14 2019, 9:47 PM

Both big arrays are meant to be used with all the graph nodes, here is their RAM usage:

  • visited: this is a BitVector meaning we only store one bit per node so 1.5GB for 12B nodes
  • nodeParent: this is a long array (it supports 64-bit indexing with a custom LongBigArray class from WebGraph environment), so 96GB

From Javalin documentation [1]:

The app.start() method spawns a user thread, starts the server, and then returns.

While the default threadpool (200 threads) is enough for most use cases, sometimes slow operations should be run asynchronously.

Hence from my understanding of their documentation (which is not very exhaustive) the framework uses threads to answer queries.


haltode closed this task as Resolved.Aug 25 2019, 2:54 PM

This was fixed with in 87192dfddd4b by using a hash map. See T1969 for long term solution.