One of the substantial benefits of the family of NOSQL (Not only SQL) databases is their tendency to be able to scale predictably. One of the key elements to being able to scale NOSQL databases is sharding, where a large dataset can be broken up and distributed across a number of (typically replicated) shards. For simple data models like Key-Value, Column-family, and Document databases this is a sensible solution. In such stores, the key to retrieve any item stored is well known and stable, while the lookup mechanism is both predictable (e.g. consistent hashing) and rapid (e.g. using Bloom filters to statistically locate a hot replica). Given those conditions, it’s straightforward for a client looking to store or retrieve data to be directed to an appropriate shard.
Unfortunately for graph databases like Neo4j, sharding isn’t straightforward at all, leaving most solutions with a bit of a scaling headache. Unlike other classes of NOSQL database, a graph doesn’t have predictable lookup since it is a highly mutable structure. Worse, there are competing requirements when sharding a graph across physical Neo4j instances. For example, we want to co-locate related nodes for traversal performance, but we don’t want to place so many connected nodes on the same database that it becomes heavily loaded.
The opposite is also true, that we don’t want too widely connected nodes across different database instances since it will incur a substantial performance penalty at runtime as traversals cross the (relatively latent) network.
Given that a naive solution will lead to hotspots causing contention for local resources, or incur many network hops as the graph is traversed thus substantially increasing query time, we need to look for a better approach. The holy grail of graph algorithms is to balance a graph across database instances by creating a minimum point cut for a graph, where graph nodes are placed such that there are few relationships that span shards.
The trouble with this picture is that it’s hard to achieve in practice, especially since connected graphs can mutate rapidly and unpredictably at runtime. We can help to maintain a balanced graph by applying domain-specific knowledge to place nodes on shards; we can use insert-time algorithms to help us select the most appropriate shard to place a node; and we can use re-balancing algorithms periodically (sort of like a graph defrag) to help maintain a good node-to-shard mapping at runtime. We can also keep heuristic information on which relationships are traversed most frequently and optimise around those. However, as you might guess, much of this is an ongoing research problem and our community and customers have pressing needs to scale even while diligent computer scientists and mathematicians are working towards ever better graph algorithms. So, in the meantime, the Neo4j team has observed a pattern that we’re calling “cache sharding” to help solve the problem of efficiently querying large datasets with graph databases, which I’ll cover in my next posting.