Inline garbage collection for log-structured file systems

Patent metadata

Field	Value
Publication number	US-9747298-B2
Application number	US-201414268698-A
Country	US
Kind code	B2
Filing date	May 2, 2014
Priority date	May 2, 2014
Publication date	Aug 29, 2017
Grant date	Aug 29, 2017

Abstract

Exemplary methods, apparatuses, and systems receive a command to overwrite or delete data stored within an allocated portion of a file system. In response to the command, an entry is added to a first data structure. A write command is received. The portion of the file system added to the first data structure is formatted for reallocation. In performance of the write command, the portion of the file system is reallocated. Portions of the file system are allocated from a second data structure when the second data structure includes a sufficient amount of space to satisfy the write command and from the first data structure when the second data structure does not include a sufficient amount of space. The second data structure includes free portions of the file system that have been formatted for allocation. The first data structure includes free portions that have yet to be formatted.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a command to overwrite or delete data stored within an allocated portion of a file system;
adding, in response to the overwrite or delete command, an entry in a first data structure indicating that the allocated portion of the file system is to be reallocated, wherein the first data structure includes entries identifying free space of the file system that has yet to be formatted for allocation;
receiving a write command to write data to the file system;
determining that a second data structure indicates an insufficient amount of formatted free space within the file system to satisfy the write command, wherein the second data structure includes entries identifying free space of the file system that has been formatted for allocation; and
in response to determining that the second data structure indicates the insufficient amount of formatted free space within the file system to satisfy the write command,
formatting the portion of the file system that was added to the first data structure, and
allocating, in performance of the write command, the portion of the file system that was added to the first data structure, wherein portions of the file system are allocated from the second data structure when the second data structure includes a sufficient amount of formatted free space within the file system to satisfy the write command and from the first data structure when the second data structure indicates an insufficient amount of formatted free space within the file system to satisfy the write command.

2. The computer-implemented method of claim 1 , wherein the portion of the file system allocated from the first data structure is formatted in response to the write command.

3. The computer-implemented method of claim 1 , further comprising:
receiving a second write command to write data to the file system;
determining that the second data structure indicates a sufficient amount of formatted free space within the file system to satisfy the second write command; and
in response to determining that the second data structure indicates the sufficient amount of formatted free space within the file system to satisfy the second write command, allocating a second portion of the file system from the second data structure, wherein the second portion of the file system is formatted in response to a threshold trigger and the formatted second portion of the file system is moved to the second data structure prior to receiving the second write command.

4. The computer-implemented method of claim 3 , wherein the threshold trigger is a determination that the first data structure accounts for a threshold amount of space within the file system.

5. The computer-implemented method of claim 3 , wherein the threshold trigger is a determination that a portion of the first data structure accounts for a threshold amount of contiguous space within the file system.

6. The computer-implemented method of claim 1 , wherein the second data structure is maintained within volatile memory and reconstructed within volatile memory each time a device utilizing the file system is started.

7. The computer-implemented method of claim 1 , wherein the second data structure is maintained within non-volatile memory.

8. The computer-implemented method of claim 1 , wherein the second data structure and first data structure are implemented as a single data structure with entries in each of the first and second data structures differentiated by the presence or lack of a flag bit.

9. A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform a method comprising:
receiving a command to overwrite or delete data stored within an allocated portion of a file system;
adding, in response to the overwrite or delete command, an entry in a first data structure indicating that the allocated portion of the file system is to be reallocated, wherein the first data structure includes entries identifying free space of the file system that has yet to be formatted for allocation;
receiving a write command to write data to the file system;
determining that a second data structure indicates an insufficient amount of formatted free space within the file system to satisfy the write command, wherein the second data structure includes entries identifying free space of the file system that has been formatted for allocation; and
in response to determining that the second data structure indicates the insufficient amount of formatted free space within the file system to satisfy the write command,
formatting the portion of the file system that was added to the first data structure, and
allocating, in performance of the write command, the portion of the file system that was added to the first data structure, wherein portions of the file system are allocated from the second data structure when the second data structure includes a sufficient amount of formatted free space within the file system to satisfy the write command and from the first data structure when the second data structure indicates an insufficient amount of formatted free space within the file system to satisfy the write command.

10. The non-transitory computer-readable medium of claim 9 , wherein the portion of the file system allocated from the first data structure is formatted in response to the write command.

11. The non-transitory computer-readable medium of claim 9 , further comprising:
receiving a second write command to write data to the file system;
determining that the second data structure indicates a sufficient amount of formatted free space within the file system to satisfy the second write command; and in response to determining that the second data structure indicates the sufficient amount of formatted free space within the file system to satisfy the second write command, allocating a second portion of the file system is allocated from the second data structure, wherein the second portion of the file system is formatted in response to a threshold trigger and the formatted second portion of the file system is moved to the second data structure prior to receiving the second write command.

12. The non-transitory computer-readable medium of claim 11 , wherein the threshold trigger is a determination that the first data structure accounts for a threshold amount of space within the file system.

13. The non-transitory computer-readable medium of claim 11 , wherein the threshold trigger is a determination that a portion of the first data structure accounts for a threshold amount of contiguous space within the file system.

14. The non-transitory computer-readable medium of claim 9 , wherein the second data structure is maintained within volatile memory and reconstructed within volatile memory each time a device utilizing the file system is started.

15. The non-transitory computer-readable medium of claim 9 , wherein the second data structure is maintained within non-volatile memory.

16. The non-transitory computer-readable medium of claim 9 , wherein the second data structure and first data structure are implemented as a single data structure with entries in each of the first and second data structures differentiated by the presence or lack of a flag bit.

17. An apparatus comprising:
a processing device; and
a memory coupled to the processing device, the memory storing instructions which, when executed by the processing device, cause the apparatus to:
receive a command to overwrite or delete data stored within an allo

Assignees

• Vmware Inc

Inventors

• Bandarupalli Sambasiva Rao
• Yadappanavar Krishna
• Gondi Anjaneya Prasad
• Thota Kiran Kumar

Classifications

• G06F2212/702

  Conservative garbage collection · CPC title

• G06F16/1805 Primary

  Append-only file systems, e.g. using logs or journals to store data · CPC title

• G06F12/0269

  Incremental or concurrent garbage collection, e.g. in real-time systems (G06F12/0261 takes precedence) · CPC title

• G06F16/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 title

• G06F16/24565

  Triggers; Constraints · CPC title