Directory synchronization of a dispersed storage network

• US 8,856,552 B2
• Filed: 10/13/2010
• Issued: 10/07/2014
• Est. Priority Date: 03/31/2008
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Baptist, Andrew, Leggette, Wesley, Volvovski, Ilya, Resch, Jason K., Cilfone, Bart
• Primary Examiner(s): Le, Vu
• Assistant Examiner(s): Mangialaschi, Tracy
• Application Number:
  US12/903,205
• Publication Number:
  US 20110161681A1
• Time in Patent Office: 1,455 Days
• Field of Search: 713/193, 711/E12.092
• US Class Current: 713/193
• CPC Class Codes: G06F 11/0745 in an input/output transactions management context input/output processing in general G06F13/00
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A method begins by a processing module dispersed storage error encoding data to produce a set of encoded data slices and generating a transaction identifier regarding storage of the set of encoded data slices. The method continues with the processing module outputting a plurality of write request messages to a plurality of dispersed storage (DS) units, wherein each of the plurality of write request messages includes the transaction identifier and a corresponding one of the set of encoded data slices. The method continues with the processing module receiving write response messages from at least some of the DS units, wherein each of the write response messages includes a reference to the transaction identifier. The method continues with the processing module updating directory information regarding storage of the data to produce updated directory information when at least a write threshold number of the write response messages have been received.

Claims

1. A method comprises:

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

generating a first transaction identifier regarding storage of the set of encoded data slices;

outputting a plurality of write request messages to a plurality of dispersed storage (DS) units, wherein each of the plurality of write request messages includes the first transaction identifier and at least a corresponding one of the set of encoded data slices;

receiving write response messages from at least some of the DS units, wherein each of the write response messages includes a reference to the first transaction identifier;

when at least a write threshold number of the write response messages have been received, updating directory information regarding storage of the data to produce updated directory information;

dispersed storage error encoding the updated directory information to produce a set of encoded directory slices;

generating a second transaction identifier regarding storage of the set of encoded directory slices;

outputting a second plurality of write request messages to the plurality of DS units or to a second plurality of DS units, wherein each of the second plurality of write request messages includes the second transaction identifier and a corresponding one of the set of encoded directory slices;

when at least a second write threshold number of second write response messages have been received within a time period, outputting a plurality of commit request messages regarding the set of encoded data slices and the set of encoded directory slices to the plurality of DS units or to the second plurality of DS units, wherein each of the plurality of commit request messages includes the first and second transaction identifiers; and

when the second write threshold number of second write response messages have not been received within the time period;

re-updating the directory information regarding storage of the data;

re-dispersed error encoding the directory information to reproduce a second set of encoded directory slices; and

outputting at least some of the second plurality of write request messages regarding the reproduced second set of encoded directory slices.

2. The method of claim 1, wherein generating the first transaction identifier or generating the second transaction identifier comprises at least one of:

utilizing a coordinated universal time;

utilizing a random number generator output;

performing a function based on at least one of a previous transaction identifier, a previous second transaction identifier;

performing a second function on the first transaction identifier to generate the second transaction identifier.

3. The method of claim 1, wherein one of the write response messages or one of the second write response messages comprises at least one of:

an operation succeeded status code;

a transaction conflict status code;

an addressing error status code;

a check condition status code; and

an unauthorized status code.

4. The method of claim 1 further comprises:

outputting the second plurality of write request messages to the plurality of DS units, wherein each of the second plurality of write request messages further includes an expected slice revision; and

interpreting the second write response messages for confirmation of the expected slice revision; and

when at least a second write threshold number of second write response messages have confirmed the expected slice revision, outputting the plurality of commit request messages regarding the set of encoded data slices and the set of encoded directory slices to the plurality of DS units.

5. The method of claim 4 further comprises:

outputting a plurality of read request messages that includes a plurality of slice names corresponding to the updated directory information;

receiving a plurality of read response messages that include a slice revision; and

establishing the expected slice revision as the slice revision.

6. The method of claim 1 further comprises at least one of:

when the write threshold number of write response messages have not been received within a time period, outputting a plurality of rollback transaction request messages to the plurality of DS units, wherein each of the plurality of rollback transaction request messages includes the first transaction identifier; and

receiving at least one of the write response messages having an unfavorable response and, when a number of write response messages having the unfavorable response exceeds a second threshold, outputting the plurality of rollback transaction request messages to the plurality of DS units.

7. A computer comprises:

an interface;

memory; and

a hardware processing module coupled to the memory and the interface, wherein the hardware processing module is operable to;

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

generate a first transaction identifier regarding storage of the set of encoded data slices;

output, via the interface, a plurality of write request messages to a plurality of dispersed storage (DS) units, wherein each of the plurality of write request messages includes the first transaction identifier and at least a corresponding one of the set of encoded data slices;

receive, via the interface, write response messages from at least some of the DS units, wherein each of the write response messages includes a reference to the first transaction identifier;

update directory information regarding storage of the data to produce updated directory information when at least a write threshold number of the write response messages have been received;

dispersed storage error encode the updated directory information to produce a set of encoded directory slices;

generate a second transaction identifier regarding storage of the set of encoded directory slices;

output, via the interface, a second plurality of write request messages to the plurality of DS units or a second plurality of DS units, wherein each of the second plurality of write request messages includes the second transaction identifier and a corresponding one of the set of encoded directory slices;

when at least a second write threshold number of second write response messages have been received within a time period, output, via the interface, a plurality of commit request messages regarding the set of encoded data slices and the set of encoded directory slices to the plurality of DS units or to the second plurality of DS units, wherein each of the plurality of commit request messages includes the first and second transaction identifiers; and

when the second write threshold number of second write response messages have not been received within the time period;

re-update the directory information regarding storage of the data;

re-dispersed error encode the directory information to reproduce a second set of encoded directory slices; and

output, via the interface, at least some of the second plurality of write request messages regarding the reproduced second set of encoded directory slices.

8. The computer of claim 7, wherein the hardware processing module further functions to generate the first transaction identifier or generate the second transaction identifier by at least one of:

utilizing a coordinated universal time;

utilizing a random number generator output;

performing a function based on at least one of a previous transaction identifier, a previous second transaction identifier;

performing a second function on the first transaction identifier to generate the second transaction identifier.

9. The computer of claim 7, wherein one of the write response messages or one of the second write response messages comprises at least one of:

an operation succeeded status code;

a transaction conflict status code;

an addressing error status code;

a check condition status code; and

an unauthorized status code.

10. The computer of claim 7, wherein the hardware processing module further functions to:

output, via the interface, the second plurality of write request messages to the plurality of DS units, wherein each of the second plurality of write request messages further includes an expected slice revision; and

interpret the second write response messages for confirmation of the expected slice revision; and

output, via the interface, the plurality of commit request messages regarding the set of encoded data slices and the set of encoded directory slices to the plurality of DS units when at least a second write threshold number of second write response messages have confirmed the expected slice revision.

11. The computer of claim 10, wherein the hardware processing module further functions to:

output, via the interface, a plurality of read request messages that includes a plurality of slice names corresponding to the updated directory information;

receive, via the interface, a plurality of read response messages that include a slice revision; and

establish the expected slice revision as the slice revision.

12. The computer of claim 7, wherein the hardware processing module further functions to perform at least one of:

outputting, via the interface, a plurality of rollback transaction request messages to the plurality of DS units, wherein each of the plurality of rollback transaction request messages includes the first transaction identifier when the write threshold number of write response messages have not been received within a time period; and

receiving, via the interface, at least one of the write response messages having an unfavorable response and, when a number of write response messages having the unfavorable response exceeds a second threshold, outputting the plurality of rollback transaction request messages to the plurality of DS units.