Distributed graph database

Patent metadata

Field	Value
Publication number	US-10810179-B2
Application number	US-201615154370-A
Country	US
Kind code	B2
Filing date	May 13, 2016
Priority date	Sep 25, 2015
Publication date	Oct 20, 2020
Grant date	Oct 20, 2020

Abstract

A distributed graph database that enables scaling and efficient processing is described. The distributed graph database can, for example, scale up to petabytes of data to enable transactional processing of graph data with low latency and low processing overhead. The distributed graph database can include a cluster of devices and a remote direct memory access (RDMA)-based communication layer to perform low latency messaging between devices of the cluster of devices. Additionally, the distributed graph database can include a shared memory layer that provides one or more data structures, a transaction layer to facilitate query processing, and a graph database layer stored in computer-readable media and executed on a processor to implement a graph data model. In at least one example, the graph data model can be mapped to the one or more data structures.

First claim

We claim:

1. A system comprising:
a cluster of devices;
a remote direct memory access (RDMA)-based communication layer to perform messaging between devices of the cluster of devices; a shared memory layer that provides one or more data structures;
a transaction layer that can be used to perform query processing; and
a graph database layer stored in computer-readable storage media and executed on a processor to implement a graph data model of data structure objects, the graph data model being mapped to the one or more data structures, wherein a respective data structure object of the data structure objects is stored in a first device of the cluster of devices and is uniquely identified by a pointer accessible to the transaction layer, the pointer including an incarnation for the respective data structure object;
wherein the graph data model and the pointer is stored at a second device of the cluster of devices;
wherein the respective data structure object located on the first device is verified as valid based on the incarnation for the respective data structure object; and
wherein the transaction layer is configured to identify that a data structure object of the graph data model is located on the first device using the graph data model and the pointer stored at the second device, and process a query from the second device related to the data structure object on the first device after the data structure object is located on the first device using the pointer.

2. A system as claim 1 recites, wherein the RDMA-based communication layer further performs replication of memory regions between the devices of the cluster of devices without involving processors associated with the devices of the cluster of devices.

3. A system as claim 1 recites, wherein the one or more data structures include at least one of a b-tree, a hash table, a linked list, or a catalog.

4. A system as claim 3 recites, wherein the hash table utilizes a changed associative hopscotch hashing algorithm to balance space efficiency and a size and a number of RDMAs used to perform the messaging between the devices.

5. A system as claim 3 recites, wherein the b-tree utilizes fence keys to perform lock-free reads for reducing a size and a number of RDMAs used to perform the messaging between the devices.

6. A system as claim 3 recites, wherein the b-tree provides a key-value store that iterates over a range.

7. A system as claim 1 recites, wherein the graph data model comprises:
a plurality of vertices; and
one or more directed edges each connecting pairs of vertices of the plurality of vertices.

8. A system as claim 1 recites, further comprising a co-processor layer, the co-processor layer comprising at least one of a trusted co-processor, an untrusted hosted co-processor, or an untrusted frontend-hosted co-processor.

9. A method comprising:
distributing a data structure across a cluster of devices in a shared transactional memory layer;
generating a graph of data structure objects based at least in part on the data structure, wherein a respective data structure object of the data structure objects is stored in a first device of the cluster of devices and is uniquely identified by a pointer accessible to the shared transactional memory layer, the pointer including an incarnation for the respective data structure object;
storing the graph and the pointer at a second device;
receiving a transaction to be executed against a data structure object of the graph;
identifying, at the second device, that the data structure object is located on the first device using the graph and the pointer stored at the second device;
verifying that the data structure object located on the first device is valid based on the incarnation for the respective data structure object; and
using remote direct memory access (RDMA) to execute the transaction from the second device against the data structure object of the graph on the first device after identifying the data structure object is located on the first device using the pointer.

10. A method as claim 9 recites, wherein the data structure is at least one of a hash table, a b-tree, a linked list, or a catalog.

11. A method as claim 9 recites, wherein the graph comprises:
a plurality of vertices; and
one or more directed edges, wherein a directed edge connects a first vertex of the plurality of vertices to a second vertex of the plurality of vertices.

12. A method as claim 11 recites, wherein the plurality of vertices and the one or more directed edges are mapped to the data structure.

13. A method as claim 9 recites, wherein:
the transaction comprises a query; and
the method further comprises executing the transaction based at least in part on a breath-first-search query.

14. A method as claim 13 recites, wherein the breath-first-search query comprises:
accessing a node of the graph; and
iteratively processing a plurality of nodes around the node to determine characteristics that match the node.

15. A method as claim 9 recites, wherein distributing the data structure across the cluster of devices comprises distributing the data structure objects according to a locality principle.

16. A method as claim 15 recites, wherein distributing the data structure objects according to the locality principle comprises:
based at least in part on determining that the data structure object of the data structure objects can be placed in a same region as another data structure object, placing the data structure object within the same region as the other data structure object;
based at least in part on determining that it is not possible to place the data structure object within the same region as the other data structure object, placing the data structure object within a same device as the other data structure object; and
based at least in part on determining that it is not possible to place the data structure object within the same device as the other data structure object, placing the data structure object within a device on a same physical rack as a device in which the other data structure object is located.

17. The method of claim 9 , wherein the transaction is sent from the second device to the first device for execution at the first device.

18. The method of claim 9 , wherein the data structure object is sent from the first device to the second device and wherein the transaction is executed at the second device after the data structure object is received at the second device.

19. A system comprising:
a cluster of devices, wherein individual devices of the cluster of devices include:
one or more processors;
a portion of a shared transactional memory associated with the cluster of devices, the portion of the shared transactional memory including a portion of a data structure that is distributed across the cluster of devices and is accessible by the cluster of devices via remote direct memory access (RDMA) reads; and
a local memory that stores one or more graphs of data structure objects generated based at least in part on the data structure associated with the shared transactional memory;
wherein a respective data structure object of the data structure objects is stored in a first device of the cluster of devices and is uniquely identified by a pointer accessible to the shared transactional memory, the pointer including an incarnation for the respective data structure object;
wherein a graph of the one or more graphs and the pointer is stored at a second device of the cluster of devices;
wherein a data structure obje

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Risvik Knut Magne
• Wu Ming-Chuan
• Narayanan Dushyanth
• Renzelmann Matthew
• Shamis Alexander
• De Castro Miguel Oom Temudo
• Dragojevic Aleksandar
• Buragohain Chiranjeeb
• Khanna Richendra
• Tan Timothy

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/182

  Distributed file systems · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/2471

  Distributed queries · CPC title

• G06F16/25

  Integrating or interfacing systems involving database management systems · CPC title