Optimistic data writing in a dispersed storage network

• US 8,572,429 B2
• Filed: 11/24/2010
• Issued: 10/29/2013
• Est. Priority Date: 10/09/2007
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg
• Primary Examiner(s): KO, CHAE M
• Application Number:
  US12/954,025
• Publication Number:
  US 20110072321A1
• Time in Patent Office: 1,070 Days
• Field of Search: 714/15, 714/18, 714/6.24, 711/114
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A method begins by a processing module dispersed storage error encoding data to produce a set of encoded data slices and sending a set of write request messages to a set of dispersed storage (DS) units, wherein each of the set of write request messages includes an encoded data slice of the set of encoded data slices. The method continues with the processing module determining whether a pillar width number of favorable write response messages has been received within a write acknowledgement (ACK) time period. The method continues with the processing module executing a retry write process to at least one DS unit of the set of DS units from which a favorable write response message was not received during the write ACK time period when the pillar width number of favorable write response messages has not been received within the write ACK time period.

Claims

1. A method comprises:

dispersed storage error encoding data to produce a set of encoded data slices;

sending a set of write request messages to a set of dispersed storage (DS) units, wherein each of the set of write request messages includes an encoded data slice of the set of encoded data slices;

determining whether a pillar width number of favorable write response messages has been received within a write acknowledgement (ACK) time period;

when the pillar width number of favorable write response messages has not been received within the write ACK time period, executing a retry write process to at least one DS unit of the set of DS units from which a favorable write response message was not received during the write ACK time period;

when a write threshold number of favorable write response messages has been received within the write ACK time period, sending a set of commit transaction request messages to the set of DS units;

determining whether a pillar width number of favorable commit transaction response messages has been received within a commit ACK time period; and

when the pillar width number of favorable commit transaction response messages has not been received within the commit ACK time period, executing a retry commit process to at least one DS unit of the set of DS units from which a favorable commit transaction response message was not received during the write ACK time period.

2. The method of claim 1, wherein the retry write process comprises:

determining whether a write threshold number of favorable write response messages has been received within the write ACK time period;

when the write threshold number of favorable write response messages has not been received within the write ACK time period, entering a loop that includes;

identifying each DS unit of the set of DS units from which a favorable write response message was not received during the write ACK time period to produce a plurality of identified DS units;

identifying each slice name associated with each of the plurality of identified DS units to produce a plurality of identified slice names;

sending a plurality of retry write request messages to the plurality of identified DS units, wherein a retry write request message of the plurality of retry write request messages includes an encoded data slice of the set of encoded data slices associated with one of the plurality of identified slice names;

determining whether the write threshold number of favorable write response messages has been cumulatively received prior to expiration of a retry write ACK time period; and

when the write threshold number of favorable write response messages has not been cumulatively received prior to expiration of the retry write ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and issuing a plurality of rollback transaction request messages; and

when the write threshold number of favorable write response messages have been cumulatively received prior to expiration of the retry write ACK time period, exiting the loop and issuing a plurality of commit transaction request messages.

3. The method of claim 1, wherein the retry write process comprises:

determining whether a write threshold number but less than the pillar width number of favorable write response messages has been received within the write ACK time period;

when the write threshold number but less than the pillar width number of favorable write response messages have been received within the write ACK time period, entering a loop that includes;

identifying a DS unit from which a favorable write response message was not received during the write ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

sending a retry write request message to the identified DS unit, wherein the retry write message includes an encoded data slice of the set of encoded data slices associated with the identified slice name;

determining whether the pillar width number of favorable write response messages has been cumulatively received prior to expiration of a retry write ACK time period; and

when the pillar width number of favorable write response messages has not been cumulatively received prior to expiration of the retry write ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and recording the identified slice name for rebuilding; and

when the pillar width number of favorable write response messages have been cumulatively received prior to expiration of the retry write ACK time period, exiting the loop.

4. The method of claim 1, wherein the retry commit process comprises:

determining whether a commit threshold number of favorable commit transaction response messages has been received within the commit ACK time period;

when the commit threshold number of favorable commit transaction response messages has not been received within the commit ACK time period, entering a loop that includes;

identifying each DS unit of the set of DS units from which a favorable commit transaction response message was not received during the commit ACK time period to produce a plurality of identified DS units;

sending a plurality of retry commit transaction request messages to the plurality of identified DS units;

determining whether the commit threshold number of favorable commit transaction response messages has been cumulatively received prior to expiration of a retry commit ACK time period; and

when the commit threshold number of favorable commit transaction response messages has not been cumulatively received prior to expiration of a retry commit ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and issuing a plurality of undo transaction request messages; and

when the commit threshold number of favorable commit transaction response messages have been cumulatively received prior to expiration of the retry commit ACK time period, exiting the loop and issuing a plurality of finalize transaction request messages.

5. The method of claim 1, wherein the retry commit process comprises:

determining whether a commit threshold number but less than the a pillar width number of favorable commit transaction response messages has been received within the commit ACK time period;

when the commit threshold number but less than the pillar width number of favorable commit transaction response messages have been received within the commit ACK time period, entering a loop that includes;

identifying a DS unit from which a favorable commit transaction response message was not received during the commit ACK time period to produce an identified DS unit;

sending a retry commit transaction request message to the identified DS unit;

determining whether the pillar width number of favorable commit transaction response messages has been cumulatively received prior to expiration of a retry commit ACK time period; and

when the pillar width number of favorable commit transaction response messages has not been cumulatively received prior to expiration of the retry commit ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and recording an associated slice name for rebuilding; and

when the pillar width number of favorable commit transaction response messages have been cumulatively received prior to expiration of the retry commit ACK time period, exiting the loop.

6. The method of claim 1, wherein the retry commit process comprises:

identifying a DS unit of the set of DS units from which a favorable commit transaction response message was not received during a commit ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

determining whether to execute a retry commit process for the identified DS unit or to execute a retry write-commit process using a foster DS unit for the identified DS unit or using an alternate DS unit in place of the identified DS unit; and

when the retry write-commit process is to be used;

sending a new write request message to the foster DS unit or the alternate DS unit, wherein the new write request message includes an encoded data slice of the set of encoded data slices associated with the identified slice name; and

when a favorable write response message is received from the foster DS unit or the alternate DS unit, sending a new commit transaction request message to the foster DS unit or the alternate DS unit.

7. The method of claim 1, wherein the retry write process comprises:

identifying a DS unit of the set of DS units from which a favorable write response message was not received during the write ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

determining whether to execute the retry write process for the identified DS unit, using a foster DS unit for the identified DS unit, or using an alternate DS unit in place of the identified DS unit; and

when the foster DS unit or the alternate DS unit is to be used, sending a retry write request message to the foster DS unit or the alternate DS unit in accordance with the retry write process, wherein the retry write request message includes an encoded data slice of the set of encoded data slices associated with the identified slice name.

8. A computer comprises:

an interface; and

a processing module operable to;

dispersed storage error encode data to produce a set of encoded data slices;

send, via the interface, a set of write request messages to a set of dispersed storage (DS) units, wherein each of the set of write request messages includes an encoded data slice of the set of encoded data slices;

determine whether a pillar width number of favorable write response messages has been received, via the interface, within a write acknowledgement (ACK) time period;

execute a retry write process to at least one DS unit of the set of DS units from which a favorable write response message was not received during the write ACK time period when the pillar width number of favorable write response messages has not been received within the write ACK time period;

send, via the interface, a set of commit transaction request messages to the set of DS units when a write threshold number of favorable write response messages has been received, via the interface, within the write ACK time period;

determine whether a pillar width number of favorable commit transaction response messages has been received, via the interface, within a commit ACK time period; and

execute a retry commit process to at least one DS unit of the set of DS units from which a favorable commit transaction response message was not received, via the interface, during the write ACK time period when the pillar width number of favorable commit transaction response messages has not been received, via the interface, within the commit ACK time period.

9. The computer of claim 8, wherein the processing module further functions to execute the retry write process by:

determining whether a write threshold number of favorable write response messages has been received, via the interface, within the write ACK time period;

when the write threshold number of favorable write response messages has not been received, via the interface, within the write ACK time period, entering a loop that includes;

identifying each DS unit of the set of DS units from which a favorable write response message was not received, via the interface, during the write ACK time period to produce a plurality of identified DS units;

identifying each slice name associated with each of the plurality of identified DS units to produce a plurality of identified slice names;

sending, via the interface, a plurality of retry write request messages to the plurality of identified DS units, wherein a retry write request message of the plurality of retry write request messages includes an encoded data slice of the set of encoded data slices associated with one of the plurality of identified slice names;

determining whether the write threshold number of favorable write response messages has been cumulatively received, via the interface, prior to expiration of a retry write ACK time period; and

when the write threshold number of favorable write response messages has not been cumulatively received, via the interface, prior to expiration of the retry write ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and issuing, via the interface, a plurality of rollback transaction request messages; and

when the write threshold number of favorable write response messages have been cumulatively received, via the interface, prior to expiration of the retry write ACK time period, exiting the loop and issuing, via the interface, a plurality of commit transaction request messages.

10. The computer of claim 8, wherein the processing module further functions to execute the retry write process by:

determining whether a write threshold number but less than the pillar width number of favorable write response messages has been received, via the interface, within the write ACK time period;

when the write threshold number but less than the pillar width number of favorable write response messages have been received, via interface, within the write ACK time period, entering a loop that includes;

identifying a DS unit from which a favorable write response message was not received, via interface, during the write ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

sending, via the interface, a retry write request message to the identified DS unit, wherein the retry write message includes an encoded data slice of the set of encoded data slices associated with the identified slice name;

determining whether the pillar width number of favorable write response messages has been cumulatively received, via the interface, prior to expiration of a retry write ACK time period; and

when the pillar width number of favorable write response messages has not been cumulatively received, via the interface, prior to expiration of the retry write ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and recording the identified slice name for rebuilding; and

when the pillar width number of favorable write response messages have been cumulatively received, via the interface, prior to expiration of the retry write ACK time period, exiting the loop.

11. The computer of claim 8, wherein the processing module further functions to execute the retry commit process by:

determining whether a commit threshold number of favorable commit transaction response messages has been received, via the interface, within the commit ACK time period;

when the commit threshold number of favorable commit transaction response messages has not been received, via the interface, within the commit ACK time period, entering a loop that includes;

identifying each DS unit of the set of DS units from which a favorable commit transaction response message was not received, via the interface, during the commit ACK time period to produce a plurality of identified DS units;

sending, via the interface, a plurality of retry commit transaction request messages to the plurality of identified DS units;

determining whether the commit threshold number of favorable commit transaction response messages has been cumulatively received, via the interface, prior to expiration of a retry commit ACK time period; and

when the commit threshold number of favorable commit transaction response messages has not been cumulatively received, via the interface, prior to expiration of a retry commit ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and issuing a plurality of undo transaction request messages; and

when the commit threshold number of favorable commit transaction response messages have been cumulatively received, via the interface, prior to expiration of the retry commit ACK time period, exiting the loop and issuing, via the interface, a plurality of finalize transaction request messages.

12. The computer of claim 8, wherein the processing module further functions to execute the retry commit process by:

determining whether a commit threshold number but less than the a pillar width number of favorable commit transaction response messages has been received, via the interface, within the commit ACK time period;

when the commit threshold number but less than the pillar width number of favorable commit transaction response messages have been received, via the interface, within the commit ACK time period, entering a loop that includes;

identifying a DS unit from which a favorable commit transaction response message was not received, via the interface, during the commit ACK time period to produce an identified DS unit;

sending, via the interface, a retry commit transaction request message to the identified DS unit;

determining whether the pillar width number of favorable commit transaction response messages has been cumulatively received, via the interface, prior to expiration of a retry commit ACK time period; and

when the pillar width number of favorable commit transaction response messages has not been cumulatively received, via the interface, prior to expiration of the retry commit ACK time period, determining whether a retry threshold has been reached;

when the retry threshold has not been reached, repeating the loop;

when the retry threshold has been reached, exiting the loop and recording an associated slice name for rebuilding; and

when the pillar width number of favorable commit transaction response messages have been cumulatively received, via the interface, prior to expiration of the retry commit ACK time period, exiting the loop.

13. The computer of claim 8, wherein the processing module further functions to execute the retry commit process by:

identifying a DS unit of the set of DS units from which a favorable commit transaction response message was not received, via the interface, during a commit ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

determining whether to execute a retry commit process for the identified DS unit or to execute a retry write-commit process using a foster DS unit for the identified DS unit or using an alternate DS unit in place of the identified DS unit; and

when the retry write-commit process is to be used;

sending, via the interface, a new write request message to the foster DS unit or the alternate DS unit, wherein the new write request message includes an encoded data slice of the set of encoded data slices associated with the identified slice name; and

when a favorable write response message is received, via the interface, from the foster DS unit or the alternate DS unit, sending, via the interface, a new commit transaction request message to the foster DS unit or the alternate DS unit.

14. The computer of claim 8, wherein the processing module further functions to execute the retry write process by:

identifying a DS unit of the set of DS units from which a favorable write response message was not received, via the interface, during the write ACK time period to produce an identified DS unit;

identifying a slice name associated with the identified DS unit to produce an identified slice name;

determining whether to execute the retry write process for the identified DS unit, using a foster DS unit for the identified DS unit, or using an alternate DS unit in place of the identified DS unit; and

when the foster DS unit or the alternate DS unit is to be used, sending, via the interface, a retry write request message to the foster DS unit or the alternate DS unit in accordance with the retry write process, wherein the retry write request message includes an encoded data slice of the set of encoded data slices associated with the identified slice name.