Management of recycling bin for thinly-provisioned logical volumes

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.

FIELD OF THE INVENTION

The present invention relates generally to data storage, and particularly to methods and systems for managing logical volumes in data storage systems.

BACKGROUND

Data storage systems typically store data on physical media in a manner that is transparent to host computers. From the perspective of a host computer, data is stored on virtual storage devices that are commonly known as logical volumes. Logical volumes are typically configured to store the data required for a specific data processing application. Data storage systems map logical volumes to addressable physical locations on storage media, such as direct-access hard disks.

System administrators frequently make copies of logical volumes, for example in order to perform backups or to test and validate new applications. Such copies are commonly referred to as snapshots.

BRIEF SUMMARY

An embodiment of the present invention provides a method for data storage. The method 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. Apparatus, system and computer software product for data storage are also provided.

In some embodiments, at least one of the logical volumes in the subset includes a copy of a given logical volume. In an embodiment, releasing the private physical partitions includes permanently deleting the logical volumes in the subset. In another embodiment, representing the logical volumes includes defining a reference-count list indicating respective counts of the logical volumes that point to the physical partitions, and permanently deleting the logical volumes in the subset includes updating the reference-count list.

In yet another embodiment, selecting the subset includes selecting the provisionally-deleted logical volumes having oldest provisional deletion times. Alternatively, selecting the subset may include selecting the provisionally-deleted logical volumes having highest numbers of the private physical partitions.

In some embodiments, representing the logical volumes includes representing the logical volumes by a hierarchical tree structure including nodes, wherein each of the nodes includes 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. In a disclosed embodiment, the local pointers in each node point to the private physical partitions of that node, and selecting the subset includes identifying the nodes having non-empty sets of the local pointers as representing the logical volumes having the private partitions.

In another embodiment, releasing the private physical partitions includes permanently deleting the logical volumes in the subset by deleting the nodes representing the logical volumes in the subset from the tree structure.

In yet another embodiment, the tree structure includes 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 include artificial nodes, and deleting a first leaf node, which represents a first logical volume and is located below an artificial node, includes:

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.

In some embodiments, the method includes accepting a request to allocate at least one physical partition to the other logical volume, and selecting the subset and releasing the private physical partitions responsively to the request. The request may include an instruction to create the other logical volume. Alternatively, the request may include an instruction to resize the other logical volume. In an embodiment, the data used by the other logical volume is stored on a first storage device, and the request includes an instruction to allocate the at least one physical partition to the other logical volume on a second storage device upon a failure in the first storage device.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

DETAILED DESCRIPTION

Overview

Embodiments of the present invention that are described hereinbelow provide methods and systems for managing a “recycling bin” for logical volumes. In some embodiments, a storage controller stores data in logical volumes. Each logical volume is represented by a respective list of pointers to physical partitions in a storage device, which hold the data used by the volume. When a user (e.g., an administrator) deletes a given logical volume, the storage controller defines the volume as provisionally-deleted, and retains the physical partitions of the deleted volume and the corresponding pointers. The deleted volume is moved from a list of valid volumes to a list of provisionally-deleted volumes (a “recycling bin”). As long as the physical partitions of the provisionally-deleted volume are retained, the user may reclaim the volume, i.e., request the storage controller to return the volume to the list of valid volumes.

In some embodiments, the storage controller represents the logical volumes using a thinly-provisioned configuration, in which a given physical partition may be used (pointed to) by multiple logical volumes. The scenario of having multiple logical volumes that use the same physical partition is common, for example, when the volumes comprise copies (“snapshots”) of a certain logical volume taken at successive time intervals. Thinly-provisioned configurations are highly efficient in using storage space, since data that is used by multiple logical volumes need not be duplicated in separate physical partitions.

When storage space is limited, the storage controller typically selects one or more of the provisionally-deleted volumes, and deletes them permanently in order to free physical partitions. When using thinly-provisioned volumes, however, the task of permanently deleting volumes is complicated, because some of the physical partitions that are used by a deleted volume may also be used by other volumes. Thus, unconditionally releasing the physical partitions of a provisionally-deleted volume may damage other volumes.

The methods and systems described herein solve the above-mentioned difficulties by selecting as candidates for permanent deletion provisionally-deleted logical volumes having private physical partitions. A private physical partition of a logical volume is defined as a physical partition whose data is used exclusively by that logical volume, and not by any other logical volume. As such, a private physical partition can be safely released for reallocation without risk of affecting volumes other than the single volume that uses this physical partition.

In some embodiments, the storage controller accepts a request to allocate one or more physical partitions to a given logical volume. In response to the request, the storage controller selects a subset of the provisionally-deleted logical volumes, such that each logical volume in the subset has at least one private physical partition. The storage controller may select the subset of provisionally-deleted volumes using various criteria. Several example criteria are described herein.

The storage controller permanently deletes the selected logical volumes in the subset, and releases one or more of the private physical partitions of these volumes. The released physical partitions are then reallocated to the given logical volume. Using this technique, only physical partitions that are used exclusively by the permanently-deleted volumes are released, and other volumes are not affected.

In some embodiments, the methods and systems described herein are applied to logical volumes that are copies of other logical volumes. Such copies are also known as snapshots. These snapshots are represented using a thinly-provisioned representation, and are stored and managed by the storage controller in the manner described above.

In some embodiments, the storage controller represents the logical volumes using a hierarchical data structure. Techniques for identifying private physical partitions and for deleting logical volumes using the hierarchical data structure are described herein.

System Description

FIG. 1is a block diagram that schematically illustrates a data storage system20, in accordance with an embodiment of the present invention. System20comprises a storage controller24, which stores and retrieves data for hosts28. The hosts are also referred to as initiators.

In the configuration ofFIG. 1, the hosts are connected to the storage controller via a Storage Area Network (SAN)32, as is known in the art. The SAN typically comprises one or more network switches36. The hosts and storage controller may communicate over SAN32using any suitable protocol, such as the Small Computer System Interface (SCSI) and/or Fibre-Channel (FC) protocols. Although the embodiment ofFIG. 1refers to a SAN configuration, the hosts and storage controller may be connected using any other suitable configuration, such as a Network-Attached Storage (NAS) or Direct-Attached Storage (DAS) configuration.

Storage controller24comprises multiple storage processing modules40, which store data in multiple storage devices, such as disks44. Storage controller24may comprise any desired number of modules40and any desired number of disks44. In a typical configuration, the storage controller may comprise between 1-32 storage processing modules and between 2-2000 disks, although any other suitable numbers can also be used. In the exemplary configuration ofFIG. 1, each module40stores data in a separate set of disks44. In alternative embodiments, however, a given disk44need not be uniquely associated with a particular module40. For example, a pool of disks44may be common to all modules40.

Each storage processing module40comprises a network interface48for communicating with hosts28over SAN32, and a processor52, which carries out the various storage and retrieval tasks of the module. In particular, processor52manipulates a “recycling bin” that allows logical volumes and copies of logical volumes to be provisionally-deleted and later reclaimed, using methods that are described in detail below.

Logical Volumes and Snapshots

Storage controller24stores data on disks44by allocating logical volumes to hosts28, or to specific applications running on the hosts. Each logical volume is typically identified by a unique Logical Unit Number (LUN). From the perspective of the host, an application issues Input/Output commands (e.g., read and write commands) to a logical volume, without knowledge of the physical storage locations in disks44in which the data is actually stored.

In some embodiments, processor52represents each volume by a list of pointers to physical partitions on disks44, which store the data used by the volume. Such a representation is referred to as a “thinly-provisioned” representation. When using thinly-provisioned volumes, a given physical partition may be pointed to by multiple volumes, if these volumes use the same data. In many cases, large amounts of data are common to multiple logical volumes. In these cases, the thinly-provisioned representation is highly efficient in using disk memory space.

(A physical partition is sometimes referred to herein as a page. The terms “physical storage location,” “physical page,” “physical partition,” “storage location,” “page” and “partition” are used interchangeably herein and refer to any form of physical storage location defined in disks44.)

In various scenarios, a user (e.g., a system administrator) creates copies of logical volumes. Copies of logical volumes are often referred to as snapshots, and the two terms are used interchangeably herein. Copies may be used, for example, for backing-up the logical volume or for performing certain low-priority processing tasks, such as collection of statistics.

Once created, a snapshot may be accessed and modified by hosts similarly to a logical volume. In some embodiments, each snapshot is assigned a corresponding LUN and the hosts are aware of these LUNs. Typically, processor52holds a mapping table that maps LUNs of logical volumes and snapshots to physical partitions on disks44. Similarly to logical volumes, processor52of storage controller24represents snapshots using a thinly-provisioned representation. When using thinly-provisioned snapshots, creation of a new snapshot does not involve physical writing of data on disks44. Data is written physically only when it is modified.

In some embodiments, processor52further maintains a reference-count list, which indicates the number of thinly-provisioned logical volumes and snapshots that use (point to) each physical partition. For example, consider a logical volume denoted V1, for which an administrator has created two snapshots denoted S1and S2. At a certain point in time, volume V1uses physical partitions {0,1,2,3,4,5}, snapshot S1uses physical partitions {0,1,2,3,104,5} and snapshot S2uses physical partitions {0,1,2,3,104,105}. The following reference-count list corresponds to this scenario:

Number of logicalvolumes and snapshotsPhysical partitionusing the partition03132333415210421051

Provisional and Permanent Deletion of Logical Volumes and Snapshots

As part of operating storage controller24, users (e.g., administrators or users of hosts28) may create, delete, resize or otherwise manipulate logical volumes and snapshots. In some embodiments, storage controller24supports a mechanism that allows logical volumes and snapshots to be defined as “provisionally deleted.” (The description that follows refers to logical volumes for the sake of clarity, but the methods and systems described herein are equally applicable to snapshots.)

When a user deletes a certain logical volume, processor52does not release the physical partitions used by this volume and does not modify the reference-count list, but rather defines the volume as provisionally deleted. Space-permitting, processor52retains the physical partitions used by the provisionally-deleted volume, as well as the pointers to these physical partitions, and does not allocate the physical partitions to other volumes. In some embodiments, the provisionally-deleted volume is moved from a list of valid volumes into a list (“recycling bin”) of provisionally-deleted volumes. The user may reclaim the provisionally-deleted volume from the recycling bin and request that processor52return the volume to the list of valid volumes, such as when the volume was deleted accidentally. Thus, a volume that is deleted by a user is marked as invisible to the user, but is retained and may be recovered later if desired.

In some embodiments, each volume is assigned an internal name, which is recognized internally to the storage controller, and an external name (e.g., LUN) that is visible to the hosts. Processor52may maintain a mapping table that maps the internal names to the external names. When using such a table, the external name of a provisionally-deleted volume can be freed and assigned to a new volume, while the internal name of the volume remains associated with the physical partitions of the provisionally-deleted volume. Additionally or alternatively, the volumes can be renumbered when provisionally deleting a volume.

A given provisionally-deleted logical volume may be deleted permanently by processor52. Subject to certain restrictions that are described further below, physical partitions of a permanently-deleted volume may be released for use and may be reallocated to new volumes or for any other purpose. Thus, a permanently-deleted volume cannot be recovered by the user and its data is lost.

In some embodiments, processor52may delete a given volume permanently when disks44do not have a sufficient number of free physical partitions for allocating to new volumes. For example, assume a scenario in which processor52is requested to create a new logical volume (or increase the size of an existing volume), but does not have a sufficient number of physical partitions in disks44in order to do so. In such a case, the processor may select one or more provisionally-deleted volumes, delete them permanently and reallocate their physical partitions to the volume being created or resized.

When using thinly-provisioned volumes, however, the task of permanently deleting a volume becomes complicated, since a given physical partition may be used by multiple volumes. Simply releasing the physical partitions of a given provisionally-deleted volume may damage other volumes (which may be valid of provisionally deleted) that share some of the physical partitions of the deleted volume.

In view of the difficulties described above, embodiments of the present invention provide methods and systems for managing thinly-provisioned logical volumes and snapshots. The methods and systems described herein enable both provisional and permanent deletion of thinly-provisioned volumes and snapshots, such as for releasing physical partitions for reallocation to new volumes.

In some embodiments, processor52frees memory space in disks44by identifying provisionally-deleted volumes, which have private physical partitions. The term “private physical partition” refers to a physical partition that is used by only a single logical volume. As can be appreciated, a private physical partition of a provisionally-deleted volume can be released without risk of damaging other volumes. The logical volume that uses this physical partition is deleted permanently, but this deletion does not affect other (valid or provisionally-deleted) volumes.

FIG. 2is a flow chart that schematically illustrates a method for freeing disk partitions for creating a thinly-provisioned logical volume, in accordance with an embodiment of the present invention. The method begins with processor52accepting a request to create a new logical volume, at a request accepting step90. The request typically comprises a requested size of the volume.

Processor52checks whether sufficient free disk space is available in disks44for creating the new volume, at a free space checking step94. If sufficient disk space is available, processor52creates the requested volume, at a volume creation step96, and the method terminates.

Otherwise, processor52attempts to free physical partitions that are used by provisionally-deleted volumes, in order to reallocate these physical partitions to the new volume. Processor52identifies provisionally-deleted volumes having at least one private physical partition, at a candidate identification step98. As explained above, a provisionally-deleted volume having private physical partitions is likely to be a good candidate for permanent deletion, because releasing the private physical partitions does not affect other volumes.

Processor52may use various techniques for identifying provisionally-deleted volumes having private physical partitions. For example, when the processor maintains a reference-count list indicating the number of logical volumes that use each physical partition, the processor can identify physical partitions whose reference count is “1” as private physical partitions. In some embodiments, processor52represents the logical volumes using a hierarchical tree data structure, in which private physical partitions can be identified in a straightforward manner. These embodiments are described in detail further below.

In some embodiments, processor52selects a subset of the provisionally-deleted volumes having private physical partitions, in accordance with certain predefined criteria. The criteria may depend on the properties of the identified candidate volumes and/or on the requested size of the new volume. For example, processor52may choose the oldest provisionally-deleted volumes (e.g., the logical volumes having the oldest provisional deletion time), assuming that permanent deletion of such volumes will have minimal impact on the system. Additionally or alternatively, the processor may choose the provisionally-deleted volumes having the highest numbers of private physical partitions, so that a relatively small number of volumes will need to be permanently deleted in order to release the requested number of physical partitions. Further additionally or alternatively, processor52may apply any other suitable criteria for selecting a subset of the provisionally-deleted volumes having private physical partitions as candidates for permanent deletion.

In some embodiments, processor52first verifies that it is possible to release the requested number of physical partitions. If, for example, processor52determines that the entire list of provisionally-deleted volumes does not contain a sufficient number of private physical partitions, the processor may deny the request and return an error (“disk full”) message.

At this stage, processor52has selected a subset of one or more provisionally-deleted logical volumes, each of which has at least one private physical partition that is not used by any other volume. These provisionally-deleted volumes are to be deleted permanently, and their private physical partitions released and reallocated to the new volume.

Processor52releases the private physical partitions of the provisionally-deleted volumes in the subset, at a releasing step102. Note that although the logical volumes in the selected subset will be permanently deleted, the processor does not release all of the physical partitions used by these volumes, but only the private physical partitions. As explained above, releasing non-private physical partitions may damage other volumes.

Processor52updates the reference-count list, at a reference count updating step106. The reference-count list is updated to indicate the updated number of volumes that use each physical partition, after permanent deletion of the provisionally-deleted volumes selected at step98above. For each volume that is permanently deleted, processor52decrements the reference count of each physical partition used by the volume. For private physical partitions (i.e., physical partitions whose reference count was “1” before updating the list), processor52removes these physical partitions from the reference-count list and moves them to the list of free physical partitions. The released physical partitions are now free and can be allocated to the new volume. Processor52permanently deletes the provisionally-deleted volumes in the subset (the volumes selected at step98above), at a permanent deletion step110.

At this stage, processor52has released a sufficient number of physical partitions for allocating to the new volume. The method thus moves to volume creation step96above, in which processor52creates the new volume using the released physical partitions.

Although the method ofFIG. 2refers to creation of a new logical volume, the method can also be used for allocating additional physical partitions to an existing volume, or for any other suitable task that involves allocating physical partitions to a volume. For example, when a certain physical disk fails, physical partitions that were originally stored on this disk may be reallocated to other disks. In such a scenario, the methods and systems described herein can be used for freeing disk space on another disk for storage of the reallocated partitions.

Moreover, in some cases disks44may have some free physical partitions, but less than the requested number. In such cases, processor52may allocate some physical partitions out of the free physical partitions, and release additional physical partitions using the method ofFIG. 2. As noted above, the method ofFIG. 2is equally applicable to logical volumes and to snapshots.

Permanent Deletion of Thinly-Provisioned Logical Volumes Using a Hierarchical Data Structure

In some embodiments, processor52represents a set of thinly-provisioned logical volumes and/or snapshots using a hierarchical data structure, i.e., a tree structure. (Again, the description that follows addresses logical volumes for the sake of clarity, but the disclosed data structures and techniques are equally applicable to snapshots.)

The logical volumes are represented by nodes of the tree. Each node has a set of pointers to a (possibly empty) set of pages (physical partitions). The pointers specified in a given node are referred to as the local pointers or local physical partitions of the node. The volumes populate the tree so that each volume uses its local physical partitions, and the physical partitions of its parents. In other words, each volume uses its own local physical partitions, and the physical partitions that are pointed to by the nodes along the path that connect it to the root. This tree representation is efficient, since it exploits the inherent commonality in physical partitions among different volumes. Physical partitions that are used by multiple volumes are located at high levels of the tree, instead of duplicating them in multiple individual snapshots.

In some embodiments, the tree comprises a binary tree, i.e., each node is either a leaf having no lower-level nodes or has exactly two lower-level nodes. In these embodiments, the volumes populate only the leaves of the tree. Higher-level nodes comprise virtual nodes that are referred to as meta-volumes (MV) or artificial nodes. The meta-volumes are not associated with volumes. Each node, including the leaves (representing the volumes) and the meta-volumes, has a corresponding (possibly empty) set of local pointers to physical partitions on disks44.

The use of the tree structure for performing deletion operations on logical volumes and snapshots is demonstrated inFIG. 3below. Further aspects of using hierarchical data structures for representing logical volumes and snapshots are addressed, for example, in U.S. Patent Application Publications 2006/0253670 and 2006/0253681.

FIG. 3is a diagram that schematically illustrates a process for deleting logical volumes represented by a hierarchical data structure, in accordance with an embodiment of the present invention. The left hand side ofFIG. 3shows a binary tree representation of three logical volumes denoted V1. . . V3, which are represented by tree nodes60A . . .60C, respectively. Volumes V1. . . V3have respective sets of local pointers64A . . .64C. Each set of local pointers point to physical partitions in disks44that are used by the respective volume. The binary tree structure further comprises two meta-volume nodes68A and68B, denoted MV1and MV2, respectively. Meta-volume nodes68A and68B have local pointers72A and72B, respectively.

The tree structure is constructed such that each volume (node) uses the physical partitions that are pointed to by the local pointers of the node itself and by its parent nodes. For example, volume V1uses the physical partitions pointed to by pointers64A of node60A and the physical partitions pointed to by pointers72A of meta-volume node68A. Similarly, volume V2uses the physical partitions pointed to by pointers64B of node60B, the physical partitions pointed to by pointers72B of meta-volume node68B and the physical partitions pointed to by pointers72A of meta-volume node68A.

Typically, the local pointers of a given node point to the private physical partitions of the node, i.e., to the physical partitions that are used exclusively by the node. Non-private physical partitions would typically populate higher-level nodes in the tree. Thus, processor52can query the local pointers of the different tree nodes so as to identify volumes having private physical partitions (e.g., in order to select candidate volumes for permanent deletion when freeing disk space—see step98of the method ofFIG. 2above). For example, processor52can identify nodes having non-empty sets of local pointers as representing logical volumes having private physical partitions. Processor52can obtain additional information regarding the private physical partitions from the tree structure, such as the number of private physical partitions a given volume. This information may also assist the processor is selecting candidate volumes for deletion.

When processor52deleted a certain volume permanently (e.g., for releasing disk space using the method ofFIG. 2above), the processor may delete the node representing the permanently-deleted volume. This deletion leaves parent of the deleted node with only one lower-level node. Thus, processor52merges the local pointers of the remaining lower-level node with the local pointers of its parent meta-volume node. This process is demonstrated on the right hand side ofFIG. 3.

The right hand side ofFIG. 3shows a process of permanently deleting volume V3from the tree structure, in accordance with an embodiment of the present invention. In the present example, processor52deletes V3permanently by performing the following steps:Delete node60C that represents V3from the tree structure. This deletion leaves meta-volume node68B (MV2) with only one son (node60B representing V2).Merge node60B with meta-volume node68B, to produce a new leaf node76. Node76now represents volume V2.Combine the local pointers of the two merged nodes (i.e., combine local pointers64B of node60B with local pointers72B of node68B) to produce local pointers80of the new node76that represents V2. (In some embodiments, the combining operation may be relatively slow, e.g., on the order of several seconds. In these embodiments, combining may be performed as a background task, since it does not create new free storage space.)Traverse the tree upwards towards the root, and update the volume count of each parent node. (Typically, a volume count is maintained by a given parent node to identify situations in which a shared partition is no longer referenced by any of the node's children and can therefore be deleted.)

In some embodiments, processor52maintains a table or other data structure, which indicates for each logical volume or snapshot whether it is provisionally-deleted or not. The following table demonstrates a possible implementation of such a table:

In this example, volume V1is provisionally deleted and is typically not visible to the user. Volumes V2and V3are not provisionally deleted (i.e., they are valid and visible to the user). If, for example, a user provisionally deleted logical volume V2as some stage, processor52changes the status of this volume in the table from FALSE to TRUE. Alternatively, processor52may use any other suitable implementation or data structure for this purpose.

The embodiments described herein refer to releasing physical partitions in response to a request to allocate partitions to a logical volume. The methods and systems described herein can be used, however, for freeing physical storage space for any other purpose and/or in response to any other trigger or event.

Although the embodiments described above mainly address releasing disk space for allocation to logical volumes, the methods and systems described herein can also be used in other applications, such as in managing snapshots of files in file-systems that support thin provisioning of large files.