Block-level and hash-based single-instance storage

• US 7,454,592 B1
• Filed: 02/16/2006
• Issued: 11/18/2008
• Est. Priority Date: 02/16/2006
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Shah, Aalop S., Vajgel, Peter, Varadarajan, Ganesh, Borate, Milind V.
• Primary Examiner(s): Nguyen; Hiep T
• Application Number:
  US11/355,684
• Time in Patent Office: 1,006 Days
• Field of Search: None
• US Class Current: 711/216
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31

Abstract

A method for reading data in a block-level single-instance storage system may involve receiving a first address of a data block, retrieving a signature corresponding to the first address, and reading data from a second address corresponding to the signature. A storage system may include a storage manager and first and second lookup tables. The storage manager may interface with an application (such as a database system or a file system) that uses a first set of identifiers for data blocks. The storage manager may use a second set of identifiers for the data blocks, and translates between the first and second identifiers using the lookup tables. The first lookup table indexes data block signatures according to the first set of identifiers. The second lookup table indexes the second set of identifiers according to the data block signatures. The second lookup table may be pruned to provide single instance storage.

Claims

1. A method comprising:

receiving a first address of a data block;

retrieving a signature corresponding to the first address, wherein the signature is derived from at least a portion of contents of the data block;

retrieving a second address corresponding to the signature.

2. The method of claim 1, where the first address is received from an application by a storage manager, and the retrieving the signature is performed by the storage manager.

3. The method of claim 2, where the storage manager is a volume manager and the application is a file system.

4. The method of claim 1, where the first address is a logical block address and the second address is a physical block address.

5. The method of claim 1, where the signature is a hash of the data block.

6. The method of claim 1, further comprising:

retrieving the data block from the second address.

7. The method of claim 1, further comprising:

writing data to the data block at the second address.

8. The method of claim 7, where the writing is performed as necessary for single-instance storage.

9. The method of claim 1, further comprising:

deleting the signature, if the data block becomes an unused data block.

10. The method of claim 1, further comprising:

deleting the data block, if the data block becomes an unused data block.

11. A method comprising:

receiving a first address;

identifying data to be written at the first address;

searching a first lookup table for the first address;

generating a signature based at least in part on the data;

searching a second lookup table for the signature; and

updating the first lookup table with the first address and the signature.

12. The method of claim 11, further comprising:

updating a reference count for the signature if the searching the second lookup table indicates that the signature is in the second lookup table; and

updating a reference count for a previous signature if the searching the first lookup table indicates that the first address is in the first lookup table.

13. The method of claim 11, further comprising:

writing the data if the searching the second lookup table indicates that the signature is not in the second lookup table.

14. The method of claim 13, where the writing the data comprises:

writing the data at a second address; and

updating the second lookup table with the second address.

15. The method of claim 14, where the first address is a logical block address and the second address is a physical block address.

16. The method of claim 11, where the first lookup table indexes signatures by first addresses, and where the second lookup table indexes second addresses by signatures.

17. A system comprising:

a storage manager configured to interface with an application, where the application is configured to identify data blocks according to a first set of identifiers for the data blocks, and where the storage manager is configured to access the data blocks on a storage medium according to a second set of identifiers for the data blocks;

a first lookup table that indexes data block signatures according to identifiers from the first set of identifiers, wherein each of the data block signatures is derived from at least a portion of contents of a corresponding data block;

a second lookup table that indexes identifiers from the second set of identifiers according to the data block signatures.

18. The system of claim 17, where the first set of identifiers for the data blocks comprises logical block addresses, and where the second set of identifiers for the data blocks comprises physical block addresses.

19. The system of claim 17, where the data block signatures are hashes of data in corresponding data blocks.

20. The system of claim 17, where the storage manager implements single-instance storage.

21. A computer readable storage medium having encoded thereon program instructions executable on one or more processors, the computer readable storage medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, where the program instructions are executable to implement each of:

receiving a first address of a data block;

retrieving a signature corresponding to the first address, wherein the signature is derived from at least a portion of contents of the data block;

retrieving a second address corresponding to the signature.

22. The computer readable storage medium of claim 21, where the first address is a logical block address and the second address is a physical block address, and where the signature is a hash of the data block.

23. A computer readable storage medium having encoded thereon program instructions executable on one or more processors, the computer readable storage medium being at least one of an electronic storage medium, a magnetic storage medium, or an optical storage medium, where the program instructions are executable to implement each of:

receiving a first address;

identifying data to be written at the first address;

searching a first lookup table for the first address;

generating a signature based at least in part on the data;

searching a second lookup table for the signature;

updating the first lookup table with the first address and the signature.

24. The computer readable storage medium of claim 23, where the program instructions are further executable to implement:

writing the data at a second address if the searching the second lookup table indicates that the signature is not in the second lookup table.

25. The computer readable storage medium of claim 24, where the first address is a logical block address, where the second address is a physical block address, and where the signature is a hash of the data block.