In-Memory Object Graph Stores

We will use mathematical induction to prove this theorem.

1. 1.

   Base Case (i = 0): Prior to capture, $o$ is present in the store, i.e., ${\sigma }_0(o)\ne \perp$. When a capture operation is executed, the state transitions as follows:

   $⟨\overline{o}.\text{capture}(o),{\sigma }_0,\mathrm{\Gamma }⟩\Downarrow ⟨\mathrm{\_},{\sigma }_1,\mathrm{\Gamma }⟩\text{where }{\sigma }_1={\sigma }_0\cup \{o\}\text{ by rule }\text{capture}$

   ${\sigma }_1$ denotes the updated state. We know that ${\sigma }_0\cup \{o\}={\sigma }_0$ since ${\sigma }_0(o)\ne \perp$. Therefore, ${\sigma }_1={\sigma }_0$ and the theorem holds for the base case.

2. 2.

   Inductive Step (i = n): Consider an ${(n-1)}^{th}$ transition:

   $⟨\overline{o}.\text{capture}(o),{\sigma }_{n-1},\mathrm{\Gamma }⟩\Downarrow ⟨\mathrm{\_},{\sigma }_n,\mathrm{\Gamma }⟩$

   Lets assume that the theorem holds for $i=(n-1)$ i.e., ${\sigma }_n={\sigma }_0$. Now for the $n^{th}$ transition, by the semantics defined in rule capture, ${\sigma }_{n+1}={\sigma }_n\cup \{o\}$. However, by our assumption of the theorem holding for $i=(n-1)$, ${\sigma }_{n+1}={\sigma }_0\cup \{o\}$. By base case, we know that ${\sigma }_0\cup \{o\}={\sigma }_0$. Therefore, we can claim by mathematical induction that ${\sigma }_{n+1}={\sigma }_0$ as required by the theorem.

$◀$

We will use structural induction on the defined semantic rules to prove this theorem.

1. 1.

   Base Case (i = 0): Prior to capture, $o$ is not present in the store, i.e., ${\sigma }_0(o)=\perp$. When a capture operation is executed, the state transitions as follows:

   $⟨\overline{o}.\text{capture}(o),{\sigma }_0,\mathrm{\Gamma }⟩\Downarrow ⟨\mathrm{\_},{\sigma }_1,\mathrm{\Gamma }⟩\text{where }{\sigma }_1={\sigma }_0\cup \{o\}\text{ by rule }\text{capture}$

   ${\sigma }_1$ denotes the updated state. Thus, immediately after execution, $o$ is present in the store or in other words ${\sigma }_1(o)\ne \perp$. Therefore, the theorem holds for the base case.

2. 2.

   Inductive Step (i = n): Consider an ${(n-1)}^{th}$ transition:

   $⟨S_{n-1},{\sigma }_{n-1},{\mathrm{\Gamma }}_{n-1}⟩\Downarrow ⟨S_{n-1}^{\prime },{\sigma }_n,{\mathrm{\Gamma }}_n⟩$

   Lets assume that the theorem holds for $i=(n-1)$ i.e., ${\sigma }_n(o)\ne \perp$. Now for the $n^{th}$ transition, the arbitrary statement $S_n$ must be chosen from set of operations including capturing, creating or matching as per the requirements of the theorem. Since these rules do not specify any removal condition and were the same choice of operations available for the ${(n-1)}^{th}$ transition. We can claim by structural induction on the operational semantics, $o$ persists in all transitions unless explicitly removed through deletion. Therefore we can conclude that ${\sigma }_{n+1}(o)\ne \perp$ as required by the theorem.

$◀$

The captureAll method given in Figure 4 line 2 is used to insert data into $ϵ$Store by capturing all objects reachable from the given argument object obj under reflexive transitive closure. We use a Breadth First Search (BFS) [10] strategy to traverse the graph of object references reachable from the root object obj. capture method inserts only the given object into $ϵ$Store.

Semantically, to capture an object in $ϵ$Store translates to storing references to the object in the EpsilonStore instance’s labelObjectMap and datastore fields as well as to store its primitive and reference field information (name and type) in ClassInfo instance present inside the labelClassInfoMap field.

The algorithm for capturing objects into $ϵ$Store is given in Algorithm 1. We use a FIFO queue inside a loop to collect all the objects directly and indirectly reachable from the argument object through its reference fields during each iteration. In each iteration, we pop an object $o^{\prime }$ from the head of the queue (line 4), compute its hash (ID) (line 8) to check if it already exists in the $ϵ$Store instance (lines 9-11), and add it to datastore if absent (line 12). We then get the fully qualified class name of the object’s class (line 13), check if its mapped to a list in labelObjectMap, and append the object to the list if mapped (line 18). If not mapped, we then insert a new empty list for this key in labelObjectMap (line 15) and append the object. In addition, we also create a ClassInfo instance for the class of this object to cache its field information and insert it into the labelClassInfoMap field (line 16). Following this, we get the reference field objects of $o^{\prime }$ and insert them into the queue (line 22). The loop terminates when the queue is empty.

The query method is shown in Figure 4 line 3 and is used to query the $ϵ$Store instance. It takes the Cypher query string cQuery as an argument and returns a ResultSet containing the result of the query: references to objects in the $ϵ$Store instance.

Data can also be inserted into $ϵ$Store through Cypher CREATE queries. The algorithm for data insertion through queries is given in Algorithm 2. We describe the case when the Cypher query specifies the creation of a multiple single node pattern (CREATE (n:label1 {...}), (m:label2), ...). We start by iterating through all the node definitions in the Cypher query string and collect their labels, property names, property values, and their outgoing edge labels. For each property name and value pair, we infer the property type (line 5) using the mapping given in Table 2. Next, for each node definition, we invoke GETORMAKECLASS which either finds a class with a fully qualified name matching that node label or dynamically creates a class with the name matching the label and with its field definitions matching the node’s property names and types. The GETORMAKECLASS procedure first checks (line 11) the labelClassInfoMap field for the class, matching the passed in label argument $l$ and returns it if present (line 12). If absent, we attempt to find the class corresponding to the label by iterating through all the classes loaded into the JVM by all the available classloaders [12, 48] and return it if found (line 18). If this also fails, then $ϵ$Store proceeds with dynamic class creation at runtime (line 21). We use the bytecode manipulation and analysis framework ASM [7] to dynamically generate the class. Once the class is found or created, we instantiate it (line 7) and set the fields of the instance to the collected property values. The instance is then captured into $ϵ$Store.

The class instantiation procedure CreateAndSetFields checks for consistency of the inferred property types and the field definitions present in the class. An exception is thrown if the checks fail due to a type mismatch.

Cypher queries may specify patterns in their clauses that require matching a node’s properties (MATCH (n {a:10})) or its relationships (MATCH ()-[:label]->()). Executing these queries requires accessing the fields of objects. To optimize query execution and avoid the overhead of repeatedly retrieving the field name and type for every object, we cache these field information in $ϵ$Store’s ClassInfo instances. Since fields are defined in an object’s class in Java, it is sufficient to have one ClassInfo instance to cache the field information for all objects of that class. These ClassInfo instances are stored in $ϵ$Store’s labelClassInfoMap field. This field is a hashmap that maps a label to its corresponding ClassInfo instance. ClassInfo is an abstract class. We have two concrete implementations of it based on the approach used to retrieve the field values. We refer to these two implementations of $ϵ$Store as $ϵ$Store^r and $ϵ$Store^u.

• $\mathrm{■}$

  $\mathit{ϵ}$Store^r uses Java reflection [53] to retrieve the field values. This implementation contains a hashmap mapping field names to their corresponding java.lang.reflect.Field [50] instances, obtained using reflection. These Field instances are used to retrieve the field values.

• $\mathrm{■}$

  $\mathit{ϵ}$Store^u uses Java’s unsafe [41] API to retrieve the field values. This implementation contains a hashmap mapping field names to field offsets (type long values). These field offsets are used to retrieve the field values.

$ϵ$Store stores inserted objects using their unique ID’s and their labels (types).

• $\mathrm{■}$

  Storing by label. Every object in Java is an instance of a class which defines its type and the fully qualified name of this class is the label of the object. The labelObjectMap field is used for storing inserted objects based on their label. This field is a hashmap that maps labels to ordered lists of objects belonging to the corresponding labels. During query execution, if the query string specifies a label for a node to be matched, then since labelObjectMap stores objects by their labels, we can use it to efficiently search only a subset of the stored objects.

• $\mathrm{■}$

  Storing by ID. The ID is assumed to be unique for every inserted object and is by default computed internally by invoking the identityHashCode [46] method provided by java.lang.System package on the object. The datastore field is used for storing objects based on their ID. This field is a hashmap that maps the ID of an inserted object to itself. If the ID of an object being inserted is found to already exist in the datastore then the old object reference mapped to that ID in the datastore is replaced with the new object reference. During query execution, if the query string specifies a node and its ID then the datastore can be used to reduce the search space of stored objects and hence optimize query performance.

Our storage schemes are designed such that the storage structures require minimal update on insertion or removal of objects from $ϵ$Store.

Neo4j [28] is a graph database and arguably, the most popular one in the industry at the moment. It uses the LPG data model. Neo4j has two modes.

• $\mathrm{■}$

  Server Mode (Neo4j^s): In this mode, Neo4j operates as a database server and runs in a JVM separate from the test JVM which contains the benchmarking queries. We use the Neo4j Java driver [35] version 4.3.3 in the test JVM to send the benchmarking query strings to the Neo4j server. The driver implements the Bolt [30] protocol (similar to JDBC) to communicate with the server. We build Neo4j from source inside docker and load it with the LDBC SNB benchmark dataset. The loading of the datasets (CSVs describing nodes and relations) is done using Neo4j’s batch import tool neo4j-admin [34].

• $\mathrm{■}$

  Impermanent Mode (Neo4jⁱ): In this mode, all data inserted into the database are stored in-memory and is non-persistent, and the database runs inside the JVM running the LDBC benchmark queries. This mode is only available in internal test-suites of Neo4j. The Docker image used for evaluation is the same as that built for the server mode. We first create an impermanent database by instantiating GraphDatabaseService [31] through dependency injection with ImpermanentDbmsExtension [32]. We then insert the LDBC SNB benchmark datasets into the database by using CREATE Cypher queries to create the corresponding nodes and relations through database transactions.

We include both, Neo4j^s and Neo4jⁱ as a point of reference in our evaluation of $ϵ$Store on the LDBC SNB benchmark. We use Neo4j version 5.13.0 and default configuration for all modes of Neo4j in our experiments.

OGO [57], similar to LINQ [42], combines imperative and declarative (via Cypher) styles of programming. Namely, OGO sees the entire JVM heap (i.e., object graph) as a single graph and enables developers to query the heap (or a subset of it) using queries. We compare it with $ϵ$Store for writing methods using queries on several data structures by replacing existing imperative implementations.

Table 3 shows some major differences between the existing systems we used in our evaluation and $ϵ$Store. We categorize the feature differences into Programmability and Database features. Programmability features broadly include capabilities such as schema creation, querying runtime program state, manipulating objects on the heap and quickly implementing methods of library classes. These are (partially) supported by OGO and $ϵ$Store. However, most graph databases lack all or most of these features. The database features include some features found in traditional databases such as support for multiple views, multi-tenancy, in-memory or non-persistent storage, and ACID compliancy. Most graph databases support all or most of these features, while $ϵ$Store focuses on support for multiple views, in-memory and multi-tenancy features. This table serves to highlight the differences in the design of traditional graph databases and $ϵ$Store and thus their area of applicability.

To evaluate $ϵ$Store as a graph store and answer RQ1, we use the SNB benchmark from LDBC [56]. LDBC provides both, various sized datasets for its benchmarks and the Cypher queries. The size of a dataset is measured using scale factor which is its uncompressed disk space (e.g., an uncompressed dataset that requires 10GB of disk space would have a scale factor of 10). The LDBC SNB was designed with the aim to model a snapshot of the activity in a realistic social network during a period of time. Table 4 shows the nodes and relationships that appear in the LDBC SNB benchmark and their variation with scale factors used in our evaluation namely, 0.1, 0.3, 1, 3 and 10. Higher scale factors can be supported since $ϵ$Store is only limited by the memory available to the JVM which can be increased with the JVM option -Xmx. We observe that the frequency of some nodes (Comment) and relationships (Person Likes Comment) scale by order of magnitude for an order of magnitude increase in scale factor whereas that of others such as Tagclass and Tagclass IsSubclassOf Tagclass do not change with scale factor. Query execution time is affected by these different occurrence frequencies depending on the node and relationship labels appearing in it. We use all the queries from the LDBC SNB benchmark that are currently supported by $ϵ$Store. Many queries use Cypher language features which are not implemented in $ϵ$Store yet (§6). Table 5 gives a brief description of the used queries. The name of the query as it appears in the LDBC SNB benchmark documentation is shown in column 1. The queries all contain either a read (MATCH) clause or a read and an update (CREATE) clause. These read and update clauses contain either single node or two-node patterns. The pattern contained in the queries is given by columns 3, 4 and 5. Finally, a brief description of the queries is given in column 6. Generally, ignoring indexing schemes, we should expect the query execution time to scale with the number of operations performed and the frequency of occurrence of labels in its patterns. For example, $Q_{SNB}^G$ contains the most occurring label (Comment) in the benchmark in its patterns and 2 clauses, and would be expected to take more time to execute than $Q_{SNB}^D$ that involves less frequently occurring labels and just 1 clause.

To evaluate $ϵ$Store as an engine to modify objects on the heap and answer RQ2, we use data structures from three sources: Java Collections Framework (JCF) [49], Google Guava [21], and the Eclipse Collections [17] projects. We rewrote on average 2 library methods from each of these data structures to use Cypher queries (rather than the imperative implementation). Simply, for $ϵ$Store, we insert the data structure into an instance of $ϵ$Store and run a query that implements the same functionality as exiting imperative code.

In our early experiments, we noticed substantial variations in query execution times across several runs, which we attribute to the JVM environment. To stabilize the time, we perform the following steps. We first load the dataset for a given scale factor into the systems used in our evaluation. Next, we execute all the chosen LDBC queries for that benchmark in a randomized order. We call this as the $1^{st}$ set. Following this, we once again execute the same set of queries in another randomized order. We call this as the $2^{nd}$ set. The sets are executed back-to-back in the same JVM process. The profile data for an evaluation run is collected for every query execution in both the sets. However, when reporting the profile data for a query for an evaluation run, we use the data from the $2^{nd}$ set and discard the $1^{st}$ set. Figure 7 shows a boxplot of the query execution time for the queries in the $1^{st}$ and $2^{nd}$ sets for $ϵ$Store^r across 10 evaluation runs. It is observable that profile data for the queries collected from the $2^{nd}$ set has substantially lower variance than that collected from the $1^{st}$ set, and, hence, the query profile data are more stable across runs.

The collected profile data breaks down the total query execution time (${𝐓}_{\mathrm{𝐭𝐨𝐭}}$) into the query parsing time (${𝐭}_{\mathrm{𝐏𝐚}}$), query plan generation time (${𝐭}_{\mathrm{𝐏𝐥}}$), and query plan execution time (${𝐭}_{\mathrm{𝐄𝐱}}$). We compute the sum breakdown time (${𝐭}_{\mathrm{𝐁𝐝}}$) from the profile data as $t_{Bd}$$=$$t_{Pa}$$+$ $t_{Pl}$$+$ $t_{Ex}$. All times are reported in milliseconds unless otherwise stated.

Table 6 shows the results for LDBC SNB. Column 1 shows the query abbreviation. Column 2 shows the scale factor of the dataset. Columns 3-5 show the results for Neo4j^s, Neo4jⁱ, and $ϵ$Store^r respectively. We initially hypothesized that using reflection to retrieve field values may degrade performance due to excessive runtime type-checking. To test our hypothesis, we decided to implement field access using reflection ($ϵ$Store^r) and the unsafe API ($ϵ$Store^u). However, we observed no significant performance difference between these two modes of $ϵ$Store. Hence, for brevity, we omit showing $ϵ$Store^u results in Table 6.

For each system, we show the query parsing time ($t_{Pa}$), query planning time ($t_{Pl}$), query plan execution time ($t_{Ex}$), sum breakdown time ($t_{Bd}$), and the total query execution ($T_{tot}$). We use bold text for $T_{tot}$, and we use gray background to show the best value (smallest $T_{tot}$) in each row. OOM indicates out of memory (when the physical memory requirement exceeds $\sim$64GB). The $T_{tot}$ of queries in general scales with scale factor of the datasets with the exception of some queries (e.g., $Q_{SNB}^A$,$Q_{SNB}^B$), that operate on node labels containing very few nodes. We can see that the $T_{tot}$ of $ϵ$Store is comparable or better than the production graph database for most of the queries. The graph database outperforms $ϵ$Store for query $Q_{SNB}^E$ because, $Q_{SNB}^E$ matches referrer node with label containing the highest amount of nodes in the benchmark (20 million+ for SF 10). This shows that for testing purposes, where datasets are relatively smaller, $ϵ$Store can be used as a lightweight graph store instead of a full fledged production graph database.

In addition to time, we also measured memory consumption for all the systems. We used pidstat [39] to collect memory consumption during evaluation runs. Figure 8 shows the peak memory usage for each system (one bar per system). The virtual and physical memory consumption in GB during running all the selected queries on the SNB for different scale factors is shown in Figure 8(a) and Figure 8(b), respectively. We allow Neo4jⁱ and Neo4j^s to manage their own memory requirements [33], e.g., allocating page cache. We observe that the virtual memory usage of a system does not change significantly across scale factors of the SNB benchmarks. The physical memory usage, on the other hand, increases with increasing scale factors for all the systems. Neo4jⁱ requires the most physical and virtual memory and is OOM for the SNB scale factor 10 dataset. $ϵ$Store^r consumes the least amount of virtual memory across the systems and is second only to Neo4j^s in terms of the least physical memory consumed. This is to be expected since $ϵ$Store^r being in-memory, stores all inserted data on RAM whereas Neo4j^s can store part of it on disk and can page it into RAM as and when required. We once again see that for smaller datasets, which is generally the case during testing, $ϵ$Store’s memory consumption is comparable or better than a production graph database.