Select pages implementing leaf nodes and internal nodes of a data set index for reuse

• US 9,305,112 B2
• Filed: 09/14/2012
• Issued: 04/05/2016
• Est. Priority Date: 09/14/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Erdmann, Derek L., Reed, David C., Reed, Thomas C., Smith, Max D.
• Primary Examiner(s): CARDWELL, ERIC
• Application Number:
  US13/619,962
• Publication Number:
  US 20140082316A1
• Time in Patent Office: 1,299 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Provided are a computer program product, system, and method for selecting pages implementing leaf nodes and internal nodes of a data set index for reuse in memory. Pages in the memory are allocated to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set, wherein the leaf nodes include information on members of the data set. The internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes to access the members of the data set. At least one page allocated to the leaf nodes and the internal nodes is selected based on durations during which the allocated pages have not been used. Pages allocated to the leaf nodes are selected for reuse at a higher rate than the pages allocated to the internal nodes.

Claims

1. A computer program product for managing a data set stored in a storage in a memory, the computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therein that executes to perform operations, the operations comprising:

allocating pages in the memory to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set, wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set;

selecting at least one page allocated to the leaf nodes and the internal nodes based on durations during which the allocated pages have not been used, wherein pages allocated to the leaf nodes are selected for reuse at a higher rate than the pages allocated to the internal nodes; and

indicating the selected at least one page as available for reuse to store data for a data set member or as a node in the data set index.

2. The computer program product of claim 1, wherein the operations further comprise:

opening an additional data set; and

allocating at least one page indicated as available for reuse to at least one of the internal nodes and leaf nodes representing an additional data set index for the additional data set.

3. The computer program product of claim 1, wherein one page is allocated to each of the internal nodes and leaf nodes of the data set index.

4. The computer program product of claim 1, wherein selecting the at least one page based on the durations during which the allocated pages have not been used comprises:

determining whether pages allocated to the leaf nodes have not been used for a leaf node duration; and

determining whether pages allocated to the internal nodes have not been used for an internal node duration, wherein the selected at least one page comprises at least one of the pages that have not been used for the leaf node duration or the internal node duration.

5. The computer program product of claim 4, wherein the internal node duration is greater than the leaf node duration to retain the pages for the internal nodes in the memory longer than the pages for the leaf nodes.

6. The computer program product of claim 4, wherein a page for a root node of the tree data structure is retained in memory until the data set is closed and wherein there is one level of the internal nodes between the root node and the leaf node.

7. The computer program product of claim 4, wherein the leaf and internal node durations comprise a number of clock cycles, wherein the leaf node duration number of cycles is less than the internal node duration number of cycles.

8. The computer program product of claim 4, wherein, the operations further comprise:

determining a utilization ratio based on a number of the allocated pages that have been accessed and are unavailable for reuse and a total number of pages allocated for use with data sets;

determining whether the determined utilization ratio exceeds a target utilization ratio;

decreasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio exceeds the target utilization ratio; and

increasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio is less than the target utilization ratio.

9. The computer program product of claim 4, wherein the operation to select the at least one page to reuse is periodically performed, wherein there is a reuse selection interval between operations to select the at least one page, and wherein the reuse selection interval is greater than the leaf and the internal node durations.

10. A system for managing a data set stored in a storage, comprising:

a processor;

a memory;

a computer readable storage medium having code executed by the processor to perform operations, the operations comprising;

allocating pages in the memory to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for the data set, wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set;

selecting at least one page allocated to the leaf nodes and the internal nodes based on durations during which the allocated pages have not been used, wherein pages allocated to the leaf nodes are selected for reuse at a higher rate than the pages allocated to the internal nodes; and

indicating the selected at least one page as available for reuse to store data for a data set member or as a node in the data set index.

11. The system of claim 10, wherein the operations further comprise:

opening an additional data set; and

allocating at least one page indicated as available for reuse to at least one of the internal nodes and leaf nodes representing an additional data set index for the additional data set.

12. The system of claim 10, wherein one page is allocated to each of the internal nodes and leaf nodes of the data set index.

13. The system of claim 10, wherein selecting the at least one page based on the durations during which the allocated pages have not been used comprises:

determining whether pages allocated to the leaf nodes have not been used for a leaf node duration; and

determining whether pages allocated to the internal nodes have not been used for an internal node duration, wherein the selected at least one page comprises at least one of the pages that have not been used for the leaf node duration or the internal node duration.

14. The system of claim 13, wherein the internal node duration is greater than the leaf node duration to retain the pages for the internal nodes in the memory longer than the pages for the leaf nodes.

15. The system of claim 13, wherein a page for a root node of the tree data structure is retained in memory until the data set is closed and wherein there is one level of the internal nodes between the root node and the leaf node.

16. The system of claim 13, wherein, the operations further comprise:

determining a utilization ratio based on a number of the allocated pages that have been accessed and are unavailable for reuse and a total number of pages allocated for use with data sets;

determining whether the determined utilization ratio exceeds a target utilization ratio;

decreasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio exceeds the target utilization ratio; and

increasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio is less than the target utilization ratio.

17. The system of claim 13, wherein the operation to select the at least one page to reuse is periodically performed, wherein there is a reuse selection interval between operations to select the at least one page, and wherein the reuse selection interval is greater than the leaf and the internal node durations.

18. A method, comprising:

allocating pages in a memory to internal nodes and leaf nodes of a tree data structure representing all or a portion of a data set index for a data set in storage, wherein the leaf nodes include information on members of the data set, wherein the internal nodes include one or more keys used to traverse the tree data structure to reach the leaf nodes that are used to access the members of the data set;

selecting at least one page allocated to the leaf nodes and the internal nodes based on durations during which the allocated pages have not been used, wherein pages allocated to the leaf nodes are selected for reuse at a higher rate than the pages allocated to the internal nodes; and

indicating the selected at least one page as available for reuse to store data for a data set member or as a node in the data set index.

19. The method of claim 18, further comprising:

opening an additional data set; and

allocating at least one page indicated as available for reuse to at least one of the internal nodes and leaf nodes representing an additional data set index for the additional data set.

20. The method of claim 18, wherein one page is allocated to each of the internal nodes and leaf nodes of the data set index.

21. The method of claim 18, wherein the selecting the at least one page based on the durations during which the allocated pages have not been used comprises:

determining whether pages allocated to the leaf nodes have not been used for a leaf node duration; and

determining whether pages allocated to the internal nodes have not been used for an internal node duration, wherein the selected at least one page comprises at least one of the pages that have not been used for the leaf node duration or the internal node duration.

22. The method of claim 21, wherein the internal node duration is greater than the leaf node duration to retain the pages for the internal nodes in the memory longer than the pages for the leaf nodes.

23. The method of claim 21, wherein a page for a root node of the tree data structure is retained in memory until the data set is closed and wherein there is one level of the internal nodes between the root node and the leaf node.

24. The method of claim 21, further comprising:

determining a utilization ratio based on a number of the allocated pages that have been accessed and are unavailable for reuse and a total number of pages allocated for use with data sets;

determining whether the determined utilization ratio exceeds a target utilization ratio;

decreasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio exceeds the target utilization ratio; and

increasing at least one of the leaf node duration and the internal node duration in response to determining that the determined utilization ratio is less than the target utilization ratio.

25. The method of claim 21, wherein the selecting the at least one page to reuse is periodically performed, wherein there is a reuse selection interval between operations to select the at least one page, and wherein the reuse selection interval is greater than the leaf and the internal node durations.