Method and apparatus for detecting the presence of subblocks in a reduced-redundancy storage system

• US 20070192548A1
• Filed: 03/10/2006
• Published: 08/16/2007
• Est. Priority Date: 03/11/2005
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Williams, Ross
• Granted Patent: US 8,051,252 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files

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.

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.

2. The method of claim 1 wherein the function is a hash function.

3. The method of claim 1 wherein the function is calculated using a first calculation being a cryptographic hash function whose result is input into a second calculation.

4. The method of claim 1 wherein the function is calculated using a first calculation being a non-cryptographic hash function whose result is input into a second calculation.

5. The method of claim 3 wherein the second calculation is a modulo K operation, where K is the number of bits in the bitfilter.

6. The method of claim 1 wherein the number of bits in the bitfilter is a power of 2.

7. The method of claim 1 wherein there is a plurality of functions, each of which maps a subblock to a position in the bitfilter, and where each bit in the bitfilter is said predetermined bit value if and only if at least one subblock/function combination maps to the bit'"'"'s position.

8. The method of claim 1 wherein the bitfilter is divided into one or more sections.

9. The method of claim 8 wherein each of one or more sections is compressed by applying a compression method.

10. The method of claim 9 wherein the compression method is a Tanaka/Leon-Garcia mode-m code.

11. The method of claim 9 wherein the compression method is run-length encoding.

12. The method of claim 9 wherein the compression method is arithmetic coding.

13. The method of claim 7 wherein the bitfilter is divided into one or more sections.

14. The method of claim 13 wherein each of one or more sections is compressed by applying a compression method.

15. The method of claim 14 wherein the compression method is a Tanaka/Leon-Garcia mode-m code.

16. The method of claim 14 wherein the compression method is run-length encoding.

17. The method of claim 14 wherein the compression method is arithmetic coding.

18. The method of claim 1 including the further step of:

creating an index of subblocks containing index entries that map a subblock or a subblock hash to a location in the subblock storage system; and

creating one or more index entry write buffers for holding newly created subblock index entries;

wherein the content of an index entry write buffer is written to the subblock index from time to time.

19. The method in claim 18 wherein the index resides on disk and the index entry buffer resides in memory.

20. The method in claim 19 wherein 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 it and the modified index is then written to disk.

21. The method of claim 1 wherein the set of all possible subblocks is partitioned into a plurality of mutually exclusive spaces and a separate bitfilter is used to represent the presence or absence of actual subblocks in the storage system that fall within each space.

22. The method of claim 21 wherein the partitioning of the subblock space is performed by hashing subblocks and splitting the space of subblock hashes using a digital search tree.

23. The method of claim 21 wherein the index entry buffer is correspondingly divided.

24. The method of claim 18 wherein the bitfilter is in memory.

25. 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 bitfilter, the bitfilter having been created in accordance with the method of claim 1.

26. A method for determining whether a subblock z is absent in a storage system by applying each of the functions of claim 7 to the subblock z and testing the value of the corresponding bits of a bitfilter created in accordance with the method of claim 7, wherein the subblock is absent if all tested bits of the bitfilter are a further predetermined bit value.

27. A method for determining, within a sequence of subblocks, the non-existence of contiguous runs of at least T present subblocks at various positions in the sequence, by using the method of claim 25 to test each subblock in the sequence for its definite absence.

28. A method for storing a BLOB of data in a storage, communication or comparison system using the method of claim 19, comprising of the further steps of:

dividing the BLOB into subblocks using a partitioning method; and

using the bitfilter to determine whether each subblock is absent from the storage system; and

if a subblock is absent, setting to a predetermined bit value the bit in the array of bits corresponding to the subblock, and adding an entry for the subblock to the index entry buffer.

33. The method of claim 4 wherein the second calculation is a modulo K operation, where K is the number of bits in the bitfilter.

34. The method of claim 18 wherein the index entry buffer is correspondingly divided.

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.

30. A data processing apparatus for storing one or more BLOBs of data using the apparatus according to claim 29, the apparatus further comprising of:

a disk data storage, wherein

the data processing means divides each BLOB into subblocks using a partitioning method, and creates an index of subblocks on the disk containing index entries that map a subblock or a subblock hash to a location in the storage system, and wherein the memory data storage has one or more index entry write buffers for holding newly created subblock index entries, the data processing means uses the bitfilter to determine whether each subblock is absent from the storage system; and

if a subblock is absent, setting to said predetermined bit value the corresponding bit in the array of bits in the bitfilter, and adding an entry for the subblock to an index entry buffer and wherein the content of an index entry write buffer in memory is written to the subblock index on disk from time to time.

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.