Utilizing request deadlines in a dispersed storage network

• US 10,169,151 B2
• Filed: 08/29/2016
• Issued: 01/01/2019
• Est. Priority Date: 10/30/2015
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Kaczmarek, Joseph M., Narubin, Renars W., Volvovski, Ilya
• Primary Examiner(s): Contino, Paul
• Application Number:
  US15/249,630
• Publication Number:
  US 20170123947A1
• Time in Patent Office: 855 Days
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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/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/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/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• 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/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 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• 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 a plurality of access requests that include an execution deadline time for transmission via a network to a corresponding subset of a plurality of storage units. A first deadline error notification is received via the network from a first storage unit of the first subset. A new one of the plurality of storage units not included in the first subset is selected in response to receiving the first deadline error notification. A new access request that includes an updated execution deadline time is generated for transmission to the new one of the plurality of storage units via the network. The new access request is based on a one of the first plurality of access requests sent to the first storage unit of the first subset.

Claims

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

generating a first plurality of access requests that include a first execution deadline time, the first plurality of access requests for transmission via a network to a corresponding first subset of a plurality of storage units;

receiving a first deadline error notification via the network from a first storage unit of the first subset;

calculating a missed deadline cost value in response to receiving the first deadline error notification;

comparing the missed deadline cost value to a new request cost threshold;

selecting a new one of the plurality of storage units not included in the first subset in response to receiving the first deadline error notification;

generating a new access request for transmission to the new one of the plurality of storage units via the network that includes an updated execution deadline time, wherein the new access request is based on a one of the first plurality of access requests sent to the first storage unit of the first subset, wherein the new one of the plurality of storage units is selected and the new access request is generated for transmission to the new one of the of the plurality of storage units when the missed deadline cost value compares favorably to the new request cost threshold; and

generating a proceed with execution notification for transmission via the network to the first storage unit of the first subset indicating a request to continue executing the access request when the missed deadline cost value compares unfavorably to the new request cost threshold.

2. The method of claim 1, wherein the first deadline error notification is transmitted by the one of the plurality of storage units in response to an estimated completion time comparing unfavorably to the first execution deadline time.

3. The method of claim 2, wherein the first deadline error notification is transmitted by the one of the plurality of storage units prior to attempting to execute the access request.

4. The method of claim 1, further comprising:

generating a plurality of execution deadline update notifications that include the updated execution deadline time for transmission via the network to the storage units of the first subset from which the first deadline error notification was not received.

5. The method of claim 1, further comprising:

determining the first execution deadline time based on at least one of;

performance data corresponding to the first subset of the plurality of storage units, an access type corresponding to the first plurality of access requests, or an access priority corresponding to the first plurality of access requests.

6. The method of claim 1, further comprising:

determining the updated execution deadline time based on at least one of;

performance data corresponding to the one of the plurality of storage units, an access type corresponding to the new access request, or an access priority corresponding to the first plurality of access requests.

7. The method of claim 1, wherein the first plurality of access requests are generated in response to a request to read a data object, and wherein the new one of the plurality of storage units is selected based on the first subset of the plurality of storage units, the one of the plurality of storage units from which the first deadline error notification was received, and a unique combination reads (UCR) protocol.

8. The method of claim 7, further comprising:

generating a new subset by removing the first storage unit from the first subset and including a new subset of the plurality of storage units that includes the new one of the plurality of storage units, wherein the new subset is based on a unique read combination of the data object; and

generating a new access request for transmission via the network to each corresponding storage unit in the new subset.

9. The method of claim 1, further comprising:

generating a second plurality of access requests that include a second execution deadline time, the second plurality of access requests for transmission via the network to a corresponding second subset of the plurality of storage units;

receiving a second deadline error notification via the network from a second storage unit of the second subset;

calculating a second missed deadline cost value in response to receiving the second deadline error notification;

comparing the second missed deadline cost value to the new request cost threshold; and

generating a plurality of access cancellation requests for transmission via the network to storage units of the second subset from which the second deadline error notification was not received in response to the second missed deadline cost value comparing unfavorably to the new request cost threshold.

10. The method of claim 1, wherein the first deadline error notification includes an estimated completion time, and wherein the missed deadline cost value is calculated based on a difference between the estimated completion time and the first execution deadline time.

11. The method of claim 1, wherein the missed deadline cost value is calculated based on at least one of:

an access type corresponding to the first plurality of access requests, an access priority corresponding to the first plurality of access requests, performance data corresponding to the first storage unit of the first subset, or performance data corresponding to at least one of the plurality of storage units not included in the first subset.

12. The method of claim 1, further comprising:

receiving a plurality of deadline error notifications via the network;

wherein the missed deadline cost value is calculated based on at least one of;

a number of deadline error notifications received, or performance data corresponding to at least one of the plurality of storage units from which the plurality of deadline error notifications was received.

13. The method of claim 1, further comprising:

generating a second plurality of access requests that include a second execution deadline time for transmission via a network to a corresponding second subset of a plurality of storage units; and

receiving a second deadline error notification via the network based on an estimated completion time comparing unfavorably to the second execution deadline time at one of a plurality of system layers.

14. The method of claim 13, wherein the plurality of system layers includes at least one of:

a grid layer logic layer, a network queue layer, a network transmission layer, a storage unit request handling layer, an IO scheduling layer, a memory device subsystem layer, a response network queue layer, or a network transmission layer.

15. The method of claim 13, wherein the second plurality of access requests include a plurality of execution deadline times corresponding to each of the plurality of system layers, and wherein the second deadline error notification is based on an estimated completion time of one of the plurality of system layers comparing unfavorably to the corresponding one of a plurality of execution deadline times.

16. A processing system of a dispersed storage and task (DST) processing 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;

generate a first plurality of access requests that include a first execution deadline time, the first plurality of access requests for transmission via a network to a corresponding first subset of a plurality of storage units;

receive a first deadline error notification via the network from a first storage unit of the first subset;

calculate a missed deadline cost value in response to receiving the first deadline error notification;

compare the missed deadline cost value to a new request cost threshold;

select a new one of the plurality of storage units not included in the first subset in response to receiving the first deadline error notification;

generate a new access request for transmission to the new one of the plurality of storage units via the network that includes an updated execution deadline time, wherein the new access request is based on a one of the first plurality of access requests sent to the first storage unit of the first subset, wherein the new one of the plurality of storage units is selected and the new access request is generated for transmission to the new one of the of the plurality of storage units when the missed deadline cost value compares favorably to the new request cost threshold; and

generate a proceed with execution notification for transmission via the network to the first storage unit of the first subset indicating a request to continue executing the access request when the missed deadline cost value compares unfavorably to the new request cost threshold.

17. The processing system of claim 16, wherein the first plurality of access requests are generated in response to a request to read a data object, and wherein the new one of the plurality of storage units is selected based on the first subset of the plurality of storage units, the one of the plurality of storage units from which the first deadline error notification was received, and a unique combination reads (UCR) protocol.

18. 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;

generate a first plurality of access requests that include a first execution deadline time, the first plurality of access requests for transmission via a network to a corresponding first subset of a plurality of storage units;

receive a first deadline error notification via the network from a first storage unit of the first subset;

calculate a missed deadline cost value in response to receiving the first deadline error notification;

compare the missed deadline cost value to a new request cost threshold;

select a new one of the plurality of storage units not included in the first subset in response to receiving the first deadline error notification;

generate a new access request for transmission to the new one of the plurality of storage units via the network that includes an updated execution deadline time, wherein the new access request is based on a one of the first plurality of access requests sent to the first storage unit of the first subset, wherein the new one of the plurality of storage units is selected and the new access request is generated for transmission to the new one of the of the plurality of storage units when the missed deadline cost value compares favorably to the new request cost threshold; and

generate a proceed with execution notification for transmission via the network to the first storage unit of the first subset indicating a request to continue executing the access request when the missed deadline cost value compares unfavorably to the new request cost threshold.