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
AssigneeInternational Business Machines Corporation
InventorsChun-Fu Chen, Jason L. Crawford, Ching-Yung Lin, Jie Lu, Mark R. Nutter, Toyotaro Suzumura, Ilie G. Tanase, Danny L. Yeh
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.