Resolving write request conflicts in a dispersed storage network

• US 9,542,239 B2
• Filed: 03/04/2015
• Issued: 01/10/2017
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Gray, Adam Michael, Resch, Jason K.
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US14/638,654
• Publication Number:
  US 20150317205A1
• Time in Patent Office: 678 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• 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/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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• 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: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method to resolve conflicts arising from substantially concurrent write requests regarding a data object begins by a computing device of a dispersed storage network (DSN) issuing a write request for a dispersed storage error encoded version of the data object to storage units of the DSN. The method continues with the computing device receiving write responses, each including either a lock indication or a non-lock indication and conflict information. The method continues with the computing device determining whether at least a write threshold number of received write responses include the lock indication. When less than the at least a write threshold number of write responses have been received that include the lock indication, the method continues with the computing device processing the conflict information to identify one or more other write requests that have a higher priority than the write request and establishing a write request retry time frame.

Claims

1. A method for execution by a computing device of a dispersed storage network (DSN) to resolve conflicts arising from substantially concurrent write requests regarding a data object, the method comprises:

issuing a write request for a dispersed storage error encoded version of the data object to storage units of the DSN;

receiving, in response to the write request, write responses from at least some of the storage units, wherein each of the write responses includes either;

a lock indication;

or

a non-lock indication and conflict information;

determining whether at least a write threshold number of write responses have been received that include the lock indication; and

when less than the at least a write threshold number of write responses have been received that include the lock indication;

processing the conflict information to identify one or more other write requests of the substantially concurrent write requests that have a higher priority than the write request; and

establishing a write request retry time frame based on the one or more other write requests that have the higher priority.

2. The method of claim 1 further comprises:

at expiration of the write request retry time frame, issuing a retry write request for the dispersed storage error encoded version of the data object;

receiving, in response to the retry write request, retry write responses from at least some of the storage units, wherein each of the retry write responses includes either;

the lock indication;

or

the non-lock indication and updated conflict information;

determining whether at least a write threshold number of retry write responses have been received that include the lock indication; and

when the at least a retry write threshold number of retry write responses have been received that include the lock indication, issuing a commit command to the at least some of the storage units.

3. The method of claim 1, wherein the conflict information from one of the at least some of the storage units comprises one or more of:

identity of a second write request for the dispersed storage error encoded version of the data object issued by a second computing device that has received the lock indication;

identity of the second computing device;

identity of a third write request for the dispersed storage error encoded version of the data object issued by a third computing device that did not receive the lock indication;

identity of the third computing device; and

information regarding write request processing characteristics of the one of the at least some of the storage units.

4. The method of claim 1, wherein the processing the conflict information to identify the one or more other write requests that have a higher priority comprises:

determining that, in response to each of the one or more other write requests, a greater number of lock indications were received than were received for the write request.

5. The method of claim 1, wherein the processing the conflict information to identify the one or more other write requests that have a higher priority comprises:

determining that, in response to one of the one or more other write requests, an equal number of lock indications were received as were received for the write request; and

executing a retry tie-breaking protocol when the equal number of lock indications were received for the one of the one or more other write requests as were received for the write request.

6. The method of claim 5, wherein the retry tie-breaking protocol comprises:

granting priority to the one of the one or more other write requests when another computing device associated with the one of the one or more other write requests has a higher device priority than the computing device.

7. The method of claim 5, wherein the retry tie-breaking protocol comprises:

interpreting the conflict information from the storage units of the at least some of the storage units that did not provide the lock indication to the write request of the computing device or to the one or more other write requests of the other computing devices to determine a retry priority between the write request and the one or more other write requests.

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

at least one memory section that stores operational instructions that, when executed by one or more processing modules of a computing device of a dispersed storage network (DSN) to resolve conflicts arising from substantially concurrent write requests regarding a data object, causes the computing device to;

issue a write request for a dispersed storage error encoded version of the data object to storage units of the DSN;

receive, in response to the write request, write responses from at least some of the storage units, wherein each of the write responses includes either;

a lock indication;

or

a non-lock indication and conflict information;

determine whether at least a write threshold number of write responses have been received that include the lock indication; and

when less than the at least a write threshold number of write responses have been received that include the lock indication;

process the conflict information to identify one or more other write requests of the substantially concurrent write requests that have a higher priority than the write request; and

establish a write request retry time frame based on the one or more other write requests that have the higher priority.

9. The computer readable storage medium of claim 8 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the computing device of the DSN to;

at expiration of the write request retry time frame, issue a retry write request for the dispersed storage error encoded version of the data object;

receive, in response to the retry write request, retry write responses from at least some of the storage units, wherein each of the retry write responses includes either;

the lock indication;

or

the non-lock indication and updated conflict information;

determine whether at least a write threshold number of retry write responses have been received that include the lock indication; and

when the at least a retry write threshold number of retry write responses have been received that include the lock indication, issue a commit command to the at least some of the storage units.

10. The computer readable storage medium of claim 8, wherein the conflict information from one of the at least some of the storage units comprises one or more of:

identity of a second write request for the dispersed storage error encoded version of the data object issued by a second computing device that has received the lock indication;

identity of the second computing device;

identity of a third write request for the dispersed storage error encoded version of the data object issued by a third computing device that did not receive the lock indication;

identity of the third computing device; and

information regarding write request processing characteristics of the one of the at least some of the storage units.

11. The computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the computing device of the DSN to process the conflict information to identify the one or more other write requests that have a higher priority by:

determining that, in response to each of the one or more other write requests, a greater number of lock indications were received than were received for the write request.

12. The computer readable storage medium of claim 8, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the computing device of the DSN to process the conflict information to identify the one or more other write requests that have a higher priority by:

determining that, in response to one of the one or more other write requests, an equal number of lock indications were received as were received for the write request; and

executing a retry tie-breaking protocol when the equal number of lock indications were received for the one of the one or more other write requests as were received for the write request.

13. The computer readable storage medium of claim 12, wherein the retry tie-breaking protocol comprises:

granting priority to the one of the one or more other write requests when another computing device associated with the one of the one or more other write requests has a higher device priority than the computing device.

14. The computer readable storage medium of claim 12, wherein the retry tie-breaking protocol comprises:

interpreting the conflict information from the storage units of the at least some of the storage units that did not provide the lock indication to the write request of the computing device or to the one or more other write requests of the other computing devices to determine a retry priority between the write request and the one or more other write requests.

15. A computing device of a group of computing devices of a dispersed storage network (DSN), the computing device comprises:

an interface;

a local memory; and

a processing module operably coupled to the interface and the local memory, wherein the processing module functions to;

issue, via the interface, a write request for a dispersed storage error encoded version of a data object to storage units of the DSN, wherein substantially concurrent write requests regarding the data object includes the write request;

receive, via the interface in response to the write request, write responses from at least some of the storage units, wherein each of the write responses includes either;

a lock indication;

or

a non-lock indication and conflict information;

determine whether at least a write threshold number of write responses have been received that include the lock indication; and

when less than the at least a write threshold number of write responses have been received that include the lock indication;

process the conflict information to identify one or more other write requests of the substantially concurrent write requests that have a higher priority than the write request; and

establish a write request retry time frame based on the one or more other write requests that have the higher priority.

16. The computing device of claim 15, wherein the processing module further functions to:

at expiration of the write request retry time frame, issue, via the interface, a retry write request for the dispersed storage error encoded version of the data object;

receive, via the interface in response to the retry write request, retry write responses from at least some of the storage units, wherein each of the retry write responses includes either;

the lock indication;

or

the non-lock indication and updated conflict information;

determine whether at least a write threshold number of retry write responses have been received that include the lock indication; and

when the at least a retry write threshold number of retry write responses have been received that include the lock indication, issue, via the interface, a commit command to the at least some of the storage units.

17. The computing device of claim 15, wherein the conflict information from one of the at least some of the storage units comprises one or more of:

identity of a second write request for the dispersed storage error encoded version of the data object issued by a second computing device that has received the lock indication;

identity of the second computing device;

identity of a third write request for the dispersed storage error encoded version of the data object issued by a third computing device that did not receive the lock indication;

identity of the third computing device; and

information regarding write request processing characteristics of the one of the at least some of the storage units.

18. The computing device of claim 15, wherein the processing module functions to process the conflict information to identify the one or more other write requests that have a higher priority by:

determining that, in response to each of the one or more other write requests, a greater number of lock indications were received than were received for the write request.

19. The computing device of claim 15, wherein the processing module functions to process the conflict information to identify the one or more other write requests that have a higher priority by:

determining that, in response to one of the one or more other write requests, an equal number of lock indications were received as were received for the write request; and

executing a retry tie-breaking protocol when the equal number of lock indications were received for the one of the one or more other write requests as were received for the write request.

20. The computing device of claim 19, wherein the retry tie-breaking protocol comprises:

granting priority to the one of the one or more other write requests when another computing device associated with the one of the one or more other write requests has a higher device priority than the computing device.

21. The computing device of claim 19, wherein the retry tie-breaking protocol comprises:

interpreting the conflict information from the storage units of the at least some of the storage units that did not provide the lock indication to the write request of the computing device or to the one or more other write requests of the other computing devices to determine a retry priority between the write request and the one or more other write requests.