System and process for delivering digital data on demand

• US 6,212,657 B1
• Filed: 05/25/1999
• Issued: 04/03/2001
• Est. Priority Date: 08/08/1996
• Status: Expired due to Term

• Current Assignee: nSTREAMS Technologies, Inc.
• Original Assignee: nSTREAMS Technologies, Inc.
• Inventors: Hsu, Ching-San, Wang, Pong-sheng
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US09/318,524
• Time in Patent Office: 679 Days
• Field of Search: 714/766, 714/764, 714/763, 714/6, 348/7, 348/13, 348/6, 709/217, 709/219
• US Class Current: 714/746
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A video server system and method has a modular and expandable system design to deliver a plurality of video streams on user demand and under user control. The video server system and method has a central control module adapted to receive control commands such as SELECT, PLAY, REWIND, PAUSE etc. to select and playback a video from a plurality of videos stored in a storage module. The central control module is a computer motherboard having a first small computer serial interface (SCSI) coupled to the storage device. The central control module also has memory for buffering data blocks of video retrieved from the storage device or devices prior to delivery to the delivery module also included in the system. The delivery module is also a computer motherboard having memory and also having a plurality of video processors for processing the video data prior to coupling the data to a client location. The delivery module additionally has a SCSI interface configured to operate in a target mode so that the central control module transfers video data to the delivery module in the same manner that it would use if it were writing to a conventional SCSI disk drive.

Claims

1. A method of storing digital data in a plurality of storage devices (N), comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks.

2. The method of claim 1 wherein generating an error recovery block comprises computing a parity code.

3. The method of claim 2 wherein storing a plurality of data blocks on each storage device comprises striping each data block (I) across a subset of the plurality of storage devices.

4. The method of claim 3, wherein striping the I-th data block across a subset of the plurality of storage devices comprises:

computing J={floor(I/M)*(M+1)+(I mod M)}mod N;

computing K=floor({floor(I/M)*(M+1)+(I mod M)}/N);

writing the I-th data block as the K-th stripe on the J-th storage device.

5. The method of claim 2, wherein the parity code for an I-th data block is written in a parity buffer when I is the last block in the error recovery group, by performing the steps of:

(a) initializing a parity buffer;

(b) testing whether I is the last block in the error recovery group;

(c) computing J={(I+1)/M*(M+1)−

1}mod N;

(d) computing K=floor({(I+1)/M*(M+1)−

1}/N);

(e) writing the parity buffer for the I-th data block as the K-th stripe on the J-th disk;

(f) reinitializing the parity buffer and testing whether the I-th data block is the last data block in the error recovery group;

(g) responsive to the I-th data block not being the last data block in the error recovery group, writing a data block with all zeros to the J-th disk and writing the I-th data block as the K-th stripe on the J-th disk;

(h) responsive to the I-th data block being the last data block in the error recovery group, writing the parity buffer to the J-th disk.

6. The method of claim 1, wherein the digital data comprises video data.

7. The method of claim 1, further comprising accessing the stored digital data.

8. A method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

reading a redundancy factor (M) associated with the stored digital data, wherein M is an integer less than N;

determining whether any of the plurality of storage devices has failed;

responsive to none of the plurality of storage devices having failed, retrieving the data blocks from the storage devices storing the data blocks; and

responsive to at least one of the plurality of storage devices having failed;

determining, for each data block (I), whether it is stored on a storage device that has failed;

for each data block (I) stored on a storage device that has failed, reconstructing the I-th data block from M storage devices; and

for each data block (I) not stored on a storage device that has failed, retrieving the I-th data block.

9. The method of claim 8, wherein the stored digital data comprises video data.

10. The method of claim 8, further comprising:

receiving a request to read the digital data.

11. The method of claim 8, wherein reconstructing the I-th data block from M storage devices comprises:

initializing a data reconstruction buffer to zero;

initializing an index (P) to zero;

performing operations comprising;

computing

12. An electronically readable medium storing a program for permitting a computer to perform a method for storing digital data in a plurality of storage devices (N), the method comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks.

13. An electronically readable medium storing a program for permitting a computer to perform a method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

reading a redundancy factor (M) associated with the stored digital data, wherein M is an integer less than N;

determining whether any of the plurality of storage devices has failed;

responsive to none of the plurality of storage devices having failed, retrieving the data blocks from the storage devices storing the data blocks; and

responsive to at least one of the plurality of storage devices having failed;

determining, for each data block (I), whether it is stored on a storage device that has failed;

for each data block (I) stored on a storage device that has failed, reconstructing the I-th data block from M storage devices; and

for each data block (I) not stored on a storage device that has failed, retrieving the I-th data block.

14. A disk load balancing method for scheduling the start of playback of a particular video stream, the method comprising:

defining a plurality of time zones, the number of times zones corresponding to a number of storage devices (M) for storing video streams; and

assigning each video stream to initiate playback at an associated time zone by identifying the storage device (n) from which a particular video stream will commence and by determining a next available time zone associated with the storage device from which the particular video stream will commence playback.

15. The method of claim 14 wherein defining the plurality of time zones comprises computing an index value C=(floor(t/T)−

n) mod M, wherein

t is current time; and

T is time duration to playback a data block.

16. An electronically readable medium storing a program for permitting a computer to perform a method for scheduling the start of playback of a particular video stream, the method comprising:

defining a plurality of time zones, the number of times zones corresponding to a number of storage devices for storing video streams; and

assigning each video stream to initiate playback at an associated time zone by identifying the storage device from which a particular video stream will commence and by determining a next available time zone associated with the storage device from which the particular video stream will commence playback.

17. A method of storing digital data in a plurality of storage devices (N), comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks;

wherein generating an error recovery block comprises computing a parity code;

wherein storing a plurality of data blocks on each storage device comprises striping each data block (I) across a subset of the plurality of storage devices;

wherein striping the I-th data block across a subset of the plurality of storage devices comprises;

computing J={floor(I/M)*(M+1)+(I mod M)}mod N;

computing K=floor({floor(I/M)*(M+1)+(I mod M)}/N);

writing the I-th data block as the K-th stripe on the J-th storage device.

18. An electronically readable medium storing a program for permitting a computer to perform a method of storing digital data in a plurality of storage devices (N), the method comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks;

wherein generating an error recovery block comprises computing a parity code;

wherein storing a plurality of data blocks on each storage device comprises striping each data block (I) across a subset of the plurality of storage devices;

wherein striping the I-th data block across a subset of the plurality of storage devices comprises;

computing J={floor(I/M)*(M+1)+(I mod M)}mod N;

computing K=floor({floor(I/M)*(M+1)+(I mod M)}/N);

writing the I-th data block as the K-th stripe on the J-th storage device.

19. A method of storing digital data in a plurality of storage devices (N), comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks;

wherein generating an error recovery block comprises computing a parity code;

wherein the parity code for an I-th data block is written in a parity buffer when I is the last block in the error recovery group, by performing the steps of;

(a) initializing a parity buffer;

(b) testing whether I is the last block in the error recovery group;

(c) computing J={(I+1)/M*(M+1)−

1}mod N;

(d) computing K=floor({(I+1)/M*(M+1)−

1}/N);

(e) writing the parity buffer for the I-th data block as the K-th stripe on the J-th disk;

(f) reinitializing the parity buffer and testing whether the I-th data block is the last data block in the error recovery group;

(g) responsive to the I-th data block not being the last data block in the error recovery group, writing a data block with all zeros to the J-th disk and writing the I-th data block as the K-th stripe on the J-th disk;

(h) responsive to the I-th data block being the last data block in the error recovery group, writing the parity buffer to the J-th disk.

20. An electronically readable medium storing a program for permitting a computer to perform a method of storing digital data in a plurality of storage devices (N), the method comprising:

dividing the digital data into N data blocks;

storing the N data blocks on the plurality of storage devices;

selecting a redundancy factor (M) wherein M is an integer less than N;

generating an error recovery block for every M data blocks; and

storing the error recovery block on a different storage device from the storage devices storing the associated data blocks;

wherein generating an error recovery block comprises computing a parity code;

wherein the parity code for an I-th data block is written in a parity buffer when I is the last block in the error recovery group, by performing the steps of;

(a) initializing a parity buffer;

(b) testing whether I is the last block in the error recovery group;

(c) computing J={(I+1)/M*(M+1)−

1}mod N;

(d) computing K=floor({(I+1)/M*(M+1)−

1}/N);

(e) writing the parity buffer for the I-th data block as the K-th stripe on the J-th disk;

(f) reinitializing the parity buffer and testing whether the I-th data block is the last data block in the error recovery group;

(g) responsive to the I-th data block not being the last data block in the error recovery group, writing a data block with all zeros to the J-th disk and writing the I-th data block as the K-th stripe on the J-th disk;

(h) responsive to the I-th data block being the last data block in the error recovery group, writing the parity buffer to the J-th disk.

21. A method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

reading a redundancy factor (M) associated with the stored digital data, wherein M is an integer less than N;

determining whether any of the plurality of storage devices has failed;

responsive to none of the plurality of storage devices having failed, retrieving the data blocks from the storage devices storing the data blocks; and

responsive to at least one of the plurality of storage devices having failed;

determining, for each data block (I), whether it is stored on a storage device that has failed;

for each data block (I) stored on a storage device that has failed, reconstructing the I-th data block from M storage devices; and

for each data block (I) not stored on a storage device that has failed, retrieving the I-th data block;

wherein reconstructing the I-th data block from M storage devices comprises;

initializing a data reconstruction buffer to zero;

initializing an index (P) to zero;

performing operations comprising;

computing

22. An electronically readable medium storing a program for permitting a computer to perform a method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

reading a redundancy factor (M) associated with the stored digital data, wherein M is an integer less than N;

determining whether any of the plurality of storage devices has failed;

responsive to none of the plurality of storage devices having failed, retrieving the data blocks from the storage devices storing the data blocks; and

responsive to at least one of the plurality of storage devices having failed;

determining, for each data block (I), whether it is stored on a storage device that has failed;

for each data block (I) stored on a storage device that has failed, reconstructing the I-th data block from M storage devices; and

for each data block (I) not stored on a storage device that has failed, retrieving the I-th data block;

wherein reconstructing the I-th data block from M storage devices comprises;

initializing a data reconstruction buffer to zero;

initializing an index (P) to zero;

performing operations comprising;

computing

23. A method of storing a video object in N storage devices, the method comprising:

(a) performing a set-up process including specifying a redundancy factor M for the video object, wherein M is less than N and wherein the video object includes data blocks;

(b) storing the redundancy factor M as an attribute of the video object, and initializing an index (I) and a parity buffer;

(c) retrieving the current data block (I), performing an exclusive OR operation of the current data block (I) with the parity buffer, and writing the current data block (I) to a J-th disk;

(d) determining if the current data block (I) is the last data block in a redundancy group;

(e) if the current data block (I) is not the last data block in the redundancy group, then incrementing (I),

(f) if the current data block (I) is the last data block in the redundancy group, then writing the parity buffer to the J-th disk, re-initializing the parity buffer and incrementing (I);

(g) determining if the last data block of the video object has been written to disk;

(h) if the last data block of the video object has been written to disk, then determining if the current data block (I) is the last data block in the redundancy group;

(i) if the last data block of the video object has not been written to disk, then repeating (c) to (h);

(j) if the current data block (I) is the last data block in the redundancy group, then writing the parity buffer to the J-th disk; and

(k) if the current data block (I) is not the last data block in the redundancy group, then incrementing I and repeating (i) to (k).

24. An electronically readable medium storing a program for permitting a computer to perform a method of storing a video object in N storage devices, the method comprising:

(a) performing a set-up process including specifying a redundancy factor M for the video object, wherein M is less than N and wherein the video object includes data blocks;

(b) storing the redundancy factor M as an attribute of the video object, and initializing an index (I) and a parity buffer;

(c) retrieving the current data block (I), performing an exclusive OR operation of the current data block (I) with the parity buffer, and writing the current data block (I) to a J-th disk;

(d) determining if the current data block (I) is the last data block in a redundancy group;

(e) if the current data block (I) is not the last data block in the redundancy group, then incrementing (I),

(f) if the current data block (I) is the last data block in the redundancy group, then writing the parity buffer to the J-th disk, re-initializing the parity buffer and incrementing (I);

(g) determining if the last data block of the video object has been written to disk;

(h) if the last data block of the video object has been written to disk, then determining if the current data block (I) is the last data block in the redundancy group;

(i) if the last data block of the video object has not been written to disk, then repeating (c) to (h);

(j) if the current data block (I) is the last data block in the redundancy group, then writing the parity buffer to the J-th disk; and

(k) if the current data block (I) is not the last data block in the redundancy group, then incrementing I and repeating (i) to (k).

25. A method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

(a) using a stream thread to request to read a data block (I) from a video object stored in a J-th disk;

(b) reading a redundancy factor M associated with the video object;

(c) determining if a failure occurred in any of the plurality of storage devices;

(d) if a failure has occurred, then initializing a reconstruction buffer and an index P;

(e) determining if a current data block (P) is stored in a failed disk, and if the current data block (P) is stored in a failed disk, then reading a data block (K) on a storage device (L);

(f) performing an exclusive OR operation on the data block (K) and data stored in the reconstruction buffer;

(g) incrementing P;

(h) if reconstruction is complete (P>

M), then returning the data in the reconstruction buffer to the stream thread; and

(i) if reconstruction is not complete, then repeating (e) to (i).

26. An electronically readable medium storing a program for permitting a computer to perform a method for accessing digital data stored in a plurality of storage devices (N), the digital data being divided into N data blocks, the method comprising:

(a) using a stream thread to request to read a data block (I) from a video object stored in a J-th disk;

(b) reading a redundancy factor M associated with the video object;

(c) determining if a failure occurred in any of the plurality of storage devices;

(d) if a failure has occurred, then initializing a reconstruction buffer and an index P;

(e) determining if a current data block (P) is stored in a failed disk, and if the current data block (P) is stored in a failed disk, then reading a data block (K) on a storage device (L);

(f) performing an exclusive OR operation on the data block (K) and data stored in the reconstruction buffer;

(g) incrementing P;

(h) if reconstruction is complete (P>

M), then returning the data in the reconstruction buffer to the stream thread; and

(i) if reconstruction is not complete, then repeating (e) to (i).