DISTRIBUTED GRAPH DATABASES THAT FACILITATE STREAMING DATA INSERTION AND LOW LATENCY GRAPH QUERIES

• US 20180039673A1
• Filed: 08/05/2016
• Published: 02/08/2018
• 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.
• Granted Patent: US 10,552,450 B2
• Time in Patent Office: 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, comprising:

performing, by a query manager operatively coupled to a processor, graph queries; and

managing, by the query manager, multiple threads of execution to handle multiple concurrent queries from one or more clients;

wherein for a complete traversal, a thread running on the query manager performs multiple requests to various shards during multiple waves corresponding to traversal levels, and wherein the thread maintains all partial results until the traversal finishes and return results to clients.

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, comprising:

a memory that stores computer executable components; and

a processor that executes the computer executable components stored in the memory, wherein the computer executable components comprise;

a query manager that performs graph queries, and manages multiple threads of execution to handle multiple concurrent queries from one or more clients;

wherein for a complete traversal, a thread running on the query manager performs multiple requests to various shards during multiple waves corresponding to traversal levels, and wherein the thread will maintain all partial results until the traversal finishes and then return results to clients.

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, 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:

employ a query manager to perform graph queries; and

employ the query manager to manage multiple threads of execution to handle multiple concurrent queries from one or more clients;

wherein for a complete traversal, a thread running on the query manager performs multiple requests to various shards during multiple waves corresponding to traversal levels, and wherein the thread will maintain all partial results until the traversal finishes and then return results to clients.

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.