  Graph databases (GDBs) are crucial in academic and industry applications. The
key challenges in developing GDBs are achieving high performance, scalability,
programmability, and portability. To tackle these challenges, we harness
established practices from the HPC landscape to build a system that outperforms
all past GDBs presented in the literature by orders of magnitude, for both OLTP
and OLAP workloads. For this, we first identify and crystallize
performance-critical building blocks in the GDB design, and abstract them into
a portable and programmable API specification, called the Graph Database
Interface (GDI), inspired by the best practices of MPI. We then use GDI to
design a GDB for distributed-memory RDMA architectures. Our implementation
harnesses one-sided RDMA communication and collective operations, and it offers
architecture-independent theoretical performance guarantees. The resulting
design achieves extreme scales of more than a hundred thousand cores. Our work
will facilitate the development of next-generation extreme-scale graph
databases.
