Asynchronous deletion of large directories

1. A method, comprising:

receiving a request to delete a directory from a storage;

unlinking a first leaf node of a tree data structure corresponding to the directory from a second leaf node of the tree data structure corresponding to a parent metadata object of the directory, wherein unlinking the first leaf node of the tree data structure corresponding to the directory from the second leaf node of the tree data structure corresponding to the parent metadata object of the directory comprises updating the first leaf node of the tree data structure corresponding to the directory and the second leaf node of the tree data structure corresponding to the parent metadata object of the directory to include corresponding update intents;

providing a success confirmation that the first leaf node of the tree data structure corresponding to the directory is unlinked from the second leaf node of the tree data structure corresponding to the parent metadata object; and

after providing the success confirmation:

marking for deletion one of more nodes of the tree data structure corresponding to one or more metadata objects of the directory; and

identifying and deleting the one or more nodes of the tree data structure corresponding to the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects and at least one of their descendant metadata objects.

2. The method of claim 1 , wherein unlinking the first leaf node of the tree data structure corresponding to the directory from the second leaf node of the tree data structure corresponding to the parent metadata object of the directory further comprises removing from a metadata object associated with the parent metadata object a reference to the directory.

3. The method of claim 1 , further comprising deleting the first leaf node of the tree data structure corresponding to the directory.

4. The method of claim 1 , further comprising removing an update intent from the second leaf node corresponding to the parent metadata object of the directory.

5. The method of claim 1 , wherein identifying the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects comprises scanning a leaf level of the tree data structure.

6. The method of claim 5 , further comprising marking for deletion the descendant metadata objects of the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects.

7. The method of claim 6 , wherein the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects are deleted after the descendant metadata objects of the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects are marked for deletion.

8. The method of claim 1 , wherein the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects of the directory are associated with a plurality of views.

9. The method of claim 8 , further comprising determining a latest view of the plurality of views that includes the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects of the directory.

10. The method of claim 9 , wherein the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects and any of their descendant metadata objects are deleted from the latest view of the plurality of views.

11. The method of claim 10 , wherein the one or more marked nodes of the tree data structure corresponding to the one or more metadata objects and any of their descendant metadata objects are deleted from a next latest view of the plurality of views.

12. The method of claim 1 , wherein the storage is comprised of a plurality of storage nodes.

13. The method of claim 12 , wherein the plurality of storage nodes are assigned a corresponding subset of a set of the one or more metadata objects.

14. The method of claim 13 , wherein the plurality of storage nodes perform the step of identifying and deleting the one or more marked nodes of the tree data structure corresponding to one or more metadata objects and any of their descendant metadata objects for their corresponding subset of the set of the one or more metadata objects.

15. The method of claim 1 , wherein identifying and deleting the one or more marked metadata nodes of the tree data structure corresponding to one or more objects and any of their descendant metadata objects includes determining whether a timeout condition has been satisfied.

16. The method of claim 15 , wherein in response to determining that the timeout condition has been satisfied:

pausing the identifying and deleting of the one or more marked nodes of the tree data structure corresponding to one or more metadata objects and any of their descendant metadata objects; and

resuming the identifying and deleting of the one or more marked nodes of the tree data structure corresponding to one or more metadata objects and any of their descendant metadata objects in a distributed manner.

17. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a request to delete a directory from a storage;

unlinking a first leaf node of a tree data structure corresponding to the directory from a second leaf node of the tree data structure corresponding to a parent metadata object of the directory, wherein unlinking the first leaf node of the tree data structure corresponding to the directory from the second leaf node of the tree data structure corresponding to the parent metadata object of the directory comprises updating the first leaf node of the tree data structure corresponding to the directory and the second leaf node of the tree data structure corresponding to parent metadata object of the directory to include corresponding update intents;

providing a success confirmation that the first leaf node of the tree data structure corresponding to the directory is unlinked from the second leaf node of the tree data structure corresponding to the parent metadata object; and

after providing the success confirmation:

marking for deletion one of more nodes of the tree data structure corresponding to one or more metadata objects of the directory; and

identifying and deleting the one or more nodes of the tree data structure corresponding to the one or more marked nodes of the tree data structure corresponding to one or more metadata objects and at least one of their descendant metadata objects.

18. The computer program product of claim 17 , wherein unlinking the first leaf node of the tree data structure corresponding to the directory from the second leaf node of the tree data structure corresponding to the parent metadata object of the directory comprises

removing from a metadata object associated with the parent metadata object a reference to the directory.

19. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:

receive a request to delete a directory from a storage;

unlink a first leaf node of a tree data structure corresponding to the directory from a second leaf node of the tree data structure corresponding to a parent metadata object of the directory, wherein to unlink the first leaf node of the tree data structure corresponding to the directory from the second leaf node of the tree data structure corresponding to the parent metadata object of the directory, the processor is configured to update the first leaf node of the tree data structure corresponding to the directory and the second leaf node of the tree data structure corresponding to parent metadata object of the directory to include corresponding update intents;

provide a success confirmation that the first leaf node of the tree data structure corresponding to the directory is unlinked from the second leaf node of the tree data structure corresponding to the parent metadata object; and

after providing the success confirmation:

mark for deletion one of more nodes of the tree data structure corresponding to one or more metadata objects of the directory; and

identify and deleting the one or more nodes of the tree data structure corresponding to the one or more marked nodes of the tree data structure corresponding to one or more metadata objects and at least one of their descendant metadata objects.