Multi-streamed method for optimizing data transfer through parallelized interlacing of data based upon sorted characteristics to minimize latencies inherent in the system

• US 8,280,895 B2
• Filed: 07/03/2009
• Issued: 10/02/2012
• Est. Priority Date: 07/03/2009
• Status: Active Grant

• Current Assignee: Barracuda Networks Incorporated
• Original Assignee: Barracuda Networks Incorporated
• Inventors: Peckham, Derrick Shea, Dictos, Jason Daniel
• Primary Examiner(s): Kim, Charles
• Assistant Examiner(s): MINA, FATIMA P
• Application Number:
  US12/497,564
• Publication Number:
  US 20110004601A1
• Time in Patent Office: 1,187 Days
• Field of Search: 707/754, 707/758, 707/802
• US Class Current: 707/752
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A method which operates a plurality of threads in parallel on disparate file sizes ordered by an additional thread. Efficiently backing up of heterogeneous non-volatile mass store to a network attached server scalably distributes computing hashes and eliminating duplication. The method segments each file and object into a hierarchy of pieces in a plurality of types and avoids sending unnecessary pieces.

Claims

1. A multi-streamed method for parallelized interlacing of data for backup comprises:

receiving and storing a list of most frequently encountered type 2 pieces each of which comprise a data hash determined from a type 3 piece which comprise a file data shard having variable length up to a maximum size;

receiving and storing a list of object identities organized by file size wherein objects comprise files;

operating on a plurality of files simultaneously using a plurality of parallel threads controlling one or more processors by

determining a single type 1 piece for each file which type 1 piece comprises file name, size, and date,

determining at least one type 3 piece for each file and

determining a single type 2 piece for each type 3 piece;

within a first parallel thread, while there is any object identity remaining on said list of object identities organized by file size,

removing a top file identity from a top of the list,

reading a top file from non-volatile mass store, and

operating on said top file to determine type 1, type 2, and type 3 pieces;

within a second parallel thread, while there is any object identity remaining on said list of object identities organized by file size,

removing a bottom file identity from a bottom of the list,

reading a bottom file from non-volatile mass store, and

operating on said bottom file to determine type 1, type 2, and type 3 pieces;

until piece store is full, in the following order, for each file operated on,

writing type 1 piece to a piece store, then, subsequently

writing one or more type 2 pieces to the piece store, and finally,

writing one or more type 3 pieces to the piece store;

comparing each type 2 piece stored in the piece store with—

the list of most frequently encountered type 2 pieces, and

removing from the piece store any type 3 piece which corresponds to a most frequently encountered type 2 piece.

2. The method of claim 1 further comprising:

for each file read from non-volatile mass store,

reiterating determination and writing steps of type 2 and type 3 pieces until reaching the file end.

3. The method of claim 1 wherein a type 2 piece is a data hash of fixed length corresponding to a specific type 3 piece.

4. A method for operating each one of a plurality of heterogeneous user stations comprising:

within a sorted file list circuit,

receiving an object request from a local area network attached apparatus,

selecting files related to the requested object,

sorting the selected files on size,

merging all identifiers of the sorted selected files into a sorted file list,

within each of a plurality of thread circuits,

extracting a plurality of files at certain positions in the sorted file list,

wherein certain positions in the sorted file list comprises;

beginning of the sorted file list,

end of the sorted file list, and

a midpoint of the sorted file list,

for each extracted file,

determining a begin file piece,

determining a first file data piece,

determining a first file data hash piece,

reiterating determination of file data and file data hash pieces;

within a piece store insertion circuit,

until each piece store is full, receiving pieces from one of a plurality of thread circuits,

until each piece store is full, writing into the piece store the following pieces if available in the following order, firstly, begin file piece, secondly, file data hash piece, thirdly, file data piece, wherein a file data piece comprises a data shard of variable length and maximum size, and a file data hash piece comprises a data hash of fixed length corresponding to a specific file data piece, and a begin file piece comprises file name, size, and date,

receiving and storing a list of file data hash pieces determined from file data pieces previously stored at the local area network attached apparatus,

removing from the piece store any file data piece which was previously stored at the local area network attached apparatus.

5. The method of claim 4 wherein the pieces further comprise:

an object attribute piece and file meta data piece, wherein the method further comprises the steps following;

until a piece store is full,

writing into the piece store the following pieces if available in the following order, firstly, object attribute piece, secondly begin file piece, thirdly, file metadata piece, fourthly, file data hash piece, and fifthly, file data piece.

6. The method of claim 4 wherein certain positions in the sorted file list comprise:

beginning of the sorted file list,

an end of the sorted file list furthest from the beginning,

a midpoint of the sorted file list, and

a position substantially half way between the midpoint of the sorted file list and the position of a file having the smallest size.

7. A method for scheduling file access to a non-volatile mass store by a plurality of parallel threads controlling a processor to convert each stored file into a hierarchy of pieces for efficient backup without duplication comprising:

determining a list of files for processing,

sorting the list of files by an orderable characteristic,

assigning a certain position in the list of files to a first thread controlling a processor,

assigning an other certain position in the list of files to a second thread controlling a processor,

assigning at least one intermediate point of the list of files to one or more additional threads,

wherein certain positions comprises a first position at a top and a second position at a bottom of the list and a third thread is assigned to receive files taken at a point half way between a bottom of the list and a midpoint of the list;

wherein the orderable characteristic is file size and wherein each thread controls a processor to perform;

converting each file into a hierarchy of pieces and a plurality of piece types;

writing a single begin file piece into piece store for each file the begin file piece comprising name, size, and date;

writing at least one file data piece of variable length but maximum size containing a data shard, into piece store; and

writing a single file data hash piece into piece store, the filed data hash piece comprising a data hash for each file data piece.