Inline coalescing of file system free space

Patent metadata

Field	Value
Publication number	US-10942845-B2
Application number	US-201815883701-A
Country	US
Kind code	B2
Filing date	Jan 30, 2018
Priority date	Jan 30, 2018
Publication date	Mar 9, 2021
Grant date	Mar 9, 2021

Abstract

An in-line (or foreground) approach to obtaining contiguous ranges of free space in a file system of a data storage system that can select windows having blocks suitable for relocation at a time when one or more blocks within the respective windows are freed or de-allocated. By providing the in-line or foreground approach to obtaining contiguous ranges of free space in a file system, a more efficient determination of windows having blocks suitable for relocation can be achieved, thereby conserving processing resources of the data storage system.

First claim

What is claimed is:

1. In a data storage system, a method of obtaining at least one contiguous range of free space, comprising:
performing a background process to obtain at least one contiguous range of free space, the background process comprising:
identifying one or more allocated blocks in one or more windows of a cache; and
relocating and de-allocating the one or more allocated blocks in the one or more windows to evacuate the one or more windows and obtain one or more contiguous ranges of free space; and

supplementing the background process with a foreground process to obtain at least one additional contiguous range of free space, the foreground process comprising:
receiving a first write request;
in response to the first write request, writing one or more first blocks as log structured data to a first window of the cache;
de-allocating one or more blocks previously written as log structured data to a previous window of the cache, the one or more previously written blocks corresponding to the one or more first blocks, respectively;
at a time when the one or more previously written blocks are de-allocated, proactively determining whether the previous window includes a number of remaining allocated blocks that is less than a first predetermined threshold value; and
having proactively determined that the previous window includes a number of remaining allocated blocks that is less than the first predetermined threshold value, relocating and de-allocating the remaining allocated blocks to evacuate the previous window and obtain the at least one additional contiguous range of free space.

2. The method of claim 1 wherein the identifying of the one or more allocated blocks includes determining whether a net number of the one or more windows of the cache exceeds a second predetermined threshold value.

3. The method of claim 2 wherein the identifying of the one or more allocated blocks is performed subsequent to determining that the net number of the one or more windows of the cache exceeds the second predetermined threshold value.

4. The method of claim 1 wherein the writing of the one or more first blocks includes sequentially writing the one or more first blocks to a head of a log corresponding to the first window of the cache.

5. A data storage system, comprising:
a memory;
a cache; and
a storage processor configured to execute instructions out of the memory to:
perform a background process to obtain at least one contiguous range of free space, the background process comprising:
identifying one or more allocated blocks in one or more windows of a cache; and
relocating and de-allocating the one or more allocated blocks in the one or more windows to evacuate the one or more windows and obtain one or more contiguous ranges of free space; and

supplement the background process with a foreground process to obtain at least one additional contiguous range of free space, the foreground process comprising:
receiving a first write request;
in response to the first write request, writing one or more first blocks as log structured data to a first window of the cache;
de-allocating one or more blocks previously written as log structured data to a previous window of the cache, the one or more previously written blocks corresponding to the one or more first blocks, respectively;
at a time when the one or more previously written blocks are de-allocated, proactively determining whether the previous window includes a number of remaining allocated blocks that is less than a first predetermined threshold value; and
having proactively determined that the previous window includes a number of remaining allocated blocks that is less than the first predetermined threshold value, relocating and de-allocating the remaining allocated blocks to evacuate the previous window and obtain the at least one additional contiguous range of free space.

6. The data storage system of claim 5 further comprising:
a storage pool including a plurality of slices of data storage.

7. The data storage system of claim 5 wherein the storage processor is further configured to execute the instructions out of the memory:
to determine, in the background process, whether a net number of the one or more windows of the cache exceeds a second predetermined threshold value.

8. The data storage system of claim 7 wherein the storage processor is further configured to execute the of instructions out of the memory:
to perform, in the background process, the identifying of the one or more allocated blocks subsequent to determining that the net number of the one or more windows of the cache exceeds the second predetermined threshold value.

9. The data storage system of claim 5 wherein the storage processor is further configured to execute the first set of instructions:
to sequentially write the one or more first blocks to a head of a log corresponding to the first window of the cache.

10. A computer program product having a non-transitory computer readable medium that stores a set of instructions that, when carried out by computerized circuitry, cause the computerized circuitry to perform a method of obtaining at least one contiguous range of free space in a data storage system, the method comprising:
performing a background process to obtain at least one contiguous range of free space, the background process comprising:
identifying one or more allocated blocks in one or more windows of a cache; and
relocating and de-allocating the one or more allocated blocks in the one or more windows to evacuate the one or more windows and obtain one or more contiguous ranges of free space; and

supplementing the background process with a foreground process to obtain at least one additional contiguous range of free space, the foreground process comprising:
receiving a first write request;
in response to the first write request, writing one or more first blocks as log structured data to a first window of the cache;
de-allocating one or more blocks previously written as log structured data to a previous window of the cache, the one or more previously written blocks corresponding to the one or more first blocks, respectively;
at a time when the one or more previously written blocks are de-allocated, proactively determining whether the previous window includes a number of remaining allocated blocks that is less than a first predetermined threshold value; and
having proactively determined that the previous window includes a number of remaining allocated blocks that is less than the first predetermined threshold value,
relocating and de-allocating the remaining allocated blocks to evacuate the previous window and obtain the at least one additional contiguous range of free space.

11. The method of claim 10 wherein the identifying of the one or more allocated blocks includes determining whether a net number of the one or more windows of the cache exceeds a second predetermined threshold value.

12. The method of claim 1 further comprising:
having evacuated the previous window, proactively determining whether a window of the cache adjacent to the previous window has a number of allocated blocks that is less than the first predetermined threshold value.

13. The method of claim 12 further comprising:
having proactively determined that a window of the cache adjacent to the previous window has a number of allocated blocks that is less than the first predetermined threshold value, evacuating the window of the cache adjacent to the previous window to obtain an increased contiguous range of free space that includes the evacuated previous window and the evacuated window of the cache adjacent

Assignees

• Emc Ip Holding Co Llc

Inventors

• Chawla Rohit
• Rashid Ahsan
• Nanda Kumari Bijayalaxmi
• Mathews Alexander S

Classifications

• G06F11/1076 Primary

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

• G06F2212/262

  configured as RAID · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F12/0238 Primary

  Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory · CPC title

• G06F12/121

  using replacement algorithms · CPC title