Method and apparatus for indexing in a reduced-redundancy storage system
View Patent ↗Method and apparatus for indexing subblocks in a reduced-redundancy storage system. Each subblock is hashed to an K-bit key and an entry for the subblock added to an index data structure comprising of a tree of hash tables. In a further aspect, by replacing the top of the tree with an array, the data structure can achieve O( 1 ) access time for random keys while still providing relatively smooth growth.
1. A method for controlling a reduced redundancy storage system to index data in the reduced redundancy storage system, by indexing one or more unique blocks of data processed by the reduced redundancy storage system, the method comprising:
creating an index on the reduced redundancy storage system, the index comprising a digital search tree having non-leaf nodes and descendant-free leaf nodes, the digital search tree having keys derived from the unique blocks;
where a descendent-free leaf node of the tree comprises a hash table configured to store an index value for a key that falls within the descendent-free leaf node;
where the hash table has a fullness splitting threshold,
where the threshold for the hash table has a random component;
where the non-leaf nodes are stored in a computer random access memory,
where an index value comprises the location of a unique block in a unique block pool of the reduced redundancy storage system;
where the keys derived from the unique blocks are separate from the index values; and
performing a leaf hash table lookup at the end of a binary tree root to leaf traversal of the digital search tree in a single random access disk seek.
2. The method of claim 1 , where the digits of the digital search tree correspond to the successive bits of the key.
3. The method of claim 1 , where the hash table comprises buckets.
4. The method of claim 1 , where the keys are fixed length hashes of unique blocks in the unique block pool of the reduced redundancy storage system.
5. The method of claim 4 , where part of the hash of the block is used to index the hash table.
6. The method of claim 1 , where the hash tables associated with the leaves are stored in an array.
7. The method of claim 6 , where the array is in memory.
8. The method of claim 1 , where the top L levels of a subtree of the digital search tree are replaced by an array.
9. The method of claim 8 , where the top L levels of the digital search tree are replaced by an array.
10. The method of claim 8 , where the array has 2L elements.
11. The method of claim 8 , where the replacement is performed when the L levels of the subtree satisfy a predetermined criterion.
12. The method of claim 11 , where the predetermined criterion is that the top L levels of the subtree consists of non-leaf nodes.
13. The method of claim 11 , where the predetermined criterion is that the top L levels of the subtree contain at least T percent non-leaf nodes where T is a predetermined threshold.
14. The method of claim 1 , where the digital search tree is expanded by replacing a leaf node with a non-leaf node having a plurality of new leaf nodes attached, where the contents of the hash table in the old leaf node is distributed among the hash tables of the new leaf nodes.
15. The method of claim 14 , where expansion occurs when the fullness of a hash table exceeds a predetermined threshold.
16. The method of claim 14 , where a new leaf is created with the hash table, where the hash table is configured to vary in size.
17. The method of claim 16 , where the size of the hash table is chosen between a predefined minimum and a predefined maximum.
18. The method of claim 17 , where the size of the hash table is chosen randomly between a predefined minimum and a predefined maximum.
19. The method of claim 16 , where the determination of the size has a random component.
20. The method of claim 14 , where the hash table is split by reading the hash table into memory, splitting the hash table into two hash tables, and writing the two hash tables to disk.
21. The method of claim 14 , where storage space consumed by the hash table of the original leaf is reallocated to be the hash table of one of the descendent leaves.
22. The method of claim 14 , where the hash table uses overflow chains, and where the hash table is split when the longest overflow chain reaches a predetermined threshold.
23. The method of claim 14 , where the hash table uses overflow chains, and where the hash table is split when an overflow chain greater than a predetermined length is traversed.
24. The method of claim 14 , where the hash table is split when the hash table becomes full or with a predetermined probability P whenever a key/value pair is added to the hash table.
25. The method of claim 1 , where the digital search tree is held in memory and the hash tables in the leaves are held on disk.
26. The method of claim 1 , where the keys are first hashed using a secret key configured to prevent a complexity attack on the data structure.
27. The method of claim 1 , where the location of the block is one of, a position of the block on disk, a filename of a file in which the block is stored, a file number of a file in which the block is stored, a block cluster number of a cluster in which the block is stored, a combination of a cluster number and block identifier within the cluster.
28. The method of claim 1 , where the location of the block is the location of the block in a network.
29. A non-transitory computer-readable medium storing computer executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:
maintaining an index for data blocks in a data de-duplication system, where the index includes a search tree with non-leaf nodes and descendant-free leaf nodes, where a descendant-free leaf node includes a hash table that stores an index value for a key that maps to the descendant-free leaf node, where the hash table has a fullness splitting threshold, and where the threshold for the hash table has a random component, where the key is derived from a data block in the data de-de-duplication system and is separate from the index value, and where the non-leaf nodes are maintained in an array in a first memory and the leaf-nodes are stored in a second memory that is a higher latency than the first memory; and
performing a hash table lookup for a data block using the search tree, where the hash table lookup occurs in a single disk seek, and where an index value returned from the hash table lookup includes a pointer to the data block in the data de-duplication system.