Redistributing data in a distributed storage system based on the attributes of the data

Patent metadata

Field	Value
Publication number	US-9811262-B1
Application number	US-201615357632-A
Country	US
Kind code	B1
Filing date	Nov 21, 2016
Priority date	Nov 1, 2012
Publication date	Nov 7, 2017
Grant date	Nov 7, 2017

Abstract

Accesses to a number of data blocks stored in a distributed storage are observed. Following observation of the accesses, the stored data blocks are redistributed. In one aspect, redistribution of the data blocks includes determining the access patterns for one or more of the data blocks based on the observed accesses, and determining the storage sizes for the one or more data blocks. Thereafter, based on the determined access patterns and determined storage sizes, the one or more data blocks are sorted. Subsequently, the one or more data blocks are redistributed or rebalanced across a number of storage devices of the distributed storage based on the sorting. In one aspect, the one or more data blocks are redistributed according to either a uniform distribution scheme or a proportional distribution scheme.

First claim

What is claimed is:

1. A method comprising:
sorting a plurality of data blocks into a plurality of categories based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, wherein each category of the plurality of categories is associated with a respective access pattern level and respective data block storage size requirement;
redistributing the plurality of data blocks across a plurality of storage devices of a distributed storage based on the sorting of the plurality of data blocks, the redistributing comprising:
calculating a target number of data blocks for each of the plurality of storage devices for a first category by dividing a total number of data blocks in the first category by a number of the plurality of storage devices; and
redistributing the data blocks in the first category across the plurality of storage devices based on the calculated target number of data blocks for each of the plurality of storage devices.

2. The method of claim 1 , wherein redistributing the plurality of data blocks across the plurality of storage devices based on the sorting comprises uniformly redistributing data blocks having similar access patterns and storage sizes across the plurality of storage devices.

3. The method of claim 1 , wherein redistributing the plurality of data blocks across the plurality of storage devices is further based on a determined performance characteristic for the plurality of storage devices.

4. The method of claim 3 , wherein redistributing the plurality of data blocks across the plurality of storage devices comprises redistributing the plurality of data blocks across the plurality of storage devices in proportion to a determined performance characteristic for the plurality of storage devices.

5. The method of claim 4 , wherein the determined performance characteristic comprises bandwidth of each of the plurality of storage devices.

6. The method of claim 4 , wherein the determined performance characteristic comprises storage capacity of each of the plurality of storage devices.

7. A non-transitory computer readable storage medium executing computer program instructions, the computer program instructions comprising instructions for:
sorting a plurality of data blocks into a plurality of categories based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, wherein each category of the plurality of categories is associated with a respective access pattern level and respective data block storage size requirement;
redistributing the plurality of data blocks across a plurality of storage devices of a distributed storage based on the sorting of the plurality of data blocks, the redistributing comprising:
calculating a target number of data blocks for each of the plurality of storage devices for a first category by dividing a total number of data blocks in the first category by a number of the plurality of storage devices; and
redistributing the data blocks in the first category across the plurality of storage devices based on the calculated target number of data blocks for each of the plurality of storage devices.

8. The medium of claim 7 , wherein redistributing the plurality of data blocks across the plurality of storage devices based on the sorting comprises uniformly redistributing data blocks having similar access patterns and storage sizes across the plurality of storage devices.

9. The medium of claim 7 , wherein redistributing the plurality of data blocks across the plurality of storage devices is further based on a determined performance characteristic for the plurality of storage devices.

10. The medium of claim 9 , wherein redistributing the plurality of data blocks across the plurality of storage devices comprises redistributing the plurality of data blocks across the plurality of storage devices in proportion to the determined performance characteristic for the plurality of storage devices.

11. The medium of claim 10 , wherein the determined performance characteristic comprises bandwidth of each of the plurality of storage devices.

12. The medium of claim 10 , wherein the determined performance characteristic comprises storage capacity of each of the plurality of storage devices.

13. A system comprising:
a non-transitory computer readable storage medium storing processor-executable computer program instructions, the instructions comprising instructions for:
sorting a plurality of data blocks into a plurality of categories based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, wherein each category of the plurality of categories is associated with a respective access pattern level and respective data block storage size requirement;
redistributing the plurality of data blocks across a plurality of storage devices of a distributed storage based on the sorting of the plurality of data blocks, the redistributing comprising:
calculating a target number of data blocks for each of the plurality of storage devices for a first category by dividing a total number of data blocks in the first category by a number of the plurality of storage devices; and
redistributing the data blocks in the first category across the plurality of storage devices based on the calculated target number of data blocks for each of the plurality of storage devices; and

a processor for executing the computer program instructions.

14. The system of claim 13 , wherein redistributing the plurality of data blocks across the plurality of storage devices based on the sorting comprises uniformly redistributing data blocks having similar access patterns and storage sizes across the plurality of storage devices.

15. The system of claim 13 , wherein redistributing the plurality of data blocks across the plurality of storage devices is further based on a determined performance characteristic for the plurality of storage devices.

16. The system of claim 15 , wherein redistributing the plurality of data blocks across the plurality of storage devices comprises redistributing the plurality of data blocks across the plurality of storage devices in proportion to the determined performance characteristic for the plurality of storage devices.

17. The system of claim 16 , wherein the determined performance characteristic comprises bandwidth of each of the plurality of storage devices.

18. The system of claim 16 , wherein the determined performance characteristic comprises storage capacity of each of the plurality of storage devices.

Assignees

• Quantcast Corp

Inventors

• Rus Silvius V
• Ovsiannikov Michael

Classifications

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F12/023

  Free address space management · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F3/064 Primary

  Management of blocks · CPC title