COMMONALITY FACTORING FOR REMOVABLE MEDIA

• US 20090013129A1
• Filed: 07/03/2008
• Published: 01/08/2009
• Est. Priority Date: 07/06/2007
• Status: Active Grant

• Current Assignee: SPEX Technologies, Inc.
• Original Assignee: ProStor Systems, Inc. (Glassbridge Enterprises, Inc.)
• Inventors: Bondurant, Matthew D.
• Granted Patent: US 8,046,509 B2
• Time in Patent Office: Days
• US Class Current: 711/115
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0686 Libraries, e.g. tape libraries, jukebox

Abstract

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.

Claims

1. An apparatus for storing data with a removable medium, the apparatus comprising:

a chunk module configured to receive an original data stream and break the original data stream into chunks;

a hash module coupled to the chunk module and configured to calculate an identifier for each chunk and to store the identifiers; and

a search module coupled to the removable medium, wherein the search module is configured to;

determine, based on the identifiers, whether each chunk is unique, and store on the removable medium, at least two of a following;

the unique chunks,

descriptors describing each of the unique chunks, and

references indicating a sequence of the unique chunks usable to reconstruct the original data stream, wherein the removable medium comprises a drive cartridge.

2. The apparatus for storing data with a removable medium of claim 1, wherein the search module is configured to store at least two of the unique chunks, the descriptors, and the references as streams on the removable medium.

3. The apparatus for storing data with a removable medium of claim 1, wherein the drive cartridge comprises a hard drive or solid state drive.

4. The apparatus for storing data with a removable medium of claim 1, wherein the removable medium comprises a plurality of drive cartridges.

5. The apparatus for storing data with a removable medium of claim 1, wherein the chunk module is further configured to break the original data stream into chunks by determining chunk boundaries through comparison between a subset of the bits returned from a sliding window algorithm and a predetermined value, whereby a match to the predetermined value designates the chunk boundary.

6. The apparatus for storing data with a removable medium of claim 1, wherein the hash module is further configured to calculate the unique identifiers using Secure Hash Algorithm-1 (SHA-1).

7. The method for storing data with a removable medium of claim 1, wherein the search module is further configured to determine whether each chunk is unique by searching a hash table indexed by the identifiers.

8. The apparatus for storing data with a removable medium of claim 1, wherein the search module is further configured to store host objects comprising virtual tape volumes for an existing tape format.

9. The apparatus for storing data with a removable medium of claim 7, wherein the hash table comprises a location on the removable medium for each descriptor, the location corresponding to where the associated unique chunk is stored.

10. The apparatus for storing data with a removable medium of claim 1, wherein the hash module stores the identifiers in a low latency memory.

11. A method for storing data with a plurality of removable media, comprising steps of:

breaking an original data stream into chunks;

calculating an identifier for each chunk;

storing the identifiers;

determining, based on the identifiers, whether each chunk is unique; and

storing on the plurality of removable media, at least two of a following;

a stream of the unique chunks,

a stream of descriptors describing each of the unique chunks, and

a stream of references indicating a sequence of the unique chunks usable to reconstruct the original data stream, wherein;

the stream of references stored in each medium includes a medium identifier, and

the medium identifier allows correlation of the references to the chunks on the different removable media.

12. A machine-readable medium having machine-executable instructions configured to perform the machine-implementable method for storing data with a plurality of removable medium of claim 11.

19. A machine-readable medium having machine-executable instructions configured to perform the machine-implementable method for storing data on a storage unit of claim 11.

13. A method for storing data on a removable storage unit, comprising:

breaking original data into chunks;

calculating an identifier for each chunk;

storing the identifiers in a low latency memory;

determining, based on the identifiers, whether each chunk is unique; and

storing on the storage unit at least two of a following;

the unique chunks,

descriptors describing each of the unique chunks, and

references indicating a sequence of the unique chunks used to reconstruct the original data.

14. The method for storing data of claim 13, wherein the storage unit comprises a single cartridge.

15. The method for storing data of claim 13, wherein the storage unit comprises a plurality of cartridges.

16. The method for storing data of claim 15, wherein the references stored in each cartridge includes a medium identifier in each entry for allowing the references to the chunks on the different cartridges.

17. The method for storing data of claim 13, wherein the at least two of the unique chunks, the descriptors, and the references are stored as streams on the storage unit.

18. The method for storing data of claim 13, wherein the storage unit is removable.