System and process for delivering digital data on demand

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.

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.

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.

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.

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.

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.

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.

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
• K=floor({floor(I/M)*(M+1)+(P mod M)}/N);
• J={floor(I/M)*(M+1)+(I mod M)}mod N;
• and
• L={J+N−(I mod M)+P}mod N;
• retrieving data from the K-th block of the stripe on the L-th disk;
• performing an exclusive OR operation of the retrieved data with the reconstruction buffer;
• storing the result of the exclusive OR operation in the reconstruction buffer;
• incrementing P;
• determining whether P is greater than M;
• responsive to P not being greater than M, determining if the P-th data block is stored on a storage device having failed, and responsive to the P-th data block being stored on a failed storage device, then repeating the performing operations until P is greater than M.

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
• K=floor({floor(I/M)*(M+1)+(P mod M)}/N);
• J={floor(I/M)*(M+1)+(I mod M)}mod N;
• and
• L={J+N−(I mod M)+P}mod N;
• retrieving data from the K-th block of the stripe on the L-th disk;
• performing an exclusive OR operation of the retrieved data with the reconstruction buffer;
• storing the result of the exclusive OR operation in the reconstruction buffer;
• incrementing P;
• determining whether P is greater than M;
• responsive to P not being greater than M, determining if the P-th data block is stored on a storage device having failed, and responsive to the P-th data block being stored on a failed storage device, then repeating the performing operations until P is greater than M.

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).

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).

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).

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).