Method of setting up a redistribution scheme of a digital storage system

• US 8,949,525 B2
• Filed: 04/14/2011
• Issued: 02/03/2015
• Est. Priority Date: 04/14/2010
• Status: Active Grant

• Current Assignee: Spotify AB (Spotify Technology SA)
• Original Assignee: Spotify AB (Spotify Technology SA)
• Inventors: Niemela, Fredrik, Kreitz, Gunnar, Gannert, Tommie, Schuller, Peter, deZalenski, Matthias
• Primary Examiner(s): Rigol, Yaima
• Assistant Examiner(s): Waddy, Jr., Edward
• Application Number:
  US13/086,427
• Publication Number:
  US 20110258383A1
• Time in Patent Office: 1,391 Days
• Field of Search: 711/165, 711/114, 711/162, 711/163, 711/170, 711/E12.002, 711/E12.103, 711/E12.019, 711/103, 711/E12.001, 711/112, 711/173, 711/141, 711/154, 711/157, 711/164, 707/807, 707/E17.005, 707/E17.032, 707/610, 707/E17.007, 707/650, 707/673, 707/E17.044, 707/640, 707/655, 707/667, 707/999.202, 717/177
• US Class Current: 711/114
• CPC Class Codes: G06F 16/214 Database migration support

Abstract

A method of setting up a redistribution scheme for redistributing digital data packages within a digital data storage system comprising a plurality of nodes, wherein the data packages are associated with respective keys and are distributed among the nodes according to a first distribution configuration within the digital data storage system. The method includes: determining a second distribution configuration, in accordance with which it is intended to redistribute the data packages; applying a migration function to the respective keys of each of the data packages, which function yields a migration value associated with each of the data packages; and assigning a migration time to each of the data packages based on its associated migration value, at which times it is intended to migrate the respective data packages to conformity with the second distribution configuration. A corresponding digital data storage system is described.

Claims

1. A method of setting up a redistribution scheme for redistributing digital data packages within a digital data storage system comprising

providing, at a plurality of nodes, a plurality of data packages,

wherein each data package is associated with a respective key that identifies its associated data package, and

wherein the plurality of data packages are originally distributed among the nodes according to a first distribution configuration;

determining a second distribution configuration, in accordance with which second distribution configuration the plurality of data packages are to be redistributed, during a transition period, among the plurality of nodes;

applying a migration function to the respective keys of each of the plurality of data packages, to determine, for each data package, a migration value associated with that data package; and

assigning, to each of the plurality of data packages, a migration time within the transition period, based on its associated migration value, at which times the respective data packages are to be migrated within those of the plurality of nodes indicated by the second distribution configuration, to be in conformity with the second distribution configuration, so that,

upon receiving a request for a particular data package

the key of the requested data package is used to determine the migration time for the particular data package,

the particular data package'"'"'s migration time is used to determine which of the first or the second distribution configurations should be used to locate the particular data package, and

the request is one of processed at a node receiving the request, or forwarded to another of the nodes, based on the determined distribution configuration and the location of the particular data package within the plurality of nodes.

2. The method of claim 1 wherein the migration values set the order in which the data packages should be migrated according to the scheme, and the migration times are assigned accordingly.

3. The method of claim 2 wherein the data packages are stored in a table distributed over the nodes of the storage system such that each of the keys can be mapped to its corresponding data package by applying a mapping function to said key;

wherein the mapping function is different than the migration function.

4. The method of claim 3 wherein the order in which the data packages should be migrated according to the scheme is different from the order in which the data packages are stored in the table distributed over the nodes of the storage system.

5. The method of claim 2 wherein the order in which the data packages should be migrated according to the scheme is different from the order in which the data packages are stored in a table distributed over the nodes of the storage system.

6. The method of claim 1 wherein the order in which the data packages should be migrated according to the scheme is different from the order in which the data packages are stored in a table distributed over the nodes of the storage system.

7. The method of claim 1 wherein the storage system is a Distributed Hash Table (DHT).

8. The method of claim 1 wherein the nodes are geographically dispersed over a plurality of continents.

9. The method of claim 1 wherein the storage system is a Redundant Array of Independent Disks (RAID) or Just a Bunch of Disks (JBOD).

10. The method of claim 1 wherein the migration time is one of

a time of day, or

an output of a controllable counter.

11. The method of claim 1 wherein the migration function is a hash function.

12. The method of claim 1 wherein the first distribution configuration is associated with a first node configuration, and the second distribution configuration is associated with a second node configuration which is different from the first node configuration.

13. The method of claim 1 further comprising migrating a plurality of the data packages, distributed according to the first distribution configuration, to conformity with the second distribution configuration based on their respective assigned migration times.

14. The method of claim 13 wherein the plurality of the data packages distributed according to the first distribution configuration are migrated such that they are each copied, and the copies are each migrated in accordance with the second distribution configuration before or at the migration time assigned to the respective data packages;

wherein each of the migrated data package copies are allowed to coexist with its corresponding data package of the first distribution configuration during a transitional period before the data package of the first distribution configuration is deleted.

15. The method of claim 1 further comprising looking up one of the data packages by:

applying the migration function to the key of said data package;

determining from the redistribution scheme whether the migration time assigned to said data package is in the past or in the future; and

in response to determining that the migration time assigned to said data package is in the future, using the first distribution configuration for lookup;

in response to determining that the migration time assigned to said data package is in the past, using the second distribution configuration for lookup.

16. The method of claim 1 wherein the migration function is dependent on a starting time of the migration according to the redistribution scheme.

17. The method of claim 1 wherein the data packages are stored in a table distributed over the nodes of the storage system such that each of the keys can be mapped to its corresponding data package by applying a mapping function to said key;

wherein the mapping function is different than the migration function.

18. The method of claim 1, wherein the second distribution configuration includes one or more additional nodes in addition to those nodes indicated by the first distribution configuration, and wherein, during the transition period, the respective data packages are migrated within those nodes represented by the second distribution configuration including the one or more additional nodes.

19. The method of claim 1, further comprising applying the migration function to the respective keys of the plurality of data packages, to distribute those data packages according to the second distribution configuration, including within one or more additional nodes, to accommodate changes in the nodes and load balancing of requests for those data packages.

20. A digital data storage system comprising:

a plurality of nodes;

wherein a plurality of data packages are associated with respective keys and are originally distributed among the nodes according to a first distribution configuration within the digital data storage system;

wherein the storage system is adapted to redistribute the data packages, during a transition period, to conformity with a second distribution configuration within the storage system by migrating the data packages at respective migration times assigned to the data packages based on respective migration values associated with the data packages by

applying a migration function to the respective keys of each of the data packages to determine, for each data package, a migration value associated with that data package, and

assigning, to each of the plurality of data packages, a migration time within the transition period, based on its associated migration value, at which times the respective data packages are to be migrated within those of the plurality of nodes indicated by the second distribution configuration, to be in conformity with the second distribution configuration, so that,

upon receiving a request for a particular data package

the key of the requested data package is used to determine the migration time for the particular data package,

the particular data package'"'"'s migration time is used to determine which of the first or the second distribution configurations should be used to locate the particular data package, and

the request is one of processed at a node receiving the request, or forwarded to another of the nodes, based on the determined distribution configuration and the location of the particular data package within the plurality of nodes.