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 for representing the presence of a subblock in a storage system, comprising:
hashing a subblock to obtain an index hash value for the subblock;
creating an array of bits using a function that inputs the index hash value for the subblock and outputs bits into the array of bits and maps the subblock to a position in the array of bits, where a bit in the array of bits is a predetermined bit value that indicates whether at least one subblock in the storage system maps to the bit position in the array of bits;
selectively storing the index hash value in a subblock index located on the storage system if the subblock is absent from the storage system;
selectively storing the index hash value in a subblock index entry write buffer located in memory if the subblock is absent from the storage system, where the index entry write buffer is divided into a plurality of buffer portions corresponding to a portion of the subblock index located on the storage system; and
transferring the contents of the index entry write buffer to the subblock index located on the storage system using a single sequential read and write operation of the storage system.
2. The method of claim 1 , where the function is a hash function.
3. The method of claim 1 , where the function is calculated using a cryptographic hash function whose result is input into a second calculation.
4. The method of claim 3 , where the second calculation is a modulo K operation, where K is the number of bits in the array of bits.
5. The method of claim 1 , where the function is calculated using a non-cryptographic hash function whose result is input into a second calculation.
6. The method of claim 5 , where the second calculation is a modulo K operation, where K is the number of bits in the array of bits.
7. The method of claim 1 , where a plurality of functions map a subblock to a position in the array of bits, and where a bit in the array of bits is said predetermined bit value when at least one subblock function combination maps to the bit position in the array of bits.
8. The method of claim 7 , where the array of bits is divided into one or more sections.
9. The method of claim 8 , where a section is compressed by a compression method.
10. A method for determining whether a subblock z is absent in a storage system by applying functions of claim 7 to the subblock z and testing the value of the corresponding bits of a array of bits created in accordance with the method of claim 7 , where the subblock is absent if tested bits of the array of bits are a further predetermined bit value.
11. The method of claim 1 , where the index entry write buffer is partitioned into a plurality of sections, and where data of a section is transferred to the subblock index on the storage system when a data capacity of the section is full.
12. The method of claim 1 , where when the index entry write buffer becomes full to a predetermined level, the index is read into memory, and the elements in the index entry write buffer are added to the index and the modified index is then written to disk.
13. The method of claim 1 , where a set of subblocks is partitioned into a plurality of mutually exclusive spaces and a second array of bits represents the presence of a subblock in the storage system.
14. The method of claim 13 , where the partitioning of the subblock space is performed by hashing subblocks and splitting the space of subblock hashes using a binary digital search tree.
15. The method of claim 13 , where the index entry write buffer is correspondingly divided.
16. The method of claim 1 , where the array of bits is stored in memory.
17. A method for determining whether a subblock z is absent in a storage system by applying the function of claim 1 , to the subblock z and testing the value of the corresponding bit of the array of bits, the array of bits having been created in accordance with the method of claim 1 .
18. A method for determining, within a sequence of subblocks, the nonexistence of contiguous runs of at least T present subblocks at various positions in the sequence, by using the method of claim 17 to test subblocks in the sequence for its definite absence.