Graph-based data models for partitioned data

Patent metadata

Field	Value
Publication number	US-9576071-B2
Application number	US-201314025657-A
Country	US
Kind code	B2
Filing date	Sep 12, 2013
Priority date	Sep 12, 2013
Publication date	Feb 21, 2017
Grant date	Feb 21, 2017

Abstract

The disclosed embodiments provide a system that manages access to data. During operation, the system provides a graph-based data model of the data, wherein the graph-based model comprises a set of nodes and a set of directed edges among the nodes. Next, the system stores the graph-based data model in a set of partitions, wherein each partition from the set of partitions includes one or more nodes from the set of nodes and all outgoing edges from the one or more nodes. Finally, the system enables lookup of a set of outgoing edges associated with a source node from the one or more nodes.

First claim

What is claimed is:

1. A computer-implemented method for managing access to data, the method comprising:
storing data structured according to a graph-based data model, wherein the structured data comprises a set of nodes and a set of directed edges among the set of nodes;
partitioning the structured data over a set of partitions, wherein each partition in the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges, in the set of directed edges, from the one or more nodes, wherein the set of partitions is distributed across two or more servers;
obtaining an identifier of a particular node of the set of nodes;
identifying a particular partition of the set of partitions based on the identifier; and
providing an answer to a lookup request by searching the outgoing edges from the particular node in the particular partition.

2. The computer-implemented method of claim 1 ,
wherein partitioning the structured data over the set of partitions includes storing all data, of the structured data, associated with a single user in a single partition of the set of partitions.

3. The computer-implemented method of claim 1 , further comprising automatically caching queries that access the structured data, so that queries that read data can add to a cache while queries that write data can invalidate entries in the cache.

4. The computer-implemented method of claim 1 , further comprising:
searching the outgoing edges to identify a set of content items that are associated with a single user.

5. The computer-implemented method of claim 1 , further comprising:
locking the particular node and the outgoing edges from the particular node during a transaction; and
unlocking the particular node and the outgoing edges after the transaction is complete.

6. The computer-implemented method of claim 1 , further comprising:
rolling back the structured data to a previous state of the particular node and the outgoing edges.

7. The computer-implemented method of claim 1 , further comprising:
searching the outgoing edges from the particular node by filtering the outgoing edges by an attribute associated with the outgoing edges.

8. The computer-implemented method of claim 1 , further comprising:
obtaining one or more destination nodes associated with one or more of the outgoing edges; and
searching one or more outgoing edges associated with the one or more destination nodes.

9. The computer-implemented method of claim 1 , wherein the particular node represents at least one of:
a user;
a collection;
an item;
a notification;
a group; and
a namespace.

10. The computer-implemented method of claim 1 , wherein the set of directed edges comprises:
a first directed edge from a first node, of the set of nodes, to a second node, of the set of nodes; and
a second directed edge from the second node to the first node.

11. A system for managing access to data, the system comprising:
one or more processors configured to:
store data structured according to a graph-based data model, wherein the structured data comprises a set of nodes and a set of directed edges among the set of nodes; and
partitioning the structured data over a set of partitions, wherein each partition in the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges, in the set of directed edges, from the one or more nodes, wherein the set of partitions is distributed across two or more servers;
obtain an identifier of a particular node of the set of nodes;
identify a particular partition of the set of partitions based on the identifier; and
provide an answer to a lookup request by searching the outgoing edges from the particular node in the particular partition.

12. The system of claim 11 ,
wherein the one or more processors are configured to store all data, of the structured data, associated with a single user in a single partition of the set of partitions.

13. The system of claim 11 , further comprising a cache for automatically caching queries that access the structured data, so that queries that read data can add to the cache while queries that write data can invalidate entries in the cache.

14. The system of claim 11 , wherein the one or more processors are further configured to:
lock the particular node and the outgoing edges during a transaction; and
unlock the particular node and the outgoing edges after the transaction is complete.

15. The system of claim 11 , wherein the one or more processors are further configured to:
search the outgoing edges by filtering the outgoing edges by an attribute associated with the outgoing edges.

16. The system of claim 11 , wherein the one or more processors are further configured to:
obtain one or more destination nodes associated with the outgoing edges; and
search one or more outgoing edges associated with the one or more destination nodes.

17. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for managing access to data, the method comprising:
storing data structured according to a graph-based data model, wherein the structured data comprises a set of nodes and a set of directed edges among the set of nodes;
partitioning the structured data over a set of partitions, wherein each partition in the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges, in the set of directed edges, from the one or more nodes, wherein the set of partitions are distributed across two or more servers; and
obtaining an identifier of a particular node of the set of nodes;
identifying a particular partition of the set of partitions based on the identifier; and
providing an answer to a lookup request by searching the outgoing edges from the particular node in the particular partition.

18. The non-transitory computer-readable storage medium of claim 17 , wherein partitioning the structured data over the set of partitions includes storing all data, of the structured data, associated with a single user in a single partition of the set of partitions.

Assignees

• Dropbox Inc

Inventors

• Metreveli Zviad
• Wable Akhil

Classifications

• G06F17/30896

  Physics · mapped topic

• G06F17/30584

  Physics · mapped topic

• G06F17/30958 Primary

  Physics · mapped topic

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/24552

  Database cache management · CPC title