Writing Idempotent Queries in Gremlin

Article summary

In Gremlin, a query executes as a self-contained transaction. That means the query must completely succeed in order for any changes it has made to be committed. If any part of the query fails, the whole thing is rolled back.

And in graph systems that support locking, queries will lock parts of the graph while they run. As with any database system, locking can lead to deadlocks or cause simultaneous queries to fail.

In many cases, queries that are deadlocked or blocked by concurrent modifications can be retried automatically. But in order for retries to work reliably, queries need to be idempotent. This just means that the query can be executed more than once, without having any additional effect beyond the first successful execution.

The Problem

Consider the following Gremlin query:

g.addV("User").property("name", "Bob")

This query will add a new user named Bob every time it is run. In order to make this query idempotent, we first need to check to see if Bob already exists. And we need to do this check in the same query. If we issued two separate queries — one to check for existence, and another to create — it’s possible that a parallel query could run in between these two, resulting in duplicate Bobs.

There is a common pattern for this type of check in Gremlin known as “fold, coalesce, unfold.” Briefly, this is what these three steps do:

Fold is like the reverse of a flatten operation. It evaluates traversals up to this point and aggregates results into a single list. Importantly, the output of fold is always a single traverser. More on this later.

Coalesce is given a number of traversals and passes through the results of the first one that outputs a result. It’s like a simplified if-else.

Unfold, as you can imagine, is the opposite of fold and is very much like a flatten operation.

The Solution

So in our example, this would look like:

g.V().hasLabel("User").has("name", "Bob")
        addV("User").property("name", "Bob"))

When Bob already exists:

  1. fold outputs [Bob]
  2. coalesce tries the first traversal (unfold outputs Bob)
  3. coalesce passes through the output of unfold

When Bob doesn’t yet exist:

  1. fold outputs []
  2. coalesce tries the first traversal (unfold outputs nothing)
  3. coalesce tries the second traversal (addV creates and outputs Bob)
  4. coalesce passes through the output of addV

The behavior of fold is important to this operation because at least one traversal must make it through each step in order for a query to continue. fold may seem excessive, since we are only dealing with a single vertex, but consider the following simplification (which will not work):

g.V().hasLabel("User").has("name", "Bob")
        addV("User").property("name", "Bob"))

In this case, the query will complete early when Bob doesn’t exist, returning no results (and not creating Bob).

Automatic Retry

Now that the query is idempotent, we can have our Gremlin client automatically retry queries that fail due to concurrency issues. The procedure for this varies depending on the client language but usually involves pasting some boilerplate into your connection handling code.