Distributed graph databases that facilitate streaming data insertion and queries by reducing number of messages required to add a new edge by employing asynchronous communication

• US 10,380,188 B2
• Filed: 08/05/2016
• Issued: 08/13/2019
• 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): Boccio, Vincent F
• Application Number:
  US15/230,000
• Publication Number:
  US 20180039709A1
• Time in Patent Office: 1,103 Days
• Field of Search: 707798
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 9/547 Remote procedure calls [RPC]; Web services

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 reduce number of messages required to add a new edge to a distributed graph database across a plurality of machines by employing asynchronous communication comprising:

receiving, by a first machine of the plurality of machines, a request to add a target vertex associated with a first shard of the first machine, wherein the first machine is operatively coupled to a processor;

adding, by the first machine, the target vertex at the first machine;

generating, by the first machine, a unique target vertex identifier (VIDT) associated with the target vertex;

forwarding, by the first machine, the VIDT to a second machine, that initiates the second machine to;

add a source vertex associated with a second shard of the second machine,

generate a unique source vertex identifier (VIDS) associated with the source vertex, comprising the acts of;

preparing a unique edge identifier (EID) as {ShardID, MAXEID}, where ShardID is a unique shard identifier, and MAXEID is a number,

creating a label (LID),

incrementing MAXEID,

adding an outgoing edge {VIDS, VIDT, LID, EID} at the second machine, and

forwarding {VIDS, VIDT, LID, EID} to the first machine; and

adding, by the first machine, an incoming edge {VIDT, VIDS, LID, EID} at the first machine.

2. The method of claim 1, wherein a maximum of three communication steps are performed per added new edge to the distributed graph database.

3. The method of claim 1, wherein a maximum of four communication steps are performed per added new edge to the distributed graph database, and further comprising sending a confirmation to a client initiating the request.

4. The method of claim 1, wherein one or more vertices or edges of the distributed graph database is associated with respective labels to categorize the one or more vertices or edges and facilitate efficient traversal.

5. The method of claim 1, wherein a property set of a vertex or edge of the distributed graph database comprises a list of key-value pairs where each key is a property name and a value associated with a key is a value of a corresponding property for the vertex or edge.

6. The method of claim 5, wherein the value of the property is at least one of:

strings, numbers, vector of numbers, or composite values consisted of strings and numbers.

7. The method of claim 1, wherein internally vertex-centric representations of the distributed graph database store vertices and edges.

8. The method of claim 1, wherein internally vertex-centric representations of the distributed graph database store maps for vertex and edge properties.

9. The method of claim 1, storing, by an underlying high-performance key-value store, representations in a memory.

10. The method of claim 1, using Remote Procedure Call (RPC) as a core communication abstraction of the distributed graph database.

11. The method of claim 10, wherein the RPC is abstracted on top of a native communication library of at least one of:

a socket, Message Passing Interface (MPI), Parallel Active Message Interface (PAMI) or Global-Address Space Networking (GASnet) inheriting advantages and disadvantages of underlying layers.

12. A machine that reduces number of messages required to add a new edge to a distributed graph database across a plurality of machines comprising the machine by employing asynchronous communication, comprising:

a processor, operatively coupled to at least one memory, to execute the following computer executable components stored in the memory;

a graph database component that;

receives a request to add a target vertex associated with a first shard of the machine;

add the target vertex at the machine;

generate a unique target vertex identifier (VIDT) associated with the target vertex;

forward the VIDT to a second machine, that initiates the second machine to;

add a source vertex associated with a second shard of the second machine,

generate a unique source vertex identifier (VIDS) associated with the source vertex, comprising the acts of;

 

prepare a unique edge identifier (EID) as {ShardID, MAXEID}, where ShardID is a unique shard identifier, and MAXEID is a number,

increment MAXEID,

add an outgoing edge {VIDS, VIDT, LID, EID} at the second machine, and

forward {VIDS, VIDT, LID, EID} to the first machine; and

add an incoming edge {VIDT, VIDS, LID, EID} at the first machine.

13. The machine of claim 12, wherein a maximum of three communication steps are performed per added new edge to the distributed graph database.

14. The machine of claim 12, wherein a maximum of four communication steps are performed per added new edge to the distributed graph database, and the graph database component further sends a confirmation to a client initiating the request.

15. The machine of claim 12, wherein one or more vertices or edges of the distributed graph database is associated with respective labels to categorize the one or more vertices or edges and facilitate efficient traversal.

16. The machine of claim 12, wherein a property set of a vertex or edge of the distributed graph database comprises a list of key-value pairs where each key is a property name and a value associated with a key is a value of a corresponding property for the vertex or edge.

17. A computer program product that reduces number of messages required to add a new edge to a distributed graph database across a plurality of machines by employing asynchronous communication, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processing component of a machine of the plurality of machines to cause the processing component to:

receive a request to add a target vertex associated with a first shard of the machine;

add the target vertex at the machine;

generate a unique target vertex identifier (VIDT) associated with the target vertex;

forward the VIDT to a second machine, that initiates the second machine to;

add a source vertex associated with a second shard of the second machine,

generate a unique source vertex identifier (VIDS) associated with the source vertex, comprising the acts of;

prepare a unique edge identifier (EID) as {ShardID, MAXEID}, where ShardID is a unique shard identifier, and MAXEID is a number,

increment MAXEID,

add an outgoing edge {VIDS, VIDT, LID, EID} at the second machine, and

forward {VIDS, VIDT, LID, EID} to the first machine; and

add an incoming edge {VIDT, VIDS, LID, EID} at the first machine.

18. The computer program product of claim 17, wherein the program instructions are further executable by the processing component to cause the processing component to perform a maximum of three communication steps per added new edge to the distributed graph database.

19. The computer program product of claim 17, wherein the program instructions are further executable by the processing component to cause the processing component to perform a maximum of four communication steps per added new edge to the distributed graph database, and the processing component further sends a confirmation to a client initiating the request.

20. The computer program product of claim 17, wherein one or more vertices or edges of the distributed graph database is associated with respective labels to categorize the one or more vertices or edges and facilitate efficient traversal.