Distributed graph databases that facilitate streaming data insertion and low latency graph queries

• US 10,552,450 B2
• Filed: 08/05/2016
• Issued: 02/04/2020
• Est. Priority Date: 08/05/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Chun-Fu, Crawford, Jason L., Lin, Ching-Yung, Lu, Jie, Nutter, Mark R., Suzumura, Toyotaro, Tanase, Ilie G., Yeh, Danny L.
• Primary Examiner(s): Mofiz, Apu M
• Assistant Examiner(s): Holland, Sheryl L
• Application Number:
  US15/230,071
• Publication Number:
  US 20180039673A1
• Time in Patent Office: 1,278 Days
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A novel distributed graph database is provided that is designed for efficient graph data storage and processing on modern computing architectures. In particular a single node graph database and a runtime & communication layer allows for composing a distributed graph database from multiple single node instances.

Claims

1. A computer-implemented method to provide low latency graph queries of a distributed graph database having a plurality of shards, comprising:

receiving, by a query manager, one or more graph queries requesting edge addition to the distributed graph database from one or more clients; and

performing, by one or more threads of execution managed by the query manager, one or more edge additions in response to the one or more graph queries;

wherein a thread of execution performs an edge addition by;

sending, by the thread, a first asynchronous request to a first node containing a first shard, the first asynchronous request identifying a source vertex, an edge label (LID), and a target vertex, thereby causing the first node to add to the first shard the target vertex and to generate a target vertex identifier (VIDT) corresponding to the target vertex;

sending, by the first node, a second asynchronous request to a second node containing a second shard, the second asynchronous request identifying the source vertex, the LID, and the VIDT, thereby causing the second node to add to the second shard the source vertex, to generate a source vertex identifier (VIDS) corresponding to the source vertex, to add to the second shard an outgoing edge labelled with the LID and associated with the source vertex, and to generate an edge identifier (EID) corresponding to the outgoing edge; and

sending, by the second node, the VIDS, the LID, the EID, and the VIDT to the first node, thereby causing the first node to add to the first shard an incoming edge associated with the target vertex and having as attributes the LID and the EID.

2. The computer-implemented method of claim 1, wherein additional query managers are instantiated to accommodate increasing load.

3. The computer-implemented method of claim 1, wherein the query manager runs on its own machine with a variable number of threads, each thread being capable of performing a traversal.

4. The computer-implemented method of claim 1, wherein multiple graph traversals are handled concurrently by multiple threads.

5. The computer-implemented method of claim 1, wherein the query manager is associated with a plurality of query managers and wherein each of the plurality of query managers maintains a connection with respective dbase shards.

6. The computer-implemented method of claim 5, further comprising:

placing, by the query manager, asynchronous requests to all dbase shards.

7. A system that provides low latency graph queries of a distributed graph database having a plurality of shards, comprising:

a memory that stores computer executable instructions; and

a processor that executes the computer executable instructions stored in the memory, wherein execution of the computer executable instructions causes the processor to;

receive, by a query manager, one or more graph queries requesting edge addition to the distributed graph database from one or more clients; and

perform, by one or more threads of execution managed by the query manager, one or more edge additions in response to the one or more graph queries;

wherein a thread of execution performs an edge addition by;

sending, by the thread, a first asynchronous request to a first node containing a first shard, the first asynchronous request identifying a source vertex, an edge label (LID), and a target vertex, thereby causing the first node to add to the first shard the target vertex and to generate a target vertex identifier (VIDT) corresponding to the target vertex;

sending, by the first node, a second asynchronous request to a second node containing a second shard, the second asynchronous request identifying the source vertex, the LID, and the VIDT, thereby causing the second node to add to the second shard the source vertex, to generate a source vertex identifier (VIDS) corresponding to the source vertex, to add to the second shard an outgoing edge labelled with the LID and associated with the source vertex, and to generate an edge identifier (EID) corresponding to the outgoing edge; and

sending, by the second node, the VIDS, the LID, the EID, and the VIDT to the first node, thereby causing the first node to add to the first shard an incoming edge associated with the target vertex and having as attributes the LID and the EID.

8. The system of claim 7, wherein additional query managers are instantiated to accommodate increasing load.

9. The system of claim 7, wherein the query manager also runs on its own machine with a variable number of threads, each thread being capable of performing a traversal.

10. The system of claim 7, wherein multiple graph traversals are handled concurrently by multiple threads.

11. The system of claim 8, wherein additional query managers maintain a connection with each respective dbase shard.

12. The system of claim 7, wherein the query manager also places asynchronous requests to all dbase shards.

13. A computer program product to provide low latency graph queries of a distributed graph database having a plurality of shards, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing component to cause the processing component to:

receive, by a query manager, one or more graph queries requesting edge addition to the distributed graph database from one or more clients; and

perform, by one or more threads of execution managed by the query manager, one or more edge additions in response to the one or more graph queries;

wherein a thread of execution performs an edge addition by;

sending, by the thread, a first asynchronous request to a first node containing a first shard, the first asynchronous request identifying a source vertex, an edge label (LID), and a target vertex, thereby causing the first node to add to the first shard the target vertex and to generate a target vertex identifier (VIDT) corresponding to the target vertex;

sending, by the first node, a second asynchronous request to a second node containing a second shard, the second asynchronous request identifying the source vertex, the LID, and the VIDT, thereby causing the second node to add to the second shard the source vertex, to generate a source vertex identifier (VIDS) corresponding to the source vertex, to add to the second shard an outgoing edge labelled with the LID and associated with the source vertex, and to generate an edge identifier (EID) corresponding to the outgoing edge; and

sending, by the second node, the VIDS, the LID, the EID, and the VIDT to the first node, thereby causing the first node to add to the first shard an incoming edge associated with the target vertex and having as attributes the LID and the EID.

14. The computer program product of claim 13, wherein the program instructions are further executable by the processing component to cause the processing component to instantiate additional query managers to accommodate increasing load.

15. The computer program product of claim 13, wherein the program instructions are further executable by the processing component to cause the processing component to run the query manager on its own machine with a variable number of threads, each thread being capable of performing a traversal.

16. The computer program product of claim 13, wherein the program instructions are further executable by the processing component to cause the processing component to handle multiple graph traversals concurrently by multiple threads.

17. The computer program product of claim 13, wherein the program instructions are further executable by the processing component to cause each respective query manager to maintain a connection with each respective dbase shard.

18. The computer program product of claim 13, wherein the program instructions are further executable by the processing component to place asynchronous requests from the query manager to all dbase shards.