Allocation and redistribution of data among storage devices

• US 20080288563A1
• Filed: 05/14/2008
• Published: 11/20/2008
• Est. Priority Date: 05/14/2007
• Status: Abandoned Application

• Current Assignee: Dataupia Corp.
• Original Assignee: Dataupia Corp.
• Inventors: Hinshaw, Foster D., Bingham, Timothy J., Potter, Alan, Harris, Craig S.
• Application Number:
  US12/152,419
• Publication Number:
  US 20080288563A1
• Time in Patent Office: Days
• US Class Current: 707/205
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Distributing and redistributing records among a changing set of storage devices is accomplished by grouping the records based on the starting and ending numbers of storage devices.

Claims

1. A method of allocating a set of data records among a plurality of data storage devices in a data storage system, the method comprising:

defining a series of group values based on the number of devices;

assigning each group value to a substantially equal number of the data records;

assigning each group value to one of the devices in the system;

storing each of the data records on the device having a group value corresponding to the group value of the data record; and

when the number of storage devices changes, re-allocating some of the records among storage devices based on the group values.

2. The method of claim 1 further comprising:

defining a record allocation table comprising a plurality of cells, each cell representing an intersection of one of N rows and M columns, wherein N equals a maximum possible number of storage devices in the system and M equals the lowest common multiple of a series of numbers from 1 to N;

assigning one of the group values in the series to each cell; and

when the number of storage devices changes, the re-allocating step is performed based on the table.

3. The method of claim 2 wherein the number of re-allocated records corresponds to an amount of storage added or subtracted due to the change in the number of storage devices.

4. The method of claim 2 wherein the number of storage devices corresponds to a row in the table, the step of re-allocating the records comprising:

selecting the row of the table corresponding to the changed number of storage devices;

distributing the group values in the selected row among the data records so that some of the data records have new group values; and

storing the data records having new group values on the devices corresponding thereto.

5. The method of claim 2 wherein the cell values are calculated at runtime.

6. The method of claim 1 wherein a plurality of group values may be assigned to a single storage device.

7. The method of claim 1 wherein all data records corresponding to a group value may be moved to a single storage device.

8. The method of claim 1 wherein each of the records has a field value and the group values are assigned to the records based at least in part on the field values.

9. The method of claim 8 wherein the field values are mapped to the group values by means of a hash function.

10. The method of claim 9 wherein the hash function is a Pearson hash.

11. The method of claim 1 wherein the data records are distributed among the storage devices within a predetermined variance from a perfectly even distribution.

12. The method of claim 11 wherein the variance is 10% or less.

13. The method of claim 12 wherein the variance is 1% or less.

14. A method of allocating a set of data records among a plurality of data storage devices in a data storage system, the method comprising:

defining a series of group values based on the number of devices;

assigning each group value to a substantially equal number of the data records;

assigning each group value to one of the devices in the system; and

storing each of the data records on the device having a group value corresponding to the group value of the data record, wherein the group values are defined as a vector of integers each corresponding to one of the storage devices, the number of integers in the vector exceeding the number of storage devices.

15. The method of claim 14 wherein:

each of the records has a field value and the group values are assigned to the records based at least in part on the field values;

the field values are mapped to the group values by means of a hash function; and

the group value corresponding to the device to which a record is assigned is determined by the residue of the hash function of the field value modulo the number of integers in the vector.

16. The method of claim 15 further comprising the step of computing a new vector when the number of devices changes and re-allocating at least some of the records in accordance with the new vector.

17. The method of claim 16 wherein the step of computing a new vector comprises the steps of:

(a) computing the least common multiple of an initial and final number of storage devices;

(b) computing a number of times a new group value appears in a sequence of length is equal to the least common multiple;

(c) computing a number of times an existing group value appears in a sequence whose length is the least common multiple; and

(d) computing a number of times an existing group value is changed to a new group value.

18. The method of claim 14 wherein the size of the vector of integers is at least ten times larger than the number of storage devices.

19. A system for allocating data records among a plurality of data storage devices in a data storage system, the system comprising:

an interface to the data storage devices; and

a data allocation module configured (i) to define a series of group values based on the number of devices, (ii) to assign each group value to a substantially equal number of the data records, (iii) to assign one or more group values to each of the devices, (iv) to cause, via the interface, each of the data records to be stored on the device having a group value corresponding to the group value of the data record, and (v) when the number of storage devices changes, to re-allocate some of the records among storage devices based on the group values.

20. The system of claim 19 wherein the data allocation module comprises a record-allocation table including a plurality of cells, each cell representing an intersection of one of N rows and M columns, wherein N equals a maximum possible number of storage devices in the system and M equals the lowest common multiple of a series of numbers from 1 to N, the data allocation module being configured to assign one of the group values in the series to each cell, and when the number of storage devices changes, re-allocating is performed based on the table.

21. The system of claim 20 wherein the number of re-allocated records corresponds to an amount of storage added or subtracted due to the change in the number of storage devices.

22. The system of claim 20 wherein the number of storage devices corresponds to a row in the table, the data allocation module re-allocating the records by (i) selecting the row of the table corresponding to the changed number of storage devices, (ii) distributing the group values in the selected row among the data records so that some of the data records have new group values, and (iii) storing the data records having new group values on the devices corresponding thereto.

23. The system of claim 19 wherein each of the records has a field value and the data allocation module assigns group values to the records based at least in part on the field values.

24. The system of claim 23 wherein the data allocation module maps field values to the group values by means of a hash function.

25. The system of claim 24 wherein the hash function is a Pearson hash.

26. A system for allocating data records among a plurality of data storage devices in a data storage system, the system comprising:

an interface to the data storage devices; and

a data allocation module configured (i) to define a series of group values based on the number of devices, (ii) to assign each group value to a substantially equal number of the data records, (iii) to assign one or more group values to each of the devices, and (iv) to cause, via the interface, each of the data records to be stored on the device having a group value corresponding to the group value of the data record, wherein the group values are defined as a vector of integers each corresponding to one of the storage devices, the number of integers in the vector exceeding the number of storage devices.

27. The system of claim 26 wherein the data allocation module computes a new vector when the number of devices changes and re-allocating at least some of the records in accordance with the new vector.

28. An article of manufacture having computer-readable program portions embodied thereon, the article comprising computer-readable instructions for allocating a set of data records among a plurality of data storage devices in a data storage system by:

defining a series of group values based on the number of devices;

assigning each group value to a substantially equal number of the data records;

assigning one or more group values to each of the devices in the system;

storing each of the data records on the device having a group value corresponding to the group value of the data record; and

when the number of storage devices changes, re-allocating some of the records among storage devices based on the group values.

29. An article of manufacture having computer-readable program portions embodied thereon, the article comprising computer-readable instructions for allocating a set of data records among a plurality of data storage devices in a data storage system by:

defining a series of group values based on the number of devices;

assigning each group value to a substantially equal number of the data records;

assigning one or more group values to each of the devices in the system;

storing each of the data records on the device having a group value corresponding to the group value of the data record, wherein the group values are defined as a vector of integers each corresponding to one of the storage devices, the number of integers in the vector exceeding the number of storage devices.