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

Patent metadata

Field	Value
Publication number	US-10114559-B2
Application number	US-201615236388-A
Country	US
Kind code	B2
Filing date	Aug 12, 2016
Priority date	Aug 12, 2016
Publication date	Oct 30, 2018
Grant date	Oct 30, 2018

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:
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 identify data set members and the internal nodes are used to traverse the tree data structure to access the leaf nodes;
processing a transaction 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;
generating, in transaction information, node access information for accessed nodes comprising nodes in the tree data structure accessed as part of processing the transaction, wherein 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;
for at least one modified node of the accessed nodes too be modified during the transaction, deallocating a page allocated to the modified node before the transaction to be available for reuse as an unallocated page and allocating a new page to the modified node including modified data for the modified node generated during the transaction; and
updating the pointer in the node access information for the at least one modified node to indicate the deallocated page.

2. The computer program product of claim 1 , wherein the transaction comprises a write operation, wherein at least one modified node comprises a leaf node allocated a new page for the leaf node indicating a data set member having write data from the write operation.

3. The computer program product of claim 1 , wherein the node access information for a plurality of modified nodes points to deallocated pages, wherein the operations further comprise:
initiating an operation to roll back the transaction; and
for each of the at least one modified node, deallocating the new page allocated to the modified node and allocating to the modified node the deallocated page indicated by the pointer in the node access information to return the modified node to a state prior to the transaction subject to the roll back.

4. The computer program product of claim 1 , wherein the operations further comprise:
indicating in the node access information for the modified node that the deallocated page indicated by the pointer in the node access information is invalid in response to the deallocated page being invalidated in the memory.

5. The computer program product of claim 4 , wherein the operations further comprises:
maintaining data set transaction information indicating transaction information for different transactions and data sets subject to the transactions;
receiving notification indicating a page allocated to a subject data set being invalidated or freed; and
determining a node access information instance in the transaction information for the subject data set having a pointer to the page indicated in the notification, wherein the indicating in the node access information that the deallocated page indicated by the pointer is invalid is performed for determined node access information.

6. The computer program product of claim 4 , wherein pointers in node access information instances in the transaction information for a plurality of modified nodes point to deallocated pages comprising unallocated pages in the memory, wherein the operations further comprise:
determining whether all of the deallocated pages addressed by the pointers in the node access information in the transaction information are freed or invalidated; and
indicating the transaction information and the node access information for the transaction information as invalid in response to determining that the deallocated pages addressed by the pointers are freed or are invalidated.

7. The computer program product of claim 1 , wherein the transaction comprises a read operation, operations further comprise:
indicating the transaction information and the node access information as invalid in response to completing the read operation.

8. The computer program product of claim 1 , wherein the node access information for each of the nodes accessed during the transaction indicates a sequence number indicating an order in which the node was accessed during the transaction, a timestamp for the access of the node, and a type of the access of the page of the node during the transaction.

9. The computer program product of claim 1 , wherein the operations further comprise:
using the transaction information including the node access information to diagnose the transaction in response to the transaction failing.

10. The computer program product of claim 1 , wherein the node access information for an accessed node is generated when the accessed node is accessed as part of processing the transaction, wherein the transaction information logs node access information for all node processing from when the transaction is opened until the transaction is closed.

11. The computer program product of claim 1 , wherein the operations further comprise:
initiating an operation to commit a page allocated to a node accessed by a completed transaction;
determining whether one instance of transaction information for one pending transaction includes node access information for the node allocated to the page to commit; and
committing the page to commit after determining that no transaction information for a transaction includes node access information for the node allocated the page to commit.

12. 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:
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 identify data set members and the internal nodes are used to traverse the tree data structure to access the leaf nodes;
processing a transaction 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;
generating, in transaction information, node access information for accessed nodes comprising nodes in the tree data structure accessed as part of processing the transaction, wherein 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;
for at least one modified node of the accessed nodes too be modified during the transaction, deallocating a page allocated to the modified node before the transaction to be available for reuse as an unallocated page and allocating a new page to the modified node including modified data for the modified node generated during the transaction; and
updating the pointer in the node access information for the at least one modified node to indicate the deallocated page.

13. The system of claim 12 , wherein the node access information for a plurality of modified nodes points to deallocated pages, wherein the operations further comprise:
initiating an operation to roll back the transaction; and
for each of

Assignees

• IBM

Inventors

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

Classifications

• G06F9/466

  Transaction processing · CPC title

• G06F3/0613 Primary

  in relation to throughput · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F3/061

  Improving I/O performance · CPC title

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title