Generating node access information for a transaction accessing nodes of a data set index

Patent metadata

Field	Value
Publication number	US-11294573-B2
Application number	US-201916430289-A
Country	US
Kind code	B2
Filing date	Jun 3, 2019
Priority date	Aug 12, 2016
Publication date	Apr 5, 2022
Grant date	Apr 5, 2022

Abstract

Provided are a computer program product, system, and method for generating node access information for a transaction accessing nodes of a data set index. 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. A transaction is processed with respect to the data set that involves accessing the internal and leaf nodes in the tree data structure, wherein the transaction comprises a read or write operation. Node access information is generated in transaction information, for accessed nodes comprising nodes in the tree data structure accessed as part of processing the transaction. The node access information includes a pointer to the page allocated to the accessed node prior to the transaction in response to the node being modified during the transaction.

First claim

What is claimed is:

1. A computer program product for maintaining information on pages in a memory used for data in a data set stored in a storage, the computer program product comprising a computer readable storage medium having computer readable program code embodied therein that executes to perform operations, the operations comprising:
processing a write transaction with respect to a data set member of the data set, comprising at least one track in the storage, that involves accessing internal nodes and leaf nodes in a tree data structure representing the data set, wherein the leaf nodes identify data set members and the internal nodes are used to traverse the tree data structure to access the leaf nodes;
generating node access information for nodes accessed during the write transaction in the tree data structure indicating whether the accessed nodes were modified, wherein the node access information includes information on modifications to internal nodes and leaf nodes; and
including the node access information for the accessed nodes in transaction information for the write transaction, wherein the transaction information for the write transaction has node access information indicating modifications to internal nodes and leaf nodes that were accessed during the write transaction and changed as a result of the write transaction.

2. The computer program product of claim 1 , wherein the operations further comprise:
including the transaction information of the node access information for the accessed nodes in a data set transaction list including transaction information for multiple write transactions to the data set.

3. The computer program product of claim 1 , wherein the transaction information indicates a lifespan threshold, wherein the operations further comprise:
deleting the transaction information and included node access information in response to a lifespan of the transaction information exceeding the lifespan threshold.

4. The computer program product of claim 1 , wherein the operations further comprise:
modifying an accessed node as part of the write transaction; and
allocating a new page for the modified accessed node for write data from the write transaction.

5. The computer program product of claim 4 , wherein the operations further comprise:
deallocating a page allocated to the modified accessed node before the write transaction to be available for reuse as an unallocated page;
adding the deallocated page to an invalidate list from which pages are invalidated and freed; and
updating a pointer in the node access information for the deallocated page to indicate the deallocated page and indicate that the deallocated page is valid.

6. The computer program product of claim 5 , wherein the operations further comprise:
indicating the deallocated page addressed by the pointer in the node access information for a node as invalid in response to freeing the page when processing the invalidate list.

7. The computer program product of claim 5 , wherein the operations further comprise:
initiating an operation to roll back the write transaction; and
for node access information for a modified node indicating that the deallocated page is valid, deallocating a current page for the modified node and allocate the page indicated by the pointer in the node access information to the modified node.

8. A system in communication with a storage, comprising:
a processor;
a memory having pages used for data in a data set stored in the storage;
computer readable program code in the memory executed by the processor to perform operations, the operations comprising:
processing a write transaction with respect to a data set member of the data set, comprising at least one track in the storage, that involves accessing internal nodes and leaf nodes in a tree data structure representing the data set, wherein the leaf nodes identify data set members and the internal nodes are used to traverse the tree data structure to access the leaf nodes;
generating node access information for nodes accessed during the write transaction in the tree data structure indicating whether the accessed nodes were modified, wherein the node access information includes information on modifications to internal nodes and leaf nodes; and
including the node access information for the accessed nodes in transaction information for the write transaction, wherein the transaction information for the write transaction has node access information indicating modifications to internal nodes and leaf nodes that were accessed during the write transaction and changed as a result of the write transaction.

9. The system of claim 8 , wherein the operations further comprise:
including the transaction information of the node access information for the accessed nodes in a data set transaction list including transaction information for multiple write transactions to the data set.

10. The system of claim 9 , wherein the transaction information indicates a lifespan threshold, wherein the operation further comprises:
deleting the transaction information and included node access information in response to a lifespan of the transaction information exceeding the lifespan threshold.

11. The system of claim 9 , wherein the operations further comprise:
modifying an accessed node as part of the write transaction; and
allocating a new page for the modified accessed node for write data from the write transaction.

12. The system of claim 11 , wherein the operations further comprise:
deallocating a page allocated to the modified accessed node before the write transaction to be available for reuse as an unallocated page;
adding the deallocated page to an invalidate list from which pages are invalidated and freed; and
updating a pointer in the node access information for the deallocated page to indicate the deallocated page and indicate that the deallocated page is valid.

13. The system of claim 12 , wherein the operations further comprise:
indicating the deallocated page addressed by the pointer in the node access information for a node as invalid in response to freeing the page when processing the invalidate list.

14. The system of claim 12 , wherein the operations further comprise:
initiating an operation to roll back the write transaction; and
for node access information for a modified node indicating that the deallocated page is valid, deallocating a current page for the modified node and allocate the page indicated by the pointer in the node access information to the modified node.

15. A method for maintaining information on pages in a memory used for data in a data set stored in a storage, comprising:
processing a write transaction with respect to a data set member of the data set, comprising at least one track in the storage, that involves accessing internal nodes and leaf nodes in a tree data structure representing the data set, wherein the leaf nodes identify data set members and the internal nodes are used to traverse the tree data structure to access the leaf nodes;
generating node access information for nodes accessed during the write transaction in the tree data structure indicating whether the accessed nodes were modified, wherein the node access information includes information on modifications to internal nodes and leaf nodes; and
including the node access information for the accessed nodes in transaction information for the write transaction, wherein the transaction information for the write transaction has node access information indicating modifications to internal nodes and leaf nodes that were accessed during the write transaction an

Assignees

• IBM

Inventors

• Erdmann Derek L
• Reed David C
• Reed Thomas C
• Smith Max D

Classifications

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F3/0613 Primary

  in relation to throughput · CPC title

• G06F9/466

  Transaction processing · CPC title