Time-Traveling with Graph Databases: A Simplified Tutorial

Time Traveling with Graph Databases: A Simplified Tutorial

A while back, we posted an in-depth article explaining how to performantly store and query graph revision data in ArangoDB. That article was heavy on the technical details, but light on straightforward examples. In this tutorial on time traveling with graph databases, we will leave behind most of the theory and help you get started with managing actual graph revision data by walking you through a simple use-case.

We will assume a basic familiarity with storing and querying graph and document data in ArangoDB using our arangosh tool.

A Simple Application

Suppose we are managing a small data center, and want to keep track of the components in servers, and how they change over time as we replace or upgrade systems. We might model this by creating vertices of different types to represent each server, each type of component (e.g. one vertex to represent each model of hard drive used), and each instance of a component (e.g. an individual physical hard drive). Furthermore, we may wish to log failure and maintenance events, and connect all of these vertices together by edges to connect an event to its server and to connect each instance of a component to both it’s model number and the server in which it is used. See below for a representation of this data model:

ArangoDB data model for the simple application

This would allow us to use a simple graph traversal to examine a particular failure event like a hard drive failure, determine the model number involved, and check which other machines use the same type of drive and thus are potentially at elevated risk for a failure.

Additionally, if we are storing all the temporal and revision data, like when an error occurs, when drives are added, removed, or replaced, when servers are brought online, etc., then we can look at our datacenter at any point in time. We can exclude past configurations from queries about the present time, or we can look back to see which configuration was live when a particular error occurred.

Basics for Time Travel

In this time traveling with graph databases tutorial, we will introduce the basic techniques for storing and querying the revision data performantly. These are covered in much greater detail in the original article. The three key notions are time-slicing, copy-on-write, and proxies.

Each vertex and edge will be augmented with two timestamps. The first will be called created and hold the timestamp denoting its creation time. The other will be called expired, denoting a time when it became invalid. We will use a placeholder value equal to the maximum representable integer to indicate it has not expired yet. The act of time-slicing is simply filtering the graph based on a given query time t, such that we return only data with values created <= t < expired.

When we wish to delete an edge or vertex, instead of actually deleting it, we simply expire it by setting the expired value to the current timestamp. When we wish to modify an edge or vertex, we expire the current version and create a new copy with the modified data. These two changes describe copy-on-write semantics.

Copy-on-write introduces a possible performance pitfall. When creating a copy of a vertex, we would also need to copy all the incident edges. Since the number of edges could be very large, this could become expensive. Instead, we will use proxies to connect our vertices with their incident edges. In this transformation, each vertex in our application is joined by a single edge to an in-proxy vertex and to an out-proxy vertex. Then, each edge in our application connects the out-proxy of its source vertex to the in-proxy of its target vertex. In this way, when we modify a vertex, we need only copy it, and it’s proxy edges. The proxy vertices remain stable with respect to application edges.

Below is a demonstration of the proxy vertex transformation. The image on the left is our original graph. Let’s focus on the vertex in the center. If we add proxy vertices, we expand this into three vertices, with a single edge connecting the original vertex to each proxy, yielding the configuration in the center. If we wish to then make a change to the logical vertex, we need only create a new vertex and connect it to the proxy vertices, as demonstrated on the right.

ArangoDB proxy vertex transformation

Because of the copy-on-write semantics, we may have multiple physical copies of each logical vertex or edge. Each will receive an auto-generated _key value, but we may wish to use some persistent identifier across the copies. This also gives us an additional way to quickly lookup proxy vertices for a given logical vertex. We’ll see some examples of this later on.

Finally, with the proxies, we can move the timestamps of the vertices themselves, and onto the incident edges. Recall that each vertex will have exactly one incident edge in each direction connecting it to its proxies, which must be traversed to include the vertex itself in a traversal.

Data

Let’s go ahead and populate our database with a bit of data. First, let’s set up our collections.

These utility functions will make it a bit easier to populate our data. We can use them as a simple pre-processors for our insertions.

Now we will write several documents transactionally. We will choose to use the same created timestamp for all of them, so that the transactionality is preserved with respect to time-slicing.

Time-slicing

We can now use time-slicing to query which drive models are used in a given server at the present moment.

This should return something like the following.

Copy-on-write

Let’s suppose we want to add additional information to one of our server records, such as a server IP. To do this, we need to first expire the document, then write the new copy. We will use a function to help us.

We can then check the current version of the server document by time-slicing.

This should return something like the following.

However, we can check for all revisions by removing the time-slicing.

This should return something like the following.

Putting It All Together

Now let’s add another server and some drives to go with it.

Now suppose we register a failure in one of these drives. We want to log the event and remove the failed drive from the datacenter.

Suppose we want to follow up and check which servers still have instances of this same drive model which failed.

This should return our (previously-modified) server.

Wrapping Up

As you can see by going through this time traveling with graph databases tutorial, maintaining revision history can be accomplished with ArangoDB in a relatively straightforward fashion. With appropriately defined indices, it should be quite performant as well.

Unfortunately, it does add some overhead to application development. Luckily, much of this can be abstracted away into some helper methods. I have chosen to show some of this abstraction above to help but did not develop a full library-like solution. The examples above help to demonstrate well the graph structures that result from copy-on-write semantics and should hopefully help you understand well enough to start working on your own solutions.

If you wish to explore the topic in further detail, please check out our earlier article on the subject. We love to hear about what others are doing with ArangoDB, so feel free to drop by our community Slack and share your story or get some help!

Do you like ArangoDB?
icon-githubStar this project on GitHub.
close-link