DISTRIBUTED STORAGE TIMESTAMPED REVISIONS

• US 20110106855A1
• Filed: 07/16/2010
• Published: 05/05/2011
• Est. Priority Date: 10/29/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Leggette, Wesley, Baptist, Andrew
• Granted Patent: US 8,732,206 B2
• Time in Patent Office: Days
• US Class Current: 707/793
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 12/00 Data switching networks interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• 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: H04L 9/3247 involving digital signatures

Abstract

Various revisions of encoded data slices stored in a distributed storage system can be time stamped to assist in retrieving desired data revisions. Each of the multiple revisions of the encoded data slices may have the same name, but different revision numbers. An encoded data slice, which is received at a distributed storage unit along with a write command, slice name, and the revision number, is time stamped. The timestamp and revision number are stored in conjunction with the data slice. A desired encoded data slice can be retrieved by sending a read command, slice name, and timeframe to the distributed storage unit. The appropriate encoded data slice can be retrieved by determining which revision number has a timestamp most closely matching the requested timeframe.

Claims

1. A method for use in a distributed storage unit configured to store data slices, the data slices encoded to prevent recovery of a data object using a single encoded data slice, but allow recovery of the data object using at least a threshold number of differently encoded data slices, the method comprising:

storing a plurality of encoded data slices having a common slice name, but different revision numbers;

receiving a read command indicating the common slice name and a requested timeframe;

identifying a selected one of the plurality of encoded data slices having a revision number most nearly correlated to the requested timeframe; and

transmitting a response to the read command including the selected one of the plurality of encoded data slices.

2. The method of claim 1, further comprising:

storing time stamps associated with each revision of the plurality of encoded data slices; and

determining a time stamp most nearly correlated to the requested timeframe.

3. The method of claim 2, wherein none of the time stamps fall within the requested timeframe.

4. The method of claim 1, further comprising:

receiving a received encoded data slice having a slice name and a revision number;

receiving a write command indicating that the received encoded data slice is to be stored;

determining a time stamp associated with the received encoded data slice and the revision number; and

storing the received encoded data slice, the revision number, and the time stamp.

5. The method of claim 1, further comprising:

receiving a delete command indicating, by slice name and revision number, one of the plurality of encoded data slices to be deleted;

determine a timestamp associated with the delete command;

appending the timestamp and a delete marker to the one of the plurality of encoded data slices indicated by the delete command to generate a marked slice; and

storing the marked slice.

6. The method of claim 5, further comprising:

deleting the marked slice based on availability of system resources.

7. A method comprising:

receiving a first encoded data slice having a slice name and a first revision number, the first encoded data slice representing one of a first plurality of differently encoded data slices generated from a first revision of a data portion, the first plurality of differently encoded data slices encoded to prevent recovery of the first revision of the data portion using a single encoded data slice, and to permit recovery of the first revision of the data portion using at least a threshold number of the first plurality of differently encoded data slices;

determining a first time stamp associated with the first encoded data slice;

storing the first encoded data slice and the first time stamp;

receiving a second encoded data slice having the same slice name as the first encoded data slice and a second revision number, the second encoded data slice representing one of a second plurality of differently encoded data slices generated from a second revision of a data portion, the second plurality of differently encoded data slices encoded to prevent recovery of the second revision of the data portion using a single encoded data slice, and to permit recovery of the second revision of the data portion using at least a threshold number of the second plurality of differently encoded data slices;

determining a second time stamp associated with the second encoded data slice;

storing the second encoded data slice and the second time stamp.

8. The method of claim 7, further comprising:

receiving a read command, the slice name, and a timeframe;

determining which of the first time stamp and the second time stamp more closely matches the timeframe;

based on the determining, selecting one of the first encoded data slice and the second encoded data slice as a matching slice; and

transmitting the matching slice in response to the read command.

9. The method of claim 8, wherein both the first time stamp and the second time stamp are outside the timeframe.

10. The method of claim 7, further comprising:

receiving a delete command identifying one of the first encoded data slice and the second encoded data slice as an identified slice;

determining a third timestamp corresponding to a time associated with the delete command;

appending the third timestamp and a delete marker to the identified slice to generate a marked slice; and

storing the marked slice.

11. A distributed storage unit comprising:

at least one memory to store a plurality of encoded data slices having a common slice name, but different revision numbers, the data slices encoded to prevent recovery of a data object using a single encoded data slice, but allow recovery of the data object using at least a threshold number of differently encoded data slices;

an interface to receive a read command indicating the common slice name and a requested timeframe;

a processor to identify a selected one of the plurality of encoded data slices having a revision number most nearly correlated to the requested timeframe; and

the interface further to transmit a response to the read command including the selected one of the plurality of encoded data slices.

12. The distributed storage unit of claim 11, further comprising:

the memory further to store time stamps associated with each revision of the plurality of encoded data slices; and

the processor further to determine a time stamp most nearly correlated to the requested timeframe.

13. The distributed storage unit of claim 12, wherein none of the time stamps fall within the requested timeframe.

14. The distributed storage unit of claim 11, further comprising:

the interface further to;

receive a received encoded data slice having a slice name and a revision number;

receive a write command indicating that the received encoded data slice is to be stored;

the processor further to determine a time stamp associated with the received encoded data slice and the revision number; and

the memory further to store the received encoded data slice, the revision number, and the time stamp.

15. The distributed storage unit of claim 11, further comprising:

the interface to receive a delete command indicating, by slice name and revision number, one of the plurality of encoded data slices to be deleted;

the processor further to;

determine a timestamp associated with the delete command;

append the timestamp and a delete marker to the one of the plurality of encoded data slices indicated by the delete command to generate a marked slice; and

the memory further to store the marked slice.

16. The distributed storage unit of claim 15, further comprising:

the processor further to delete the marked slice based on availability of system resources.

17. A distributed storage unit comprising:

an interface to receive a first encoded data slice having a slice name and a first revision number, the first encoded data slice representing one of a first plurality of differently encoded data slices generated from a first revision of a data portion, the first plurality of differently encoded data slices encoded to prevent recovery of the first revision of the data portion using a single encoded data slice, and to permit recovery of the first revision of the data portion using at least a threshold number of the first plurality of differently encoded data slices;

a processor to determine a first time stamp associated with the first encoded data slice;

a memory to store the first encoded data slice and the first time stamp;

the interface further to receive a second encoded data slice having the same slice name as the first encoded data slice and a second revision number, the second encoded data slice representing one of a second plurality of differently encoded data slices generated from a second revision of a data portion, the second plurality of differently encoded data slices encoded to prevent recovery of the second revision of the data portion using a single encoded data slice, and to permit recovery of the second revision of the data portion using at least a threshold number of the second plurality of differently encoded data slices;

the processor further to determine a second time stamp associated with the second encoded data slice;

the memory further to store the second encoded data slice and the second time stamp.

18. The distributed storage unit of claim 17, further comprising:

the interface further to receive a read command, the slice name, and a timeframe;

the processor further to;

determine which of the first time stamp and the second time stamp more closely matches the timeframe and generate a result;

select one of the first encoded data slice and the second encoded data slice as a matching slice based on the result; and

the interface further to transmit the matching slice in response to the read command.

19. The distributed storage unit of claim 18, wherein both the first time stamp and the second time stamp are outside the timeframe.

20. The distributed storage unit of claim 17, further comprising:

the interface further to receive a delete command identifying one of the first encoded data slice and the second encoded data slice as an identified slice;

the processor further to;

determine a third timestamp corresponding to a time associated with the delete command;

append the third timestamp and a delete marker to the identified slice to generate a marked slice; and

the memory further to store the marked slice.