Rebalancing data storage in a dispersed storage network

• US 10,254,992 B2
• Filed: 09/12/2016
• Issued: 04/09/2019
• Est. Priority Date: 04/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Khadiwala, Ravi V., Motwani, Manish, Resch, Jason K., Vossberg, Trevor J., Wozniak, Ethan S.
• Primary Examiner(s): Abraham, Esaw T
• Application Number:
  US15/262,985
• Publication Number:
  US 20160378395A1
• Time in Patent Office: 939 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for execution by a dispersed storage and task (DST) execution unit includes generating location weight data that includes a plurality of location weights assigned to a plurality of memory devices of the DST execution unit. A first one of the plurality of memory devices and a second one of the plurality of memory devices are selected for reallocation based on the location weight data. The reallocation is executed by removing a data slice from the first one of the plurality of memory devices and storing the data slice in the second one of the plurality of memory devices.

Claims

1. A method for execution by a dispersed storage and task (DST) execution unit that includes a processor, the method comprises:

determining a plurality of location weights assigned to a plurality of memory devices of the DST execution unit;

generating a ranked plurality of scores by performing a deterministic function on an identifier of a data slice and on the plurality of location weights;

selecting a first one of the plurality of memory devices in response to determining the data slice is stored in the first one of the plurality of memory devices;

selecting a second one of the plurality of memory devices in response to determining a highest ranked one of the ranked plurality of scores corresponds to the second one of the plurality of memory devices;

removing the data slice from the first one of the plurality of memory devices; and

storing the data slice in the second one of the plurality of memory devices.

2. The method of claim 1, wherein the plurality of location weights are assigned based on at least one of:

storage utilization levels of the plurality of memory devices or storage availability levels of the plurality of memory devices.

3. The method of claim 1, wherein the first one of the plurality of memory devices and the second one of the plurality of memory devices are selected in response to a second location weight corresponding to the second one of the plurality of memory devices being more favorable than a first location weight corresponding to the first one of the plurality of memory devices.

4. The method of claim 3, wherein the second location weight is more favorable than the first location weight in response to the second one of the plurality of memory devices having a higher storage availability level than the first one of the plurality of memory devices.

5. The method of claim 1, wherein the first one of the plurality of memory devices includes a plurality of memory sections, wherein the plurality of location weights includes a plurality of section weights corresponding to the plurality of memory sections, and wherein the data slice is selected based on the plurality of section weights.

6. The method of claim 1, wherein the second one of the plurality of memory devices includes a plurality of memory sections, wherein the plurality of location weights includes a plurality of section weights corresponding to the plurality of memory sections, wherein one of the plurality of memory sections is selected based on the plurality of section weights, and wherein the data slice is stored in the selected one of the plurality of memory sections.

7. The method of claim 1, wherein generating the ranked plurality of scores is based on a decentralized agreement protocol.

8. The method of claim 1, further comprising:

receiving a second data slice for storage via a network;

selecting a third one of the plurality of memory devices based on the plurality of location weights; and

storing the second data slice in the third one the plurality of memory devices.

9. The method of claim 1, further comprising:

receiving an access request via a network that includes the identifier corresponding to the data slice;

generating slice retrieval data by determining the data slice is stored in the second one of the plurality of memory devices based on the identifier and the plurality of location weights;

retrieving the data slice from the second one of the plurality of memory devices based on the slice retrieval data; and

generating an access response that includes the data slice for transmission via the network.

10. The method of claim 9, wherein the slice retrieval data is further generated based on a decentralized agreement protocol.

11. A processing system of a dispersed storage and task (DST) execution unit comprises:

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to;

determine a plurality of location weights assigned to a plurality of memory devices of the DST execution unit;

generate a ranked plurality of scores by performing a deterministic function on an identifier of a data slice and on the plurality of location weights;

selecting a first one of the plurality of memory devices in response to determining the data slice is stored in the first one of the plurality of memory devices;

selecting a second one of the plurality of memory devices in response to determining a highest ranked one of the ranked plurality of scores corresponds to the second one of the plurality of memory devices;

remove the data slice from the first one of the plurality of memory devices; and

store the data slice in the second one of the plurality of memory devices.

12. The processing system of claim 11, wherein the plurality of location weights are assigned based on at least one of:

storage utilization levels of the plurality of memory devices or storage availability levels of the plurality of memory devices.

13. The processing system of claim 11, wherein the first one of the plurality of memory devices and the second one of the plurality of memory devices are selected in response to a second location weight corresponding to the second one of the plurality of memory devices comparing favorably to a first location weight corresponding to the first one of the plurality of memory devices.

14. The processing system of claim 13, wherein the second location weight compares favorably to the first location weight in response to the second one of the plurality of memory devices having a higher storage availability level than the first one of the plurality of memory devices.

15. The processing system of claim 11, wherein the first one of the plurality of memory devices includes a plurality of memory sections, wherein the plurality of location weights includes a plurality of section weights corresponding to the plurality of memory sections, and wherein the data slice is selected based on the plurality of section weights.

16. The processing system of claim 11, wherein the second one of the plurality of memory devices includes a plurality of memory sections, wherein the plurality of location weights includes a plurality of section weights corresponding to the plurality of memory sections, wherein one of the plurality of memory sections is selected based on the plurality of section weights, and wherein the data slice is stored in the selected one of the plurality of memory sections.

17. The processing system of claim 11, wherein selecting the first one of the plurality of memory devices and the second one of the plurality of memory devices is further based on a decentralized agreement protocol.

18. The processing system of claim 11, wherein the operational instructions, when executed by the at least one processor, further cause the processor to:

receive a second data slice for storage via a network;

select a third one of the plurality of memory devices based on the plurality of location weights; and

store the second data slice in the third one the plurality of memory devices.

19. The processing system of claim 11, wherein the operational instructions, when executed by the at least one processor, further cause the processor to:

receive an access request via a network that includes the identifier corresponding to the data slice;

generate slice retrieval data by determining the data slice is stored in the second one of the plurality of memory devices based on the identifier and the plurality of location weights;

retrieve the data slice from the second one of the plurality of memory devices based on the slice retrieval data; and

generate an access response that includes the data slice for transmission via the network.

20. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to;

determine a plurality of location weights assigned to a plurality of memory devices;

generate a ranked plurality of scores by performing a deterministic function on an identifier of a data slice and on the plurality of location weights;

selecting a first one of the plurality of memory devices in response to determining the data slice is stored in the first one of the plurality of memory devices;

selecting a second one of the plurality of memory devices in response to determining a highest ranked one of the ranked plurality of scores corresponds to the second one of the plurality of memory devices;

remove the data slice from the first one of the plurality of memory devices; and

store the data slice in the second one of the plurality of memory devices.