Selection and placement of volumes in a storage system using stripes

Patent metadata

Field	Value
Publication number	US-11048627-B2
Application number	US-201916457762-A
Country	US
Kind code	B2
Filing date	Jun 28, 2019
Priority date	Nov 10, 2015
Publication date	Jun 29, 2021
Grant date	Jun 29, 2021

Abstract

Provided are a computer program product, system, and method for determining the location for volumes of data being initially stored within a storage space, regardless of the physical location of the data. The storage space includes stripes composed of volumes, which can be logically represented as a utilization histogram of stripe locations offset from one another. Sometime the stripes are fully allocated with one large volume or partially allocated with multiple, arbitrary-sized smaller volumes. When there are multiple smaller volumes that do not utilize all of the available stripe space, gaps form. To minimize the creation of such gaps, when a volume of data is initially stored, a start location to place the volume of data is selected by using selection criteria as guidance.

First claim

What is claimed is:

1. A computer program product comprising a computer readable storage medium having program instructions executed by a processor to perform operations, the operations comprising:
generating a utilization representation of used and free blocks in a storage space comprised of a plurality of storage devices in a storage system for placement of a storage volume to be stored across the storage devices, wherein the storage volume can be placed starting at offset locations, wherein the utilization representation indicates free space in stripes configured in the storage space that extend across the storage devices, wherein each stripe is represented as a range of contiguous spaces in a row, and wherein spaces for a stripe at an end of a row wrap to a beginning of a next higher row in the utilization representation;
for a plurality of possible starting offsets indicated in the utilization representation, selecting one possible starting offset at which to place blocks of the storage volume that minimizes a number of gaps in the storage space according to a criteria that would result from placement of the storage volume at the possible starting offset, wherein a gap comprises free space between used space;
initiating volume placement at the selected possible starting offset; and
selecting free spaces from contiguous columns of the utilization representation from the selected possible starting offset having free spaces to select the blocks of the storage volume.

2. The computer program product of claim 1 , wherein the utilization representation comprises a histogram of rows of used and free blocks, each row has zero or more free blocks, and offset locations are assigned to the free blocks, wherein selecting one of the possible starting offsets to minimize the number of gaps comprises placing contiguous blocks of the storage volume at contiguous offsets of free blocks represented in at least two different rows of the histogram.

3. The computer program product of claim 1 , wherein the utilization representation comprises a utilization histogram, wherein the selecting one of the possible starting offsets comprises selecting one of the possible starting offsets to satisfy at least one criteria comprising:
preventing peaks of storage blocks in the utilization histogram;
reducing a number of edges between storage blocks in the utilization histogram; and
filling a lowest unallocated storage space in the utilization histogram.

4. The computer program product of claim 1 , wherein an allocated storage space includes at least one stripe having at least one allocated volume, the allocated volume being partitioned into data blocks.

5. The computer program product of claim 1 , wherein the operations further comprise:
receiving a request to add a new volume comprising the storage volume, wherein the utilization representation is generated in response to receiving the request to add the new volume and based on already present volumes in the storage space.

6. The computer program product of claim 1 , wherein the operations further comprise:
determining a plurality of scores for each possible starting offset using different criteria to minimize the number of gaps; and
for each of the possible starting offsets, combining the scores to form an overall score, wherein the selecting the possible starting offset comprises selecting the possible starting offset at which to start storing the storage volume according to a highest overall score.

7. The computer program product of claim 1 , wherein the utilization representation includes a plurality of rows of used and free blocks and vertical columns extending through the rows, wherein selecting one of the possible starting offsets at which to place the blocks of the storage volume that minimizes the number of gaps in the storage space that satisfy a criteria comprises selecting the possible offset that avoids decreasing a number of units of free space in a most utilized vertical column.

8. A system for managing storage volumes of a storage system, comprising:
a processor; and
a computer readable storage medium including program instructions executed by the processor to perform operations, the operations comprising:
generating a utilization representation of used and free blocks in a storage space comprised of a plurality of storage devices in a storage system for placement of a storage volume to be stored across the storage devices, wherein the storage volume can be placed starting at offset locations, wherein the utilization representation indicates free space in stripes configured in the storage space that extend across the storage devices, wherein each stripe is represented as a range of contiguous spaces in a row, and wherein spaces for a stripe at an end of a row wrap to a beginning of a next higher row in the utilization representation;
for a plurality of possible starting offsets indicated in the utilization representation, selecting one possible starting offset at which to place blocks of the storage volume that minimizes a number of gaps in the storage space according to a criteria that would result from placement of the storage volume at the possible starting offset, wherein a gap comprises free space between used space;

initiating volume placement at the selected possible starting offset; and
selecting free spaces from contiguous columns of the utilization representation from the selected possible starting offset having free spaces to select the blocks of the storage volume.

9. The system of claim 8 , wherein the utilization representation comprises a histogram of rows of used and free blocks, each row has zero or more free blocks, and offset locations are assigned to the free blocks, wherein selecting one of the possible starting offsets to minimize the number of gaps comprises placing contiguous blocks of the storage volume at contiguous offsets of free blocks represented in at least two different rows of the histogram.

10. The system of claim 8 , wherein the utilization representation comprises a utilization histogram, wherein the selecting one of the possible starting offsets comprises selecting one of the possible starting offsets to satisfy at least one criteria comprising:
preventing peaks of storage blocks in the utilization histogram;
reducing a number of edges between storage blocks in the utilization histogram; and
filling a lowest unallocated storage space in the utilization histogram.

11. The system of claim 8 , wherein an allocated storage space includes at least one stripe having at least one allocated volume, the allocated volume being partitioned into data blocks.

12. The system of claim 8 , wherein the operations further comprise:
receiving a request to add a new volume comprising the storage volume, wherein the utilization representation is generated in response to receiving the request to add the new volume and based on already present volumes in the storage space.

13. The system of claim 8 , wherein the operations further comprise:
determining a plurality of scores for each possible starting offset using different criteria to minimize the number of gaps; and
for each of the possible starting offsets, combining the scores to form an overall score, wherein the selecting the possible starting offset comprises selecting the possible starting offset at which to start storing the storage volume according to a highest overall score.

14. The system of claim 8 , wherein the utilization representation includes a plurality of rows of used and free blocks and vertical columns extending through the rows, wherein selecting one of the possible starting offsets at whic

Assignees

• IBM

Inventors

• Keller Michael

Classifications

• G06F12/0653 Primary

  with centralised address assignment · CPC title

• G06F11/34

  Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation {; Recording or statistical evaluation of user activity, e.g. usability assessment} · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G06F2212/261

  Storage comprising a plurality of storage devices · CPC title