Deduplication metadata access in deduplication file system

• US 9,372,865 B2
• Filed: 02/12/2013
• Issued: 06/21/2016
• Est. Priority Date: 02/12/2013
• Status: Active Grant

• Current Assignee: Atlantis Computing, Inc. (hiveIO, Inc.)
• Original Assignee: Atlantis Computing, Inc. (hiveIO, Inc.)
• Inventors: Hoskeri, Abhijit P, Venkatesh, Chetan C
• Primary Examiner(s): Gofman, Alex
• Assistant Examiner(s): Mian, Umar
• Application Number:
  US13/765,664
• Publication Number:
  US 20140229451A1
• Time in Patent Office: 1,225 Days
• Field of Search: 707/692
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/1756 based on delta files

Abstract

Techniques associated with deduplication metadata access in a deduplication file system are described, including determining a state of a file system, reading a table associated with the file system, including reading block numbers associated with files in the file system, the table being stored in a storage, wherein the block numbers include a block number and logical block number, determining whether each of the block numbers exists in a reconstruction map, modifying the reconstruction map, obtaining a hash value associated with each of the block numbers, reading data blocks from a disk using the plurality of block numbers, and constructing deduplication metadata in system memory (i.e., RAM) using a read of the data blocks.

Claims

1. A method, comprising:

determining a state of a file system comprising reading a flag configured to track whether a previous unmount of the file system was complete;

reading a table associated with the file system, including reading a plurality of block numbers associated with a plurality of files in the file system, the table being stored on a disk in a non-volatile storage, wherein the plurality of block numbers includes a block number and another block number, wherein each block number is read to determine an ordered sequence of locations on the disk of one or more data blocks or block groups for a file associated with said each block number;

determining whether each of the plurality of block numbers exists in a reconstruction map being created in a volatile system memory;

modifying the reconstruction map by adding a new entry to the reconstruction map for a block number that does not already exist in the reconstruction map, and incrementing a reference count in the reconstruction map for a block number that does already exist in the reconstruction map;

obtaining a hash value associated with each of the plurality of block numbers and adding the hash value to corresponding entries of the reconstruction map;

reading a plurality of block numbers sequentially from the disk to retrieve corresponding data blocks or block groups from the ordered sequence of locations on the disk using the plurality of block numbers; and

constructing a deduplication metadata data structure that describes file system data based on the hash value, wherein the deduplication metadata structure is constructed in the volatile system memory from the reconstruction map.

2. The method of claim 1, wherein determining the state of the file system comprises determining that a previous unmount of the file system was unclean.

3. The method of claim 1, wherein the table comprises an inode table.

4. The method of claim 1, wherein the block number comprises a logical block number, and the another block number comprises another logical block number.

5. The method of claim 1, wherein adding the new entry for the block number that does not already exist in the reconstruction map comprises associating the block number with a reference count value of 1.

6. The method of claim 1, further comprising setting the flag to a first value after constructing the deduplication metadata in the volatile system memory.

7. The method of claim 6, further comprising unmounting the file system.

8. The method of claim 7, wherein unmounting the file system comprises writing the deduplication metadata to a storage array.

9. The method of claim 7, further comprising setting the flag to a second value after unmounting the file system.

10. A system, comprising:

a volatile system memory configured to store a deduplication metadata; and

a processor configured to run a deduplication application configured to

determine a state of a file system and read a table associated with the file system, including reading a plurality of block numbers associated with a plurality of files in the file system, wherein the plurality of block numbers includes a block number and another block number, and wherein each block number is read to determine an ordered sequence of locations on a disk of one or more data blocks or block groups for a file associated with said each block number, and wherein the state of the file system is determined by reading a flag configured to track whether a previous unmount of the file system was complete

determine whether each of the plurality of block numbers exists in a reconstruction map being created in the volatile system memory,

modify the reconstruction map by adding a new entry to the reconstruction map for a block number that does not already exist in the reconstruction map, and incrementing a reference count in the reconstruction map for a block number that does already exist in the reconstruction map,

obtain a hash value associated with each of the plurality of block numbers and add the hash value to corresponding entries of the reconstruction map,

read a plurality of block numbers sequentially from the disk to retrieve corresponding data blocks or block groups from the ordered sequence of locations on the disk using the plurality of block numbers, and

construct the deduplication metadata as a deduplication metadata data structure that describes file system data based on the hash value, wherein the deduplication metadata structure is constructed in the volatile system memory from the reconstruction map.

11. The system of claim 10, further comprising a storage configured to store the table and the deduplication metadata.

12. The system of claim 10, wherein the plurality of block numbers references a block group in a storage.

13. The system of claim 10, wherein the plurality of block numbers references a block in a storage.

14. The system of claim 10, wherein the reconstruction map comprises a plurality of hash values, each of the plurality of hash values associated with at least one of the plurality of block numbers.

15. The system of claim 10, wherein the reconstruction map comprises a hash table in which a key comprises one of the plurality of block numbers.

16. The system of claim 10, further comprising a virtual machine manager configured to create and operate a virtual machine.

17. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:

determining a state of a file system comprising reading a flag configured to track whether a previous unmount of the file system was complete;

reading a table associated with the file system, including reading a plurality of block numbers associated with a plurality of files in the file system, the table being stored on a disk in a non-volatile storage, wherein the plurality of block numbers includes a block number and another block number, wherein each block number is read to determine an ordered sequence of locations on the disk of one or more data blocks or block groups for a file associated with said each block number;

determining whether each of the plurality of block numbers exists in a reconstruction map being created in a volatile system memory;

modifying the reconstruction map by adding a new entry to the reconstruction map for a block number that does not already exist in the reconstruction map, and incrementing a reference count in the reconstruction map for a block number that does already exist in the reconstruction map;

obtaining a hash value associated with each of the plurality of block numbers and adding the hash value to corresponding entries of the reconstruction map;

reading a plurality of block numbers sequentially from the disk to retrieve corresponding data blocks or block groups from the ordered sequence of locations on the disk using the plurality of block numbers; and

constructing a deduplication metadata data structure that describes file system data based on the hash value, wherein the deduplication metadata structure is constructed in the volatile system memory from the reconstruction map.