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

• US 20110004601A1
• Filed: 07/03/2009
• Published: 01/06/2011
• 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
• Granted Patent: US 8,280,895 B2
• Time in Patent Office: Days
• 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 for optimizing data transfer through parallelized interlacing of data based upon sorted characteristics to minimize latencies inherent in the system. Operating a plurality of threads in parallel on disparate file sizes ordered by an additional thread. Efficient backup of heterogeneous non-volatile mass store to a network attached server. Scalable distribution of backup processes for computing hashes and eliminating duplication. Increased granularity of file pieces to match blocking of file I/O with network transmission. Efficiently packing each network transmission block using sequence search criteria. Avoidance of sending undesired pieces. Segmentation of each file and object into a hierarchy of pieces in a plurality of types.

Claims

1. A method comprising the following processes:

receiving an object selection comprising a plurality of files,

scanning files on a non-volatile mass store,

ordering identities of the files according to a criteria,

merging identities of the files into a list of ordered file identities.

2. The method of claim 1 further comprising the following parallel processes:

a first process comprising

removing a first file identity from the top of the list of ordered file identities,

reading the first file from a non-volatile mass store,

operating on the first file in a first stream;

a second process executing simultaneously with the first process comprising

removing a second file identity from the bottom of the list of ordered file identities,

reading the second file from a non-volatile mass store,

operating on the second file in a second stream.

3. The method of claim 2 further comprising at least one of the following processes:

an additional parallel process comprising;

removing an additional file identity from the list of ordered file identities at a certain point intermediate between the top and the bottom,

reading the additional file from a non-volatile mass store,

operating on the additional file in an additional stream.

4. The method of claim 3 wherein operating on a file comprises managing a header, storing into an object store, formatting a logical tape, and writing to a device.

5. The method of claim 3 wherein operating on a file comprises:

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

writing a single first piece type into piece store for each file comprising name, size, and date,

writing at least one third piece type into piece store for each file of variable length but maximum size containing a data shard,

writing a single second piece type into piece store for each third piece type.

6. The method of claim 5 further comprising:

receiving from a backup apparatus a sorted list of most frequently encountered type two

pieces already stored at the network attached backup apparatus,

matching the type 2 piece determined by the method with a type 2 piece in the list of most frequently encountered type 2 pieces, and

removing from pieces store the type 3 piece corresponding to a type 2 piece found on the list of the most frequently encountered type 2 pieces whereby more room is available for additional type 1 and type 2 pieces in the pieces store, and

whereby computing and comparing hashes at each user station improves scalability of the network attached backup apparatus.

7. The method of claim 6 further comprising the following steps:

reading a file from a nonvolatile mass store,

determining a type 1 piece from the file and writing a type 1 piece into a piece store,

determining at least one type 3 piece from the file and writing each type 3 piece into a piece store,

determining one type 2 piece for each type 3 piece and writing each type 2 piece into a piece store,

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

8. The method of claim 7 wherein a type 3 piece is a data shard of variable length and maximum size.

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

11. The method of claim 9 for operating one of a plurality of heterogeneous user stations further comprising the steps following:

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 the selected files into the sorted file is list,

within each of the plurality of thread circuits,

extracting a file from a certain position in the sorted file list,

determining pieces wherein pieces comprise;

begin file,

file data,

file data hash;

determining a begin file piece,

determining a file data piece,

determining a file data hash piece,

reiterating determination of file data and file data hash pieces;

within the piece store insertion circuit

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

until a piece store is full, writing into the piece store the following pieces if available in the following order,

firstly, begin file,

secondly, file data hash,

thirdly, file data;

and enabling the piece store extraction circuit;

resuming when the piece store has available space;

within the piece store purge circuit,

receiving a skip flag from a local area network attached apparatus in a request,

identifying the pieces within the piece store related to the skip flag, and

deleting from piece store each piece related to the skip flag.

12. The method of claim 11

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

secondly begin file

thirdly, file metadata

fourthly, file data hash

fifthly, file data.

13. The method of claim 11

wherein a certain position in the sorted file list comprises one of:

beginning of the sorted file list,

the end of the sorted file list,

whereby the smallest file and the largest file are selected, and the midpoint of the sorted file list

whereby data throughput is improved by selectively interlacing files with high overhead and files with low overhead.

14. The method of claim 11

wherein a certain position in the sorted file list comprises one of:

beginning of the sorted file list,

the end of the sorted file list,

whereby the smallest file and the largest file are selected,

the midpoint of the sorted file list, and

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

15. The method of claim 11

wherein a certain position in the sorted file list comprises one of:

beginning of the sorted file list,

the end of the sorted file list,

whereby the smallest file and the largest file are selected, and

a plurality of positions substantially equidistant between the smallest and largest file positions.

16. The method of claim 11 for scheduling file access to a non-volatile mass store by a plurality of parallel threads controlling a processor further comprising:

determining a list of files for processing,

sorting a list of files by an orderable characteristic,

assigning beginning of the file list to a first thread controlling a processor,

assigning end of the file list to a second thread controlling a processor,

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

wherein the characteristic is file size.

17. The method of claim 16 for copying files from nonvolatile mass storage into a pieces store further comprising:

placing the identity of each file selected for backup on the list sorted by size,

selecting a file from a certain position,

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

writing a single first piece type into piece store for each file comprising name, size, and date,

writing at least one third piece type into piece store for each file of variable length but maximum size containing a data shard,

writing a single second piece type into piece store for each third piece type.

18. The method of claim 17 wherein a certain position comprises positions at a top and bottom of the list whereby the largest file and the smallest file are each assigned to a thread and a third thread may be assigned to receive files taken at a certain position comprising the midpoint, the median, or nearest the mean.

19. The method of claim 18 wherein a certain position comprises the point half way between the smallest and the midpoint.

10. A system for bare metal backup of user disk storage into a public network comprising

a wide area network attached server coupled to at least one local area network attached apparatus, coupled to

a plurality of heterogeneous user stations,

wherein each heterogeneous user station comprises

a plurality of piece stores,

a piece store insertion circuit,

plurality of thread circuits,

a piece store purge circuit,

a sorted file list circuit, and

a computer readable storage apparatus;

wherein the wide area network attached server comprises;

means for receiving pieces comprising an operating system piece, a data hash piece, and an

encrypted data piece,

means for requesting transmission of an encrypted data piece if a data hash is a new, and

means for restoring platform independent data files and data files adapted to a specific user'"'"'s operating system configuration and file system;

wherein the local area network attached apparatus comprises;

means for requesting an object from a local area network attached user station,

means for transmitting pieces to a wide area network attached server,

means for encrypting a data piece, and

means for restoring platform independent data files and data files adapted to a specific user'"'"'s operating system configuration and file system.

20. An apparatus comprising a nonvolatile mass store, coupled to at least one streams processor, and at least one piece store coupled to the streams processor, the processor adapted by a software program to perform the simultaneous threads:

ordering file identities into a list ordered by file size,

operating on the largest file on the list,

operating on the smallest file on the list, and

operating on a file substantially at the midpoint of the list.