Resumable copy-on-write (COW) B+tree pages deletion

Patent metadata

Field	Value
Publication number	US-11860736-B2
Application number	US-202117644618-A
Country	US
Kind code	B2
Filing date	Dec 16, 2021
Priority date	Dec 16, 2021
Publication date	Jan 2, 2024
Grant date	Jan 2, 2024

Abstract

A method for resumeable snapshot deletion is provided. A method for deletion of nodes maintained in an ordered data structure for a first snapshot includes processing the nodes maintained in the ordered data structure according to a defined order, setting a node path cursor with a pointer to a node and an indication of the deletion of the node; storing the node path cursor in a persistent storage; and during processing of the nodes: detecting a failure; after the failure, checking the pointer of the node path cursor; and resuming processing of the nodes starting from the first node indicated by the pointer.

First claim

We claim:

1. A method for deletion of nodes maintained in an ordered data structure for a first snapshot, the method comprising:
processing the nodes maintained in the ordered data structure according to a defined order, wherein processing the nodes includes:
identifying a first node of a plurality of nodes maintained in the ordered data structure for the first snapshot;
determining the first node is exclusively owned by the first snapshot; and
deleting the first node based on the determination;

setting a node path cursor with a pointer to the first node and an indication of the deletion of the first node;
storing the node path cursor in a persistent storage; and
during processing of the nodes:
detecting a failure;
after the failure, checking the pointer of the node path cursor; and
resuming processing of the nodes starting from the first node indicated by the pointer.

2. The method of claim 1 , wherein processing the nodes according to the defined order comprises, for each of the nodes, processing all child nodes of the node before deleting the node.

3. The method of claim 1 , wherein processing the nodes further includes:
identifying a second node of the plurality of nodes maintained in the order data structure for the first snapshot;
determining the node is shared with a second snapshot; and
skipping the second node for deletion.

4. The method of claim 1 , wherein the node path cursor further comprises a physical block address (PBA) of the first node.

5. The method of claim 1 , wherein the node path cursor further comprises a physical block address (PBA) of a root node in the order data structure for the first snapshot and a pointer at each level of the ordered data structure to the first node.

6. The method of claim 1 , wherein storing the node path cursor in the persistent storage comprises:
storing the node path cursor in memory;
determining a threshold number of nodes have been deleted in memory;
deleting the number of nodes from the persistent storage as a transaction; and
storing the node path cursor in the persistent storage as a part of the transaction.

7. The method of claim 1 , wherein determining the first node is exclusively owned by the first snapshot comprises determining a logical block address (LBA) associated with the first node is not found in the ordered data structure for any other snapshot.

8. A system for deletion of nodes maintained in an ordered data structure for a first snapshot, comprising:
one or more processors; and
at least one memory, the one or more processors and the at least one memory configured to:
process the nodes maintained in the ordered data structure according to a defined order, wherein processing the nodes includes:
identify a first node of a plurality of nodes maintained in the ordered data structure for the first snapshot;
determine the first node is exclusively owned by the first snapshot; and
delete the first node based on the determination;
set a node path cursor with a pointer to the first node and an indication of the deletion of the first node;
store the node path cursor in a persistent storage; and
during processing of the nodes:
detect a failure;
after the failure, check the pointer of the node path cursor; and
resume processing of the nodes starting from the first node indicated by the pointer.

9. The system of claim 8 , wherein the one or more processors and the at least one memory are configured to process the nodes according to the defined order by, for each of the nodes, processing all child nodes of the node before deleting the node.

10. The system of claim 8 , wherein the one or more processors and the at least one memory are configured to process the nodes by:
identifying a second node of the plurality of nodes maintained in the order data structure for the first snapshot;
determining the node is shared with a second snapshot; and
skipping the second node for deletion.

11. The system of claim 8 , wherein the node path cursor further comprises a physical block address (PBA) of the first node.

12. The system of claim 8 , wherein the node path cursor further comprises a physical block address (PBA) of a root node in the order data structure for the first snapshot and a pointer at each level of the ordered data structure to the first node.

13. The system of claim 8 , wherein the one or more processors and the at least one memory are configured to store the node path cursor in the persistent storage by:
storing the node path cursor in memory;
determining a threshold number of nodes have been deleted in memory;
deleting the number of nodes from the persistent storage as a transaction; and
storing the node path cursor in the persistent storage as a part of the transaction.

14. The system of claim 8 , wherein the one or more processors and the at least one memory are configured to determine the first node is exclusively owned by the first snapshot by determining a logical block address (LBA) associated with the first node is not found in the ordered data structure for any other snapshot.

15. A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations for deletion of nodes maintained in an ordered data structure for a first snapshot, the operations comprising:
processing the nodes maintained in the ordered data structure according to a defined order, wherein processing the nodes includes:
identifying a first node of a plurality of nodes maintained in the ordered data structure for the first snapshot;
determining the first node is exclusively owned by the first snapshot; and
deleting the first node based on the determination;

setting a node path cursor with a pointer to the first node and an indication of the deletion of the first node;
storing the node path cursor in a persistent storage; and
during processing of the nodes:
detecting a failure;
after the failure, checking the pointer of the node path cursor; and
resuming processing of the nodes starting from the first node indicated by the pointer.

16. The non-transitory computer-readable medium of claim 15 , wherein processing the nodes according to the defined order comprises, for each of the nodes, processing all child nodes of the node before deleting the node.

17. The non-transitory computer-readable medium of claim 15 , wherein processing the nodes further includes:
identifying a second node of the plurality of nodes maintained in the order data structure for the first snapshot;
determining the node is shared with a second snapshot; and
skipping the second node for deletion.

18. The non-transitory computer-readable medium of claim 15 , wherein the node path cursor further comprises a physical block address (PBA) of the first node.

19. The non-transitory computer-readable medium of claim 15 , wherein the node path cursor further comprises a physical block address (PBA) of a root node in the order data structure for the first snapshot and a pointer at each level of the ordered data structure to the first node.

20. The non-transitory computer-readable medium of claim 15 , wherein storing the node path cursor in the persistent storage comprises:
storing the node path cursor in memory;
determining a threshold number of nodes have been deleted in memory;
deleting the number of nodes from the persistent storage as a transaction; and
storing the node path cursor in the persistent storage as a part of the

Assignees

• Vmware Inc

Inventors

• Xiang Enning
• Singh Pranay
• Gao Junlong
• Negi Hardik Singh
• Wang Wenguang

Classifications

• G06F11/1407 Primary

  Checkpointing the instruction stream · CPC title

• G06F11/1474

  in transactions (updating of structured data in databases G06F16/23) · CPC title

• G06F16/128

  Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16) · CPC title

• G06F16/2246

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

• G06F11/0751 Primary

  Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06) · CPC title