Allocating data for storage by utilizing a location-based hierarchy in a dispersed storage network

• US 10,387,248 B2
• Filed: 08/09/2016
• Issued: 08/20/2019
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K.
• Primary Examiner(s): Vallecillo, Kyle
• Application Number:
  US15/232,147
• Publication Number:
  US 20170286222A1
• Time in Patent Office: 1,106 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 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 11/3051 Monitoring arrangements for monitoring the configuration of the computing system or of the computing system component, e.g. monitoring the presence of processing resources, peripherals, I/O links, software programs verification or detection of system hardware configuration G06F11/2247
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 11/3692 for test results analysis
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• 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]
• CPC Class Codes: H03M 13/1515 : Reed-Solomon codes
• CPC Class Codes: H03M 13/373 : with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/616 : Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• 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]

Abstract

A method for execution by a dispersed storage and task (DST) processing unit includes generating storage allocation data indicating a subset of a plurality of storage units based on storage location hierarchy data and an information dispersal algorithm (IDA) width. A plurality of write requests corresponding to each storage unit in the first subset are generated for transmission via a network, where each of the plurality of write requests includes one of a plurality of encoded slices of a data object.

Claims

1. A method for execution by a dispersed storage and task (DST) processing unit of a dispersed storage network (DSN) that includes a plurality of storage units, the method comprises:

selecting a first width number from a first hierarchal storage location level of the DSN;

selecting a second width number from a second hierarchal storage location level of the DSN, wherein the second hierarchal storage level is a sub-division of the first hierarchal storage location level;

selecting a base width number from a base hierarchal storage location level of the DSN, wherein the base hierarchal storage level is a sub-division of the second hierarchal storage location level, and wherein a storage location of the base hierarchal storage location level includes one or more storage units of the plurality of storage units;

selecting an information dispersal algorithm (IDA) value based on a maximum IDA value and a DSN performance value;

identifying a first subset of the plurality of storage units based on the first, second, and base width numbers and the selected IDA value; and

generating a first plurality of write requests for sending to the first subset of the plurality of storage units, wherein each of the first plurality of write requests includes one of a plurality of encoded slices of a data object.

2. The method of claim 1, wherein the selecting one or more of the first, second, and base width numbers is based on a decentralized agreement protocol (DAP).

3. The method of claim 1, wherein the identifying the first subset of the plurality of storage units further comprises:

selecting a number of storage units from each storage location of the base width number of storage locations of the base hierarchal storage location level as the first subset of the plurality of storage units such that the first subset of the plurality of storage units are equally distributed among the base width number of storage locations.

4. The method of claim 3, wherein the selecting the number of storage units from each location of the base width number of storage locations further comprises:

calculating the number of storage units from each location of the base width number of storage locations by dividing the selected IDA value by the base width number.

5. The method of claim 1, wherein the first hierarchal storage location level includes a plurality of geographical regions and the first width number includes a selected number of geographical regions of the plurality of geographical regions, the second hierarchal storage location level includes a plurality of cities selected based on the selected number of geographical regions and the second width number includes a selected number of cities of the plurality of cities, and the base hierarchal storage location level includes a plurality of data centers selected based on the selected cities and the base width number includes a selected number of data centers of the plurality of data centers.

6. The method of claim 1, wherein the identifying the first subset of the plurality of storage units further comprises:

selecting the first subset of the plurality of storage units based on location parameter data.

7. The method of claim 6, wherein the location parameter data includes location weight data indicating at least one location weight corresponding to at least one of:

at least one storage location from the first hierarchal storage location level, at least one storage location from the second hierarchal storage location level, or at least one storage location from the base hierarchal storage location level, wherein a distribution of the first subset of the plurality of storage units among the base width number of storage locations from the base hierarchal storage location level is based on the location weight data.

8. The method of claim 1, wherein the identifying the first subset of the plurality of storage units is further based on a decentralized agreement protocol (DAP).

9. The method of claim 1, further comprises:

selecting one or more of the first width number, the second width number, the base width number, and a desired number of storage units per storage location of the base hierarchal storage location level based on width parameter data.

10. The method of claim 1, wherein the selecting the IDA value further comprises:

calculating the product of the first width number, the second width number, the base width number, and a number of storage units available on each storage location of the base hierarchal storage location level to determine the maximum IDA value; and

selecting the selected IDA value to be less than or equal to the maximum IDA value in accordance with the DSN performance level, wherein the DSN performance level indicates one or more of;

a status of one or more units of the DSN, loading of the one or more units of the DSN, and wherein the status includes failed, added, upgraded, repaired, expanded, replaced, deleted, activated, and deactivated, and wherein the one or more units of the DSN includes the plurality of storage units.

11. The method of claim 1, further comprising:

generating reassignment data in response to a change in one or more of the first width number, the second width number, the base width number, and the selected IDA value, wherein the reassignment data indicates a mapping of the plurality of encoded slices to a second subset of the plurality of storage units of the DSN based on the change in the one or more of the first width number, the second width number, the base width number and the selected IDA value; and

generating a second plurality of write requests for sending to the second subset, wherein each of the second plurality of write requests includes one of the plurality of encoded slices of a data object based on the reassignment data.

18. The method of claim 1 further comprises:

selecting a third width number from a third hierarchal storage location level of the DSN, wherein the third hierarchal storage level is a sub-division of the second hierarchal storage location level;

selecting the base width number from the base hierarchal storage location level of the DSN, wherein the base hierarchal storage level is a sub-division of the third hierarchal storage location level; and

identifying the first subset of the plurality of storage units based on the first, second, third, and base width numbers and the selected IDA value.

12. A processing system of a dispersed storage and task (DST) processing unit of a dispersed storage network (DSN) that includes a plurality of storage units 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;

select a first width number from a first hierarchal storage location level of the DSN;

select a second width number from a second hierarchal storage location level of the DSN, wherein the second hierarchal storage level is a sub-division of the first hierarchal storage location level;

select a base width number from a base hierarchal storage location level of the DSN, wherein the base hierarchal storage level is a sub-division of the second hierarchal storage location level, and wherein a storage location of the base hierarchal storage location level includes one or more storage units of the plurality of storage units;

select an information dispersal algorithm (IDA) value based on a maximum IDA value and a DSN performance value;

identify a first subset of the plurality of storage units based on the first, second, and base width numbers and the selected IDA value; and

generate a first plurality of write requests for sending to the first subset of the plurality of storage units, wherein each of the first plurality of write requests includes one of a plurality of encoded slices of a data object.

13. The processing system of claim 12, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to select one or more of the first, second, and base width numbers based on a decentralized agreement protocol (DAP).

14. The processing system of claim 12, wherein the identifying the first subset of the plurality of storage units further comprises:

selecting a number of storage units from each storage location of the base width number of storage locations of the base hierarchal storage location level as the first subset of the plurality of storage units such that the first subset of the plurality of storage units are equally distributed among the base width number of storage locations.

15. The processing system of claim 14, wherein the operational instructions, when executed by the at least one processor, further cause the processing system to select the number storage units from each location of the base width number of storage locations by:

calculating the number of storage units from each location of the base width number of storage locations by dividing the selected IDA value by the base width number.

16. The processing system of claim 12, wherein the first hierarchal storage location level includes a plurality of geographical regions and the first width number includes a selected number of geographical regions of the plurality of geographical regions, the second hierarchal storage location level includes a plurality of cities selected based on the selected number of geographical regions and the second width number includes a selected number of cities of the plurality of cities, and the base hierarchal storage location level includes a plurality of data centers selected based on the selected cities and the base width number includes a selected number of data centers of the plurality of data centers.

17. A non-transitory computer readable storage device 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;

select a first width number from a first hierarchal storage location level of the DSN;

select a second width number from a second hierarchal storage location level of the DSN, wherein the second hierarchal storage level is a sub-division of the first hierarchal storage location level;

select a base width number from a base hierarchal storage location level of the DSN, wherein the base hierarchal storage level is a sub-division of the second hierarchal storage location level, and wherein a storage location of the base hierarchal storage location level includes one or more storage units of the plurality of storage units;

select an information dispersal algorithm (IDA) value based on a maximum IDA value and a DSN performance value;

identify a first subset of the plurality of storage units based on the first, second, and base width numbers and the selected IDA value; and

generate a first plurality of write requests for sending to the first subset of the plurality of storage units, wherein each of the first plurality of write requests includes one of a plurality of encoded slices of a data object.