Fault tolerant architectures for continuous media servers

• US 6,079,028 A
• Filed: 04/23/1997
• Issued: 06/20/2000
• Est. Priority Date: 04/23/1997
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Ozden, Banu, Shenoy, Prashant J., Rastogi, Rajeev, Silberschatz, Abraham
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Elisca, Pierre E.
• Application Number:
  US08/839,188
• Time in Patent Office: 1,154 Days
• Field of Search: 395/182.02, 395/182.03, 395/182.04, 395/182.11, 395/200.49, 395/849, 395/200.61, 395/182.01, 395/200.47, 395/200.53, 395/200.54 , 395/200.59, 395/200.65, 714/6
• US Class Current: 714/6.23
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1016 Continuous RAID, i.e. RAID system that allows streaming or continuous media, e.g. VOD

Abstract

A continuous media server that provides support for the storage and retrieval of continuous media data at guaranteed rates using one of two fault-tolerant approaches that rely on admission control in order to meet rate guarantees in the event of a failure of the data storage medium that renders part of the continuous media inaccessible. In the first approach, a declustered parity storage scheme is used to uniformly distribute the additional load caused by a disk failure, uniformly across the disks. Contingency bandwidth for a certain number of clips is reserved on each disk in order to retrieve the additional blocks. In the second approach, data blocks in a parity group are prefetched and thus in the event of a disk failure only one additional parity block is retrieved for every data block to be reconstructed. While the second approach generates less additional load in the event of a failure, it has higher buffer requirements. For the second approach, parity blocks can either be stored on a separate parity disk, or distributed among the disks with contingency bandwidth reserved on each disk.

Claims

1. A method for servicing one or more requests for a continuous media clip stored on a plurality of data storage mediums at a desired playback rate, said method comprising the steps of:

reserving available bandwidth for each of said requests on a particular order;

maintaining a reserved list of all said requests having reserved bandwidth, said requests on said reserved list represented as reserved requests;

maintaining a service list corresponding to each of said plurality of data storage mediums each of said service lists listing a number of said reserved requests having a unit of data on said service list'"'"'s corresponding data storage medium, said reserved requests on each of said service lists representing a request in service, said number of requests in service limited such that the total bandwidth necessary for said requests in service does not exceed the maximum bandwidth for servicing a request for a continuous media clip at said desired playback rate, minus an amount of contingency bandwidth;

determining from each of said service lists if excess bandwidth is available on a corresponding data storage medium to service a next reserve request on each of said service lists;

moving in response to said determining step, said next reserved request from said reserved list to a service list with excess bandwidth and for which a unit of data of said request resides on said corresponding data storage medium;

retrieving at least one unit of data for each request service from each data storage medium;

determining whether any of said units of data are inaccessible due to a failure of one of said data storage mediums;

reconstructing said inaccessible units of data; and

transmitting said retrieved and reconstructed units of data at said playback rate.

2. A method according to claim 1 wherein the amounts of said contingency bandwidth is determined for each data storage medium.

3. A method according to claim 1 wherein the amount of said contingency bandwidth is determined after each round of retrieving said units of data of said requests in service, and is allocated only for those of said data storage mediums to be accessed during a next subsequent round of retrieval.

4. A method according to claim 1 wherein said inaccessible units of data includes one of p units of data comprising p-1 units of data of a continuous medium clip and one units of parity data, said p units of data comprising a parity group, said reconstructing step involves retrieving each of said accessible units of data of said parity group of said inaccessible unit of data.

5. A method according to claim 1 wherein each of said units of data to be retrieved is one of p units of data of a parity group, said parity group comprising p-1 units of data of at least one continuous media clip and one unit of parity data, said retrieving step further comprising retrieving said parity group of said unit of data of said request, other than said unit of parity data, and wherein said reconstructing step further comprises retrieving said unit of parity data of said parity group.

6. A method according to claim 1 further comprising the steps of:

allocating newly available bandwidth resulting from said transmitting of said retrieved and reconstructed units of data, to said reserved requests; and

deleting each request from said service and reserved lists after all of said units of data of said request have been transmitted.

7. A method of storing successive data blocks of a file on a plurality of data storage mediums, said plurality of data storage mediums comprising d data storage mediums grouped into clusters of p-1 data storage mediums, wherein said successive data blocks of the file are sequentially distributed among said plurality of data storage mediums in a round robin fashion, p-1 consecutive data blocks within a cluster forming a data group, each data group associated with a parity block computed from the data group, parity blocks associated with data groups within a particular cluster being uniformly distributed among a subset of data storage mediums, said subset of storage mediums excluding said particular cluster.

8. A method for storing at least one group according to claim 7, wherein the uniform distribution of said data and parity blocks is determined in accordance with the theory of Balanced Incomplete Block Designs.

9. A continuous media server for servicing at a particular playback rate, a request for a multimedia clip from a set of at least one stored multimedia clip comprising:

data storage memory for storing said at least one stored multimedia clip and parity data;

a storage manager for executing and managing a layout of said at least one stored multimedia clip and said parity data on said data storage memory, said layout including a substantially uniform distribution of said parity data on said data storage memory in substantial absence of a designated parity storage memory;

an admission controller for determining whether said request can be serviced; and

a retriever responsive to said admission controller means for retrieving said serviceable, multimedia clip from said data storage memory.

10. A server according to claim 9 wherein said data storage memory includes at least one data storage medium, wherein p-1 data blocks of said multimedia clip and one parity block form a parity group, and wherein said layout of said at least one stored multimedia clip and parity data is a declustered distribution of said parity group on said at least one data storage medium.

11. A server according to claim 10 wherein said layout further includes an amount of reserved bandwidth for each one of said data storage mediums sufficient to retrieve p-2 data blocks and one parity block.

12. A server according to claim 11 wherein said admission controller comprises:

at least one pending list for queuing each of said requests for a multimedia clip;

at least one reserved list for each of said requests on said pending list for which bandwidth has been allocated;

a locator for identifying the data storage memory location of said allocated bandwidth for each of said requests on said reserved lists;

at least one service list identifying those requests currently being serviced; and

means to continuously update said pending, reserved and service lists.

13. A server according to claim 12 further comprising means to reserve bandwidth for each of said data storage mediums having stored thereon at least one data block of said requests on said reserved lists.

14. A server according to claim 9 wherein each of said stored multimedia clips comprise a plurality of data blocks, wherein said layout includes an amount of reserved bandwidth for each one of said data storage mediums sufficient to retrieve one parity block, wherein each of said data blocks are sequentially distributed among said plurality of data storage mediums in a round robin fashion, and wherein said data blocks of said stored multimedia clips are grouped such that each group includes p-1 data blocks and one parity block, said parity blocks being uniformly distributed throughout the data storage memory.

15. A server according to claim 14 further comprising a buffer capable of storing p-1 data blocks and one parity block.