Hardware acceleration of commonality factoring with removable media
Systems and methods for commonality factoring for storing data on removable storage media are described. The systems and methods allow for highly compressed data, e.g., data compressed using archiving or backup methods including de-duplication, to be stored in an efficient manner on portable memory devices such as removable storage cartridges. The methods include breaking data, e.g., data files for backup, into unique chunks and calculating identifiers, e.g., hash identifiers, based on the unique chunks. Redundant chunks can be identified by calculating identifiers and comparing identifiers of other chunks to the identifiers of unique chunks previously calculated. When a redundant chunk is identified, a reference to the existing unique chunk is generated such that the chunk can be reconstituted in relation to other chunks in order to recreate the original data. The method further includes storing one or more of the unique chunks, the identifiers and/or the references on the removable storage medium. The acceleration hardware and/or software can reside in multiple devices, depending on the embodiment. For example, hardware and/or software for the chunking and/or hashing functions can reside in one or more of a host computer, a removable storage device, a removable cartridge holder and the removable storage cartridge.
1. A system for commonality factoring for storing data with a removable storage cartridge, comprising:
a processor;
an expansion bus coupled to the processor;
a socket coupled to the expansion bus and configured to accept the removable storage cartridge; and
an expansion module removably coupled to the expansion bus, wherein the expansion module is configured to transfer data to the removable storage cartridge, the expansion module comprising:
a chunking module configured to break an original data stream into a plurality of chunks; and
a hashing module coupled to the chunking module in a pipeline fashion such that at least a portion of input to the hashing module comprises output from the chunking module, the hashing module configured to:
determine if each chunk is unique, and
forward chunks determined to be unique toward the removable storage cartridge;
wherein multiple data paths in parallel are utilized and the multiple data paths comprise a single data stream split across multiple instances by truncating the data stream.
2. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein a first byte of each chunk is processed by the hashing module before a last byte of the chunk has been processed by the chunking module.
3. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein the original data stream comprises a plurality of files.
4. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein the hashing module is further configured to:
calculate an identifier for each forwarded chunk;
store the identifiers; and
determine that the chunks are unique based on the identifiers.
5. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , further comprising an additional data processing module.
6. The system for commonality factoring for storing data with the removable storage cartridge according to claim 5 , wherein the additional data processing module comprises one or more of a data compression module, an encryption module and an error correction coding module.
7. The system for commonality factoring for storing data with the removable storage cartridge according to claim 5 , further comprising an identifier database search module for performing a search of an identifier database based on outputs from the hashing module and forwarding the unique chunks to the additional processing module.
8. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein the single data stream is truncated at locations that do not necessarily align with chunk boundaries.
9. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein a size of truncated portions of the single data stream is either fixed or variable.
10. The system for commonality factoring for storing data with the removable storage cartridge according to claim 1 , wherein the hashing module is configured to use one or more of Message Digest Algorithm 5 (MD5) hashing, Secure Hash Algorithm-1(SHA-1) hashing and Secure Hash Algorithm-2 (SHA-2) hashing.
11. A method for commonality factoring for storing data with a removable storage cartridge, comprising:
receiving, at an expansion module removably coupled to a host computer, an original data stream, wherein the expansion module comprises:
a chunking module, and
a hashing module,
wherein the hashing module and the chunking module are configured in a pipeline architecture such that at least a portion of input to the hashing module comprises output from the chunking module;
at the chunking module, breaking the original data stream into a plurality of chunks; and
forwarding the chunks toward the hashing module, wherein the hashing module performs the following steps:
calculating an identifier for each forwarded chunk;
storing the identifiers; and
determining, based on the identifiers, whether each chunk is unique; and
forwarding at least one of the unique chunks and the identifier to the removable storage cartridge, wherein the removable storage cartridge includes a storage drive; and
further wherein multiple data paths in parallel are utilized and the multiple data paths comprise a single data stream split across multiple instances by truncating the single data stream.
12. The method for commonality factoring for storing data with the removable storage cartridge according to claim 11 , wherein the identifiers are stored in low latency memory.
13. The method for commonality factoring for storing data with the removable storage cartridge according to claim 11 , wherein at least one of the chunking module and the hashing module is external to the host computer.
14. An expansion card for commonality factoring for storing data with a removable storage cartridge, comprising:
a chunking module configured to:
receive an original data stream from the host computer, and
break the original data stream into a plurality of chunks, wherein the expansion card is configured to:
be removably coupled to a host computer and the removable storage cartridge, and
store data on the removable storage cartridge; and
a hashing module coupled to the chunking module in a pipeline fashion such that at least a portion of input to the hashing module comprises output from the chunking module, wherein the hashing module is configured to:
receive the plurality of chunks from the chunking module,
calculate an identifier for each of the received chunks,
determine, based on the identifiers, if each chunk is unique, and
store the unique chunks on the removable storage cartridge, wherein multiple data paths in parallel are utilized and the multiple data paths comprise a single data stream split across multiple instances by truncating the single data stream.
15. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 14 , wherein the original data stream comprises a plurality of files.
16. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 14 , the single data stream is truncated at locations that do not necessarily align with chunk boundaries.
17. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 14 , wherein a first byte of each chunk is processed by the hashing module before a last byte of the chunk has been processed by the chunking module.
18. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 14 , further comprising an additional data processing module.
19. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 18 , further comprising an identifier database search module for performing a search of an identifier database based on outputs from the hashing module and forwarding the unique chunks to the additional processing module.
20. The expansion card for commonality factoring for storing data with the removable storage cartridge according to claim 18 , wherein the additional data processing module comprises one or more of a data compression module, an encryption module and an error correction coding module.