GRAPH-BASED DATA MODELS FOR PARTITIONED DATA

• US 20150074044A1
• Filed: 09/12/2013
• Published: 03/12/2015
• Est. Priority Date: 09/12/2013
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Wable, Akhil, Metreveli, Zviad
• Granted Patent: US 9,576,071 B2
• Time in Patent Office: Days
• US Class Current: 707/609
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions

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.

Claims

1. A computer-implemented method for managing access to data, comprising:

providing 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;

storing the graph-based data model in a set of partitions, wherein each partition from the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges from the one or more nodes; and

providing an interface configured to lookup of a set of outgoing edges associated with a source node from the one or more nodes.

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

3. The computer-implemented method of claim 1, further comprising automatically caching queries that access the graph-based data model, 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:

updating the graph-based data model using a set of transactions.

5. The computer-implemented method of claim 4, wherein updating the graph-based data model using the set of transactions involves:

enabling locking of a node from the set of nodes and one or more outgoing edges associated with the node during a transaction associated with the node and an edge type of the one or more outgoing edges; and

enabling unlocking of the node and the one or more outgoing edges after the transaction is complete.

6. The computer-implemented method of claim 5, wherein updating the graph-based data model using the set of transactions further involves:

enabling rollback of the graph-based data model to a previous state of the node and the one or more outgoing edges.

7. The computer-implemented method of claim 1, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes involves:

identifying the partition comprising the source node; and

searching the outgoing edges by an identifier associated with the source node.

8. The computer-implemented method of claim 7, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes further involves:

filtering the outgoing edges by an attribute associated with the outgoing edges.

9. The computer-implemented method of claim 7, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes further involves:

obtaining one or more destination nodes associated with the outgoing edges; and

searching a set of additional outgoing edges associated with the one or more destination nodes.

10. The computer-implemented method of claim 1, wherein each node from the set of nodes is associated with at least one of:

a user;

a collection;

an item;

a notification;

a group; and

a namespace.

11. The computer-implemented method of claim 1, wherein the set of directed edges comprises:

a first directed edge from a first node to a second node; and

a second directed edge from the second node to the first node.

12. A system for managing access to data, comprising:

a modeling apparatus configured to;

provide 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; and

store the graph-based data model in a set of partitions, wherein each partition from the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges from the one or more nodes; and

an interface with the modeling apparatus, wherein the interface is configured to lookup a set of outgoing edges associated with a source node from the one or more nodes.

13. The system of claim 12, wherein the modeling apparatus is configured to store all data associated with a single user in a single partition.

14. The system of claim 12, further comprising a cache for automatically caching queries that access the graph-based data model, so that queries that read data can add to the cache while queries that write data can invalidate entries in the cache.

15. The system of claim 12, wherein the modeling apparatus and the interface are further configured to update the graph-based data model using a set of transactions by:

enabling locking of a node from the set of nodes and one or more outgoing edges associated with the node during a transaction associated with the node and an edge type of the one or more outgoing edges;

enabling unlocking of the node and the one or more outgoing edges after the transaction is complete; and

enabling rollback of the graph-based data model to a previous state of the node and the one or more outgoing edges.

16. The system of claim 12, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes involves:

identifying the partition comprising the source node; and

searching the outgoing edges by an identifier associated with the source node.

17. The system of claim 16, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes further involves:

filtering the outgoing edges by an attribute associated with the outgoing edges.

18. The system of claim 16, wherein enabling lookup of the set of outgoing edges associated with a source node from the one or more nodes further involves:

obtaining one or more destination nodes associated with the outgoing edges; and

searching a set of additional outgoing edges associated with the one or more destination nodes.

19. A 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:

providing 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;

storing the graph-based data model in a set of partitions, wherein each partition from the set of partitions comprises one or more nodes from the set of nodes and all outgoing edges from the one or more nodes; and

providing an interface configured to lookup of a set of outgoing edges associated with a source node from the one or more nodes.

20. The computer-readable storage medium of claim 19, wherein storing the graph-based data model in the set of partitions includes storing all data associated with a single user in a single partition.