Relocating compressed extents using file-system hole list

• US 10,762,047 B2
• Filed: 10/31/2018
• Issued: 09/01/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Armangau, Philippe, Karri, Ajay, Chaudhary, Monica, Daniel, Alexander
• Primary Examiner(s): Portka, Gary J
• Application Number:
  US16/176,767
• Publication Number:
  US 20200134045A1
• Time in Patent Office: 671 Days
• Field of Search: 707693, 710 68, 711165, 711171
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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/1847 specifically adapted to static storage, e.g. adapted to flash memory or SSD
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

A technique for writing data in a file system includes aggregating data received in a set of I/O requests into a batch that includes multiple extents of data. After compressing a current extent of the batch and determining that the compressed extent does not fit in a space where a previous version of the extent is stored, the technique performs an FS-relocate operation by accessing an F S-hole list provided for the file system and selecting a hole, from the FS-relocate list, which is large enough to accommodate the compressed extent. The technique then places the compressed extent in the selected hole.

Claims

1. A method of writing data in a data storage system, the method comprising:

aggregating a set of data received in I/O (Input/Output) requests into a batch of data, the batch of data including multiple extents, each extent directed to a respective logical address in a file system running in the data storage system;

compressing a current extent of the batch of data to produce a compressed extent, the current extent directed to a logical address that is already backed by a fragment in the data storage system, such that a write of the compressed extent is an overwrite; and

performing an FS-relocate operation, the FS-relocate operation (i) accessing an FS-hole list provided for the file system to select a hole large enough to accommodate the compressed extent, each hole in the FS-hole list representing a range of storage in the file system that contains no currently-valid data, and (ii) placing the compressed extent into the selected hole found in the FS-hole list,

wherein the FS-hole list contains multiple queues, each queue specifying a respective set of holes of a respective size, and wherein selecting a hole large enough to accommodate the compressed extent includes (i) selecting, based on a size of the compressed extent, the queue that specifies holes that are minimally large enough to accommodate the compressed extent, and (ii) identifying one of the holes from the selected queue as the selected hole.

2. The method of claim 1, wherein the FS-relocate operation is performed in response to first determining that the compressed extent does not fit into a space that the fragment already occupies.

3. The method of claim 2, wherein the FS-relocate operation is performed in response to first determining that no hole large enough to accommodate the compressed extent is contained in a batch-hole list, the batch-hole list formed by (i) obtaining a set of mapping metadata that maps all of the extents in the batch of data, (ii) identifying a set of holes pointed to by the set of mapping metadata, and (iii) adding each of the identified set of holes to the batch-hole list.

4. The method of claim 1, wherein each size of holes for which the queues are provided is an integer multiple of one sector (512 Bytes).

5. The method of claim 1, wherein the queues include first through N-th queues provided for holes of sizes ranging from one through N sectors, respectively, wherein the method further comprises limiting a maximum number of holes in each queue, and wherein the maximum number of holes for each of the first and N-th queues is not greater than the maximum number of holes for each of the second through (N−

1)-th queues.

6. The method of claim 1, wherein each of the queues in the FS-hole list has a head and a tail, and wherein, when selecting the hole into which to place the compressed extent includes selecting the hole at the head of the selected queue.

7. The method of claim 6, further comprising:

discovering a new hole in the file system;

identifying a queue into which to place the new hole based on a size of the new hole; and

adding the new hole to the tail of the selected queue.

8. The method of claim 7, further comprising, prior to selecting the hole in the FS-hole list:

identifying an initial hole into which to place the compressed extent, the initial hole specified at the head of a current queue in the FS-hole list;

performing a testing operation configured to produce a first result in response to confirming that a set of mapping metadata for the initial hole currently resides in volatile-memory cache, and to produce a second result otherwise; and

in response to the testing operation producing the second result, (i) removing the initial hole from the head of the current queue and from the FS-hole list, and (ii) identifying a next hole in the current queue now at the head of the selected queue, the next hole providing the selected hole into which the compressed extent is placed.

9. The method of claim 7, further comprising, prior to identifying the hole in the FS-hole list:

identifying an initial hole into which to place the compressed extent, the initial hole specified at the head of a current queue in the FS-hole list;

performing a second testing operation configured to produce a first result in response to confirming that a set of mapping metadata for the initial hole is unlocked, and to produce a second result otherwise; and

in response to the testing operation producing the second result, (i) moving the initial hole from the head of the current queue to the tail of the current queue, and (ii) identifying a next hole in the current queue now at the head of the selected queue, the next hole providing the selected hole into which the compressed extent is placed.

10. The method of claim 1, further comprising, prior to placing the compressed extent into the selected hole in the FS-hole list:

accessing a set of mapping metadata that maps the selected hole;

identifying, from the accessed set of mapping metadata, a set of additional holes referenced in the accessed set of mapping metadata; and

adding the set of additional holes to the batch-hole list.

11. The method of claim 1, further comprising, in response to determining that the compressed extent does not fit into the space that the fragment already occupies, adding the space that the fragment occupies to the FS-hole list.

12. The method of claim 1, further comprising, in response to determining that the compressed extent does not fit into the space that the fragment already occupies, adding the space that the fragment occupies to the FS-hole list.

13. A data storage system, comprising control circuitry that includes a set of processing units coupled to memory, the control circuitry constructed and arranged to:

aggregate a set of data received in I/O (Input/Output) requests into a batch of data, the batch of data including multiple extents, each extent directed to a respective logical address in a file system running in the data storage system;

compress a current extent of the batch of data to produce a compressed extent, the current extent directed to a logical address that is already backed by a fragment in the data storage system, such that a write of the compressed extent is an overwrite; and

perform an FS-relocate operation, the FS-relocate operation (i) accessing an FS-hole list provided for the file system to select a hole large enough to accommodate the compressed extent, each hole in the FS-hole list representing a range of storage in the file system that contains no currently-valid data, and (ii) placing the compressed extent into the selected hole found in the FS-hole list,

wherein the control circuitry is constructed and arranged to perform the FS-relocate operation in response to first determining that no hole large enough to accommodate the compressed extent is contained in a batch-hole list, the batch-hole list formed by (i) obtaining a set of mapping metadata that maps all of the extents in the batch of data, (ii) identifying a set of holes pointed to by the set of mapping metadata, and (iii) adding each of the identified set of holes to the batch-hole list.

14. A computer program product including a set of non-transitory, computer-readable media having instructions which, when executed by control circuitry of a data storage system, cause the control circuitry to perform a method for writing data, the method comprising:

aggregating a set of data received in I/O (Input/Output) requests into a batch of data, the batch of data including multiple extents, each extent directed to a respective logical address in a file system running in the data storage system;

compressing a current extent of the batch of data to produce a compressed extent, the current extent directed to a logical address that is already backed by a fragment in the data storage system, such that a write of the compressed extent is an overwrite; and

performing an FS-relocate operation, the FS-relocate operation (i) accessing an FS-hole list provided for the file system to select a hole large enough to accommodate the compressed extent, each hole in the FS-hole list representing a range of storage in the file system that contains no currently-valid data, and (ii) placing the compressed extent into the selected hole found in the FS-hole list,

wherein the FS-hole list contains multiple queues, each queue specifying a respective set of holes of a respective size, and wherein selecting a hole large enough to accommodate the compressed extent includes (i) selecting, based on a size of the compressed extent, the queue that specifies holes that are minimally large enough to accommodate the compressed extent, and (ii) identifying one of the holes from the selected queue as the selected hole.

15. The computer program product of claim 14, wherein each size of holes for which the queues are provided is an integer multiple of one sector (512 Bytes).

16. The computer program product of claim 15, wherein the method further comprises, prior to selecting the hole in the FS-hole list:

identifying an initial hole into which to place the compressed extent, the initial hole specified at the head of a current queue in the FS-hole list;

performing a testing operation configured to produce a first result in response to confirming that a set of mapping metadata for the initial hole currently resides in volatile-memory cache, and to produce a second result otherwise; and

in response to the testing operation producing the second result, (i) removing the initial hole from the head of the current queue and from the FS-hole list, and (ii) identifying a next hole in the current queue now at the head of the selected queue, the next hole providing the selected hole into which the compressed extent is placed.

17. The computer program product of claim 14, wherein the method further comprises, prior to placing the compressed extent into the selected hole in the FS-hole list:

accessing a set of mapping metadata that maps the selected hole;

identifying, from the accessed set of mapping metadata, a set of additional holes referenced in the accessed set of mapping metadata; and

adding the set of additional holes to the batch-hole list.