Distribution of unique copies of broadcast data utilizing fault-tolerant retrieval from dispersed storage

• US 9,661,356 B2
• Filed: 05/28/2014
• Issued: 05/23/2017
• Est. Priority Date: 10/29/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Leggette, Wesley, Holmes, Alan E., Grube, Gary W., Markison, Timothy W., Gladwin, S. Christopher, Resch, Jason K.
• Primary Examiner(s): RABOVIANSKI, JIVKA A
• Application Number:
  US14/289,064
• Publication Number:
  US 20140282763A1
• Time in Patent Office: 1,091 Days
• Field of Search: 725 32, 725 34, 725 38, 725 44, 725 46, 725 91, 725 98, 725118
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/356 Unequal error protection [UEP]
• CPC Class Codes: H04N 21/2181 comprising remotely distributed storage units, e.g. when movies are replicated over a plurality of video servers distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/25816 involving client authentication restricting access to computer systems by authenticating users using a predetermined code G06F21/33; cryptographic authentication protocols H04L9/32; networks authentication protocols H04L63/08; authentication in wireless network security H04W12/06
• CPC Class Codes: H04N 21/25875 involving end-user authentication restricting access to computer systems by authenticating users using a predetermined code G06F21/33; arrangements for secret or secure communication including means for verifying the identity or authority of a user of the system H04L9/32; networks authentication protocols H04L63/08; authentication in wireless network security H04W12/06
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

A broadcast of data is stored as a plurality of sets of encoded data slices stored using an error coding dispersal storage function. In response to receiving a playback request, a centralized digital video recorder (DVR) identifies a first unique combination of encoded data slices, and determines whether that combination of data slices is available for retrieval. If the data slices are available, they are retrieved. If the data slices are not available, another unique combination of encoded data slices of the plurality of sets of encoded data slices is identified and retrieved, instead. Both combinations of data slices can be used to recreate a unique copy of broadcast data.

Claims

1. A method for execution by a dispersed storage processing module, the method comprises:

storing a broadcast of data in accordance with an error coding dispersal storage function, wherein the broadcast of data is stored as a plurality of sets of encoded data slices and wherein encoding the broadcast of data via the error coding dispersal storage function facilitates error-free decoding of the broadcast of data via decoding of a threshold number of encoded data slices that is less than a total number of the plurality of sets of encoded data slices, wherein the threshold number of encoded data slices can be any combination of encoded data slices from the plurality of sets of encoded data slices;

receiving, from a requesting unit, a playback request for the broadcast of data;

in response to the playback request;

determining a first unique combination of encoded data slices of the plurality of sets of encoded data slices as a first subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices;

determining whether the first unique combination of encoded data slices is available for retrieval, based on a number of the first unique combination of encoded data slices available for retrieval including at least the threshold number of encoded data slices;

when the first unique combination is available;

retrieving, as a unique copy of the broadcast data, the first unique combination of encoded data slices; and

transmitting the first unique combination of encoded data slices to the requesting unit;

when the first unique combination is not available because the number of the first unique combination of encoded data slices available for retrieval is less than the threshold number of encoded data slices;

determining a second unique combination of encoded data slices of the plurality of sets of encoded data slices to be retrieved as a second subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices, wherein the second subset of encoded data slices is different from the first subset;

retrieving, as the unique copy of the broadcast data, the second unique combination of encoded data slices; and

transmitting the second unique combination of encoded data slices to the requesting unit.

2. The method of claim 1, wherein determining the first unique combination of encoded data slices comprises selecting one of a plurality of combinations of encoded data slices assigned to the requesting unit.

3. The method of claim 2, wherein determining the second unique combination of encoded data slices comprises selecting a different one of the plurality of combinations of encoded data slices assigned to the requesting unit.

4. The method of claim 1, wherein determining the first unique combination of encoded data slices comprises selecting a combination of encoded data slices assigned to the requesting unit.

5. The method of claim 4, wherein determining the second unique combination of encoded data slices comprises selecting the second subset of encoded data slices of the plurality of sets of encoded data slices.

6. The method of claim 1, wherein:

the plurality of sets of encoded data slices include an encoded data slice stored in a first pillar corresponding to a first distributed storage (DS) unit; and

determining the second unique combination of encoded data slices includes selecting the second subset to exclude any data slice stored in the first pillar corresponding to the first DS storage unit.

7. The method of claim 1, wherein determining whether the first unique combination is available for retrieval includes determining whether a distributed storage (DS) unit storing at least one encoded data slice of the first unique combination is operational.

8. The method of claim 1, wherein determining whether the first unique combination is available for retrieval includes determining whether load balancing parameters are satisfied.

9. A centralized digital video recorder (DVR) comprises:

a dispersed storage error encoding module operable to encode a broadcast of data in accordance with an error coding dispersal storage function to produce a plurality of sets of encoded data slices wherein the error coding dispersal storage function facilitates error-free decoding of the broadcast of data via decoding of a threshold number of encoded data slices that is less than a total number of the plurality of sets of encoded data slices, wherein the threshold number of encoded data slices can be any combination of encoded data slices from the plurality of sets of encoded data slices;

a plurality of storage nodes operable to store the plurality of sets of encoded data slices;

a distribution module operable to;

receive, from a requesting unit, a playback request for the broadcast of data;

in response to the playback request;

determine a first unique combination of encoded data slices of the plurality of sets of encoded data slices as a first subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices;

determine whether the first unique combination is available for retrieval, based on a number of the first unique combination of encoded data slices available for retrieval including at least the threshold number of encoded data slices;

when the first unique combination is available;

retrieve, as a unique copy of the broadcast data, the first unique combination of encoded data slices; and

transmit the first unique combination of encoded data slices to the requesting unit;

when the first unique combination is not available because the number of the first unique combination of encoded data slices available for retrieval is less than the threshold number of encoded data slices;

determine a second unique combination of encoded data slices of the plurality of sets of encoded data slices as a second subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices, wherein the second subset is different from the first subset;

retrieve, as the unique copy of the broadcast data, the second unique combination of encoded data slices; and

transmit the second unique combination of encoded data slices to the requesting unit.

10. The centralized DVR of claim 9, wherein determining the first unique combination of encoded data slices comprises selecting one of a plurality of combinations of encoded data slices assigned to the requesting unit.

11. The centralized DVR of claim 10, wherein determining the second unique combination of encoded data slices comprises selecting a different one of the plurality of combinations of encoded data slices assigned to the requesting unit.

12. The centralized DVR of claim 9, wherein determining the first unique combination of encoded data slices comprises selecting a combination of encoded data slices assigned to the requesting unit.

13. The centralized DVR of claim 12, wherein determining the second unique combination of encoded data slices comprises selecting the second subset of encoded data slices of the plurality of sets of encoded data slices.

14. The centralized DVR of claim 9, wherein:

the plurality of sets of encoded data slices include an encoded data slice stored in a first pillar corresponding to a first distributed storage (DS) unit; and

determining the second unique combination of encoded data slices includes selecting the second subset to exclude any data slice stored in the first pillar corresponding to the first DS storage unit.

15. The centralized DVR of claim 9, wherein determining whether the first unique combination is available for retrieval includes determining whether a distributed storage (DS) unit storing at least one encoded data slice of the first unique combination is operational.

16. The centralized DVR of claim 9, wherein determining whether the first unique combination is available for retrieval includes determining whether load balancing parameters are satisfied.

17. A non-transitory computer readable storage medium storing a program of instructions configured to be executed by a processor to implement a method for execution by a dispersed storage processing module, the program of instructions comprising:

at least one instruction configured to store a broadcast of data in accordance with an error coding dispersal storage function, wherein the broadcast of data is stored as a plurality of sets of encoded data slices and wherein the error coding dispersal storage function facilitates error-free decoding of the broadcast of data via decoding of a threshold number of encoded data slices that is less than a total number of the plurality of sets of encoded data slices, wherein the threshold number of encoded data slices can be any combination of encoded data slices from the plurality of sets of encoded data slices;

at least one instruction configured to receive, from a requesting unit, a playback request for the broadcast of data;

in response to the playback request;

at least one instruction configured to determine a first unique combination of encoded data slices of the plurality of sets of encoded data slices as a first subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices;

at least one instruction configured to determine whether the first unique combination is available for retrieval, based on a number of the first unique combination of encoded data slices available for retrieval including at least the threshold number of encoded data slices;

when the first unique combination is available;

at least one instruction configured to retrieve, as a unique copy of the broadcast data, the first unique combination of encoded data slices; and

at least one instruction configured to transmit the first unique combination of encoded data slices to the requesting unit;

when the first unique combination is not available because the number of the first unique combination of encoded data slices available for retrieval is less than the threshold number of encoded data slices;

at least one instruction configured to determine a second unique combination of encoded data slices of the plurality of sets of encoded data slices to be retrieved as a second subset of the total number of the plurality of sets of encoded data slices having at least the threshold number of encoded data slices, wherein the second subset is different from the first subset;

at least one instruction configured to retrieve, as the unique copy of the broadcast data, the second unique combination of encoded data slices; and

at least one instruction configured to transmit the second unique combination of encoded data slices to the requesting unit.

18. The non-transitory computer readable storage medium of claim 17, wherein determining the first unique combination of encoded data slices comprises selecting one of a plurality of combinations of encoded data slices assigned to the requesting unit.

19. The non-transitory computer readable storage medium of claim 18, wherein determining the second unique combination of encoded data slices comprises selecting a different one of the plurality of combinations of encoded data slices assigned to the requesting unit.

20. The non-transitory computer readable storage medium of claim 17, wherein determining the first unique combination of encoded data slices comprises selecting a combination of encoded data slices assigned to the requesting unit.

21. The non-transitory computer readable storage medium of claim 20, wherein determining the second unique combination of encoded data slices comprises selecting the second subset of encoded data slices of the plurality of sets of encoded data slices.

22. The non-transitory computer readable storage medium of claim 17, wherein:

the plurality of sets of encoded data slices include an encoded data slice stored in a first pillar corresponding to a first distributed storage (DS) unit; and

determining the second unique combination of encoded data slices includes selecting the second subset to exclude any data slice stored in the first pillar corresponding to the first DS storage unit.

23. The non-transitory computer readable storage medium of claim 17, wherein determining whether the first unique combination is available for retrieval includes determining whether a distributed storage (DS) unit storing at least one encoded data slice of the first unique combination is operational.

24. The non-transitory computer readable storage medium of claim 17, wherein determining whether the first unique combination is available for retrieval includes determining whether load balancing parameters are satisfied.