Distributed graph database

Patent metadata

Field	Value
Publication number	US-2017091246-A1
Application number	US-201615154370-A
Country	US
Kind code	A1
Filing date	May 13, 2016
Priority date	Sep 25, 2015
Publication date	Mar 30, 2017
Grant date	—

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 low latency 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 media and executed on a processor to implement a graph data model, the graph data model being mapped to the one or more data structures.

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 low latency 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 low latency 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 based at least in part on the data structure; receiving a transaction to be executed against the graph; and using remote direct memory access (RDMA) to execute the transaction against the graph.

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 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 a 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 . 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 generated based at least in part on the data structure associated with the shared transactional memory.

18 . A system as claim 17 recites, wherein the shared transactional memory is configured to:
receive a transaction to be executed against a graph of the one or more graphs; and
utilize the RDMA to execute the transaction against the graph.

19 . A system as claim 18 recites, wherein the shared transactional memory implements efficient non-uniform memory access (NUMA)-aware multiplexing to improve execution of the transaction against the graph.

20 . A system as claim 17 recites, wherein the shared transactional memory comprises a petabyte transactional memory storage layer.

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/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/182

  Distributed file systems · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title