LOCK STEALING WRITES FOR IMPROVED RELIABILITY

• US 20170160941A1
• Filed: 02/14/2017
• Published: 06/08/2017
• Est. Priority Date: 12/05/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Volvovski, Ilya
• Granted Patent: US 10,558,621 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/182 Distributed file systems

Abstract

A method includes sending, by a first computing device, a first set of write requests and sending, by a second computing device, a second set of write requests to a set of storage units. The method further includes receiving, by the first computing device, favorable write responses from a first subset of storage units of the set of storage units and receiving, by the second computing device, favorable write responses from a second subset of storage units. The method further includes determining, by the first computing device, whether a number of the favorable write responses from the first subset of storage units equals or exceeds a write threshold number. When the number of the favorable write responses from the first subset of storage units equals or exceeds the write threshold number, the first computing device sends a set of commit requests to the set of storage units.

Claims

1. A method comprises:

sending, by a first computing device of a dispersed storage network (DSN), a first set of write requests to a set of storage units of the DSN, wherein the first set of write requests is regarding a set of encoded data slices;

sending, by a second computing device of the DSN, a second set of write requests to the set of storage units, wherein the second set of write requests is regarding the set of encoded data slices, wherein the second computing device sends the second set of write requests substantially concurrently with the first computing device sending the first set of write requests;

receiving, by the first computing device, favorable write responses from a first subset of storage units of the set of storage units;

receiving, by the second computing device, favorable write responses from a second subset of storage units of the set of storage units;

determining, by the first computing device, whether a number of the favorable write responses from the first subset of storage units equals or exceeds a write threshold number; and

when the number of the favorable write responses from the first subset of storage units equals or exceeds the write threshold number, sending, by the first computing device, a set of commit requests to the set of storage units.

2. The method of claim 1 further comprises:

when the number of the favorable write responses from the first subset of storage units is less than the write threshold number, sending, by the first computing device, a set of rollback requests to the set of storage units.

3. The method of claim 1 further comprises:

determining, by the second computing device, whether a number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number; and

when the number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number, sending, by the second computing device, a set of commit requests to the set of storage units.

4. The method of claim 1 further comprises:

determining, by the second computing device, whether a number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number; and

when the number of the favorable write responses from the second subset of storage units is less than the write threshold number, sending, by the second computing device, a set of rollback requests to the set of storage units.

5. The method of claim 1 further comprises:

when a storage unit of the set of storage units receives a write request of the first set of write requests prior to receiving a write request of the second set of write requests;

locking, by the storage unit, a write operation for the write request of the first set of write requests;

sending, by the storage unit, a favorable response to the first computing device; and

sending, by the storage unit, an unfavorable response to the second computing device.

6. The method of claim 1 further comprises:

when a storage unit of the set of storage units has a locked write operation for a write request of the first set of write requests and receives a commit request of a set of commit requests from the second computing device prior to receiving a rollback request of a set of rollback requests from the first computing device;

unlocking, by the storage unit, the write operation for the write request of the first set of write requests;

locking, by the storage unit, a write operation for a write request of the second set of write requests;

committing, by the storage unit, the write operation for the write request of the second set of write requests;

deleting, by the storage unit, the write operation for the write request of the first set of write requests; and

sending, by the storage unit, a rollback execution notification to the first computing device.

7. The method of claim 1 further comprises:

when a storage unit of the set of storage units has a locked write operation for a request of the first set of write requests and receives a commit request of a set of commit requests from the second computing device prior to receiving a rollback request of a set of rollback requests from the first computing device;

waiting, by the storage unit, a predetermined amount of time to receive a rollback request of the set of rollback requests from the first computing device; and

when the rollback request is received from the first computing device within the predetermined amount of time or when the rollback request is not received from the first computing device within the predetermined amount of time;

unlocking, by the storage unit, the write operation for the write request of the first set of write requests;

locking, by the storage unit, the write operation for the write request of the second set of write requests;

committing, by the storage unit, the write operation for the write request of the second set of write requests;

deleting, by the storage unit, the write operation for the write request of the first set of write requests; and

sending, by the storage unit, a rollback execution notification to the first computing device.

8. The method of claim 1 further comprises:

when a storage unit of the set of storage units has a locked write operation for a write request of the first set of write requests and receives a rollback request of a set of rollback requests from the first computing device prior to receiving a commit request of a set of commit requests from the second computing device;

waiting, by the storage unit, a predetermined amount of time to receive a commit request of the set of commit requests from the second computing device before executing the rollback request of the set of rollback requests from the first computing device; and

when the commit request of the set of commit requests from the second computing device is received within the predetermined amount of time or when the commit request of the set of commit requests from the second computing device is not received within the predetermined amount of time;

executing, by the storage unit, the rollback request of the set of rollback requests from the first computing device.

9. The method of claim 1 further comprises:

receiving, by the set of storage units, a set of rollback requests from the first computing device and a set of rollback requests from the second computing device;

selecting, by the set of storage units, one of the first computing device and the second computing device as a selected computing device based on a contention resolution policy;

unlocking, by the set of storage units, write operations locked by the unselected computing device;

locking, by the set of storage units, at least a write threshold number of write operations for the selected computing device;

sending, by the set of storage units, requests to send commit requests to the selected computing device;

executing, by the set of storage units, the set of rollback requests from the unselected computing device; and

sending, by the set of storage units, rollback execution notifications to the unselected computing device.

10. A computer readable memory comprises:

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

send a first set of write requests to a set of storage units of the DSN, wherein the first set of write requests is regarding a set of encoded data slices;

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

send a second set of write requests to the set of storage units, wherein the second set of write requests is regarding the set of encoded data slices, wherein the second computing device sends the second set of write requests substantially concurrently with the first computing device sending the first set of write requests;

a third memory element that stores operational instructions that, when executed by the first computing device, causes the first computing device to;

receive favorable write responses from a first subset of storage units of the set of storage units;

a fourth memory element that stores operational instructions that, when executed by the second computing device, causes the second computing device to;

receive favorable write responses from a second subset of storage units of the set of storage units;

a fifth memory element that stores operational instructions that, when executed by the first computing device, causes the first computing device to;

determine whether a number of the favorable write responses from the first subset of storage units equals or exceeds a write threshold number; and

when the number of the favorable write responses from the first subset of storage units equals or exceeds the write threshold number, send a set of commit requests to the set of storage units.

11. The computer readable memory of claim 10, wherein the fifth memory element further stores operational instructions that, when executed by the first computing device, causes the first computing device to:

when the number of the favorable write responses from the first subset of storage units is less than the write threshold number, send a set of rollback requests to the set of storage units.

12. The computer readable memory of claim 10, wherein a sixth memory element that stores operational instructions that, when executed by the second computing device, causes the second computing device to:

determine whether a number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number; and

when the number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number, send a set of commit requests to the set of storage units.

13. The computer readable memory of claim 10, wherein a sixth memory element that stores operational instructions that, when executed by the second computing device, causes the second computing device to:

determine whether a number of the favorable write responses from the second subset of storage units equals or exceeds the write threshold number; and

when the number of the favorable write responses from the second subset of storage units is less than the write threshold number, send a set of rollback requests to the set of storage units.

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

a seventh memory element that stores operational instructions that, when executed by a storage unit of the set of storage units, causes the storage unit to;

when the storage unit receives a write request of the first set of write requests prior to receiving a write request of the second set of write requests;

lock a write operation for the write request of the first set of write requests;

send a favorable response to the first computing device; and

send an unfavorable response to the second computing device.

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

a seventh memory element that stores operational instructions that, when executed by a storage unit of the set of storage units, causes the storage unit to;

when the storage unit of the set of storage units has a locked write operation for the write request of the first set of write requests and receives a commit request of a set of commit requests from the second computing device prior to receiving a rollback request of a set of rollback requests from the first computing device;

unlock the write operation for the write request of the first set of write requests;

lock a write operation for a write request of the second set of write requests;

commit the write operation for the write request of the second set of write requests;

delete the write operation for the write request of the first set of write requests; and

send a rollback execution notification to the first computing device.

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

a seventh memory element that stores operational instructions that, when executed by a storage unit of the set of storage units, causes the storage unit to;

when the storage unit of the set of storage units has a locked write operation for the write request of the first set of write requests and receives a commit request of a set of commit requests from the second computing device prior to receiving a rollback request of a set of rollback requests from the first computing device;

wait a predetermined amount of time to receive a rollback request of the set of rollback requests from the first computing device; and

when the rollback request is received from the first computing device within the predetermined amount of time or when the rollback request is not received from the first computing device within the predetermined amount of time;

unlock the write operation for the write request of the first set of write requests;

lock the write operation for the write request of the second set of write requests;

commit the write operation for the write request of the second set of write requests;

delete the write operation for the write request of the first set of write requests; and

send a rollback execution notification to the first computing device.

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

a seventh memory element that stores operational instructions that, when executed by a storage unit of the set of storage units, causes the storage unit to;

when a storage unit of the set of storage units has a locked write operation for a write request of the first set of write requests and receives a rollback request of a set of rollback requests from the first computing device prior to receiving a commit request of a set of commit requests from the second computing device;

wait a predetermined amount of time to receive a commit request of the set of commit requests from the second computing device before executing the rollback request of the set of rollback requests from the first computing device; and

when the commit request of the set of commit requests from the second computing device is received within the predetermined amount of time or when the commit request of the set of commit requests from the second computing device is not received within the predetermined amount of time;

execute the rollback request of the set of rollback requests from the first computing device.

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

an eighth memory element that stores operational instructions that, when executed by the set of storage units, causes the set of storage units to;

receive a set of rollback requests from the first computing device and a set of rollback requests from the second computing device;

select one of the first computing device and the second computing device as a selected computing device based on a contention resolution policy;

unlock write operations locked by the unselected computing device;

lock at least a write threshold number of write operations for the selected computing device;

send requests to send commit requests to the selected computing device;

execute the set of rollback requests from the unselected computing device; and

send rollback execution notifications to the unselected computing device.