Management of recycling bin for thinly-provisioned logical volumes

• US 8,347,059 B2
• Filed: 08/15/2008
• Issued: 01/01/2013
• Est. Priority Date: 08/15/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Helman, Haim, Schwarz, Shemer, Sandler, Kariel Eliahu
• Primary Examiner(s): Rojas, Midys
• Application Number:
  US12/192,242
• Publication Number:
  US 20100042802A1
• Time in Patent Office: 1,600 Days
• Field of Search: 711/170, 711/173, 711/202, 711/203, 711/206, 711/E12.01
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for data storage includes representing logical volumes by respective sets of pointers to physical partitions in which data used by the logical volumes is stored. One or more of the logical volumes are defined as provisionally deleted. A subset of the provisionally-deleted logical volumes is selected such that each logical volume in the subset has one or more private physical partitions whose data is used exclusively by that logical volume. One or more of the private physical partitions of the logical volumes in the subset are released for reallocation to another logical volume.

Claims

1. A method for data storage, comprising:

representing logical volumes by respective sets of pointers to physical partitions in long-term storage devices in which data used by the logical volumes is stored;

defining one or more of the logical volumes as provisionally deleted;

selecting, based on a predetermined criterion, a provisionally-deleted logical volume for deletion, wherein;

the selected provisionally-deleted logical volume comprises one or more private physical partitions,

a private physical partition is a physical partition on a long-term storage device including data that is used exclusively by the provisionally-deleted logical volume, and

the predetermined criterion comprises an age of the selected provisionally-deleted logical volume, a number of private physical partitions associated with the selected provisionally-deleted logical volume, and a size of a private physical partition associated with the selected provisionally-deleted logical volume;

deleting the selected provisionally-deleted logical volume; and

releasing at least one of the one or more of the private physical partitions for reallocation to another logical volume subsequent to deleting the selected provisionally-deleted logical volume.

2. The method according to claim 1, wherein the selected provisionally-deleted logical volume comprises a copy of a given logical volume.

3. The method according to claim 1, wherein deleting the selected provisionally-deleted logical volume comprises permanently deleting the selected provisionally-deleted logical volume.

4. The method according to claim 3, wherein representing the logical volumes comprises defining a reference-count list indicating respective counts of the logical volumes that point to the physical partitions, and wherein permanently deleting the selected provisionally-deleted logical volume comprises updating the reference-count list.

5. The method according to claim 1, wherein representing the logical volumes comprises representing the logical volumes by a hierarchical tree structure comprising nodes, wherein each of the nodes comprises a respective set of local pointers, and wherein the logical volumes are represented by respective nodes such that the local pointers in the nodes located along a path via the tree structure that connects a given node to a root node of the tree structure point to the physical partitions in which the data used by the logical volume represented by the given node is stored.

6. The method according to claim 5, wherein the local pointers in each node point to the private physical partitions of that node, and wherein selecting comprises identifying the nodes having non-empty sets of the local pointers as representing logical volumes comprising the private partitions.

7. The method according to claim 5, wherein deleting the selected provisionally-deleted logical volume comprises permanently deleting the selected provisionally-deleted logical volume by deleting the nodes representing the selected provisionally-deleted logical volume from the tree structure.

8. The method according to claim 7, wherein the tree structure comprises a binary tree in which the logical volumes are represented by leaf nodes and in which nodes that connect the leaf nodes to the root node comprise artificial nodes, and wherein deleting a first leaf node, which represents a first logical volume and is located below an artificial node, comprises:

deleting from the tree structure a second leaf node that represents a second logical volume and is located below the artificial node;

converting the artificial node into a merged node representing the second logical volume; and

combining the local pointers of the second leaf node with the local pointers of the artificial node to produce the local pointers of the merged node.

9. The method according to claim 1, and comprising accepting a request to allocate the at least one of the one or more physical partition to the other logical volume and allocating the at least one of the one or more private physical partitions responsively to the request.

10. The method according to claim 9, wherein the request comprises an instruction to create the other logical volume.

11. The method according to claim 9, wherein the request comprises an instruction to resize the other logical volume.

12. The method according to claim 9, wherein the data used by the other logical volume is stored on a first storage device, and wherein the request comprises an instruction to allocate the at least one of the one or more physical partitions to the other logical volume on a second storage device upon detection of a failure in the first storage device.

13. Apparatus for data storage, comprising:

an interface, which is operative to communicate with at least one host computer so as to receive data for storage that is addressed to logical volumes assigned on a storage device having physical partitions; and

a processor, which is coupled to represent the logical volumes by respective sets of pointers to the physical partitions in long-term storage devices in which data used by the logical volumes is stored, is configured to;

define one or more of the logical volumes as provisionally deleted,

select, based on a predetermined criterion, a provisionally-deleted logical volume for deletion, wherein;

the selected provisionally-deleted logical volume comprises one or more private physical partitions,

a private physical partition is a physical partition in a long-term storage device including data that is used exclusively by the selected provisionally-deleted logical volume, and

the predetermined criterion comprises an age of the selected provisionally-deleted logical volume, a number of private physical partitions associated with the selected provisionally-deleted logical volume, and a size of a private physical partition associated with the selected provisionally-deleted logical volume, and

delete the selected provisionally-deleted logical volume, and

release at least one of the one or more of the private physical partitions for reallocation to another logical volume subsequent to deleting the selected provisionally-deleted logical volume.

14. The apparatus according to claim 13, wherein the selected provisionally-deleted logical volume comprises a copy of a given logical volume.

15. The apparatus according to claim 13, wherein the processor is configured to permanently delete the selected provisionally-deleted logical volume.

16. The apparatus according to claim 13, wherein the processor is configured to represent the logical volumes by a hierarchical tree structure comprising nodes, wherein each of the nodes comprises a respective set of local pointers, and wherein the logical volumes are represented by respective nodes such that the local pointers in the nodes located along a path via the tree structure that connects a given node to a root node of the tree structure point to the physical partitions in which the data used by the logical volume represented by the given node is stored.

17. The apparatus according to claim 16, wherein the local pointers in each node point to the private physical partitions of that node, and wherein the processor is configured to identify the nodes having non-empty sets of the local pointers as representing logical volumes comprising the private partitions.

18. The apparatus according to claim 16, wherein the processor is configured to permanently delete the selected provisionally-deleted logical volume by deleting the nodes representing the selected provisionally-deleted logical volume from the tree structure.

19. The apparatus according to claim 18, wherein the tree structure comprises a binary tree in which the logical volumes are represented by leaf nodes and in which nodes that connect the leaf nodes to the root node comprise artificial nodes, and wherein the processor is coupled to delete a first leaf node, which represents a first logical volume and is located below an artificial node, by:

deleting from the tree structure a second leaf node that represents a second logical volume and is located below the artificial node;

converting the artificial node into a merged node representing the second logical volume; and

combining the local pointers of the second leaf node with the local pointers of the artificial node to produce the local pointers of the merged node.

20. A system for data storage, comprising:

a long-term storage device comprising physical partitions; and

a storage controller, which is coupled to communicate with at least one host computer so as to receive data for storage that is addressed to logical volumes assigned on the storage device, configured to;

represent the logical volumes by respective sets of pointers to the physical partitions in which data used by the logical volumes is stored,

define one or more of the logical volumes as provisionally deleted,

select, based on a predetermined criterion, a provisionally-deleted logical volume for deletion, wherein;

the selected provisionally-deleted logical volume comprises one or more private physical partitions,

a private physical partition is a physical partition in the long-term storage device including data that is used exclusively by the selected provisionally-deleted logical volume, and

the predetermined criterion comprises at least one-elan age of the selected provisionally-deleted logical volume, a number of private physical partitions associated with the selected provisionally-deleted logical volume, and a size of a private physical partition associated with the selected provisionally-deleted logical volume,

delete the selected provisionally-deleted logical volume, and

release at least one of the one or more of the private physical partitions for reallocation to another logical volume subsequent to deleting the selected provisionally-deleted logical volume.

21. The system according to claim 20, wherein deleting the selected provisionally-deleted logical volume comprises permanently deleting the selected provisionally-deleted logical volume.

22. The system according to claim 21, wherein representing the logical volumes comprises defining a reference-count list indicating respective counts of the logical volumes that point to the physical partitions, and wherein permanently deleting the selected provisionally-deleted logical volume comprises updating the reference-count list.

23. A computer software product for data storage, the product comprising non-transitory computer-readable storage medium, in which program instructions are stored, which instructions, when read by the computer, cause the computer to communicate with at least one host computer so as to receive data for storage that is addressed to logical volumes assigned on a long-term storage device having physical partitions, to:

represent the logical volumes by respective sets of pointers to the physical partitions in which data used by the logical volumes is stored,

define one or more of the logical volumes as provisionally deleted,

select, based on a predetermined criterion, a provisionally-deleted logical volume for deletion, wherein;

the selected provisionally-deleted logical volume comprises one or more private physical partitions,

a private physical partition is a physical partition in the long-term storage device including data that is used exclusively by the selected provisionally-deleted logical volume, and

the predetermined criterion comprises age of the selected provisionally-deleted logical volume, a number of private physical partitions associated with the selected provisionally-deleted logical volume, and a size of a private physical partition associated with the selected provisionally-deleted logical volume,

delete the selected provisionally-deleted logical volume, and release at least one of the one or more of the private physical partitions for reallocation to another logical volume subsequent to deleting the selected provisionally-deleted logical volume.

24. The computer software product according to claim 23, wherein deleting the selected provisionally-deleted logical volume comprises permanently deleting the selected provisionally-deleted logical volume.

25. The computer software product according to claim 24, wherein representing the logical volumes comprises defining a reference-count list indicating respective counts of the logical volumes that point to the physical partitions, and wherein permanently deleting the selected provisionally-deleted logical volume comprises updating the reference-count list.