Granted Patent B2

US 12,346,290 · App. 17/864,190 · Granted Jul 1, 2025

Inventors: Steven Henry Haber (Seattle, WA); Noah Trent Nelson (Seattle, WA); Thomas Scott Urban (Seattle, WA)

Assignee: Qumulo, Inc.

G06F16/128G06F11/1451G06F16/162G06F2201/84

Abstract

Claims (128)

1. A method for managing data in a file system over a network using one or more processors that execute instructions that are configured to cause performance of actions, comprising:

providing the file system that includes one or more storage nodes and a plurality of snapshots, wherein each snapshot is associated with a plurality of data blocks; and

in response to deleting one or more snapshots of the plurality of snapshots, performing further actions, including:

determining a plurality of dead blocks associated with the one or more deleted snapshots, wherein each dead block is a data block that is unassociated with one or more undeleted snapshots;

adding the plurality of dead blocks to a plurality of dead trees located on a randomly determined selection of the one or more storage nodes;

determining an urgency score based on a workload model that includes one or more individual workload sub-models for each of one or more file system metrics and one or more other metrics, wherein an overall urgency score is determined based on a highest urgency score determined by an individual workload sub-model for a plurality of delete tasks, and wherein the one or more other metrics are based on configuration information for a current state of the file system and include one or more of a network utilization, a cloud computing cost structure, a hardware capability, an ongoing rebalancing operation, or a rate of transactions;

determining initiation of the plurality of delete tasks for the one or more storage nodes based on the overall urgency score;

determining a portion of the storage nodes sequentially based on a total number of delete tasks that are initiated for each storage node in the portion, wherein a sequential order of the portion of the storage nodes is determined by an amount of the total number of initiated delete tasks that correspond to each storage node in the portion and configuration information for one or more of local requirements or local circumstances; and

executing each corresponding amount of initiated delete tasks concurrently on the portion of storage nodes to perform further actions including:

determining one or more dead blocks on the portion of storage nodes that are associated with the one or more deleted snapshots; and

deleting the one or more determined dead blocks on the portion of storage nodes and the one or more dead blocks added to the one or more dead trees on the one or more randomly determined storage nodes, wherein a storage capacity associated with the one or more deleted snapshots is returned to the file system.

2. The method of claim 1 , wherein determining the one or more file system metrics, further comprises, determining one or more of a count of the plurality of snapshots or an amount of available storage capacity in the file system.

3. The method of claim 1 , wherein determining the one or more dead blocks on the portion of storage nodes, further comprises:

determining one or more dead trees on the one or more storage nodes, wherein each dead tree includes a plurality of dead blocks associated with a plurality of deleted snapshots; and

traversing the one or more determined dead trees to identify the one or more dead blocks associated with the one or more deleted snapshots.

4. The method of claim 1 , further comprising:

in response to a completion of the execution of each corresponding amount of initiated delete tasks, performing further actions, including:

determining a remainder portion of the one or more storage nodes, wherein the execution of the corresponding amounts of initiated delete tasks excluded the remainder portion of storage nodes; and

further executing other corresponding amounts of other initiated delete tasks on the remainder portion of storage nodes.

5. The method of claim 1 , wherein deleting the one or more determined dead blocks, further comprises:

determining a portion of the one or more determined dead blocks that correspond to a storage capacity of a storage node in the file system based on the portion of the one or more determined dead blocks; and

providing a delete message to the storage node, wherein the storage node deletes the portion of the one or more determined dead blocks.

6. The method of claim 1 , wherein deleting the one or more snapshots of the plurality of snapshots, further comprises:

adding the one or more deleted snapshots to a deleted snapshot queue; and

in response to deleting each dead block associated with the one or more deleted snapshots, removing the one or more deleted snapshots from the deleted snapshot queue.

7. The method of claim 1 , wherein adding the plurality of dead blocks to the plurality of dead trees, further comprises:

determining one or more portions of the plurality of dead blocks;

randomly determining a storage node in the file system;

determining a dead tree stored on the randomly determined storage node; and

adding the portion of dead blocks to the determined dead tree.

8. A system for managing data in a file system comprising:

a network computer, comprising:

a memory that stores at least instructions; and

one or more processors that execute instructions that are configured to cause performance of actions, including:

providing the file system that includes one or more storage nodes and a plurality of snapshots, wherein each snapshot is associated with a plurality of data blocks; and

in response to deleting one or more snapshots of the plurality of snapshots, performing further actions, including:

determining a plurality of dead blocks associated with the one or more deleted snapshots, wherein each dead block is a data block that is unassociated with one or more undeleted snapshots;

adding the plurality of dead blocks to a plurality of dead trees located on a randomly determined selection of the one or more storage nodes;

determining an urgency score based on a workload model that includes one or more individual workload sub-models for each of one or more file system metrics and one or more other metrics, wherein an overall urgency score is determined based on a highest urgency score determined by an individual workload sub-model for a plurality of delete tasks, and wherein the one or more other metrics are based on configuration information for a current state of the file system and include one or more of a network utilization, a cloud computing cost structure, a hardware capability, an ongoing rebalancing operation, or a rate of transactions;

determining initiation of the plurality of delete tasks for the one or more storage nodes based on the overall urgency score;

determining a portion of the storage nodes sequentially based on a total number of delete tasks that are initiated for each storage node in the portion, wherein a sequential order of the portion of the storage nodes is determined by an amount of the total number of initiated delete tasks that correspond to each storage node in the portion and configuration information for one or more of local requirements or local circumstances; and

executing each corresponding amount of initiated delete tasks concurrently on the portion of storage nodes to perform further actions including:

 determining one or more dead blocks on the portion of storage nodes that are associated with the one or more deleted snapshots;

 deleting the one or more determined dead blocks on the portion of storage nodes and the one or more dead blocks added to the one or more dead trees on the one or more randomly determined storage nodes, wherein a storage capacity associated with the one or more deleted snapshots is returned to the file system; and

a client computer, comprising:

a memory that stores at least instructions; and

one or more processors that execute instructions that are configured to cause performance of actions, including, providing one or more requests to delete the one or more snapshots.

9. The system of claim 8 , wherein determining the one or more file system metrics, further comprises, determining one or more of a count of the plurality of snapshots or an amount of available storage capacity in the file system.

10. The system of claim 8 , wherein determining the one or more dead blocks on the portion of storage nodes, further comprises:

determining one or more dead trees on the one or more storage nodes, wherein each dead tree includes a plurality of dead blocks associated with a plurality of deleted snapshots; and

traversing the one or more determined dead trees to identify the one or more dead blocks associated with the one or more deleted snapshots.

11. The system of claim 8 , wherein the one or more network computer processors execute instructions that perform actions, further comprising:

in response to a completion of the execution of each corresponding amount of initiated delete tasks, performing further actions, including:

determining a remainder portion of the one or more storage nodes, wherein the execution of the corresponding amounts of initiated delete tasks excluded the remainder portion of storage nodes; and

further executing other corresponding amounts of other initiated delete tasks on the remainder portion of storage nodes.

12. The system of claim 8 , wherein deleting the one or more determined dead blocks, further comprises:

determining a portion of the one or more determined dead blocks that correspond to a storage capacity of a storage node in the file system based on the portion of the one or more determined dead blocks; and

providing a delete message to the storage node, wherein the storage node deletes the portion of the one or more determined dead blocks.

13. The system of claim 8 , wherein deleting the one or more snapshots of the plurality of snapshots, further comprises:

adding the one or more deleted snapshots to a deleted snapshot queue; and

in response to deleting each dead block associated with the one or more deleted snapshots, removing the one or more deleted snapshots from the deleted snapshot queue.

14. The system of claim 8 , wherein adding the plurality of dead blocks to the plurality of dead trees, further comprises:

determining one or more portions of the plurality of dead blocks;

randomly determining a storage node in the file system;

determining a dead tree stored on the randomly determined storage node; and

adding the portion of dead blocks to the determined dead tree.

15. A processor readable non-transitory storage media that includes instructions for managing data in a file system over a network, wherein execution of the instructions, by one or more processors on one or more network computers, are configured to cause performance of actions, comprising:

providing the file system that includes one or more storage nodes and a plurality of snapshots, wherein each snapshot is associated with a plurality of data blocks; and

in response to deleting one or more snapshots of the plurality of snapshots, performing further actions, including:

determining a plurality of dead blocks associated with the one or more deleted snapshots, wherein each dead block is a data block that is unassociated with one or more undeleted snapshots;

adding the plurality of dead blocks to a plurality of dead trees located on a randomly determined selection of the one or more storage nodes;

determining an urgency score based on a workload model that includes one or more individual workload sub-models for each of one or more file system metrics and one or more other metrics, wherein an overall urgency score is determined based on a highest urgency score determined by an individual workload sub-model for a plurality of delete tasks, and wherein the one or more other metrics are based on configuration information for a current state of the file system and include one or more of a network utilization, a cloud computing cost structure, a hardware capability, an ongoing rebalancing operation, or a rate of transactions;

determining initiation of the plurality of delete tasks for the one or more storage nodes based on the overall urgency score;

determining a portion of the storage nodes sequentially based on a total number of delete tasks that are initiated for each storage node in the portion, wherein a sequential order of the portion of the storage nodes is determined by an amount of the total number of initiated delete tasks that correspond to each storage node in the portion and configuration information for one or more of local requirements or local circumstances; and

executing each corresponding amount of initiated delete tasks concurrently on the portion of storage nodes to perform further actions including:

determining one or more dead blocks on the portion of storage nodes that are associated with the one or more deleted snapshots; and

deleting the one or more determined dead blocks on the portion of storage nodes and the one or more dead blocks added to the one or more dead trees on the one or more randomly determined storage nodes, wherein a storage capacity associated with the one or more deleted snapshots is returned to the file system.

16. The media of claim 15 , wherein determining the one or more file system metrics, further comprises, determining one or more of a count of the plurality of snapshots or an amount of available storage capacity in the file system.

17. The media of claim 15 , wherein determining the one or more dead blocks on the portion of storage nodes, further comprises:

determining one or more dead trees on the one or more storage nodes, wherein each dead tree includes a plurality of dead blocks associated with a plurality of deleted snapshots; and

traversing the one or more determined dead trees to identify the one or more dead blocks associated with the one or more deleted snapshots.

18. The media of claim 15 , further comprising:

in response to a completion of the execution of each corresponding amount of initiated delete tasks, performing further actions, including:

determining a remainder portion of the one or more storage nodes, wherein the execution of the corresponding amounts of initiated delete tasks excluded the remainder portion of storage nodes; and

further executing other corresponding amounts of other initiated delete tasks on the remainder portion of storage nodes.

19. The media of claim 15 , wherein deleting the one or more determined dead blocks, further comprises:

determining a portion of the one or more determined dead blocks that correspond to a storage capacity of a storage node in the file system based on the portion of the one or more determined dead blocks; and

providing a delete message to the storage node, wherein the storage node deletes the portion of the one or more determined dead blocks.

20. The media of claim 15 , wherein deleting the one or more snapshots of the plurality of snapshots, further comprises:

adding the one or more deleted snapshots to a deleted snapshot queue; and

in response to deleting each dead block associated with the one or more deleted snapshots, removing the one or more deleted snapshots from the deleted snapshot queue.

21. The media of claim 15 , wherein adding the plurality of dead blocks to the plurality of dead trees, further comprises:

determining one or more portions of the plurality of dead blocks;

randomly determining a storage node in the file system;

determining a dead tree stored on the randomly determined storage node; and

adding the portion of dead blocks to the determined dead tree.

22. A network computer for managing data in a file system, comprising:

a memory that stores at least instructions; and

one or more processors that execute instructions that are configured to cause performance of actions, including:

providing the file system that includes one or more storage nodes and a plurality of snapshots, wherein each snapshot is associated with a plurality of data blocks; and

in response to deleting one or more snapshots of the plurality of snapshots, performing further actions, including:

determining a plurality of dead blocks associated with the one or more deleted snapshots, wherein each dead block is a data block that is unassociated with one or more undeleted snapshots;

adding the plurality of dead blocks to a plurality of dead trees located on a randomly determined selection of the one or more storage nodes;

determining an urgency score based on a workload model that includes one or more individual workload sub-models for each of one or more file system metrics and one or more other metrics, wherein an overall urgency score is determined based on a highest urgency score determined by an individual workload sub-model for a plurality of delete tasks, and wherein the one or more other metrics are based on configuration information for a current state of the file system and include one or more of a network utilization, a cloud computing cost structure, a hardware capability, an ongoing rebalancing operation, or a rate of transactions;

determining initiation of the plurality of delete tasks for the one or more storage nodes based on the overall urgency score;

determining a portion of the storage nodes sequentially based on a total number of delete tasks that are initiated for each storage node in the portion, wherein a sequential order of the portion of the storage nodes is determined by an amount of the total number of initiated delete tasks that correspond to each storage node in the portion and configuration information for one or more of local requirements or local circumstances; and

executing each corresponding amount of initiated delete tasks concurrently on the portion of storage nodes to perform further actions including:

determining one or more dead blocks on the portion of storage nodes that are associated with the one or more deleted snapshots; and

deleting the one or more determined dead blocks on the portion of storage nodes and the one or more dead blocks added to the one or more dead trees on the one or more randomly determined storage nodes, wherein a storage capacity associated with the one or more deleted snapshots is returned to the file system.

23. The network computer of claim 22 , wherein determining the one or more file system metrics, further comprises, determining one or more of a count of the plurality of snapshots or an amount of available storage capacity in the file system.

24. The network computer of claim 22 , wherein determining the one or more dead blocks on the portion of storage nodes, further comprises:

determining one or more dead trees on the one or more storage nodes, wherein each dead tree includes a plurality of dead blocks associated with a plurality of deleted snapshots; and

traversing the one or more determined dead trees to identify the one or more dead blocks associated with the one or more deleted snapshots.

25. The network computer of claim 22 , wherein the one or more processors execute instructions that perform actions, further comprising:

in response to a completion of the execution of each corresponding amount of initiated delete tasks, performing further actions, including:

determining a remainder portion of the one or more storage nodes, wherein the execution of the corresponding amounts of initiated delete tasks excluded the remainder portion of storage nodes; and

further executing other corresponding amounts of other initiated delete tasks on the remainder portion of storage nodes.

26. The network computer of claim 22 , wherein deleting the one or more determined dead blocks, further comprises:

determining a portion of the one or more determined dead blocks that correspond to a storage capacity of a storage node in the file system based on the portion of the one or more determined dead blocks; and

providing a delete message to the storage node, wherein the storage node deletes the portion of the one or more determined dead blocks.

27. The network computer of claim 22 , wherein deleting the one or more snapshots of the plurality of snapshots, further comprises:

adding the one or more deleted snapshots to a deleted snapshot queue; and

in response to deleting each dead block associated with the one or more deleted snapshots, removing the one or more deleted snapshots from the deleted snapshot queue.

28. The network computer of claim 22 , wherein adding the plurality of dead blocks to the plurality of dead trees, further comprises:

determining one or more portions of the plurality of dead blocks;

randomly determining a storage node in the file system;

determining a dead tree stored on the randomly determined storage node; and

adding the portion of dead blocks to the determined dead tree.

Assignments (2)

Continuity (1)

References Cited (400)

Cited By (5)

US 12,585,563 US 12,619,582 US 12,670,081 US 12,743,357 US 12,748,730