Two-stage front end for extent map database

Abstract

Multiple key-value stores may be employed to smooth out random updates (based on the extent ID) to the EMAP database. The updates to the EMAP database occur in a two-stage manner: (i) using an append-only log store for the first stage and (ii) using an on-disk hash store for the second stage. The append-only log store is used to convert the random updates to sequential write operations on the EMAP database. Once full, the contents of the log store are sorted and moved to the on-disk hash store, which holds the updates for a transient period of time to enable batching of the updates. Once sufficient batching of the extent map entries are accumulated, those entries are sorted and moved to the EMAP database. Thereafter, the EMAP database can be scanned to find extent map entries having identical checksum bits to perform data deduplication.

What is claimed is: 
     
         1 . A method comprising:
 storing extent identifiers of extents into a data structure as extent entries comprising the extent identifiers and corresponding storage location identifiers of the extents;   sorting the extent identifiers in the data structure based upon expiration of a time period;   prioritizing deduplication of the extents based upon the data structure.   
     
     
         2 . The method of  claim 1 , wherein the prioritizing comprises:
 organizing data of write requests into a new extent, wherein the data is hashed to generate checksum bits of an extent identifier of a new extent entry for the new extent.   
     
     
         3 . The method of  claim 2 , wherein the prioritizing comprises:
 determining that the checksum bits of the new extent entry match checksum bits of an existing extent entry, wherein matching checksum bits of the new extent entry are incremented within the data structure.   
     
     
         4 . The method of  claim 3 , wherein the new extent entry is inserted into the data structure with a score corresponding to a greatest duplicate bit value, wherein the score is used to prioritize deduplication of the extents. 
     
     
         5 . The method of  claim 3 , wherein the new extent entry is inserted into the data structure as an update to a leaf node with a score corresponding to a total number of extent entries on the leaf node, wherein the score is used to prioritize deduplication of the extents. 
     
     
         6 . The method of  claim 5 , wherein the data structure comprises a tree structure, and wherein each leaf node accumulates duplicate bits as a change log of extent identifiers are inserted into the tree structure to create scores representing total numbers of recipients outstanding on each leaf node. 
     
     
         7 . The method of  claim 6 , wherein a recipient is configured to share an extent from a donor. 
     
     
         8 . The method of  claim 1 , wherein an extent identifier within the data structure comprises a checksum generated from an extent and a counter used to distinguish between matching checksums. 
     
     
         9 . The method of  claim 1 , wherein the data structure comprises a key-value store, wherein the extent identifiers are keys and the storage location identifiers are values. 
     
     
         10 . The method of  claim 1 , comprising:
 inserting an extent entry into a node of the data structure based upon a determination that the node includes an existing extent entry with a checksum of an extent identifier of the extent entry, wherein a score for the node is updated based upon a number of extent entries in the node with a same checksum, wherein the score is used to prioritize deduplication of the extents.   
     
     
         11 . The method of  claim 10 , comprising:
 marking a dirty bit for a second node within the data structure based on a determination that the second node has a second extent entry with a second checksum matching the checksum of the extent entry being inserted into the node.   
     
     
         12 . The method of  claim 1 , wherein the prioritizing comprises:
 searching the data structure using a partial cuckoo hash of an extent based upon a write operation, wherein a matching result of the search is deduplicated.   
     
     
         13 . A non-transitory machine readable medium comprising instructions for performing a method, which when executed by a machine, causes the machine to:
 store wherein the prioritizing comprises;   sort the extent identifiers in the data structure based upon expiration of a time period;   prioritize deduplication of extents based upon the data structure.   
     
     
         14 . The non-transitory machine readable medium of  claim 13 , wherein the instructions cause the machine to:
 organize data of write requests into a new extent, wherein the data is hashed to generate checksum bits of an extent identifier of a new extent entry for the new extent.   
     
     
         15 . The non-transitory machine readable medium of  claim 14 , wherein the instructions cause the machine to:
 determine that the checksum bits of the new extent entry match checksum bits of an existing extent entry, wherein matching checksum bits of the new extent entry are incremented within the data structure.   
     
     
         16 . The non-transitory machine readable medium of  claim 15 , wherein the new extent entry is inserted into the data structure with a score corresponding to a greatest duplicate bit value, wherein the score is used to prioritize deduplication of the extents. 
     
     
         17 . The non-transitory machine readable medium of  claim 15 , wherein the new extent entry is inserted into the data structure as an update to a leaf node with a score corresponding to a total number of extent entries on the leaf node, wherein the score is used to prioritize deduplication of the extents, 
     
     
         18 . The non-transitory machine readable medium of  claim 17 , wherein the data structure comprises a tree structure, and wherein each leaf node accumulates duplicate bits as a change log of extent identifiers are inserted into the tree structure to create scores representing total numbers of recipients outstanding on each leaf node. 
     
     
         19 . The non-transitory machine readable medium of  claim 18 , wherein a recipient is configured to share an extent from a donor. 
     
     
         20 . A computing device comprising:
 a memory comprising machine executable code for performing a method; and   a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
 store extent identifiers of extents into a data structure as extent entries comprising the extent identifiers and corresponding storage location identifiers of the extents; 
 sort the extent identifiers in the data structure based upon expiration of a time period; 
 prioritize deduplication of extents based upon the data structure.