Why a graph database?

QS2 uses tree based structures for more than half of the data. The other half can fit in a relational database, but we still need a complex schema for some parts, more easily handled with graphs.

Also, the model is highly hierarchical with a clear notion of ownership. Each atomic piece (a row in a table or a node in Neo4j) is only related to one parent, containing at most a few hundred children. Graph databases are more adapted to hold such data than managing SQL queries with dozens of joins or denormalized schema.

Why a schemaless database?

Even if we are doing SaaS, some of our customers are big enough to request some customizations. Customization include adding custom validation procedures with specific comments fields, or linking QS2 to other sytems with connectors to retrieve existing data. Much easier if you only have to update the code, no?

We are also dealing with extension modules complementing the core software with specific complex business needs. With a schemaless database, modules can simply be activated on demand for a specific client, without thinking about deploying a complex SQL alter-script.

I agree that schemaless databases are not a miracle solution. It can even be worse than schema-based databases due to the need of thinking explicitely about constraints implementation. A bad implementation will easily lead to data corruption. So, warning here. Remember, NoSQL stands for Not Only SQL. Never use a NoSQL database because it's cool. (But because it's fun, you can :P).

Why Neo4j?

Easy to understand, easy to use, professional, and it works!

During our preliminary tests, another java database seemed pretty cool and I gave it a try. This base can be used as a graph database or as a document database, with 6 different API to do whatever you want. Sadly, during some simple tests, we found 3 critical bugs, with one pretty frightening for scientists like us (missing parenthesis in a 3 lines 'if'). Neo4j offers far less features, but done well!

After one year of use, we only have been annoyed by one bug, which was already fixed in the next version at the time we discovered it.

Also, I have to thank the great Neo4j community, and offer them this blog post :)

One database per customer

With embedded Neo4j, this feature is really easy to implement. Simply create a new EmbeddedGraphDatabase with the right path :). This way, the currently used databases are the only ones to keep in memory (important in an SaaS environment).

In addition to security, another advantage is load balancing. Too many connected clients on one server? Simply open the previously duplicated database on another server and send clients request there.

Upgraders and migrations

Even if Neo4j is schemaless, as we have to send DTOs to the client, each node is typed and follows a core-schema (defined by DTO and linked to Neo4j using getProperty and setProperty calls). Extensions, modules and plugins can add some fields and relationships without influencing the base schema. To update the base schema in order to match the modification of core features, there are two diffrent ways: the hard track is by using an update-proof code, which can be really hard to maintain, while the second is using upgraders!

An upgrader is a class defined with a version number to upgrade, and implements an "upgrade" method. This method will process to the changes into the database. All upgraders are defined in the source code. When a user get connected, the corresponding customer database is loaded. Just after the database is loaded, the version number of the schema is checked, and upgraders are executed if available. Et voilà! No long global-alter procedure, only lazy applied upgraders when needed.

"Parameters" nodes

One important feature of QS2 is user defined parameters. Users can declare variables and use them in formulae. Parameters are declared in lists of parameters. All parameters declared in a parameter list are stored in one node, one property per parameter. The key of the property is the alias of the parameters, as every alias of a list has to be unique. Name, rank, value, unit and description are stored in one array, and the array is stored in the Neo4j node as the property value.

The solution is not perfect since the description can be rather long, and the whole array needs to be loaded to access to the value. An alternative solution would thus be spliting the node in two, and storing the description in the second node.

Helpers

Here are some of our helpers. I wish one day they will be built-in :)

UPDATE 2012-11-01: Remove getOppositeNode helper, as there is a built-in getOtherNode method

public class Neo4jUtils
{
    public static final <T> void setPropertyOrRemoveIfNull(final Node n,
                                                           final String propertyName,
                                                           final T propertyValue)
    {
        if (propertyValue != null)
        {
            n.setProperty(propertyName, propertyValue);
        }
        else
        {
            n.removeProperty(propertyName);
        }
    }
}

public class Neo4jDateUtils
{
    //TODO: Use FastDateFormat from Apache common ?
    private static final ThreadLocal<SimpleDateFormat> dateFormat = new ThreadLocal<SimpleDateFormat>()
                                                              {
                                                                  @Override
                                                                  protected SimpleDateFormat initialValue()
                                                                  {
                                                                      final SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
                                                                      sdf.setTimeZone(TimeZone.getTimeZone("UTC"));
                                                                      return sdf;
                                                                  }
                                                              };

    public static final Date convertToUTCDate(final String string)
    {
        try
        {
            return string == null ? null : dateFormat.get().parse(string);
        }
        catch (final ParseException e)
        {
            // This will happens only if the database is corrupted or if a developer messed up
            throw Throwables.propagate(e);
        }
    }

    public static String convertToUTCString(final Date date)
    {
        return date == null ? null : dateFormat.get().format(date);
    }
}

Ordered trees

Even if trees can easily be done using Neo4j, we sometimes need to store trees in which children are ordered. Neo4j doesn't provide ordered relationships.

A first solution, that we do not apply, would be to store the "rank" property in nodes or relationships. The issue here is that a rank depends on the rank of the other nodes, and since the relationships are not ordered, all children have to be explored to find a rank. As a result, when adding a node at the beginning of the children of the parent node, all children nodes have to be updated. Even to add a node at the end of children, the rank of the previous node have to be found.

A second solution, the one we use, is to do a sort of linked list, using four relationship types:

• CHILD: the relationship between the parent and all its children
• FIRST_CHILD: the relationship between the parent and its first child
• LAST_CHILD: the relationship between the parent and its last child
• NEXT_CHILD: the relationship between a child and the next child of the parent

This way, the number of nodes to explore is much less: you only have to touch 3 nodes in the worst case (child insertion or deletion in the middle). Sadly, this kind of modeling is heavier, and is not compatible with traversals nor Cypher

Factories, Deleters, Duplicators: 3 mini-frameworks

"Primary key" and Ids

IMHO, one big essential mind-shift when using Neo4j instead of SQL databases is the primary key handling. Many people (too many, I think), use auto-increment features for every tables, without thinking about the root question of database modeling: "What makes my record unique?".

To the question "How to have auto-increment feature in Neo4j?", my first answer would thus be "Are you sure you need an auto-incremented id?". In case of a positive answer, my second answer would be "Why the hell are you using a graph database then?" Think about it. Why do we need an auto-incremented id in an SQL database? Well, all rows are in the same table, so each row needs to have a different id to find the row during normal use. If the records don't have a natural unique ID, you can use for example an UUID. Or if performances matter, why not, use auto-increment.

Now, Neo4j. The great power of a graph database is clearly not to store flat data. So you certainly have a way to uniquely identify you nodes using structural info. Let's say you don't. Why not using UUID? Performances? I'm not sure using UUID instead of interger ids will make a big difference.

Worst, for now there is no build-in auto-increment feature. Implementing it wrongly could create bottlenecks. For example if each time you add a node with an auto-increment ID and make the choice to store the next available ID in a meta-data node, this meta-data node will be locked in every add transaction.

In our case, since our model is highly hierarchical, we decided to implement relative IDs, a kind of local auto-increment. Each time we add a node, its local ID is determined using a counter in the parent node. As the parent node is already locked due to the parent-child relationship, there is no locking overhead.

How to retrieve this node when the client does something? Let's start with the DTOs. When they are forged using recursive factories, each forged object is filled with a globalID composed by two parts: nodeId and chained local IDs.

NodeId

The nodeId is the internal Neo4j ID. As Neo4j can reuse nodeIds it's NOT recommended to use them as IDs. But as for now it's guaranteed that nodeIds are not reused until the next database restart, we took the decision that we will use them for a session time (DTOs are never saved to disk and totally recreated if a user reloads the client).

Chained local IDs

The chained local IDs is a string created by the concatenation of entity prefixes and entity IDs.

So a globalID will be like that: 1284_prj2_sys45_elt5_flw5.

When the client does an edition, the globalID is sent to the server. The nodeId is used to directly find the node concerned by the edition. The chained local IDs is used for security/ACL checks. For instance, if a user doesn't have credentials for editing anything in a specific project, any edition request with a chained local IDs starting with the local ID part of the project (e.g. prj2_) will be forbidden. This way, we can implement an ACL solution out of the graphDB.

The chained local IDs is also used for verification purpose, to ensure that the nodeId is really the node corresponding to the chained local IDs. Another good point about this kind of ids: duplications. Users often duplicate parts of their work. With local ids, we only have to care about changing the id of each top level duplicated node. For example, on project duplication, we can duplicate all the nodes and relationships with properties, and only change the id of the duplicate project node.

For import/export purpose, we also use sometime UUID in addition of local IDs.

Fragmentation

When computing LCA results for a project, we need to traverse the entire project. But we don't need other projects. Now imagine that the first created project is updated over and over for a long time. During this period, more projects are created and completed. The first project will have nodes here and there in the whole database, so it has to be fully loaded to retrieve only a few nodes.

It can even be worst if the whole database doesn't fit in RAM. We will have to be careful about this point.

Potential manual indexing issues

After some discussions in the mailing list, it seems that we have to be careful about indexes. When deleting a node without deleting the corresponding entries in the index, the index still contains the entries to this node. If you do a request on the index that should return the deleted node, corresponding entries will be automatically removed. So everything appears to be ok.

But, here comes the NodeID reusability. If the database is restarted and new nodes created between the deletion and the query, a node with the same nodeID as the deleted one can be created. As indexes works with IDs, your index will be corrupted and the query will return the newly created node...

So, remember: when deleting a node, always remove the entries in all the indexes related to the node.

Database opening time & Warm-up

For now, we're loading the database when a user log-in. We don't really have time to warm it up. We will have to be careful about first-connection metrics, and see if we need to do something about that.

No ordered tree support

A wonderful thing would be to have a native relationship ordering feature :)

No blob support

Even if it's not the purpose of a graph database to store blobs, it would be a great feature. Maybe using the same mecanism as what is done for indexes can be done, using an existing key-value store solution and only implement a kind of connector?