Graph-based data models for partitioned data

Patent metadata

Field	Value
Publication number	US-10740319-B2
Application number	US-201816039651-A
Country	US
Kind code	B2
Filing date	Jul 19, 2018
Priority date	Sep 12, 2013
Publication date	Aug 11, 2020
Grant date	Aug 11, 2020

Abstract

A method and system for managing access to data. A plurality of data items is stored across a plurality of partitions according to a graph-based data model. The data model associates each data item with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity. When a lookup request is received identifying a source entity and a type of directed relationship from the source entity, a particular partition is identified based on the source entity identifier. A response to the lookup request is then returned that includes data item(s) from the identified partition that are associated in the partition with both the identified source entity identifier and the identified directed relationship type.

First claim

The invention claimed is:

1. A method of managing access to data, comprising:
at one or more computer systems comprising processors, memory, and storage:
storing a plurality of data items across a plurality of partitions of a database of the plurality of data items;
wherein the storing is according to a graph-based data model that associates each data item of the plurality of data items with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity;
wherein the plurality of partitions is stored across a plurality of physical machines;
wherein each partition of the plurality of partitions comprises a respective subset of data items of the plurality of data items;
receiving a lookup request specifying an identifier of a particular source entity and an identifier of a particular type of directed relationship from the particular source entity;
based on the identifier of the particular source entity specified in the lookup request, identifying a particular partition of the plurality of partitions; and
returning a response to the lookup request, the response comprising data items, of the plurality of data items stored across the plurality of partitions, each of the data items of the response both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship.

2. The method of claim 1 , wherein the particular source entity is a user having a user account with an online content management system; and wherein each data item, of the data items returned in the response, identifies a different collection of content items, under management of the online content management system, to which the user having the user account has permission to access.

3. The method of claim 1 , wherein the particular source entity is a collection of content items under management of an online content management system; and wherein each data item, of the data items returned in the response, identifies a different user having a user account, with the online content management system, that has permission to access the collection of content items.

4. The method of claim 1 , wherein each data item, of the data items returned in the response, represents permissions that a particular user having a user account with an online content management system has with respect to a different collection of content items under management of the online content management system, the particular user identified by the identifier of the particular source entity, the different collection of content items identified by the each data item.

5. The method of claim 1 , wherein each data item, of the data items returned in the response, represents permissions that a different user having a user account with an online content management system has with respect to a particular collection of content items under management of the online content management system, the particular collection of content items identified by the identifier of the particular source entity, the different user having a user account identified by the each data item.

6. The method of claim 1 , wherein:
the lookup request is a first lookup request;
the response is a first response;
the method further comprises: receiving a second lookup request specifying the identifier of the particular source entity, an identifier of a particular destination entity, and the identifier of the particular type of directed relationship; responsive to receiving the second lookup request, identifying, based on the identifier of the particular source entity specified in the second lookup request, the particular partition of the plurality of partitions; and returning a second response to the second lookup request, the second response comprising a particular data item that is both: (a) stored in the particular partition; and (b) associated in the particular partition, according to the graph-based data model, with all of: (b1) the identifier of the particular source entity, (b2) the identifier of the destination entity, and (b3) the identifier of the type of directed relationship.

7. The method of claim 1 , wherein the particular source entity corresponds to a node in the graph-based data model and the particular type of directed relationship corresponds to a directed edge from the node in the graph-based data model.

8. The method of claim 1 , wherein at least one data item of the data items returned in the response is obtained from a cache of data items.

9. The method of claim 1 , further comprising:
storing a plurality of slave partitions corresponding to the plurality of partitions.

10. An online content management system comprising:
one or more processors;
one or more computer-readable media storing one or more computers programs, the one or more computer programs configured for:
storing a plurality of data items across a plurality of partitions of a database of the plurality of data items;
wherein the storing the plurality of data items is according to a graph-based data model that associates each data item of the plurality of data items with an identifier of a source entity pertaining to the data item, an identifier of a destination entity pertaining to the data item, and an identifier of a type of directed relationship pertaining to the data item from the source entity to the destination entity;
wherein the plurality of partitions is stored across a plurality of physical machines;
wherein each partition of the plurality of partitions comprises a respective subset of data items of the plurality of data items;
receiving a first lookup request specifying an identifier of a particular source entity, an identifier of a particular destination entity, and an identifier of a particular type of directed relationship from the particular source entity to the particular destination entity;
based on the identifier of the particular source entity specified in the first lookup request, identifying a particular partition of the plurality of partitions;
returning a first response to the first lookup request, the first response comprising a particular data item that is both: (a) stored in the particular partition; and (b) associated, according to the graph-based data model, with all of: (b1) the identifier of the particular source entity, (b2) the identifier of the particular destination entity, and (b3) the identifier of the particular type of directed relationship;
receiving a second lookup request specifying the identifier of the particular source entity and the identifier of the particular type of directed relationship;
based on the identifier of the particular source entity specified in the second lookup request, identifying the partition of the plurality of partitions; and
returning a second response to the second lookup request, the second response comprising data items, of the plurality of data items stored across the plurality of partitions, each of the data items of the second response both: (a) stored in the particular partition; and (b) associated, according to the graph-based data model, with at least both: (b1) the identifier of the particular source entity and (b2) the identifier of the particular type of directed relationship.

11. A system for managing access to data, the system comprising:
one or more processors;
one of more computer-readable media storing one or more sets of instructions configu

Assignees

• Dropbox Inc

Inventors

• Metreveli Zviad
• Wable Akhil

Classifications

• G06F16/278 Primary

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

• G06F16/2343 Primary

  Locking methods, e.g. distributed locking or locking implementation details · CPC title

• G06F16/9024

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

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/24552

  Database cache management · CPC title