Resolving write request conflicts in a dispersed storage network

• US 9,817,611 B2
• Filed: 11/15/2016
• Issued: 11/14/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:
  US15/352,188
• Publication Number:
  US 20170060480A1
• Time in Patent Office: 364 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 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 includes issuing, by a first computing device, first write requests for a first version of the data object. The method further includes issuing, by a second computing device, second write requests for a second version of the data object. The method further includes sending, by each of a first group of storage units, a first write response to the first and second computing devices. The method further includes sending, by each of a second group of storage units, a second write response to the first and second computing devices. The method further includes determining, by the first and second computing devices, whether a threshold number of first or second write responses were received. When the threshold number of the first write responses were received, the method further includes continuing, by the first computing device, the first write operation and establishing, by the second computing device, a write retry.

Claims

1. A method to resolve conflicts arising from substantially concurrent write requests regarding a data object within dispersed storage network (DSN), the method comprises:

issuing, by a first computing device of the DSN, first write requests regarding a first write operation for a first dispersed storage error encoded version of the data object to storage units of the DSN;

issuing, by a second computing device of the DSN, second write requests regarding a second write operation for a second dispersed storage error encoded version of the data object to the storage units, wherein the first and second write requests are issued substantially concurrently and wherein the storage units receive either the first write request or the second write request before the other one of the first or second write request;

sending, by each of a first group of storage units that received the first write request first, a first write response to the first and second computing devices, wherein the first write response indicates that the first write request has priority;

sending, by each of a second group of storage units that received the second write request first, a second write response to the first and second computing devices, wherein the second write response indicates that the second write request has priority;

determining, by each of the first and second computing devices, whether a threshold number of first write responses or second write threshold responses were received;

when the threshold number of the first write responses were received;

continuing, by the first computing device, the first write operation by issuing commit requests; and

establishing, by the second computing device, a second write request retry time frame for the second write operation.

2. The method of claim 1 further comprises:

generating, by each of the first group of storage units, a first version of the first write response for the first computing device to include information only regarding the first write requests; and

generating, by each of the second group of storage units, a second version of the first write response for the second computing device to include information indicating that the first write requests have priority over the second write requests.

3. The method of claim 1 further comprises:

when the threshold number of the second write responses were received;

continuing, by the second computing device, the second write operation by issuing commit requests; and

establishing, by the first computing device, a first write request retry time frame for the first write operation.

4. The method of claim 1 further comprises:

when the threshold number was not received for either of the first or the write responses;

determining, by the first computing device, that more of the first write responses were received than of the second write responses;

when more of the first write responses were received than of the second write responses, issuing, by the first computing device, retry write requests regarding the first write operation to storage units of the second group of storage units; and

when less of the first write responses were received than of the second write responses, establishing, by the first computing device, a first write request retry time frame for the first write operation.

5. The method of claim 1 further comprises:

when the threshold number was not received for either of the first or the write responses;

determining, by the second computing device, that more of the second write responses were received than of the first write responses;

when more of the second write responses were received than of the first write responses, issuing, by the second computing device, retry write requests regarding the second write operation to storage units of the first group of storage units; and

when less of the second write responses were received than of the first write responses, establishing, by the second computing device, the second write request retry time frame.

6. The method of claim 1 further comprises:

the first write response including a lock indication for the first computing device; and

the second write response including a lock indication for the second computing device.

7. The method of claim 1 further comprises:

when the threshold number was not received for either of the first or the write responses;

determining, by the first computing device, that an equal number of the first and of the second write responses were received; and

when the equal number of the first and of the second write responses were received, determining, by the first computing device, whether the first computing device has a higher priority than the second computing device;

when the first computing device has the higher priority, issuing, by the first computing device, retry write requests regarding the first write operation to storage units of the second group of storage units; and

when the first computing device does not have the higher priority, establishing, by the first computing device, a first write request retry time frame for the first write operation.

8. The method of claim 1 further comprises:

when the threshold number was not received for either of the first or the write responses;

determining, by the second computing device, that an equal number of the first and of the second write responses were received; and

when the equal number of the first and of the second write responses were received, determining, by the second computing device, whether the second computing device has a higher priority than the first computing device;

when the second computing device has the higher priority, issuing, by the second computing device, retry write requests regarding the second write operation to storage units of the second group of storage units; and

when the second computing device does not have the higher priority, establishing, by the second computing device, a second write request retry time frame for the second write operation.

9. A non-transitory computer readable memory comprises:

a first memory section that stores operational instructions that, when executed by a first computing device of a dispersed storage network (DSN), causes the first computing device to;

issue first write requests regarding a first write operation for a first dispersed storage error encoded version of the data object to storage units of the DSN;

a second memory section that stores operational instructions that, when executed by a second computing device of the DSN, causes the second computing device to;

issue second write requests regarding a second write operation for a second dispersed storage error encoded version of the data object to the storage units, wherein the first and second write requests are issued substantially concurrently and wherein the storage units receive either the first write request or the second write request before the other one of the first or second write request;

a third memory section that stores operational instructions that, when executed by each storage unit of a first group of storage units that received the first write request first, causes each storage unit of the first group of storage units to;

send a first write response to the first and second computing devices, wherein the first write response indicates that the first write request has priority;

a fourth memory section that stores operational instructions that, when executed by each storage unit of a second group of storage units that received the second write request first, causes each storage unit of the second group of storage units to;

send a second write response to the first and second computing devices, wherein the second write response indicates that the second write request has priority; and

a fifth memory section that stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to;

determine whether a threshold number of first write responses or second write threshold responses were received;

when the threshold number of the first write responses were received;

continue, by the first computing device, the first write operation by issuing commit requests; and

establish, by the second computing device, a second write request retry time frame for the second write operation.

10. The computer readable memory of claim 9 further comprises:

the third memory section further stores operational instructions that, when executed by each storage unit of a first group of storage units that received the first write request first, causes each storage unit of the first group of storage units to;

generate a first version of the first write response for the first computing device to include information only regarding the first write requests; and

the fourth memory section further stores operational instructions that, when executed by each storage unit of a second group of storage units that received the second write request first, causes each storage unit of the second group of storage units to;

generate a second version of the first write response for the second computing device to include information indicating that the first write requests have priority over the second write requests.

11. The computer readable memory of claim 9, wherein the fifth memory section further stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to:

when the threshold number of the second write responses were received;

continue, by the second computing device, the second write operation by issuing commit requests; and

establish, by the first computing device, a first write request retry time frame for the first write operation.

12. The computer readable memory of claim 9, wherein the fifth memory section further stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to:

when the threshold number was not received for either of the first or the write responses;

determine, by the first computing device, that more of the first write responses were received than of the second write responses;

when more of the first write responses were received than of the second write responses, issue, by the first computing device, retry write requests regarding the first write operation to storage units of the second group of storage units; and

when less of the first write responses were received than of the second write responses, establish, by the first computing device, a first write request retry time frame for the first write operation.

13. The computer readable memory of claim 9, wherein the fifth memory section further stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to:

when the threshold number was not received for either of the first or the write responses;

determine, by the second computing device, that more of the second write responses were received than of the first write responses;

when more of the second write responses were received than of the first write responses, issue, by the second computing device, retry write requests regarding the second write operation to storage units of the first group of storage units; and

when less of the second write responses were received than of the first write responses, establish, by the second computing device, the second write request retry time frame.

14. The computer readable memory of claim 9 further comprises:

the first write response including a lock indication for the first computing device; and

the second write response including a lock indication for the second computing device.

15. The computer readable memory of claim 9, wherein the fifth memory section further stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to:

when the threshold number was not received for either of the first or the write responses;

determine, by the first computing device, that an equal number of the first and of the second write responses were received; and

when the equal number of the first and of the second write responses were received, determine, by the first computing device, whether the first computing device has a higher priority than the second computing device;

when the first computing device has the higher priority, issue, by the first computing device, retry write requests regarding the first write operation to storage units of the second group of storage units; and

when the first computing device does not have the higher priority, establish, by the first computing device, a first write request retry time frame for the first write operation.

16. The computer readable memory of claim 9, wherein the fifth memory section further stores operational instructions that, when executed by each of the first and the second computing devices, causes each of the first and second computing devices to:

when the threshold number was not received for either of the first or the write responses;

determine, by the second computing device, that an equal number of the first and of the second write responses were received; and

when the equal number of the first and of the second write responses were received, determine, by the second computing device, whether the second computing device has a higher priority than the first computing device;

when the second computing device has the higher priority, issue, by the second computing device, retry write requests regarding the second write operation to storage units of the second group of storage units; and

when the second computing device does not have the higher priority, establish, by the second computing device, a second write request retry time frame for the second write operation.