Method and apparatus for indexing in a reduced-redundancy storage system

• US 20060271540A1
• Filed: 03/10/2006
• Published: 11/30/2006
• 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 Neil
• Granted Patent: US 8,356,021 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

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.

Claims

1. A method for indexing data for the purpose of storing, communicating or comparing data, by indexing one or more blocks of data, the method comprising the step of:

creating an index comprising a digital search tree having keys derived from said blocks, where each leaf of the tree has a table that contains a index value for each key that falls within that leaf.

2. The method according to claim 1 wherein the digital search tree is a binary digital search tree.

3. The method according to claim 2 wherein the digits of the digital search tree correspond to the successive bits of the key.

4. The method according to claim 1 wherein each table is a hash table.

5. The method of claim 4 wherein each hash table comprises buckets.

6. The method of claim 1 wherein each index value comprises the location of a block.

7. The method of claim 1 wherein the keys are hashes of blocks.

8. The method of claim 7 wherein part of the hash of the block is used to index the table.

9. The method of claim 1 wherein the tables associated with the leaves are stored in an array.

10. The method of claim 9 wherein the array is in memory.

11. The method of claim 9 wherein the array is on disk.

12. The method of claim 1 wherein the top L levels of a subtree of the tree are replaced by an array.

13. The method of claim 12 wherein the top L levels of the tree are replaced by an array.

14. The method of claim 12 wherein the tree is a binary digital search tree and the replacement array has 2^L elements.

15. The method of claim 12 wherein the replacement is performed when the L levels of the subtree satisfy a predetermined criterion.

16. The method of claim 15 wherein the predetermined criterion is that the top L levels of the subtree consists of non-leaf nodes.

17. The method of claim 15 wherein 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.

18. The method of claim 1 wherein 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 table in the old leaf node is distributed among the tables of the new leaf nodes.

19. The method of claim 18 wherein expansion occurs when the fullness of a table exceeds a predetermined threshold.

20. The method of claim 18 wherein the tables are hash tables.

21. The method of claim 20 wherein each hash table has a fullness splitting threshold.

22. The method of claim 21 wherein the threshold for each hash table has a random component.

23. The method of claim 18 wherein each new leaf is created with a hash table of varying size.

24. The method of claim 23 wherein the size of each hash table is chosen between a predefined minimum and a predefined maximum.

25. The method of claim 24 wherein the size of each hash table is chosen randomly between a predefined minimum and a predefined maximum.

26. The method of claim 23 wherein the determination of each size has a random component.

27. The method of claim 18 wherein a 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.

28. The method of claim 18 wherein storage space consumed by the table of the original leaf is reallocated to be the table of one of the descendent leaves.

29. The method of claim 18 wherein the table uses overflow chains, and wherein the table is split when the longest overflow chain reaches a predetermined threshold.

30. The method of claim 18 wherein the table uses overflow chains, and wherein the table is split when an overflow chain greater than a predetermined length is traversed.

31. The method of claim 18 wherein the table is split when it becomes full or with a predetermined probability P whenever a key/value pair is added to the table.

32. The method of claim 1 wherein the tree is held in memory and the hash tables in the leaves are held on disk.

33. The method of claim 1 wherein the keys are first hashed using a secret key so as to prevent a complexity attack on the data structure.

34. A data processing apparatus for indexing data for the purpose of storing, communicating or comparing data, by indexing one or more blocks of data, comprising of:

data processing means for creating an index comprising of a digital search tree having keys derived from said blocks, where each leaf of the tree has a table that maps the keys that fall within that leaf to their corresponding index values.

35. A computer readable memory, encoded with data representing a computer program that can be used to direct a programmable device for indexing data for the purpose of storing, communicating or comparing data, by indexing one or more blocks of data, using a processing means for operating the computer readable memory to use an index comprising of a digital search tree having keys derived from said blocks, where each leaf of the tree has a table that maps the keys that fall within that leaf to their corresponding index values.

36. A computer program element comprising a computer program code means for indexing data for the purpose of storing, communicating or comparing data, by indexing one or more blocks of data, to make a programmable device execute:

a first function of using an index comprising of a digital search tree having keys derived from said blocks, where each leaf of the tree has a table that maps the keys that fall within that leaf to their corresponding index values.