Fingerprints datastore and stale fingerprint removal in de-duplication environments

Abstract

A storage server is coupled to a storage device that stores blocks of data, and generates a fingerprint for each data block stored on the storage device. The storage server creates a fingerprints datastore that is divided into a primary datastore and a secondary datastore. The primary datastore comprises a single entry for each unique fingerprint and the secondary datastore comprises an entry having an identical fingerprint as an entry in the primary datastore. The storage server merges entries in a changelog with the entries in the primary datastore to identify duplicate data blocks in the storage device and frees the identified duplicate data blocks in the storage device. The storage server stores the entries that correspond to the freed data blocks to a third datastore and overwrites the primary datastore with the entries from the merged data that correspond to the unique fingerprints to create an updated primary datastore.

What is claimed is: 
     
         1 . A method comprising:
 generating a fingerprint for each of a plurality of data blocks stored in a storage device;   storing the fingerprint in a fingerprints datastore;   identifying stale entries in the fingerprints datastore, the stale entries corresponding to duplicate data blocks eliminated from the storage device by a de-duplication operation;   writing stale entry information for the stale entries to a stale entries datastore; and   removing the stale entries in the fingerprints datastore using the stale entry information in response to a request for the de-duplication operation.   
     
     
         2 . The method of  claim 1 , wherein the fingerprints datastore includes a primary datastore and a secondary datastore, and wherein storing the fingerprint in the fingerprints datastore includes:
 determining whether the fingerprint corresponds to a duplicate data block of the duplicate data blocks;   in response to determining that the fingerprint does not correspond to a duplicate data block of the duplicate data blocks, storing the fingerprint as a first entry in the primary datastore; and   in response to determining that the fingerprint does correspond to a duplicate data block of the duplicate data blocks, storing the fingerprint as a second entry in the secondary datastore.   
     
     
         3 . The method of  claim 2 , wherein removing the stale entries in the fingerprints datastore comprises removing the stale entries from the secondary datastore. 
     
     
         4 . The method of  claim 1 , further comprising:
 overwriting the fingerprints datastore with stale-free entries; and   executing the de-duplication operation using the fingerprints datastore having the stale-free entries.   
     
     
         5 . The method of  claim 1 , wherein removing the stale entries in the fingerprints datastore using the stale entry information comprises:
 identifying entries in the fingerprints datastore that correspond to the stale entries in the stale entries datastore as stale entries.   
     
     
         6 . The method of  claim 1 , wherein the stale entry information includes a stale entry for a data block of the plurality of data blocks, the stale entry including an entry index for the stale entry, the fingerprint of the data block, context information for the data block, an inode number of a file to which the data block belongs, and a file block number of the data block. 
     
     
         7 . The method of  claim 1 , further comprising:
 in response to determining that the request for the de-duplication operation is received during execution of a verify operation, suspending the verify operation, storing a current state of the verify operation to the storage device, and marking the fingerprints datastore as read-only.   
     
     
         8 . A storage apparatus comprising:
 a storage interface to communicate with a storage device;   one or more processors communicably coupled to the storage interface;   a memory to store instructions that, when executed by the one or more processors, cause the storage apparatus to:
 generate a fingerprint for each of a plurality of data blocks stored in the storage device; 
 store the fingerprint in a fingerprints datastore; 
 identify stale entries in the fingerprints datastore, the stale entries corresponding to duplicate data blocks eliminated from the storage device by a de-duplication operation; 
 write stale entry information for the stale entries to a stale entries datastore; and 
 remove the stale entries in the fingerprints datastore using the stale entry information in response to a request for the de-duplication operation. 
   
     
     
         9 . The storage apparatus of  claim 8 , wherein the fingerprints datastore includes a primary datastore and a secondary datastore, and wherein the instructions to cause the storage apparatus to store the fingerprint in the fingerprints datastore include instructions to cause the storage apparatus to:
 determine whether the fingerprint corresponds to a duplicate data block of the duplicate data blocks;   in response to a determination that the fingerprint does not correspond to a duplicate data block of the duplicate data blocks, store the fingerprint as a first entry in the primary datastore; and   in response to a determination that the fingerprint does correspond to a duplicate data block of the duplicate data blocks, store the fingerprint as a second entry in the secondary datastore.   
     
     
         10 . The storage apparatus of  claim 8 , wherein the instructions further include instructions to cause the storage apparatus to:
 overwrite the fingerprints datastore with stale-free entries; and   execute the de-duplication operation using the fingerprints datastore having the stale-free entries.   
     
     
         11 . The storage apparatus of  claim 8 , wherein the instructions to cause the storage apparatus to remove the stale entries in the fingerprints datastore using the stale entry information include instructions to cause the storage apparatus to identify entries in the fingerprints datastore that correspond to the entries in the stale entries datastore as the stale entries in the fingerprints datastore. 
     
     
         12 . The storage apparatus of  claim 8 , wherein the stale entry information includes a stale entry for a data block of the plurality of data blocks, the stale entry including an entry index for the stale entry, the fingerprint of the data block, context information for the data block, an inode number of a file to which the data block belongs, and a file block number of the data block. 
     
     
         13 . The storage apparatus of  claim 8 , wherein the instructions further include instructions to cause the storage apparatus to:
 in response to determination that the request for the de-duplication operation is received during execution of a verify operation, suspend the verify operation, store a current state of the verify operation to the storage device, and mark the fingerprints datastore as read-only.   
     
     
         14 . A non-transitory computer-readable medium having stored thereon instructions, that when executed by one or more processors, cause the one or more processors to:
 generate a fingerprint for each of a plurality of data blocks stored in a storage device;   store the fingerprint in a fingerprints datastore;   identify stale entries in the fingerprints datastore, the stale entries corresponding to duplicate data blocks eliminated from the storage device by a de-duplication operation;   write stale entry information for the stale entries to a stale entries datastore; and   remove the stale entries in the fingerprints datastore using the stale entry information in response to a request for the de-duplication operation.   
     
     
         15 . The non-transitory computer-readable medium of  claim 14 , wherein the fingerprints datastore includes a primary datastore and a secondary datastore, and wherein the instructions to cause the one or more processors to store the fingerprint in the fingerprints datastore include instructions to cause the one or more processors to:
 determine whether the fingerprint corresponds to a duplicate data block of the duplicate data blocks;   in response to a determination that the fingerprint does not correspond to a duplicate data block of the duplicate data blocks, store the fingerprint as a first entry in the primary datastore; and   in response to a determination that the fingerprint does correspond to a duplicate data block of the duplicate data blocks, store the fingerprint as a second entry in the secondary datastore.   
     
     
         16 . The non-transitory computer-readable medium of  claim 15 , wherein the instructions to cause the one or more processors to remove the stale entries in the fingerprints datastore include instructions to cause the one or more processors to remove the stale entries from the secondary datastore. 
     
     
         17 . The non-transitory computer-readable medium of  claim 14 , wherein the instructions further include instructions to cause the one or more processors to:
 overwrite the fingerprints datastore with stale-free entries; and   execute the de-duplication operation using the fingerprints datastore having the stale-free entries.   
     
     
         18 . The non-transitory computer-readable medium of  claim 14 , wherein the instructions to cause the one or more processors to remove the stale entries in the fingerprints datastore using the stale entry information include instructions to cause the one or more processors to identify entries in the fingerprints datastore that correspond to the entries in the stale entries datastore as stale entries. 
     
     
         19 . The non-transitory computer-readable medium of  claim 14 , wherein the stale entry information includes a stale entry for a data block of the plurality of data blocks, the stale entry including an entry index for the stale entry, the fingerprint of the data block, context information for the data block, an inode number of a file to which the data block belongs, and a file block number of the data block. 
     
     
         20 . The non-transitory computer-readable medium of  claim 14 , wherein the instructions further include instructions to cause the one or more processors to:
 in response to a determination that the request for the de-duplication operation is received during execution of a verify operation, suspend the verify operation, store a current state of the verify operation to the storage device, and mark the fingerprints datastore as read-only.