Method and apparatus for detecting the presence of subblocks in a reduced-redundancy storage system
View Patent ↗Method and apparatus for rapidly determining whether a particular subblock of data is present in a reduced-redundancy storage system. An aspect of the invention achieves this by hashing each subblock in the storage system into a bitfilter that contains a ‘1’ bit for each position to which at least one subblock hashes. This bitfilter provides an extremely fast way to determine whether a subblock is in the storage system. In a further aspect of the invention, index entries for new subblocks may be buffered in a subblock index write buffer so as to convert a large number of random access read and write operations into a single sequential read and a single sequential write operation. The combination of the bitfilter and the write buffer yields a reduced-redundancy storage system that uses significantly less high speed random access memory than is used by systems that store the entire subblock index in memory.
1. A method, comprising:
upon determining that a bitfilter indicates that a subblock is not known to a deduplication storage system:
selectively storing an index hash value associated with the subblock in a subblock index entry write buffer located in a first storage area; and
updating the bitfilter to indicate that the subblock is now known to the deduplication storage system; and
upon determining that a property of the subblock index entry write buffer has exceeded a threshold, selectively transferring the contents of the index entry write buffer to a subblock index located in a second storage area,
where the index entry write buffer is divided into a plurality of portions corresponding to portions of a subblock index located in the deduplication storage system,
where the first storage area is located in a solid state drive (SSD) and where the second storage area is located on a non-solid state disk drive.
2. A method, comprising:
upon determining that a bitfilter indicates that a subblock is not known to a deduplication storage system:
selectively storing an index hash value associated with the subblock in a subblock index entry write buffer located in a first storage area; and
updating the bitfilter to indicate that the subblock is now known to the deduplication storage system; and
upon determining that a property of the subblock index entry write buffer has exceeded a threshold, selectively transferring the contents of the index entry write buffer to a subblock index located in a second storage area,
where the index entry write buffer is divided into a plurality of portions corresponding to portions of a subblock index located in the deduplication storage system, and
where determining that a bitfilter indicates that a subblock is not known to the deduplication storage system comprises:
hashing the subblock to obtain a first hash;
hashing the first hash to obtain one or more second hashes;
using the one or more second hashes as indexes into the bitfilter; and
analyzing the values of the bits found at the one or more locations indexed by the one or more second hashes.
3. A deduplication storage system, comprising:
a first data storage apparatus configured to store first data in one or more first data structures; and
a second data storage apparatus configured to store second data in one or more second data structures,
where the first data storage apparatus is faster to access than the second data storage apparatus,
where the first data structures include one or more of, a bitfilter buffer, a first portion of a bitfilter, an index entry buffer, a first portion of an index, a subblock buffer, and a first portion of a deduplication subblock pool,
where the second data structures include one or more of, a second portion of the bitfilter, a second portion of the index, and a second portion of the deduplication subblock pool,
where the index is divided into portions and stores information concerning the location of subblocks in the deduplication subblock pool,
where the bitfilter stores information about the absence of subblocks in the deduplication subblock pool,
where the index entry buffer is divided into a plurality of portions corresponding to portions of the index, and
where the bitfilter buffer is divided into a plurality of portions corresponding to the portions of the index.
4. The system of claim 3 , where the first data storage apparatus is random access memory and the second data storage apparatus is a solid state drive (SSD).
5. The system of claim 3 , where the first data storage apparatus is a solid state drive and the second data storage apparatus is a non-solid state disk drive.
6. The system of claim 3 , where the index is organized as a tree of hash tables, and where the bitfilter includes bitfilter portions corresponding to the hash tables in the tree of hash tables.
7. The system of claim 6 , comprising a split apparatus configured to split a hash table associated with the index into two or more hash tables associated with the index upon determining that a hash table property has exceeded a desired hash table property threshold.
8. The system of claim 7 , the hash table property being the degree to which the hash table is full.
9. The system of claim 7 , the split apparatus being configured to resize a bitfilter portion corresponding to the hash table that is split into two or more hash tables.
10. The system of claim 3 , comprising a density apparatus configured to resize a bitfilter portion upon determining that a bitfilter property for the bitfilter portion has exceeded a desired bitfilter property threshold.
11. The system of claim 10 , the bitfilter property being bitfilter density.
12. The system of claim 3 , the bitfilter being configured to represent the absence of a subblock on a remote computer.
13. The system of claim 12 , the remote computer being a member of a peer to peer deduplication environment.
14. The system of claim 3 , where the first portion of the bitfilter stores information about the absence of runs of N or more subblocks in the deduplication subblock pool, N being an integer greater than one.
15. The system of claim 3 , comprising a reconfiguration logic configured to move a member of the one or more first data structures from the first data storage apparatus to the second data storage apparatus upon determining that a usage property of the member has exceeded a usage threshold.
16. The system of claim 15 , the usage threshold being associated with access frequency.
17. The system of claim 15 , the reconfiguration logic being configured to move a member of the one or more second data structures from the second data storage apparatus to the first data storage apparatus upon determining that a usage property of the member of the one or more second data structures has exceeded a second usage threshold.
18. The system of claim 17 , the second usage threshold being associated with access frequency.
19. The system of claim 3 , comprising a reconfiguration logic configured to move a member of the one or more second data structures from the second data storage apparatus to the first data storage apparatus upon determining that a usage property of the member has exceeded a usage threshold.
20. The system of claim 19 , the usage threshold being associated with access frequency.
21. A multi-layered deduplication storage system, comprising:
three or more different data storage apparatus having different access times, where the data storage apparatus are configured to store data in one or more of, a bitfilter buffer, a bitfilter, an index entry buffer, an index, a subblock buffer, and a deduplication subblock pool; and
logic configured to dynamically move data between members of the three or more data storage apparatus,
where the index stores information concerning the location of subblocks in the deduplication subblock pool,
where the bitfilter stores information about the absence of subblocks in the deduplication subblock pool,
where the index entry buffer is divided into a plurality of portions corresponding to portions of the index, and
where the bitfilter buffer is divided into a plurality of portions corresponding to the portions of the index.