Recovering data lost in data de-duplication system

• US 9,367,397 B1
• Filed: 12/20/2011
• Issued: 06/14/2016
• Est. Priority Date: 12/20/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Anderson, Curtis Christian, Xie, Ying, Garg, Nitin, Moghe, Dheer
• Primary Examiner(s): Mamillapalli, Pavan
• Application Number:
  US13/332,132
• Time in Patent Office: 1,638 Days
• Field of Search: 707/814, 707/820
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/1724 Details of de-fragmentation performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/24565 Triggers; Constraints
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

An indication is received that a data object is to be deleted, wherein the data object comprises data stored in a segment within a container. It is determined no currently alive data object references any segment within the container. The container is placed in a delete-ready but not yet reclaimable state.

Claims

1. A method, comprising:

receiving an indication that a data object is to be deleted, wherein the data object comprises data stored in a segment within a container;

determining no currently alive data object references any segment within the container, wherein an alive data object refers to a data object being actively used or stored by one or more of the following;

a user, a system, and an administrator;

placing the container in a delete-ready state, wherein a delete-ready state is a state indicating the container is ready for deletion but not yet reclaimable;

recording metadata reflecting a temporal order in which the container was placed in the delete-ready state relative to one or more other containers being placed in the delete-ready state;

retaining in a segment index, at least for as long as the container remains in the delete-ready state, a segment index data associated with the container;

receiving an indication that a trigger event to reclaim storage space has occurred; and

changing the container from the delete-ready state to a deleted state in which storage space associated with the container is subject to being reclaimed based at least in part on the indication that the trigger event has occurred and said metadata reflecting the temporal order in which the container was place in the delete-ready state.

2. The method of claim 1, where each segment is immutable and unique.

3. The method of claim 1, where each container is stored in a deduplicating filesystem.

4. The method of claim 1, wherein said metadata comprises a token associated with the container when placing the container in the delete-ready state.

5. The method of claim 4, further comprising determining an earliest deleted container amongst a plurality of containers in the delete-ready state in part by determining which container has a smallest token.

6. The method of claim 5, further comprising receiving a second indication that at least one container must be deleted, and determining to delete the earliest deleted container to maintain a FIFO order.

7. The method of claim 5, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon:

(1) the token with each container in the delete-ready state; and

(2) a position of each container in the delete-ready state.

8. The method of claim 5, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon:

(1) a FIFO order based on the token associated with each container in the delete-ready state; and

(2) a position of each container in the delete-ready state in relation to contiguous areas in a filesystem.

9. The method of claim 1, further comprising associating a delete time with the container when placing the container in the delete-ready state.

10. The method of claim 9, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon the delete time associated with each container in the delete-ready state.

11. The method of claim 9, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon a FIFO ordering based on the delete time associated with each container in the delete-ready state.

12. The method of claim 9, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon:

(1) the delete time associated with each container in the delete-ready state; and

(2) a position of each container in the delete-ready state.

13. The method of claim 9, further comprising receiving a second indication that at least one container must be deleted, and determining to delete a specific container based at least upon:

(1) a FIFO ordering based on the delete time associated with each container in the delete-ready state; and

(2) a position of each container in the delete-ready state in relation to contiguous areas in a filesystem.

14. The method of claim 1, further comprising receiving a second indication that a reclamation criteria is met and taking the container out of the delete-ready state.

15. A system, comprising:

a garbage collector coupled to a container manager and configured to;

determine no currently alive data object references any segment within the container, wherein an alive data object refers to a data object being actively used or stored by one or more of the following;

a user, a system, and an administrator;

the container manager configured to;

receive an indication that a data object is to be deleted, wherein the data object comprises data stored in a segment within the container;

place the container in a delete-ready state after the determination, wherein a delete-ready state is a state indicating the container is ready for deletion but not yet reclaimable;

record metadata reflecting a temporal order in which the container was placed in the delete-ready state relative to one or more other containers being placed in the delete-ready state;

retain in a segment index, at least for as long as the container remains in the delete-ready state, a segment index data associated with the container;

receive an indication that a trigger event to reclaim storage space has occurred; and

change the container from the delete-ready state to a deleted state in which storage space associated with the container is subject to being reclaimed based at least in part on the indication that the trigger event has occurred and said metadata reflecting the temporal order in which the container was place in the delete-ready state;

a processor configured to execute instructions for the garbage collector and the container manager; and

a memory coupled to the processor and configured to provide the processor with said instructions.

16. The system recited in claim 15, wherein said metadata comprises a token associated with the container when placing the container in the delete-ready state.

17. The system recited in claim 15, wherein said metadata comprises a delete time associated with the container when placing the container in the delete-ready state.

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

receiving an indication that a data object is to be deleted, wherein the data object comprises data stored in a segment within a container;

determining no currently alive data object references any segment within the container, wherein an alive data object refers to a data object being actively used or stored by one or more of the following;

a user, a system, and an administrator;

placing the container in a delete-ready state, wherein a delete-ready state is a state indicating the container is ready for deletion but not yet reclaimable;

recording metadata reflecting a temporal order in which the container was placed in the delete-ready state relative to one or more other containers being placed in the delete-ready state;

retaining in a segment index, at least for as long as the container remains in the delete-ready state, a segment index data associated with the container;

receiving an indication that a trigger event to reclaim storage space has occurred; and

changing the container from the delete-ready state to a deleted state in which storage space associated with the container is subject to being reclaimed based at least in part on the indication that the trigger event has occurred and said metadata reflecting the temporal order in which the container was place in the delete-ready state.

19. The computer program product recited in claim 18, further comprising computer instructions for:

associating a token with the container when placing the container in the delete-ready state.

20. The computer program product recited in claim 18, further comprising computer instructions for:

associating a delete time with the container when placing the container in the delete-ready state.