Method and apparatus for detecting the presence of subblocks in a reduced-redundancy storage system
First Claim
1. A method for representing, in a lossy manner, the existence of subblocks residing in a storage system, the method including the step of:
- creating 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 at least one subblock in the storage system maps to the bit'"'"'s position.
11 Assignments
0 Petitions
Accused Products
Abstract
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.
-
Citations
34 Claims
-
1. A method for representing, in a lossy manner, the existence of subblocks residing in a storage system, the method including the step of:
creating 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 at least one subblock in the storage system maps to the bit'"'"'s position. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 33, 34)
-
29. A data processing apparatus for representing, in a lossy manner, the existence of subblocks residing in a storage system, comprising of:
-
a memory data storage, and data processing means for creating an array of bits (bitfilter) in memory 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. - View Dependent Claims (30)
-
-
31. 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.
-
32. 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:
a first function of creating 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.
Specification