Back to results
US 2007/0192548 A1Published application
Method and apparatus for detecting the presence of subblocks in a reduced-redundancy storage system
OwnerRoss Williamsinventor
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
OwnerRoss Williamsinventor
Estimating the term…
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.
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, comprising of:
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 the 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.