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

Patent metadata

Field	Value
Publication number	US-9529540-B1
Application number	US-201514950461-A
Country	US
Kind code	B1
Filing date	Nov 24, 2015
Priority date	Nov 1, 2012
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

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 based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, the sorting comprising:
assigning the plurality of data blocks to a plurality of buckets, each bucket associated with a particular respective access pattern level and respective data block storage size requirement, wherein assigning the plurality of data blocks to the plurality of buckets comprises:
matching an access pattern and a storage size of a particular data block to an access pattern level and a data block storage requirement of a particular bucket from the plurality of buckets; and
assigning the particular data block to the particular bucket based on the matching; and

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:
determining a total number of data blocks assigned to a particular bucket from the plurality of buckets;
calculating a target number of data blocks for each of the plurality of storage devices for the particular bucket by dividing the determined total number of data blocks by a number of the plurality of storage devices; and
redistributing the data blocks assigned to the particular bucket across the plurality of storage devices based on the calculated target number of data blocks for each of the plurality of storage devices for the particular bucket.

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 performance characteristics 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 based on performance characteristics for the plurality of storage devices comprises redistributing the one or more data blocks across the plurality of storage devices in proportion to the determined performance characteristics for the plurality of storage devices.

5. The method of claim 1 , wherein redistributing the plurality of data blocks across the plurality of storage devices comprises:
selecting a bucket from the plurality of buckets, the bucket having an access pattern level specifying an access time that is more recent than an access time specified by an access pattern level for another bucket from the plurality of data buckets; and
redistributing data blocks assigned to the selected bucket prior to redistributing data blocks assigned to the another bucket.

6. The method of claim 1 , wherein each particular access pattern level comprises at least one of an access time range and an access count range.

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 based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, the sorting comprising:
assigning the plurality of data blocks to a plurality of buckets, each bucket associated with a particular respective access pattern level and respective data block storage size requirement, wherein assigning the plurality of data blocks to the plurality of buckets comprises:
matching an access pattern and a storage size of a particular data block to an access pattern level and a data block storage requirement of a particular bucket from the plurality of buckets; and
assigning the particular data block to the particular bucket based on the matching; and

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:
determining a total number of data blocks assigned to a particular bucket from the plurality of buckets;
calculating a target number of data blocks for each of the plurality of storage devices for the particular bucket by dividing the determined total number of data blocks by a number of the plurality of storage devices; and
redistributing the data blocks assigned to the particular bucket across the plurality of storage devices based on the calculated target number of data blocks for each of the plurality of storage devices for the particular bucket.

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 performance characteristics 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 based on performance characteristics for the plurality of storage devices comprises redistributing the one or more data blocks across the plurality of storage devices in proportion to the determined performance characteristics for the plurality of storage devices.

11. The medium of claim 7 , wherein redistributing the plurality of data blocks across the plurality of storage devices comprises:
selecting a bucket from the plurality of buckets, the bucket having an access pattern level specifying an access time that is more recent than an access time specified by an access pattern level for another bucket from the plurality of data buckets; and
redistributing data blocks assigned to the selected bucket prior to redistributing data blocks assigned to the another bucket.

12. The medium of claim 7 , wherein each particular access pattern level comprises at least one of an access time range and an access count range.

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 based at least in part on an access pattern and a size corresponding to respective data blocks of the plurality of data blocks, the sorting comprising:
assigning the plurality of data blocks to a plurality of buckets, each bucket associated with a particular respective access pattern level and respective data block storage size requirement, wherein assigning the plurality of data blocks to the plurality of buckets comprises:
matching an access pattern and a storage size of a particular data block to an access pattern level and a data block storage requirement of a particular bucket from the plurality of buckets; and
assigning the particular data block to the particular bucket based on the matching; and

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:
determining a total number of data blocks assigned to a particular bucket from the plurality of buckets;
calculating a target number of data blocks for each of the plurality of storage devices for the particular bucket by dividing the determined total number of data blocks by a number of the plurality of sto

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/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F3/0647

  Migration mechanisms · CPC title

• G06F3/0613

  in relation to throughput · CPC title