METHOD OF SETTING UP A REDISTRIBUTION SCHEME OF A DIGITAL STORAGE SYSTEM

• US 20110258383A1
• Filed: 04/14/2011
• Published: 10/20/2011
• Est. Priority Date: 04/14/2010
• Status: Active Grant

• Current Assignee: Spotify AB (Spotify Technology SA)
• Original Assignee: Spotify Limited (Spotify Technology SA)
• Inventors: Schuller, Peter, Gannert, Tommie, De Zalenski, Matthias, Niemela, Fredrik, Kreitz, Gunnar
• Granted Patent: US 8,949,525 B2
• Time in Patent Office: Days
• 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 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 comprising;

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 a plurality 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.

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 the 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 the 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 and 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. A digital data storage system comprising:

a plurality of nodes;

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

wherein the storage system is adapted to redistribute the digital data packages 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.