Reallocating storage in a dispersed storage network

• US 10,127,110 B2
• Filed: 05/02/2016
• Issued: 11/13/2018
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Motwani, Manish, Resch, Jason K.
• Primary Examiner(s): Bui, Jonathan A
• Application Number:
  US15/143,815
• Publication Number:
  US 20170034271A1
• Time in Patent Office: 925 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/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 13/4282 on a serial bus, e.g. I2C bus, SPI bus on daisy chain buses G06F13/4247
• CPC Class Codes: G06F 16/122 using management policies backup systems G06F11/1446; file migration policies for HSM systems G06F16/185
• CPC Class Codes: G06F 16/1824 implemented using Network-attached Storage [NAS] architecture distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/645 using a third party
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0653 : Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0668 : adopting a particular infrastructure
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 : Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/1515 : Reed-Solomon codes
• CPC Class Codes: H03M 13/2906 : using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/3761 : using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/061 : for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/0853 : using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 63/108 : when the policy decisions are valid for a limited amount of time
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/63 : Routing a service request depending on the request content or context
• CPC Class Codes: H04L 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

A method for execution by a dispersed storage and task (DST) execution unit includes updating a plurality of weighting factors corresponding to each of a plurality of memories in response to an indication of a change in memory capacity of one of the plurality of memories. At least one encoded data slice is received for storage by the DST execution unit. A plurality of scores are generated corresponding to each of the plurality of memories, wherein each of the plurality of scores is based on one of the plurality of weighting factors of a corresponding one of the plurality of memories. One of the plurality of memories is selected based on the plurality of scores, and the at least one encoded data slice is stored in the selected memory.

Claims

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

updating a plurality of weighting factors corresponding to each of a plurality of memories of the DST execution unit in response to an indication of a change in memory capacity of one of the plurality of memories and in accordance with a Decentralized Agreement Protocol (DAP) that is implemented to maintain utilization across the plurality of memories to be substantially equal;

receiving, via the interface and via a dispersed or distributed storage network (DSN) and from a DST processing unit, at least one encoded data slice for storage by the DST execution unit;

generating a plurality of scores corresponding to each of the plurality of memories, wherein each of the plurality of scores is based on one of the plurality of weighting factors of a corresponding one of the plurality of memories;

selecting one of the plurality of memories based on the plurality of scores in accordance with a resource map that indicates relative remaining healthy storage capacities of the plurality of memories; and

storing the at least one encoded data slice in the selected one of the plurality of memories.

2. The method of claim 1, wherein the indication of the change of the memory capacity is generated based on interpreting an error message.

3. The method of claim 1, further comprising performing a memory test on the plurality of memories;

and

wherein the indication of the change of memory capacity is generated based on comparing a result of the memory test to a previous result corresponding to a previous memory test.

4. The method of claim 1, wherein the indication of the change of the memory capacity is generated based on one of:

a failure or removal of a memory block of the one of the plurality of memories.

5. The method of claim 1, wherein the plurality of weighting factors are updated in response to an indication that the change in memory capacity is greater than a predefined threshold.

6. The method of claim 1, wherein the selected one of the plurality of memories is determined based on the corresponding one of the plurality of memories with the highest corresponding score.

7. The method of claim 1, wherein each of the plurality of scores is further generated based on an attribute of the received encoded slice.

8. The method of claim 1, wherein the indication of a change in the memory capacity indicates a lowered memory capacity of the one of the plurality of memories, and wherein the plurality of weighting factors are updated by decreasing a weighting factor of the plurality of weighting factors corresponding to the one of the plurality of memories with the lowered memory capacity, and increasing remaining ones of the weighting factors of remaining memories of the plurality of memories.

9. The method of claim 8, wherein the decrease of the weighting factor of the corresponding one of the plurality of memories with the lowered memory capacity is proportional to a degree of change in the memory capacity, and remaining ones of the plurality of weighting factors corresponding to the remaining memories are increased based on the decrease in the weighting factor of the one of the plurality of memories with the lowered memory capacity.

10. The method of claim 1, wherein the plurality of weighting factors are updated in response to an indication that at least one second encoded data slice has been one of:

written to or deleted from the one of the plurality of memories.

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

an interface configured to interface and communicate with a dispersed storage network (DSN);

at least one processor;

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

update a plurality of weighting factors corresponding to each of a plurality of memories of the DST execution unit in response to an indication of a change in memory capacity of one of the plurality of memories and in accordance with a Decentralized Agreement Protocol (DAP) that is implemented to maintain utilization across the plurality of memories to be substantially equal;

receive, via the interface and via the DSN from a DST processing unit, at least one encoded data slice for storage by the DST execution unit;

generate a plurality of scores corresponding to each of the plurality of memories, wherein each of the plurality of scores is based on one of the plurality of weighting factors of a corresponding one of the plurality of memories;

select one of the plurality of memories based on the plurality of scores in accordance with a resource map that indicates relative remaining healthy storage capacities of the plurality of memories; and

store the at least one encoded data slice in the selected one of the plurality of memories.

12. The processing system of claim 11, wherein the indication of the change of the memory capacity is generated based on interpreting an error message.

13. The processing system of claim 11, wherein execution of the operational instructions by the at least one processor further causes the processing system to perform a memory test on the plurality of memories;

and

wherein the indication of the change of memory capacity is generated based on comparing a result of the memory test to a previous result corresponding to a previous memory test.

14. The processing system of claim 11, wherein the indication of the change of the memory capacity is generated based on one of:

a failure or removal of a memory block of the one of the plurality of memories.

15. The processing system of claim 11, wherein the plurality of weighting factors are updated in response to an indication that the change in memory capacity is greater than a predefined threshold.

16. The processing system of claim 11, wherein the selected one of the plurality of memories is determined based on the corresponding one of the plurality of memories with the highest corresponding score.

17. The processing system of claim 11, wherein the indication of a change in the memory capacity indicates a lowered memory capacity of the one of the plurality of memories, and wherein the plurality of weighting factors are updated by decreasing a weighting factor of the plurality of weighting factors corresponding to the one of the plurality of memories with the lowered memory capacity, and increasing remaining ones of the weighting factors of remaining memories of the plurality of memories.

18. The processing system of claim 17, wherein the decrease of the weighting factor of the corresponding one of the plurality of memories with the lowered memory capacity is proportional to a degree of change in the memory capacity, and remaining ones of the plurality of weighting factors corresponding to the remaining memories are increased based on the decrease in the weighting factor of the one of the plurality of memories with the lowered memory capacity.

19. The processing system of claim 11, wherein the plurality of weighting factors are updated in response to an indication that at least one second encoded data slice has been one of:

written to or deleted from the one of the plurality of memories.

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;

update a plurality of weighting factors corresponding to each of a plurality of memories of a dispersed storage and task (DST) execution unit in response to an indication of a change in memory capacity of one of the plurality of memories and in accordance with a Decentralized Agreement Protocol (DAP) that is implemented to maintain utilization across the plurality of memories to be substantially equal;

receive, via the DSN from a DST processing unit, at least one encoded data slice for storage;

generate a plurality of scores corresponding to each of the plurality of memories, wherein each of the plurality of scores is based on one of the plurality of weighting factors of a corresponding one of the plurality of memories;

select one of the plurality of memories based on the plurality of scores in accordance with a resource map that indicates relative remaining healthy storage capacities of the plurality of memories; and

store the at least one encoded data slice in the selected one of the plurality of memories.