Positional allocation

• US 7,640,262 B1
• Filed: 06/30/2006
• Issued: 12/29/2009
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Yang, Bin, Pocas, Jamie, Beaverson, Arthur
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US11/480,322
• Time in Patent Office: 1,278 Days
• Field of Search: 707/1, 707/4, 707/101, 711111-114
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Described are techniques for managing an index structure used to access data portions. A token having a token value for a data portion is provided. An entry in said index structure for said data portion is provided. The index structure is accessed using said token value as a key to determine said entry in said index structure for said data portion. The entry is allocated to have a location in accordance with said token value.

Claims

1. A method of managing an index structure used to access data portions comprising:

providing a token having a token value for a data portion;

providing an entry in said index structure for said data portion, wherein said index structure is accessed using said token value as a key to determine said entry in said index structure for said data portion, and wherein each entry of said index structure is allocated to have a physical storage location with a position relative to other physical storage locations of other entries in said index structure in accordance with said token value of said each entry, entries of said index structure having corresponding token values, said corresponding token values having a sequential ordering wherein physical storage locations of said entries are located at positions relative to one another in accordance with positions in said sequential ordering of said corresponding token values for said entries, wherein token values used as keys in connection with said index structure are approximately uniformly distributed with respect to a token value range;

determining an initial address of said entry in accordance with said token value of said data portion; and

if said initial address identifies a first physical storage location which is already allocated for use with another token value and corresponding entry of said index structure, determining a second address for said entry using a resolution technique identifying a second physical storage location which is an available storage location nearest to said first physical storage location initially determined, wherein said index structure includes a unique entry for each data portion and the data portion is stored in one or more data storage systems including only a single copy of each data portion, the unique entry including a reference count indicating a number of times the data portion is referenced in one or more data segments stored in said one or more data storage systems.

2. The method of claim 1, wherein said index structure is a B-tree index structure.

3. The method of claim 2, wherein said B-tree index structure is partitioned into a number of index structures, each of said index structures being associated with a portion of said token value range of token values for data portions.

4. The method of claim 1, wherein said entry is allocated from an allocation space having a size determined in accordance with a maximum number of possible nodes in said index structure.

5. The method of claim 1, wherein a size of the allocation space from which said entry is allocated is selected to be a value in a range of 10% to 20% more than a size associated with a maximum number of possible nodes in said index structure.

6. The method of claim 1, wherein each data portion has a same fixed length.

7. The method of claim 1, wherein a cache size is selected as being an integer value larger than an average distance between physical storage locations of entries in said index structure which are out of order with respect to two token values corresponding to the entries, wherein a first of said token values is less than a second of said token values, and a first entry in said index structure associated with said first token value is allocated at a first physical storage location and a second entry in said structure associated with said second token value is allocated at a second physical storage location, the first physical storage location having an address which is greater than an address of the second physical storage location.

8. The method of claim 7, wherein a cache size is selected as being an integer multiple of said average distance between physical storage locations of entries in said index structure which are out of order with respect to two token values corresponding to the entries.

9. The method of claim 1, further comprising:

storing said data portion at a storage location, wherein said entry indicates said storage location of said data portion and said index structure is accessed using said token value as a key to determine said storage location of said data portion.

10. A method of storing data comprising:

receiving a plurality of data portions and a corresponding token having a token value for each of the data portions; and

updating an access structure to include entries for said plurality of data portions, wherein the access structure is indexed by token values of the data portions, each of said entries for each token value being located at an address identifying a physical storage location at which storage is allocated for said entry, said physical storage location determined in accordance with said each token value, entries of said access structure having corresponding token values, said corresponding token values having a sequential ordering wherein physical storage locations of said entries are located at positions relative to one another in accordance with positions in said sequential ordering of said corresponding token values for said entries, wherein token values used as keys in connection with said index structure are approximately uniformly distributed with respect to a token value range;

wherein, for at least a first of said entries, the method further comprising;

determining an initial address of said first entry in accordance with said token value of said data portion; and

if said initial address identifies a first physical storage location which is already allocated for use with another token value and corresponding entry of said index structure, determining a second address for said first entry using a resolution technique identifying a second physical storage location which is an available storage location nearest to said first physical storage location initially determined, wherein said index structure includes a unique entry for each data portion and the data portion is stored in one or more data storage systems including only a single copy of each data portion, the unique entry including a reference count indicating a number of times the data portion is referenced in one or more data segments stored in said one or more data storage systems.

11. The method of claim 10, further comprising:

storing each of the data portions to a different storage location.

12. The method of claim 10, wherein each of said plurality of data portions are of a same size, and each token value is a hash value.

13. A computer readable storage medium comprising code stored thereon for managing an index structure used to access data portions, the computer readable medium comprising code executing instructions for:

providing a token having a token value for a data portion;

providing an entry in said index structure for said data portion, wherein said index structure is accessed using said token value as a key to determine said entry in said index structure for said data portion, and wherein each entry of said index structure is allocated to have a physical storage location with a position relative to other physical storage locations of other entries in said index structure in accordance with said token value of said each entry, entries of said index structure having corresponding token values, said corresponding token values having a sequential ordering wherein physical storage locations of said entries are located at positions relative to one another in accordance with positions in said sequential ordering of said corresponding token values for said entries, wherein token values used as keys in connection with said index structure are approximately uniformly distributed with respect to a token value range;

determining an initial address of said entry in accordance with said token value of said data portion; and

if said initial address identifies a first physical storage location which is already allocated for use with another token value and corresponding entry of said index structure, determining a second address for said entry using a resolution technique identifying a second physical storage location which is an available storage location nearest to said first physical storage location initially determined, wherein a cache size is selected as being an integer value larger than an average distance between physical storage locations of entries in said index structure which are out of order with respect to two token values corresponding to the entries, wherein a first of said token values is less than a second of said token values, and a first entry in said index structure associated with said first token value is allocated at a first physical storage location and a second entry in said structure associated with said second token value is allocated at a second physical storage location, the first physical storage location having an address which is greater than an address of the second physical storage location.

14. The computer readable storage medium of claim 13, wherein said index structure is a B-tree index structure.

15. The computer readable storage medium of claim 14, wherein said B-tree index structure is partitioned into a number of index structures, each of said index structures being associated with a portion of said token value range of token values for data portions.

16. The computer readable storage medium of claim 13, wherein said index structure includes a unique entry for each data portion and the data portion is stored in one or more data storage systems including only a single copy of each data portion, the unique entry including a reference count indicating a number of times the data portion is referenced in one or more data segments stored in said one or more data storage systems.

17. The computer readable storage medium of claim 13, wherein said entry is allocated from an allocation space having a size determined in accordance with a maximum number of possible nodes in said index structure.