Massive Parallel Imports in Neo4j Without Deadlock and Lock Contention

Optimizing graph import partitioning based on workers and k-1 coloring algorithm. This article is a generalization of the approach designed by Eric MONK in his article “Mix and batch: a technique for fast, parallel relationship loading in Neo4j”. It explains the theoretical underpinnings and ideas. A follow up article will show the practical application and provide the source code repository. His approach uses the final digits of source and target node IDs to build non-overlapping partitions, then groups the resulting matrix cells along cyclic diagonals into sequential batches that can be loaded in parallel without accessing the same node sets concurrently. The approach has two main limitations: Diagonal batching is unsafe when source and target nodes are not disjoint (for example, if you create relationships between Person nodes). Use the K-1 coloring algorithm to compute batches of partitions that can be imported in parallel. Generally, when data is loaded in batches, there is one table for nodes and one table for relationships. This…