Method and apparatus for detecting the presence of subblocks in a reduced redundancy storing system
View Patent ↗This application concerns determining whether a particular subblock of data is present in a reduced-redundancy storage system. One embodiment achieves this by hashing subblocks in the storage system into a bitfilter that contains ‘1’ bit for each position to which at least one subblock hashes. This bitfilter provides a fast way to determine whether a subblock is in the storage system. In another embodiment, index entries for new subblocks may be buffered in a subblock index write buffer 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 other systems that store the entire subblock index in memory.
1. A method for controlling a reduced redundancy storage system to selectively transfer the contents of an index entry write buffer associated with the reduced redundancy storage system to a subblock index associated with the reduced redundancy storage system, comprising:
configuring a bitfilter associated with the subblock index with information sufficient to correctly report that a subblock is not present in the reduced redundancy storage system;
accessing a subblock to be considered for inclusion in the reduced redundancy storage system;
upon determining that the bitfilter indicates that the sublock to be considered is not known to the reduced redundancy storage system:
selectively storing an index hash value associated with the subblock to be considered in the subblock index entry write buffer, where the subblock index entry write buffer is located in a first storage area accessible to the reduced redundancy storage system, the first storage area having a faster access time than a second, different storage area; and
updating the bitfilter with information sufficient to correctly report that the subblock to be considered is known to the reduced redundancy storage system; and
upon determining that a property of the sublock index entry write buffer has exceeded a threshold, selectively transferring the contents of the index entry write buffer to the subblock index, where the subblock index is located in the second, different storage area accessible to the reduced redundancy storage system, and where the index entry write buffer is divided into a plurality of portions corresponding to portions of the subblock index.
2. The method of claim 1 , where the bitfilter comprises a plurality of bits, where a bit in the bitfilter is one of, a first predetermined value that inconclusively indicates that the subblock to be considered is known to the reduced redundancy storage system, and a second predetermined value that conclusively indicates that the subblock to be considered is not known to the reduced redundancy storage system.
3. The method of claim 2 , where determining that the bitfilter indicates that the subblock to be considered is not known to the reduced redundancy storage system comprises:
hashing the subblock to be considered to obtain a first hash;
using the first hash as an index into the bitfilter; and
analyzing the value of the bit found at the location in the bitfilter indexed by the first hash.
4. The method of claim 3 , where updating the bitfilter to indicate that the subblock to be considered is now known to the reduced redundancy storage system comprises selectively storing a bit associated with the subblock being considered in the bitfilter, where the bit associated with the subblock being considered is determined using a function that inputs an index value derived from a hash of the subblock and that maps the subblock to a position in the bitfilter.
5. The method of claim 3 , where updating the bitfilter to indicate that the subblock to be considered is now known to the reduced redundancy storage system comprises selectively storing a bit associated with the subblock in a bitfilter buffer located in the first storage area.
6. The method of claim 3 , comprising:
upon determining that a property of the bitfilter buffer has exceeded a threshold, selectively transferring the contents of the bitfilter buffer to a bitfilter located in the second storage area,
where the bitfilter buffer is divided into a plurality of buffer portions corresponding to a portion of the subblock index.
7. An apparatus, comprising:
a processor;
a memory;
a set of logics; and
an interface configured to connect the processor, the memory, and the set of logics;
the set of logics comprising:
a first logic configured to manage a pool of sub-blocks for a reduced redundancy storage system;
a second logic configured to manage an index of sub-blocks stored in the pool;
a third logic configured to manage an index buffer associated with the index;
a fourth logic configured to manage a bit-filter associated with the index, where the fourth logic maintains, in the bit-filter, information sufficient to conclusively determine that a sub-block is not in the pool; and
a fifth logic configured to access a sub-block presented to the apparatus and to determine whether the sub-block is to be added to the pool based, at least in part, on information stored in the bit-filter;
where the first logic selectively adds the sub-block presented to the apparatus to the pool upon determining that the bit-filter indicates that the sub-block presented is not in the pool,
where the second logic manages the index as having a plurality of index portions;
where the third logic selectively adds index information associated with the sub-block presented to the index buffer and where the third logic manages a plurality of index buffers corresponding to the plurality of index portions;
where the fourth logic selectively adds information to the bit-filter concerning the sub-block presented; and
where the third logic selectively copies information from the index buffer to the index upon determining that a pre-determined condition associated with the index buffer has occurred.