Resolving write conflicts in a dispersed storage network

• US 9,274,908 B2
• Filed: 01/13/2014
• Issued: 03/01/2016
• Est. Priority Date: 02/26/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew, Resch, Jason K.
• Primary Examiner(s): Homayounmehr, Farid
• Assistant Examiner(s): Torres-Diaz, Lizbeth
• Application Number:
  US14/153,366
• Publication Number:
  US 20140245063A1
• Time in Patent Office: 778 Days
• US Class Current: 1/1
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• 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]

Abstract

A method begins by first and second client devices transmitting first and second sets of write requests to storage units. The method continues with a storage unit sending a write response message to the first and second client devices, where the write response message indicates a storage unit score value for one of the client devices. The method continues with the first and second client devices interpreting the storage unit score values from the storage units to determine which client device has write priority. The method continues with the client device that has the write priority sending a set of next-phase write requests to the storage units. The method continues with the other client device that does not have the write priority sending a set of rollback requests to the storage units.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

transmitting, by a first client device, a first set of write requests regarding a first set of encoded data slices to storage units of the DSN, wherein the first client device dispersed storage error encoded a data object to produce the first set of encoded data slices;

transmitting, by a second client device and nearly concurrently with the transmitting by the first client device, a second set of write requests regarding a second set of encoded data slices to the storage units, wherein the second client device dispersed storage error encoded the data object to produce the second set of encoded data slices;

for a storage unit of the storage units;

receiving one of the first set of write requests before one of the second set of write requests or receiving the one of the second set of write requests before the one of the first set of write requests;

when the one of the first set of write requests is received before the one of the second set of write requests;

generating a first write response message that includes an indication that the data object is locked for the first client device and a storage unit score value;

sending the first write response message to the first client device in response to receiving the one of the first set of write requests; and

sending the first write response message to the second client device in response to receiving the one of the second set of write requests;

when the one of the second set of write requests is received before the one of the first set of write requests;

generating a second write response message that includes an indication that the data object is locked for the second client device and the storage unit score value;

sending the second write response message to the first client device in response to receiving the one of the first set of write requests; and

sending the second write response message to the second client device in response to receiving the one of the second set of write requests;

receiving, by the first client device, first and second write response messages from the storage units;

interpreting, by the first client device, storage unit score values of the received first and second write response messages to determine whether the first client device has write priority over the second client device; and

when the first client device has the write priority over the second client device, sending, by the first client device, a set of next-phase write requests regarding the data object to the storage units.

2. The method of claim 1 further comprises:

when the first client device does not have the write priority over the second client device, sending, by the first client device, a set of rollback requests regarding the data object to the storage units such that the storage units cancel the first set of write requests.

3. The method of claim 1 further comprises:

receiving, by the second client device, the first and second write response messages from the storage units;

interpreting, by the second client device, the storage unit score values of the received first and second write response messages to determine whether the second client device has the write priority over the first client device; and

when the second client device has the write priority over the first client device, sending, by the second client device, the set of next-phase write requests regarding the data object to the storage units.

4. The method of claim 3 further comprises:

when the second client device does not have the write priority over the first client device, sending, by the second client device, a set of rollback requests regarding the data object to the storage units such that the storage units cancel the second set of write requests.

5. The method of claim 1, wherein the interpreting the storage unit score values of the received first and second write response messages further comprises:

mathematically processing the storage unit score values of the received first and second write response messages to determine whether the first client device has the write priority over the second client device, wherein each of the storage units is assigned a storage value that, when mathematically processing, avoids a priority tie between the first and second client devices.

6. The method of claim 1, wherein the interpreting the storage unit score values of the received first and second write response messages further comprises:

mathematically processing the storage unit score values of the received first and second write response messages to produce a first client device score and a second client device score;

when the first client device score compares favorably to the second client device score, indicating that the first client device has the write priority over the second client device; and

when the first client device score substantially equals the second client device score, applying a tie-breaker mechanism to determine which of the first and second client devices has the write priority.

7. The method of claim 1 further comprises:

temporarily storing, by the storage unit, one of the first set of encoded data slices when the one of the first set of write requests is received; and

temporarily storing, by the storage unit, one of the second set of encoded data slices when the one of the second set of write requests is received.

8. The method of claim 7 further comprises:

in response to receiving one of the set of next-phase write requests, continuing, by the storage unit, with a write process of permanently storing the one of the first set of encoded data slices; and

in response to receiving one of a set of rollback requests, deleting, by the storage unit, the one of the second set of encoded data slices that was temporarily stored.

9. The method of claim 7 further comprises:

in response to receiving one of a second set of next-phase write requests from the second client device, continuing, by the storage unit, with a write process of permanently storing the one of the second set of encoded data slices; and

in response to receiving one of a set of rollback requests from the first client device, deleting, by the storage unit, the one of the first set of encoded data slices that was temporarily stored.

10. A memory module of a dispersed storage network (DSN), the memory module comprises:

a first storage device that stores operational instructions that, when executed by a first client device or a second client device, causes the first client device or the second client device to;

transmit, as the first client device, a first set of write requests regarding a first set of encoded data slices to storage units of the DSN, wherein the first client device dispersed storage error encoded a data object to produce the first set of encoded data slices;

transmit, as the second client device and nearly concurrently with the transmitting by the first client device, a second set of write requests regarding a second set of encoded data slices to the storage units, wherein the second client device dispersed storage error encoded the data object to produce the second set of encoded data slices;

a second storage device that stores operational instructions that, when executed by a storage unit, causes the storage unit to;

determine whether one of the first set of write requests was received before one of the second set of write requests or whether the one of the second set of write requests was received before the one of the first set of write requests;

when the one of the first set of write requests is received before the one of the second set of write requests;

generate a first write response message that includes an indication that the data object is locked for the first client device and a storage unit score value;

send the first write response message to the first client device in response to receiving the one of the first set of write requests; and

send the first write response message to the second client device in response to receiving the one of the second set of write requests;

when the one of the second set of write requests is received before the one of the first set of write requests;

generate a second write response message that includes an indication that the data object is locked for the second client device and the storage unit score value;

send the second write response message to the first client device in response to receiving the one of the first set of write requests; and

send the second write response message to the second client device in response to receiving the one of the second set of write requests; and

a third storage device that stores operational instructions that, when executed by the first client device or the second client device, causes the first client device or the second client device to;

interpret storage unit score values of received first and second write response messages to determine whether the first client device has write priority over the second client device; and

when the first client device has the write priority over the second client device, send, as the first client device, a set of next-phase write requests regarding the data object to the storage units.

11. The memory module of claim 10 further comprises:

the third storage device further stores operational instructions that, when executed by the first client device or the second client device, further causes the first client device or the second client device to;

when the first client device does not have the write priority over the second client device, send, as the first client device, a set of rollback requests regarding the data object to the storage units such that the storage units cancel the first set of write requests.

12. The memory module of claim 10 further comprises:

the third storage device further stores operational instructions that, when executed by the first client device or the second client device, further causes the first client device or the second client device to;

receive, as the second client device, first and second write response messages from the storage units;

interpret, as the second client device, the storage unit score values of the received first and second write response messages to determine whether the second client device has the write priority over the first client device; and

when the second client device has the write priority over the first client device, send, as the second client device, the set of next-phase write requests regarding the data object to the storage units.

13. The memory module of claim 12 further comprises:

the third storage device further stores operational instructions that, when executed by the first client device or the second client device, further causes the first client device or the second client device to;

when the second client device does not have the write priority over the first client device, send, as the second client device, a set of rollback requests regarding the data object to the storage units such that the storage units cancel the second set of write requests.

14. The memory module of claim 10, wherein the operational instructions that, when executed by the first client device or the second client device, causes the first client device or the second client device to interpret the storage unit score values of the received first and second write response messages by:

mathematically processing the storage unit score values of the received first and second write response messages to determine whether the first client device has the write priority over the second client device, wherein each of the storage units is assigned a storage value that, when mathematically processing, avoids a priority tie between the first and second client devices.

15. The memory module of claim 10, wherein the operational instructions that, when executed by the first client device or the second client device, causes the first client device or the second client device to interpret the storage unit score values of the received first and second write response messages by:

mathematically processing the storage unit score values of the received first and second write response messages to produce a first client device score and a second client device score;

when the first client device score compares favorably to the second client device score, indicating that the first client device has the write priority over the second client device; and

when the first client device score substantially equals the second client device score, applying a tie-breaker mechanism to determine which of the first and second client devices has the write priority.

16. The memory module of claim 10 further comprises:

the second storage device further stores operational instructions that, when executed by the storage unit, further causes the storage unit to;

temporarily store, by the storage unit, one of the first set of encoded data slices when the one of the first set of write requests is received; and

temporarily store, by the storage unit, one of the second set of encoded data slices when the one of the second set of write requests is received.

17. The memory module of claim 16 further comprises:

the second storage device further stores operational instructions that, when executed by the storage unit, further causes the storage unit to;

in response to receiving one of the set of next-phase write requests, continue, by the storage unit, with a write process of permanently storing the one of the first set of encoded data slices; and

in response to receiving one of a set of rollback requests, delete, by the storage unit, the one of the second set of encoded data slices that was temporarily stored.

18. The memory module of claim 16 further comprises:

the second storage device further stores operational instructions that, when executed by the storage unit, further causes the storage unit to;

in response to receiving one of a second set of next-phase write requests from the second client device, continue, by the storage unit, with a write process of permanently storing the one of the second set of encoded data slices; and

in response to receiving one of a set of rollback requests from the first client device, delete, by the storage unit, the one of the first set of encoded data slices that was temporarily stored.