Method and Apparatus For Detecting The Presence of Subblocks in a Reduced Redundancy Storing System
OwnerRoss Neil WILLIAMSinventor
Life of this patent
Estimating the term…
Loading patent…
OwnerRoss Neil WILLIAMSinventor
Estimating the term…
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.
A method for representing, in a lossy manner, the existence of subblocks residing in a storage system, the method including the step of,
A data processing apparatus for representing, in a lossy manner, the existence of subblocks residing in a storage system;
A computer readable memory, encoded with data representing a computer program that can be used to direct a programmable device for representing, in a lossy manner, the existence of subblocks residing in a storage system, using a processing means for operating the computer readable memory to create an array of bits (bitfilter) using a function that maps a subblock to a position in the bitfilter, where each bit in bitfilter is a predetermined bit value if and only if at least one subblock in the storage system maps to the bit's position.
A computer program element comprising a computer program code means for representing, in a lossy manner, the existence of subblocks residing in a storage system, to make a programmable device execute:
Dependencies are inferred from the claim text.