Memory efficient lookup structure

Patent metadata

Field	Value
Publication number	US-10366065-B2
Application number	US-201615142828-A
Country	US
Kind code	B2
Filing date	Apr 29, 2016
Priority date	Apr 29, 2016
Publication date	Jul 30, 2019
Grant date	Jul 30, 2019

Abstract

A method for mapping a first address space to a second address space is provided. In some embodiments, the method includes creating a first array of lookup entries and one or more second arrays of metadata entries for maintaining an ordering among the lookup entries using a tree structure. Each of the metadata entries includes one or more data index values identifying a corresponding one of the lookup entries by its position in the first array and one or more metadata index values identifying a corresponding one of the metadata entries by its position in one of the one or more second arrays. The method further includes receiving a request including a lookup value, traversing the tree structure to locate a lookup entry corresponding to the lookup value, and when the lookup value is located among the lookup entries, using the located lookup entry to process the request.

First claim

What is claimed is:

1. A method comprising:
utilizing, by a computing device, a first array of data lookup entries and a second array of a plurality of metadata entries for maintaining an ordering among the data lookup entries in the first array using a tree structure, each of the metadata entries being associated with a corresponding level of a plurality of levels and storing:
a first data index value identifying a data lookup entry in the first array;
a first metadata index value identifying a metadata entry in a same level of the tree structure; and
a second metadata index identifying a metadata entry in a level below the corresponding level of the tree structure;

locating a data lookup entry in the first array, the data lookup entry corresponding to a lookup value, associated with a received request, from among the data lookup entries in the first array; and
processing the request in response to locating the lookup value among the data lookup entries in the first array.

2. The method of claim 1 , wherein:
processing the request comprises translating a first address in a first address space to a second address in a second address space using the located data lookup entry.

3. The method of claim 2 , wherein the first address is located within a range of addresses in the first address space identified by the located data lookup entry.

4. The method of claim 1 , further comprising:
updating the tree structure to add a new data lookup entry to the tree structure while maintaining the ordering among the data lookup entries in the first array.

5. The method of claim 4 , wherein updating the tree structure comprises rebalancing the tree structure.

6. The method of claim 1 , wherein each of the metadata entries in a lowest level of the plurality of levels has a same position in the second array as a corresponding data lookup entry in the first array.

7. The method of claim 1 , wherein a number of metadata entries is between a first predetermined number and a second predetermined number.

8. The method of claim 6 , wherein the lowest level is a leaf level.

9. The method of claim 1 , further comprising, maintaining a list of data entries deleted from the tree structure.

10. A non-transitory machine readable medium having stored thereon instructions for performing a method comprising machine executable code which when executed by at least one machine, causes the machine to:
utilize a first array of lookup nodes and a second array of a plurality of metadata nodes for maintaining an ordering among the lookup nodes in the first array using a multi-level structure, each of the metadata nodes being associated with a corresponding level of a plurality of levels and storing:
a first data index pointing to a position of a lookup node in the first array;
a first metadata index pointing to a position of a metadata node in a same level of the multi-level structure; and
a second metadata index pointing to a position of a metadata node in a level below the corresponding level of the multi-level structure;

locate a lookup node in the first array, the lookup node corresponding to a lookup value, associated with a received data transaction, from among the lookup nodes in the first array; and
process the data transaction in response to locating the lookup value among the lookup nodes in the first array.

11. The non-transitory machine readable medium of claim 10 , wherein:
to process the data transaction, the machine translates a first address in a first address space to a second address in a second address space using the located lookup node.

12. The non-transitory machine readable medium of claim 11 , wherein the first address is located within a range of addresses in the first address space identified by the located lookup node.

13. The non-transitory machine readable medium of claim 10 , the machine further:
updates the multi-level structure to add a new lookup node to the multi-level structure while maintaining the ordering among the lookup nodes in the first array.

14. The non-transitory machine readable medium of claim 13 , wherein updating the multi-level structure comprises rebalancing the multi-level structure.

15. The non-transitory machine readable medium of claim 10 , wherein each of the metadata nodes in a lowest level of the plurality of levels has a same position in the second array as a corresponding one of the lookup nodes in the first array.

16. The non-transitory machine readable medium of claim 15 , wherein a number of first metadata nodes is between a first predetermined number and a second predetermined number.

17. A computing device comprising:
a memory containing machine readable medium comprising machine executable code having stored thereon instructions for performing a method of processing requests; and a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
utilize a first array of data lookup entries and a second array of metadata entries for maintaining an ordering among the data lookup entries in the first array using a tree structure, each of the metadata entries being associated with a corresponding level of a plurality of levels and storing a first data index value identifying a data lookup entry by its position in the first array, a first metadata index value identifying a metadata entry in a same level of the tree structure by its position in the second array, and a second metadata index value identifying a metadata entry in a level below the corresponding level of the tree structure by its position in the second array;
locate a data lookup entry in the first array, the data lookup entry corresponding to a lookup value, associated with a received request, from among the data lookup entries; and
process the request in response to locating the lookup value among the data lookup entries.

18. The computing device of claim 17 , wherein:
to process the request the processor translates a first address in a first address space to a second address in a second address space using the located data lookup entry; and
the first address is located within a range of addresses in the first address space identified by the located data lookup entry.

19. The computing device of claim 17 , wherein the processor is further caused to:
update the tree structure to add a new data lookup entry to the tree structure while maintaining the ordering among the data lookup entries in the first array.

20. The computing device of claim 19 , wherein to update the tree structure the processor rebalances the tree structure.

Assignees

• Netapp Inc

Inventors

• Delaney William P
• Blount Joseph
• Binford Charles
• Moore Joseph
• Sterns Randolph
• Stilger Jeff

Classifications

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/9017

  using directory or table look-up (use of a directory or look-up table in file systems G06F16/13) · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title