System and method for performing shard migration to support functions of a cloud-based service

• US 9,792,320 B2
• Filed: 07/08/2013
• Issued: 10/17/2017
• Est. Priority Date: 07/06/2012
• Status: Active Grant

• Current Assignee: Box Incorporated
• Original Assignee: Box Incorporated
• Inventors: Bercovici, Tamar, Jourda, Florian, Trombley-Shapiro, Benjamin
• Primary Examiner(s): LIN, SHEW FEN
• Application Number:
  US13/937,060
• Publication Number:
  US 20140012814A1
• Time in Patent Office: 1,562 Days
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation

Abstract

Systems and methods of maintaining a horizontally scaled database based on data ownership for a cloud-based platform (e.g., cloud-based collaboration and/or storage platform/service) are disclosed. The system database comprises multiple shard databases, and all files and folders owned by a user are stored on a single shard database. When a user transfers ownership of a file and/or a folder to a second user, the transferred file and/or folder is stored on the shard database that stores all of the data for the second user.

Claims

1. A method of database partitioning within a collaborative environment hosted by a cloud-based platform, the method comprising:

partitioning a database into multiple shard databases based upon ownership of one or more objects stored in the database, wherein the one or more objects are stored within a given one of the multiple shard databases based upon an association of the one or more objects with a user identification;

mapping within a mapping database, a first user identification to a first shard database and a second user identification to a second shard database, wherein the mapping database, the first shard database, and the second shard database are associated with the cloud-based platform that supports collaboration between a first user having the first user identification and a second user having the second user identification;

providing, via the cloud-based platform, to the second user, access to a collaboration folder that is owned by the first user, wherein the collaboration folder is located in the first shard database, wherein the collaboration folder is identifiable by a parent folder and a path that indicates a location of the collaboration ion folder within a folder tree;

receiving a request to transfer the association of the one or more objects and the collaboration folder from the first user identification to the second user identification;

migrating ownership of the one or more objects and the collaboration folder from the first shard database of the cloud-based platform to the second shard database of the cloud-based platform,

wherein the migrating includes migrating the collaboration folder and one or more folders stored within the collaboration folder;

inserting an access lock on the one or more objects and the collaboration folder in the mapping database, the first shard database, and the second shard database;

updating a status of the one or more objects and a status of the collaboration folder in the mapping database to point to the second shard database;

moving the one or more objects and the collaboration folder from the first shard database associated with the first user identification to the second shard database associated with the second user identification;

deleting the one or more objects and the collaboration folder from the first shard database; and

releasing the access lock on the one or more objects and the collaboration folder in the second shard database, the mapping database, and the first shard database.

2. The method of claim 1, wherein at least a subset of users of the database are associated with an enterprise account provided by a cloud-based platform, and further wherein the one or more objects associated with the subset of users are stored in the single shard database.

3. The method of claim 2, further comprising:

permitting an administrator of the enterprise account to query database objects associated with the subset of users associated with the enterprise account.

4. The method of claim 1, further comprising:

receiving a database-related request for a first object, the first object included in the one or more objects;

upon determining that the database-related request involves transfer of association of the first object from the first user identification to the second user identification, identifying a third shard database that stores objects associated with the first user identification and a fourth shard database that stores objects associated with the second user identification, wherein the third shard database and the fourth shard database are included in the multiple shard databases;

moving the first object from the third shard database to the fourth shard database, upon determining that the third shard database is different from the fourth shard database; and

updating the mapping database to reflect the movement of the first object to the fourth shard database.

5. The method of claim 4, wherein determining that the database-related request involves transfer of association includes:

identifying a field of the database-related request as a mapping key used by the mapping database to identify a shard database included in the multiple shard databases that stores the first object.

6. The method of claim 4, wherein the first object is a folder, the method further comprising:

determining one or more objects stored within the first object;

moving the one or more objects stored within the first object to the fourth shard database, upon determining the third shard database is different from the fourth shard database.

7. The method of claim 6, wherein determining that the one or more objects are stored within the first object comprises using a prefix query with the first object.

8. The method of claim 6, wherein a parent for the folder and a path for the folder are stored for use in responding to the prefix query.

9. The method of claim 1, further comprising:

receiving a database-related request for a second object;

upon determining that the database-related request does not involve transfer of association of the second object, executing the database-related request.

10. The method of claim 9, wherein the determining that the database-related request does not involve transfer of association comprises determining that fields of the database-related request do not include a mapping key, wherein the mapping key is used with the mapping database to determine in which one of the multiple shard databases a particular object is stored.

11. The method of claim 10, wherein the multiple shard databases are used to store data for a cloud-based platform.

12. The method of claim 1, wherein the one or more objects stored in the database have a single owner.

13. A method of performing shard migration within a collaborative environment hosted by a cloud-based platform, the method comprising:

mapping within a mapping database, a first user identification to a first shard database and a second user identification to a second shard database, wherein the mapping database, the first shard database, and the second shard database are associated with the cloud-based platform that supports collaboration between a first user having the first user identification and a second user having the second user identification, wherein one or more objects are stored in the first shard database and associated with the first user identification;

receiving a request that involves change of association of the one or more items stored in one of multiple shard databases in the cloud-based platform;

providing, via the cloud-based platform, to the second user, access to a collaboration folder that is owned by the first user, wherein the collaboration folder is located in the first shard database, wherein the collaboration folder is identifiable by a parent folder and a path that indicates a location of the collaboration folder within a folder tree;

migrating ownership of the one or more objects and the collaboration folder from the first shard database of the cloud-based platform to the second shard database of the cloud-based platform,

wherein the migrating includes migrating the collaboration folder and one or more folders stored within the collaboration folder; and

moving the one or more items and the collaboration folder from a source shard database associated with a first user identification to a destination shard database associated with a second user identification

updating a status of the one or more items and a status of the collaboration folder in the mapping database to point to the destination shard database;

inserting the one or more items and the collaboration folder from the source shard database into the destination shard database;

deleting the one or more items and the collaboration folder from the source shard database.

14. The method of claim 13, wherein access to the one or more items in the source shard database, the mapping database, and the destination shard database are locked while moving the one or more items.

15. The method of claim 13, further comprising:

upon determining that there is a problem with moving the one or more items from the source shard database to the destination shard database, reinstating a state of the mapping database, the source shard database, and the destination shard database to a state prior to the moving of the one or more items.

16. The method of claim 13, wherein the multiple shard databases are used to store the items for collaboration via the cloud-based platform.

17. The method of claim 13, wherein each of the one or more items stored in the multiple shard databases has a single owner.

18. A system for performing shard migration to support functions of a cloud-based platform, the system comprising:

a processor;

a memory having stored thereon instructions which, when executed by the processor, causes the system to;

map, within a mapping database, a first user identification to a first shard database and a second user identification to a second shard database, wherein the mapping database, the first shard database, and the second shard database are associated with the cloud-based platform that supports collaboration between a first user having a first user identification and a second user having a second user identification, wherein one or more objects are stored in the first shard database and associated with the first user identification;

receive a request that involves change of association of the one or more objects stored in one of multiple shard databases;

provide, via the cloud-based platform, to the second user, access to a collaboration folder that is owned by the first user, wherein the collaboration folder is located in the first shard database, wherein the collaboration folder is identifiable by a parent folder and a path that indicates a location of the collaboration folder within a folder tree;

migrate ownership of the one or more objects and the collaboration folder from the first shard database of the cloud-based platform to the second shard database of the cloud-based platform,

wherein the migrating includes migrating the collaboration folder and one or more folders stored within the collaboration folder;

move the one or more objects and the collaboration folder from a source shard database associated with a first user identification to a destination shard database associated with a second user identification, wherein upon the move the one or more objects appear in the destination shard database and are removed from the source shard database; and

update a status of the one or more objects and a status of the collaboration folder in the mapping database to point to the destination shard database.

19. The system of claim 18, wherein moving the one or more objects comprises:

inserting the one or more objects from the source shard database into the destination shard database; and

deleting the one or more objects from the source shard database.

20. The system of claim 19, wherein the system is further caused to:

lock access to the source shard database, the mapping database, and the destination shard database while moving the one or more objects.

21. The system of claim 18, wherein the system is further caused to:

upon encountering a problem with moving the one or more objects from the source shard database to the destination shard database, return the mapping database, the source shard database, and the destination shard database to a state prior to the moving of the one or more objects.

22. A non-transitory machine-readable storage medium having stored thereon instructions which, when executed by a processor, cause the processor to:

partition a database into multiple shard databases based upon ownership of objects stored in the database, wherein the objects are stored within one of the multiple shard databases based upon an association of the objects with a user identification, wherein the user identification uniquely corresponds to a single shard database in the multiple shard databases;

map, within a mapping database, a first user identification to a first shard database and a second user identification to a second shard database, wherein the mapping database, the first shard database, and the second shard database are associated with a cloud-based platform that supports collaboration between a first user having the first user identification and a second user having the second user identification, wherein the one or more objects are stored in the first shard database and associated with the first user identification;

provide, via the cloud-based platform, to the second user, access to a collaboration folder that is owned by the first user, wherein the collaboration folder is located in the first shard database, wherein the collaboration folder is identifiable by a parent folder and a path that indicates a location of the collaboration folder within a folder tree;

receive a request to transfer the association of the objects and the collaboration folder from the first user identification to the second user identification; and

migrate ownership of the one or more objects and the collaboration folder from the first shard database of the cloud-based platform to the second shard database of the cloud-based platform,

wherein the migrating includes migrating the collaboration folder and one or more folders stored within the collaboration folder;

move the one or more objects and the collaboration folder from the first shard database associated with the first user identification to the second shard database associated with the second user identification, wherein upon the move, the one or more objects appear in the second shard database and are removed from the first shard database; and

update a status of the one or more objects and a status of the collaboration folder in the mapping database to point to the second shard database.

23. The non-transitory machine-readable storage medium of claim 22, wherein the instructions further cause the processor to:

maintain a key in the mapping database, wherein the key maps the objects stored in the database to the multiple shard databases.

24. The non-transitory machine-readable storage medium of claim 22, wherein the instructions further cause the processor to:

receive a request pertaining to a first database object, the first database object included in the objects;

upon determining that the request involves transfer of association of the first database object from a first user to a second user, identifying a third shard database that stores objects associated with the first user and a fourth shard database that stores objects associated with the second user;

moving the first database object from the third shard database to the fourth shard database, upon determining that the third shard database is different from the fourth shard database; and

updating the mapping database to reflect the movement of the first object to the fourth shard database.

25. The non-transitory machine-readable storage medium of claim 24, wherein the first database object is a folder, and wherein the instructions further cause the processor to:

determine one or more objects stored within the first database object;

move the one or more database objects stored within the first database object to the fourth shard database, upon determining that the third shard database is different from the fourth shard database.

26. The non-transitory machine-readable storage medium of claim 22, wherein the instructions further cause the processor to:

receive a request pertaining to a second database object;

upon determining that the request does not involve transfer of association of the second database object, execute the request.

27. An apparatus for performing shard migration for a cloud-based collaboration platform, the apparatus performing the operations of:

a memory having stored thereon instructions and coupled to a processor;

the processor configured for;

mapping, based on mapping metadata, a user identification to a shard database included in multiple databases that store one or more items based upon an association of the one or more items with the user identification, wherein the user identification uniquely corresponds to a single shard database in the multiple shard databases, wherein the mapping metadata identifies a first user having a first user identification and a second user having a second user identification, wherein the one or more items are stored in the first shard database and associated with the first user identification;

receiving a request and determining whether the request involves a change of association of one or more items in the cloud-based collaboration platform; and

providing, via the cloud-based collaboration platform, to the second user, access to a collaboration folder that is owned by the first user, wherein the collaboration folder is located in a first shard database, wherein the collaboration folder is identifiable by a parent folder and a path that indicates a location of the collaboration folder within a folder tree, wherein the first shard database and the second shard database are included in the multiple databases;

migrating ownership of the one or more items and the collaboration folder from the first shard database of the cloud-based collaboration platform to the second shard database of the cloud-based collaboration platform, wherein the migrating includes migrating the collaboration folder and one or more folders stored within the collaboration folder; and

moving the one or more items and the collaboration folder from the first shard database of the cloud-based collaboration platform to the second shard database of the cloud-based collaboration platform responsive to the request wherein the second shard database is different from the first shard database; and

updating the mapping metadata that maps the one or more items and the collaboration folder in the cloud-based collaboration platform to the user identification for determining whether the first shard database or the second shard database stores the one or more items.

28. The apparatus of claim 27, further performing the operations of:

executing the request upon determining that the request does not involve a change of association in the cloud-based collaboration platform.